HMAC is a randomness extractor and applications to TLS

ABSTRACT

In this paper, we study the security of a practical randomness extractor and its application in the TLS standard. Randomness extraction is the first stage of key derivation functions since the secret shared between the entities does not always come from a uniformly distributed source. More precisely, we wonder if the Hmac function, used in many standards, can be considered as a randomness extractor? We show that when the shared secret is put in the key space of the Hmac function, there are two cases to consider depending on whether the key is larger than the block-length of the hash function or not. In both cases, we provide a formal proof that the output is pseudo-random, but under different assumptions. Nevertheless, all the assumptions are related to the fact that the compression function of the underlying hash function behaves like a pseudo-random function. This analysis allows us to prove the TLS randomness extractor for Diffie-Hellman and RSA key exchange. Of independent interest, we study a computational analog to the leftover hash lemma for computational almost universal hash function families: any pseudo-random function family matches the latter definition.

REFERENCES

• 1: B. Barak, R. Shaltiel, and E. Tromer. True random number generators secure in a changing environment. In C. D. Walter, Çetin Kaya Koç, and C. Paar, editors, CHES 2003, volume 2779 of LNCS, pages 166--180. Springer, Sept. 2003.
• 2: M. Bellare. New proofs for NMAC and HMAC: security without collision-resistance. In Crypto '06, LNCS 4117. Springer-Verlag, Berlin, 2006.
• 3: Mihir Bellare , Ran Canetti , Hugo Krawczyk, Keying Hash Functions for Message Authentication, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.1-15, August 18-22, 1996
• 4: M. Bellare, R. Canetti, and H. Krawczyk. Message authentication using hash functions: the hmac construction. RSA Laboratories' Cryptobytes, 2(1), Spring 1996.
• 5: M. Bellare, R. Cannetti, and H. Krawczyk. HMAC: keyed-hashing for message authentication, february 1997. RFC 2104 Available from http://www.ietf.org/rfc.html.
• 6: R. Canetti, J. Friedlander, S. Konyagin, M. Larsen, D. Lieman, and I. Shparlinski. On the statistical properties of Diffie-Hellman distributions. Israel Journal of Mathemathics, 120:23--46, 2000.
• 7: R. Canetti, J. Friedlander, and I. Shparlinski. On certain exponential sums and the distribution of Diffie-Hellman triples. Journal of the London Mathematical Society, 59(2):799--812, 1999.
• 8: O. Chevassut, P. A. Fouque, P. Gaudry, and D. Pointcheval. The twist-augmented technique for key exchange. In PKC '06, LNCS. Springer-Verlag, Berlin, 2006.
• 9: Q. Dang and T. Polk. Hash-based key derivation function (hkd). draft-dang-nistkdf-01.txt, June 2006.
• 10: T. Dierks , C. Allen, The TLS Protocol Version 1.0, RFC Editor, 1999
• 11: T. Dierks and E. Rescorla. The Transport Layer Security (TLS) protocol version 1.2, July 2007. Internet Request for Comment RFC 4346 bis, Internet Engineering Task Force.
• 12: Y. Dodis, R. Gennaro, J. Håstad, H. Krawczyk, and T. Rabin. Randomness extraction and key derivation using the CBC, cascade and HMAC modes. In Crypto '04, LNCS, pages 494--510. Springer-Verlag, Berlin, 2004.
• 13: P.-A. Fouque, D. Pointcheval, J. Stern, and S. Zimmer. Hardness of distinguishing the MSB or LSB of secret keys in Diffie-Hellman schemes. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, ICALP 2006, Part II, volume 4052 of LNCS, pages 240--251. Springer, July 2006.
• 14: R. Gennaro, H. Krawczyk, and T. Rabin. Secure hashed Diffie-Hellman over non-DDH groups. In Eurocrypt '04, LNCS 3027, pages 361--381. Springer-Verlag, Berlin, 2004.
• 15: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 16: R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proc. of the 30th FOCS, pages 248--253. IEEE, New York, 1989.
• 17: Jakob Jonsson , Burton S. Kaliski, Jr., On the Security of RSA Encryption in TLS, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.127-142, August 18-22, 2002
• 18: C. Kaufman. RFC 4306: Internet Key Exchange (IKEv2) protocol, Dec. 2005.
• 19: Recommendations for pair-wise key establishment schemes using discrete logarithm cryptography (revised). NIST Special Publications 800--56A, Mar. 2007.
• 20: Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, New York, NY, 2005

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
HMAC, TLS, key extraction, randomness extraction