Memory-hard function

Last updated

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]

Contents

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]

Related Research Articles

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.

In cryptanalysis and computer security, password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system in scrambled form. A common approach is to repeatedly try guesses for the password and to check them against an available cryptographic hash of the password. Another type of approach is password spraying, which is often automated and occurs slowly over time in order to remain undetected, using a list of common passwords.

Hashcash is a proof-of-work system used to limit E-mail spam and denial-of-service attacks. Hashcash was proposed in 1997 by Adam Back and described more formally in Back's 2002 paper "Hashcash - A Denial of Service Counter-Measure".

Proof of work (PoW) is a form of cryptographic proof in which one party proves to others that a certain amount of a specific computational effort has been expended. Verifiers can subsequently confirm this expenditure with minimal effort on their part. The concept was invented by Moni Naor and Cynthia Dwork in 1993 as a way to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from a service requester, usually meaning processing time by a computer. The term "proof of work" was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels.

In cryptography, PBKDF1 and PBKDF2 are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

<span class="mw-page-title-main">Hardware acceleration</span> Specialized computer hardware

Hardware acceleration is the use of computer hardware designed to perform specific functions more efficiently when compared to software running on a general-purpose central processing unit (CPU). Any transformation of data that can be calculated in software running on a generic CPU can also be calculated in custom-made hardware, or in some mix of both.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.

In cryptography, scrypt is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.

Litecoin is a decentralized peer-to-peer cryptocurrency and open-source software project released under the MIT/X11 license. Inspired by Bitcoin, Litecoin was among the earliest altcoins, starting in October 2011. In technical details, the Litecoin main chain shares a slightly modified Bitcoin codebase. The practical effects of those codebase differences are lower transaction fees, faster transaction confirmations, and faster mining difficulty retargeting. Due to its underlying similarities to Bitcoin, Litecoin has historically been referred to as the "silver to Bitcoin's gold." In 2022, Litecoin added optional privacy features via soft fork through the MWEB upgrade.

Zerocoin is a privacy protocol proposed in 2013 by Johns Hopkins University professor Matthew D. Green and his graduate students, Ian Miers and Christina Garman. It was designed as an extension to the Bitcoin protocol that would improve Bitcoin transactions' anonymity by having coin-mixing capabilities natively built into the protocol. Zerocoin is not currently compatible with Bitcoin.

Argon2 is a key derivation function that was selected as the winner of the 2015 Password Hashing Competition. It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from the University of Luxembourg. The reference implementation of Argon2 is released under a Creative Commons CC0 license or the Apache License 2.0, and provides three related versions:

Lyra2 is a password hashing scheme (PHS) that can also work as a key derivation function (KDF). It received a special recognition during the Password Hashing Competition in July 2015, which was won by Argon2. Besides being used for its original purposes, it is also in the core of proof-of-work algorithms such as Lyra2REv2, adopted by Vertcoin, MonaCoin, among other cryptocurrencies Lyra2 was designed by Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo C. F. dos Santos, and Paulo S. L. M. Barreto from Escola Politécnica da Universidade de São Paulo. It is an improvement over Lyra, previously proposed by the same authors. Lyra2 preserves the security, efficiency and flexibility of its predecessor, including: (1) the ability to configure the desired amount of memory, processing time and parallelism to be used by the algorithm; and (2) the capacity of providing a high memory usage with a processing time similar to that obtained with scrypt. In addition, it brings the following improvements when compared to its predecessor:

Proof of space (PoS) is a type of consensus algorithm achieved by demonstrating one's legitimate interest in a service by allocating a non-trivial amount of memory or disk space to solve a challenge presented by the service provider. The concept was formulated in 2013 by Dziembowski et al. and by Ateniese et al.. Proofs of space are very similar to proofs of work (PoW), except that instead of computation, storage is used to earn cryptocurrency. Proof-of-space is different from memory-hard functions in that the bottleneck is not in the number of memory access events, but in the amount of memory required.

Equihash is a memory-hard Proof-of-work algorithm introduced by the University of Luxembourg's Interdisciplinary Centre for Security, Reliability and Trust (SnT) at the 2016 Network and Distributed System Security Symposium. The algorithm is based on a generalization of the Birthday problem which finds colliding hash values. It has severe time-space trade-offs but concedes vulnerability to unforeseen parallel optimizations. It was designed such that parallel implementations are bottle-necked by memory bandwidth in an attempt to worsen the cost-performance trade-offs of designing custom ASIC implementations. ASIC resistance in Equihash is based on the assumption that commercially-sold hardware already has quite high memory bandwidth, so improvements made by custom hardware may not be worth the development cost.

Balloon hashing is a key derivation function presenting proven memory-hard password-hashing and modern design. It was created by Dan Boneh, Henry Corrigan-Gibbs and Stuart Schechter in 2016. It is a recommended function in NIST password guidelines.

Cryptojacking is the act of exploiting a computer to mine cryptocurrencies, often through websites, against the user's will or while the user is unaware. One notable piece of software used for cryptojacking was Coinhive, which was used in over two-thirds of cryptojacks before its March 2019 shutdown. The cryptocurrencies mined the most often are privacy coins—coins with hidden transaction histories—such as Monero and Zcash.

References

  1. 1 2 3 4 5 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. 1 2 3 LIU, ALEC (2013-11-29). "Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies". Vice. Retrieved 2023-09-30.
  4. 1 2 3 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 . Archived (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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.