Reconsidering Speck

The Speck cipher is geared toward good performance in software, which makes it attractive for smaller, often embedded, systems with underpowered CPUs that lack hardware crypto acceleration. But it also comes from the US National Security Agency (NSA), which worries lots of people outside the US—and, in truth, a fair number of US citizens as well. The NSA has earned a reputation for promulgating various types of cryptographic algorithms with dubious properties. While the technical arguments against Speck, which is a fairly simple and straightforward algorithm with little room for backdoors, have not been all that compelling, the political arguments are potent—to the point where it is being dropped by the main proponent for including it in the kernel.

A bit of history

Speck was merged for the 4.17 kernel and the fscrypt module for ext4 and F2FS added Speck128 and Speck256 support in 4.18. Speck is a block cipher, rather than a stream cipher, which makes it suitable for uses like filesystem encryption. As Eric Biggers noted when Speck was proposed in February, it is a good choice for low-end CPUs:

But the "controversial" nature of Speck that he referred to soon reared its head. In response to version 2 of the patch set in April, Jason A. Donenfeld questioned the move: "Can we please not Speck?" He noted that Speck (and its hardware-oriented counterpart, Simon) had recently been rejected by ISO. Biggers acknowledged Donenfeld's complaint, but asked what alternative he would suggest. Furthermore:

The ISO rejection was based on NSA refusal to answer questions about Speck and Simon, particularly with regard to what cryptanalysis the agency had already done on them, according to Tomer Ashur, who was part of the ISO group that rejected the ciphers. In that lengthy message, which came a few months after the rest of the discussion, Ashur outlined a number of different problems that he and others see with Speck and the NSA's behavior—though no serious technical flaws have been found in the algorithm itself.

Donenfeld said that one of his concerns was that "some of the best symmetric cryptographers in academia have expressed reservations about it", but did not offer up any alternative that might fit the bill. Biggers had mentioned some work that Google has done on alternatives, but there were concerns there as well:

Samuel Neves did have some suggestions on alternatives, however. He listed a handful of ciphers that might be worth investigating; Biggers implemented and compared many of those in a post in early May. The other algorithms were mostly slower than Speck and those that weren't suffered from other shortcomings. In that message, he mentioned Crowley's work again, with an eye toward proposing it as an alternative at some point:

Android dropping Speck

Since then, Google has decided not to use Speck and to pursue HPolyC (which is described in this paper [PDF]), Biggers said in an RFC patch set that was posted August 6. The patch set implements primitives for XChaCha20, XChaCha12 (which has fewer rounds), and the Poly1305 cryptographic hash for the Linux crypto subsystem. HPolyC is a combination of those primitives:

The switch to 12 rounds for ChaCha, from the more usual 20, was questioned by Donenfeld. Though he believes ChaCha12 "probably still provides adequate security", he is concerned that "introducing ChaCha12 into the ecosystem feels like a bit of a step backwards". He wondered what testing had been done to determine that 12 rounds was needed instead of 20.

Crowley pointed out that the best attack on ChaCha can only break seven rounds and requires 2²⁴⁸ operations to do so. "Every round of ChaCha makes attacks vastly harder." Neves agreed that 12 rounds was reasonable, but did note that more recent attacks on ChaCha7 have reduced the complexity to 2²³⁵:

Meanwhile, Crowley said that the performance of HPolyC is "still a lot slower than I'm happy with, and encryption still has a quite noticeable effect on the feel of low end devices" even using ChaCha12. Since it provides "a solid margin of security", ChaCha12 is what was chosen. He also noted that, even if all handsets were to get accelerated AES at some point, the low-end problem doesn't go away: "we'll probably be worrying about it for IoT devices".

Remove Speck from the kernel?

Since Google is no longer planning to use Speck, Donenfeld posted a patch to remove Speck from the kernel. Biggers was not opposed and acked the patch, though he did want to clarify that there were no technical flaws that he (or Google) knows about in Speck. There are other things to take into account, he said:

Jeffrey Walton argued against removing Speck in order to provide more algorithm choices. But, as Biggers pointed out, the kernel is probably not the right place to provide that choice:

But Theodore Y. Ts'o said that any decision not to use Speck and/or to remove it from the kernel is "purely political --- not [technical]". On the other hand, Ard Biesheuvel sees the decision to remove it from the kernel in more pragmatic terms:

The Speck code is a recent addition to the kernel and, as far as anyone knows, is unused since it will not be appearing in Android handsets. Assuming no other users materialize, it would seem likely that it will be gone before long. While the complaints of Ashur and other cryptographers are, in part, technical, those arguments are not particularly compelling, at least within the kernel community. But a lack of users—and maintainers—for the cipher is a good reason to remove it. While politics may have led to that outcome, it is a reasonable technical argument for its removal.

The NSA clearly burned many bridges with the cryptography community with its Dual_EC_DRBG shenanigans and other actions over the years. It should come as no surprise to the agency or anyone else that cryptographic contributions from the NSA are going to be heavily scrutinized. The likelihood that Speck is backdoored in some way is generally seen as quite low, but being uncooperative during the ISO review is not the way to get out of the hole it has dug for itself. The NSA has a large and potent stable of cryptographers, but its aims are not necessarily aligned with anyone outside its walls, so it is not surprising to see skepticism—or outright rejection—of algorithms it is pushing.

#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;
}