Nettle project funded by Internetfonden
Status update for March 2013
* Summary
ARM optimizations of cryptographic primitives.
* Activities
The time in March have been spent mainly on ARM assembly implementation of various cryptographic primitives. The portability of the new ECC code has been improved, with contributions from Martin Storsjö. In the process, also the non-ARM code and the testsuite has seen some improvements.
The GNU GMP library is used by Nettle for general arithmetic on large integers. For example, each multiplication of two ECC coordinates is done as a call to a general multiplication routine in GMP, followed by a call to an optimized curve-specific function for reducing the product modulo a fixed prime p. During the month, some work has been done to make more low-level operations in GMP available for users of the library. The functions mpn_cnd_add_n and mpn_cnd_sub_n, for side-channel silent conditional addition and subtraction, are now available and documented, as well as some functions for easy conversion betwen GMP's higher-level "mpz" interface and the lower-level "mpn" interface.
On the GMP side, Torbjörn Granlund have been improving the ARM code. Relinking Nettle code with the development version of GMP also give nice performance improvements.
During March, 103 working hours have been spent on the project.
* Results
The "normal" ARM instruction set offers 16 general purpose registers, of 32 bits each. Some ARM processors, including the Cortex-A9, also offer an extension for single-instruction-multiple-data (SIMD). The ARM "Neon" instruction set is in some ways similar to the SSE2 instructions available on current x86_64 processors, but well designed and much easier to work with. It offers 16 additional registers of 128 bits each, with both integer operations on up to 64-bit quantities, and floating point operations (which are not used in Nettle).
Using Neon instructions gives a dramatic speedup for the SHA512 and SHA3 hash functions, which make heavy use of 64-bit operations. The ARM assembly code for the other algorithms don't make any use of Neon, but they have nevertheless beeen sped up compared to the C implementation, due to better register allocation, and tricks to use aligned reads for possibly unaligned input data.
There is certainly room for additional optimizations to the assembly code, in particular improving instruction scheduling.
* Benchmarks
For these cryptographic primitives, the numbers are in units of MByte/s, benchmarked on a 1GHz ARM Cortex-A9.
Algorithm Before After Speedup
memxor (aligned) 988 1906 93% memxor (unaligned) 511 638 25% aes-128 17.3 21.9 27% aes-192 14.5 16.7 15% aes-256 12.5 16.1 29% salsa20 39.9 58.1 46% sha1 55.7 60.7 9% sha256 24.6 31.7 29% sha512 7.8 30.4 290% sha3-224 5.77 27.5 377% sha3-256 5.45 26.0 377% sha3-384 4.18 20.0 378% sha3-512 2.90 13.9 379%
Public key operations:
name size sign/ms verify/ms rsa 1024 0.5014 ( +90%) 9.1323 (+101%) rsa 2048 0.0835 (+113%) 2.6942 (+116%) dsa 1024 0.9857 (+110%) 0.5026 (+111%) ecdsa 192 1.4312 ( +16%) 0.5530 ( +28%) ecdsa 224 1.0072 ( +18%) 0.4037 ( +31%) ecdsa 256 0.7846 ( +25%) 0.3094 ( +38%) ecdsa 384 0.3308 ( +31%) 0.1307 ( +49%) ecdsa 521 0.1823 ( +38%) 0.0719 ( +60%) ecdsa (openssl) 224 0.1842 0.1545 ecdsa (openssl) 384 0.0695 0.0590 ecdsa (openssl) 521 0.0261 0.0216
The improvements here are due to GMP work.
* Remaining tasks
The most important remaining task is documentation and release work. Plan and progress for the release is maintained at http://www.lysator.liu.se/~nisse/nettle/plan.html.