nach oben

Designs, Codes and Cryptography

Erschienen in:

13.02.2017

Strengthening the security of authenticated key exchange against bad randomness

verfasst von: Michèle Feltz, Cas Cremers

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2018

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recent history has revealed that many random number generators (RNGs) used in cryptographic algorithms and protocols were not providing appropriate randomness, either by accident or on purpose. Subsequently, researchers have proposed new algorithms and protocols that are less dependent on the RNG. One exception is that all prominent authenticated key exchange (AKE) protocols are insecure given bad randomness, even when using good long-term keying material. We analyse the security of AKE protocols in the presence of adversaries that can perform attacks based on chosen randomness, i.e., attacks in which the adversary controls the randomness used in protocol sessions. We propose novel stateful protocols, which modify memory shared among a user’s sessions, and show in what sense they are secure against this worst case randomness failure. We develop a stronger security notion for AKE protocols that captures the security that we can achieve under such failures, and prove that our main protocol is correct in this model. Our protocols make substantially weaker assumptions on the RNG than existing protocols.

Vorheriger Artikel -double cyclic codes

Nächster Artikel Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness

Nur mit Berechtigung zugänglich

Note that our syntax implies that all randomness required during the execution of session s is deterministically derived from \(s_{ rand }\).

The crucial observation is that the protocol execution algorithm P in [12] uses abstract session-specific state information for a user U’s session i, denoted by \( St ^{i}_{U}\). Additionally, the framework includes user-specific information: the identity U, and public/private keys \( pk _{U}, sk _{U}\). It follows from their definition of the protocol execution algorithm that a protocol can only update the session-specific state \( St ^{i}_{U}\), but cannot change any state that can be accessed by other sessions of the same user. Hence, stateful protocols are not modeled in their framework.

Note that the ephemeral secret keys x and y can either be stored in a session-specific variable and reused in the key derivation phase or recomputed in the key derivation phase.

In the long version of this paper, the class \(\varLambda \) is referred to as \(\mathsf {INDP\text {-}DH} \cap \mathsf {ISM} \).

We do not need to keep consistency with \(H_{1}\) queries via lookup in table J since the probability that the adversary guesses the randomness of a session created via a query \(\mathsf {create} \) is negligible.

Here we need to keep consistency with \(H_{1}\) queries via lookup in table J to be able to consistently answer all possible combinations of queries. Consider, e. g., the following scenario. The adversary first issues a query \((x,\mathsf{sk}_{\hat{P}},i)\) to \(H_{1}\) and then issues the query \(\mathsf {cr\text{- }create} (\hat{P},r,x,\hat{Q})\), which increments the current counter value \(i-1\) by 1 so that the counter value used in session \(s=(\hat{P},i)\) is i. So, in contrast to the NAXOS proof with respect to model eCK\(^{w}\), we need to additionally keep consistency between \(\mathsf {cr\text{- }create} \) queries and queries to the random oracle for \(H_{1}\).

Note that \(s^{*}_{ rand }\) is not used in the calculation.

This entry exists in table Q since the status of the session is different to \(\bot \).

Under event \(A_{1}\) the query \(\mathsf {randomness} \) (e. g., for two sessions of different users) together with other queries might enable the adversary to learn all the information necessary to compute the session key of the target session without violating the freshness condition.

The value of \(l_{s'}\) is the concatenation of the randomness of the current and the previous sessions of the same user.

Debian, Debian Security Advisory DSA-1571-1 openssl—predictable random number generator. http://www.debian.org/security/2008/dsa-1571. Accessed 05 Nov 2013.

Lenstra A., Hughes J., Augier M., Bos J., Kleinjung T., Wachter C.: Public keys. In: Advances in Cryptology (Crypto 2012). LNCS, vol. 7417, pp. 626–642. Springer, Heidelberg (2012).

Marvin R.: Google admits an Android crypto PRNG flaw led to Bitcoin heist (2013). http://sdt.bz/64008 Accessed 01 Oct 2013.

Perlroth N., Larson J., Shane S.: N.S.A. able to foil basic safeguards of privacy on web. The New York Times (2013).

Koblitz N., Menezes A.: The random oracle model: a twenty-year retrospective. Cryptology ePrint Archive, Report 2015/140 (2015). http://eprint.iacr.org/.

Bernstein D.J., Lange T., Niederhagen R.: Dual EC: a standardized back door. Cryptology ePrint Archive, Report 2015/767 (2015). http://eprint.iacr.org/. Accessed July 2015.

Pornin T.: Deterministic usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), RFC 6979 (2013).

Bellare M., Brakerski Z., Naor M., Ristenpart T., Segev G., Shacham H., Yilek S.: Hedged public-key encryption: how to protect against bad randomness. In: Advances in Cryptology (ASIACRYPT 2009). LNCS, pp. 232–249. Springer, Heidelberg (2009).

Yilek S.: Resettable public-key encryption: how to encrypt on a virtual machine. In: Proceedings of the 2010 International Conference on Topics in Cryptology (CT-RSA’10), pp. 41–56. Springer, Berlin (2010).

10.

LaMacchia B., Lauter K., Mityagin A.: Stronger security of authenticated key exchange. In: Susilo W., Liu J.K., Mu Y. (eds.) ProvSec’07. LNCS, vol. 4784, pp. 1–16. Springer, Berlin (2007).

11.

Canetti R., Krawczyk H.: Analysis of key-exchange protocols and their use for building secure channels. In: Pfitzmann B. (ed.) EUROCRYPT’01. LNCS, vol. 2045, pp. 453–474. Springer, London (2001).

12.

Yang G., Duan S., Wong D.S., Tan C.H., Wang H.: Authenticated key exchange under bad randomness. In: Proceedings of the 15th International Conference on Financial Cryptography and Data Security. FC’11, pp. 113–126. Springer, Berlin (2012). doi:10.1007/978-3-642-27576-0_10.

13.

Ristenpart T., Yilek S.: When good randomness goes bad: virtual machine reset vulnerabilities and hedging deployed cryptography. In: Proceedings of the Network and Distributed System Security Symposium (NDSS’10) (2010).

14.

Kamara S., Katz J.: How to encrypt with a malicious random number generator. In: Fast Software Encryption. LNCS, vol. 5086, pp. 303–315. Springer, Berlin (2008).

15.

Bellare M., Tackmann B.: Nonce-based cryptography: retaining security when randomness fails. Cryptology ePrint Archive, Report 2016/290 (2016). http://eprint.iacr.org/.

16.

Krawczyk H.: HMQV: a high-performance secure Diffie–Hellman protocol. In: Shoup, V. (ed.) Advances in Cryptology (CRYPTO 2005). LNCS, vol. 3621, pp. 546–566. Springer, Berlin (2005).

17.

Ustaoglu B.: Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS. Cryptology ePrint Archive, Report 2007/123, 2007, version June 22 (2009).

18.

Blake-Wilson S., Johnson D., Menezes A.: Key agreement protocols and their security analysis. In: Darnell M. (ed.) Crytography and Coding. LNCS, vol. 1355, pp. 30–45. Springer, Berlin (1997). doi:10.1007/BFb0024447.

19.

Cremers C., Feltz M.: Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal. Des. Codes Cryptogr. 74(1), 183–218 (2015).MathSciNetCrossRefMATH

20.

Brzuska C., Fischlin M., Warinschi B., Williams S.: Composability of Bellare-Rogaway key exchange protocols. In: Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS’11). pp. 51–62. ACM, New York (2011). doi:10.1145/2046707.2046716.

21.

Boyd C., Cremers C., Feltz M., Paterson K., Poettering B., Stebila D.: ASICS: authenticated key exchange security incorporating certification systems. In: Crampton J., Jajodia S., Mayes K. (eds.) Computer Security (ESORICS 2013). LNCS, vol. 8134, pp. 381–399. Springer, Berlin (2013).

22.

Bellare M., Rogaway P.: Entity authentication and key distribution. In: 13th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO’93), pp. 232–249. Springer, New York (1994).

23.

Bellare M., Rogaway P.: Provably secure session key distribution: the three party case. In: 27th Annual ACM Symposium on Theory of Computing (STOC’95), pp. 57–66. ACM, New York (1995).

24.

Bellare M., Pointcheval D., Rogaway P.: Authenticated key exchange secure against dictionary attacks. In: 19th International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT’00), pp. 139–155. Springer, Berlin (2000).

25.

Cremers C., Feltz M.: Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal. In: Proceedings of the 17th European Conference on Research in Computer Security. ESORICS. Springer, Berlin (2012).

26.

Okamoto T., Pointcheval D.: The gap-problems: a new class of problems for the security of cryptographic schemes. In: Kim K. (ed.) PKC’2001. LNCS, vol. 1992, pp. 104–118. Springer, Berlin (2001).

27.

Feltz M., Cremers C.: On the limits of authenticated key exchange security with an application to bad randomness. Cryptology ePrint Archive, Report 2014/369 (2014). http://eprint.iacr.org/.

28.

Choo K.-K.R., Boyd C., Hitchcock Y.: Examining indistinguishability-based proof models for key establishment protocols. In: Advances in Cryptology—ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, 4–8 Dec 2005, Proceedings. Lecture Notes in Computer Science, vol. 3788, pp. 585–604. Springer, Berlin (2005).

29.

Schneier B., Fredrikson M., Kohno T., Ristenpart T.: Surreptitiously weakening cryptographic systems. Cryptology ePrint Archive, Report 2015/097 (2015). http://eprint.iacr.org/. Accessed March 2015.

Titel: Strengthening the security of authenticated key exchange against bad randomness
verfasst von: Michèle Feltz
Cas Cremers
Publikationsdatum: 13.02.2017
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2018
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-017-0337-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2018

Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness

Improved, black-box, non-malleable encryption from semantic security

New families of balanced symmetric functions and a generalization of Cusick, Li and Stǎnicǎ’s conjecture

Connecting tweakable and multi-key blockcipher security

Infinite families of 3-designs from a type of five-weight code

A family of semifields in odd characteristic