[OTR-dev] OTR version 4 Draft #2

[Sofia]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://lists.cypherpunks.ca/pipermail/otr-dev/attachments/20180324/49ce1fc3/attachment.sig>