On Wed, May 11, 2011 at 01:33:17PM -0400, Nick Mathewson wrote:

On Fri, May 6, 2011 at 11:12 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote: [...]

...

...

* I'm hoping to write this up as a proposed spec soon, unless Ian or somebody wants to give it a shot.

Please go ahead.

Here's a draft sketch that I've put into proposals/ideas in the the torspec repository. Please let me know what I've gotten wrong, what is over/under-engineered, and so on.

Filename: xxx-ntor-handshake.txt Title: Improved circuit-creation key exchange Author: Nick Mathewson Created: 11-May-2011 Status: Draft

This is an attempt to translate the proposed circuit handshake from "Anonymity and one-way authentication in key-exchange protocols" by Goldberg, Stebila, and Ustaoglu, into a Tor proposal format.

It assumes something like Robert Ransom's proposal draft is in place to provide an extended CREATE cell format that can indicate what type of handshake is in use.

Notation:

Let a|b be the concatenation of a with b.

Let H(x,t) be a tweakable hash function of output width H_LENGTH bytes.

Let t_keyid, t_mac, t_key, and t_verify be a set of arbitrarily-chosen tweaks for the hash function.

Let EXP(a,b) be a^b in some appropriate group G where the appropriate DH parameters hold. Let's say elements of this group, when represented as byte strings, are all G_LENGTH bytes long. Let's say we are using a generator g for this group.

Let PROTOID be a string designating this variant of the protocol.

Let KEYID be a collision-resistant (but not necessarily preimage-resistant) hash function on members of G, of output length H_LENGTH bytes.

Instantiation:

Let's call this PROTOID "ntor-curve25519-sha256-1"

Note that if the things you're hashing spill over a (56 mod 64) byte boundary, you pay extra. So it may behoove us to count bytes and see if PROTOID couldn't be a little shorter.

Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32. Set t_mac == PROTOID | ":mac" t_key1 == PROTOID | ":key1" t_key2 == PROTOID | ":verify" Set EXP(a,b) == curve25519(a,b), and g == 9 .

Careful! The arguments to curve25519 are (output, exponent, base). (Note the order; that confused me when we were coding up Sphinx.) Presumably you meant for EXP(a,b) to mean a^b, though.

Note that 9 does not have prime order in curve25519; it has order 8 times a prime. But if the client always ensures private keys are 0 mod 8 (as djb requires; see below), this problem is mostly elided.

Set KEYID(B) == B. (We don't need to use a hash function here, since our keys are already very short. It is trivially collision-resistant, since KEYID(A)====KEYID(B) iff A==B.)

Is "====" intentional?

Protocol:

Take a router with identity key digest ID.

As setup, the router generates a secret key b, and a public onion key

All "generates a secret key" operations should follow djb's recommendation, of course (fiddle with the 2 high bits, and clear the low 3 bits).

B = EXP(g,b). The router publishes B in its server descriptor.

To send a create cell, the client generates a keypair of x, X=EXP(g,y) and

X=EXP(g,x) presumably?

sends a CREATE cell with contents:

NODEID:     ID             -- H_LENGTH bytes
KEYID:      KEYID(B)       -- H_LENGTH bytes
CLIENT_PK:  X              -- G_LENGTH bytes

The server checks X,

What is "checks X" here? Since the server doesn't really care whether or not the crypto is good, this check can probably be elided.

generates a keypair of y, Y=EXP(g,y) and computes

secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
KEY_SEED = H(secret_input, t_key)
verify = H(secret_input, t_verify)

Depending on the lengths involved, the above may be doing some unnecessary work.

auth_input = verify | ID | B | Y | X | PROTOID | "Server"

The server sends a CREATED cell containing:

SERVER_PK:  Y                     -- G_LENGTH bytes
AUTH:       H(auth_input, t_mac)  -- H_LENGTH byets

The client then checks Y, and computes

Here, the check is more important. Ideally, one would check that Y \in G^* (which should have prime order, but doesn't here). But in curve25519, I think you can get away with something a bit cheaper. If Y isn't in G at all, but is on the twist curve, the AUTH verification below is certain to fail, so that's OK. If it's in G, but has low order (i.e. order dividing 8), then EXP(Y,x) will end up being the point at infinity, which would be bad. (Indeed, it would be pretty much the same problem that Tor had lo those many years ago.) So I think it's probably OK to check that EXP(Y,x), which you're computing anyway, is not the point at infinity. I don't remember offhand how curve25519 represents that point; it may be as simple as all-0s, but you should check.

Berkant and Doug, opinions on this?

secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
KEY_SEED = H(secret_input, t_key1)

Above, you used t_key, not t_key1, to create the KEY_SEED.

verify = H(secret_input, t_verify)
auth_input = verify | ID | B | Y | X | PROTOID | "Server"

The client verifies that AUTH == H(auth_input, t_mac).

Both parties now have a shared value for KEY_SEED. They expand this into the keys needed for the Tor relay protocol.

Key expansion:

Currently, the key expansion formula used by Tor here is

   K = SHA(K0 | [00]) | SHA(K0 | [01]) | SHH(K0 | [02]) | ...

SHH => SHA

   where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions.

Instead, let's have it be

   K = H(KEY_SEED, t_expand1) | H(KEY_SEED, t_expand2) | ...

where t_expand1..N are tweaks for the hash.

Krawczyk has a paper on how to do this crypto-correctly:

http://eprint.iacr.org/2010/264

See section 8 for an explanation of why the above is not ideal. Note that our "KEY_SEED" is approximately his "PRK", not his "SKM", as it's already been hashed. So if t_expand = PROTOID | ":expand", what's he's suggesting is

K = K_1 | K_2 | ... where K_1 = H(t_expand | 0, KEY_SEED) K_(i+1) = H(K_i | t_expand | i, KEY_SEED)

Note that KEY_SEED is used as the HMAC *key*, not the *message*.

Performance notes:

In Tor's current circuit creation handshake, the client does: One RSA public-key encryption A full DH handshake in Z_p A short AES encryption Five SHA1s for key expansion And the server does: One RSA private-key decryption A full DH handshake in Z_p A short AES decryption Five SHA1s for key expansion

While in the revised handshake, the client does: A full DH handshake A public-half of a DH handshake 3 H operations for the handshake 3 H operations for the key expansion and the server does: A full DH handshake A private-half of a DH handshake 3 H operations for the handshake 3 H operations for the key expansion

Note that each H operation is 2 underlying hashes.

- Ian

On Wed, May 11, 2011 at 03:42:30PM -0400, Nick Mathewson wrote:

RIght. If we can get away with something faster than HMAC_SHA256 here, I'd love to move to it. SHA3 is right around the corner, and most of the candidates seem to allow better constructions for "tweakability" than HMAC.

Would this make a difference, actually? Let's see. Looking at the numbers from my desktop and doing some back-of-the-envelope calculations.

I would expect the old handshake to take, total, about 3500 microseconds. (This is counting both client and server crypto.)

If we tried to do that with 2048-bit keys, it would take, total, about 14700 microseconds.

And I would expect the new handshake to take, total, something like 830 microseconds. That's more than 4x faster than the old one, and more than 17x faster than the old one using keys with equivalent security. (Nice!)

Of that 830 microseconds, I'd spend something like 3-5% doing SHA256 hashes. So it might not be worthwhile spending too much time optimizing the number of hashes here.

You're totally right. No sense stressing about how many hash blocks we're processing.

Remember also that if you have non-black-box access to the exponentiation routine, the server can compute X^y and X^b simultaneously. That will make a bigger difference in time, but is not really relevant from a spec-level standpoint.

- Ian

On Wed, May 11, 2011 at 08:01:28PM -0400, Nick Mathewson wrote:

On Wed, May 11, 2011 at 6:10 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote: [...]

...

Remember also that if you have non-black-box access to the exponentiation routine, the server can compute X^y and X^b simultaneously.  That will make a bigger difference in time, but is not really relevant from a spec-level standpoint.

Can you expand on how this would work? I didn't ask the first time you told me this, on the theory that I could figure it out if I thought about it for long enough, but several days later I still don't have it. All the ways I can think of are inefficient, non-constant-time, or both.

Use right-to-left exponentiation. This is totally off the top of my head.

def exp(base,expon): a = base mask = 1 res = 1 # Invariant: a = base^mask do: # Be a little cleverer about the if if you # care about constant-time; just save the output # somewhere useless if (expon & mask): # bitwise and res = res*a a *= a mask <<= 1 until (mask is larger than the maximum possible expon) return res

Then exp2(base, expon1, expon2) will be:

def exp2(base,expon1, expon2): a = base mask = 1 res1 = 1 res2 = 1 # Invariant: a = base^mask do: # Be a little cleverer about the if if you # care about constant-time; just save the output # somewhere useless if (expon1 & mask): # bitwise and res1 = res1*a if (expon2 & mask): # bitwise and res2 = res2*a a *= a mask <<= 1 until (mask is larger than the maximum possible expon) return (res1, res2)

The idea is that the squarings are common between the exps, and just the multiplications have to be done separately.

- Ian

On Thu, May 12, 2011 at 02:07:10PM +1000, Douglas Stebila wrote:

Implementing simultaneous exponentiation for curve25519 is going to be problematic, no matter how simple the algorithm, because Dan Bernstein's curve25519 main loop code is an unravelled assembly file. Modifying it directly to do simultaneous exponentiation will be a huge pain. I expect he actually wrote the code using his personal pseudo-assembly language called qhasm and then generated the .s Athlon assembly from that. We could email him to ask. Without it, and without spending decades decoding the assembly, his curve25519 code, even when run twice, will likely be faster than any simultaneous exponentiation code I write myself.

Nick, were you planning on using djb's qhasm code, or the C version (curve25519-donna)? (A quick look at the latter suggests it's doing left-to-right, so some changes would still be required, but not evil assembly ones.

In curve25519, every 32-byte string is a valid public key. The curve25519 webpage http://cr.yp.to/ecdh.html says that public key validation is not required for Diffie-Hellman key agreement. The webpage also lists several points that do not guarantee "contributory" behaviour, which the webpage suggests may be important in non-DH protocols. Contributory, as I know it, refers to when it is important that both parties contributed some randomness to the protocol. I would think that being contributory is a desirable property of key agreement, as it seems necessary for forward secrecy. Perhaps I'm misunderstanding this, however.

Every string is a valid public key, but half of them are on the twist curve instead of the normal curve. As discussed in the other part of the thread, this turns out not to matter because the twist curve has order 4*p_2.

Now that I think about it, I'm no longer positive that the client absolutely needs to check that Y has large order, since the adversary still won't know B^x = X^b.

So *either* the client should check this, *or* the directory authorities should check that submitted B's are in G^*. (Or both. I think both is best.)

That said, the client check is practically free; it's calculating EXP(Y,x) anyway, and it just needs to memcmp that with 32 bytes of 0.

The directory authorities should probably checks the B's anyway, just to be sane. They should all have order exactly p_1, so check that EXP(B,8) is not O, and check that EXP(B,p_1) is O.

- Ian

On Thu, May 12, 2011 at 8:12 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:

On Thu, May 12, 2011 at 07:13:58AM -0400, Ian Goldberg wrote:

...

The directory authorities should probably checks the B's anyway, just to be sane.  They should all have order exactly p_1, so check that EXP(B,8) is not O, and check that EXP(B,p_1) is O.

While we're talking about this, note that our paper says that the CA (the directory authority here) should check that the node submitting B actually does know b (the private key).  This could be as simple as the standard Fiat-Shamir NIZKPK.

Hm. What goes wrong in the protocol as I've written it if the authorities *don't* check this? As "simple" as you say Fiat-Shamir is, it would seem to add a few round trips to the server publication protocol.

So let's see. If we don't check that the server really knows the private key for B, then the server could either publish a junk value of B for which nobody knows the private key, or the server could publish somebody else's B. What would this hurt?

In the junk-B case, nobody knows b, so nobody can compute EXP(X,b) without knowing x, so the server cant generate a created cell that the client will accept.

In the stolen-B case, the attacker could try to do an MITM and pass the client's CREATE cell to the server that *does* know b. But that won't work in the variant I specified, since secret_input and auth_input both include an ID field based on the server's identity key. The client will only accept a CREATED cell whose AUTH field is based on the desired server's identity key, but the server that *does* know b will only generate a CREATED cell whose AUTH field is based on its own identity key.

So I think that adding the ID field to secret_input and auth_input solves the problem here. Am I missing something?

Quoting Ian Goldberg iang@cs.uwaterloo.ca:

On Thu, May 12, 2011 at 10:10:11AM -0400, Nick Mathewson wrote:

...

On Thu, May 12, 2011 at 8:12 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:

...

On Thu, May 12, 2011 at 07:13:58AM -0400, Ian Goldberg wrote:

...

The directory authorities should probably checks the B's anyway, just to be sane.  They should all have order exactly p_1, so check that EXP(B,8) is not O, and check that EXP(B,p_1) is O.

While we're talking about this, note that our paper says that the CA (the directory authority here) should check that the node submitting B actually does know b (the private key).  This could be as simple as the standard Fiat-Shamir NIZKPK.

Hm. What goes wrong in the protocol as I've written it if the authorities *don't* check this? As "simple" as you say Fiat-Shamir is, it would seem to add a few round trips to the server publication protocol.

No, Fiat-Shamir is the non-interactive (the NI in NIZKPK) version, so the node would just attach the proof to B when it submits it.

Node knows b and B = g^b Node picks random t \in Z/p_Z where p is the order of g Node computes c = H(g^t | B | ID | D) where ID is the node ID, D is any other data already sent or received in the server publication protocol Node computes r = t - c*b mod p Node sends (c,r) along with B to be registered. (256+256 bits)

The DA checks that c =?= H(g^r * B^c | B | ID | D) before accepting the registration.

You're right that it seems unlikely anything will go wrong in this particular protocol if B is unattested. But then you're getting back to lots of moving parts relying on the properties of other moving parts.

• Ian

Proof of possession of private key is indeed the more sound cryptographic thing to do, but for security it suffices to verify B lies on the correct group. Hijacking someone else's public key is not going to help the adversary to break ntor's security. That is what ntor's argument suggests. Given that is it really worth creating and maintaining the extra code to run a NIZKPK, when validation - a routine already required for the protocol, suffices?

This does not mean foolproof security, for example using B also as a signature key is likely to be problematic. However, such problems feel independent from whether you know or don't know "b". The only case where this would be issue is if two server use their respective Bs not only to establish connection with clients but between each other *and* the protocol used to establish server-to-server channel relies non-trivially on the assumption that your peer knows its own private key. Well in that case it's better to simply use a protocol that doesn't rely on proof of possession.

Last remark: I think in Ian's algorithm the DA must also check that B lies in the correct group. Otherwise, it's still possible to register invalid keys: for example with finite fields set B = 0 and it's easy to fool the verification step; a similar idea can be applied to elliptic curves (if validation is free then not on curve25519). I'm not familiar with how exactly Tor handles registration, but can come up with a few "reasonable" scenarios where an adversary can successfully impersonate servers by posting invalid static keys.

Berkant

On Thu, May 12, 2011 at 10:31:47AM -0400, Paul Syverson wrote:

Ian tells me that he has another paper dealing with these further issues as well, which he will check into being able to make available in tech report. So maybe there will be a further discussion and proposal on those issues.

It just got approved at eprint.

http://eprint.iacr.org/2011/308

Thanks,

- Ian

On Thu, May 12, 2011 at 8:56 AM, Adam Langley agl@imperialviolet.org wrote:

On Thu, May 12, 2011 at 7:13 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:

...

Nick, were you planning on using djb's qhasm code, or the C version (curve25519-donna)?  (A quick look at the latter suggests it's doing left-to-right, so some changes would still be required, but not evil assembly ones.

donna is much faster than the reference implementation on 64-bit, but much slower at 32-bit. The reference implementation was, indeed, derived from a qhasm source, although I don't have it. (donna was only intended to work on 64-bit systems, the 32-bit version is just for completeness.)

It's likely we'll want to use the fast reference implementation on 32-bit intel (It's assembly, right?), and donna on 64-bit platforms. We're going to need to find an answer for 32-bit PPC and ARM platforms, though. Any suggestions there?

On Thu, May 12, 2011 at 10:28 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:

Does "the 32-bit version is just for completeness" mean there _is_ a (slower?) 32-bit version in donna?  Or only for x86?

Yes, there's a 32-bit version: https://github.com/agl/curve25519-donna/blob/master/curve25519-donna.c with room for improvement.

Cheers

AGL

On Wed, May 11, 2011 at 1:19 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote:

On Wed, May 11, 2011 at 01:33:17PM -0400, Nick Mathewson wrote:

...

On Fri, May 6, 2011 at 11:12 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:  [...] [...]

...

Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32.   Set t_mac   == PROTOID | ":mac"       t_key1  == PROTOID | ":key1"       t_key2  == PROTOID | ":verify"   Set EXP(a,b) == curve25519(a,b), and g == 9 .

Careful!  The arguments to curve25519 are (output, exponent, base). (Note the order; that confused me when we were coding up Sphinx.) Presumably you meant for EXP(a,b) to mean a^b, though.

Note that 9 does not have prime order in curve25519; it has order 8 times a prime.  But if the client always ensures private keys are 0 mod 8 (as djb requires; see below), this problem is mostly elided.

More technically we have H=the curve25519 group, which is Z/pZxZ/8Z. Since private keys are 0 mod 8 they always annihilate the Z/8Z part. So the curve25519 group is in fact one that is cyclic with prime order when we generate private keys the right way. The problem is completely elided

...

Set KEYID(B) == B.  (We don't need to use a hash function here, since our      keys are already very short.  It is trivially collision-resistant, since      KEYID(A)====KEYID(B) iff A==B.)

Is "====" intentional?

...

Protocol:

Take a router with identity key digest ID.

As setup, the router generates a secret key b, and a public onion key

All "generates a secret key" operations should follow djb's recommendation, of course (fiddle with the 2 high bits, and clear the low 3 bits).

...

B = EXP(g,b).  The router publishes B in its server descriptor.

To send a create cell, the client generates a keypair of x, X=EXP(g,y) and

X=EXP(g,x) presumably?

...

sends a CREATE cell with contents:

NODEID:     ID             -- H_LENGTH bytes     KEYID:      KEYID(B)       -- H_LENGTH bytes     CLIENT_PK:  X              -- G_LENGTH bytes

The server checks X,

What is "checks X" here?  Since the server doesn't really care whether or not the crypto is good, this check can probably be elided.

In the GSO paper it is required that X be a non identity element. This is nontrivial given the curve25519 wire format, but is either squaring four times or checking that EXP(X,y) is not zero. when we calculate it.

...

generates a keypair of y, Y=EXP(g,y) and computes

secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID     KEY_SEED = H(secret_input, t_key)     verify = H(secret_input, t_verify)

Depending on the lengths involved, the above may be doing some unnecessary work.

Counting time! EXP(X,y), EXP(X,b), B, X and Y are all 32 bytes, so we have 160 bytes there. The nearest boundary above is 184, but PROTOID is 23 bytes and ID is 32 bytes (H_LENG), so we have a total of 215 bytes, wasting 33 bytes in the hash (This is assuming I interpreted 56 (mod 64) correctly). We could take a page out of DJB's book and make ID simply B to fix this.

...

auth_input = verify | ID | B | Y | X | PROTOID | "Server"

The server sends a CREATED cell containing:

SERVER_PK:  Y                     -- G_LENGTH bytes     AUTH:       H(auth_input, t_mac)  -- H_LENGTH byets

The client then checks Y, and computes

Here we want to count the bytes in the inner and outer hashes. The outer hash hashes 64 bytes: nothing we can do about that. But the inner one hashes the key length plus the message length, which here is 189 bytes, 5 bytes over a nice block boundary.

Here, the check is more important.  Ideally, one would check that Y \in G^* (which should have prime order, but doesn't here).  But in curve25519, I think you can get away with something a bit cheaper.  If Y isn't in G at all, but is on the twist curve, the AUTH verification below is certain to fail, so that's OK.  If it's in G, but has low order (i.e. order dividing 8), then EXP(Y,x) will end up being the point at infinity, which would be bad.  (Indeed, it would be pretty much the same problem that Tor had lo those many years ago.) So I think it's probably OK to check that EXP(Y,x), which you're computing anyway, is not the point at infinity.  I don't remember offhand how curve25519 represents that point; it may be as simple as all-0s, but you should check.

Checking EXP(Y,x) is non zero is correct, according to my reading of the Curve25519 paper and the GSO paper. Again, curve25519 takes place on a group that has structure Z/pZxZ/8Z, and valid private keys annihilate the Z/8Z component.

Berkant and Doug, opinions on this?

...

secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID     KEY_SEED = H(secret_input, t_key1)

Above, you used t_key, not t_key1, to create the KEY_SEED.

...

verify = H(secret_input, t_verify)     auth_input = verify | ID | B | Y | X | PROTOID | "Server"

The client verifies that AUTH == H(auth_input, t_mac).

Both parties now have a shared value for KEY_SEED.  They expand this into   the keys needed for the Tor relay protocol.

Here the counting is the same, as the same things are being HMACed.

...

Key expansion:

Currently, the key expansion formula used by Tor here is

K = SHA(K0 | [00]) | SHA(K0 | [01]) | SHH(K0 | [02]) | ...

SHH => SHA

...

where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions.

Instead, let's have it be

K = H(KEY_SEED, t_expand1) | H(KEY_SEED, t_expand2) | ...

where t_expand1..N are tweaks for the hash.

Krawczyk has a paper on how to do this crypto-correctly:

http://eprint.iacr.org/2010/264

See section 8 for an explanation of why the above is not ideal.  Note that our "KEY_SEED" is approximately his "PRK", not his "SKM", as it's already been hashed.  So if t_expand = PROTOID | ":expand", what's he's suggesting is

K = K_1 | K_2 | ... where K_1 = H(t_expand | 0, KEY_SEED) K_(i+1) = H(K_i | t_expand | i, KEY_SEED)

Note that KEY_SEED is used as the HMAC *key*, not the *message*.

...

Performance notes:

In Tor's current circuit creation handshake, the client does:      One RSA public-key encryption      A full DH handshake in Z_p      A short AES encryption      Five SHA1s for key expansion   And the server does:      One RSA private-key decryption      A full DH handshake in Z_p      A short AES decryption      Five SHA1s for key expansion

While in the revised handshake, the client does:      A full DH handshake      A public-half of a DH handshake      3 H operations for the handshake      3 H operations for the key expansion   and the server does:      A full DH handshake      A private-half of a DH handshake      3 H operations for the handshake      3 H operations for the key expansion

Note that each H operation is 2 underlying hashes.

- Ian _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

The GSO paper uses HMAC for only some of the operations that we are doing them on and use hash functions of double the length of the HMAC. Is this an important detail or an unimportant one?

Sincerely, Watson Ladd

Quoting Ian Goldberg iang@cs.uwaterloo.ca:

...

...

What is "checks X" here?  Since the server doesn't really care whether or not the crypto is good, this check can probably be elided.

In the GSO paper it is required that X be a non identity element. This is nontrivial given the curve25519 wire format, but is either squaring four times or checking that EXP(X,y) is not zero. when we calculate it.

The paper does indeed say that, but I'm questioning whether we actually needed that restriction. All it's checking is that the client isn't stupidly picking x=0. But the server doesn't really care, as it doesn't know who it's speaking with, anyway. The client could just as easily broadcast whatever x it chose. But yes, for symmetry, we could abort if EXP(X,y) is the identity element. (Which I just verified is indeed represented by all-0s.)

In theory, the check X \in G* does a bit more than selecting x=0, namely prevents invalid curve attacks. A server doesn't really care for the security of a single connection (the anonymous client may decide on purpose to reveal it's secrets and only the client would suffer, server and other clients will remain unaffected). If however, the server blindly accepts anything, then server would accept X' that lies on an invalid curve where X' has small prime order. As a result an adversary could potentially learn server's "b" - for comparison invalid curve attacks apply to MQV, HMQV with similar result (leaked static keys); I think it took a day for Alfred to verify the attack works on HMQV for a curve defined in FIPS 186-2. Having server's Y and the secret X'^y would complicate the attack a bit, but for sufficiently motivated adversary I suspect it will not be a barrier. As a result, if a client does establish a connection with the server, the adversary cannot compromise the security of that particular connection, but it would be trivial to fool the client to establish connection with the adversary thinking the connection is with an honest server.

In practice, I haven't read D. Bernsteins curve25519-20060209.pdf in detail. It claims (as pointed out by Doug) that there is "free key validation", which seems to imply invalid curves are not an issue. However, I'd still suggest to keep the check X \in G* if at least to serve as warning should there be a decision to move away from curve25519.

There may be an alternative form of validation: instead of computing X^y and X^b, the shared secret can be set as X^8y and X^8b. The results is verified to not match identity point (assuming X \in G of course). This will kill any multiples coming from the cofactor 8. If I recall correctly something along these lines is going on in SP800-56A for ECMQV.

- BU

On Mon, Jan 16, 2012 at 03:16:31PM -0500, Nick Mathewson wrote:

On Sun, Jan 15, 2012 at 4:15 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote: [...]

...

FYI: it's now been accepted to the Designs, Codes, and Cryptography jounral:

http://www.springerlink.com/content/nl86n0u547873001/

(The above cacr link has also been updated to the latest version.)

Congratulations, Ian! Any substantial changes since the CACR version?

No, just minor ones, and I don't think any involving the protocol itself, but just the text.

Have you been getting any feedback from other vectors? Any interesting/useful comments from reviewers?

Is it your sense that folks outside of PCs and this list are reviewing your work here and giving it the kind of attention we'd want before deploying it? And if not, is there anything we can do to help this design get more attention?

As far as I know, only the journal reviewers and this list (and we authors, of course) have looked at it. Not too surprising, of course, as Tor is probably the most obvious use case.

- Ian

On Mon, Jan 16, 2012 at 02:41:11PM -0600, Watson Ladd wrote:

...

As far as I know, only the journal reviewers and this list (and we authors, of course) have looked at it. Not too surprising, of course, as Tor is probably the most obvious use case.

Most SSL connections involve only one authenticated side.

Indeed, we talk about TLS in section 5.5 of the paper.

- Ian