Memory-hard function

In cryptography, a memory-hard function (MHF) is a function that costs a significant amount of memory to efficiently evaluate.^[1] It differs from a memory-bound function, which incurs cost by slowing down computation through memory latency.^[2] MHFs have found use in key stretching and proof of work as their increased memory requirements significantly reduce the computational efficiency advantage of custom hardware over general-purpose hardware compared to non-MHFs.^[3][1]

Introduction

MHFs are designed to consume large amounts of memory on a computer in order to reduce the effectiveness of parallel computing. In order to evaluate the function using less memory, a significant time penalty is incurred. As each MHF computation requires a large amount of memory, the number of function computations that can occur simultaneously is limited by the amount of available memory. This reduces the efficiency of specialised hardware, such as application-specific integrated circuits and graphics processing units, which utilise parallelisation, in computing a MHF for a large number of inputs, such as when brute-forcing password hashes or mining cryptocurrency.^[1][4]

Motivation and examples

Bitcoin's proof-of-work uses repeated evaluation of the SHA-256 function, but modern general-purpose processors, such as off-the-shelf CPUs, are inefficient when computing a fixed function many times over. Specialized hardware, such as application-specific integrated circuits (ASICs) designed for Bitcoin mining, can use 30,000 times less energy per hash than x86 CPUs whilst having much greater hash rates.^[4] This led to concerns about the centralization of mining for Bitcoin and other cryptocurrencies.^[4] Because of this inequality between miners using ASICs and miners using CPUs or off-the shelf hardware, designers of later proof-of-work systems utilised hash functions for which it was difficult to construct ASICs that could evaluate the hash function significantly faster than a CPU.^[3]

As memory cost is platform-independent,^[1] MHFs have found use in cryptocurrency mining, such as for Litecoin, which uses scrypt as its hash function.^[3] They are also useful in password hashing because they significantly increase the cost of trying many possible passwords against a leaked database of hashed passwords without significantly increasing the computation time for legitimate users.^[1]

Measuring memory hardness

There are various ways to measure the memory hardness of a function. One commonly seen measure is cumulative memory complexity (CMC). In a parallel model, CMC is the sum of the memory required to compute a function over every time step of the computation.^[5][6]

Other viable measures include integrating memory usage against time and measuring memory bandwidth consumption on a memory bus. Functions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions".^[7]

Variants

MHFs can be categorized into two different groups based on their evaluation patterns: data-dependent memory-hard functions (dMHF) and data-independent memory-hard functions (iMHF). As opposed to iMHFs, the memory access pattern of a dMHF depends on the function input, such as the password provided to a key derivation function.^[8] Examples of dMHFs are scrypt and Argon2d, while examples of iMHFs are Argon2i and catena. Many of these MHFs have been designed to be used as password hashing functions because of their memory hardness.

A notable problem with dMHFs is that they are prone to side-channel attacks such as cache timing. This has resulted in a preference for using iMHFs when hashing passwords. However, iMHFs have been mathematically proven to have weaker memory hardness properties than dMHFs.^[9]

References

1. Chen, Binyi (2019). Memory-Hard Functions: When Theory Meets Practice (Thesis). UC Santa Barbara.
2. Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). Boneh, Dan (ed.). "On Memory-Bound Functions for Fighting Spam". Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 426–444. doi:10.1007/978-3-540-45146-4_25. ISBN 978-3-540-45146-4.
3. LIU, ALEC (2013-11-29). "Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies". Vice. Retrieved 2023-09-30.
4. Biryukov, Alex; Khovratovich, Dmitry (2015). Iwata, Tetsu; Cheon, Jung Hee (eds.). "Tradeoff Cryptanalysis of Memory-Hard Functions". Advances in Cryptology – ASIACRYPT 2015. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 633–657. doi:10.1007/978-3-662-48800-3_26. ISBN 978-3-662-48800-3.
5. (AS15) Alwen, Serbineko, High Parallel Complexity Graphs and Memory-Hard Functions, 2015
6. Alwen, Joel; Blocki, Jeremiah; Pietrzak, Krzysztof (2017-07-07). "Sustained Space Complexity". arXiv:1705.05313 [cs.CR].
7. Blocki, Jeremiah; Liu, Peiyuan; Ren, Ling; Zhou, Samson (2022). "Bandwidth-Hard Functions: Reductions and Lower Bounds" (PDF). Cryptology ePrint Archive. (PDF) from the original on 2023-01-12. Retrieved 2023-01-11.
8. Blocki, Jeremiah; Harsha, Ben; Kang, Siteng; Lee, Seunghoon; Xing, Lu; Zhou, Samson (2019). Boldyreva, Alexandra; Micciancio, Daniele (eds.). "Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions". Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. Cham: Springer International Publishing: 573–607. doi:10.1007/978-3-030-26951-7_20. ISBN 978-3-030-26951-7.
9. Alwen, J., Blocki, J. (2016). Efficiently Computing Data-Independent Memory-Hard Functions.