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.

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.

The complete EnRUPT hash function submission to the NIST SHA3 competition is now officially online at http://www.enrupt.com/SHA3/. It will remain unaltered. No changes will be made without NIST authorisation and an official announcement in this blog.

It looks like 51% of our visitors do not believe that it has a chance… We know, it is hard to believe at a first glance that such a simple algorithm can be also secure and efficient at the same time.

For those of you who are too lazy to look at the document, it is the ïrRUPT64 mode with P=2 and s=4 parameters proposed for the general-purpose use. We did not complicate things by including our own high level parallelisation scheme such as tree hashing simply because EnRUPT can be used in any of them.

Wish us luck!

Complete ïrRUPT for P=2 in pseudocode (w=32 or w=64)

Apparently, the reverse engineered Philips/NXP Mifare Crypto-1 algorithm has been published along with some leaked NXP documentation for it. It looks an awful lot like the Philips/NXP Hitag2 cipher published earlier this year. We hope that Philips/NXP will stop trying to sue people for its own stupidity and start being ashamed.

Why ashamed? They have been caught red handed selling people fake security for many years and still trying to defend their position. Over a billion of deliberately made insecure Mifare microchips have been manufactured and sold putting all their users at risk in the name of the price/security ratio hoping that the inbuilt obscurity would protect their revenues for a while.

Philips/NXP knew very well just how bad the cipher was, which is why they kept it secret suing anyone who tried to publish any information about it. In the 21^st century it is no longer acceptable to keep a cryptographic algorithm a secret unless it is used exclusively by the military, and even then intelligent management should consider publishing it just in case others do find a flaw in it, so it could be replaced as quickly as possible.

Is it possible to fit a 256-bit secure cipher on RFID chips of that size and cost? – Yes of course. Could Philips/NXP have done it? – No. Why not? – Because microchip manufacturers are not cryptologists. Most of them do not have anyone qualified to do that and are too greedy to hire them. The only way to do anything right is to hire experts to do the job.

PS: It looks like the above mentioned algorithm implementation by I.C. Wiener does not specify the key byte order, which is also not perfectly clear from the picture. Our more detailed algorithm implementation and specification can be found in the work of Henryk Plötz, which we did not publish until the algorithm became available from other sources to protect its users a little longer from attacks that can be built on it.