[PATCH v2 0/5] crypto: Speck support

[Eric Biggers]

Hi Samuel,

On Wed, Apr 25, 2018 at 03:33:16PM +0100, Samuel Neves wrote:
> Let's put the provenance of Speck aside for a moment, and suppose that
> it is an ideal block cipher. There are still some issues with this
> patch as it stands.
> 
>  - The rationale seems off. Consider this bit from the commit message:
> 
> > Other AES alternatives such as Twofish, Threefish, Camellia, CAST6, and Serpent aren't
> > fast enough either; it seems that only a modern ARX cipher can provide sufficient performance
> > on these devices.
> 
> One of these things is very much not like the others. Threefish _is_ a
> modern ARX cipher---a tweakable block cipher in fact, precluding the
> need for XEX-style masking. Is it too slow? Does it not have the
> correct block size?
> 
> > We've also considered a novel length-preserving encryption mode based on
> > ChaCha20 and Poly1305.
> 
> I'm very curious about this, namely as to what the role of Poly1305
> would be here. ChaCha20's underlying permutation could, of course, be
> transformed into a 512-bit tweakable block cipher relatively
> painlessly, retaining the performance of regular ChaCha20 with
> marginal additional overhead. This would not be a standard
> construction, but clearly that is not an issue.
> 
> But the biggest problem here, in my mind, is that for all the talk of
> using 128-bit block Speck, this patch tacks on the 64-bit block
> variant of Speck into the kernel, and speck64-xts as well! As far as I
> can tell, this is the _only_ instance of a 64-bit XTS instance in the
> entire codebase. Now, if you wanted a fast 64-bit ARX block cipher,
> the kernel already had XTEA. Instead, this is adding yet another
> 64-bit block cipher into the crypto API, in a disk-encryption mode no
> less, so that it can be misused later. In the disk encryption setting,
> it's particularly concerning to be using such a small block size, as
> data volumes can quickly add up to the birthday bound.
> 
> > It's easy to say that, but do you have an actual suggestion?
> 
> I don't know how seriously you are actually asking this, but some
> 128-bit software-friendly block ciphers could be SPARX, LEA, RC5, or
> RC6. SPARX, in particular, has similarities to Speck but has some
> further AES-like design guarantees that other prior ARX block ciphers
> did not. Some other bitsliced designs, such as Noekeon or SKINNY, may
> also work well with NEON, but I don't know much about their
> performance there.
> 

I agree that my explanation should have been better, and should have considered
more crypto algorithms.  The main difficulty is that we have extreme performance
requirements -- it needs to be 50 MB/s at the very least on even low-end ARM
devices like smartwatches.  And even with the NEON-accelerated Speck128-XTS
performance exceeding that after much optimization, we've been getting a lot of
pushback as people want closer to 100 MB/s.

That's why I also included Speck64-XTS in the patches, since it was
straightforward to include, and some devices may really need that last 20-30% of
performance for encryption to be feasible at all.  (And when the choice is
between unencrypted and a 64-bit block cipher, used in a context where the
weakest points in the cryptosystem are actually elsewhere such as the user's
low-entropy PIN and the flash storage doing wear-leveling, I'd certainly take
the 64-bit block cipher.)  So far we haven't had to use Speck64 though, and if
that continues to be the case I'd be fine with Speck64 being removed, leaving
just Speck128.

Note that in practice, to have any chance at meeting the performance requirement
the cipher needed to be NEON accelerated.  That made benchmarking really hard
and time-consuming, since to definitely know how an algorithm performs it can
take upwards of a week to implement a NEON version.  It needs to be very well
optimized too, to compare the algorithms fairly -- e.g. with Speck I got a 20%
performance improvement on some CPUs just by changing the NEON instructions used
to implement the 8-bit rotates, an optimization that is not possible with
ciphers that don't use rotate amounts that are multiples of 8.  (This was an
intentional design choice by the Speck designers; they do know what they're
doing, actually.)

Thus, we had to be pretty aggressive about dropping algorithms from
consideration if there were preliminary indications that they wouldn't perform
well, or had too little cryptanalysis, or had other issues such as an unclear
patent situation.  Threefish for example I did test the C implementation at
https://github.com/wernerd/Skein3Fish, but on ARM32 it was over 4 times slower
than my NEON implementation of Speck128/256-XTS.  And I did not see a clear way
that it could be improved over 4x with NEON, if at all, so I did not take the
long time it would have taken to write an optimized NEON implementation to
benchmark it properly.  Perhaps that was a mistake.  But, time is not unlimited.

RC5 and RC6 use data-dependent rotates which won't perform too well on NEON,
also historically those algorithms have been patented.  It sounds like the last
patents expired last year, but we'd need to double check and be very sure that's
really the case.

As for the wide-block mode using ChaCha20 and Poly1305, you'd have to ask Paul
Crowley to explain it properly, but briefly it's actually a pseudorandom
permutation over an arbitrarily-sized message.  So with dm-crypt for example, it
would operate on a whole 512-byte sector, and if any bit of the 512-byte
plaintext is changed, then every bit in the 512-byte ciphertext would change
with 50% probability.  To make this possible, the construction uses a polynomial
evalution in GF(2^130-5) as a universal hash function, similar to the Poly1305
mode.

Using ChaCha20's underlying 512-bit permutation to build a tweakable block
cipher is an interesting idea.  But maybe in my crypto-naivety, it is not
obvious to me how to do so.  Do you have references to any relevant papers?
Remember that we strongly prefer a published cipher to a custom one -- even if
the core is reused, a mistake may be made in the way it is used.  Thus,
similarly to Paul's wide-block mode, I'd be concerned that we'd have to
self-publish a new construction, then use it with no outside crypto review.
*Maybe* it would be straightforward enough to be okay, but to know I'd need to
see the details of how it would actually work.

But in the end, Speck seemed like the clear choice because it had multiple NEON
implementations available already which showed it could be implemented very
efficiently in NEON; it has over 70 cryptanalysis papers (far more than most
ciphers) yet the security margin is still similar to AES; it has no intellectual
property concerns; there is a paper clearly explaining the design decisions; it
is naturally resistant to timing attacks; it supports a 128-bit block size, so
it can be easily used in XTS mode; it supports the same key sizes as AES; and it
has a simple and understandable design with no "magic numbers" besides 8 and 3
(compare to an actual backdoored algorithm like Dual_EC_DRGB, which basically
had a public key embedded in the algorithm).  Also as Paul mentioned he is
confident in the construction, and he has published cryptanalysis on Salsa20, so
his opinion is probably more significant than mine :-)

But I will definitely take a closer look at SPARX and some of the other ciphers
you mentioned in case I missed something.  I really do appreciate the
suggestions, by the way, and in any case we do need to be very well prepared to
justify our choices.  I just hope that people can understand that we are
implementing real-world crypto which must operate under *very* tight performance
constraints on ARM processors, and it must be compatible with dm-crypt and
fscrypt with no room for ciphertext expansion.  Thus, many algorithms which may
at first seem reasonable choices had to (unfortunately) be excluded.

Thanks!

Eric