EnRUPT – The Simpler The Better

The recent EnRUPT-512 cryptanalysis by D. Khovratovich and I. Nikolic requires some clarification as it has provoked an old debate. To put it simply, the described attack would break a hash function that claimed security of more than 864 bits, but not EnRUPT-512 with its 512-bit preimage attack resistance.

First of all, I must remind everyone the two generic attacks that apply to all the ciphers and hash functions. The first one is most hated by the cryptanalysts since it naturally proves most of their attack efforts to be futile. It is the brute-force. Not the dumb serial brute-force on a single processor with no memory, but the actually-employed-to-break-ciphers-in-real-life parallel brute-force with a very large number of chips or processors.

It means that a cipher or a hash function that is expected to provide 512-bit security, can be broken by 2²⁵⁶ small circuits in 2²⁵⁶ time. Memory is a circuit. An attack requiring as much memory as those small circuits would occupy is a significant resource, therefore an attack for instance requiring 2³⁸⁴ memory and 2⁴⁸⁰ time does not break a 512-bit secure algorithm. 2³⁸⁴ small circuits would break it in 2¹²⁸ time simply by brute-force.

The second one is the generic time-memory-data trade-off (TMDTO) that also applies to all the ciphers and hash functions. It has very similar implications comparing to the parallel brute-force, but with certain restrictions on the possible time-memory trade-offs and on the amounts of required data. Since we are talking about hash functions today, with no restrictions on the available plaintext-ciphertext pairs, the implications of TMDTO are the same as parallel brute-force:

Any N-bit secure hash preimage can be found in time 2^T with memory 2^M where T+M=N. The 2^N precomputation required to perform TMDTO attacks can also be computed by M small circuits or processors in the same time 2^T, where T=N-M.

IMHO, someone has to extend TMDTO to parallel TMDTO with 2^K processors sharing that memory… That will send a lot more such ephemeral attacks beyond actually being able to break anything.

Second, I must point at a very important detail: EnRUPT is a highly parameterised algorithm. The specification of EnRUPT clearly recommends 4*N-bit states to provide N-bit security, specifically to comfort the most paranoid demanding total 2^2N time*memory attack complexity of an N-bit secure algorithm.

In other words, although we have proposed H=16 words for EnRUPT-512, H=12 words for EnRUPT-384 and H=8 words for EnRUPT-256 and EnRUPT-224, the [totally unnecessary] additional resistance to ephemeral attacks while maintaining the same high security margin can be obtained by simply doubling the internal state to 32 words for EnRUPT-512, 24 words for EnRUPT-384 and 16 words for EnRUPT-256 and EnRUPT-224, in which case we would also recommend the two times faster EnRUPTx4. The same state size restriction would apply to any hash function. But with such an unnecessarily large state, the 8-bit microchips are out of luck.