[OTR-dev] OTR version 4 Draft #2

[Danny van Heumen]

Hi,

On 03/25/2018 01:41 AM, Sofia wrote:
> 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.

Okay, good to know. This can be a good starting point.

>
>> 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.

Sure, that's clear to me. I was referring to it for the similarities it
has. Furthermore, the rust implementation allows me to look at it with a
different perspective. Anything that helps improve my understanding of
the ECC field is welcome.

>
>> 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

Okay, this is clear. I read up on the intentions of decaf from the
original paper. But skipped the details so far.
>
> 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.

Thanks for clarifying.

>
> 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

Don't worry, the importance of constant-time operations is absolutely
clear to me. That is also the reason I mentioned it. To make clear that
this (and its importance) is "on the radar".

>
> 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

This part is clear to me. So far I've been using hyperelliptic's
explicit formulas database.

>
> 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 ;)

Also clear.
The "rant" is fine. It helps touch on some parts.

Let's be clear, I intend to make the work as transparent as possible.
This includes mentioning things that I'm aware of that have not been
implemented yet. (Hence mentioning the constant-time operations.) First,
I will make things function,  then continue to improve on the other
requirements. The advantage then is that I have a reference to compare
against in case I fail to do a correct implementation.

>
>> 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.

I don't think so. Have a look at:
https://github.com/otrv4/otrv4/blame/master/otrv4.md#L956
That is, line 956 (currently), start of section "Generating ECDH and DH
keys". It lists the following code for generating an (short-lived) ECDH key:

~~~
generateECDH()
- pick a random value r (57 bytes)
- generate 'h' = KDF_1(0x01 || r, 57).
- prune 'h': 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.
- Interpret the buffer as the little-endian integer, forming the secret
scalar
's'.
- Securely delete 'r' and 'h'.
- return our_ecdh.public = G * s, our_ecdh.secret = s
~~~

Notice the second step: generating 'h' using KDF_1 and using an 58-byte
value.
Granted, this is not the long-lived Ed448 signing key, however it is an
ECDH key and generation slighly differs here.
I expect that this is intentional, but in any case, this is the
procedure I was referring to in my previous statement.


>
>> 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.

As I mentioned, there are multiple "future" improvements on the radar. ;-)

>
>
>> 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!
>
>

Danny



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