Hi all,
I think we can make next-generation onion (hidden) services (proposal #224) more resilient against certain kinds of DoS / client discovery attacks, by using a different blinded public key for each HSDir.
Attack Summary:
Once a malicious HSDir receives a descriptor, it can locate other HSDirs with that descriptor's blinded public key. It doesn't need to know the onion service address or decrypt the descriptor. Each descriptor contains the blinded public key:
The 'certificate' field contains a certificate in the format from proposal 220, with the short-term ed25519 descriptor-signing key signed by the blinded public key. It must contain a ed25519-signing-key extension containing the blinded public key.
(All quotes are from https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt )
This allows an attacker to target onion services for DoS, as long as they don't care which onion service they're targeting.
The effects of this attack could be: * if the malicious HSDir also stops serving the descriptor, it denies service to some onion service, * if the malicious HSDir continues to serve the descriptor, it becomes the only source of descriptors for some onion service.
I think this enables traffic confirmation attacks on some onion service or its clients (by bringing the sole descriptor source up and down). Client descriptor downloads could also be subject to traffic fingerprinting or slow (byte-at-a-time) delivery.
Attack Details:
Let's assume an attacker who: * doesn't know any onion service addresses * runs a malicious HSDir that collects blinded public keys * can check other HSDirs for descriptors based on blinded public keys * wants to DoS some onion services, but doesn't care which ones
This attacker then: 1. chooses an arbitrary blinded public key from their HSDir's collection 2. calculates possible HSDirs for the blinded public key 3. checks each of the possible HSDirs to see if they actually have a descriptor with that blinded public key 4. runs a DoS on each HSDir with that blinded public key (this is the resource-intensive step)
A refinement of the attack is to: A. find the HSDirs for each blinded public key uploaded to the malicious HSDir (steps 1-3) B. find the blinded public keys with the most vulnerable HSDirs (perhaps using the maximum consensus weight among all 5) C. DoS the blinded public keys with the most vulnerable HSDirs (step 4)
I think this is a plausible attack that could be run repeatedly until the attacker happens to hit a high-value onion service, or a high enough number of onion services. The targeted onion services would change blinded keys and HSDirs with the next shared random period, but they'd be down for up to 24 hours.
Mitigation Summary:
If each onion service uploads a descriptor with a different blinded public key to each HSDir, a malicious HSDir is unable to locate other HSDirs serving the same onion service.
Even with this change, an attacker who knows an onion service's address can still find all its HSDirs. They can set up a malicious HSDir and wait unit it happens to get chosen as the HSDir for that service. But this targeted attack requires more resources and time than the unknown target attack I describe above. The unknown target attack can also consider hundreds of blinded public keys, and target the ones with the weakest HSDirs. The targeted attack is unlikely to host a particular descriptor on a malicious HSDir, and also simultaneously find that all the other HSDirs for that descriptor are vulnerable to a DoS.
Alternative Mitigations:
The current keyblinding nonce is based on the period number and start time. This allows the blinded keys to be generated in advance. But the drawback is that the blinded key is the same for each HSDir.
There is a master keypair (sk, pk). Given the keypair and a nonce n, there is a derivation function that gives a new blinded keypair (sk_n, pk_n). This keypair can be used for signing. Given only the public key and the nonce, there is a function that gives pk_n. …
We propose the following scheme for key blinding, based on Ed25519.
(This is an ECC group, so remember that scalar multiplication is the trapdoor function, and it's defined in terms of iterated point addition. See the Ed25519 paper [Reference ED25519-REFS] for a fairly clear writeup.)
Let the basepoint be written as B. Assume B has prime order l, so lB=0. Let a master keypair be written as (a,A), where a is the private key and A is the public key (A=aB).
To derive the key for a nonce N and an optional secret s, compute the blinding factor h as H(A | s, B, N), and let:
private key for the period: a' = h a public key for the period: A' = h A = (ha)BGenerating a signature of M: given a deterministic random-looking r (see EdDSA paper), take R=rB, S=r+hash(R,A',M)ah mod l. Send signature (R,S) and public key A'.
Verifying the signature: Check whether SB = R+hash(R,A',M)A'.
(If the signature is valid, SB = (r + hash(R,A',M)ah)B = rB + (hash(R,A',M)ah)B = R + hash(R,A',M)A' ) … (To use this with Tor, set N = INT_8(period-number) | INT_8(Start of period in seconds since epoch).)
Mitigation #1:
Mitigation #1 generates a blinded key for every replica. (This means the attacker can only target a single replica of the descriptor, which they can likely do anyway, because the "spread_store" HSDirs are in order on the hash ring.)
But it looks like this can't be done in advance, because the number of replicas is a consensus parameter.
The following consensus parameters control where a hidden service descriptor is stored; hsdir_n_replicas = an integer in range [1,16] with default value 2. hsdir_spread_fetch = an integer in range [1,128] with default value 3. hsdir_spread_store = an integer in range [1,128] with default value 3. hsdir_spread_accept = an integer in range [1,128] with default value 8
But we can instead generate a blinded key for every replica mod default_hsdir_n_replicas.
Then, if the number of replicas in the consensus increases, the attack can only target 1/default_hsdir_n_replicas of the replicas. It simply doesn't know where the other replicas are, because they have different blinded keys.
The spec change for Mitigation #1 would look like:
(To use this with Tor, create a key, blinded_public_key(advance_replicanum) for each N = INT_8(period-number) | INT_8(Start of period in seconds since epoch) | INT_8(advance_replicanum), where advance_replicanum takes every value from 1 to default_hsdir_n_replicas. Each key is used for the replicas where replicanum mod default_hsdir_n_replicas is equal to advance_replicanum.)
The blinded key is then used by both the service and clients to determine the descriptor's hashring index:
To determine where a given hidden service descriptor will be stored in a given period, after the blinded public key for that period is derived, the uploading or downloading party calculate for replicanum in 1...hsdir_n_replicas: hs_index(replicanum) = H("store-at-idx" | blinded_public_key(replicanum mod default_hsdir_n_replicas) | INT_8(replicanum) | INT_8(periodnum) )
For Mitigation #1, including advance_replicanum in the keyblinding does NOT remove the need for replicanum in the hs_index(replicanum) hash. (advance_replicanum could be lower than replicanum if the hsdir_n_replicas consensus parameter is increased from the default.)
There's also a slight clarification to the spread upload wording:
Finally, for replicanum in 1...hsdir_n_replicas, the hidden service host uploads descriptors for the corresponding replica's blinded signing key to the first hsdir_spread_store nodes whose indices immediately follow hs_index(replicanum).
In summary, by creating a blinded public key for each replica, Mitigation #1 restricts the attack described to a single descriptor replica per malicious HSDir. This significantly increases the resources or knowledge required for the attack.
Mitigation #2:
Mitigation #2 generates a blinded key for every spread. (This means the attacker can only target a single spread for the descriptor.)
Spread is specified like this in the existing proposal:
Finally, for replicanum in 1...hsdir_n_replicas, the hidden service host uploads descriptors to the first hsdir_spread_store nodes whose indices immediately follow hs_index(replicanum).
A similar process applies for advance generation of blinded public keys:
(To use this with Tor, create a key blinded_public_key(advance_spreadnum) for each N = INT_8(period-number) | INT_8(Start of period in seconds since epoch) | INT_8(advance_spreadnum), where advance_spreadnum takes every value from 1 to default_hsdir_spread_store. Each key is used for the spreads where spreadnum mod default_hsdir_spread_store is equal to advance_spreadnum.)
Mitigation #2 changes the way the spread indexes are positioned on the hashring. Because the blinded key for each advance_spreadnum is different, the spreads are distributed around the hashring, rather than appearing on it sequentially. To maintain this distribution if the consensus value of hsdir_spread_store is increased, we have two options: * spreadnum can be included in the descriptor index hash (Mitigation #2A), or * the spread position need only be incremented once for each advance_spreadnum spreads (Mitigation #2B).
Mitigation #2A:
spreadnum can be included in the descriptor index hash:
To determine where a given hidden service descriptor will be stored in a given period, after the blinded public key for that period is derived, the uploading or downloading party calculate for replicanum in 1...hsdir_n_replicas: for spreadnum in 1...hsdir_spread_store: hs_index(replicanum, spreadnum) = H("store-at-idx" | blinded_public_key(spreadnum mod default_hsdir_spread_store) | INT_8(replicanum) | INT_8(spreadnum) | INT_8(periodnum) )
There's also a slight clarification to the spread upload wording:
Finally, for replicanum in 1...hsdir_n_replicas, the hidden service host uploads descriptors for the corresponding spread's blinded signing key to the first node whose index immediately follows hs_index(replicanum, spreadnum). This uploads to hsdir_spread_store nodes per replica.
Mitigation #2B:
The spread position need only be incremented once for each advance_spreadnum spreads:
Finally, for replicanum in 1...hsdir_n_replicas, the hidden service host uploads descriptors to hsdir_spread_store nodes per replica as follows: the descriptor for the corresponding spreadnum's blinded signing key is uploaded to the first node whose index immediately follows hs_index(replicanum, spreadnum). If any spreads would upload to the same node, they instead upload to the second and subsequent nodes whose indices immediately follows the hs_index.
But spreadnum is NOT included in the descriptor index hash:
To determine where a given hidden service descriptor will be stored in a given period, after the blinded public key for that period is derived, the uploading or downloading party calculate for replicanum in 1...hsdir_n_replicas: hs_index(replicanum, spreadnum) = H("store-at-idx" | blinded_public_key(spreadnum mod default_hsdir_spread_store) | INT_8(replicanum) | INT_8(periodnum) )
In summary, by creating a blinded public key for each replica, Mitigation #2 (both variants) restricts the attack described to a single descriptor spread per malicious HSDir. This significantly increases the resources or knowledge required for the attack.
Mitigation #3:
Alternately, we could double blind each public key: once when it is generated from the master key in advance, and again just before it is uploaded to the HSDir.
This double-blinding should use two nonces, P and Q: * P is the advance-blinding nonce based on the period * Q is the post-blinding nonce based on the replica and/or spread (I considered and rejected a design where Q is based on the fingerprint of the HSDir. This would lead to blinding with an externally-supplied fingerprint, potentially chosen by an attacker to reveal information on blinding.)
The blinding would look something like this, where H(Q, H(P, …)) replaces H(N, …):
There is a master keypair (sk, pk). Given the keypair and a nonce n, there is a derivation function that gives a new blinded keypair (sk_n, pk_n). This keypair can be used for signing. Given only the public key and the nonce, there is a function that gives pk_n. …
We propose the following scheme for key blinding, based on Ed25519.
(This is an ECC group, so remember that scalar multiplication is the trapdoor function, and it's defined in terms of iterated point addition. See the Ed25519 paper [Reference ED25519-REFS] for a fairly clear writeup.)
Let the basepoint be written as B. Assume B has prime order l, so lB=0. Let a master keypair be written as (a,A), where a is the private key and A is the public key (A=aB). To derive the key for a advance-blinding nonce P, an optional secret s, and a post-blinding nonce Q: compute the advance-blinding factor h as H(A | s, B, P), and let:
advance-blinded private key for the period: a' = h a advance-blinded public key for the period: A' = h A = (ha)B
compute the post-blinding factor j as H(A' | 0, B, Q), and let:
post-blinded private key for the period: a'' = j a' = j (ha) post-blinded public key for the period: A'' = j A' = j ((ha)B)
Generating a signature of M: given a deterministic random-looking r (see EdDSA paper), take R=rB, S=r+hash(R,A'',M)ahj mod l. Send signature (R,S) and public key A''.
Verifying the signature: Check whether SB = R+hash(R,A'',M)A''.
(If the signature is valid, SB = (r + hash(R,A'',M)ahj)B = rB + (hash(R,A'',M)ahj)B = R + hash(R,A'',M)A'' ) ... (To use this with Tor, set P = INT_8(period-number) | INT_8(Start of period in seconds since epoch) and Q = INT_8(replicanum) and/or INT_8(spreadnum).
Other Considerations:
Combining Mitigations:
Mitigations #1 and #2 (either variant) can be combined, but this means generating 6 blinded keys per period, rather than 1. I don't think the extra benefit gained from implementing both outweighs the complexity involved.
Issue with Per-Spread Keys:
One drawback of Mitigations #2 and #3 (different blinding keys for each spread) is that the client may need to request multiple blinded keys from each HSDir due to relays dropping out of the hash ring.
For example: 1. An onion service uploads descriptors with keys A, B, C to spread servers a, b, c respectively 2. Spread server a goes down 3. the client wants the descriptor for the onion service, and tries spread servers b, c, d The client doesn't know how many servers have gone down. Therefore, it will need to ask for A, B, C from the first server (actually b, which has B); B, C from the second server (actually c, which has C); and C from the third server (actually d, which has nothing).
I don't like the extra load involved in this, and I wonder about the potential for information leaks to either the HSDir, or an observer of the client's connection. (For example, each of the traffic patterns above is distinct, so an observer of the client could tell which spread number it used for the descriptor.)
Security Proofs:
The modified security proof in Mitigation #3 would need to check out for me to be comfortable with this option.
Conclusion:
Can we consider Mitigation #1: creating a different blinded public key for each replica? This would double the number of keys we generate in advance, one for each replica.
Alternately, we could use Mitigation #3: double-blinding each key with the period in advance, then the replica number just before upload. But we'd need to check the modified security proof carefully.
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B
teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
Hi All,
prop224 salts the encrypted portion of each descriptor with a random value. If we use the same "salt" for every replica/spread, the encrypted portions of the descriptor will be identical. (In the spec, it looks like the same encrypted descriptor / salt is used for each replica / spread, but it's not explicit.)
I can't think of an attack based on matching up the encrypted portions of descriptors. But I like the idea of making the blinded key and encrypted portion of every descriptor different, so there's no way to tell if they're from the same service or not.
Then there would be no way of telling whether replica/spread descriptors were from the same hidden service, which I think is a useful property.
(Unless you can decrypt them, and therefore you'd likely know the key, or could match up the introduction points. Even then, the service might be using a load balancing technique that puts different intro points in each descriptor, like OnionBalance; or posting multiple descriptors with the same key, like the Tor: Hidden Service Scaling paper.[0])
The relevant portion of the proposal is:
The encrypted part of the hidden service descriptor is encrypted and authenticated with symmetric keys generated as follows:
salt = 16 random bytes secret_input = blinded_public_key | subcredential | INT_4(revision_counter) keys = KDF(secret_input, salt, "hsdir-encrypted-data", S_KEY_LEN + S_IV_LEN + MAC_KEY_LEN) SECRET_KEY = first S_KEY_LEN bytes of keys SECRET_IV = next S_IV_LEN bytes of keys MAC_KEY = last MAC_KEY_LEN bytes of keysThe encrypted data has the format:
SALT (random bytes from above) [16 bytes] ENCRYPTED The plaintext encrypted with S [variable] MAC MAC of both above fields [32 bytes]
Tim
Tim Wilson-Brown (teor)
[0]: https://www.benthamsgaze.org/wp-content/uploads/2015/11/sucu-torscaling.pdf
On 7 Nov 2015, at 07:22, teor teor2345@gmail.com wrote:
Hi all,
I think we can make next-generation onion (hidden) services (proposal #224) more resilient against certain kinds of DoS / client discovery attacks, by using a different blinded public key for each HSDir.
Attack Summary:
Once a malicious HSDir receives a descriptor, it can locate other HSDirs with that descriptor's blinded public key. It doesn't need to know the onion service address or decrypt the descriptor. Each descriptor contains the blinded public key:
...
Tim Wilson-Brown - teor teor2345@gmail.com writes:
Hi All,
prop224 salts the encrypted portion of each descriptor with a random value. If we use the same "salt" for every replica/spread, the encrypted portions of the descriptor will be identical. (In the spec, it looks like the same encrypted descriptor / salt is used for each replica / spread, but it's not explicit.)
I can't think of an attack based on matching up the encrypted portions of descriptors. But I like the idea of making the blinded key and encrypted portion of every descriptor different, so there's no way to tell if they're from the same service or not.
Then there would be no way of telling whether replica/spread descriptors were from the same hidden service, which I think is a useful property.
You are suggesting we should use a different salt for each descriptor we push?
Sounds reasonable, with a small cost on implementation complexity since now we will have to generate N different descriptors and push them properly to the right HSDirs. Plausible.
If you send a patch for the proposal, I will merge!
Thanks!
(Unless you can decrypt them, and therefore you'd likely know the key, or could match up the introduction points. Even then, the service might be using a load balancing technique that puts different intro points in each descriptor, like OnionBalance; or posting multiple descriptors with the same key, like the Tor: Hidden Service Scaling paper.[0])
The relevant portion of the proposal is:
The encrypted part of the hidden service descriptor is encrypted and authenticated with symmetric keys generated as follows:
salt = 16 random bytes secret_input = blinded_public_key | subcredential | INT_4(revision_counter) keys = KDF(secret_input, salt, "hsdir-encrypted-data", S_KEY_LEN + S_IV_LEN + MAC_KEY_LEN) SECRET_KEY = first S_KEY_LEN bytes of keys SECRET_IV = next S_IV_LEN bytes of keys MAC_KEY = last MAC_KEY_LEN bytes of keysThe encrypted data has the format:
SALT (random bytes from above) [16 bytes] ENCRYPTED The plaintext encrypted with S [variable] MAC MAC of both above fields [32 bytes]Tim
Tim Wilson-Brown (teor)
On 7 Nov 2015, at 07:22, teor teor2345@gmail.com wrote:
Hi all,
I think we can make next-generation onion (hidden) services (proposal #224) more resilient against certain kinds of DoS / client discovery attacks, by using a different blinded public key for each HSDir.
Attack Summary:
Once a malicious HSDir receives a descriptor, it can locate other HSDirs with that descriptor's blinded public key. It doesn't need to know the onion service address or decrypt the descriptor. Each descriptor contains the blinded public key:
...
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Hi George,
Please see below for a spec patch covering this email thread and various issues discussed on Trac and tor-dev@
On 20 Nov 2015, at 00:13, George Kadianakis desnacked@riseup.net wrote:
Tim Wilson-Brown - teor <teor2345@gmail.com mailto:teor2345@gmail.com> writes:
Hi All,
prop224 salts the encrypted portion of each descriptor with a random value. If we use the same "salt" for every replica/spread, the encrypted portions of the descriptor will be identical. (In the spec, it looks like the same encrypted descriptor / salt is used for each replica / spread, but it's not explicit.)
I can't think of an attack based on matching up the encrypted portions of descriptors. But I like the idea of making the blinded key and encrypted portion of every descriptor different, so there's no way to tell if they're from the same service or not.
Then there would be no way of telling whether replica/spread descriptors were from the same hidden service, which I think is a useful property.
You are suggesting we should use a different salt for each descriptor we push?
Sounds reasonable, with a small cost on implementation complexity since now we will have to generate N different descriptors and push them properly to the right HSDirs. Plausible.
If you send a patch for the proposal, I will merge!
I've created a branch rend-ng-descriptors on https://github.com/teor2345/torspec.git
It addresses the issues I've mentioned in this email trail, tickets #17239 and #17242, and the raw random value leakage issue mentioned by Jacob in [0].
A full list of changes is: * add a comment that prop252 wants to add extend-info to the descriptor (perhaps it will need more padding) * add distinguishing values to every hash * hash raw random bytes before use * deal with replica hashing collisions * randomise revision-counter to avoid information leaks * use a different salt for each replica and upload * avoid replicas with the same blinded key
They are in approximate order of complexity / impact.
Please feel free to ask me questions about any of these changes. (And please to cherry-pick as needed.)
Tim
[0]: https://lists.torproject.org/pipermail/tor-dev/2015-November/009954.html
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B
teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
On 20 Nov 2015, at 12:21, Tim Wilson-Brown - teor teor2345@gmail.com wrote:
...
A full list of changes is: ...
- randomise revision-counter to avoid information leaks
…
I just pushed a fixup to this commit: the revision-counter requires a minimum increment of 1 (not 0).
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B
teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
-
George Kadianakis -
teor -
Tim Wilson-Brown - teor