31
$\begingroup$

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, now archived, is titled A Note on SIMON-32/64 Security 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 supposed findings.

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 ciphers?

$\endgroup$
11
  • 1
    $\begingroup$ @kodlu They don't find "the key" with any higher probabilities of finding "a key" that selects a working permutation. It's probably just a simple calculation to determine whether or not it would be practical to recover "the key" in that circumstance if given a realistic number of plaintext/ciphertext pairs. In particular, it'd be necessary to find out the probability of one of the keys actually being the original key. $\endgroup$
    – forest
    May 11, 2019 at 5:14
  • 1
    $\begingroup$ @kodlu: assuming that Simon-32/64 acts like a random permutation family, then there is an expected one false key that maps the two (P, C) pairs together (in addition to the correct key). So, if there are able to find a key, then either Simon has unexpected properties, or they do have a good probability of finding the correct one. $\endgroup$
    – poncho
    May 11, 2019 at 13:16
  • 3
    $\begingroup$ I don't know the practice for incorporating code samples here in crypto, but I actually wrote a program to produce more "table 6"-like C/E/K values. It can produce around 1000 such in a CPU minute on my i7. emergent.unpythonic.net/files/sandbox/search.c -- put a copy of the corpus "pg10.txt" in the current directory and run it. Since "table 6"-alike data can be produced effortlessly without breaking SIMON, there's no need to take their secret method seriously. $\endgroup$
    – Jeff Epler
    May 11, 2019 at 16:57
  • 2
    $\begingroup$ Related "Hacker News" thread, mentioning this site, with some more research on the publishers of this great book (pun intended). $\endgroup$
    – Maarten Bodewes
    May 11, 2019 at 18:40
  • 2
    $\begingroup$ The paper appears to no longer be available at the linked location. It is, however, available via the Internet Archive. $\endgroup$
    – user
    May 14, 2019 at 11:25

2 Answers 2

56
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ I checked the examples in table 5 and 6. I couldn't reproduce table 5. It's not Simon-32/64 ECB. $\endgroup$ May 11, 2019 at 15:32
  • 20
    $\begingroup$ This paper is an elaborate joke. It seems like a modern cryptographer's equivalent of Death and the Compass. Look at the authors' names! John Matthew, James Luke, and Mark? $\endgroup$ May 11, 2019 at 17:41
  • 2
    $\begingroup$ Besides, their names don't match any person at a university or institute it seems. Actually Luke Menzis is a professional wrestler. Probably required to help break the crypto algorithm :) And they have just one mail address on Protonmail, a swiss organization that will keep their actual identity secret. Note that some of these organizations require you to publish a paper to get access to their library (if you're not directly affiliated with a university or similar)... $\endgroup$
    – Maarten Bodewes
    May 11, 2019 at 18:29
  • 11
    $\begingroup$ Bwahaha, we like to thank mr Oleg Popov for his contributions. That's it, I'm out. Oh, yeah, and the surnames are of 3 "professional" wrestlers. So we have 3 wrestlers and the worlds best known clown in addition to the evangelists that Squamish already found. $\endgroup$
    – Maarten Bodewes
    May 11, 2019 at 18:47
  • 3
    $\begingroup$ @kelalaka: not SCI-GEN; the paper has more global coherence than what you'd expect from a computer-generated paper $\endgroup$
    – poncho
    May 11, 2019 at 23:26
7
$\begingroup$

In addition to the excellent mathematical analysis done by Thomas Pornin which thoroughly debunks the supposed benefits of this attack, it seems there are also numerous jokes or oversights peppered throughout the paper that make it clear that it's just a prank and not a professional research paper:

  • The surnames of the authors are those of professional wrestlers.

  • The first and middle names of the authors are the names of gospels in the Bible.

  • They claim to be part of a group called Alba3, which does not appear in any searches.

  • At the end of their paper, they thank Oleg Popov, a Russian circus performer who died in 2016.

These all point to it being a hoax or parody paper. Together, it looks like it's definitively a fake.

$\endgroup$
7
  • $\begingroup$ There is no obvious evidence of any company named Alba3 Group, but there are allegedly three coauthors and ‘Alba’ is the name for Scotland in Scots-Gaelic (and in antiquity). $\endgroup$ May 12, 2019 at 2:59
  • $\begingroup$ @SqueamishOssifrage Yeah I searched for Alba3 when I first read the paper and couldn't find anything. $\endgroup$
    – forest
    May 12, 2019 at 3:00
  • 4
    $\begingroup$ They thank "Oleg Ivanovich Popov", which may be a combination of Oleg Ivanovich Yankovsky and Oleg Konstantinovich Popov. $\endgroup$
    – Nat
    May 12, 2019 at 4:14
  • 1
    $\begingroup$ In addition to the answers pointing to a joke, I would add that Alba3 also sounds a bit like Albatross. Or maybe this is just a coincidence. I wonder what its meaning could be. $\endgroup$
    – mocenigo
    May 12, 2019 at 14:58
  • 3
    $\begingroup$ @MartinBonner: Speaking of odd word choices, there's also the suspicious "SIMON et SPECK" at the beginning of the introduction, which might hint at a French author. (Perhaps coincidentally, the author of the "zero-knowledge-like proof" paper cited as inspiration in the abstract is also French.) But of course it could also be a deliberate red herring. $\endgroup$ May 13, 2019 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.