Implement the handshake and key exchange as described in the paper
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.
Activity
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_donnathat 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 (2^255^) 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.)
the quick kludged-up hack that I used to find 3 and 4
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?
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).
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.
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.)
Trac:
Parent: N/A to #8099 (closed)corrected version of the generator-finding program
My program tested points' orders incorrectly. I've attached the corrected version; here is its output:
twist generator: 3 curve generator: 6- Author
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:
We are going to implement this instead.
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.
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.
Trac:
Cc: N/A to isis- Trac closed
closed