nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Memory-Hard Functions from Cryptographic Primitives

verfasst von : Binyi Chen, Stefano Tessaro

Erschienen in: Advances in Cryptology – CRYPTO 2019

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Memory-hard functions (MHFs) are moderately-hard functions which enforce evaluation costs both in terms of time and memory (often, in form of a trade-off). They are used e.g. for password protection, password-based key-derivation, and within cryptocurrencies, and have received a considerable amount of theoretical scrutiny over the last few years. However, analyses see MHFs as modes of operation of some underlying hash function \(\mathcal {H}\), modeled as a monolithic random oracle. This is however a very strong assumption, as such hash functions are built from much simpler primitives, following somewhat ad-hoc design paradigms.

This paper initiates the study of how to securely instantiate \(\mathcal {H}\) within MHF designs using common cryptographic primitives like block ciphers, compression functions, and permutations. Security here will be in a model in which the adversary has parallel access to an idealized version of the underlying primitive. We will provide provably memory-hard constructions from all the aforementioned primitives. Our results are generic, in that we will rely on hard-to-pebble graphs designed in prior works to obtain our constructions.

One particular challenge we encounter is that \(\mathcal {H}\) is usually required to have large outputs (to increase memory hardness without changing the description size of MHFs), whereas the underlying primitives generally have small output sizes.

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

Vorheriges Kapitel Stronger Leakage-Resilient and Non-Malleable Secret Sharing Schemes for General Access Structures

Nächstes Kapitel Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions

Nur mit Berechtigung zugänglich

We will use the more fine-grained metric of cumulative memory complexity (CMC), but for now the product of time and memory will suffice for an informal understanding.

Actually for certain graphs, we prove that the efficiency gap can be reduced to the optimal bound O(1), by giving a more memory-efficient sequential algorithm.

Our first result in fact only requires a lower bound on \({\mathsf {cc}} ({\mathbb {G}})\). It is an interesting open question to provide a wide-block labeling function which only relies on a lower bound for \({\mathsf {cc}} ({\mathbb {G}})\), rather than the (stronger) depth-robustness requirement.

We assume the compression function allows both \({L} \)- and \(2{L} \)-bit inputs, though most compression functions do not allow this by design. This could however be easily achieved by reserving one bit of the input to implement domain separation, and then padding short inputs.

\({{\mathsf {Tm}}} ({{\mathsf {A}}})\) (and \({{\mathsf {Spc}}} ({{\mathsf {A}}})\)) measure worst-case sequential efficiency by providing upper bounds on time/memory.

Recall that the total number of output labels/ideal primitive queries that the algorithm makes is at most \({{\mathsf {q}}} \).

\({\mathsf {pred}} (v) = \emptyset \) for \(v\in {\mathsf {src}} ({\mathbb {G}})\).

First-predecessor-distinctness holds as each non-source node v can pick her previous node in the subpath (that traverses all of the vertices) as their first predecessor; predecessors-distinctness holds as otherwise a cycle would exist.

See Remark 3 for definition of predecessors-distinct graphs.

\({\mathbb {G}} \) can have multiple source/sink nodes.

\({{\mathbb {CF}}} \) denotes the compression function, \({{\mathbb {IC}}} \) denotes the ideal cipher, and \({{\mathbb {RP}}} \) denotes the random permutation.

We assume an implicit order for the calls in the same round.

Note that the existence of a correct call for v in round \({i} \) does not imply \(v \in {\mathsf {P}} _{{i}}\), because v may not have a critical call in the future.

If \({{\mathbb {IP}}} ={{\mathbb {IC}}}/{{\mathbb {RP}}} \), this also implies that \(\{{\mathsf {aftlab}} (v)\}_{v\in {\mathbb {V}}}\) are distinct.

By non-colliding, we mean \({\mathbf {x}} = ({x} _{1},\dots ,{x} _{{n_{s}}})\) where \({x} _{i}\ne {x} _{j}\) for every \(i\ne j\).

Note that we don’t need an indicator (e.g., \({h} _{j} = \bot \)) to tell if \({h} _{j}\) is empty or not, as we can know it from the sequence \(Q_{{i}}\). This enables us to have a shorter \(H_{{i}}\).

We assume that the encoding of the hint is unambiguous.

Recall that there is an implicit chronological order for the calls.

\({v} _{ |{\mathsf {P}} _{{i}}|}\) is picked first, then \({v} _{|{\mathsf {P}} _{{i}}|-1}\),..., and finally \({v} _{1}\).

Recall that in \({{{\mathsf {A}}} ({\sigma } _{{i}})} \), there was no correct call for v before the round of the first critical call for v.

\({\mathbb {G}} \) has a single source/sink vertex.

The last \({K}-1\) edges make sure that the \({K} \) nodes at column 1 have distinct sets of predecessors (Sect. 2.3).

We assume an implicit order for nodes in \({\mathbb {G}} _{1}\) and \({\mathbb {G}} _{2}\).

See Remark 3 for definition of first-predecessor-distinctness.

Note that \({\beta } _{{\mathsf {fix}}}\)-pebbling reducibility holds for multi-sources graphs.

A \({d} \)-path is a path with \({d} \) vertices.

Note that \({\mathsf {copy}} (v_1) -{S_{\mathsf {ext}}} \) is non-empty because \( |{\mathsf {copy}} (v_1) \cap {S_{\mathsf {ext}}} | \le |{\mathsf {nodes}} (v_1) \cap {S_{\mathsf {ext}}} |< \frac{{K}}{4}< {K} = |{\mathsf {copy}} (v_1)|\,. \) The first inequality holds as \({\mathsf {copy}} (v_1) \subseteq {\mathsf {nodes}} (v_1)\), the second inequality holds because \(v_1 \notin S\).

See Remark 3 for definition of first-predecessor-distinctness.

\({\mathbb {G}} \) has single source/sink.

A random permutation can be viewed as an ideal cipher with a fixed key.

Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_9CrossRef

Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.), ACM CCS 17, pp. 1001–1017. ACM Press, October/November 2017

Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_1CrossRef

Alwen, J., Blocki, J., Pietrzak, K.: Sustained space complexity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 99–130. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_4CrossRef

Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 358–387. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_13CrossRefMATH

Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: Scrypt is maximally memory-hard. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 33–62. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_2CrossRef

Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Servedio, R.A. Rubinfeld, R. (eds.), 47th ACM STOC, pp. 595–603. ACM Press, June 2015

Alwen, J., Tackmann, B.: Moderately hard functions: definition, instantiations, and applications. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 493–526. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_17CrossRef

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.), ACM CCS 93, pp. 62–73. ACM Press, November 1993

10.

Biryukov, A., Dinu, D., Khovratovich, D.: Argon2 password hash. Version 1.3 (2016). https://www.cryptolux.org/images/0/0d/Argon2.pdf

11.

Blocki, J., Harsha, B., Kang, S., Lee, S., Xing, L., Zhou, S.: Data-independent memory hard functions: new attacks and stronger constructions. Cryptology ePrint Archive, Report 2018/944 (2018). http://eprint.iacr.org/2018/944

12.

Blocki, J., Zhou, S.: On the depth-robustness and cumulative pebbling cost of Argon2i. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 445–465. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_15CrossRefMATH

13.

Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: a memory-hard function providing provable protection against sequential attacks. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 220–248. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_8CrossRef

14.

Dryja, T., Liu, Q.C., Park, S.: Static-memory-hard functions, and modeling the cost of space vs. time. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part I. LNCS, vol. 11239, pp. 33–66. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_2CrossRefMATH

15.

Dwork, C., Naor, M., Wee, H.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37–54. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_3CrossRef

16.

Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125–143. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_9CrossRef

17.

Forler, C., Lucks, S., Wenzel, J.: Catena: a memory-consuming password scrambler. IACR Cryptology ePrint Archive 2013/525 (2013)

18.

Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_2CrossRef

19.

Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)

20.

Percival, C., Josefsson, S.: The scrypt password-based key derivation function (2012)

21.

Ren, L., Devadas, S.: Bandwidth hard functions for ASIC resistance. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 466–492. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_16CrossRef

22.

Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_27CrossRef

Titel: Memory-Hard Functions from Cryptographic Primitives
verfasst von: Binyi Chen
Stefano Tessaro
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2019
Print ISBN: 978-3-030-26950-0

Electronic ISBN: 978-3-030-26951-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-26951-7_19

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"

Premium Partner