[curves] Ed448-Goldilocks on NEON; point encoding
mike at shiftleft.org
Wed Mar 11 15:34:15 PDT 2015
First, embarrassing security announcement: while auditing the Goldilocks code I found a bug in the NEON code, where I used a signed shift instead of an unsigned shift, and also a saturation bug. Hooray for asm. These are fixed in the latest commits to git master. Somehow it passed all the tests before; the tests are now more rigorous in order to catch this sort of bug; furthermore I did a more careful analysis of the code (but not full formal) which suggests that the bug is fixed. It is possible that the bug is exploitable, so I encourage those who have forked the repo to patch. I’ve also deleted the non-“experimental” arch_neon to avoid maintaining two codebases for the same arch. The “experimental” code was much faster but not much more complicated, so I chose to keep that one.
It’s probably worth doing a more complete audit, cleanup and paredown before deploying the existing code on a wide scale. For example, for testing purposes the existing code has many point formats and scalarmul algorithms, but only a couple will be needed in production. Nick Wilson also suggested that the hash algorithm and RNG be decoupled. Work on this is ongoing in the decaf branch, and then afterwards in master.
Second, there is a question of point formats. Ed448-Goldilocks may end up in TLS or other standards alongside Curve25519, and so it will probably need a point format which matches *25519 point formats. The most likely option would be that for ECDH, we would use x-coordinates on an isogenous Montgomery curve with small A = 2-4*-39081. This allows reuse of the Curve25519 ladder code, though it loses the advantages of the fancy point formats in the original Goldilocks and in the Decaf branch. Perhaps one of those should be brought back for signatures, but again possibly not because parallel construction to Curve25519 is desirable.
Does anyone have a problem with this, or a suggestion, or an existing deployment of Goldilocks which could be affected?
More information about the Curves