Introduction to the
Memory hard function (MHF) is a function that requires a large amount of Memory to complete. MHF is mainly used in proof of work. Because it takes a lot of memory, MHF is also used in password hashes to prevent malicious attacks.
MHF is also familiar with the MBF (memory-bound function), called the memory constraint function, which slows down the computation speed through memory delay, resulting in the computation cost.
Why need MHF
We know that the execution of an application requires two parts: CPU, which provides computing power, and memory, which provides storage power.
In the case of Bitcoin, mining for Bitcoin is actually a function of repeatedly calculating SHA-2, and when the result is small enough, mining succeeds. But for traditional CPUs, when the task is to calculate the same fixed function over and over again, the efficiency is very low. Miners developed application-specific integrated circuits (ASICs), or mining machines, to greatly improve this computing efficiency. From now on, mining is in the hands of the miners or the pools, because the average person can’t compete with them.
Because SHA-2 is only CPU-dependent, if the CPU is good enough, or if the algorithm is optimized using ASICs, you can gain an edge over everyone else.
The result is wasteful computing and a surge in electricity use. That’s actually not what we want. So a new algorithm is needed to change this situation.
Note that in addition to the CPU, the program also uses memory, which is a scarcer resource than the CPU. For example, if you need 1 gigabyte to compute a function, for the average person, an 8-core, 16-gigabyte computer can compute 16 functions at the same time. If you want to speed up the computation, you need to increase the memory space, and the speed increase is not too obvious, so if you use memory as the limitation of the computation, you can greatly reduce the malicious computation, which makes encryption and decryption relatively fair.
So, we need MHF.
Evaluation methods for Memory hard
So what does it mean to call Memory hard? We can measure it from three aspects. The first aspect is cumulative memory complexity, referred to as CMC. In the parallel model, the CMC measures the difficulty of memory by adding up all the inputs at each step.
Another approach is to use the product of time and memory. Another approach is to calculate the amount of memory bandwidth consumed on the memory bus. This type of function is also called bandwidth-hard functions (BHF).
The types of MHF
According to the evaluation method of MHF, MHF can be divided into two types, which are data dependent (DMHF) and data independent (IMHF).
Data-dependent (DMHF) refers to the fact that the later calculated data depends on the previous data, but it is uncertain which messages are required.
Data independent (IMHF) means that the data dependent on the subsequent calculation is determined.
Examples of DMHFS are Scrypt and Argon2D. Examples of IMHFS are Argon2i and Catena.
Because of the memory nature of MHF, it is very suitable for cryptographic hash functions.
Because DMHF is data-dependent, it has a stronger memory-hard feature than IMHF in cryptography. However, DMHF has a problem that it is vulnerable to side channel attacks such as cache timing. For this reason, people tend to use IMHFS as the cryptographic algorithm.
The Cryptographic Significance of MHF
We know that MHF is mainly used for password encryption, mainly in order to resist ASIC (application of integrated circuit) crack. We have mentioned three measures above, and here we use the product of time and memory.
Normally, we give the password P and salt S and use the Hash function H to generate the resulting Tag.
But for the crackers, they get the Tag and the S, hoping to get the P in a variety of reverse ways, as follows:
In the case of password hashing, we assume that the password creator allocates a certain amount of execution time (say 1 second) and a certain number of CPU cores (say 4) to each password. He then hashes the password with the maximum amount of memory, M.
So for the password cracker, who uses an ASIC to crack the code, let’s say that the memory area required is A, and the time T of running the ASIC is determined by the length of the longest computing chain and the ASIC memory latency. I want to maximize the product of AT’s. So as to achieve the meaning of anti-crack.
In general, the memory of the ASIC machine must be smaller than the ordinary memory M, assuming that A= AM, where A < 1. According to the time tradeoff principle, when memory is used less, the corresponding computation time will naturally be longer. Assuming that C(a) is needed, the corresponding computation time will be extended to D(a) times.
We can get the following maximization formula:
So if in this case, as a goes to 0, D of a times bB0, one over a. This means that as long as memory is used less, the product of memory and time will be larger than before. For such functions, we call them memory-hard functions.
Application of memory-hard in MHF
Consider the application of memory-hard in MHF. It is the essence of memory-hard to prepare some initial data in memory before calculating the password hash.
The initialization of the memory array B[I] can be summarized as the following steps:
The initial value:
For index j from 1 to t in memory array, we initialize it as follows:
Where G is the compression function,
According to the
Assuming that a kernel G occupies beta times the total memory, then the product of time and memory in this case is:
if
The above is the cryptographic significance of MHF.
This article has been included in http://www.flydean.com/memory-hard/
The most popular interpretation, the most profound dry goods, the most concise tutorial, many you do not know the tips to wait for you to discover!
Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!