Content deleted Content added
General copyediting, removed a duplicate citation, expanded opening paragraph, changed short description |
GreenC bot (talk | contribs) Move 1 url. Wayback Medic 2.5 per WP:URLREQ#www.vice.com |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 1:
{{short description|Type of cryptographic algorithm}}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
▲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 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.<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><ref name=":0" />
== 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
== Motivation and examples ==
Line 19 ⟶ 16:
== 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.<ref>{{Cite
A notable problem with 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>
| |||