Opened 7 years ago

Closed 14 months ago

#8089 closed defect (wontfix)

Implement the handshake and key exchange as described in the paper

Reported by: vmon Owned by: zwol
Priority: Very High Milestone:
Component: Archived/Stegotorus Version:
Severity: Normal Keywords: archived-closed-2018-07-04
Cc: isis Actual Points:
Parent ID: #8099 Points:
Reviewer: Sponsor:

Description

The handshake protocol as described in the paper was never implemented. The program as-is uses "session keys" which are WRITTEN INTO THE SOURCE CODE.

Obviously this renders it totally unfit for deployment outside
laboratory test environments.

Child Tickets

Attachments (2)

find-curve-generators.cpp (4.7 KB) - added by rransom 7 years ago.
the quick kludged-up hack that I used to find 3 and 4
find-curve-generators-v2.cpp (5.0 KB) - added by rransom 7 years ago.
corrected version of the generator-finding program

Download all attachments as: .zip

Change History (14)

comment:1 Changed 7 years ago by rransom

You can use Curve25519 instead of Möller's binary curve -- 3 is a generator of the ‘twist’ group; 4 generates the main group.

For curve25519-donna, remove the part of curve25519_donna that masks the secret key bits. The scalar-multiplication loop in curve25519-donna (as of commit 6c6251ead7366d4499856c543a2de3e3dfadc4e4) will correctly compute arbitrary multiples of a point without further changes.

For all Curve25519 implementations, clear the high (2255) bit of the curve point before calling the scalar-multiply routine. curve25519-donna ignores that bit when ‘unpacking’ a coordinate-field element; DJB's software might not ignore it. Clearing the bit should work with all implementations.

Note that if you use any implementation other than curve25519-donna, you'll need to both hack out any exponent-munging and look closely at the main loop to make sure it doesn't assume that the exponent has had the bit-munging DJB specifies applied to it. (An implementation can save a small amount of time by skipping the differential addition in the last three iterations if the exponent is known to have its three low bits cleared.)

Changed 7 years ago by rransom

Attachment: find-curve-generators.cpp added

the quick kludged-up hack that I used to find 3 and 4

comment:2 Changed 7 years ago by zwol

I like the sound of that; curve25519 has known-fast, known-constant-time implementations, which is decidedly not the case for OpenSSL's generic EC code, and also has been subject to considerably more cryptanalysis than Möller's curve.

However, could you please explain why it is necessary to make the modifications you describe?

comment:3 in reply to:  2 Changed 7 years ago by rransom

Replying to zwol:

I like the sound of that; curve25519 has known-fast, known-constant-time implementations, which is decidedly not the case for OpenSSL's generic EC code, and also has been subject to considerably more cryptanalysis than Möller's curve.

However, could you please explain why it is necessary to make the modifications you describe?

DJB specified that Curve25519 private keys are 32-byte strings with bits 0, 1, 2, and 255 cleared and bit 254 set (see http://cr.yp.to/papers.html#curve25519 page 5). curve25519-donna enforces this in the same function which it exposes to perform the scalar multiplication.

The server should choose a private key of the form DJB specifies. However, if clients choose keys with the low bits cleared, their public keys will always be in a prime-order subgroup of the curve or its twist; this distribution is easily distinguishable from uniform (less than half of the coordinate-field elements have prime order on the curve or twist). This is why curve25519-donna cannot be used without modification (as of the last time that I looked at the upstream version).

There are two remaining issues -- remember that the high bit of the client's public key must be set to a uniform random bit (to remove an easy P=1/2 passive distinguisher), and the client's public key (including the padding bit) must be either included in the input to the KDF used to compute the symmetric key for the rest of the handshake message or covered by the MAC over the message (so that neither the curve point nor the padding bit can be modified by an active attacker).

comment:4 Changed 7 years ago by zwol

Thanks, that's very helpful. I may come back and bug you more when I get around to actually doing this. It sounds like we're going to wind up with something that's sufficiently different than Curve25519 that we should maybe come up with a new name for it.

comment:5 in reply to:  1 Changed 7 years ago by rransom

Parent ID: #8099

Replying to rransom:

You can use Curve25519 instead of Möller's binary curve -- 3 is a generator of the ‘twist’ group; 4 generates the main group.

By the way, someone else should check that there are points with these x coordinates which have the right order before they're baked into a protocol. (I'm quite sure that the approach I used (check that (n/2)*P is either the point of order 1 or the point of order 2, and that (n/4)*P isn't) is correct, but if it isn't correct, it's better to find out before the system is deployed.)

Changed 7 years ago by rransom

corrected version of the generator-finding program

comment:6 Changed 7 years ago by rransom

My program tested points' orders incorrectly. I've attached the corrected version; here is its output:

twist generator: 3
curve generator: 6

comment:7 Changed 5 years ago by vmon

DJB/Tanja told me that the handshake in the paper isn't secure, the secure replacement for the handshake in the paper, i.e. handshake totally indistinguishable from random based on ECC is Elligator:

http://elligator.cr.yp.to/

We are going to implement this instead.

comment:8 Changed 5 years ago by zwol

Yes, definitely use Elligator instead of the mess I made up. You may also want to replace AES-GCM with something that's more likely to run in constant time. AES-OCB might be usable now, depending where the funding is coming from (OCB is patented; there's a blanket license for open source use, but there's also a clause specifically forbidding use for military purposes, which could be read to extend to anything funded by military tentacles of the government). ChaCha/Poly1305 might also be a good choice. In general, I have come around to the opinion that I should have trusted DJB instead of NIST when I designed this thing.

comment:9 Changed 5 years ago by zwol

One of the reasons I have been making noises about UDP-based link protocols is that it would be nice not to need the special one-block cipher for Stegotorus block headers. If we can transmit the length in cleartext we can encrypt the rest of the block header using the same authenticated cipher as the payload. (If the length is encrypted, it can't be used to determine the offset to the MAC until it itself is authenticated, or you give the attacker a chosen-ciphertext oracle.) UDP would give us cleartext block length for free. On the other hand, doing that might make life harder for steg modules, which now have to conceal a decidedly-nonrandom length field somewhere.

comment:10 Changed 5 years ago by isis

Cc: isis added

comment:11 Changed 21 months ago by teor

Severity: Normal

Set all open tickets without a severity to "Normal"

comment:12 Changed 14 months ago by teor

Keywords: archived-closed-2018-07-04 added
Resolution: wontfix
Status: newclosed

Close all tickets in archived components

Note: See TracTickets for help on using tickets.