[curves] How close is Mike's Ed448 to being production-ready?

[Michael Hamburg]

> On Aug 29, 2014, at 10:47 AM, Nicholas Wilson <nicholas at nicholaswilson.me.uk> wrote:
> 
> Hi,
> 
> I'm trying to decide between curve41417 and Ed448-Goldilocks, for a
> product prototype using a high-security curve. (I can't see the
> product being released in the immediate-term, so there should be time
> for these curves to get a bit more review and for implementations to
> stabilise before we release, don't worry! Until this year, I was too
> cautious to jump onto the curve25519 bandwagon because it felt "too
> new".)
> 
> My preference is for Ed448-Goldilocks because of its strong curve
> choice, and because the code looks good already. Really all I'm after
> is a good curve, with a canonical and stable wire format for an ECDH
> exchange. For me, speed isn't too big an issue, because in a blunt
> sense customers who demand "maximum security", higher than curve25519,
> are already wasting cycles. Just a nice portable file, MIT-licensed,
> plain-C (like curve25519-donna), with a focus on correctness, would be
> good enough, and it could be optimized in a later release.

I really should write a ref version.

> It seems like most of the focus of the ECC community these days seems
> to benchmarks and speed comparisons!
> 
> Mike's "experimental" Ed448 code is actually already close to meeting
> my ease-of-compiling requirements, although I have made two minor
> changes:
> 1. Pull out the ChaCha and /dev/random code as an optional thing.
> People shipping crypto code already have their own random source, and
> it saves having to making a whole load of ifdefs for fetching Windows
> CryptoApi randomness, emscripten/WebCryto getRandomNumber…

Yeah, this is a good idea.

> 2. Avoid the requirement on SHA-512. All protocols already hash in the
> ECDH secret with nonces and protocol values, so we may as well make it
> easy for protocol designers to use the function their protocol uses
> (HKDF, in the protocol I'm working on)

Or another tack on the same thing: a better separation of the curve library from the protocol.  For example, exposing the scalarmul, point add and linear combo algorithms.

> (I also fixed a few typos I think Mike might want to merge in
> https://github.com/NWilson/ed448-goldilocks/commit/143f0e0b33fa54816d5e153d7512059e8d91a233)
> 
> My version is at https://github.com/NWilson/ed448-goldilocks/tree/nicks-changes

Thanks, I’ll add them.

> I have to admit, they might things faster, but all the CPU-specific
> stuff and __attributes__ scare me off! I have to get code running on 7
> architectures, 4 vendors' compilers, and 8 OSes before our company can
> ship it…

Yeah, the CPU-specific stuff is scary.  Sorry about that.  In addition to a garbage-free /ref/, I should also unify the existing copy-pasta as much as possible.  Eg functions that differ only in limb sizes, temporary names and calls to p448_bias().

The asm widemul intrinsics should be easy to remove.

Most of the __attributes__ are there to support static analysis or strong warnings, or just to be as strong as possible with the inliner, and can be removed.  Eg __attribute__((unused)) for header functions is there for -Wunused-function.

One of the less portable things in the code is the vector intrinsic stuff, which I think is specific to GCC and Clang.  It should be possible to just remove everything that depends on SSE, though.  If your compiler’s vectorizer actually works (unlike, say, clang’s), then this shouldn’t even be a big perf regression.

> So really, the question is, how close is Mike's Ed448 to being
> production-ready? I'd say the theory looks robust enough that a
> serious problem in Ed448 would be very bad news for a lot of Edwards
> curves…?

The curve is fine.  The code is reasonably solid and workable.  The protocols are just kind of cooked up examples.  The point format might change.  There really should be a condensed ref version.

The implementation of Elligator is likely to change, it’s just there for proof of concept and benchmarking, and maybe to support a PAKE.  You can tell this, because there’s no elligator_2s_encode to act as a left-inverse of elligator_2s_inject.

> But I'm not an expert! I've studied
> http://shiftleft.org/papers/fff/fff.pdf which is helpful which helps
> understanding some of the bits of Mike's code that are bit different
> to way some other Edwards curves are implemented.
> 
> One thing I like about Ed448 is that the Montgomery curve public
> format is elegant, so meets my requirement for a stable, canonical
> wire format for doing ECDH with. Is that right, or is that something
> that might be up for change in a future implementation of Ed448? What
> I mean is, suppose that towards the end of 2015 things look good for
> Ed448 and we ship it as an experimental feature, is there is a risk
> that if later on big popular crypto libraries add support for it,
> they'll be using a different serialisation format? We don't want our
> protocol to be stranded using an old format that needs conversions to
> the "preferred" serialisation!

Unfortunately, there isn’t a “preferred” serialization, and from discussions here and on CFRG, I’m concerned that there won’t be for a while.  Half the guys there want short Weierstrass for everything, and the other half don’t want to put new wine in old wineskins.

I like the Ed448 point format and don’t want to change it.  But there is definitely a risk that an “official” protocol using Ed448 would want a different point format.  The basic reason is that, so far as I know, the format used in Ed448 is specific to 3-mod-4 curves (it conveys information using the Jacobi symbol), and so it cannot be used with other curves such as Curve25519.  Also, Ed448 is the only published software which uses this format.

There’s a follow-on problem to this, too.  The Ed448 point format intentionally only represents the 2q-order subgroup (including the identity but not the point of order 2; and the *non*-2q’ subset of the twist if you don’t do the on-the-curve check).  This means that any protocol requiring cofactor removal can multiply by 2, so long as it’s checked that the point is indeed on the curve.  (There’s something about a Huff curve with group structure 2*2*q in here, but I don’t remember exactly how it works out.)  Anyway, if the point format changes and can represent the whole group, you’ll have to multiply by 4.

> Thanks for any comments on my rather-long question.
> 
> Nick

I hope I answered at least some of your questions.  Feel free to re-ask anything I missed; I’m still a little bit sick and out of it.

Cheers,
— Mike