2.6. Hash functions

For a very large number of security technologies (eg, authentication, EDS), one-way encryption functions are used, also called hash functions . The main purpose of such functions is to obtain from the message an arbitrary size of its digest — a fixed-size value. The digest can be used as the checksum of the original message, thus providing (using the appropriate protocol) integrity monitoring of the information. The main properties of the hash function:

1) a message of arbitrary length is fed to the input of the hash function;

2) at the output of the hash function, a block of data of a fixed length is formed;

3) the values ​​at the output of the hash function are distributed according to a uniform law;

4) when changing one bit at the input of the hash function, the output changes significantly.

In addition, to ensure the stability of the hash function to attacks, it must meet the following requirements:

1) if we know the value of the hash function h , then the task of finding a message M such that H ( M ) = h must be computationally difficult;

2) for a given message M, the task of finding another message M ^' , such that H ( M ) = H ( M ^' ), must be computationally difficult

If the hash function satisfies the listed properties, the value generated by it will uniquely identify the messages, and any attempt to modify the message during transmission will be detected by performing hashing on the receiving side and comparing with the digest received on the transmitting side.

Another feature of the hash functions is that they do not allow the inverse transform - it is impossible to receive the original message by its digest. Therefore, they are also called one-way encryption functions.

Hash functions are built on an iterative scheme, when the original message is divided into blocks of a certain size, and a number of transformations are performed on them using both reversible and irreversible operations. As a rule, the compressing function is included in the hash transformation, since its output is often smaller in size than the block fed to the input. The input of each hash cycle is the output of the previous cycle, as well as the next message block. Thus, on each cycle, the output of the hash function h _i is the hash of the first i blocks.

If you remember how random block ciphers randomize an input message, you can use a block cipher as a hash function. The fact that block ciphers are reversible transformations does not contradict the properties of the hash function, since the block cipher is irreversible by the encryption key, and if the output of the previous step of the hash transformation is used as the encryption key, and the next message block as the encrypted message ), you can get a hash function with good cryptographic characteristics. Such an approach was used, for example, in the Russian hashing standard - GOST R 34.11-94. This hash function forms a 256-bit output value, using the block cipher GOST 28147-89 as a transforming operation (Figure 2.17). H Hash Function receives the hash received at the previous step ( h ₀ arbitrary initial number), as well as the next message block m _i . Its internal structure is presented in ris.2.18. Here in an encryption transform block to modify h _i in s _i The block code number is GOST 28147-89. A mixing transform is a modified Feystel permutation. For the last block m _N ( N is the total number of message blocks), stuffing is performed up to the size of 256 bits with the addition of the true length of the message. In parallel, the checksum of message S is calculated. and the total length L , which are involved in the final compression function.

Fig.2.17. The general scheme of hashing according to GOST R 34.11 - 94

Fig.2.18. The structure of the hash function in GOST R 34.11-94

The main disadvantage of hash functions based on block ciphers is their low speed. Therefore, a number of specialized algorithms were designed, which, providing similar resistance to attacks, perform a much smaller number of operations on the input data and provide greater speed of work. Examples of such algorithms are: MD2, MD4, MD5, RIPEMD –160, SHA. Let us take a closer look at the structure of the SHA (Secure Hash Algorithm) hash algorithm, which is described in the SHS standard and ensures the security of a digital signature DSA, forming a 160-bit message digest.

First, the message is divided into blocks of 512 bits. If the message length is not a multiple of 512, the last block is assigned to the right 1, after which it is padded with zeros up to 512 bits. The message length code is written to the end of the last block. As a result, the message becomes n 512-bit blocks M ₁ , M ₂ , ..., M _n .

The SHA algorithm uses 80 logical functions f ₀ , f ₁ , ..., f ₇₉ , which perform operations on three 32-bit words ( B , C , D ):

The algorithm also uses 4 initialized constants K _i and 5 initial values H _{i in a} special way .

We divide the array M into groups of 16 words W ₀ , W ₁ , ..., W ₁₅ ( W ₀ the leftmost word).

For t = 16 - 79 W _t = S ¹ ( W _t-3 Å W _t-8 Å W _t-14 Å W _t-16 )

S ^k means the cyclic left shift operation by k bits.

Now let A = H ₀ , B = H ₁ , C = H ₂ , D = H ₃ , E = H ₄ .
for t = 0 to 79 do
TEMP = S ⁵ ( A ) + f _t ( B, C, D ) + E + W _t + K _i .
E = D; D = C; C = S ³⁰ ( B ); B = A; A = TEMP ;
Let H ₀ = H ₀ + A; H ₁ = H ₁ + B; H ₂ = H ₂ + C; H ₃ = H ₃ + D; H ₄ = H ₄ + E.

Graphically, one SHA cycle is presented in Figure 2.19.

Fig.2.19. One SHA conversion cycle

As a result of processing the array M, 5 words H ₀ , H ₁ , H ₂ , H ₃ , H ₄ with a total length of 160 bits will be received, which form the message digest.

From the above data it is clear that the complexity of the American standard hashing is lower than that of the Russian one. The Russian standard involves the implementation of four encryption in one production cycle hash, or a total of 128 rounds. Each round of encryption requires approximately one and a half dozen elementary machine operations, which significantly increases the cost of machine time to perform linear mixing operations. One round of SHA hash generation is much simpler: it can be implemented in about 15–20 teams, the total number of rounds is only 80, and for one hash production cycle, twice as much source data is processed - 512 versus 256 in GOST P34.ll -94. Thus, it can be assumed that the speed of SHA software implementations will be about 3-6 times faster than the national standard.

The main task of hash functions is the generation of digests that are unique to a particular document. If the hash function gives the same digest for two different input blocks, this is called a hash collision . From the theorem called the “paradox of birthdays”, it follows that for an n - bit hash value, an average of 2 ^{n / 2} different input messages is necessary for a collision to occur. This makes it almost impossible to change a document when it is signed using, for example, the SHA algorithm by simple selection, since with this approach it will be necessary to generate about 2 ⁸⁰ different messages in order to receive a similar substitute for the received digest. This figure is unattainable for the current level of technology.

2.7. Conclusion

Cryptography is the science of transforming information into a kind inaccessible to an outside observer. Cryptographic methods are divided into symmetric, requiring knowledge of the parties sharing some shared secret (key), and asymmetric, using a pair of keys to exchange information, one of which is public - accessible to all. A separate type of crypto-transformation is hashing, which allows you to create a unique digest identifying for each message. Cryptography methods are used to ensure confidentiality, data integrity, authentication, proof of ownership. Their practical application will be discussed in subsequent chapters.