Network Working Group E. Rescorla
Internet-Draft Network Resonance
Intended status: Standards Track March 01, 2007
Expires: September 2, 2007
How to Implement Secure (Mostly) Stateless Tokens
draft-rescorla-stateless-tokens-01.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on September 2, 2007.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
A common protocol problem is to want to arrange to maintain client
state with little or no local storage. The usual design pattern here
is to provide the client with a token which is returned with
subsequent interactions. In order to prevent tampering, forgery, and
privacy issues, such tokens should be cryptographically protected.
This draft describes one workable mechanism for constructing such
tokens.
Rescorla Expires September 2, 2007 [Page 1]
Internet-Draft Stateless Tokens March 2007
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Conventions Used In This Document . . . . . . . . . . . . . . 3
3. General Principles . . . . . . . . . . . . . . . . . . . . . . 3
3.1. Reference Architecture . . . . . . . . . . . . . . . . . . 3
3.2. Token Construction and Processing . . . . . . . . . . . . 4
3.3. Invalidation and Supercession . . . . . . . . . . . . . . 5
4. Example Token Format . . . . . . . . . . . . . . . . . . . . . 5
4.1. Key Rollover . . . . . . . . . . . . . . . . . . . . . . . 8
5. ITLs Data Structures . . . . . . . . . . . . . . . . . . . . . 9
5.1. Simple Lists . . . . . . . . . . . . . . . . . . . . . . . 9
5.2. Bit Fields . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 10
6. Security Considerations . . . . . . . . . . . . . . . . . . . 10
6.1. Failure to Authenticate . . . . . . . . . . . . . . . . . 10
6.2. Failure to Encrypt . . . . . . . . . . . . . . . . . . . . 11
6.3. Distinguishable Encryption . . . . . . . . . . . . . . . . 11
6.4. Replay Attacks . . . . . . . . . . . . . . . . . . . . . . 11
6.5. Token Binding . . . . . . . . . . . . . . . . . . . . . . 12
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.1. Normative References . . . . . . . . . . . . . . . . . . . 12
8.2. Informational References . . . . . . . . . . . . . . . . . 12
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 13
Intellectual Property and Copyright Statements . . . . . . . . . . 14
Rescorla Expires September 2, 2007 [Page 2]
Internet-Draft Stateless Tokens March 2007
1. Introduction
A common protocol problem is to want to arrange to maintain client
state with little or no local storage. The usual design pattern here
is to provide the client with a token which is returned with
subsequent interactions. One such application is TLS tickets [4],
which allow the server to offload the TLS session cache onto the
client. Another application is globally routable unique identifiers
[5] (GRUUs) which bind a second URI to a SIP AOR. GRUUs can be
defined in a stateless mode, which requires no storage on the SIP
registrar. Another application for this kind of technique is to
build Web "shopping carts".
Because the state token is stored on a remote node it is susceptible
to inspection and /or tampering by untrusted third parties.
Therefore, it becomes important to cryptographically secure tokens,
typically by encrypting them to provide confidentiality and adding a
message integrity check (MIC) to provide integrity for the token data
and assurance that it was generated by the consuming node. Note that
the remote node doesn't need to do anything with the token other than
echo it back, therefore there is no need for it to be able to access
the internals of the token.
Although the general techniques for constructing tokens of this type
are well understood, there are some subtle issues involved and there
is no single reference that describes acceptable constructions.
Accordingly, each token-using application has had to design its own
construction. The purpose of this document is to provide such a
reference.
2. Conventions Used In This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [1].
3. General Principles
This section provides a somewhat abstract overview of the techniques
for constructing stateless tokens. In the next section we will
describe precise example formats that implement these principles.
3.1. Reference Architecture
The reference architecture for this kind of system is shown in the
figure below:
Rescorla Expires September 2, 2007 [Page 3]
Internet-Draft Stateless Tokens March 2007
Client Server
------ ------
1. Hello ---------> \ State
<--------- 2. State token / Creation
[time passes]
3. State token ---------> \ State
<--------- 4. I remember you / Recovery
In message 1, the client contacts the server. The server creates
some state (e.g., creates a shopping cart structure), serializes that
into a state token, and sends it to the client in message 2. From
the client's perspective, this token is opaque, though it of course
has some internal structure that is parseable by the server.
Some time later, the client wants to talk to the server again. When
it reconnects, it sends the state token back in message 3. The
server decodes the state token and recovers the previously created
state and can process whatever transaction the client is trying to
perform.
3.2. Token Construction and Processing
We assume that the server has some static cryptographic keying
material, consisting of:
K_e -- an encryption key
K_m -- a message integrity (MAC) key
These keys SHOULD be randomly generated and of sufficient length to
match whatever cryptographic algorithms are in use. They are stored
in semi-permanent storage and used for protecting all tokens.
In order to construct a token, the server takes its state and packs
it into a single string S. S should be constructed so that it can be
unambiguously parsed by the server. The server than encrypts the
token and applies a MAC. For instance:
EA = Encrypt(K_e, S)
Token = EA || MAC(K_m, EA)
The encryption algorithm SHOULD to be chosen to have the following
properties:
1. Given any (EA, S) pair, it is computationally infeasible to
determine whether EA was derived from S. (Note that you may
obtain some information from length).
Rescorla Expires September 2, 2007 [Page 4]
Internet-Draft Stateless Tokens March 2007
2. Multiple encryptions of the same value S produce different tokens
3. It is computationally infeasible to determine any information
about the relationship between the S values embedded in two
separate tokens.
AES [6] in either CBC or counter (CTR) with randomly chosen IVs both
meet these requirements.
The MAC algorithm is simply a standard MAC, such as HMAC [2].
The design described above works in a variety of situations but has
the significant drawback that it does not permit the server to
invalidate or supercede states. Consider the case where the token is
being used to contain login state. One function such interfaces
typically offer is a "logout" button. However, if the server is
stateless, then there is no way to detect that a token which is
presented corresponds to a session which has been invalidated. A
related issue is "state rollback". If a server gives a client a new
state token (e.g., decrementing an account balance) the client can
send an older token instead; this is effectively a replay attack.
3.3. Invalidation and Supercession
Invalidating or superceding tokens requires the server to be able to
store some state. The usual procedure is for the server to retain a
list of invalid tokens. In the most primitive implementation, this
requires the server to keep all invalid tokens since the beginning of
time. Obviously this is inconvenient, so tokens are created with an
expiration time, thus limiting the invalid list to unexpired tokens
which are invalid (there is a parallel here to certificate revocation
lists [3]).
Even with expiry, high invalidation rates can lead to large Invalid
Token Lists (ITLs). This is especially true if you are having state
n+1 supercede state n (this is done by invalidating state n and then
issueing state n+1). A number of techniques can be used to minimize
the size of the ITL. For instance, it may be stored in a Bloom
filter or each token may be assigned an index with the ITL stored as
a bit field. These options are examined in more detail in Section 5.
4. Example Token Format
In this section we describe one acceptable token format that complies
with the guidelines in the previous section. For reference, consider
a state value as shown in Figure 1:
Rescorla Expires September 2, 2007 [Page 5]
Internet-Draft Stateless Tokens March 2007
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------------------------------------------------------+
| User Name |
| (64 bits) |
+---------------------------------------------------------------+
| E-mail address |
/ (variable length) /
| |
+---------------------------------------------------------------+
Figure 1: Example state value
This state value would allow the server to "remember" some
registration information, e.g., for a web bulletin board. Note that
the token construction is agnostic about the state value as long as
it can be represented as a byte string.
The token format is shown in Figure 1.
Rescorla Expires September 2, 2007 [Page 6]
Internet-Draft Stateless Tokens March 2007
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-------------------------------+-------------------------------+ <-+
| Version (16 bits) | Protection Suite ID (16 bits) | |
+---------------------------------------------------------------+ <-+-+
| | |
| Initialization Vector (IV) | |
| (typically 128 bits) | |
| | |
+-> +-------------------------------+-------------------------------+ <-+-+
| | Expiration Time (32 bits) | |
| +---------------------------------------------------------------+ |
| | Sequence Number (32 bits) | |
| +---------------------------------------------------------------+ |
| | | |
| | State (S) | |
| / (Variable Length) / |
| | | |
| | +-------------------------------------+ |
| | | Padding | |
| +-------------------------+ Variable length | |
| | | |
+-> +---------------------------------------------------------------+ <-+
| | | |
| | MAC | |
| | (Typically 160 bits) | |
| | | |
| | | |
| +---------------------------------------------------------------+ |
| |
| |
Encrypted Authenticated
Portion Portion
Figure 2: Example stateless token format
We assume that the state value that the server wishes to deliver is a
byte string S.
To construct a token, follow the following steps.
1. Construct TI = ET || SEQ || S where ET is the expiry time in
seconds since the UNIX epoch and SEQ is the token sequence
number. Both are 32-bit integers so TI can be unambiguously
parsed.
Rescorla Expires September 2, 2007 [Page 7]
Internet-Draft Stateless Tokens March 2007
2. Generate a random 128-bit initialization vector.
3. Set EA equal to the encryption of TI with key K_e and
initialization vector IV: EA = Encrypt(K_e, IV, TI)
4. Compute the MAC over the Version, Protection Suite ID (PSID), and
EA: H = MAC(K_m, Version || PSID || EA)
5. Pack the values into token T.
Because the producer and consumer of the token are the same machine,
the Version and Protection Suite IDs are strictly unnecessary because
the consumer knows what kind of tokens it produces. However, in the
interest of tokens being self-describing and ease of version/
algorithm transition, they are included in the token. Similarly,
there is no need to have standardized Version and Protection Suite ID
(PSID) values. However, we recommend that Version be the integer 1
and the following Prot_Id values:
+--------------------------+------+-------------+--------------+
| Protection Suite | PSID | Encryption | MAC |
+--------------------------+------+-------------+--------------+
| AES_128_CBC_WITH_SHA1 | 1 | AES-128-CBC | HMAC-SHA1 |
| AES_256_CBC_WITH_SHA_256 | 2 | AES-256-CBC | HMAC-SHA-256 |
+--------------------------+------+-------------+--------------+
Table 1
Note that this follows the "Encrypt-then-Authenticate (EtA) paradigm
recommended by Krawczyk [7].
To verify token T, perform the following steps:
1. Compare MAC(K_m, Version || Prot_ID || EA) to the MAC in the
token. If they don't match, reject the token.
2. Decrypt EA using K_e and IV to recover TI: TI = Decrypt(K_e, IV,
EA)
3. Break up TI into ET, SEQ, and S.
4. If the current time is after ET, the token is expired and should
be rejected.
5. If applicable, verify that the token is not on the ITL.
6. Deliver the token to the application
4.1. Key Rollover
One concern that people sometimes have is that you may wish to
periodically roll over keys. In general, this is not necessary since
modern cryptosystems do not require rekeying with the traffic volumes
relevant here. If this is a concern, then there are several easy
options, including adding a key ID, placing the sequence number in
the clear, or overloading the IV or protection suite ID. If only a
Rescorla Expires September 2, 2007 [Page 8]
Internet-Draft Stateless Tokens March 2007
few keys are used, trial verification can be used to determine which
one is active.
5. ITLs Data Structures
In this section, we discuss three data structures for maintaining the
ITL.
5.1. Simple Lists
The most natural implementation is to simply store a list of all the
invalid but unexpired tokens. This requires I*size(Token) bytes of
storage where I is the number of tokens. If you instead store a list
of sequence numbers, then the required storage becomes 4I. It's
probably a good idea to keep this list sorted so that binary search
can be used for looking up potential tokens. Note that if you have a
very high invalidity rate it is more efficient to maintain a valid
token list.
5.2. Bit Fields
In environments where a large fraction (> 1/32) of tokens will
eventually be invalidated, a superior data structure is a bitmask
vector. What needs to be recorded here is:
o The sequence number of the earliest valid token (the low-water
mark)
o A bit vector with one bit for every token from the low water mark
to the latest unexpired invalid token (the high-water mark).
For instance, if you have issued tokens 0-18 and tokens 1, 3, 5, 7,
11 12, and 15 have been invalidated, but tokens 0-7 have also
expired, you would need to store a low-water of 8 (the earliest valid
token), plus to store an 8-bit bitmask vector as shown in Figure 3.
Note that because the high-water mark is 15, there is no need to
store bits corresponding to sequence numbers 16-18.
1 1 1 1 1 1
8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+
|0 0 0 1 1 0 0 1|
+-+-+-+-+-+-+-+-+
Figure 3: Bitmask vector invalidation list
The bitmask may also be stored compressed (e.g., run length encoded),
though of course this provides slower access.
Rescorla Expires September 2, 2007 [Page 9]
Internet-Draft Stateless Tokens March 2007
5.3. Bloom Filters
With lower invalidation rates, Bloom filters [9] can be used to store
the ITL. Bloom filters have the significant advantage that they are
much smaller (about 10x smaller for bitmasks for 1% revocation
rates). They have the drawback that they have false positives
(tokens which appear to be invalidated but are not in fact invalid).
In settings where the state being stored is soft (e.g., [4]), this
isn't a problem but when it is hard state, then it can be. The Bloom
filter can be tuned for arbitrary false positive rates, but improved
specificity requires larger Bloom filter sizes.
Another issue with simple Bloom filters is that they do not allow you
to delete entries from the ITL when the token expires. The result is
that the filter fills up with expired tokens and produces a
monotonically increasing false positive rate. One approach here is
to use counting Bloom filters [10]. However, these can still
overflow and produce false positives. A superior solution is simply
to use multiple Bloom filters corresponding to different expiry
periods and then delete a Bloom filter once the current time sweeps
past the expiry period represented by the filter.
6. Security Considerations
In this section, we address a number of easy mistakes to make in
designing mechanisms of this type.
6.1. Failure to Authenticate
One common error is to simply encrypt the token without using any
authentication or message integrity. The result is that tokens are
susceptible to a variety of forgery attacks. This is a particular
problem if a stream cipher such as counter mode is used, because an
attacker can make targeted changes to any bit in the token, but
attacks are possible with CBC mode as well.
Consider a token format like the one presented in Figure 1 but
without an integrity check. The attacker contacts the server and
gets a state token T, containing his identity. The first block (128
bits) of ciphertext contain ET, SEQ, and the first 64 bits of S,
which contain the username, which we call I. The attacker wants to
pose as username I'. The attacker then generates a new IV' with the
low order 64-bits set to IV XOR I XOR I' and builds a new token T' =
IV' || EA. Because of the properties of CBC, when T' is decrypted
its first block will decrypt to EQ || SEQ || I', thus allowing a user
to pose as any other user. Such attacks are much more serious with
CTR mode, where the whole plaintext may be tampered with. This is
Rescorla Expires September 2, 2007 [Page 10]
Internet-Draft Stateless Tokens March 2007
simply a special case of the general cryptographic rule that
encryption cannot be counted on to provide integrity.
6.2. Failure to Encrypt
Encryption of tokens is not strictly necessary in order to provide
integrity for the tokens. However, in most settings it is desirable
to provide confidentiality. In the case of TLS tickets, that is
because secret keying material is carried in the token. In the case
of GRUUs one of the purposes of the construction is to provide
privacy. Therefore, despite the possibility that confidentiality is
not required, in general we recommend encrypting the data unless
there is a clear requirement for it not to be.
6.3. Distinguishable Encryption
In cases such as GRUU where privacy is a requirement, then it is
important for tokens to be unlinkable; at minimum, it must be
infeasible for an attacker to determine whether two tokens issued by
the same server correspond to the same or related underlying state
information. Optimally, it should be infeasible for an attacker to
determine whether two tokens were generated by the same server or
different servers (obviously, this depends on them using the same
token format and similar state value lengths.)
This places a requirement on the algorithms used to encrypt the
token; repeated encryptions of the same (or related) plaintexts must
produce ciphertexts that cannot be distinguished from encryptions of
different plaintexts. Specifically, block ciphers in ECB mode are
not suitable here and block ciphers in CBC or CTR mode require unique
initialization vectors. In order to avoid attackers determining the
temporal relationship between two tokens, the IV should be generated
with a cryptographically secure random or pseudorandom number
generator. This is also the rationale for encrypting the expiry time
and sequence number. Note, however, that this is a tradeoff; having
these values in the clear would allow immediate rejection of
invalidated or expired tokens. Instead, the server has to decrypt
the token in order to check its status.
6.4. Replay Attacks
As described in Section 5, if one wishes to be able to invalidate
tokens, one must keep state on the server. This is obvious in
contexts where you wish to invalidate tokens directly (such as
logout) but in cases where you simply wish one state to supersede
another, the necessity for invalidating the old state is less
obvious. However, the failure to do so subjects you to replay
attacks. Implementations which replace state tokens therefore need
Rescorla Expires September 2, 2007 [Page 11]
Internet-Draft Stateless Tokens March 2007
to maintain invalid token lists.
6.5. Token Binding
In order to prevent a token from being used outside its intended
context it may be necessary to bind the token to a set of verifiable
information associated with the intended context. For example, if a
token belongs to a particular user then including the username in the
token allows the server to verify that the user authenticated during
the current session is indeed the user that was issued the token.
Another possibility is to bind the token to a particular key that the
client possess and is included in the token (note that in this case
the token must be encrypted). Other information may be bound within
the token, which may further limit its use in other contexts. In
some cases privacy or other considerations may prevent inserting this
information into the token. In these cases the system should attempt
prevent the disclosure of the token to third parties through the use
of encryption and other access control mechanisms.
7. Acknowledgments
The material in Section 5 is based on the analysis in [8]. The
material in Section 6.5 was contributed by Joe Salowey. Thanks to
Joe Salowey for review comments.
8. References
8.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
8.2. Informational References
[2] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-Hashing
for Message Authentication", RFC 2104, February 1997.
[3] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509
Public Key Infrastructure Certificate and Certificate
Revocation List (CRL) Profile", RFC 3280, April 2002.
[4] Salowey, J., Zhou, H., Eronen, P., and H. Tschofenig,
"Transport Layer Security (TLS) Session Resumption without
Server-Side State", RFC 4507, May 2006.
[5] Rosenberg, J., "Obtaining and Using Globally Routable User
Rescorla Expires September 2, 2007 [Page 12]
Internet-Draft Stateless Tokens March 2007
Agent (UA) URIs (GRUU) in the Session Initiation Protocol
(SIP)", draft-ietf-sip-gruu-11 (work in progress),
October 2006.
[6] National Institute of Standards and Technology, "Specification
for the Advanced Encryption Standard (AES)", FIPS 197,
November 2001.
[7] Krawczyk, H., "The Order of Encryption and Authentication for
Protecting Communications (or: How Secure Is SSL?)",
CRYPTO 2001.
[8] Schacham, H., Boneh, D., and E. Rescorla, "Client-Side Caching
for TLS", ACM Trans. Info. & Sys. Security 7(4):553-75.
[9] Bloom, B., "Space/time trade-offs in hash coding with allowable
errors", Comm. ACM 13(7):422-6.
[10] Fan, L., Cao, P., Almeida, J., and A. Broder, "Summary Cache: A
Scalable Wide-Area Web Cache Sharing Protocol", SIGCOMM .
Author's Address
Eric Rescorla
Network Resonance
2483 E. Bayshore #212
Palo Alto, CA 94303
USA
Email: ekr@networkresonance.com
Rescorla Expires September 2, 2007 [Page 13]
Internet-Draft Stateless Tokens March 2007
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Rescorla Expires September 2, 2007 [Page 14]