| « enRUPT Related-key Attack | ïrRUPT Collision Resistance » |
ïrRUPT64x2/H
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).
9 comments
Face it. You are out of the competition!
Are you sure Boole can not be patched by doubling the amount of rounds?
1. No changes need to be made to EnRUPT submitted as EnRUPT[w]x[P]/[s] and so far not broken as such.
2. Whether EnRUPT is in or out of the competition, it is up to NIST to decide, NOT you. However, your bitterness is understandable. EnRUPT is too competitive. Many submitters are eager to see it out of their way.
3. You are shooting in the dark obviously without any knowledge of Boole structure or the attack. Boole has no tunable parameters, it is submitted fixed at 16 mixing rounds. The Boole attack also exploits a structural flaw that cannot be fixed with extra rounds. So, yes, I am sure.
It is up to the designer of the algorithm to pick the correct parameters (tradeoff between security and performance). You made a wrong choice.
In your specification you wrote: "Therefore, in order to be able to break ïrRUPT faster than 2^h, the attacker must be able to approximate each arithmetic adder at a cost of less than w/4⋅(s–1) bits, which is highly unlikely even for s=2." Now it turns out s has to be at least 8...
"algorithms that specify the number of rounds as a parameter" makes no sense. It is either a specific number or a variable parameter. In case of EnRUPT it is a parameter, not a specified constant.
The measurements of complexity of linearization were incorrectly transferred from block hashing to stream hashing. We do not say that s has to be at least 8, even for stream hashing. It is still at least 2 for block hashing and for stream ciphers. For collision resistance it probably has to be at least 5 for w=32 and at least 7 for w=64. We recommend a slightly higher value for s to guarantee a sufficiently high change in the state between the inputs.
No matter how much you want to see EnRUPT removed from the competition, it is still incorrect to call the entire EnRUPT family, its ïrRUPT mode and even more specifically ïrRUPT64x2-256/s broken. No one has pointed out a structural weakness in any of them, merely an attack against 8 rounds of ïrRUPT64x2 (s=4). The future versions of its specification will be updated accordingly. It is not even known if EnRUPT is going to be accepted in the competition yet, so your verbal attacks are premature.
> looking to get rid of all the most competitive
> algorithms as quickly as possible?
It is instructive to compare your and Greg Rose's responses to having your hash broken.
Yes it is. It is also very instructive to compare the two hashes and the attacks. Greg Rose’s hash has no tunable parameter and requires major structural changes to protect against the attack. Contrary to that, EnRUPT was submitted with a security parameter s, requiring only a few extra rounds to defend against such class of attacks. In that light, EnRUPT cannot even be considered or called broken, only 8 rounds of it are broken. 5 rounds of Rijndael are broken, and nobody is complaining about Rijndael with 10.
Naturally, Greg Rose does not want people to waste any more time on his hash since it cannot be easily fixed, while I insist that it is premature to declare EnRUPT broken trying to dismiss it, no matter how much you hate it as one of your competitors. EnRUPT simply does not need any fixing, only tuning the tunable parameter requested by NIST to increase its security. All the attacks must take all the parameters into consideration before claiming EnRUPT to be broken.
Comment feed for this post
