Reconsidering Speck

Posted Aug 8, 2018 18:51 UTC (Wed) by wahern (subscriber, #37304)
In reply to: Reconsidering Speck by brouhaha
Parent article: Reconsidering Speck

Design rationale from the designers: https://eprint.iacr.org/2017/560.pdf

See also their other papers: https://github.com/nsacyber/simon-speck

At the end of the day it was primarily political. People can keep arguing that the designers didn't do *enough* explaining, but no amount of explanation would have ever be enough.

Simon and Speck were never really pushed by the NSA; not like other algorithms. The NSA knows how to work the standards process, and knows how to dot their Is and cross their Ts. Simon and Speck was a side project of some internal staff who took the initiative to solve a problem they foresaw. Now, you can disagree with their vision of the problem (i.e. no encryption is better than so-called lightweight encryption); but the solution viz-a-viz the problem is a technical matter susceptible to direct, substantive analysis.

(Of course, maybe it was all subterfuge. But I don't think that's a healthy attitude. In hindsight the truly nefarious stuff the NSA has done could have been--and sometimes was--properly assessed according to the technical merits. And it's worth pointing out that when the NSA really wanted to be surreptitious they've used third-party proxies or lied about identities.)

to post comments

Reconsidering Speck

Posted Aug 8, 2018 19:10 UTC (Wed) by brouhaha (subscriber, #1698) [Link] (5 responses)

I've read that rationale, and I agree with Ashur that it is thoroughly inadequate compared to rationales and published cryptanalysis results of other algorithms.

When I say that the decision is technical rather than political, what I mean is that ANY cipher with such a poor rationale should be rejected, regardless of who it came from, government or otherwise. If DJB had invented it and pushed it without a proper rationale, it would have been rejected for exactly the same reason. If you look at the rationales and published results for other modern algorithms, including AES (Rijndael), SHA3, X25519, Ed25519, etc., they provide exactly the sort of information that NSA refused to provide to ISO regarding Speck. The considerations are the same regardless of who proposes it.

The lack of a proper rationale doesn't prove that there's nothing nefarious going on, but it certainly doesn't inspire any confidence.

Reconsidering Speck

Posted Aug 8, 2018 22:31 UTC (Wed) by zyzzyva (guest, #107472) [Link] (1 responses)

> If DJB had invented it and pushed it without a proper rationale, it would have been rejected for exactly the same reason.

Are you sure? I think there's a double standard. Salsa and ChaCha, for example, didn't come with any formal cryptanalysis either, only some hand-wavy explanations about a few types of attacks:

* https://cr.yp.to/snuffle/security.pdf
* https://cr.yp.to/snuffle/design.pdf
* https://cr.yp.to/chacha/chacha-20080128.pdf

Like Speck, cryptanalysis was left for third parties. djb even formally proposed 8-round variants of Salsa and ChaCha, even though they turned out to have basically no security margin! (To be clear, the 12 and 20-round variants of ChaCha are still secure, and seem to be excellent stream ciphers; they've since undergone significant third-party cryptanalysis.)

It's true that Salsa and ChaCha were published over a decade ago too, so perhaps (and I hope!) the academic standards have gotten stricter since then. Either way, Speck's design rationale (https://eprint.iacr.org/2017/560.pdf) seemed more detailed, especially when combined with the authors' previous 3 other papers. I understand that people still go out of their way to find every reason to claim otherwise, and that there is more information the authors would have included in an ideal world, e.g. revealing cryptanalysis methods that aren't publicly known, which likely do exist, though the authors did mention which of their attacks did best, or least which they claim did best (differential cryptanalysis).

And there's a reasonable argument that if the authors don't publish *everything* they know, then their paper is insufficient, regardless of the details they *do* provide -- even if it is already greater than that which other authors provided. Still, personally I was impressed by the level of detail provided, and when evaluating other ciphers I usually found myself wishing that their authors had provided as much details as the Speck authors did.

To be clear, I'm *not* arguing that Speck should remain in the kernel, or that it should be used when other options are available. I just wish that people would be honest about how cryptographic primitives are assessed. In reality, it's clear that the author does matter. Whether that's a good thing or a bad thing can still be debated, of course...

Reconsidering Speck

Posted Aug 9, 2018 9:38 UTC (Thu) by jschrod (subscriber, #1646) [Link]

> Salsa and ChaCha, for example, didn't come with any formal cryptanalysis either

Are they ISO or NIST standards? I couldn't find any reference that they are.

Reconsidering Speck

Posted Aug 9, 2018 17:07 UTC (Thu) by flussence (guest, #85566) [Link] (2 responses)

You mention SHA3, but I recall Keccak's authors being unhappy with how it was “tweaked” with no good reasoning.

Reconsidering Speck

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

I thought that NIST backed off and returned to the c=2d capacity in the final standard, as a result of public criticism. My understanding is that the final SHA3 choice is in fact a proper subset of the Keccak proposal. Were there other changes I've overlooked?

Reconsidering Speck

Posted Aug 12, 2018 21:14 UTC (Sun) by flussence (guest, #85566) [Link]

The basis of the complaint was that SHA3 chose different defaults for tunable parameters, compared to what was originally used. As you said, it's still a proper subset of Keccak that way.

I haven't paid full attention to events though, so I guess I missed the part where they backed off later on. Thanks for the correction.

Reconsidering Speck

Posted Aug 8, 2018 20:03 UTC (Wed) by mageta (subscriber, #89696) [Link] (22 responses)

What gives. Somehow I don't have a problem with discriminating against the NSA purely based on political reasons.

> Of course, maybe it was all subterfuge. But I don't think that's a healthy attitude.

I realize its probably irrational .. but not being paranoid is a very hard thing to sell when it comes to this actor. And my guess is, it will stay that way for some time to come.

Reconsidering Speck

Posted Aug 8, 2018 20:13 UTC (Wed) by brouhaha (subscriber, #1698) [Link] (21 responses)

Somehow I don't have a problem with discriminating against the NSA purely based on political reasons.

Some people might be OK with nixing NSA-pushed ciphers for political reasons, others might not. But if there are technical reasons also, then it's that much easier to justify. Refusal to provide requested design rationale information qualifies as a technical reason IMO, since that is completely independent of who is pushing the cipher.

Reconsidering Speck

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

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.)

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.

Reconsidering Speck

Posted Aug 9, 2018 10:29 UTC (Thu) by dunlapg (guest, #57764) [Link]

Did you read the comment from a cryptogropher on the ISO committee? There's no way I'd approve an algorithm where I'd had an interaction like that.

Distrusting people who act distrustful may not be "technical", but it isn't "political"; it's just good judgement.

Reconsidering Speck

Posted Aug 12, 2018 23:53 UTC (Sun) by ceplm (subscriber, #41334) [Link]

> At the end of the day it was primarily political. People can keep arguing that the designers didn't do *enough* explaining, but no amount of explanation would have ever be enough.

And so what?

This is just about my pet peeve, when somebody is not able to sustain discussion, so he discards all objections are "just political". Political means related to polis, and yes, polis of programmers is what decides here. Of course, our decisions are political. And yes, NSA past behavior is huge political black eye on its face, which makes all its onward contributions suspicious (aren't they just worried that their last efforts to provide snake oil were thwarted, so they try a new one?).

In short, there is nothing about political argument.

(if somebody wants to say that the code in question was not sufficiently conservative, socialist or any other political ideology, then he is just silly and should be ignored)