A Note on SIMON-32/64 Security
eprint.iacr.org
eprint.iacr.org
https://crypto.stackexchange.com/questions/70467/what-are-th...
The cryptanalysis (really, "proof of zero knowledge", if I might clarify and shoplift someone else's zinger at the same time) they claim to have performed is slower than brute force.
Long story short: this is almost certainly just a troll.
For those who are unaware: Thomas Pornin is a professional cryptographer. He's a member of the NCC Crypto Services team and one of the authors of the Sosemanuk stream cipher, which was part of the final portfolio for eSTREAM. He's also involved in the development of one of the cryptosystems which has made it to round 2 of the ongoing NIST PQCRYPTO standardization process.
His writing on crypto.stackexchange is prolific and highly informative, and this is a strong rebuttal in particular.
- Novel crypto analysis technique which can't be revealed because "a lot of work to be done to obtain an optimized, more efficient and industry-level version".
- Claim that success probability is low, but "we have a 2nd algorithm": "To date the probability of success is still very low (p = 0.025) but we are optimistic about the possibility of significantly increasing it in the upcoming months. Indeed we have a second algorithm, which is theoretically proven, with a success rate of 0.25. It is not yet fully tested and executed because it requires a higher computing power, although it is still reasonable for operational cryptanalysis (which can be repeated over time)."
- Claim that SIMON algorithm had been introduced in the Linux 4.16 kernel (it was Speck, not Simon). May be an honest typo.
- Testing on Odroid cluster.
- Can't find anything on "Alba3 Group" or the authors (who have @protonmail.com address -- also suspicious).
- "The only reference for this magnitude of cryptanalysis is [9]. In 2002, a 64-bit RC4 key was obtained in 1,754 days (300,000 participants). Today, to keep up with the evolution of computing power since 2002, it is necessary to divide by 2^10, or about 3 days with the same number of participants." It was RC5, not RC4 (it's even in the title of reference -- again, may be a typo), and how did they come up with 2^10 number?
I don't math, but it also looks suspicious: https://twitter.com/colmmacc/status/1127100892883312640
See also:
https://www.reddit.com/r/crypto/comments/bn5hds/crikey_key_r...
In any case, my real takeaway:
> Our main result is that we can find a 64-bit key in about three days (average time) on two Odroid MC1 clusters (8 Gb) [18] from two pairs of plaintext/ciphertext.
The algorithm isn't strong vs key reuse. I'm unsure if it actually claimed to be so - key reuse is almost always a big problem, though, and in this case they're exploiting the birthday paradox to make the search for the key more efficient.
> how did they come up with 2^10 number?
I'd guess common interpretation of Moore's law as a doubling of computing power every 18 months. 2002 was 17y ago, so you end up with ~11 doublings. Discrepancy can be explained by ballparking.
>But we are not going to publish how
>Trust us
Yeaaaaah, no.
As highlighted by dchest and that twitter thread, highly improbably anything real comes out of this.
https://emergent.unpythonic.net/files/sandbox/474.py
(Table 5 isn't "important", it's just a justification of why their algorithm 1 skips analyzing pairs where the plaintext in each pair is identical; and finding such keys doesn't seem TOO hard to do in the obvious way, you can get one such key every 4 billion trials or so)
PS The authors thank an Oleg Ivanovich Popov. I found one such person who is a researcher ... with publications such as "Thermodynamics of Hydrogen-Sulfide Conversion in a Claus Reactor in Coke-Oven Gas Desulfurization Circuit of MMK"
https://emergent.unpythonic.net/files/sandbox/474bis.py
It does seem like there has to be some interesting cryptanalysis going on to produce this many interesting pairs, particularly when they're (claimed to be) drawn from a relatively short corpus.
However, when considering how you would generate such pairs, you need not actually do "Algorithm 1" (in which step 6 is "do the secret magic"); you can select your block Pi and key Ki, then see if the result happens to be a block Ci that you can claim you picked first. In "pg10.txt" there are 53103 distinct 4-byte blocks, or about 2^32 pairs of blocks, so if you work in this way you only have to do around 2^33 SIMON-64/32 block encryptions to be able to produce a new row of "table 6".
Also, some of the C/E values are not actually present in "pg10.txt", their supposed restricted corpus. For instance, "{" is a character in several of them, but appears nowhere at all in my copy downloaded from the URL they gave. So they have somehow failed to accurately describe the corpus they actually used.
$ curl -s > pg10.txt https://www.gutenberg.org/cache/epub/10/pg10.txt
$ grep -F '{' pg10.txt
$ sha256sum pg10.txt
33d5b0600eed937022386d3d1afd2316f1fa219bd0e3ce723c8b1fb49352498f pg10.txthttps://emergent.unpythonic.net/files/sandbox/trolled.txt
Here's the search program (built with g++ -O3 -fopenmp -fno-strict-aliasing on debian stretch)
https://emergent.unpythonic.net/files/sandbox/search.c
Just put the corpus "pg10.txt" in the current directory and run.
Newlines in the corpus are turned to spaces; carriage returns are deleted.
I back-checked just a few using the same Python SIMON implementation.
Also, interestingly, none of the authors seem to have left much footprints on the Internet, which is extremely odd at best, the sign of some kind of fraud at worst...
A 64-bit keyspace is small enough that I don't think it's reasonable to take their paper as proof.
It would be fairly straight forward to use a FPGA farm (or potentially GPU farm) to search the entire keyspace. The fringes of the cryptocurrency altcoin ecosystem have caused the creation of some pretty impressive FPGA and GPU farms...
Additionally since they equate two pieces of text from the document via a key, they can get a massive speedup if they don't actually fix them. On this basis their proof mechanism seems highly suspect to me, unless I'm misreading it.
To be more clear of about I'm suggesting: pick a piece of text from the source, pick a key, encrypt or decrypt, then check if the result is anywhere in the text. Assuming the lookups are free this gets you a 4.2 million fold speedup (the corpus they're using is about 4.2MB). I'm not familiar with the structure of the cipher but there may be a meet in the middle that dramatically improves this approach.
It's completely reasonable that someone might search a 64-bit keyspace as a prank, ... I factored a 100-digit semiprime last night for a prank. My prank was not anywhere near as "cool" as convincing a lot of people that an NSA cipher was backdoored.
If this style algorithm does indeed have an intentional backdoor: That's some crazy mathematic chops and I'd love to read the theory behind how it (the intentionally weak algorithm) was found (since hopefully that leads to a natural way to generate stronger algorithms, or at least check for weak ones). That'd be a valuable takeaway for the security community once the secret's spoiled, if it is the case.
It should be noted that we should be very wary of these types of "nothing up my sleeve" numbers. djb showed[1] that with enough effort you could come up with more than a million "obviously not backdoored" numbers (this was done in the context of elliptic curves) -- enough to exploit a million-to-one unknown-by-the-public vulnerability.
My point is that "the values come from pi" is not necessarily proof that the constants really are "nothing up my sleeve". Bernstein was discussing this in the context of NIST curves (which could be backdoored), but the same one-in-a-million maths works for any constants (so long as you happen to know a weak-constants vulnerability that isn't known by the public).
That's not how you want to conduct cryptography as a science.
No, it doesn't.
EDIT: To whoever downvoted - developing cryptography is hard. The idea that developing one broken cipher implies mathematical incompetence is laughable. You can't draw any conclusion from it except that it's hard to develop ciphers which aren't broken.