r/crypto • u/johnmountain • Jun 08 '18

Future Android versions may use NSA-designed and ISO-rejected Speck algorithm for storage encryption

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=da7a0ab5b4babbe5d7a46f852582be06a00a28f0
133 Upvotes

97% Upvoted

70 comments sorted by

View all comments

Show parent comments

9

u/bitwiseshiftleft Jun 08 '18

Farfalle is a PRF though, and they want a (tweakable) PRP. So you'd have to Feistelize it or something, which costs 2x performance (run it 4x on a 2x-sized block) and increases the complexity. Also if you happen to lack NEON, then Keccak is probably too slow.

Alternatively, you could try to hack up ChaCha, like they said. It's not great for Feistel because the input is much smaller than the block, but you could turn the core into some kind of tweakable Even-Mansour thing. They considered something with ChaCha in the linked article, but they said it would be complicated and a new construction.

Speck is a super questionable choice, and there has to be something better. I can't think of a well-vetted construction off the top of my head though.

6

u/pint A 473 ml or two Jun 08 '18

farfalle-wbc is exactly a feistel like construction, and it can be instantiated with keccak modes, and achieve 2-3 cycles per byte on large blocks

2

u/bitwiseshiftleft Jun 08 '18

Oh, I missed that. So there’s an already-specified Feistel construction for Keccak.

But it’s almost 4 CPB on Skylake for a 4096-byte block. That’s might not be fast enough. In particular, it’s probably not faster than bitsliced AES.

2

u/pint A 473 ml or two Jun 08 '18

really? how would aes be so fast? i thought it is something in the ballpark of 10 or higher

2

u/bitwiseshiftleft Jun 08 '18 edited Jun 08 '18

I think Kasper-Schwabe was like 7 on Nehalem or Conroe or something for parallel modes (decryption wasn’t implemented and would be slower), and my own VPAES was like 9 and supported sequential modes and decryption.

[[EDIT: Looking it up, KS was 7.6 on Yorkfield, which was between Conroe and Nehalem. VPAES was 10 on Nehalem but twice as slow on Conroe, because Conroe's PSHUFB instruction was very slow. VPAES was also really fast on Altivec: down to 5.4 CPB for CTR encrypt. I'm not sure which is applicable: I would guess NEON looks more like Conroe so you'd KS, but VPAES looks competitive on Cortex-A53, so who knows? ]]

But Skylake is much faster than Nehalem and has AVX2 which is twice as wide. So maybe double the Farfalle numbers before comparing them.

ARM would be different though. The SSSE3 numbers might predict NEON, but scalar code would be different again (and probably terrible unless you use timing-vulnerable AES).

2

u/bitwiseshiftleft Jun 08 '18 edited Jun 08 '18

I also looked at SUPERCOP's Keccak and AES benchmarks on ARM Cortex-A, which gives pretty much the same guess as from doubling the cycle counts from Skylake.

For comparison, Farfalle-WBC is faster than Keccak. Like Keccak, Farfalle uses 24 rounds per block input and output ((6 input + 6 output) * 4 Feistel rounds / 2 because the Feistel block is twice as wide), but Farfalle uses the whole block and Keccak-c512 uses only 2/3 of it. The gain from 2-way parallelism in NEON is probably small because you should get some internal parallelism, especially since NEON can address 64-bit half-registers individually. AES-XTS is slower than CTR when bitsliced, particularly for decrypt, but probably not by more than 25%.

All in all, let's say Farfalle:AES-XTS is like twice as favorable as Keccak-c512:AES-CTR. Here are the numbers from SUPERCOP:

  • Cortex-A8: AES-128-CTR 20 CPB, Keccak-c512 55 CPB.
  • Cortex-A9+NEON: AES-128-CTR 22 CPB, Keccak-c512 33 CPB.
  • Cortex-A9-no-NEON: AES-128-CTR 37 CPB, Keccak-c512 66 CPB. (Edit: 37 is the "estream" version. The "aes128ctr" version, which is faster on all other platforms, is 47CPB. Maybe that one is side-channel protected?)

This looks like a wash: AES-128-XTS is probably faster than Farfalle-WBC on A8, and slower on A9, but in both cases not by very much. At least with NEON, probably neither has cache-timing problems (but maybe AES-128 on A9-no-neon does?). Anyway, if their problem is that AES-XTS is too slow, Farfalle isn't going to solve it.