Opened 7 years ago

Closed 6 years ago

#7202 closed project (implemented)

Implement ntor handshake or its successor

Reported by: karsten Owned by:
Priority: Medium Milestone: Tor: 0.2.4.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: SponsorZ tor-relay
Cc: nickm, andrea, mikeperry Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

Proposal idea xxx-ntor-handshake.txt specifies the ntor handshake. Nick suggests implementing it or its successor. This depends on proposal 200 being implemented. Nick says that he and Andrea could work on this together.

Child Tickets

Attachments (1)

andrea_7199-7202_notes.txt (3.2 KB) - added by andrea 6 years ago.

Download all attachments as: .zip

Change History (34)

comment:1 Changed 7 years ago by nickm

Keywords: tor-relay added
Milestone: Tor: 0.2.4.x-final

comment:2 Changed 6 years ago by mikeperry

Cc: mikeperry added

comment:3 Changed 6 years ago by mikeperry

Hrmm. I am worried that ntor is even more asymmetric and DoS-vulnerable than what we have now. It seems as though ntor CREATE2 cells will cost a client roughly 0 computation if it wants to spam ntor CREATE2's at a node and ignore the results. The server, on the other hand, has to do a lot of exponentiations and HMACing.

Crazy idea: What if we included a hash of the CREATE2 cell's content, with some additional requirements on the hash to be verified server-side as proof-of-work. For example, we could require timestamp+nonce parameter additions (that are themselves hashed) such that the hash has a certain number of leading zeroes. Nodes could also verify that they don't see repeats of this hash value over some time period after which they would simply discard CREATE2 with old enough timestamps, without hashing anything.

This makes discarding replayed CREATE2s require zero crypto from the server, and can be made to be arbitrarily costly for the client (dare I say it: perhaps via a consensus parameter specifying the required hash prefix?)

comment:4 Changed 6 years ago by mikeperry

Doh. Clock-drift fingerprinting probably makes timestamps a bad thing to include.. unless they're on the resolution of "Here's the timestamp from my current consenus, +/- 2hrs" or we implement dir mirror timesources or something..

~4 hrs might also be a very long time to keep track of CREATE2 hashes too.. unless we only store shortest unique suffixes, and only when our onionskin queue is full, or something?

comment:5 Changed 6 years ago by nickm

Replying to mikeperry:

Hrmm. I am worried that ntor is even more asymmetric and DoS-vulnerable

How?

Suppose a DoS-ing attacker who takes the minimal effort and just generates random bits.

In the current case, a server has to respond to a randomly generated CREATE cell by doing a futile RSA1024 private-key operation and noticing that the padding's wrong after the RSA decrypt.

With ntor+curve25519, the server has to respond by doing two curve25519 operations and some hashing.

curve25519 is well more than twice as fast as private-key RSA1024 (an order of magnitude faster on my laptop), so this is *less* "asymmetric and DOS-vulnerable" than the current RSA approach.

What am I missing?

I agree that solving CREATE-based DoS matters, but it seems like this isn't a step backwards.

comment:6 Changed 6 years ago by nickm

Status: newneeds_review

This is implemented in my branch "ntor", which needs far more review and testing.

comment:7 Changed 6 years ago by mikeperry

I started checking that the unit tests match the ntor paper's page 16, and I noticed what looks like a serious issue: In onion_skin_ntor_server_handshake(), it seems you omit step 9, the identity-element check on X.

Oh wait, hah! I just checked the client side in onion_skin_ntor_client_handshake() and saw "XXXXX VERIFY Y IS NOT POINT AT INFINITY". So it looks like you're aware of it. But damn, we better add a matching comment in onion_skin_ntor_server_handshake() too. Probably also a log message or something until we fix the XXXX. Otherwise the old 2007 DH bug could sneak back in again :(.

I have a bunch more questions and comments, but this seemed pressing enough that it needed to be written down ASAP.

comment:8 Changed 6 years ago by rransom

If you are using Curve25519 with the point-reduced Montgomery-form representation specified in DJB's paper, there is no need to test public keys used in ntor for curve or subgroup membership.

comment:9 in reply to:  7 Changed 6 years ago by nickm

Replying to mikeperry:

I started checking that the unit tests match the ntor paper's page 16, and I noticed what looks like a serious issue: In onion_skin_ntor_server_handshake(), it seems you omit step 9, the identity-element check on X.

Oh wait, hah! I just checked the client side in onion_skin_ntor_client_handshake() and saw "XXXXX VERIFY Y IS NOT POINT AT INFINITY". So it looks like you're aware of it. But damn, we better add a matching comment in onion_skin_ntor_server_handshake() too. Probably also a log message or something until we fix the XXXX. Otherwise the old 2007 DH bug could sneak back in again :(.

I have a bunch more questions and comments, but this seemed pressing enough that it needed to be written down ASAP.

This was discussed a lot on the tor-dev thread, and I discussed it more with Ian, Douglas, and Brekant. It isn't necessary.

At Ian's suggestion, I added a set of tests to ensure that the output of the various EXP() operations wasn't the point at infinity. I'm not sure they're needed, but they oughtn't hurt assuming I did them in the non-stupid way. (Which I believe I did.)

comment:10 Changed 6 years ago by nickm

Reviewing aides: In addition to the implementation matching the paper, it should also match proposal 216 and the reference implementation in ntor_ref.py. It has been verified to interoperate with the latter.

comment:11 Changed 6 years ago by rransom

Status: needs_reviewneeds_revision

From commit af175dbe07d3fd712c8d7cf232d6715a55b8580d:

+  /* NOTE: If we ever use a curve other than curve25519, we'll need to include
+   * a check for Y's validity as a public key, or the handshake won't be
+   * secure. We MAY need to check other public keys too; see the ntor paper. */

If you ever use a point-reduced Montgomery-form curve over a prime-order coordinate field whose ‘quadratic twist’ has smooth order, you need to check X (the client's ephemeral public key) for validity (to avoid leaking b). Anyone who can feed a malformed Y to a client (a) won't learn bits of a long-term secret and (b) was already able to compute b*X, and thus could have impersonated the server using a properly generated Y anyway.

Some other curve representations (e.g. twisted Edwards form, as used in Ed25519) do require that both parties check all public keys for curve membership, but testing for subgroup membership (the really expensive test) can still be avoided by choosing private keys appropriately.

comment:12 Changed 6 years ago by nickm

Status: needs_revisionneeds_review

I've pushed an updated comment in 5c46faf8fafca744da7b7111b572a04e0e3dcb36; I have tried to make it accurate this time, but it's not unlikely I've screwed up some other term somewhere or other. Please let me know if so.

comment:13 Changed 6 years ago by mikeperry

What is the tor-dev post discussing the checks on X for this curve? (There are at least 4 or 5 threads on circuit handshakes with different subjects, and the only thread I see with ntor in the subject is not talking about ntor.)

Either way, I still think the source, the spec or both should explain why we can omit the checks on X and/or Y for our curve choice, and perhaps cite the curve25519 paper pages or relevant material if the answer is buried in there. In every other DH-esque protocol, omitting checks that gq = 1 and identity checks on keys is asking for critical vulnerability.. I do *not* think the new comment does this. It only says "beware of dragons on other curves!". It doesn't say why our curve is dragon-proof by default.

Speaking of gq == 1 check, I assume we also know this is true for our g=9 choice because of some deep curve25519 magic used to construct the subgroup?

Forgive me for still thinking of this problem in terms of Z_p, but if we write our protocols such that only people who already understand both ECC and the deep magic of our specific curve choice can verify their correctness, we're begging for mistakes to slip through unnoticed due to lack of eyeballs.

comment:14 Changed 6 years ago by nickm

Replying to mikeperry:

What is the tor-dev post discussing the checks on X for this curve? (There are at least 4 or 5 threads on circuit handshakes with different subjects, and the only thread I see with ntor in the subject is not talking about ntor.)

Try "New Paper by Goldberg, Stebila, and [UO]staoglu ...". (I misspelled Berkant's name in the subject originally.)

In particular see Ian's messages on that thread.

I'll ask Ian if he has a good writeup in one place for the spec; if anybody else has one, that would be keen too.

Either way, I still think the source, the spec or both should explain why we can omit the checks on X and/or Y for our curve choice, and perhaps cite the curve25519 paper pages or relevant material if the answer is buried in there. In every other DH-esque protocol, omitting checks that gq = 1 and identity checks on keys is asking for critical vulnerability.. I do *not* think the new comment does this. It only says "beware of dragons on other curves!". It doesn't say why our curve is dragon-proof by default.

Errr... it *does* check to see whether gpq == the identity element. (Or rather whether Gpq == the identity element.) That's what all of those tor_memeq(x, "\x00\x00\x00\...") things in af175dbe07d3fd71 are. If one of the inputs is the identity element, then the output will be too. Are you looking at the *final* version of the code, or at intermediate versions? It might be a good idea to make a local copy of the branch and do "git rebase -i --autosquash" on it.

*ALSO*, I'm pretty sure that attacks substituting in the identity element aren't what we're worried about here. Suppose that an adversary tries to do that, and we don't check for 0. So alice sends X, and the adversary substitutes X'==0.

Now Bob computes Xb == 0 and Xy==0, so his secret_input == 0, 0, ID, B, 0, Y, PROTOID. His verify is H_verify(secret_input). His auth_input is verify, ID, B, Y, 0, PROTOID, "Server". He sends back Y and H(auth_input).

Now the adversary is stuck! Alice is going to reject any modified message unless the adversary can provide an H(auth_input) based on Xb, not 0b. But the adversary doesn't know b--that's Bob's private key. So the attack fails.

If the adversary tries replacing Y with 0 but not X with 0, then the adversary still won't be able to make the client think the handshake worked.

So whatever attacks we're worried about here, the "substitute the identity element" attack isn't one.

Speaking of gq == 1 check, I assume we also know this is true for our g=9 choice because of some deep curve25519 magic used to construct the subgroup?

It's not our choice, it's djb's choice. His paper has more info.

Forgive me for still thinking of this problem in terms of Z_p, but if we write our protocols such that only people who already understand both ECC and the deep magic of our specific curve choice can verify their correctness, we're begging for mistakes to slip through unnoticed due to lack of eyeballs.

I sympathize; like I've said, I'm asking Ian if he has a writeup-for-regular-folks sitting around I could use.

comment:15 Changed 6 years ago by nickm

Ian just gave me permission to post this from personal email:

There are three ways a point can be "bad":

  1. point at infinity
  2. on the curve, but not in the prime-order subgroup
  3. not on the curve at all

If each side generates their private keys with the low 3 bits set to 0, then after any exponentiation, the component outside the prime-order subgroup will vanish, as both the group and the twist group are of the form Z_k x Z_p for a small k that's either 4 or 8 (group or twist), and a large prime p. So what's important is that the component in the prime subgroup is nontrivial. Checking for all-0 bytes after the exponentiation will cover that. So that deals with (1) and (2) above. [Well, it will allow points not in the subgroup as long as they have a non-zero component in the subgroup. But that's OK. It just means there are 4 or 8 ways to represent on the wire any particular point in the group.]

The other question is what do you do if you get a point that's actually on the twist curve, and not on the main curve at all (3). I'm pretty sure in that case (where one side is honest and generated points on the main curve, but the other side generated points on the twist), the dishonest party won't be able to generate the same secret as the honest party, as the honest party will take the dishonest party's public key to the power of something, yielding a point on the twist, while the dishonest party will get a public key on the main curve from the honest party, and won't be able to generate the corresponding point on the twist. So I think you can just ignore this problem entirely, as the handshake will fail.

comment:16 Changed 6 years ago by mikeperry

Thanks for the above. I'm reviewing the thread now. I just noticed this from Ian:

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.

It seems everybody agreed this was a good idea, but I don't see these checks in the ntor branch.

There was also some additional discussion about proof of possession of b, but everyone seemed to agree that was overkill (though it did remind me of #5968).

comment:17 Changed 6 years ago by mikeperry

Ok, I think I've finished looking over the unit test in comparison to the original paper. I think it all matches up now (aside from the dirauth checking issue), but I have one nagging, basic question: Why do we separately compute s.verify anymore now that we use rfc5869_sha256() to derive our key material? Couldn't s.secret_input go directly into the Hmac step and save us the verify hash, or is there additional future-proofing against hash weaknesses hidden in this step?

I am asking for my own education rather than out of any argument to change the protocol.

comment:18 in reply to:  16 ; Changed 6 years ago by nickm

Replying to mikeperry:

Thanks for the above. I'm reviewing the thread now. I just noticed this from Ian:

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.

It seems everybody agreed this was a good idea, but I don't see these checks in the ntor branch.

I didn't see it as a terribly great idea; it doesn't achieve anything security-wise. If a malicious router wanted to use a broken key in this way, it wouldn't actually be achieving anything other than letting anybody else authenticate as it. But a malicious router could also just publish or share its private key or session keys, and thereby achieve the same result without getting detected. This is useful to check for a particular set of bug in the routers, nothing more.

We can add another patch if need be, I guess. Can somebody tell me the right value for p_1, or do I have to dig it out myself.

There was also some additional discussion about proof of possession of b, but everyone seemed to agree that was overkill (though it did remind me of #5968).

comment:19 in reply to:  17 Changed 6 years ago by nickm

Replying to mikeperry:

Ok, I think I've finished looking over the unit test in comparison to the original paper. I think it all matches up now (aside from the dirauth checking issue), but I have one nagging, basic question: Why do we separately compute s.verify anymore now that we use rfc5869_sha256() to derive our key material? Couldn't s.secret_input go directly into the Hmac step and save us the verify hash, or is there additional future-proofing against hash weaknesses hidden in this step?

I believe it's meant to be future-proofing against hash weaknesses, bad kdfs, or stuff like that.

comment:20 in reply to:  18 Changed 6 years ago by rransom

Replying to nickm:

Replying to mikeperry:

Thanks for the above. I'm reviewing the thread now. I just noticed this from Ian:

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.

It seems everybody agreed this was a good idea, but I don't see these checks in the ntor branch.

I didn't see it as a terribly great idea; it doesn't achieve anything security-wise. If a malicious router wanted to use a broken key in this way, it wouldn't actually be achieving anything other than letting anybody else authenticate as it. But a malicious router could also just publish or share its private key or session keys, and thereby achieve the same result without getting detected. This is useful to check for a particular set of bug in the routers, nothing more.

We can add another patch if need be, I guess. Can somebody tell me the right value for p_1, or do I have to dig it out myself.

It's on page 8 of http://cr.yp.to/ecdh/curve25519-20060209.pdf, but you can't raise a point to a power divisible by p_1 without modifying the Curve25519 software. Fortunately, none of this key-checking crap is necessary, or even useful, for ntor.

comment:21 Changed 6 years ago by asn

Super quick and completely incomplete review:

  • Maybe in curve25519_public_key_isok() you could use tor_mem_is_zero()? OTOH, maybe you want to explicitly show how the point at infinity looks like.
  • You forgot to check the retval of crypto_rand() in one or two occasions.
  • What is the XXXX added in circuit_finish_handshake()?
  • Shouldn't parse_create2_payload() check that p_len is larger (or equal) than 4 before doing get_uint16() and p_len - 4?
  • It's kind of weird looking at parse_create2_payload() parsing EXTEND2 cells. Maybe parse_create2_payload() should be renamed, or at least specify that it's capable of parsing EXTEND2 in its documentation?

(The branch is huge and I haven't had time to review most of it. I hope to look more at it the following days.)

comment:22 Changed 6 years ago by nickm

I think I've got those issues covered now.

comment:23 Changed 6 years ago by mikeperry

I suppose upgrading INTRODUCE1 to use the ntor handshake will also require a proposal and a new cell format?

comment:24 in reply to:  23 ; Changed 6 years ago by rransom

Replying to mikeperry:

I suppose upgrading INTRODUCE1 to use the ntor handshake will also require a proposal and a new cell format?

The ntor protocol cannot be used for hidden service introduction.

comment:25 in reply to:  24 Changed 6 years ago by nickm

Replying to rransom:

Replying to mikeperry:

I suppose upgrading INTRODUCE1 to use the ntor handshake will also require a proposal and a new cell format?

The ntor protocol cannot be used for hidden service introduction.

Even if it could, there's no f'ing way we're changing those protocols without a proposal, this late in 0.2.4.

comment:26 Changed 6 years ago by andrea

By way of code review, I'm attaching my notes for this and 7199. A lot of the things that popped out to me turned out to be addressed in later patches, but they still raised questions I felt like I should know, so I'm mentioning them all here.

Changed 6 years ago by andrea

Attachment: andrea_7199-7202_notes.txt added

comment:27 Changed 6 years ago by rransom

The server looks up B in a constant-time map in order to prevent an attacker who is monitoring the server for side-channel leaks and cannot read a client's CREATE cell from determining whether the client is using the server's current or previous ntor public key. This attack is not especially plausible or likely, but defending against it is easy enough, and it's much better than Tor's usual practice of not trying to defend against any side-channel attacks.

Line 21 is almost entirely correct; the only incorrect statement in it is that things will break somehow if X is not included in the hash function's input. ntor is secure even if none of the public keys (long-term and ephemeral) are passed as inputs to the KDF, because if the server properly generates B and the client properly generates X, x*B is not known to the attacker. (A malicious server or client can completely break the protocol's security without generating B or X improperly by giving their secret keys to an attacker.)

(Elliptic-curve groups are usually written ‘additively’ -- the group operation is written as addition, and ‘exponentiation’ is written as multiplication (and referred to as ‘scalar multiplication’).)

The ‘point at infinity’ on a Montgomery-form elliptic curve is the group's identity element. There is absolutely no reason to check whether any public key or shared secret used in ntor is the point at infinity; read section 3 of the Curve25519 paper for why.

In Tor's current/old circuit-extension protocol, the server publishes an encryption public key (‘onion key’) K in its descriptor, the client sends E_K(g^x), the server replies with g^y, and both parties compute and use g^xy as their shared secret key. The ‘2007 DH bug’ was that clients would accept 0 or 1 or p-1 or p or p+1 as g^y, because they had no way to verify that g^y was sent by the server other than by assuming that (g^y)^x would be unknown to the attacker.

A good PRNG has two states: insufficiently seeded (i.e. not yet safe to use for any purpose), and sufficiently seeded that it can produce as many random bits as its caller needs. If your PRNG can be attacked by ‘consuming entropy’ from it, it is either insufficiently seeded or bad. If your PRNG is bad, it should be thrown away and replaced.

comment:28 Changed 6 years ago by nickm

In 6bd72b711dd21d34e08fe2299dfe0bc5b4a72f41, you implement a linear-time data structure. Do we expect this to be small or will you replace it later with something faster?

I expect it to have typical size of 1 or 2. In the future I could conceive of 3 or 4, but if we ever needed it for something big, we'd want to reimplement.

  • Okay, this is just the one I commented on under 316f22fe141624d2b0a6ac6b25c4f4ece6d5e10f

I'll assume the correctness of the curve25519 implementation in 8bd4d20a693dad9d3de743d8921d69762c50558e, since it's external and you've addressed portability issues in 9648ac43f1a1eb0ca200eed9177f41ee8324ca2a.

Yup. It's currently synchronized with Adam's code; I expect to keep it that way.

In 316f22fe141624d2b0a6ac6b25c4f4ece6d5e10f:

  • /* XXXX Does this possible early-return business threaten our security? */
    • The first early return for the check if the node_id matches seems harmless, since the only thing it depends on is something that's public anyway: the router's identity digest.
  • Why do we need the map for keypair_bB, though? Is the router's curve25519 public key not a once-per-router public value? If not, then this provides a timing-based test for whether a router has a particular key in its map. Does this leak anything dangerous?

A router's onion key is a one-per-router value as far as any client knows, but it servers want to rotate them sometimes. When they do this, they need the old key to keep working for a while.

  • 0a685804f407e06dac8bbf338f8e38aaedcbc33f makes it seem like it has only ever one or two entries: current and possibly previous keys - we need the map because the key is rotated and clients might not have seen the new key yet. Is this correct? Since the keys then appear in the consensus, I think this can't provide any information that wasn't already public.
  • But in 18ff5cb448181f2090349d89a3f1bc1a02e54d26, the early-exit is removed. Just being paranoid, or something amiss in my reasoning above?

I believe I'm just being paranoid there, for values of paranoia less like "everything is trying to get me" and more like "let's engineer this a little better than we think we need to, in case there's some circumstance I'm not thinking of that makes this less safe than it appears."

  • Just as an aside making sure I understand the protocol properly, the essential thing here is that secret_input contains the X the server saw *and* has gxy and gxb in it, so by the latter it could only be computed by someone who knows x (as Yx and Bx) or by someone who knows y and b (as Xy and Xb), so the client can check that the value of verify that it received was based on the same X that it sent and knows that it could only have been produced by the server? We need the server ephemeral keypair (y,Y) because without it, compromising b lets an attacker compute secret_input for past recorded traffic and decrypt it?

I think rransom's answer here is right; I think that most of the stuff in the secret_input/auth_input parts of the ntor protocol are there on the theory that you're not going to regret having more part of the protocol get checked.

For more info on the security of the protocol, you can check out

  • /* XXXXX VERIFY Y IS NOT POINT AT INFINITY */
    • Fix this?
    • Okay, af175dbe07d3fd712c8d7cf232d6715a55b8580d. Is the all-zeros comparison the representation of the point at infinity here? (Sorry, I'm just reading up on elliptic curves as groups here; the point at infinity is always the group

identity?)

  • What was the 2007 DH bug mikeperry mentions in the comments on #7202?

See rransom's answer here. As discussed above, I don't believe that checking for all zeros output or other checks is necessary for curve25519 either.

In 512ab64aa45e7cef83f1c54d7aeb3be69d22f48e;

  • Generating the server ephemeral key means an attacker can force us to consume entropy. What happens to the quality

of the entropy we would be using for legitimate clients in that case? Looks like crypto_strongest_rand() can't block to wait on real random bits, but I presume it's a strong enough PRNG that this isn't dangerous?

So, crypto_rand() just uses the OpenSSL RNG; crypto_strongest_rand() uses the OpenSSL RNG *and* the platform RNG. It's only used to generate the medium-term onion keys, not the ephemeral keys. So even if "consuming OS entropy" were something we worried about, we'd only be using it for the onion keys, which aren't made once-per-handshake unless I seriously screwed up.

The traditional rationale behind tracking how much entropy is "in" a cryptographic PRNG is to distinguish whether you're getting an information-theoretic kind of security (i.o.w, "short of a defect in the entropy source, you'd need sorcery to break this") or "merely" cryptographic security (i.o.w., "you could also break this if there's a defect in the PRNG algorithm.") But rransom is correct that the right answer to a suspect PRNG is pretty much always "Get a better PRNG", unless you're trying to use /dev/random to make a one-time-pad or something, which we aren't.

(It's not insane IMO for paranoid folks to re-seed their PRNGs periodically though, like we do, since we probably haven't heard the last word in cryptanalysis, and since most likely advances against currently good-looking PRNGs are likely to take the form of "given a whole lot of output from the same seed, the adversary can guess things about other output".)

Also, it *would be* a bit rude to read huge amounts of data from the OS RNG, since even if we don't believe in blocking on entropy, some other programs do, and it's a bit rude to punish users who want to use programs like that.

I'm okay with all the create_cell_t, etc. refactoring assuming this has been tested thoroughly.

I tested all the cases I could think of in a chutney network, and there are unit tests for the other cases.

This CREATE2-inside-CREATE business in 89e3dd8c3029e2319466fb47f33d31b76c870008 isn't in the proposal. Is it going to get into the spec properly?

It's in the last paragraph of "Integrating with the rest of Tor" in proposal 216.

comment:29 Changed 6 years ago by nickm

Just thought of another case and tested it. This is even more tested now. Wow, does chutney ever need more automation though.

comment:30 Changed 6 years ago by nickm

It's now in a "ntor-squashed" branch. It should be the same as "ntor" when I made it, but I'm taking a couple of fixup patches there from sebastian, which will lead to a ntor-resquashed or something.

comment:31 in reply to:  27 Changed 6 years ago by andrea

Replying to rransom:

The server looks up B in a constant-time map in order to prevent an attacker who is monitoring the server for side-channel leaks and cannot read a client's CREATE cell from determining whether the client is using the server's current or previous ntor public key. This attack is not especially plausible or likely, but defending against it is easy enough, and it's much better than Tor's usual practice of not trying to defend against any side-channel attacks.

Okay.

Line 21 is almost entirely correct; the only incorrect statement in it is that things will break somehow if X is not included in the hash function's input. ntor is secure even if none of the public keys (long-term and ephemeral) are passed as inputs to the KDF, because if the server properly generates B and the client properly generates X, x*B is not known to the attacker. (A malicious server or client can completely break the protocol's security without generating B or X improperly by giving their secret keys to an attacker.)

Okay, thanks.

(Elliptic-curve groups are usually written ‘additively’ -- the group operation is written as addition, and ‘exponentiation’ is written as multiplication (and referred to as ‘scalar multiplication’).)

Okay; I take it the need to refer to the addition/multiplication operations in the underlying field the curve is defined over distinctly does not create ambiguity in practice?

The ‘point at infinity’ on a Montgomery-form elliptic curve is the group's identity element. There is absolutely no reason to check whether any public key or shared secret used in ntor is the point at infinity; read section 3 of the Curve25519 paper for why.

Hmmm, okay. I'm not sure why the 'on a Montgomery-form elliptic curve' qualifier appears; does it denote a particular way of representing points (and so the group operation should not depend on it), or a particular subset of curves? Well, you seem to have much more background on this than I do, so I'll take your word for it and go read up some more and await enlightenment.

In Tor's current/old circuit-extension protocol, the server publishes an encryption public key (‘onion key’) K in its descriptor, the client sends E_K(g^x), the server replies with g^y, and both parties compute and use g^xy as their shared secret key. The ‘2007 DH bug’ was that clients would accept 0 or 1 or p-1 or p or p+1 as g^y, because they had no way to verify that g^y was sent by the server other than by assuming that (g^y)^x would be unknown to the attacker.

Okay, thanks.

A good PRNG has two states: insufficiently seeded (i.e. not yet safe to use for any purpose), and sufficiently seeded that it can produce as many random bits as its caller needs. If your PRNG can be attacked by ‘consuming entropy’ from it, it is either insufficiently seeded or bad. If your PRNG is bad, it should be thrown away and replaced.

Hmm.

comment:32 in reply to:  28 Changed 6 years ago by andrea

Replying to nickm:

I expect it to have typical size of 1 or 2. In the future I could conceive of 3 or 4, but if we ever needed it for something big, we'd want to reimplement.

Okay, no problem then. :)

Yup. It's currently synchronized with Adam's code; I expect to keep it that way.

Okay.

A router's onion key is a one-per-router value as far as any client knows, but it servers want to rotate them sometimes. When they do this, they need the old key to keep working for a while.

Okay.

I believe I'm just being paranoid there, for values of paranoia less like "everything is trying to get me" and more like "let's engineer this a little better than we think we need to, in case there's some circumstance I'm not thinking of that makes this less safe than it appears."

Right :)

I think rransom's answer here is right; I think that most of the stuff in the secret_input/auth_input parts of the ntor protocol are there on the theory that you're not going to regret having more part of the protocol get checked.

Okay, thanks. I'll find the paper and read it, I think.

See rransom's answer here. As discussed above, I don't believe that checking for all zeros output or other checks is necessary for curve25519 either.

Okay.

So, crypto_rand() just uses the OpenSSL RNG; crypto_strongest_rand() uses the OpenSSL RNG *and* the platform RNG. It's only used to generate the medium-term onion keys, not the ephemeral keys. So even if "consuming OS entropy" were something we worried about, we'd only be using it for the onion keys, which aren't made once-per-handshake unless I seriously screwed up.

Right, okay.

The traditional rationale behind tracking how much entropy is "in" a cryptographic PRNG is to distinguish whether you're getting an information-theoretic kind of security (i.o.w, "short of a defect in the entropy source, you'd need sorcery to break this") or "merely" cryptographic security (i.o.w., "you could also break this if there's a defect in the PRNG algorithm.") But rransom is correct that the right answer to a suspect PRNG is pretty much always "Get a better PRNG", unless you're trying to use /dev/random to make a one-time-pad or something, which we aren't.

Mmm.

Also, it *would be* a bit rude to read huge amounts of data from the OS RNG, since even if we don't believe in blocking on entropy, some other programs do, and it's a bit rude to punish users who want to use programs like that.

Yeah.

This CREATE2-inside-CREATE business in 89e3dd8c3029e2319466fb47f33d31b76c870008 isn't in the proposal. Is it going to get into the spec properly?

It's in the last paragraph of "Integrating with the rest of Tor" in proposal 216.

Okay, sorry.

comment:33 Changed 6 years ago by nickm

Resolution: implemented
Status: needs_reviewclosed

After a couple more reviews, merged!

Note: See TracTickets for help on using tickets.