EnRUPT – The Simpler The Better

After a long analysis and due consideration, we have decided to propose EnRUPT/8 for all three 64-bit variants: EnRUPT64x2-256/8, EnRUPT64x2-384/8 and EnRUPT64x2-512/8 as our updated SHA-3 submission.

In simple terms, the same security parameter s=8 is chosen for different sizes due to the fact that the most effective [linearized collision] attacks cannot break a greater number of rounds for the larger sizes with their much higher security levels that allow for much more expensive attacks. Since the more expensive attacks cannot break a greater number of rounds, the attacker’s control is limited equally for all the different sizes, most probably by the word width equally limiting the attacker’s control. Therefore, an equal number of rounds is sufficient for the different sizes, while the higher security is achieved by increasing the size of the state. Although we firmly believe in the cryptographic resistance of s≥5 and we are working on a proof of its resistance to linearization attacks, we propose s=8 to establish a sufficient margin from the best known attacks (2x) to ensure a lasting public trust in the algorithm.

The latest improved 64-bit C and the new Intel Assembly implementations also bring the speed of EnRUPT/8 from 10 to 7.8 CPB (Core 2 Duo, with minor variations on different CPUs) placing it somewhere between Tiger and SHA-1 by speed.

We will publish and submit the updated specification including the updated optimized implementation soon.

With best regards,
The EnRUPT Team

While we are working on determining the best value for ïrRUPT security parameter, we do not have much time for watching the news, but this is something we thought is worth your attention because of its irony:

The US is outraged that India restricts symmetric encryption to 40-bit security.

We think it is truly hilarious. The US has gone a long way from banning strong encryption to developing standards for it to enforcing it and enforcing it more and now… to forcing others to allow it. It looks like the US officials are beginning to realize that the benefits of secure communications far outweigh the losses since the vast majority of the population are NOT criminals. We do not remove the seat belts from the cars just because they would save lives of the terrorists, do we?

I wonder if India has access to the AES-256 encrypted Skype chats, calls and file transfers or if Skype S.A.R.L. has deposited some sort of an Additional Decryption Key with their DOT to avoid getting themselves banned from the second largest country in the world?

PS: Apparently, that PTI News article got deleted without an explanation.

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.

Say hello to full disk encryption! All six major hard disk manufacturers have finally agreed on a single open specification for full encryption of hard drives with proper secure management of passwords and encryption keys. The painfully complex specification supports SHA-1, SHA-2 and the AES in proper secure modes of operation and seems like a lot of good work that the world must be very grateful for, including the little additional side effect: the stolen hard drives have no value anymore as they will not even power up.

Thank you, guys! Great job! I hope that you all got well paid for it. You deserve it.

An interesting new related-key attack has been found that can break enRUPT32x1 (block cipher mode) if the attacker is allowed to modify the key and request a sufficiently large number of chosen plaintext/ciphertext pairs. We will comment on it after a thorough investigation of the attack itself, how it got overlooked by our tools and what is required to prevent it in the future by detecting such vulnerabilities with automated cryptanalysis.

Interestingly enough, this attack also breaks XXTEA but without the need for related keys. Also, according to the author of the attack, it cannot be applied to the stream cipher or stream hashing modes of EnRUPT including the ïrRUPT mode submitted to the SHA-3 competition.

After studying Sebastiaan’s linearization attack in detail, we have come to the conclusion that EnRUPT does not require any structural changes, corrections or tweaks and that its dismissal is more than premature. It is only a matter of setting the ‘s’ parameter to a slightly higher value increasing the amount of diffusion in the state between inputs.

It is incorrect to call EnRUPT or EnRUPT/s broken in general as there is no structural flaw exploited in the recent collision attack. Only EnRUPT/4 is broken so far. After a detailed study of this attack, we can recommend the following variants:

EnRUPT64x2-224/8, s=H=8
EnRUPT64x2-256/8, s=H=8
EnRUPT64x2-384/12, s=H=12
EnRUPT64x2-512/16, s=H=16

That is, EnRUPT64x2/H by simply setting s=H. In general, s should be set to approximately (h+63)/64+4P-2 for all the different EnRUPT variants throwing all such linearization based collision searches well beyond the birthday bound. At such speed, ïrRUPT preimage resistance will also be higher.

In regard to the other variants included in the submission, we also recommend:

EnRUPT32x2-128/8, s=H=8
EnRUPT32x2-160/10, s=H=10
EnRUPT32x2-192/12, s=H=12

As NIST requested, we have submitted a highly parameterised algorithm to the SHA-3 competition. It looks like we have chosen a variant that is a little too fast to resist linearization based collision searches. Even being 2-4 times slower, EnRUPT still has a competitive performance at 10-20 CPB on 64-bit CPUs, much faster than most submissions. Or maybe we should have submitted EnRUPT/2H or EnRUPT/64 like Professor Bernstein did with CubeHash/1 just to avoid someone labelling it as “broken” in a hurry? Are we looking for a good algorithm or are we looking to get rid of all the most competitive algorithms as quickly as possible?

We hope that Sebastiaan will have the time to include in his paper his own measurements of what values of s are sufficient for EnRUPT to resist such attacks. We sincerely apologise for any inconvenience caused. We will publish a paper with our findings after Sebastiaan Indesteege publishes the details of his cryptanalysis.

Unless proven otherwise, it is still unnecessary to use such high values of s for the stream cipher modes as the cost of finding linearized collisions in the unkeyed unrandomised ïrRUPT has no impact on other attack scenarios. EnRUPT can still use s=2 to operate as a PRNG or authenticated or unauthenticated stream cipher (running at 2-2.5 CPB on 64-bit Core 2 Duo).

Collisions have been found in ïrRUPT64x2-256/4 with its default parameters.

We have taken the risk of submitting the least researched but the most convenient stream hashing mode of EnRUPT to the SHA-3 competition to encourage its cryptanalysis and to learn if there are any hidden security problems with stream hashing.

It looks like we have overestimated the total cost of linearization in regard to stream hashing. While EnRUPT itself and its ïrRUPT stream hashing mode do not require any structural changes, the recommended default parameters are insufficient to resist linearization-based collision searches.

Most probably, ïrRUPT-256 must be simply slowed down 2 times by setting s=8. It would still remain reasonably competitive at 10 CPB on 64-bit CPUs and at 26 CPB on 32-bit CPUs, much faster than most submissions. We will have to wait for Sebastiaan to publish his paper to see what parameters he can recommend for ïrRUPT as collision resistant.

It is still hard to find ïrRUPT preimages, which is the same as finding the secret key for EnRUPT stream cipher modes RUPT and aeRUPT. By increasing the number of rounds, ïrRUPT preimage resistance will also be increased.

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.