Memory-hard function: Difference between revisions

Revision as of 09:41, 25 August 2023

Revision as of 02:58, 30 September 2023

Line 2:

{{Multiple issues|{{More citations needed|date=December 2019}}{{original research|date=December 2019}}{{tone|date=January 2021}}}}

In [[cryptography]], a '''memory-hard function''' (MHF) is a function that costs a significant amount of [[random-access memory|memory]] to efficiently evaluate.<ref name=":0">{{Cite thesis |title=Memory-Hard Functions: When Theory Meets Practice |url=https://escholarship.org/uc/item/7x4630qv |publisher=UC Santa Barbara |date=2019 |language=en |first=Binyi |last=Chen}}</ref> It differs from a [[memory-bound function]], which incurs cost by slowing down computation through memory latency.<ref>{{Cite journal |last=Dwork |first=Cynthia |last2=Goldberg |first2=Andrew |last3=Naor |first3=Moni |date=2003 |editor-last=Boneh |editor-first=Dan |title=On Memory-Bound Functions for Fighting Spam |url=https://link.springer.com/chapter/10.1007/978-3-540-45146-4_25 |journal=Advances in Cryptology - CRYPTO 2003 |series=Lecture Notes in Computer Science |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=426–444 |doi=10.1007/978-3-540-45146-4_25 |isbn=978-3-540-45146-4}}</ref> MHFs can be used as [[proof of work]].<ref name=":1">{{Cite web |last=LIU |first=ALEC |date=2013-11-29 |title=Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies |url=https://www.vice.com/en/article/4x3ywn/beyond-bitcoin-a-guide-to-the-most-promising-cryptocurrencies |access-date=2023-09-30 |website=Vice |language=en}}</ref>

== 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 circuit]]s and [[Graphics processing unit|graphics processing units]], which utilise parallelisation, in computing a MHF for a large number of inputs, such as when [[Brute-force attack|brute-forcing]] password hashes or [[Cryptocurrency|mining cryptocurrency]].<ref name=":0" /><ref name=":2">{{Cite journal |last=Biryukov |first=Alex |last2=Khovratovich |first2=Dmitry |date=2015 |editor-last=Iwata |editor-first=Tetsu |editor2-last=Cheon |editor2-first=Jung Hee |title=Tradeoff Cryptanalysis of Memory-Hard Functions |url=https://link.springer.com/chapter/10.1007/978-3-662-48800-3_26 |journal=Advances in Cryptology – ASIACRYPT 2015 |series=Lecture Notes in Computer Science |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=633–657 |doi=10.1007/978-3-662-48800-3_26 |isbn=978-3-662-48800-3}}</ref>

== Memory hard measure ==

Line 9 ⟶ 12:

Other viable measures include integrating memory against physical time and measuring memory [[bandwidth (computing)|bandwidth]] consumption on a memory bus.<ref>(BR18) Blocki, Ren, [https://eprint.iacr.org/2018/221.pdf ''Bandwidth-Hard Functions: Reductions and Lower Bounds''], 2018</ref> Functions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions".<ref>{{Cite web |last1=Blocki |first1=Jeremiah |last2=Liu |first2=Peiyuan |last3=Ren |first3=Ling |last4=Zhou |first4=Samson |date=2022 |title=Bandwidth-Hard Functions: Reductions and Lower Bounds |url=https://eprint.iacr.org/2018/221.pdf |url-status=live |archive-url=https://web.archive.org/web/20230112040047/https://eprint.iacr.org/2018/221.pdf |archive-date=2023-01-12 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>

== Motivation and Examples ==

MHFs are designed to consume large amounts of memory instead of another resource on a computer. [[Bitcoin]]'s proof-of-work useduses repeated evaluation of the [[SHA-2]] function, but modern general-purpose processors, such as off-the-shelf [[central processing unit|CPUs]], are inefficient when computing a fixed function many times over. Specialized hardware, such as [[application-specific integrated circuit]]scircuits (ASICs) designed for Bitcoin mining, can computeuse these30,000 hashestimes upless toenergy 100,000per timeshash fasterthan x86 CPUs.<ref name=":2" /> This led to concerns about the centralization of mining for Bitcoin and other cryptocurrencies. Because of this inequality between miners using ASICs and miners using CPUs or off-the shelf hardware, designers of later proof-of-work systems wanted to designutilised hash functions for which it was difficult to construct ASICs that could evaluate the hash function significantly faster than a CPU.<ref name=":1" />

OverAs time,memory itcost hasis beenplatform-independent,<ref demonstratedname=":0" that/> memoryMHFs costshave remainsfound relativelyuse constantin betweencryptocurrency CPUsmining, andsuch moreas specializedfor hardware[[Litecoin]], which isuses why[[scrypt]] MHFsas haveits foundhash usefunction.<ref inname=":1" cryptocurrency mining./> 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.<ref name=":0" />

== 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 specificmemory dataaccess required for later stepspattern of a dMHF dependdepends on the resultsfunction ofinput, previoussuch stepsas the password provided to a key derivation function.<ref>{{Cite journal |last=Blocki |first=Jeremiah |last2=Harsha |first2=Ben |last3=Kang |first3=Siteng |last4=Lee |first4=Seunghoon |last5=Xing |first5=Lu |last6=Zhou |first6=Samson |date=2019 |editor-last=Boldyreva |editor-first=Alexandra |editor2-last=Micciancio |editor2-first=Daniele |title=Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions |url=https://link.springer.com/chapter/10.1007/978-3-030-26951-7_20 |journal=Advances in Cryptology – CRYPTO 2019 |series=Lecture Notes in Computer Science |language=en |___location=Cham |publisher=Springer International Publishing |pages=573–607 |doi=10.1007/978-3-030-26951-7_20 |isbn=978-3-030-26951-7}}</ref> Examples of dMHFs are [[scrypt]] and [[Argon2]]d, while examples of iMHFs are [[Argon2]]i and [[catena (cryptography)|catena]]. Many of these MHFs have been designed to be used as [[key derivation function|password hashing function]]s because of their memory hardness.

A notable problem ofwith dMHFs is that they are prone to [[side-channel attack]]s 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.<ref>Alwen, J., Blocki, J. (2016). [https://doi.org/10.1007/978-3-662-53008-5_9''Efficiently Computing Data-Independent Memory-Hard Functions.'']</ref>

==References==