EnRUPT – The Simpler The Better

EnRUPT has been presented at the First SHA-3 Candidate Conference. The good news for EnRUPT is that NIST has allowed tuning the tunable parameters in the first round. The recent collision attack against ïrRUPTx2 is only effective for s = 1 to 4. EnRUPTx2/5 and higher are not affected by this attack. Although differential trails such as:

0000009000000000 - 2102
00000090000BFF40 - 2110
00000BD0000BDBD0 - 2109
0000090000026D90 - 262
0000000000000000 - 20

or

4924924920822492 - 278
A0A8000000000000 - 2110
000200000AAA0000 - 262
A0200000028A0000 - 259
0020000002080000 - 277
80880000028A0000 - 295
2022000008200000 - 257
8000000000000000 - 225
6924924920002492 - 20

do exist for the linearized ïrRUPT64x2-256/6, it is not clear if they can be exploited at all with only 64 bits of freedom the attacker has in every input. The probability of an ADD=XOR approximation existing for the first two rounds is much lower than what the 2⁶⁴ possible pairs of inputs can satisfy on each step. Unfortunately, our computational resources are insufficient to prove either way. As it stands, ïrRUPTx2/5 is currently the fastest unbroken variant for any security level.

As we have also mentioned at the conference, the discovered colliding pairs for ïrRUPTx2/4 have little to no effect on the real life data. Any difference more than one word away from the collision generating input set would spread to a half of the state bits after one more input word pushing complexity of this attack well beyond the brute-force (2^h/2) as almost every bit of the state difference adds one bit to the complexity of this attack. Thus it does not allow generation of colliding messages at the same low cost unlike the Merkle-Damgård collisions.

We believe that EnRUPT/8 provides a sufficient security margin away from the best attacks, while EnRUPT/H is the simplest although the slowest choice and EnRUPT-256/8,-384/10,-512/12 offers provable security against linearized collisions. Please vote for your preference. We have until June to make a decision and choose the best security/performance trade-off. Currently, the vote is leaning towards EnRUPT/8 as the best choice… Please write to us. We appreciate your input.

The slightly corrected slides (including memory requirements) are available at www.enrupt.com/EnRUPT_2009.pdf and their b/w printable copy at www.enrupt.com/EnRUPT_2009_bw.pdf.