. 2
( 2)

tions, and 20 bitwise rotations by ¬xed amounts AND
ten require more than just an AE scheme or an
on 32-bit words. So Helix is not simple to specify;
AEAD scheme: perhaps they require something
instead we give a high-level description.
that more resembles a network transport proto-
Helix keeps its “state” in ¬ve 32-bit registers
col. Desirable properties might include resistance
(the designers were thinking of the Intel family
to replay and prevention against packet loss or
of processors). The ith block of Helix emits one
packet reordering. In fact, protocols like SSH aim
32-bit word of key-stream Si , requires two 32-bit
to achieve precisely this.
words scheduled from K and N, and also requires
Work is currently underway to extend AE no-
the ith plaintext word Mi . It is highly unusual
tions to encompass a broader range of such
for a stream cipher to use the plaintext stream as
goals [27]. This is an extension to the SSH analy-
part of its key-stream generation, but this feature
sis referred to above [4], but considers the various
is what allows Helix to achieve authentication as
EtM, MtE, and E&M approaches rather than fo-
well as generating a key-stream.
cusing on just one. Such research is another step
As usual, the key-stream is used as a one-time
in closing the gap between what cryptographers
pad to encrypt the plaintext. In other words, the
ith ciphertext block Ci is simply Mi • Si . The produce and what consumers of cryptographic
protocols require. The hope is that we will reach
¬ve-word state resulting from block i is then fed
into block i + 1 and the process continues until the point where methods will be available to prac-
titioners which relieve them from inventing cryp-
we have a long enough key-stream to encrypt M.
tography (which, as we have seen, is a subtle
At this point, a constant is XORed into one of the
area with many insidious pitfalls) and yet allow
words of the resulting state, twelve more blocks
them easy access to provably secure cryptographic
are generated using a ¬xed plaintext word based
protocols. We anticipate further work in this
on the length of M, with the key-stream of the four
last blocks yielding the 128-bit authentication tag.

SOBER-128 NOTES REFERENCES: Note that AE and its
extensions continue to be an active area of re-
A competitor to Helix is an offering from Hawkes search. Therefore, many of the bibliographic ref-
and Rose called SOBER-128 [22]. This algorithm erences are currently to unpublished pre-prints
evolved from a family of simple stream ciphers of works in progress. It would be prudent for the
(i.e., ciphers which did not attempt simultaneous reader to look for more mature versions of many
authentication) called the SOBER family, the ¬rst of these research reports to obtain the latest revi-
of which was introduced in 1998 by Rose. SOBER- sions.
128 retains many of the characteristics of its
ancestors, but introduces a method for authenti- J. Black
20 Authenticated encryption

References [12] Black, J. and P. Rogaway (2000). “CBC MACs
for arbitrary-length messages: The three-key con-
structions.” Advances in Cryptology”CRYPTO
[1] Bellare, M., R. Canetti, and H. Krawczyk (1996).
2000, Lecture Notes in Computer Science, vol.
“Keying hash functions for message authentica-
1880, ed. M. Bellare. Springer-Verlag, Berlin.
tion.” Advances in Cryptology”CRYPTO™96, Lec-
[13] Black, J. and P. Rogaway (2002). “A block-
ture Notes in Computer Science, vol. 1109, ed. N.
cipher mode of operation for parallelizable mes-
Koblitz. Springer-Verlag, Berlin, 1“15.
sage authentication.” Advances in Cryptology”
[2] Bellare, M., A. Desai, D. Pointcheval, and P.
EUROCRYPT 2002, Lecture Notes in Computer
Rogaway (1998). “Relations among notions of se-
Science, vol. 2332, ed. L. Knudsen. Springer-
curity for public-key encryption schemes.” Ad-
Verlag, Berlin, 384“397.
vances in Cryptology”CRYPTO™98, Lecture Notes
[14] Black, J. and H. Urtubia (2002). “Side-channel at-
in Computer Science, vol. 1462, ed. H. Krawczyk.
tacks on symmetric encryption schemes: The case
Springer-Verlag, Berlin, 232“249.
for authenticated encryption.” Proceedings of the
[3] Bellare, M., J. Kilian, and P. Rogaway (2000).
Eleventh USENIX Security Symposium, August
“The security of the cipher block chaining
2002, ed. D. Boneh, 327“338.
message authentication code.” Journal of Com-
[15] Borisov, N., I. Goldberg, and D. Wagner (2001).
puter and System Sciences (JCSS), 61 (3)
“Intercepting mobile communications: The insecu-
362“399. Earlier version in CRYPTO™94. See
rity of 802.11.” MOBICOM. ACM Press, New York,
[4] Bellare, M., T. Kohno, and C. Namprempre (2002).
[16] Carter, L. and M. Wegman (1979). “Universal hash
“Authenticated encryption in SSH: Provably ¬xing
functions.” J. of Computer and System Sciences, 18,
the SSH binary packet protocol.” ACM Conference
on Computer and Communications Security (CCS-
[17] Ferguson, N., D. Whiting, B. Schneier, J. Kelsey,
9). ACM Press, New York, 1“11.
S. Lucks, and T. Kohno (2003). “Helix: Fast en-
[5] Bellare, M. and C. Namprempre (2000). “Authen-
cryption and authentication in a single crypto-
ticated encryption: Relations among notions and
graphic primitive.” Fast Software Encryption, 10th
analysis of the generic composition paradigm.”
International Workshop, FSE 2003, Lecture Notes
Advances in Cryptology”ASIACRYPT 2000, Lec-
in Computer Science, vol. 2887, ed. T. Johansson.
ture Notes in Computer Science, vol. 1976, ed. T.
Springer-Verlag, Berlin.
Okamoto. Springer-Verlag, Berlin.
[18] Gligor, V. and P. Donescu (2002). “Fast encryp-
[6] Bellare, M. and P. Rogaway (2000). “Encode-then-
tion and authentication: XCBC encryption and
encipher encryption: How to exploit nonces or re-
XECB authentication modes.” Fast Software En-
dundancy in plaintexts for ef¬cient encryption.”
cryption, 8th International Workshop, FSE 2001,
Advances in Cryptology”ASIACRYPT 2000, Lec-
Lecture Notes in Computer Science, vol. 2355, ed.
ture Notes in Computer Science, vol. 1976, ed.
M. Matsui. Springer-Verlag, Berlin, 92“108. See
T. Okamoto. Springer-Verlag, Berlin, 317“330. See
www.cs.ucdavis.edu/ ˜rogaway
[19] Goldwasser, S., S. Micali, and R. Rivest (1998). “A
[7] Bellare, M., P. Rogaway, and D. Wagner (2003).
digital signature scheme secure against adaptive
“EAX: A conventional authenticated-encryption
chosen-message attacks.” SIAM Journal of Com-
mode.” Cryptology ePrint archive, reference num-
puting, 17 (2), 281“308.
ber 2003/069, submitted April 13, 2003, revised
[20] Krawczyk, H., M. Bellare, and R. Canetti (1997).
September 9, 2003. See eprint.iacr.org
“HMAC: Keyed hashing for message authentica-
[8] Bellovin, S. (1996). “Problem areas for the IP secu-
tion.” IETF RFC-2104.
rity protocols.” Proceedings of the Sixth USENIX
[21] Halevi, S. (2001). “An observation regarding Jutla™s
Security Symposium, July 1996, 1“16.
modes of operation.” Cryptology ePrint archive,
[9] Berendschot, A., B. den Boer, J. Boly, A. Bosse-
˚ reference number 2001/015, submitted Febru-
laers, J. Brandt, D. Chaum, I. Damgard, M. Dichtl,
ary 22, 2001, revised April 2, 2001. See eprint.iacr
W. Fumy, M. van der Ham, C. Jansen, P. Landrock,
B. Preneel, G. Roelofsen, P. de Rooij, and J.
[22] Hawkes, P. and G. Rose (2003). “Primitive spec-
Vandewalle (1995). Final Report of Race Integrity
i¬cation for SOBER-128.” Available from http://
Primitives, Lecture Notes in Computer Science,
vol. 1007, eds. A. Bosselaers and B. Preneel.
[23] Iwata, T. and K. Kurosawa (2003). “OMAC: One-
Springer-Verlag, Berlin.
key CBC MAC.” Fast Software Encryption, Lec-
[10] Bernstein, D. (2000). “Floating-point arithmetic
ture Notes in Computer Science, vol. 2887, ed. T.
and message authentication.” Available from
Johansson. Springer-Verlag, Berlin.
[24] Jonsson, J. (2002). “On the security of CTR + CBC-
[11] Black, J., S. Halevi, H. Krawczyk, T. Krovetz, and
MAC.” Selected Areas in Cryptography”SAC 2002,
P. Rogaway (1999). “UMAC: Fast and secure mes-
Lecture Notes in Computer Science, vol. 2595, eds.
sage authentication.” Advances in Cryptology”
K. Nyberg and H.M. Heys. Springer-Verlag, Berlin,
CRYPTO™99, Lecture Notes in Computer Science,
vol. 1666, ed. J. Wiener. Springer-Verlag, Berlin.
Authentication 21

tication (also as information integrity), should
[25] Jutla, C. (2001). “Encryption modes with almost
free message integrity.” Advances in Cryptology” guarantee with some con¬dence that a given in-
EUROCRYPT 2001, Lecture Notes in Computer formation is authentic, i.e., has not been altered or
Science, vol. 2045, ed. B. P¬tzmann. Springer- substituted by the opponent. This con¬dence may
Verlag, Berlin, 529“544. depend on the computing power of the opponent
[26] Katz, J. and M. Yung (2000). “Complete character-
(e.g., in digital signature schemes this is the case).
ization of security notions for probabilistic private-
The latter is called unconditional authentication
key encryption.” Proceedings of the 32nd Annual
and makes use of symmetric cryptosystems.
Symposium on the Theory of Computing (STOC).
The model of unconditional authentication
ACM Press, New York.
schemes (or codes) consists of a sender, a receiver,
[27] Kohno, T., A. Palacio, and J. Black (2003). “Build-
and an opponent. The last one can observe all
ing secure cryptographic transforms, or how to en-
the information transmitted from the sender to
crypt and MAC.” Cryptology ePrint archive, refer-
ence number 2003/177, submitted August 28, 2003. the receiver; it is assumed (following Kerkhoff™s
See eprint.iacr.org maxim) that the opponent knows everything, even
[28] Kohno, T., J. Viega, and D. Whiting (2003). “High- the original (plain) message (this is called authen-
speed encryption and authentication: A patent-free tication without secrecy), but he does not know the
solution for 10 Gbps network devices.” Cryptology
used key.
ePrint archive, reference number 2003/106, sub-
There are two kinds of possible attacks by the
mitted May 27, 2003, revised September 1, 2003.
opponent. One speaks about an impersonation at-
See eprint.iacr.org
tack when the opponent sends a message in the
[29] Krawczyk, H. (2001). “The order of encryption and
hope that it will be accepted by the receiver as
authentication for protecting communications
a valid one. In a substitution attack the opponent
(or: How secure is SSL?).” Advances in
observes a transmitted message and then replaces
Cryptology”CRYPTO 2001, Lecture Notes in
Computer Science, vol. 2139, ed. J. Kilian. it with another message. For authentication pur-
Springer-Verlag, Berlin, 310“331. poses it is enough to consider only so-called sys-
[30] Liskov, M., R. Rivest, and D. Wagner (2002). tematic authentication codes in which the trans-
“Tweakable block ciphers.” Advances in mitted message has the form (m; z), where m is
Cryptology”CRYPTO 2002, Lecture Notes in
chosen from the set M of possible messages and
Computer Science, vol. 2442, ed. M. Yung.
z = f (m) is its tag (a string of “parity-check sym-
Springer-Verlag, Berlin, 31“46.
bols” in the language of coding theory). Let Z be
[31] Petrank, E. and C. Rackoff (2000). “CBC MAC for
the tag-set and let F = { f1 , . . . , fn } be a set of n en-
real-time data sources.” Journal of Cryptology, 13
coding maps fi : M ’ Z. To authenticate (or code)
(3), 315“338.
message m, the sender chooses randomly one of
[32] Rogaway, P. (2002). “Authenticated-encryption
the encoding mappings fi (the choice is in fact
with associated-data.” ACM Conference on Com-
puter and Communications Security (CCS-9). ACM the secret key unknown to the opponent). One
Press, New York, 196“205. may assume without loss of generality that these
[33] Rogaway, P., M. Bellare, and J. Black (2003). encoding maps fi are chosen uniformly. The cor-
“OCB: A block-cipher mode of operation for ef¬cient responding probabilities of success for imperson-
authenticated encryption.” ACM Transactions on
ation and substitution attacks are denoted by PI
Information and System Security (TISSEC), 6 (3),
and PS respectively. The ¬rst examples of authen-
tication codes were given in [3], among which is
[34] Wegman, M. and L. Carter (1981). “New hash func-
the following optimal scheme (known as af¬ne
tions and their use in authentication and set equal-
ity.” J. of Comp. and System Sciences, 22, 265“279.
Let the set M of messages and the set Z of tags
[35] Whiting, D., R. Housley, and N. Ferguson (2002).
coincide with the ¬nite ¬eld Fq of q elements (q
“Counter with CBC-MAC (CCM).” Available from
csrc.nist.gov/encryption/modes/proposedmodes/ should be a power of a prime number). The set F
of encoding mappings consists of all possible af¬ne
functions, i.e. mappings of the form
fa,b (m) = am + b.
For this scheme PI = PS = q ’1 and the scheme is
There is a rather common saying that cryptology optimal for both parameters”for PI this is obvi-
has two faces. The ¬rst (and better known) face ous and for PS this follows from the square-root

bound PS ≥ 1/ n which is also derived in [3]. Al-
is cryptography in its narrow sense which should
protect data (information) from being revealed to though this scheme is optimal (meets this bound
an opponent. The second face, known as authen- with equality), it has a serious drawback when
22 Authentication

being applied in practice since its key size (which Application of the q-twisted construction to
is equal to log n = 2 log q) is two times larger than many optimal ECC (with enough large minimal
the message size. code distance) produces optimal or near optimal
For a long time (see [6, 10]), no known schemes authentication codes. For instance, Reed“Solomon
(codes) had a key size that was much smaller codes generate authentication schemes which are
than the message size. Schemes that did allow the natural generalization of the aforementioned
af¬ne scheme (namely, k = 1) and have the follow-
this were ¬rst constructed in [4]. They made use
of a very important relationship between authen- ing parameters ([2, 5]):
tication codes and error-correcting codes (ECC,
The number of messages is q k , the number
shortly) (see [8] and cyclic codes).
of keys is q 2 , and the probabilities are PI =
By de¬nition (see [5]), an authentication code
1/q, PS = k/q, where k + 1 is the number of in-
is a q-ary code V over the alphabet Z (|Z| =
formation symbols of the corresponding Reed“
q) of length n consisting of |M| codewords
Solomon code.
( f (m), . . . , fn (m)) : m ∈ M. Almost without loss of
generality one can assume that all words in the A- Reed“Solomon codes are a particular case of
code V have a uniform composition, i.e., all “char- algebraic-geometry (AG) codes and the corre-
acters” from the alphabet Z appear equally often sponding application of q-twisted construction to
in every codeword (more formally, |{i : vi = z}| = AG codes leads to an asymptotically very ef¬cient
n/q for any v ∈ V and any z ∈ Z). This is equiva- class of schemes with the important, additional
lent to saying that PI takes on its minimal possible property of being polynomial constructible (see
value q ’1 . The maximal probability of success of a [9]).
substitution by the opponent is To conclude, we note that there is also another
equivalent “language” to describe and investigate
PS = 1 ’ n’1 d A(V),
unconditional authentication schemes, namely,
where d A(x, y) = n ’ qγ (x, y), γ (x, y) = max{|{i : the notion of almost strongly two-universal hash
xi = z, yi = z }| : z, z ∈ Z} and d A(V) (the min- functions (see [7] and also [10]).
imum A-distance of the code V) is de¬ned as
Grigory Kabatiansky
usual (see cyclic codes and McEliece public-key
Ben Smeets
encryption scheme). The obvious inequality
d A(V) ¤ d H (V), with d H (V) being the minimum
Hamming distance of V, allows one to apply
known upper bounds for ECC to systematic A-
codes and re-derive known nonexistence bounds
[1] Bassalygo, L.A. and M.V. Burnashev (1996). “Au-
for authentication codes as well as obtain new
thentication, identi¬cation and pairwise separated
bounds (see [1, 5] for details).
measures.” Problems of Information Transmission,
On the other hand, the q-twisted construction 32 (1), 41“47.
proposed in [5] turns out to be a very effective tool [2] den Boer, B. (1993). “A simple and key-economical
to construct good authentication codes from ECC unconditionally authentication scheme.” Journal
(in fact almost all known authentication schemes on Computer Security, 2 (1), 65“67.
are implicitly or explicitly based on the q-twisted [3] Gilbert, E.N., F.J. MacWilliams, and N.J.A. Sloane
(1974). “Codes which detect deception.” Bell Syst.
construction). Let C be an error-correcting code
Tech. J., 33 (3), 405“424.
of length m over Fq with the minimal Hamming
[4] Johansson, T., G.A. Kabatianskii, and B. Smeets
distance d H (C) and let U be its subcode of car-
(1994). “On the relation between A-codes and
dinality q ’1 | C | such that for all U ∈ U and all
codes correcting independent errors.” Adavances
» ∈ Fq vectors u + »1 are distinct and belong to
in Cryptology”EUROCRYPT™93, Lecture Notes
C, where 1 is the all-one vector. Then the fol-
in Computer Science, vol. 765, ed. T. Helleseth.
lowing q-ary code VU := {(u, u + »1 1, . . . , u + »q 1) : Springer-Verlag, Berlin, 1“11.
u ∈ U} (where »1 , . . . , »q are all different elements [5] Kabatianskii, G.A., B. Smeets, and T. Johansson
of the ¬eld Fq ) of length n = mq is called q-twisted (1996). “On the cardinality of systematic authen-
code and considered as A-code generates the au- tication codes via error-correcting codes.” IEEE
thentication scheme [5] for protecting |U| mes- Transactions on Information Theory, 42 (2), 566“
sages with the number of keys n = mq providing 578.
[6] Simmons, G.J. (1992). “A survey of information au-
thentication. Contemporary cryptology.” The Sci-
1 d H (C) ence of Information Integrity. IEEE Press, Piscat-
PI = , PS = 1 ’ .
away, NJ.
q m
Authorization architecture 23

like those described above, which are provided di-
[7] Stinson, D.R. (1994). “Universal hashing and au-
thentication codes.” Designs, Codes and Cryptog- rectly by the end user to the authenticating party,
raphy, 4, 369“380. except in that they originate with a third party,
[8] van Tilborg, H.C.A. (1996). “Authentication codes: the authentication server.
An area where coding and cryptology meet.” Cryp- Usually these tokens take the form of a
tography and Coding V, Lecture Notes in Com-
data structure which has been digitally signed
puter Science, vol. 1025, ed. C. Boyd. Springer-
(see digital signature schemes) or MACed (see
Verlag, Berlin, 169“183.
MAC algorithms) by the authentication server
[9] Vladuts, S.G. (1998). “A note on authentication
and thus vouch for the identity of the authen-
codes from algebraic geometry.” IEEE Transactions
ticated party. In other words, the authenticated
on Information Theory, 44, 1342“1345.
party can assert his/her identity to the applica-
[10] Wegman, M.N. and J.L. Carter (1981). “New hash
tion server simply by presenting the token. These
functions and their use in authentication and set
equality.” J. Comput. Syst. Sci., 22, 265“279. tokens must have a short lifetime since if they are
stolen they can be used by an attacker to gain ac-
cess to the application server.
Quite often the credentials that must be provided
The term “authentication token” can have at least to an authenticating party are such that they can-
three different de¬nitions, but is generally used to not be constructed using only data that can be re-
refer to an object that is used to authenticate one membered by a human user. In such situations
entity to another (see authentication). The various it is necessary to provide a storage mechanism
de¬nitions for “authentication token” include the to maintain the user™s private information, which
credentials provided to an authenticating party can then be used when required in an identity ver-
as part of an identity veri¬cation protocol, a data i¬cation protocol. This storage mechanism can be
structure provided by an authentication server for either a software ¬le containing the private infor-
later use in authenticating to a different applica- mation and protected by a memorable password,
tion server, and a physical device or computer ¬le or it can be a hardware device (e.g., a smart card
used to authenticate oneself. These de¬nitions are and is sometimes called an “authentication token.”
expanded below. In addition to making many identity veri¬ca-
tion protocols usable by human end entities, these
CREDENTIALS PROVIDED TO AN AUTHENTI- authentication tokens have another perhaps more
CATING PARTY: In most identity veri¬cation or important bene¬t. Since successful completion
authentication protocols, the entity being authen- of the protocol now usually involves both some-
ticated must provide the authenticating entity thing the end entity has (the ¬le or device) and
with some proof of the claimed identity. This something the end entity knows (the password or
proof will allow the authenticating party to ver- PIN to access the smart card) instead of just some-
ify the identity that is being claimed and is some- thing the end entity knows, the actual security
times called an “authentication token.” Examples of the authentication mechanism is increased. In
of these types of authentication tokens include particular, when the token is a hardware device,
functions of shared secret information, like pass- obtaining access to that device can often be quite
words, known only to both the authenticating and dif¬cult, thereby providing substantial protection
authenticated parties and responses to challenges from attack.
that are provided by the authenticating party but
Robert Zuccherato
which could only be produced by the authenticated

TICATION SERVER: In some security architec-
tures end users are authenticated by a dedicated
“authentication server” by means of an identity
veri¬cation protocol. This server then provides the Authentication and authorization are separate
user with credentials, sometimes called an “au- concepts (although authentication may be used in
thentication token,” which can be provided to other the service of authorization), and their respective
application servers in order to authenticate to architectures or infrastructures may be separately
those servers. Thus, these credentials are not un- deployed and managed. Authentication allows
24 Authorization architecture

ing to an authorization policy that is applicable to
this request. The relevant data includes the sub-
mitted request along with particular attributes
about both the subject and the resource, and may
PIP PDP PRP PAP also include attributes about the environment in
which the request is submitted. Various authori-
ties are responsible for creating and making avail-
able this attribute information: one or more sub-
ject authorities (SAs), a resource authority (RA),
and one or more environmental authorities (EAs)
package this information in a syntax that will be
Fig. 1. Conceptual model of an authorization architec- accessible by a policy information point (PIP), the
ture entity that collects this data on behalf of the PDP.
Similarly, a policy administration point (PAP) is
entity A to convince entity B of A™s identity responsible for creating authorization policies and
with some degree of certainty (see identi¬cation, making them accessible to a policy retrieval point
identity veri¬cation protocol, and entity authen- (PRP), the entity that fetches policies for the
tication). Typically, however, this information is PDP.
insuf¬cient. Entity A may be trying to perform A given implementation may have variations on
some task (e.g., execute an application, invoke a the basic architecture discussed above. For exam-
function, or access a ¬le) and B needs to know ple, there may be multiple PDPs that work to-
not “who A is” as much as “whether A should be gether to render an overall decision with respect
allowed to perform this task.” Authorization al- to an authorization request.
lows B to make and enforce this decision. In some
cases, A™s identity will be a critical input to the INFORMATION FLOW: The ¬‚ow of information
decision-making process (“is A allowed to read A™s in Figure 1 is as follows. The subject S submits
medical record?”); in other cases, A™s identity may a request to access a resource R. The PEP inter-
be almost irrelevant, useful for auditing purposes cepts this access request and sends a request for
only (“the requester is an executive of the com- an authorization decision to the PDP. The decision
pany and”regardless of who it is”all executives request will contain the information contained in
are allowed to see the quarterly results before the original access request, but may also contain
they are announced”). Authentication answers the additional information, such as some attributes
question “who is this entity?” and authorization of the subject, resource, or environment that are
answers the question “is this entity allowed to do known to the PEP (e.g., the IP address of the ma-
what it is trying to do?” chine from which the access request was made).
The PDP will need to ¬nd an authorization pol-
AUTHORIZATION ARCHITECTURE: An autho- icy that is relevant to this access request and so
rization architecture is the set of components and will supply the appropriate subject, resource, and
data that allows authorization decisions to be action information to the PRP and ask it to retrieve
made and enforced. The components of this archi- the correct policy. Once the PDP has the authoriza-
tecture are shown in Figure 1 (note that this is tion policy for this access request, it can examine
a conceptual model; actual implementations will the policy to see what subject, resource, or environ-
typically combine subsets of these components ment attributes are required in order for it to ren-
into single machines or even single processes). der a decision. If the PDP requires attributes that
were not supplied by the PEP in the authorization
COMPONENTS: The subject, S, sends a request to decision request, the PDP will ask the PIP to re-
perform some action on a resource, R (e.g., read a trieve these attributes. Once the PDP has all the
¬le, POST to a Web site, execute an application, data it requires (or has determined that some at-
or invoke an object method). This request is in- tribute data cannot be retrieved for some reason),
tercepted by an entity called a policy enforcement it can evaluate the authorization policy and render
point (PEP) whose job is to enforce a “PERMIT” a decision or produce a value of “indeterminate”
or “DENY” decision with respect to this request. (no decision possible due to missing attributes) or
The decision itself is made by an entity called a “error” (no decision possible due to network or pro-
policy decision point (PDP). The PDP makes this cessing dif¬culties). The PDP can then return its
decision by gathering all the input data that is result to the PEP, which will enforce this result
relevant to this request and evaluating it accord- by granting access to the requested resource, or
Authorization architecture 25

by returning an “access denied” or relevant error resource, for example) and to have the relevant
message to the subject. authority digitally sign this data structure. The
signed data structure is the authority™s “certi¬-
ATTRIBUTES: An attribute is a piece of informa- cate” of the authenticity of the binding between
the attribute data and the entity, which the en-
tion that may be categorized as being associated
tity may be able to use in a proof procedure with
with the subject, action, resource, or environment
other parties to show ownership of the contained
in an authorization architecture. Attributes may
be static or dynamic. Static attributes of the sub-
When static attributes are available in an au-
ject are referred to by many names in various
thorization architecture, the use of signed data
discussions and contexts, including privileges, per-
structures binding such attributes to entities can
missions, rights, authorizations, properties, char-
have a number of attractive bene¬ts. First, “of-
acteristics, entitlements, and grants. Static at-
¬‚ine” operation may be possible, in that relying
tributes can also be associated with resources and
parties such as the PDP and PIP do not need to
with actions. Groups, roles, and document labels
access SAs or RAs in real time as access requests
are all examples of static attributes (even though
are being evaluated. Second, caching or other rela-
a “role” is dynamic in another sense: that is, an
tively local storage of this data at the PDP/PIP can
entity may be able to step into or out of a role at
signi¬cantly reduce network traf¬c when these
will in the course of performing some aspects of its
attributes need to be retrieved. Third, extended
trust and delegation of attribute granting author-
Dynamic attributes are those whose values can-
ity are more readily achievable through the use of
not be relied upon to remain unchanged between
signed data structures. Finally, such an architec-
one time they are required (e.g., by the PDP) and
ture can allow a simple mechanism to “turn off”
the next time they are required. Example dynamic
all attributes for a given entity simultaneously
attributes of the subject include current account
(for example, if all attribute certi¬cates are cryp-
balance, amount of credit remaining, and IP ad-
tographically linked to an entity™s public-key cer-
dress of requesting machine; dynamic attributes
ti¬cate, then revoking that single public-key cer-
of the resource include the number of times it has
ti¬cate will automatically revoke all associated
been accessed; and dynamic attributes of the en-
attribute certi¬cates”this can be a signi¬cant
vironment include current time of day, and time of
convenience when a company employee is ¬red or
receipt of the request.
otherwise rendered inactive and access to many
Dynamic attributes are retrieved by the
different networks and systems has to be cut off
PDP/PIP in real time (i.e., at the time of access re-
quest evaluation) from the relevant authority. In
order for this exchange to occur securely, it is nec-
POLICIES: An access control policy with respect
essary for the response to be authenticated so that
the PDP/PIP can be con¬dent that the intended to a speci¬c resource or set of resources is the
authority created the response. In some cases, the set of rules governing who can do what to those
request for these attributes may also need to be resources under what conditions. The term au-
authenticated so that the authority can be con¬- thorization policy includes access control policy,
dent that the legitimate PDP/PIP asked for this but has a broader de¬nition, potentially includ-
information. This authentication may take place ing rules regarding the actual assignment of at-
independently on each message (e.g., using digi- tributes to subjects or resources, the rules re-
tal signatures), or may take place in the context garding the delegation of authority to assign such
of a secure session (such as an SSL (see Secure attributes, rules regarding the default behavior of
Socket Layer) session between the PDP/PIP and various components in the absence of suf¬cient in-
the relevant authority). formation, rules regarding the trusted system en-
Static attributes need not be retrieved in real tities for each component in the architecture, and
time from the authority; for example, they may be so on.
cached locally by the PDP or retrieved from an on- Terminology in this area is far from universally
line repository such as a database or a directory. agreed, but the concepts are quite similar across
However, in such cases, the authenticity and in- many discussions. Typically a “rule” has an effect
tegrity of the information must still be ensured. (indicating whether it is intended to contribute
A method commonly employed is to put the at- to a PERMIT decision or a DENY decision), a
tribute data into a data structure along with some scope or a target of applicability (indicating the
representation of the entity to which it pertains subject, resource, and action to which it applies),
(the identity of the subject, or the name of the and a condition or set of conditions (indicating any
26 Authorization architecture

restrictions, limitations, or quali¬cations to be im- or trust infrastructure is critical to the success of
posed upon this subject being permitted or denied the authorization architecture.
access to this resource). A “policy” is a collection Another important aspect of management is at-
of one or more rules along with an (implicit or tribute/policy storage and retrieval. How can this
explicit) algorithm for combining the rules that information be found by the components that need
it contains or references. A well-known example it (the PIP and PRP), when they need it? At-
combining algorithm is “deny overrides,” in which tributes and policies must be indexed and stored in
any satis¬ed rule that has an effect of DENY takes a manner that makes them easy to retrieve in real
precedence over all satis¬ed rules that have an ef- time, given only the information contained in the
fect of PERMIT. Another common example is “de- access request. Finding the best indexing mecha-
fault deny,” in which access is denied if for what- nism, storage technology, and retrieval method for
ever reason an actual decision cannot be rendered a given environment is an area of both theoretical
by the PDP from the available data. and practical interest.
In many environments, policies will have what
is referred to as “distributed authorship.” That
SYNTAX: The various pieces of information in the
is, several different PAPs (policy administration
points) may independently create policies that per- authorization architecture must be expressed and
tain to the same subject or to the same resource. conveyed in a syntax that is understood by dif-
For example, in a particular company or orga- ferent components in the architecture. For exam-
nization, there may be regulatory policies that ple, the Subject Authority will bind attribute in-
govern access to certain types of data, legislative formation to subject identi¬ers and express this
policies regarding the release of the same data, binding in a data structure; the policy adminis-
and corporate and even departmental policies re- tration point will de¬ne an access control policy
garding access to the same data. When a subject and express this policy in a data structure; the pol-
asks to read this data, all these policies must be icy enforcement point will need a decision from a
taken into account by the PDP before it can ren- policy decision point regarding a particular access
der the appropriate decision. This means that the request and will package this decision request in
PDP must have some sort of reconciliation algo- a protocol message. In each case, the syntax and
rithm, determining the correct (i.e., intended) way semantics of the data must be understood by mul-
in which to combine these various”potentially tiple components in the architecture in order for
con¬‚icting”policies. The reconciliation algorithm proper enforcement of the intended authorization
must be robust and comprehensive in order for policies to take place.
the PDP to be able to deal in an automated fash- Over the years, there have been many at-
ion with all the possible ways in which indepen- tempts to de¬ne a syntax to express attribute
dently created policies may interact. This aspect bindings and policy information, some based on
of authorization policy is still an area of much Baccus-Nauer Form (BNF), some based on Ab-
research. stract Syntax Notation One (ASN.1), and some
more recent work based on Extensible Markup
Language (XML). Examples include work in
ATTRIBUTE POLICY MANAGEMENT: Sub- the Distributed Computing Environment (DCE),
ject and resource attributes, as well as access con- SESAME, and CORBA Security initiatives, Policy-
trol and authorization policies, need to be man- Maker, PONDER, Distributed Management Task
aged in an authorization architecture. Attributes Force/Common Information Model (DMTF/CIM),
and policies have life cycles: they may be created, IETF Simple Public Key Infrastructure (SPKI) s-
used, versioned, audited, revoked, and archived. expressions, ISO/ITU-T X.509 Attribute Certi¬-
They may be “current” (i.e., active and valid) for a cate and PrivilegePolicy, OASIS XACML policy
relatively short period of time or for a long period language, and OASIS SAML assertions and pro-
of time, and components in the architecture (espe- tocols.
cially the PDP) must readily be able to tell whether It is unlikely that a single syntax for attribute
a particular attribute binding or policy statement binding information or for policy expression will
can be relied upon or not. Various authorities in meet the needs of all environments and architec-
the architecture are responsible for managing the tures. However, the search for ¬‚exible, powerful
life cycle of this information, including SAs, RAs, syntaxes for these types of information continues
and PAPs. Such authorities must be trusted to do throughout the academic and commercial commu-
this job in a reliable and timely fashion; thus, the nities. In the meantime, some of the efforts men-
establishment of a trust model (see trust models) tioned above have been found to be appropriate
Availability 27

and useful in speci¬c environments and commu-
nities of interest.
Let {at } be a sequence of period n (so at = at+n
FURTHER READING: Further discussion on au- for all values of t) with symbols being the inte-
thorization models and architectures can be found gers mod q (see modular arithmetic). The periodic
auto-correlation of the sequence {at } at shift „ is
in the references list.
de¬ned as
Carlisle Adams
ωat+„ ’at ,
A(„ ) =
References t=0

where ω is a complex qth root of unity.
[1] Adams, C. and S. Lloyd (2003). Understanding PKI:
In most applications one considers binary
Concepts, Standards, and Deployment Considera-
sequences when q = 2 and ω = ’1. Then the auto-
tions (2nd ed.). Addison-Wesley, Reading, MA.
correlation at shift „ equals the number of agree-
[2] CORBA Security Project, http://security.dstc.edu
ments minus the number of disagreements be-
tween the sequence {at } and its cyclic shift {at+„ }.
[3] Distributed Computing Environment (DCE),
http://www.opengroup.org/dce/ Note that in most applications one wants the au-
[4] Godik, S. and T. Moses (2003). “eXtensible Access tocorrelation for all nonzero shifts „ = 0 (mod n)
Control Markup Language (XACML) Version 1.0.”
(the out-of-phase autocorrelation) to be low in
OASIS Standard, 18 February 2003.
absolute value. For example, this property of a
[5] Hallam-Baker, P. and E. Maler (2002). “Asser-
sequence is extremely useful for synchronization
tions and protocol for the OASIS security asser-
tion markup language (SAML).” OASIS Standard,
5 November 2002.
Tor Helleseth

[1] Golomb, S.W. (1982). Shift Register Sequences.
MANAGEMENT Aegean Park Press, Laguna Hills, CA.
[2] Helleseth, T. and P.V. Kumar (1998). “Sequences
Authorizations management is a subset of with low correlation.” Handbook of Coding Theory,
general “authorization data” management (see eds. V.S. Pless and W.C. Huffman. Elsevier, Amster-
authorization architecture) in which the data be-
[3] Helleseth, T. and P.V. Kumar (1999). “Pseudonoise
ing managed is authorizations associated with en-
sequences.” The Mobile Communications Hand-
tities in an environment. An authorization may
book, ed. J.D. Gibson. CRC Press, Boca Raton, FL,
be de¬ned as follows [1]: something (typically in
Chapter 8.
writing) “empowering a person (or system entity)
to perform an act or to execute an of¬ce.”

Carlisle Adams
A service is of no practical use if no one is able to
access it. Availability is the property that legiti-
[1] Encyclopaedia Britannica, http://www.britannica
mate principals are able to access a service within
a timely manner whenever they may need to do so.
Availability is typically expressed numerically as
the fraction of a total time period during which a
AUTHORIZATION POLICY service is available. Although one of the keystones
of computer security, availability has historically
not been emphasized as much as other properties
Authorization policy is the policy used by a policy
of security such as con¬dentiality and integrity.
decision point (PDP), in conjunction with autho-
This lack of emphasis on availability has changed
rization data, to render authorization decisions.
recently with the rise of open Internet services.
See authorization architecture for details.
Decreased availability can occur both inadver-
Carlisle Adams tently, through failure of hardware, software, or
28 Availability

infrastructure, or intentionally, through attacks attacker is able to degrade availability, it is known
on the service or infrastructure. The ¬rst can be as a Denial of Service attack. Malicious attacks
mitigated through redundancy, where the prob- against availability can focus on the service it-
ability of all backups experiencing a failure si- self (e.g., exploiting a common software bug to
multaneously is (hopefully) very low. It is in re- cause all backups to fail simultaneously), or on the
gard to these random failures where “¬ve-nines infrastructure supporting the service (e.g., ¬‚ood-
of availability” (available 99.999% of the time) ing network links between the service and the
are often used when describing systems. The principal).
second cause for loss of availability is of more
interest from a security standpoint. When an Eric Cronin


. 2
( 2)