EnRUPT – The Simpler The Better

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 4 times by setting s=16. It would still remain reasonably competitive at 20 CPB on 64-bit CPUs and at 50 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.

Five years ago, the DSD puzzle corner got updated with boring easily solvable puzzles, and to make it even less interesting, the solutions to them got provided as well. Since there is no web page containing solutions to all the cool old DSD puzzles [if you can’t see the crossword there, select all the text with CTRL-A], and since even the puzzles themselves are nowhere to be found besides the internet archive, we have decided to share our solutions:

1. The words of a problem are numbered in lexicographical order. Then the first word of the problem is written in the position denoted by 1, the second word in the position denoted by 2, etc. The result is: “five random order is eight that numbers six one square four are the what a written digit is resulting number probability and three in down the the”. Solve the (mathematical) problem!

   The mathematical problem is: “The numbers one three four six and eight are written down in random order. What is the probability that the resulting five digit number is a square?”. The answer is: 1/24.

2. Authorities intercepted the message LJPPV KOUYK OIRWQ HKIQC DPAKB RXHJI, believed transmitted by a gang of smugglers. This was decrypted to: “Password for next month is Bogeyman”. About a month later the message KUVMF PPVLO RVDII EUPUK QLKQS UPRFX was intercepted. This was decrypted to: “New password will be sent on Tuesday”. The following Tuesday the single word EFGMRIHQ was intercepted. What was the new password?

   The three messages are encrypted with monoalphabetic substitution with encryption keys JANUARY, FEBRUARY and MARCH. The last message decrypts to the new password HIJACKER.

3. A broker sent a cable to a client advising the purchase of a commodity on certain terms. The message, which contained no repeated letters, was only ten letters long. The client converted the letters into numbers (A=1, B=2, etc.) and was amazed to notice that no three of these numbers formed an arithmetic progression. What was the message?

   Of all the possible anagrams that satisfy the given requirement, only one makes sense in the given context: BUY TEN FLAX.

4. Self-Referential Crossword

   

Congratulations, Nevada!

We are very pleased to see an intelligent government leading the way for everyone else into the 21^st century, the age of information. As of the 1^st of October, the state of Nevada will require businesses to encrypt their internet communications.

What is the worst crime to commit in any country, a crime so bad that it is punished worse than murder? – It is high treason, incomparable with petty treason, an aggravated form of murder. Sending an unencrypted e-mail is as good as as adding to it BCC: NSA and BCC: Other Foreign Agencies. Thus by sending unencrypted e-mails or messages, you are committing the worst crime there is, treason, as you are sharing all your correspondence with the foreign intelligence agencies. That is not counting your gross negligence of allowing hackers and everyone else see your messages.

The Vedas teach us that stupidity is a sin. We cannot plead ignorance under the mask of naiveté forever without getting punished for it. When one commits a crime, one is responsible and punishable even if one is unaware of having done anything wrong. All our e-mails and instant messages are thoroughly scanned, analysed and recorded by a number of agencies as well as the countless hackers, and as surveys show, by dangerously irresponsible ISP employees.

All the initial difficulties of enforcing the new law aside, the US State of Nevada is the first to make the key step towards prevention of hacking and digital espionage: enforcing encryption of all the business traffic. Well done!

I implore all the governments in the world to follow this lead and to enforce strong encryption of business communications in your countries as soon as possible. The benefits of preventing the damage from the industrial and government espionage, hacking, worms, viruses, trojans and other malware, by far outweighs the losses from inability to intercept communications of the dumbest few of the criminals and terrorists, most of whom use strong encryption anyway.

Abusus non tollit usum

It looks like the cube attacks have been preceded by a year by Michael Vielhaber. An interesting twist…

Although AIDA is not as catchy a name as “cube attacks”, but judging by the paper, it is indeed the same thing. We are glad to see the algebraic structure analysis growing to become the mainstream cryptologic research.

Forget all the hype around the clonability of electronic passports! The US is taking it up a notch. The new US RFID-“enhanced” drivers licenses cost their legitimate users a whopping $30 more than the old ones to pay for the additional feature of allowing hackers to enter into the US by land or sea from Canada, Mexico and the Caribbean with a cloned RFID-“enhanced” drivers license now instead of a passport! Apparently, no biometrics, no personal information and no digital signatures of any kind will be stored or transmitted by the $30 chip, only an ID to replay… Forget encryption!

Far out!!! Will they ever learn???

I don’t even know how to comment on this without offending anyone.