Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Depth-Robust Graphs and Their Cumulative Memory Complexity

verfasst von : Joël Alwen, Jeremiah Blocki, Krzysztof Pietrzak

Erschienen in: Advances in Cryptology – EUROCRYPT 2017

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) \(G_n\) on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of \(G_n\):
  • The parallel cumulative pebbling complexity \(\varPi ^{\parallel }_{cc}(G_n)\) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory).
  • The sequential space-time pebbling complexity \(\varPi _{st}(G_n)\) should be as close as possible to \(\varPi ^{\parallel }_{cc}(G_n)\) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage).
In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where \(\varPi ^{\parallel }_{cc}(G_n)=\varOmega (n^2/\log (n))\) (which matches a known upper bound) and \(\varPi _{st}(G_n)\) is within a constant factor of \(\varPi ^{\parallel }_{cc}(G_n)\).
Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high \(\varPi ^{\parallel }_{cc}\). Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high \(\varPi ^{\parallel }_{cc}\) in terms of DR.
Complementing these results, we provide new upper and lower bounds on the \(\varPi ^{\parallel }_{cc}\) of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i.
Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the \(\varPi ^{\parallel }_{cc}\) of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by \(O\left( n^{1.71} \right) \). We also show an upper bound of \(O(n^{1.625})\) for the Catena functions and the two remaining Balloon Hashing functions.

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
Nächstes Kapitel Scrypt Is Maximally Memory-Hard
Fußnoten
1
Note that \(\varPi ^{\parallel }_{cc}(G)\le \varPi _{{st}}(G)\) as parallelism can only help, and space-time complexity (i.e., number of rounds times the size of the largest state) is always higher than cumulative complexity (the sum of the sizes of all states).
 
2
The statement below is obtained from the result in [AB16] by treating the core-memory ratio as a constant and observing that, trivially, at most n pebbles are on G during a balloon phase and at most n pebbles are placed in one step during a balloon phase.
 
3
\(\varPi ^{\parallel }_{cc}\) satisfies a direct product property: pebbling k copies of G cost k times as much as pebbling G, i.e., \(\varPi ^{\parallel }_{cc}(G^k)=k\cdot \varPi ^{\parallel }_{cc}(G)\), but this is not true for \(\varPi _{{st}}\) complexity.
 
4
The Argon2 specification [BDK16] has undergone several revisions all of which are regularly referred to as “Argon2.” To avoid confusion we follow [AB17] and use Argon2i-A [BDK15] to denote the version of Argon2i from the password hashing competition [PHC] and we use Argon2i-B [BDKJ16] to refer the version of Argon2 that is currently being considered for standardization by the Cryptography Form Research Group (CFRG) of the IRTF. We conjecture that the techniques introduced in this paper could also be used to establish tighter bounds for Argon2i-B. However, we leave this as an open challenge for future work.
 
5
[ACK+16] introduces a combinatorial conjecture, which if true, means that lower bounds on \(\varPi ^{\parallel }_{cc}\) translate to cumulative memory complexity. At this point a strong variant of the conjecture has already been refuted, the state of the conjecture is updated in the eprint version [ACK+16] of the paper.
 
6
In particular, \((e,d,b \ge 1)\)-block depth robustness implies (e, d)-depth robustness. However, (e, d)-depth robustness only implies (e / b, d, b)-block depth robustness.
 
7
A superconcentrator is a DAG with m inputs and outputs such that any subset of \(s\in [m]\) inputs and outputs are connected by s node disjoint paths.
 
8
The odd case is identical but with messy but inconsequential rounding terms.
 
9
Formally, \(i \in P_i\) and \(S \cap [i] \subseteq P_i\) for each \(i \le n\).
 
10
Recall that \(g\ge d\) so \({\varLambda } _{c-1}\) lasts long enough to accommodate \(B_{c-1}\).
 
11
For example, in the final d steps of the execution one last balloon phase can be run to (re)pebble all of G including T at no added cost to the asymptotic complexity.
 
12
For example we can sort the nodes in topological order and divided them up into the partition. Whenever a set is larger than \(n/d_0\) we insert a new set into the partition with the overflow.
 
Literatur
[AB16]
Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53008-5_​9 CrossRef
[AB17]
Alwen, J., Blocki, J.: Towards practical attacks on Argon2i and balloon hashing. In: Proceedings of the 2nd IEEE European Symposium on Security and Privacy (EuroS&P 2017). IEEE (2017, to appear). http://​eprint.​iacr.​org/​2016/​759
[ABW03]
Abadi, M., Burrows, M., Wobber, T.: Moderately hard, memory-bound functions. In: Proceedings of the Network and Distributed System Security Symposium, NDSS, San Diego, California, USA (2003)
[ACK+16]
Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of RYPT and proofs of space in the parallel random oracle model. In: Advances in Cryptology - EUROCRYPT 2016 - Vienna, Austria, May 8–12, 2016, Part II, pp. 358–387 (2016). http://​eprint.​iacr.​org/​2016/​100
[ACP+17]
[AGK+16]
Alwen, J., Gai, P., Kamath, C., Klein, K., Osang, G., Pietrzak, K., Reyzin, L., Rolnek, M., Rybr. M.: On the memory-hardness of data-independent password-hashing functions. Cryptology ePrint Archive, Report 2016/783 (2016). http://​eprint.​iacr.​org/​2016/​783
[AS15]
[BCGS16]
Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: provably space-hard hash functions with data-independent access patterns. Cryptology ePrint Archive, Report 2016/027, Version: 20160601:225540 (2016). http://​eprint.​iacr.​org/​
[BDK15]
[BDK16]
[BDKJ16]
Biryukov, A., Dinu, D., Khovratovich, D., Josefsson, S.: The memory-hard Argon2 password hash and proof-of-work function. Internet-Draft draft-irtf-cfrg-argon2-00, Internet Engineering Task Force, March 2016
[BK15]
[Cha73]
Chandra, A.K.: Efficient compilation of linear recursive programs. In: SWAT (FOCS), pp. 16–25. IEEE Computer Society (1973)
[Coo73]
Cook, S.A.: An observation on time-storage trade off. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 29–33. ACM, New York (1973)
[DFKP15]
[DGN03]
[DKW11a]
Dziembowski, S., Kazana, T., Wichs, D.: Key-evolution schemes resilient to space-bounded leakage. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 335–353. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22792-9_​19 CrossRef
[DKW11b]
[DNW05]
[EGS75]
Paul, E., Graham, R.L., Szemeredi, E.: On sparse graphs with dense long paths. Technical report, Stanford, CA, USA (1975)
[FLW13]
Christian, F., Stefan, L., Jakob, W.: Catena: a memory-consuming password scrambler. IACR Cryptology ePrint Archive 2013, 525 (2013)
[HJO+16]
Hemenway, B., Jafargholi, Z., Ostrovsky, R., Scafuro, A., Wichs, D.: Adaptively secure garbled circuits from one-way functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 149–178. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53015-3_​6 CrossRef
[HP70]
Hewitt, C.E. Paterson, M.S.: Comparative Schematology. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119–127. ACM, New York (1970)
[JW16]
[Kal00]
Kaliski, B.: PKCS#5: password-based cryptography specification version 2.0 (2000)
[LT82]
Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4), 1087–1130 (1982)MathSciNetCrossRefMATH
[MMV13]
Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Kleinberg, R.D. (ed.) ITCS 2013, pp. 373–388. ACM, January 2013
[NBF+15]
Narayanan, A., Bonneau, J., Felten, E.W., Miller, A., Goldfeder, S.: Bitcoin and Cryptocurrency Technology (manuscript) (2015). Accessed 8 June 2015
[Per09]
Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)
[PHC]
[PR80]
Paul, W.J., Reischuk, R.: On alternation II. A graph theoretic approach to determinism versus nondeterminism. Acta Inf. 14, 391–403 (1980)MathSciNetMATH
[RD16]
[Sch82]
[Sch83]
Schnitger, G.: On depth-reduction and grates. In: 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7–9 November 1983, pp. 323–328. IEEE Computer Society (1983)
[SS78]
[SS79a]
Savage, J.E., Swamy, S.: Space-time tradeoffs for oblivious integer multiplication. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 498–504. Springer, Heidelberg (1979). doi:10.​1007/​3-540-09510-1_​40 CrossRef
[SS79b]
Swamy, S., Savage, J.E.: Space-time tradeoffs for linear recursion. In: Aho, A.V., Zilles, S.N., Rosen, B.K. (eds) POPL, pp. 135–142. ACM Press (1979)
[Tom78]
Tompa, M.: Time-space tradeoffs for computing functions, using connectivity properties of their circuits. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 196–204. ACM, New York (1978)
Metadaten
Titel
Depth-Robust Graphs and Their Cumulative Memory Complexity
verfasst von
Joël Alwen
Jeremiah Blocki
Krzysztof Pietrzak
Copyright-Jahr
2017
Buch
Advances in Cryptology – EUROCRYPT 2017

Print ISBN: 978-3-319-56616-0

Electronic ISBN: 978-3-319-56617-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-56617-7_1

Premium Partner

    Bildnachweise