[OTR-dev] OTR version 4 Draft #2

[Sofia]

Hey!

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

Ok :)

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

As you said, this is for the ephemeral keys, where we don't follow the
RFC8032. Only for the generation of the long-term keys is that we use
the same method as the RCF8032, so the generation and the verification
of the signature are the same. If you see the section where the
long-term keys are generated, you will see that they are the same as the
RFC8032. But the ephemeral keys are generated differently, they don't
follow the RFC, and that is why that section don't mention it (in
contrast to the other sections, where it is mentioned).

Thanks! :)


On 3/25/18 11:35 AM, Danny van Heumen wrote:
> 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
> 
> 
> 

-- 
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/20180325/f0d58c95/attachment.sig>