Geekly Articles each Day

The discussion about the cryptographic strength of repeated use of a hash over a password (which slipped, by the way, in other forums), which has risen in this topic , pushed me to this somewhat mathematical topic. The essence of the problem arises from the idea of â€‹â€‹repeatedly (1,000 or more times) processing a password before storing with any crypto-resistant algorithm (most often a hash function) in order to get a

Reduction of resilience will be considered in two threat models:

- the attacker bans random input byte sets in the hope of finding a collision due to the narrowing of the value space (â€śfull brute forceâ€ť);
- bust through the dictionary.

Let's start with the first, more theoretical, question:

')

One of the main properties / requirements for crypto-resistant hash functions is a very good uniformity of distribution of output results. This makes it possible to operate in the estimates required by ordinary probability theory and combinatorics.

Let us take an input set of

The probability that a particular element of the output set will NOT be chosen by a specific display (arrow) is equal to accordingly, the probability that it will NOT be selected by any of the

Limit is a consequence of the second remarkable limit and is equal to i.e. approximately 0.3679. This is the probability that the element in the output set will "turn gray." At the same time, we note that for large

As soon as the input set begins to be filled out completely (that is, after the second iteration in the first threat model or immediately in the second threat model (with a dictionary attack)), other formulas and other patterns begin to work. This is clearly seen in the same figure for the case if there were only 3 â€śactiveâ€ť elements in the input set. The probability of â€ślosingâ€ť an element (narrowing the output set) decreases sharply, since now far less often two or more mappings are found on the same element.

Let only

Iteration number, i | The proportion of the set of values, k |
---|---|

one | 1.0000 |

2 | 0.6321 |

3 | 0.4685 |

four | 0.3740 |

five | 0.3120 |

6 | 0.2680 |

Of course, the share of active elements continues to decrease with each iteration, but not as quickly and catastrophically as at the very beginning.

In order to assess the degree of reduction of resistance for a large number of iterations, it is more convenient to study not the number

The points at which the graph intersects the integer values â€‹â€‹of

Reduced durability r (bit) | Number of iterations, i |
---|---|

four | thirty |

five | 61 |

6 | 125 |

7 | 253 |

eight | 509 |

9 | 1.020 |

ten | 2.044 |

eleven | 4.092 |

12 | 8.188 |

13 | 16.379 |

14 | 32.763 |

15 | 65.531 |

sixteen | 131.067 |

... | ... |

20 | 2.097.146 |

... | ... |

24 | 33.554.425 |

As you can see, the decrease in durability from a certain point increases very slowly. Moreover, the number of iterations exactly follows the powers of two: . In all cases when similar patterns are observed, they can be proved analytically, but I did not set it as my goal. Thus, without reducing the robustness of the algorithm to more than 16 bits (and in my firm conviction for 128-bit hash functions, this does not affect their practical strength for the next 25 years, for example), you can perform 130.000 password hash iterations. For 256-bit hash functions (SHA-256, GOST R 34.11, RIPEMD-256, etc.), obviously, this bar is still many times higher.

As always, after a large number of theoretical speculations, there is a desire to at least somehow assess how far the obtained theory is from practice. As a test hash function, I took the first 16 bits from MD5 (a crypto-resistant hash function allows you to select any set of result bits to form a truncated hash function with similar properties, although, of course, less persistence - according to its new bit depth). All possible values â€‹â€‹from 0 to 0xFFFF are input to the algorithm,

Planned decrease in durability, r (bit) | Number of iterations, i | The expected number of elements in the set | The observed number of elements in the set |
---|---|---|---|

four | thirty | 2 ^{16-4} = 4.096 | 3.819 |

6 | 125 | 2 ^{16-6} = 1.024 | 831 |

eight | 509 | 2 ^{16-8} = 256 | 244 |

Of course, with such a small value of

The time has

The described scheme of protection against brute force can be freely applied in practice with virtually no restrictions on the part of cryptographic security. The recommended upper limits for the number of iterations (the allowed decrease in the stability of

Hash function bit (bits) | Permitted decrease in durability, r (bit) | The upper limit of the allowed number of iterations, i |
---|---|---|

128 | sixteen | 130.000 |

160 | 20 | 2,000,000 |

192 | 24 | 32.000.000 |

224 | 28 | 500.000.000 |

256 | 32 | 8.000.000.000 |

Source: https://habr.com/ru/post/100301/