< draft-horowitz-key-derivation-01.txt		draft-horowitz-key-derivation-02.txt >
	Network Working Group M. Horowitz		Network Working Group M. Horowitz
	<draft-horowitz-key-derivation-01.txt> Cygnus Solutions		<draft-horowitz-key-derivation-02.txt> Stonecast, Inc.
	Internet-Draft March, 1997		Internet-Draft August, 1998
	Key Derivation for Authentication, Integrity, and Privacy		Key Derivation for Authentication, Integrity, and Privacy
	Status of this Memo		Status of this Memo
	This document is an Internet-Draft. Internet-Drafts are working		This document is an Internet-Draft. Internet-Drafts are working
	documents of the Internet Engineering Task Force (IETF), its areas,		documents of the Internet Engineering Task Force (IETF), its areas,
	and its working groups. Note that other groups may also distribute		and its working groups. Note that other groups may also distribute
	working documents as Internet-Drafts.		working documents as Internet-Drafts.
	Internet-Drafts are draft documents valid for a maximum of six months		Internet-Drafts are draft documents valid for a maximum of six months
	and may be updated, replaced, or obsoleted by other documents at any		and may be updated, replaced, or obsoleted by other documents at any
	time. It is inappropriate to use Internet-Drafts as reference		time. It is inappropriate to use Internet-Drafts as reference
	material or to cite them other than as ``work in progress.''		material or to cite them other than as ``work in progress.''
	To learn the current status of any Internet-Draft, please check the		To learn the current status of any Internet-Draft, please check the
	``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow		``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
	Directories on ds.internic.net (US East Coast), nic.nordu.net		Directories on ftp.ietf.org (US East Coast), nic.nordu.net
	(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific		(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific
	Rim).		Rim).
	Distribution of this memo is unlimited. Please send comments to the		Distribution of this memo is unlimited. Please send comments to the
	author.		author.
	Abstract		Abstract
	Recent advances in cryptography have made it desirable to use longer		Recent advances in cryptography have made it desirable to use longer
	cryptographic keys, and to make more careful use of these keys. In		cryptographic keys, and to make more careful use of these keys. In
	particular, it is considered unwise by some cryptographers to use the		particular, it is considered unwise by some cryptographers to use the
	same key for multiple purposes. Since most cryptographic-based		same key for multiple purposes. Since most cryptographic-based
	systems perform a range of functions, such as authentication, key		systems perform a range of functions, such as authentication, key
	exchange, integrity, and encryption, it is desirable to use different		exchange, integrity, and encryption, it is desirable to use different
	cryptographic keys for these purposes.		cryptographic keys for these purposes.
	This document does not define a particular protocol, but defines a set of		This RFC does not define a particular protocol, but defines a set of
	cryptographic transformations for use with arbitrary network		cryptographic transformations for use with arbitrary network
	protocols and block cryptographic algorithm.		protocols and block cryptographic algorithm.
	Deriving Keys		Deriving Keys
	In order to use multiple keys for different functions, there are two		In order to use multiple keys for different functions, there are two
	possibilities:		possibilities:
	- Each protocol ``key'' contains multiple cryptographic keys. The		- Each protocol ``key'' contains multiple cryptographic keys. The
	implementation would know how to break up the protocol ``key'' for		implementation would know how to break up the protocol ``key'' for
	skipping to change at page 2, line 37 ¶		skipping to change at page 2, line 37 ¶
	Since the derived key has as much entropy as the base keys (if the		Since the derived key has as much entropy as the base keys (if the
	cryptosystem is good), password-derived keys have the full benefit of		cryptosystem is good), password-derived keys have the full benefit of
	all the entropy in the password.		all the entropy in the password.
	To generate a derived key from a base key:		To generate a derived key from a base key:
	Derived Key = DK(Base Key, Well-Known Constant)		Derived Key = DK(Base Key, Well-Known Constant)
	where		where
	DK(Key, Constant) = n-truncate(E(Key, Constant))		DK(Key, Constant) = k-truncate(E(Key, Constant))
	In this construction, E(Key, Plaintext) is a block cipher, Constant		In this construction, E(Key, Plaintext) is a block cipher, Constant
	is a well-known constant defined by the protocol, and n-truncate		is a well-known constant defined by the protocol, and k-truncate
	truncates its argument by taking the first n bits; here, n is the key		truncates its argument by taking the first k bits; here, k is the key
	size of E.		size of E.
	If the output of E is is shorter than n bits, then some entropy in		If the output of E is is shorter than k bits, then some entropy in
	the key will be lost. If the Constant is smaller than the block size		the key will be lost. If the Constant is smaller than the block size
	of E, then it must be padded so it may be encrypted. If the Constant		of E, then it must be padded so it may be encrypted. If the Constant
	is larger than the block size, then it must be folded down to the		is larger than the block size, then it must be folded down to the
	block size to avoid chaining, which affects the distribution of		block size to avoid chaining, which affects the distribution of
	entropy.		entropy.
	In any of these situations, a variation of the above construction is		In any of these situations, a variation of the above construction is
	used, where the folded Constant is encrypted, and the resulting		used, where the folded Constant is encrypted, and the resulting
	output is fed back into the encryption as necessary (the | indicates		output is fed back into the encryption as necessary (the | indicates
	concatentation):		concatentation):
	K1 = E(Key, n-fold(Constant))		K1 = E(Key, n-fold(Constant))
	K2 = E(Key, K1)		K2 = E(Key, K1)
	K3 = E(Key, K2)		K3 = E(Key, K2)
	K4 = ...		K4 = ...
	DK(Key, Constant) = n-truncate(K1 | K2 | K3 | K4 ...)		DK(Key, Constant) = k-truncate(K1 | K2 | K3 | K4 ...)
	n-fold is an algorithm which takes m input bits and ``stretches''		n-fold is an algorithm which takes m input bits and ``stretches''
	them to form n output bits with no loss of entropy, as described in		them to form n output bits with no loss of entropy, as described in
	[Blumenthal96]. In this document, n-fold is always used to produce n		[Blumenthal96]. In this document, n-fold is always used to produce n
	bits of output, where n is the key size of E.		bits of output, where n is the block size of E.
	If the size of the Constant is not equal to the block size of E, then		If the size of the Constant is not equal to the block size of E, then
	the Constant must be n-folded to the block size of E. This number is		the Constant must be n-folded to the block size of E. This string is
	used as input to E. If the block size of E is less than the key		used as input to E. If the block size of E is less than the key
	size, then the output from E is taken as input to a second invocation		size, then the output from E is taken as input to a second invocation
	of E. This process is repeated until the number of bits accumulated		of E. This process is repeated until the number of bits accumulated
	is greater than or equal to the key size of E. When enough bits have		is greater than or equal to the key size of E. When enough bits have
	been computed, the first n are taken as the derived key.		been computed, the first k are taken as the derived key.
	Since the derived key is the result of one or more encryptions in the		Since the derived key is the result of one or more encryptions in the
	base key, deriving the base key from the derived key is equivalent to		base key, deriving the base key from the derived key is equivalent to
	determining the key from a very small number of plaintext/ciphertext		determining the key from a very small number of plaintext/ciphertext
	pairs. Thus, this construction is as strong as the cryptosystem		pairs. Thus, this construction is as strong as the cryptosystem
	itself.		itself.
	Deriving Keys from Passwords		Deriving Keys from Passwords
	When protecting information with a password or other user data, it is		When protecting information with a password or other user data, it is
	necessary to convert an arbitrary bit string into an encryption key.		necessary to convert an arbitrary bit string into an encryption key.
	In addition, it is sometimes desirable that the transformation from		In addition, it is sometimes desirable that the transformation from
	password to key be difficult to reverse. A simple variation on the		password to key be difficult to reverse. A simple variation on the
	construction in the prior section can be used:		construction in the prior section can be used:
	Key = DK(n-fold(Password), Well-Known Constant)		Key = DK(k-fold(Password), Well-Known Constant)
	The n-fold algorithm is reversible, so recovery of the n-fold output		k-fold is same algorithm as n-fold, used to fold the Password into
	is equivalent to recovery of Password. However, recovering the n-		the same number of bits as the key of E.
			The k-fold algorithm is reversible, so recovery of the k-fold output
			is equivalent to recovery of Password. However, recovering the k-
	fold output is difficult for the same reason recovering the base key		fold output is difficult for the same reason recovering the base key
	from a derived key is difficult.		from a derived key is difficult.
	Traditionally, the transformation from plaintext to ciphertext, or		Traditionally, the transformation from plaintext to ciphertext, or
	vice versa, is determined by the cryptographic algorithm and the key.		vice versa, is determined by the cryptographic algorithm and the key.
	A simple way to think of derived keys is that the transformation is		A simple way to think of derived keys is that the transformation is
	determined by the cryptographic algorithm, the constant, and the key.		determined by the cryptographic algorithm, the constant, and the key.
	For interoperability, the constants used to derive keys for different		For interoperability, the constants used to derive keys for different
	purposes must be specified in the protocol specification. The		purposes must be specified in the protocol specification. Also, the
	constants must not be specified on the wire, or else an attacker who		endian order of the keys must be specified.
	determined one derived key could provide the associated constant and
	spoof data using that derived key, rather than the one the protocol		The constants must not be specified on the wire, or else an attacker
	designer intended.		who determined one derived key could provide the associated constant
			and spoof data using that derived key, rather than the one the
			protocol designer intended.
	Determining which parts of a protocol require their own constants is		Determining which parts of a protocol require their own constants is
	an issue for the designer of protocol using derived keys.		an issue for the designer of protocol using derived keys.
	Security Considerations		Security Considerations
	This entire document deals with security considerations relating to		This entire document deals with security considerations relating to
	the use of cryptography in network protocols.		the use of cryptography in network protocols.
			Appendix
			This Appendix quotes the n-fold algorithm from [Blumenthal96]. It is
			provided here as a convenience to the implementor. Sample vectors
			are also included. It should be noted that the sample vector in
			Appendix B.2 of the original paper appears to be incorrect. Two
			independent implementations from the specification (one in C by the
			author, and another in Scheme by Bill Sommerfeld) agree on a value
			different from that in [Blumenthal96].
			We first define a primitive called n-folding, which takes a
			variable-length input block and produces a fixed-length output
			sequence. The intent is to give each input bit approximately
			equal weight in determining the value of each output bit. Note
			that whenever we need to treat a string of bytes as a number, the
			assumed representation is Big-Endian -- Most Significant Byte
			first.
			To n-fold a number X, replicate the input value to a length that
			is the least common multiple of n and the length of X. Before
			each repetition, the input is rotated to the right by 13 bit
			positions. The successive n-bit chunks are added together using
			1's-complement addiiton (that is, with end-around carry) to yield
			a n-bit result....
			The result is the n-fold of X. Here are some sample vectors, in
			hexadecimal. For convenience, the inputs are ASCII encodings of
			strings.
			64-fold("012345") =
			64-fold(303132333435) = be072631276b1955
			56-fold("password") =
			56-fold(70617373776f7264) = 78a07b6caf85fa
			64-fold("Rough Consensus, and Running Code") =
			64-fold(526f75676820436f6e73656e7375732c20616e642052756e
			6e696e6720436f6465) = bb6ed30870b7f0e0
			168-fold("password") =
			168-fold(70617373776f7264) = 59e4a8ca7c0385c3c37b3f6d2000247cb6e6bd5b3e
			192-fold("MASSACHVSETTS INSTITVTE OF TECHNOLOGY"
			192-fold(4d41535341434856534554545320494e5354495456544520
			4f4620544543484e4f4c4f4759) =
			db3b0d8f0b061e603282b308a50841229ad798fab9540c1b
	Acknowledgements		Acknowledgements
	I would like to thank Uri Blumenthal, Hugo Krawczyk, and Bill		I would like to thank Uri Blumenthal, Hugo Krawczyk, and Bill
	Sommerfeld for their contributions to this document.		Sommerfeld for their contributions to this document.
	References		References
	[Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like		[Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like
	Ciphers", Proceedings of PRAGOCRYPT '96, 1996.		Ciphers", Proceedings of PRAGOCRYPT '96, 1996.
	Author's Address		Author's Address
	Marc Horowitz		Marc Horowitz
	Cygnus Solutions		Stonecast, Inc.
	955 Massachusetts Avenue		108 Stow Road
	Cambridge, MA 02139		Harvard, MA 01451
	Phone: +1 617 354 7688		Phone: +1 978 456 9103
	Email: marc@cygnus.com		Email: marc@stonecast.net
End of changes. 16 change blocks.
	23 lines changed or deleted		75 lines changed or added
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/