What are the implications of the new alleged key recovery attack preprint on SIMON? Just recently, a new attack was published against SIMON-32/64 which claims to also be applicable to other versions of the cipher. The paper is titled A Note on SIMON-32/64 Security (archived 2019-05-11) and describes a new practical, low-cost key recovery attack which is significantly faster than exhaustive search. Unfortunately, the authors spend more time describing a zero-knowledge proof that allows them to refuse to publish their analysis methods than in actually describing their analysis.

Abstract: This paper presents the results of a new approach to the cryptanalysis of SIMON-32/64, a cipher published by NSA in 2013. Our cryptanalysis essentially considers combinatorial properties. These properties allow us to recover a secret key from two plaintext/ciphertext pairs, in a time ranging from a few hours to a few days, with rather limited computing resources.
The efficiency of our cryptanalysis technique compared to all known cryptanalyses (including key exhaustive search) is a justification for not revealing the cryptanalysis techniques used. We have adopted a zero-knowledge-inspired method of proof which was initiated in [11].

Given only what is known so far, what are the implications of this attack? Does it apply to any SIMON-like block cipher, or is it a general technique that works on a large number of different ciphers?
TL;DR: this paper seems to be a joke, or delusional; the "zero-knowledge proof" proves nothing.



The report purports to have found an efficient cryptanalysis on SIMON-32/64, a small block cipher. The exact details are, on purpose, not disclosed. However, to convince the reader that the method actually exists, a so-called "zero-knowledge proof" (not really what is usually called zero-knowledge, by the way) is presented in section 4. What I will show here is that this proof shows nothing, and the same kind of feat could be relatively achieved with any block cipher with the same block size.

SIMON is a family of block cipher. Here, we talk about the "smallest" of these, SIMON-32/64, which has blocks of 32 bits and keys of 64 bits. The block size is important here: it means that when the article shows 64-bit plaintexts and ciphertexts, these really are pairs of plaintext blocks and pairs of ciphertext blocks, encrypted in ECB mode.

Let's see the first kind of "proof": the paper shows a few keys that encrypt the plaintext "YHWHYHWH" into the ciphertext "YHWHYHWH" (using ASCII encoding for both). As explained above, these really are keys that encrypt "YHWH" (32-bit plaintext block) into "YHWH" (32-bit ciphertext block); the repetition is a mere distraction. If you find a key that encrypts a given 32-bit block $P$ into a given 32-bit ciphertext block $C$, then of course the same key will encrypt $P\mathbin\|P$ into $C\mathbin\|C$, and $P\mathbin\|P\mathbin\|P$ into $C\mathbin\|C\mathbin\|C$, and so on. This is what ECB mode means.

Now, take a given plaintext block $P$, and a given ciphertext block $C$. How hard is it to find a matching key? If you take a random key $K$, the encryption of $P$ with key $K$ yields a ciphertext block $C'$, which has size 32 bits. Thus, the probability of having $C' = C$ is about $2^{-32}$. Which means that if you try random keys, you'll need on average to try about $2^{32}$ keys to find a match. Any decent-sized laptop should be able to try about $2^{25}$ keys per second (I am assuming here that encrypting a block takes 400 clock cycles, the CPU runs at 3.2 GHz, and there are four cores; we can probably do a lot better than that with AVX2 capers, but let's focus on stupid, basic software). Thus, $2^{32}$ keys will be tried in about two minutes. In other words, if you ask me to find keys that encrypt "YHWHYHWH" into "YHWHYHWH", then I should find one every two minutes. The six keys presented in the article represent less than 15 minutes of work of a single laptop! And all of that is using SIMON-32/64 as a black box, i.e. assuming that it is a perfect, ideal block cipher.

Now, let's investigate the second "proof": the authors take a large corpus of 64-bit messages (pairs of blocks), extracted from the King James Bible. In raw UTF-8 text (really, ASCII, it's all in English and does not contain the word café), this is a 4452069 bytes file. This means that there are 4452062 sequences of 8 bytes in there. Let's round that low to $2^{22}$ to make computations easier. The "proof" is that they show keys that map one of these blocks to another of these blocks; the table 6 shows 18 such plaintext/ciphertext/key triplets (the text of the article says "19" but there are only 18 in the table).

Take a perfect ideal cipher with 64-bit blocks (here we are not even going to use the fact that SIMON-32/64 uses 32-bit blocks and that 64-bit messages are really pairs of 32-bit blocks). Take a random key. Encrypt one of the $2^{22}$ plaintext blocks into a 64-bit block. What is the probability that the output 64-bit block is one of the $2^{22}$ in the list? It's $2^{-42}$ (because there are $2^{64}$ possible 64-bit blocks and $2^{22}$ targets). This means that if you try random keys, you'll get a match every $2^{42}$ random keys on average. At $2^{25}$ per second, we're talking about one key every two days; the 18 keys will then take a bit more than a month. The authors claim to have required 120 days, so they're a bit lagging here. Again, taking the block cipher as an ideal black box, a basic brutal attack does better than the cryptanalysis claims.

(With some details: some basic optimization here is that the "attack" will only encrypt one 32-bit block to start with, and encrypt the second one only if there was a match with the first one; moreover, the lookup in RAM for a match can be optimized by doing it only if the output block is ASCII, i.e. if the top bits of each byte are zero, so we end up with, for each key: one SIMON-32/64 encryption, a test on the top bits of the output bytes, a lookup into RAM only in 1/16th of cases, and a second block encryption only in 1/64th of the cases were a lookup in RAM is done; thus, we can easily approximate the cost as "1 SIMON-32/64 encryption per try".)



So whatever they are doing, it does not seem to be any better than brute force that has nothing to do with the internal structure of the block cipher.

An open question is whether this is a deliberate prank, a skewed attempt at damaging the reputation of the eprint maintainers, or a case of self-delusion. I don't attempt to answer that question.