keccak: add aarch64 ASM implementation for f1600

[recmo]

This uses ARMv8.4-A FEAT_SHA3 instructions which can be found on recent Apple processors. (tested on M1, but ARMv8.4 is as early as A13, but I can't find information if A13 implements the SHA3 extensions)

[tarcieri]

The provenance of this code appears to be the Linux kernel and therefore it's GPLv2 licensed, which is quite restrictive. We generally look for the most liberal licenses possible even making exceptions for our normal Apache 2.0+MIT for assembly.

Perhaps you could look at the eXtended Keccak Code Package (XKCP)?

https://github.com/XKCP/XKCP

There appears to be an implementation here, although I'm not quite clear on if it uses FEAT_SHA3 or not:

https://github.com/XKCP/XKCP/blob/master/lib/low/KeccakP-1600-times2/SIMD128/KeccakP-1600-times2-SIMD128.c

I believe that code is in the public domain, although it doesn't have a specific public domain dedication (e.g. CC0) outside the toplevel LICENSE file.

[tarcieri]

Regardless of what implementation we go with, it would also be good to have cross tests in CI.

Here's an example of how we do them elsewhere:

https://github.com/RustCrypto/block-ciphers/blob/4334b85/.github/workflows/aes.yml#L222-L249

[recmo]

The provenance of this code appears to be the Linux kernel and therefore it's GPLv2 licensed, which is quite restrictive. We generally look for the most liberal licenses possible even making exceptions for our normal Apache 2.0+MIT for assembly.

It's basically the ARM reference implementation (see gigantic pdf):

The only difference between the reference and this one / the Linux kernel one is that the registers are renamed so they are consecutive v0-v24. This makes loading/storing a bit easier. The loading/storing code here is original (the Linux one does some more clever tricks for block processing).

[tarcieri]

@recmo okay, can you make the code match the ARM reference manual, add a reference to its origin and remove references to the Linux kernel?

That should hopefully address the IPR issues.

[recmo]

Perhaps you could look at the eXtended Keccak Code Package (XKCP)?

As far as I can tell (not the most readable source) it's not using any of the FEAT_SHA3 codes. I can check openssl and supercop implementations.

[recmo]

OpenSSL: https://github.com/openssl/openssl/blob/cac250755efd0c40cc6127a0e4baceb8d226c7e3/crypto/sha/asm/keccak1600-armv8.pl#L561

Ah, and here is an XKCP one, just a different repo: https://github.com/XKCP/K12/blob/master/lib/ARMv8Asha3/KeccakP-1600-ARMv8Asha3.S#L69

[recmo]

The problem with the ARM reference version (and why everyone changes it) is that it doesn't loop nicely. The output registers are in a different order than the input.

I can change it to the register convention from XKCP. Does that work?

[tarcieri]

Sure, that's fine

[newpavlov]

Should we consider this change MSRV-compatible? asm! was stabilized in 1.59, which is much bigger than MSRV of this crate and, more importantly, than MSRV of sha3. The sha3 target feature is unstable, so IIUC it should not be enabled by target-cpu=native, but strictly speaking sha3 may get enabled on pre-1.59 toolchains.

Also, have you tried to use the arch intrinsics? If there is no substantial difference in performance between generated assembly, I think we should prefer an intrinsics-based implementation behind nightly-only crate feature (or configuration parameter). It also should help with keeping state in registers between rounds.

[tarcieri]

@newpavlov to avoid MSRV incompatibilities we can have an asm feature.

Re: intrinsics, my guess would be the ones needed are unstable, where asm! is stable

[newpavlov]

Yeah, I will be fine with introducing an asm feature with MSRV note until the necessary intrinsics get stabilized. Ideally we would have both implementations (asm and intrinsics based), but the latter could be added in a separate PR.

[recmo]

Also, have you tried to use the arch intrinsics?

I did look at them and the required instructions have intrinsics. But they require nightly+experimental while the asm block will work on stable.

For example: https://doc.rust-lang.org/stable/core/arch/aarch64/fn.veor3q_u64.html

It also should help with keeping state in registers between rounds.

Good point! We can change it to intrinsics once they are stable.

[recmo]

Finally got the cross test to build with the SHA3 feature (it requires upgrading cross to a later version than cross-install provides and forcing it enabled through RUSTFLAGS)

On stable it tests the assembly version:

https://github.com/RustCrypto/sponges/actions/runs/3353380335/jobs/5556112925#step:6:91

On MSRV it falls back to non-assembly without complaints:

https://github.com/RustCrypto/sponges/actions/runs/3353380335/jobs/5556112899#step:6:90

I assume this is because MSRV doesn't support target_feature = "sha3". But this raises the question if there are rust versions in between MSRV and stable that support target_feature = "sha3" but do not support asm! or those opcodes.

[newpavlov]

@recmo
As discussed earlier, you should gate the functionality on the asm feature. Do not forget to add a note about bumped MSRV. It could look like this.

Good point! We can change it to intrinsics once they are stable.

Would you be interested in prototyping it in a separate PR? We can have both backends simultaneously. It could be interesting to compare their performance.

[tarcieri]

it requires upgrading cross to a later version than cross-install provides

That's easy enough to bump.

Something else it'd be good to add to this PR is runtime feature detection using the cpufeatures crate.

The sha3 feature is already supported on ARM, so it shouldn't be too hard to add, and can replace the compile-time gating with selecting the best available implementation at runtime (with automatic compile-time gating if the appropriate target features are enabled).

You can look at the aes and polyval crates as examples which perform this sort of runtime feature gating on ARM platforms.

[tarcieri]

Going to go ahead and merge this. I'll take care of the cpufeatures integration (I have an M1 I can test it on)

[recmo]

Thanks!