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,It’s the index function.

According to theWe can divide MHF into two types, one is data independent type, that is to sayThe value of is not dependent on the input password P and salt S, then the entire memory array B value can be constructed before the password and salt are obtained, and can be calculated at the same time with the help of parallel computing function.

Assuming that a kernel G occupies beta times the total memory, then the product of time and memory in this case is:

ifThe value of depends on the input password P and salt S, so I call this situation data independent. In this case, parallel calculation cannot be carried out. If the final number of calculations is a tree with an average depth of D, then the product of time and memory in this case can be expressed as:

The above is the cryptographic significance of MHF.

This article has been included in

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!