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.

Itai Dinur and Adi Shamir have published their Cube Attack paper. A detailed study reveals that it is a brilliant straightforward linear key recovery attached to the ANF reconstruction that we have been using for 15 years to measure quality of ciphers. Some of our results are presented on our ASD site. Now that the genie is out of the bottle, lots of ciphers will fall. Some of the eSTREAM winners will fall… Now let us unveil some of the hidden historical facts leading to the discovery of the now famous cube attacks:

1. Before we revealed our monomial randomness analysis in Bochum in 2006, mere counting of monomials had been previously suggested by Eric Filiol and used by M-J.O. Saarinen.
2. Bart Preneel [one of the co-authors of Trivium] insisted that we submit a paper to the SASC 2007 workshop where Thomas Johansson [one of the co-authors of Grain] was the program chair.
3. In the only two weeks that were available to us, we had analysed a number of ciphers and submitted a paper that shows incredible weakness of Grain, Mickey and Trivium as far as monomial analysis is concerned.
4. While SASC is not a peer review conference with proceedings but a mere workshop for presenting new ideas and work in progress, our paper got rejected nevertheless, criticised by the reviewers as if it was submitted to Eurocrypt.
5. Thomas Johansson had almost immediately contacted Meltem Turan asking her to verify our results on Grain, Trivium and Mickey presenting them to her as their own: “We have these results…”
6. She did of course reproduce most of our results (limited to attacking only the IV), promptly publishing it as their joint work [known as “A Framework for Chosen IV Statistical Analysis of Stream Ciphers”] at the Tools for Cryptanalysis 2007 workshop [where our ASD tests were presented as well] and at INDOCRYPT 2007.
7. It appears that a year-long investigation of plagiarism by Thomas Johansson has been quietly swept under the carpet by the Lünd University.
8. Fischer, Khazaei, and Meier have explored adding statistical key recovery to our tests (limited to attacking only the IV again) publishing their work at AFRICACRYPT 2008 as “Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers”. Kudos!
9. Dinur and Shamir have announced their cube attacks at Crypto 2008 and published them on ePrint. Lots of Kudos!
10. F-FCSR has been removed from the eSTREAM portfolio of stream chipers leaving only Grain, Trivium and Mickey in the hardware category.

There are three parallel lines in this story: one is the catastrophic state of plagiarism in cryptology, unheard of in any other academic department. Unless one is willing to risk having their work stolen, they must publish it on ePrint immediately. The Cube Attack paper is already on ePrint due to appear in Eurocrypt-2009 in 10 months. It is not even certain yet if it is going to be accepted or not! By failing to observe the rules of this tricky game, we have lost our chance to finish our work and publish a proper paper at a peer review conference. It is of course flattering to see your work stolen like that, but this flattery has a bitter aftertaste. So watch out, cryptology students!

The other line is of course the development of the cryptologic research exactly in the direction we have set by revealing the details of our tests: monomial analysis is not only significantly more superior to linear and differential cryptanalysis as the cube attacks demonstrate and will continue to demonstrate, it can also analyse any black box cipher regardless of its structure, even unknown ciphers such as Mifare Crypto1.

The third line is the eSTREAM competition turning into another flop following the NESSIE competition fiasco failing to find a single good stream cipher… Once Grain, Trivium and Mickey fall victims of cube and algebraic attacks, there will be not a single competition winner in the hardware category. Mark our words.

Let us sit back, relax, and watch the remaining three algorithms by the greatest authorities in cryptology get badly broken as if they were made of paper. I am sorry, but I cannot even call them ciphers – they are that weak. It demonstrates yet again the “state of the art” in cryptology: cryptologists following each other’s research for years making minor improvements to each other’s linear and differential cryptanalysis… Now with the publication of cube attack paper and with an escalating amount of research in the direction of using SAT solvers for cryptanalysis, we will see a lot of old ciphers fall and a lot of new ciphers fall faster than ever before. Good bye, linear and differential cryptanalysis!

The cube attack paper lists our ASD tests among “chosen IV” attacks. It is not correct. Unlike the recent attempts to extend our tests to key recovery by attacking only the IV or the plaintext, our monomial testing includes analysis of proper randomisation of the secret (key) material as well as the public (IV or plaintext) variables. Since algebraic attacks, the cube attacks are the first to exploit the real potential of monomial analysis.

What is going to happen to EnRUPT, VEST and to other ciphers we have designed? – Nothing. Our ciphers are designed to resist any such attacks. Our Algebraic Structure Defectoscopy testing [AKA monomial randomness analysis] ensures that EnRUPT as well as all our other ciphers grow sufficiently complex sufficiently fast. EnRUPT with s=2 is resistant to the basic cube attacks and EnRUPT with s=4, just like all the VEST ciphers designed with s=4, will be resistant to any of the adaptive variants of cube attacks. To everyone else, good luck!

… and should undergo the same thorough cryptanalysis.

Verayo is the second company to announce the “World’s first unclonable RFID tag” based on a so-called “physically unclonable function” (PUF). The announcement reads:

“PUF technology is a type of electronic DNA or fingerprinting technology for silicon chips that makes each chip unclonable” besides the fact that it is the DNA that is used for cloning and that fingerprints are just as easily clonable.

PUFs are built around the idea of creating complex functions with some device-dependent inputs and some variable inputs for use in challenge-response protocols. Sounds like a keyed hash function, doesn’t it? – Well, it is.

While the basic idea of using process variation for creating variable identities is striking, the current realisation of PUFs defies several basic principles of cryptography. The algorithms that map inputs to outputs, for instance, are unknown, even to their designers. Furthermore, the device keys arise from process variation, which may or may not be a good source of entropy. Does this sound like security by obscurity?

Every circuit is a deterministic function. PUFs are no exception to this rule, but some of their inputs may not be controlled directly. When used for security, shouldn’t PUFs be cryptanalysed with the same rigour as other cryptographic functions? For a PUF to be cryptographically secure, its designers need to ensure that:

1. the fixed part of the circuit (the cipher) is cryptographically secure,
2. the number of device-dependent inputs (the secret key) is large and
3. the entropy of these inputs is high.

Neither of which seems to be the case. PUFs are a wonderful idea for using manufacturing variance constructively, but does their current realisation really use that potential for security or for obscurity?

Algorithms and protocols designed by the academics are getting more and more complicated for their users – software and hardware developers. The opportunities for attacks and implementation errors are growing along with complexity. It has gone too far. MD6 is a perfect example of what NOT to do if you are a code-maker – sacrifice simplicity on the altar of parallelism. Academic cryptographers have got to stop hating the industry so much and get down to Earth…

Dear Ron Rivest, with all due respect, first of all, memory is NOT plentiful and cannot be wasted on mere hashing like it was free, certainly not so in the smartcard or RFID applications responsible for most of our security, replacing keys everywhere.

Second of all, processor cores are NOT plentiful either. Of all the multiple-core CPU or GPU users, who would want to stall ALL their processor cores and engage them all at once in mere hashing of one long stream just to save some 50% in time it will take to do it??? Yes, it is a rhetorical question. If MD6 is indeed 200 MBps, the 5 seconds or 3 seconds it will take to hash a gigabyte will NOT make any difference whatsoever, while doing what? Freezing your entire server or workstation during that time??? Or what, freezing all 16 cores for a full second to engage them all in hashing? You gotta be kidding!!! Why not simply use a simple fast hash like EnRUPT, which would take 2.5 seconds engaging only one of the cores and not worry about a thing?

People get multiple-CPU cores for a reason, and for all of those people besides the handful of dedicated hashers or hash-breakers, it is NOT hashing. While theoretically it all sounds great, and even if the software developers do find a way to engage all the processor cores in hashing the same stream, [which I guarantee to be insanely complicated on its own], it is inherently a VERY BAD idea.

Dear code-makers, please talk to the software and hardware developers, especially the limited-resource application developers! Meet them, work with them. It is them who will have to implement the same exact monstrosity of a hash function of yours everywhere to adhere to the established standards if the company wants to be able to market its products. Those people cannot appreciate the beautiful complexity of all the mathematics in the design of your precious algorithm. They need simple things that they can understand, possibly even memorise and certainly implement themselves. A lot of them are not too bright and often are not even qualified to do any programming at all, but they do it nevertheless being responsible for a lot of useful products out there. They must be able to implement your cryptosystems successfully and effortlessly, or all their customers [and potentially all of us] will suffer the consequences. NXP Mifare and ePassports are perfect examples of that…

Code management costs A LOT, especially these days with the increased portability issues, developers having to adapt the old code to all the new hardware that is coming out continuously and to all the different compilers, even different versions of which are incompatible with each other… People can’t even agree on the same byte order! Developers have enough problems as it is. Just try to make your code compile with every compiler on every platform! You will see how quickly even the simplest things can get complicated. There is no need to overload their brains and their code with the unnecessary complexity of your design, just because you are too paranoid to keep things simple.

Dear code-makers, I implore you, please listen to Auguste Kerkhoffs and Keep It Simple, Stupid!

> Do cryptography experts deliberately choose complexity over simplicity
> when the latter might provide the same strength of protection?

Yes they do. For three main reasons:

1. Paranoia. Nobody really knows cryptology and whoever says that they do, they are lying. Unlike mathematics or physics studied for thousands of years, digital cryptology has only been actively researched by the academia for 33 years since the publication of the DES in 1975. The first NIST call for the DES resulted in 0 submissions. Thanks to the competitive nature of this field, the designed cryptosystems are constantly bombarded with attacks without much help for the code-makers to design systems resistant to those attacks. Besides the few fundamental works like the 1988 Luby-Rackoff paper [which took them two years to publish by the way, their first submission in 1986 got rejected], nobody really knows what is and what isn’t secure, what is weaker and what is stronger. The lack of knowledge makes designers over-complicate things unnecessarily. IMHO, if there is a flaw, the best way to fix it is by simplifying the design, not by making it more complicated. But I must admit that it is very hard to resist the urge to add that extra layer “just in case”.

The truth: Knowledge is power. The tools to verify what is and what is not secure do exist. Cryptologic theory needs to catch up with reality: neither linear nor differential cryptanalysis are responsible for a single cipher or hash being broken in practice. Algebraic attacks, guess-and-determine, TMDTO, adaptive collision searches and monomial analysis are the real threat and security against them can be verified and measured with automated tools.

2. Mathematics. Most cryptographers are either mathematicians or come from a very strong mathematical background [including myself] and we love beautiful mathematical structures. We like magic squares, we like fancy patterns, we like cool mathematical properties such as guaranteed long periods, etc. etc. etc. It is extremely hard to resist the temptation to include an unnecessarily complex but mathematically pretty component in your design that other mathematicians might admire. We do tend to forget that the beautiful mathematics of it tend to be responsible for the algebraic structures that may turn out to be exploitable to mount successful attacks. We get attached to our cute little babies and to their beautiful mathematical complexity.

The truth: The cipher’s job is to destroy mathematics as quickly as possible.

3. Show-off. The cryptographer’s ego often demands to show to the world that they can design a system that others will have a very hard time trying to comprehend. I myself am guilty of this one as well. We don’t want to make an impression that we are incapable of creating a more complex structure that would at least seem stronger, would be harder to analyse and would thus hopefully survive a little longer before someone figures out how to break it. “Security by obscurity” indeed.

The truth: Most ciphers are designed by the academics. “Publish or Perish!” is their motto. We all make our choices in lives and while the quiet achievers in the industry have chosen the money, the academics have chosen fame and glory. They must show off their academic superiority: they have so many students looking up to them and the whole world must admire their academic genius.

But at the end of the day, the most secure structure is a rock, a solid ball. Simple. No way in, no way out, nothing to pick on. Bruce Schneier has numerously pointed out that the higher the complexity the more vulnerable the system, and I too hope that we will start placing as much importance on the 6^th Kerkhoffs’ desideratum [le système doit être simple d’utilisation] as we do on the second one [les interlocuteurs ne doivent pas subir de dégâts au cas où le système de codage serait dévoilé].

*KISS*