Add constant-time AES-GCM that doesn't require assembly language

[briansmith]

Currently, we have AES-GCM implementations that are constant time for many advanced processors, with SIMD and/or dedicated instructions (e.g. AES-NI). However, we should have constant-time AES-GCM for every platform we support.

See https://bugzilla.mozilla.org/show_bug.cgi?id=868948 for ideas, though we can't copy code from that bug without assurances that we can use it under an ISC license or similar.

[DemiMarie]

The obvious implementation is dog slow.

There is a trick that uses precomputed tables and uses bitwise operations for lookups, but it is also slow, even with SIMD.

Some thoughts:

• I believe that x86 chip built since 2003 has SSE2, so I think we can simply drop support for >= 13-year-old hardware.
• My understanding of AArch64 is that SIMD is built in to that instruction set.
• That leaves 32-bit ARM. IMO forcing such a chip to do AES-GCM is a bug in a higher-level protocol and/or its implementation (should be using ChaCha20-Poly1305), but in the real world some have no choice.

My first thought would be to check if cache lookups within a cache line are constant time on ARM32. Otherwise, such users will need to live with miserable performance.

[briansmith]

That leaves 32-bit ARM.

Also, eventually, MIPS. (I would live to eventually port ring to OpenWRT and other low-end MIPS devices.)

My first thought would be to check if cache lookups within a cache line are constant time on ARM32. Otherwise, such users will need to live with miserable performance.

That's mostly what I'm thinking too. See also the comments in aes-586.pl regarding cache timing countermeasures.

[jkilpatr]

@briansmith what would be the criteria for a solution to this issue? Long story short we need mips support and are in a position where we pretty much just have to add it.

Can we make a arch generic pure rust implementation instead of a mips specific one? I understand that might have constant time issues, any thoughts on solutions?

If we must write assembly what are the exact criteria?

[randombit]

Don't know if it helps but there is an approach implemented here:

https://raw.githubusercontent.com/randombit/botan/master/src/lib/modes/aead/gcm/ghash.cpp
https://raw.githubusercontent.com/randombit/botan/master/src/lib/modes/aead/gcm/clmul_ssse3/clmul_ssse3.cpp

that is constant time (without relying on lookups within a cache line being side channel silent, which at this point is known to be an invalid assumption), easily implemented with either ALU or SIMD, and relatively fast (on a Sandybridge, the SSSE3 version is ~18 cycles/byte, ALU ~22 cycles/byte which seems to compare favorably with the 29 cpb reported for the (not const time) NSS patch on same arch). The SSSE3 version would map well to NEON I think, though I haven't tried yet.

[jkilpatr]

barebones mips processors have no vector extensions. The generic cpp could be useful.

[DemiMarie]

Darn. Do you really need AES-GCM? It will be dog slow. Are you sure you cannot use ChaCha20-Poly1305? If you absolutely must have AES-GCM (because the legacy protocol you are implementing requires it), your best option is probably that taken by BearSSL. On Jul 18, 2018 8:45 AM, "Justin Kilpatrick" <[email protected]> wrote: barebones mips processors have no vector extensions. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#104 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGGWB4FPV4u2RkFil0fSJ6itzQqDb22Xks5uHy3bgaJpZM4HTxez> .

[jkilpatr]

we are using ChaCha20-Poly1305 unrelated to Ring we have some libraries (infrequently used for signing things) that pull in Ring, so we need mips support for Ring and speed is not really a concern.

[briansmith]

Regarding MIPS support, let's discuss that in the MIPS issue: #562. Maybe fixing this issue (#104) is part of solving that, maybe not.

[briansmith]

PR #970 is the first step at this. After that, my plan is to merge the BoringSSL C fallback implementation of GCM and then its C fallback implementation of AES.

[briansmith]

PR #972 is the next step.

[briansmith]

PR #973 adds the GCM code needed for this. AES to follow.

[briansmith]

PR #976 and PR #977 are two more steps towards getting this done.

[briansmith]

PR #981 adds the Rust GCM code.

[briansmith]

PR #993 adds the AES code.

[briansmith]

Note that the portable AES and GCM implementations come from BoringSSL. BoringSSL writes their code assuming the target is little endian. Thus, additional work is necessary to adapt this code to work for big-endian targets. I don't intend to do that adaptation myself, but I will review PRs that do that adaptation.

[briansmith]

This is done.