Computationally Data-Independent Memory Hard Functions

Authors Mohammad Hassan Ameri , Jeremiah Blocki , Samson Zhou



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.36.pdf
  • Filesize: 0.65 MB
  • 28 pages

Document Identifiers

Author Details

Mohammad Hassan Ameri
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Jeremiah Blocki
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Samson Zhou
  • School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA

Acknowledgements

Part of this work was done while Samson Zhou was a postdoctoral fellow at Indiana University. We would like to thank anonymous ITCS 2020 reviewers for thoughtful comments which helped us to improve the paper.

Cite AsGet BibTex

Mohammad Hassan Ameri, Jeremiah Blocki, and Samson Zhou. Computationally Data-Independent Memory Hard Functions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 36:1-36:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.36

Abstract

Memory hard functions (MHFs) are an important cryptographic primitive that are used to design egalitarian proofs of work and in the construction of moderately expensive key-derivation functions resistant to brute-force attacks. Broadly speaking, MHFs can be divided into two categories: data-dependent memory hard functions (dMHFs) and data-independent memory hard functions (iMHFs). iMHFs are resistant to certain side-channel attacks as the memory access pattern induced by the honest evaluation algorithm is independent of the potentially sensitive input e.g., password. While dMHFs are potentially vulnerable to side-channel attacks (the induced memory access pattern might leak useful information to a brute-force attacker), they can achieve higher cumulative memory complexity (CMC) in comparison than an iMHF. In particular, any iMHF that can be evaluated in N steps on a sequential machine has CMC at most ?((N^2 log log N)/log N). By contrast, the dMHF scrypt achieves maximal CMC Ω(N^2) - though the CMC of scrypt would be reduced to just ?(N) after a side-channel attack. In this paper, we introduce the notion of computationally data-independent memory hard functions (ciMHFs). Intuitively, we require that memory access pattern induced by the (randomized) ciMHF evaluation algorithm appears to be independent from the standpoint of a computationally bounded eavesdropping attacker - even if the attacker selects the initial input. We then ask whether it is possible to circumvent known upper bound for iMHFs and build a ciMHF with CMC Ω(N^2). Surprisingly, we answer the question in the affirmative when the ciMHF evaluation algorithm is executed on a two-tiered memory architecture (RAM/Cache). We introduce the notion of a k-restricted dynamic graph to quantify the continuum between unrestricted dMHFs (k=n) and iMHFs (k=1). For any ε > 0 we show how to construct a k-restricted dynamic graph with k=Ω(N^(1-ε)) that provably achieves maximum cumulative pebbling cost Ω(N^2). We can use k-restricted dynamic graphs to build a ciMHF provided that cache is large enough to hold k hash outputs and the dynamic graph satisfies a certain property that we call "amenable to shuffling". In particular, we prove that the induced memory access pattern is indistinguishable to a polynomial time attacker who can monitor the locations of read/write requests to RAM, but not cache. We also show that when k=o(N^(1/log log N)) , then any k-restricted graph with constant indegree has cumulative pebbling cost o(N^2). Our results almost completely characterize the spectrum of k-restricted dynamic graphs.

Subject Classification

ACM Subject Classification
  • Security and privacy → Hash functions and message authentication codes
Keywords
  • Computationally Data-Independent Memory Hard Function
  • Cumulative Memory Complexity
  • Dynamic Pebbling Game

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Martín Abadi, Michael Burrows, Mark S. Manasse, and Ted Wobber. Moderately hard, memory-bound functions. ACM Trans. Internet Techn., 5(2):299-327, 2005. Google Scholar
  2. Joël Alwen and Jeremiah Blocki. Efficiently Computing Data-Independent Memory-Hard Functions. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Proceedings, Part II, pages 241-271, 2016. Google Scholar
  3. Joël Alwen and Jeremiah Blocki. Towards Practical Attacks on Argon2i and Balloon Hashing. In 2017 IEEE European Symposium on Security and Privacy, EuroS&P, pages 142-157, 2017. Google Scholar
  4. Joël Alwen, Jeremiah Blocki, and Benjamin Harsha. Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 1001-1017, 2017. Google Scholar
  5. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Depth-Robust Graphs and Their Cumulative Memory Complexity. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III, pages 3-32, 2017. Google Scholar
  6. Joël Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin, and Stefano Tessaro. Scrypt Is Maximally Memory-Hard. In Advances in Cryptology - EUROCRYPT - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III, pages 33-62, 2017. Google Scholar
  7. Joël Alwen and Vladimir Serbinenko. High Parallel Complexity Graphs and Memory-Hard Functions. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, 2015. Google Scholar
  8. Daniel J Bernstein. Cache-timing attacks on AES, 2005. Google Scholar
  9. Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich. Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing. IACR Cryptology ePrint Archive, 2015:430, 2015. Google Scholar
  10. Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich. Argon2: New Generation of Memory-Hard Functions for Password Hashing and Other Applications. In IEEE European Symposium on Security and Privacy, EuroS&P, pages 292-302, 2016. Google Scholar
  11. Jeremiah Blocki, Benjamin Harsha, Siteng Kang, Seunghoon Lee, Lu Xing, and Samson Zhou. Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings, Part II, pages 573-607, 2019. Google Scholar
  12. Jeremiah Blocki, Benjamin Harsha, and Samson Zhou. On the Economics of Offline Password Cracking. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, pages 853-871, 2018. Google Scholar
  13. Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. Approximating Cumulative Pebbling Cost is Unique Games Hard. CoRR, abs/1904.08078, 2019. URL: http://arxiv.org/abs/1904.08078.
  14. Jeremiah Blocki, Ling Ren, and Samson Zhou. Bandwidth-Hard Functions: Reductions and Lower Bounds. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS, pages 1820-1836, 2018. Google Scholar
  15. Jeremiah Blocki and Samson Zhou. On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i. In Theory of Cryptography - 15th International Conference, TCC, Proceedings, Part I, pages 445-465, 2017. Google Scholar
  16. Jeremiah Blocki and Samson Zhou. On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling. In Financial Cryptography and Data Security - 22nd International Conference, FC, Revised Selected Papers, pages 329-346, 2018. Google Scholar
  17. Dan Boneh, Henry Corrigan-Gibbs, and Stuart E. Schechter. Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. In Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I, pages 220-248, 2016. Google Scholar
  18. Joseph Bonneau. The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords. In 2012 IEEE Symposium on Security and Privacy, pages 538-552, San Francisco, CA, USA, May 21-23 2012. IEEE Computer Society Press. URL: https://doi.org/10.1109/SP.2012.49.
  19. Xavier Boyen. Halting Password Puzzles: Hard-to-break Encryption from Human-memorable Keys. In Proceedings of the 16th USENIX Security Symposium, 2007. Google Scholar
  20. Elette Boyle and Moni Naor. Is There an Oblivious RAM Lower Bound? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 357-368, 2016. Google Scholar
  21. Cynthia Dwork and Moni Naor. Pricing via Processing or Combatting Junk Mail. In Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Proceedings, pages 139-147, 1992. Google Scholar
  22. Christian Forler, Stefan Lucks, and Jakob Wenzel. Memory-Demanding Password Scrambling. In Advances in Cryptology - ASIACRYPT - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part II, pages 289-305, 2014. Google Scholar
  23. Oded Goldreich and Rafail Ostrovsky. Software Protection and Simulation on Oblivious RAMs. J. ACM, 43(3):431-473, 1996. Google Scholar
  24. Marcos A. Simplício Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo C. F. dos Santos, and Paulo S. L. M. Barreto. Lyra2: Password Hashing Scheme with improved security against time-memory trade-offs. IACR Cryptology ePrint Archive, page 136, 2015. Google Scholar
  25. Kasper Green Larsen and Jesper Buus Nielsen. Yes, There is an Oblivious RAM Lower Bound! In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Proceedings, Part II, pages 523-542, 2018. Google Scholar
  26. Thomas Lengauer and Robert Endre Tarjan. Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM, 29(4):1087-1130, 1982. Google Scholar
  27. Colin Percival. Stronger key derivation via sequential memory-hard functions, 2009. Google Scholar
  28. Nicholas Pippenger. Superconcentrators. SIAM J. Comput., 6(2):298-304, 1977. Google Scholar
  29. Ling Ren and Srinivas Devadas. Bandwidth Hard Functions for ASIC Resistance. In Theory of Cryptography - 15th International Conference, TCC 2017, Proceedings, Part I, pages 466-492, 2017. Google Scholar
  30. Georg Schnitger. On Depth-Reduction and Grates. In 24th Annual Symposium on Foundations of Computer Science (FOCS), pages 323-328, 1983. Google Scholar
  31. Emil Stefanov, Marten van Dijk, Elaine Shi, T.-H. Hubert Chan, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: An Extremely Simple Oblivious RAM Protocol. J. ACM, 65(4):18:1-18:26, 2018. Google Scholar
  32. Leslie G. Valiant. Graph-Theoretic Arguments in Low-Level Complexity. In Mathematical Foundations of Computer Science 1977, 6th Symposium, Proceedings, pages 162-176, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail