nach oben

Journal of Cryptology

Erschienen in:

19.08.2016

Merkle’s Key Agreement Protocol is Optimal: An \(O(n^2)\) Attack on Any Key Agreement from Random Oracles

verfasst von: Boaz Barak, Mohammad Mahmoody

Erschienen in: Journal of Cryptology | Ausgabe 3/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We prove that every key agreement protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary who makes \(O(n^2)\) queries to the oracle. This improves on the previous \({\tilde{\Omega }}(n^6)\) query attack given by Impagliazzo and Rudich (STOC ’89) and resolves an open question posed by them. Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with n queries to a random oracle and cannot be broken by any adversary who asks \(o(n^2)\) queries.

Vorheriger Artikel Locally Computable UOWHF with Linear Shrinkage

Nächster Artikel Short Signatures from Diffie–Hellman: Realizing Almost Compact Public Key

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In this work, random oracles denote any randomized oracle \(O :\{0,1\}^* \mapsto \{0,1\}^*\) such that O(x) is independent of \(O(\{0,1\}^* \setminus \left\{ x \right\} )\) for every x (see Definition 2.2). The two protocols of Merkle we describe here can be implemented using a length-preserving random oracle (by cutting the inputs and the output to the right length). Our negative results, on the other hand, apply to any random oracle.

This is not to be confused with some more recent works such as [6], that combine the random oracle model with assumptions on the intractability of other problems such as factoring or the RSA problem to obtain more efficient cryptographic constructions.

More accurately, [17] gave an \(O(m^6\log m)\)-query attack where m is the maximum of the number of queries n and the number of communication rounds, though we believe their analysis could be improved to an \(O(n^6\log n)\)-query attack. For the sake of simplicity, when discussing [17]’s results we will assume that \(m = n\), though for our result we do not need this assumption.

The proof of this statement for the case of non-uniform adversaries is quite non-trivial; see [12] for a proof.

This argument applies to our result as well, and of course extends to any other primitive that is implied by random oracles (e.g., collision-resistant hash functions) in a black-box way.

These numbers are just an example, and in practical applications the constant terms will make an important difference; however, we note that these particular constants are not ruled out by [17]’s attack but are ruled out by ours by taking number of operations to mean the number of calls to the oracle.

We are not aware of any perfectly complete n-query key agreement protocol in the random oracle with \(\omega (n)\) security. In other words, it seems conceivable that all such protocols could be broken with a linear number of queries.

For example, a non-adaptive attacker who prepares all of its oracle queries and then asks them in one shot, has round complexity one.

[16] proved this result for a larger class of oracles, see [16] for more details.

Readers familiar with the setting of communication complexity may note that this is analogous to the well-known fact that conditioning on any transcript of a 2-party communication protocol results in a product distribution (i.e., combinatorial rectangle) over the inputs. However, things are different in the presence of a random oracle.

As a simple example for such dependence consider a protocol where in the first round Alice chooses x (which is going to be the shared key) to be either the string \(0^n\) or \(1^n\) at random, queries the oracle H at x and sends \(y=H(x)\) to Bob. Bob then makes the query \(1^n\) and gets \(y'=H(1^n)\). Now even if Alice chose \(x=0^n\) and hence Alice and Bob have no intersection queries, Bob can find out the value of x just by observing that \(y'\ne y\). Still, an attacker must ask a non-intersection query such as \(1^n\) to know if \(x=0^n\) or \(x=1^n\).

Our results extend to the case where the probabilities are not necessarily rational numbers; however, since every reasonable candidate random oracle we are aware of satisfies this rationality condition, and it avoids some technical subtleties, we restrict attention to oracles that satisfy it. In Sect. 4.2 we show how to remove this restriction.

We use the term seminormal to distinguish it from the normal-form protocols defined in [17].

Impagliazzo and Rudich [17] use the term normal form for protocols in which each party asks exactly one query before sending their messages in every round.

Also note that \(M_i\) is not necessarily the same as \(M^i\). The latter refers to the transcript till the ith message of the protocol is sent, while the former refers to the messages till Bob is going to ask his ith messages (and might ask zero or more than one queries in some rounds).

A similar observation was made by [17], see Lemma 6.5 there.

Note that \(V_A, V_B\) uniquely determine M, P so \(\Pr [V_A, V_B, M, P] = \Pr [V_A,V_B]\) holds for consistent \(V_A, V_B, M, P\), but we choose to write the full event’s description for clarity.

C.H. Bennett , G. Brassard, A.K. Ekert, Quantum cryptography. Sci. Am. 267(4), 50–57 (1992)

E. Biham, Y.J. Goren, Y. Ishai, Basing weak public-key cryptography on strong one-way functions, in TCC (Ran Canetti, ed.). Lecture Notes in Computer Science, vol. 4948 (Springer, 2008), pp. 55–72.

G. Brassard, P. Høyer, K. Kalach, M. Kaplan, S. Laplante, L. Salvail, Merkle puzzles in a quantum world, in CRYPTO (Phillip Rogaway, ed.). Lecture Notes in Computer Science, vol. 6841 (Springer, 2011), pp. 391–410.

Z. Brakerski, J. Katz, G. Segev, A. Yerukhimovich, Limits on the power of zero-knowledge proofs in cryptographic constructions, in TCC (Yuval Ishai, ed.). Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp. 559–578.

B. Barak, M. Mahmoody-Ghidary, Merkle puzzles are optimal— an O (n \(^2\))-query attack on any key exchange from a random oracle, in CRYPTO (Shai Halevi, ed.). Lecture Notes in Computer Science, vol. 5677 (Springer, 2009), pp. 374–390.

M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in ACM Conference on Computer and Communications Security (1993), pp. 62–73.

G. Brassard, L. Salvail, Quantum merkle puzzles, in International Conference on Quantum, Nano and Micro Technologies (ICQNM), IEEE Computer Society (2008), pp. 76–79.

R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. JACM: J. ACM 51(4), 557–594 (2004)

R. Cleve, Limits on the security of coin flips when half the processors are faulty (extended abstract), in Annual ACM Symposium on Theory of Computing (Berkeley, California), 28–30 May (1986), pp. 364–369.

10.

W. Diffie, M, Hellman, New directions in cryptography. IEEE Trans. Inf. Theory IT-22(6), 644–654 (1976)

11.

D. Dachman-Soled, Y. Lindell, M. Mahmoody, T. Malkin, On the black-box complexity of optimally-fair coin tossing, in Y. Ishai, ed. TCC. Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp. 450–467.

12.

R. Gennaro, Y. Gertner, J. Katz, L. Trevisan, Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)

13.

L.K. Grover, A fast quantum mechanical algorithm for database search, in Annual ACM Symposium on Theory of Computing (STOC), 22–24 May (1996), pp. 212–219.

14.

I. Haitner, J.J. Hoch, O. Reingold, G. Segev, Finding collisions in interactive protocols—a tight lower bound on the round complexity of statistically-hiding commitments, in Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE (2007), pp. 669–679.

15.

T. Holenstein, Complexity theory (2015). http://www.complexity.ethz.ch/education/Lectures/ComplexityFS15/skript_printable.pdf

16.

I. Haitner, E. Omri, H. Zarosim, Limits on the usefulness of random oracles, in A. Sahai, ed. Theory of Cryptography, TCC. Lecture Notes in Computer Science, vol. 7785 (Springer, 2013), pp. 437–456.

17.

R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in Annual ACM Symposium on Theory of Computing (STOC) (1989). Full version available from Russell Impagliazzo’s home page https://cseweb.ucsd.edu/~russell/secret.ps, pp. 44–61.

18.

J. Katz, D. Schröder, A. Yerukhimovich, Impossibility of blind signatures from one-way permutations, in Yuval Ishai, ed. TCC. Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp. 615–629.

19.

R.C. Merkle, C.S. 244 project proposal (1974). http://merkle.com/1974/

20.

R.C. Merkle, Secure communications over insecure channels. Commun. ACM 21(4), 294–299 (1978)

21.

M. Mahmoody, H.K Maji, M. Prabhakaran, Limits of random oracles in secure computation, in Proceedings of the 5th conference on Innovations in theoretical computer science, ACM (2014), pp. 23–34.

22.

M. Mahmoody, T. Moran, S.P. Vadhan, Time-lock puzzles in the random oracle model, in P. Rogaway, ed. CRYPTO. Lecture Notes in Computer Science, vol. 6841 (Springer, 2011), pp. 39–50.

23.

M. Mahmoody, R, Pass, The curious case of non-interactive commitments—on the power of black-box vs. non-black-box use of primitives, in R. Safavi-Naini, R. Canetti, eds. CRYPTO. Lecture Notes in Computer Science, vol. 7417 (Springer, 2012), pp. 701–718.

24.

R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)

25.

O. Reingold, L. Trevisan, S.P. Vadhan, Notions of reducibility between cryptographic primitives, in M. Naor, ed. TCC. Lecture Notes in Computer Science, vol. 2951 (Springer, 2004), pp. 1–20.

Titel: Merkle’s Key Agreement Protocol is Optimal: An Attack on Any Key Agreement from Random Oracles
verfasst von: Boaz Barak
Mohammad Mahmoody
Publikationsdatum: 19.08.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2017
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9233-9

Springer Professional

Abstract

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2017

Short Signatures from Diffie–Hellman: Realizing Almost Compact Public Key

Lattices with Symmetry

More Efficient Oblivious Transfer Extensions

Integral Cryptanalysis on Full MISTY1

Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

Differential-Linear Cryptanalysis Revisited