Hey! > I have found all of the mentioned libraries, except for libgoldilocks.
This library is a simplification of libdecaf that only takes care of ed448-Golidlocks, while still internally using the decaf technique. > Additionally, I found a rust implementation for Ed25519. Well, for OTRv4 we use ed448-Goldilocks, because we want to achieve a security level of 224~ ;) We are planning on still working on the Golang implementation. > In the end, I got stuck on Mike's original source code due to the > amount of "extras": > * Some of the core code generated > * Decaf > * Pre-computed multiples (IIRC) > * constant-time operations > * Alternative representation, ... IIRC he used the Extended > representation at the time > * Not sure if Elligator was also in, in any case, I read about that > too. So libdecaf is not only for ed448-Goldilocks. It is multiple purpose elliptic curve library that internally uses the decaf technique for several curves, like Iso-25519, ed448-Goldilocks, 25519, p521.. You can check the multiple data for different curves on the library here: https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/generator/curve_data.py So, basically, what decaf means is to remove cofactors through point compression, or through quotients and isogenies. The internal representation of points in libdecaf is as "even" elements of a twisted Edwards curve with a=-1. Using this subgroup removes a factor of 2 from the "original" cofactor (note that for ed448-Goldilocks, this is 4). The remaining factor of 2 is removed with a quotient group: any two points which differ by an element of the 2- or 4-torsion subgroup are considered equal to each other. This is applied to several curves. There are precomputed tables and constant-time operations in the library. The latter is a must for any cryptographic library. You can read about the reasons for it over here: https://www.bearssl.org/constanttime.html Yes, there are several places with different coordinates. If I remember correctly, most of the time extended homogenous projective coordinates are used, of the form (X : Y : Z : T). Homogeneous projective coordinates, for example, are of the form (X : Y : Z), which correspond to the affine point (X/Z, Y/Z) with Z != 0. For extended homogeneous projective coordinates this will be (X : Y : Z : T), as said, where T = X^2 / Z. There is a very nice thesis from Hisil, around this: https://core.ac.uk/download/pdf/10898289.pdf Elligator is also included if there is the will to use it, and it is mostly used internally for tests, I think. What it does is basically make curve points indistinguishable from uniform random strings. Sorry, for the long rant ;) > In the end, I could not figure out which parts were relevant and given > that I'm new to EC in general, it was too much information for me to > confidently, reliably extract the critical core parts. Currently, I've > picked up the necessary basics and noticed in the mean time that a lot > of OTRv4 depends on RFC 8032 approach, i.s.o. of plain > Ed448Goldilocks. This also made it significant more approachable. Don't worry ;). Yes, we mostly used RFC8032 operations and encodings. We are still working on libgoldilocks, but this library contains only ed448-Goldilocks: https://github.com/otrv4/libgoldilocks I think the file: https://github.com/otrv4/libgoldilocks/blob/master/src/eddsa.c can clarify a lot of things. > The Ed448-Goldilocks parts will be in a separate repository. It may be > far from complete compared to Mike Hamburg's ref. implementation. But > it should contain most - if not all - of the parts that are not > strictly specific to OTRv4. (Ed448-Goldilocks basics and RFC 8032.) This sounds awesome! > So far I've managed to do addition, multiplication and EdDSA > operations. I believe private key generation is slightly differently > applied in OTRv4 (IIRC not sure right now but I remember kdf1 or so > being applied). It is the same: 1. You generate first a 57 bytes of cryptographically secure random data (this is 'sym_key'). 2. You hash those values using 'SHAKE-256(sym_key, 114)'. 3. You prune this buffer: the two least significant bits of the first byte are cleared, all eight bits of the last byte are cleared, and the highest bit of the second to last byte is set. 4. You interpret this as a scalar. > However, currently using Affine notation, i.s.o. one of the faster > defined representation as in hyperelliptic.org/EFD. (I started out > with Extended, but struggled with the math. I believe I know my > mistake now.) Additionally, the math currently relies on BigInteger, > so I'm not operating directly on byte[] yet. Mmm. > Like I said, a naive implementation. I'll drop a note on this list, > once I'm far enough ahead that it makes sense to open it up for > feedback. By then I hope people will jump in to give feedback or help > with optimizing the implementation. Ok, I'll love to see this. :) Thanks a lot! -- Sofía Celi (aka cherenkov) @claucece / @cherenkov_d EF74 1A5F 5692 E56F 14F6 243C 3992 6144 F89D 996F
signature.asc
Description: OpenPGP digital signature
_______________________________________________ OTR-dev mailing list [email protected] http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
