Reconsidering Speck

Posted Aug 9, 2018 5:56 UTC (Thu) by smurf (subscriber, #17840)
In reply to: Reconsidering Speck by brouhaha
Parent article: Reconsidering Speck

The problem is that we don't know whether there are technical reasons. Maybe it has an algorithmic back door – who knows?

The NSA has a recent history of having pushed questionable cryptography (the elliptical curves that are presumed to carry an interesting back door, for instance). Thus, yes, any other new crypto coming from them is automatically suspect and requires much higher scrutinity than the work of DJB or Schneier or whoever. Sorry, but that's their own damn fault.

I'd revisit Speck in a year or two. (Or longer … how long did it take before their rationals for modifying the DES s-boxes was rediscovered? ancient history, from the time when it was the National Security Agency instead of the National Surveillance Agency … again, their own damn fault.)

to post comments

Reconsidering Speck

Posted Aug 9, 2018 6:35 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link] (16 responses)

Have you checked Speck? Let me write its full source code here:

#define ROR(x, r) ((x >> r) | (x << (64 - r)))
#define ROL(x, r) ((x << r) | (x >> (64 - r)))
#define R(x, y, k) (x = ROR(x, 8), x += y, x ^= k, y = ROL(y, 3), y ^= x)
#define ROUNDS 32
void encrypt(uint64_t ct[2], uint64_t const pt[2], uint64_t const K[2])
{
   uint64_t y = pt[0], x = pt[1], b = K[0], a = K[1];
   R(x, y, b);
   for (int i = 0; i < ROUNDS - 1; i++) {
      R(a, b, i);
      R(x, y, b);
   }
   ct[0] = y;
   ct[1] = x;
}

Yes, it's THAT SIMPLE. There's quite literally no place for intentional backdoor here, unless NSA knows about a whole new class of attacks.

Reconsidering Speck

Posted Aug 9, 2018 11:21 UTC (Thu) by smurf (subscriber, #17840) [Link] (5 responses)

We don't know that there's no backdoor. Yes it looks simple, but so what? I can imagine as well as anybody that some NSA cryptographer or two thought of a clever trick that allows them to recover bits of the key by exploiting patterns in plaintext. Write a "simple" block cipher around that, propose it as a new standard, and presto! you win. The fact that nobody else has stumbled upon it doesn't prove anything.

We do know that no rationale has been provided by the NSA for several key parameters of this algorithm, including such boring parameters as ROUNDS (why 32? Cool neat power-of-two?).

For further details, see https://www.spinics.net/lists/linux-crypto/msg33291.html

Reconsidering Speck

Posted Aug 9, 2018 16:25 UTC (Thu) by zyzzyva (guest, #107472) [Link] (2 responses)

The parameters are explained in the paper "Notes on the design and analysis of Simon and Speck" (https://eprint.iacr.org/2017/560.pdf). For example, the number of rounds is explained on pages 12-13 (Section 4), with more discussion on pages 17-18. Basically, they say that for each variant of Speck they added a security margin similar to AES-128 on top of the rounds the best attacks (differential attacks) made it through. That's the same way that other cipher designers set their security margins, except that other designers often haven't done much cryptanalysis themselves, so they just make an informed guess. Granted, there are differences of opinion about what an appropriate security margin is; some designers prefer a larger or smaller security margin than AES-128. But Speck's designers make a reasonable argument for their choice.

Of course, people can argue that it's still not enough, or that the 2017 paper came too late so it doesn't "count" as things could have been retroactively justified. But it's not true that the parameters are unexplained.

Reconsidering Speck

Posted Aug 9, 2018 19:35 UTC (Thu) by smurf (subscriber, #17840) [Link] (1 responses)

This boils down to the fact that when I read an email message from a cryptographer with reasonable academic credentials who describes this rationale as glorified handwaving (my paraphrase) and points out numerous other errors or even lies etc. in this paper (see the email I linked to), I tend to trust that cryptographer and not the NSA (with numerous examples documenting the latter agency's history of, well, everything from glorified handwaving to lies), and you don't. (Assuming you have read that email.)

Fair enough, but no longer a technical discussion I'd be interested in.

Reconsidering Speck

Posted Aug 9, 2018 22:50 UTC (Thu) by zyzzyva (guest, #107472) [Link]

Well, not *trusting* the explanation is different from there not *being* an explanation.

Yes, I'm well aware of that email. The question of "trust" is relevant for things like the writer's personal experience where he is the primary source. But it isn't (or shouldn't be, in an ideal world) relevant for objective statements, like statements about what the designers claim, or about the current state of cryptanalysis of the ciphers; these can be verified using primary sources. I've read the primary sources, including third-party cryptanalysis and ironically even the writer's own paper he cites, and a somewhat different story is told; e.g., the claim of only a ~15% security margin isn't actually anywhere to be found, nor are rotational attacks on Speck (currently) any better than differential attacks. If you're interested and willing to learn new things, I encourage you to do the same, i.e. please don't just "trust" me either.

Remember, even cryptographers can have an axe to grind :-)

Reconsidering Speck

Posted Aug 9, 2018 18:07 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

Let me recap this message: "NSA bad. We good."

I still don't see any actual technical problems with the cipher itself. It belongs to the same family as the sainted Salsa or ChaCha, and the same attacks (do not) apply to it. If the NSA has some ground-breaking way to crack ARX ciphers then should we deprecate ChaCha and Salsa out of abundance of caution?

Reconsidering Speck

Posted Aug 9, 2018 20:13 UTC (Thu) by gioele (subscriber, #61675) [Link]

> If the NSA has some ground-breaking way to crack ARX ciphers then should we deprecate ChaCha and Salsa out of abundance of caution?

A credible argument IMO is that the NSA may have discovered ground-breaking ways to crack ARX ciphers that have certain properties. ChaCha and Salsa happen not to have these properties (maybe just out of pure luck) but Speck has been developed to have them.

Reconsidering Speck

Posted Aug 9, 2018 17:16 UTC (Thu) by felixfix (subscriber, #242) [Link] (4 responses)

Crypto backdoors are not hidden passwords and such. They are leaked bits, redundancies that reduce the keyspace, weaknesses that supercomputers can attack, mathematical quirks that leave clues for careful observers.

Reconsidering Speck

Posted Aug 9, 2018 18:04 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link] (3 responses)

Have you _checked_ the source code? There are no hidden parameters in Speck. It's dead simple.

Reconsidering Speck

Posted Aug 9, 2018 18:54 UTC (Thu) by felixfix (subscriber, #242) [Link] (2 responses)

Have you checked the source code for the XOR cypher? It's even simpler.

Oh ho! you say, I know that trick. It's not a real cypher!

And there's your answer. Not all backdoors are secret hard-coded passwords.

Reconsidering Speck

Posted Aug 9, 2018 19:00 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

XOR with a one-time pad is a good cipher. So nope.

Reconsidering Speck

Posted Aug 9, 2018 23:02 UTC (Thu) by simcop2387 (subscriber, #101710) [Link]

XOR with a one time pad is only as good as the pad. If it has patterns (bit 12 is never set) or was generated with a backdoored RNG, then it's no longer a good cipher.

The argument here is that because the rationale hasn't been provided (maybe even if it had been), we can't know if the NSA has a way to know something like, if bits 12 and 13 of the key are set to 01 then bits 0-7 of the key only end up adding 2 bits of entropy to the result (obviously an overly simplified example).

The attacks on the rationale that has been provided are better covered in other comments, but it basically seems to boil down to "There's a lot of unanswered questions we have about this, that everything else we use has answered, why won't you answer them?"

Reconsidering Speck

Posted Aug 10, 2018 0:04 UTC (Fri) by gerdesj (subscriber, #5446) [Link]

"Let me write its full source code here:"

Those first three #DEFINES look a bit tricksy to me! I offer as a counter example:

Z_n+1 = Z_n² + c

OK, there is additional complexity (hah!) in what Z really means but let's face it, you can get a lot out of messing around with that equation. I recall my first efforts with GW Basic on a 80286 ran to around 20 odd lines. Here's an example in C: Mandelbrot set plotter

Reconsidering Speck

Posted Aug 10, 2018 0:51 UTC (Fri) by wahern (subscriber, #37304) [Link] (2 responses)

It's also worth pointing out that the key schedule is baked into the above code. Performant implementations can break out the key schedule and save some work on long streams. But what makes Speck so enticing is precisely how simple it is. It could be the new RC4. But therein lies the dilemma.

RC4 was so successful because it was so simple, easy to implement, and susceptible to copy+paste imports. Without RC4 cryptography on the internet may have been delayed even further; not just because of opaqueness of cryptographic engineering but because of the difficulty software management in general. The engineering benefit of this *should* *not* be underestimated. Not only does it make it easy to wield strong cryptography in novel ways (think SipHash), but there's less chance for getting it wrong. People have screwed up key mixing into bespoke ChaCha CSPRNGs. That would be more difficult to do with Spec because the obvious way to turn it into a CSPRNG doesn't involve tweaking the internals, particularly if you stick to the above code which doesn't break out the key schedule.

OTOH, RC4 ultimately proved too simple. And I think that's the fear with Speck. It's not the parameters, per se, that bother people. The only real parameter is the number of rounds, which qualitatively isn't the type of parameter that traditionally invites suspicion. What concerns people is whether the state-of-the-art in the community is sufficient that people can reasonably rely on the absence of evidence that its too weak as evidence of absence for the duration of its lifetime. DJB has stated in some papers that he thinks the community relies too heavily on proofs of security--they're not always properly verified, and people overlook explicit or implicit premises that leave room for future attacks. Which is another way of saying that he thinks there are still too many unknowns, that there's still an art to cryptography, and some amount of unquantifiable complexity is prudent.

Similarly, there's an argument that Speck is so simple and so enticing that it might displace future, stronger alternatives.

Those are really what the criticisms boil down to. They're reasonable perspectives but they're difficult arguments to make, and of course easy to conflate with NSA animus, which I think is what has actually happened.

I'm not a cryptographer but I've written lots of software that use cryptographic primitives. And I'm familiar with the limitations of existing libraries, including pre-packaged stacks like NaCL. From my perspective Speck is hugely enticing. Not to replace traditional primitives, but to augment the ecosystem. Two simple examples off the top of my head:

1) A simpler portable arc4random. Have you seen the "portable" ChaCha-based arc4random files floating around!? It's not the kind of code you'd ever want to touch, yet compiling it as its own unit file brings integration headaches, especially in libraries and modules, because of visibility issues. (Building cross-platform C code is really easy these days if you keep things simple, *except* when managing symbol visibility beyond the standard C extern or static scopes.)

2) Permutation generators. I once used XTEA to write a 16-bit Feistel cipher for a DNS QID permutation generator that used only a few bytes of state per context, rather than the typical solution of using a Fisher–Yates shuffle on a 128KB array (or keeping a cached of used QIDs), which isn't user friendly if you're trying to avoid dynamic memory, sharing data structures, or introducing non-obvious edge cases. It didn't matter that XTEA wasn't a particularly strong cryptographic cipher; it was strong enough to generate 16-bit QIDs such that it was no easier to break than a system shuffling an array with a provably secure CSPRNG.

Reconsidering Speck

Posted Aug 10, 2018 10:17 UTC (Fri) by tialaramex (subscriber, #21167) [Link] (1 responses)

"OTOH, RC4 ultimately proved too simple. And I think that's the fear with Speck"

I think this helps calibrate the worries we're talking about here. RC4 is considered completely broken... but you actually need to do a lot of heavy lifting to get anywhere against RC4 with the best known attacks. The web is insanely friendly to an adversary because they're assumed to be allowed to tell both parties to do loads of encryptions / decryptions (public web servers, clients run Javascript) and the adversary gets to eavesdrop and time everything. So on the web when you say things like "With just $40k of pre-computation after 2^20 trial encryptions we were able to recover a byte with 84% success" that's rightly considered broken.

For comparison the Banburismus technique to attack the Kriegsmarine Engima were considered viable if about 200 messages had been intercepted.

And so with this calibration I have to agree with Google's original stance. This is much better than nothing. Even if it turns out that the NSA knows something we don't about Speck and it's to their advantage (which it seems is what so many observers imagine, even though the reality is just as likely that the NSA found nothing and _doesn't want anybody who does finds things to realise they're a step ahead of the NSA_) the NOBUS principle protects us from a lot of other adversaries.

If we get this complicated and perhaps somewhat fragile DJB-based alternative deployed instead, that satisfies me, and so in the end I'm not so worried as I was when it looked like the fanatics were determined to have nothing rather than risk approving of anything from the NSA. But I think we've strayed far into the weeds on this, which is disappointing, even if the NSA must take most of the blame for that.

Reconsidering Speck

Posted Aug 10, 2018 13:47 UTC (Fri) by smurf (subscriber, #17840) [Link]

> the fanatics were determined to have nothing rather than risk approving of anything from the NSA

Umm, no. As you wrote yourself,

> the NSA must take most of the blame for that

So, well, they could easily have answered questions about Speck openly. They didn't, thus fuelling the well-deserved suspicion (these days) about any novel crypto thingy proposed by them.

The NOBUS principle might have been a valid doctrine in earlier days. These days it's just hubris. The Puzzle Palace is not an impenetrable fortress; we need to assume that any secret knowledge the NSA has about this algorithm – and they certainly act as if they do have such knowledge – will be made public tomorrow, at which point Speck-based encryption may or may not be a big pile of security theater make-believe. That's not good enough even if you happen not to be a "fanatic".

Reconsidering Speck

Posted Aug 10, 2018 18:32 UTC (Fri) by synaxin (guest, #122012) [Link]

What would Bruce say?

https://www.schneier.com/blog/archives/2013/07/simon_and_...
He's got a comment lower:
"The code is not relevant here; the question is whether a back door could be hidden in the mathematics of the cipher, like this [this links to https://www.schneier.com/essays/archives/2007/11/did_nsa_...].

It's hard. Basically, the NSA would need to have a cryptanalytic technique that is 1) powerful enough to practically break the algorithm, and 2) unknown to the academic world. And it's risky. Once the algorithm is out there, there's a good chance that we in the academic community would figure out the technique. (When the NSA updated SHA to SHA-1, it didn't take that long for the academic community to figure out why.)

So, maybe, but I don't think so."

Reconsidering Speck

Posted Aug 9, 2018 17:40 UTC (Thu) by brouhaha (subscriber, #1698) [Link] (2 responses)

Lack of a reasonable rationale document _IS_ a technical reason, having nothing to do with politics.

Reconsidering Speck

Posted Aug 9, 2018 17:50 UTC (Thu) by pizza (subscriber, #46) [Link] (1 responses)

> Lack of a reasonable rationale document _IS_ a technical reason, having nothing to do with politics.

However, the definition of "reasonable" is highly political.

Reconsidering Speck

Posted Aug 9, 2018 20:42 UTC (Thu) by brouhaha (subscriber, #1698) [Link]

Did you read the Ashur email? When the NSA did provide their so-called rationale, they did not really address even the most basic concerns raised by the ISO committee. That would be grounds for rejection_regardless_ of who was pushing the cipher. That's why I stand by my statement that the rejection was on a technical basis, not political.