Abstract
We study the suitability of common pseudorandomnessmodes associated with cryptographic hash functions and block ciphers (CBC-MAC, Cascade and HMAC) for the task of “randomness extraction”, namely, the derivation of keying material from semi-secret and/or semi-random sources. Important applications for such extractors include the derivation of strong cryptographic keys from non-uniform sources of randomness (for example, to extract a seed for a pseudorandom generator from a weak source of physical or digital noise), and the derivation of pseudorandom keys from a Diffie-Hellman value.
Extractors are closely related in their applications to pseudorandom functions and thus it is attractive to (re)use the common pseudorandom modes as randomness extractors. Yet, the crucial difference between pseudorandom generation and randomness extraction is that the former uses random secret keys while the latter uses random but known keys. We show that under a variety of assumptions on the underlying primitives (block ciphers and compression functions), ranging from ideal randomness assumptions to realistic universal-hashing properties, these modes induce good extractors. Hence, these schemes represent a more practical alternative to combinatorial extractors (that are seldom used in practice), and a better-analyzed alternative to the common practice of using SHA-1 or MD5 (as a single un-keyed function) for randomness extraction. In particular, our results serve to validate the method of key extraction and key derivation from Diffie-Hellman values used in the IKE (IPsec’s Key Exchange) protocol.
Extended abstract. Full version available at eprint.iacr.org/2004/
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barak, B., Shaltiel, R., Tromer, E.: True Random Number Generators Secure in a Changing Environment. In: CHESS 2003, pp. 166–180 (2003)
Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Bellare, M., Canetti, R., Krawczyk, H.: Pseudorandom Functions Revisited: The Cascade Construction and Its Concrete Security. In: Proc. 37th FOCS, pp. 514–523. IEEE, Los Alamitos (1996)
Bellare, M., Kilian, J., Rogaway, P.: The Security of Cipher Block Chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994)
Carter, L., Wegman, M.N.: Universal Classes of Hash Functions. JCSS 18(2), 143–154 (1979)
Damgard, I.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Gennaro, R., Krawczyk, H., Rabin, T.: Secure Hashed Diffie-Hellman over Non-DDH Groups. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 361–381. Springer, Heidelberg (2004)
Goldreich, O.: Foundations of Cryptography. Cambridge University Press, Cambridge (2001), Preliminary version http://philby.ucsd.edu/cryptolib.html/
Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: Construction of a Pseudo-random Generator from any One-way Function. SIAM. J. Computing 28(4), 1364–1396 (1999)
IKEv2. Internet Key Exchange (IKEv2) Protocol, draft-ietf-ipsec-ikev2- 13.txt (to be published as an RFC). Editor: C. Kaufman (March 2004)
Krawczyk, H.: SIGMA: The ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 400–425. Springer, Heidelberg (2003)
Luby, M.: Pseudorandomness and Cryptographic Applications, January 1996. Princeton Computer Science Note. Princeton University Press, Princeton (January 1996)
Harkins, D., Carrel, D.: RFC2409. The Internet Key Exchange (IKE) (November 1998)
Shaltiel, R.: Recent developments in Extractors. Bulletin of the European Association for Theoretical Computer Science 77, 67–95 (2002), Available at: http://www.wisdom.weizmann.ac.il/~ronens/papers/survey.ps
Stinson, D.R.: Universal Hashing and Authentication Codes. Designs, Codes and Cryptography 4, 369–380 (1994)
Wegman, M.N., Carter, L.: New Hash Functions and Their Use in Authentication and Set Equality. JCSS 22(3), 265–279 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dodis, Y., Gennaro, R., Håstad, J., Krawczyk, H., Rabin, T. (2004). Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive