Here's a proposal Nick Mathewson and I just wrote for ticket #11157.
--- Begin proposal body --- Filename: xxx-consensus-hash-chaining.txt Title: Consensus Hash Chaining Author: Nick Mathewson, Andrea Shepard Created: 06-Jan-2015 Status: Draft
1. Introduction and overview
To avoid some categories of attacks against directory authorities and their keys, it would be handy to have an explicit hash chain in consensuses.
2. Directory authority operation
We add the following field to votes and consensuses:
previous-consensus ISOTIME [SP HashName "=" Base16]* NL
where HashName is any keyword.
This field may occur any number of times.
The date in a previous-consensus line in a vote is the valid-after date of the consensus the line refers to. The hash should be computed over the signed portion of the consensus document. A directory authority should include a previous-consensus line for a consensus using all hashes it supports for all consensuses it knows which are still valid, together with the two most recently expired ones.
When this proposal is implemented, a new consensus method should be allocated for adding previous-consensus lines to the consensus.
A previous-consensus line is included in the consensus if and only if a line with that date was listed by more than half of the authorities whose votes are under consideration. A hash is included in that line if the hash was listed by more than half of the authorities whose votes are under consideration. Hashes are sorted lexically with a line by hashname; dates are sorted in temporal order.
If, when computing a consensus, the authorities find that any previous-consensus line is *incompatible* with another, they must issue a loud warning. Two lines are incompatible if they have the same ISOTIME, but different values for the the same HashName.
The hash "sha256" is mandatory.
3. Client and cache operation
All parties receiving consensus documents should validate previous-consensus lines, and complain loudly if a hash fails to match.
When a party receives a consensus document, it SHOULD check all previous-consensus lines against any previous consensuses it has retained, and if a hash fails to match it SHOULD warn loudly in the log mentioning the specific hashes and valid-after times in question, and store both the new consensus containing the mismatching hashes and the old consensus being checked for later analysis. An option SHOULD be provided to disable operation as a client or as a hidden service if this occurs.
All relying parties SHOULD by default retain all valid consensuses they download plus two; but see "Security considerations" below.
If a hash is not mismatched, the relying party may nonetheless be unable to validate the chain: either because there is a gap in the chain itself, or because the relying party does not have any of the consensuses that the latest consensus mentions. If this happens, the relying party should log a warning stating the specific cause, the hashes and valid-after time of both the consensus containing the unverifiable previous-consensus line and the hashes and valid-after time of the line for each such line, and retain a copy of the consensus document in question. A relying party MAY provide an option to disable operation as a client or hidden service in this event, but due to the risk that breaks in the chain may occur accidentally, such an option SHOULD be disabled by default if provided.
If a relying party starts up and finds only very old consensuses such that no previous-consensus lines can be verified, it should log a notice of the gap along the lines of "consensus (date, hash) is quite new. Can't chain back to old consensus (date, hash)". If it has no old consensuses at all, it should log an info-level message of the form "we got consensus (date, hash). We haven't got any older consensuses, so we won't do any hash chain verification"
4. Security Considerations:
* Retaining consensus documents on clients might leak information about when the client was active if a disk is later stolen or the client compromised. This should be documented somewhere and an option to disable (but thereby also disable verifying previous-consensus hashes) should be provided.
* Clients MAY offer the option to retain previous consensuses in memory only to allow for validation without the potential disk leak. --- End proposal body ---
On Tue, Jan 6, 2015 at 12:51 PM, Andrea Shepard andrea@torproject.org wrote:
Here's a proposal Nick Mathewson and I just wrote for ticket #11157.
Thanks for writing this up! Added as proposal 239.
06.01.2015, 18:51 Andrea Shepard:
Here's a proposal Nick Mathewson and I just wrote for ticket #11157.
[...]
- Introduction and overview
To avoid some categories of attacks against directory authorities and their keys, it would be handy to have an explicit hash chain in consensuses.
- Directory authority operation
We add the following field to votes and consensuses:
previous-consensus ISOTIME [SP HashName "=" Base16]* NLwhere HashName is any keyword.
[...]
To quote Nick Mathewson "I forget what else this was supposed to be good for." (see the ticket)
I fail to see what kind of attacks would be prevented/avoided.
It's just "we authorities agree that we know these previous consensuses" isn't it?
Let's say one gets a copy from some authorities' key(s), blocks access to it/them, forges the IP addresses as they are hardcoded and then he makes them give the Guard flag to some relays he controls. Those consensuses would contain the previous hashes as well.
OK that might not be the case it should work against, but I fail to understand what it adds to security since an attacker would have access to the previous consensuses as well and therefore be able to create a hash of it.
I understand that it allows the network to notice if I feed it a valid consensus (because I got enough of the right keys to sign it) that doesn't include any or wrong hashes of previous consensuses.
Nevertheless it wouldn't do any damage either, beside what was mentioned in the security implications.
Best Regards, Sebastian G.
On Tue, Jan 6, 2015 at 1:54 PM, Sebastian G. <bastik.tor> bastik.tor@googlemail.com wrote:
06.01.2015, 18:51 Andrea Shepard:
Here's a proposal Nick Mathewson and I just wrote for ticket #11157.
[...]
- Introduction and overview
To avoid some categories of attacks against directory authorities and their keys, it would be handy to have an explicit hash chain in consensuses.
- Directory authority operation
We add the following field to votes and consensuses:
previous-consensus ISOTIME [SP HashName "=" Base16]* NLwhere HashName is any keyword.
[...]
To quote Nick Mathewson "I forget what else this was supposed to be good for." (see the ticket)
I fail to see what kind of attacks would be prevented/avoided.
The point of this proposal is to make some kinds of attacks are more easily detected. Right now, an attacker who somehow managed to steal or compromise a majority of authority signing keys (which we really hope is hard to do) could generate their own consensuses, and feed them to targeted clients. The rest of the network wouldn't necessarily notice.
With this proposal, the attacker would need to keep any targeted client misfed indefinitely, since if you didn't, the clients would eventually get a good consensus and realize that the previous one was bogus. This would raise the cost of such an attack, and raise the odds of it being detected.
At least, that's the theory.
06.01.2015, 18:51 Andrea Shepard:
All relying parties SHOULD by default retain all valid consensuses they download plus two; [...]
Unfortunately I did not consider this in my previous mail, but this does not account for the possibility that the valid-until ever increases.
Depending on valid-until there might be a huge pile of valid consensuses that will take some space.
Depending on what it buys a relying party some more or less future-proof defaults like let's say four consensuses whose valid-until is not expired and two whose valid-until expired most recently.
Long running parties will have checked the previous-consensus lines for consensuses that are expired for longer than they are kept.
Maybe a torrc option would be a good idea for clients or bridges on hardware with less storage space. Maybe even relays and exits don't have storage space, when they are run something like RAMDISK.
I might lack to understand the importance of keeping all consensuses that are still valid, but if it's just checking the hash by having them chained why couldn't Tor compute the hash(es), store it/them with the consensuses valid-after time and valid-until time in a separate file and then check that file if the latest consensus contains valid hashes in previous-consensus lines it knows about to be valid or recently expired?
It might not necessary to specify in the proposal since it says:
[...] if a hash fails to match it SHOULD warn loudly in the log mentioning the specific hashes and valid-after times in question [...]
but, what if a previous-consensus line is included with SHA256 and SHA512 and one of them mismatches? Are relying parties expected to throw a warning if ANY of the hashes mismatch or just if they fail to validate one? I guess it shouldn't happen at all, but for security reasons it seems to be better to make relying parties warn if anything goes wrong.
Best Regards, Sebastian G.
On Tue, Jan 06, 2015 at 05:51:53PM +0000, Andrea Shepard wrote:
Here's a proposal Nick Mathewson and I just wrote for ticket #11157.
--- Begin proposal body --- Filename: xxx-consensus-hash-chaining.txt Title: Consensus Hash Chaining Author: Nick Mathewson, Andrea Shepard Created: 06-Jan-2015 Status: Draft
- Introduction and overview
To avoid some categories of attacks against directory authorities and their keys, it would be handy to have an explicit hash chain in consensuses.
- Directory authority operation
We add the following field to votes and consensuses:
previous-consensus ISOTIME [SP HashName "=" Base16]* NLwhere HashName is any keyword.
This field may occur any number of times.
The date in a previous-consensus line in a vote is the valid-after date of the consensus the line refers to. The hash should be computed over the signed portion of the consensus document. A directory authority should include a previous-consensus line for a consensus using all hashes it supports for all consensuses it knows which are still valid, together with the two most recently expired ones.
When this proposal is implemented, a new consensus method should be allocated for adding previous-consensus lines to the consensus.
A previous-consensus line is included in the consensus if and only if a line with that date was listed by more than half of the authorities whose votes are under consideration. A hash is included in that line if the hash was listed by more than half of the authorities whose votes are under consideration. Hashes are sorted lexically with a line by hashname; dates are sorted in temporal order.
If, when computing a consensus, the authorities find that any previous-consensus line is *incompatible* with another, they must issue a loud warning. Two lines are incompatible if they have the same ISOTIME, but different values for the the same HashName.
The hash "sha256" is mandatory.
- Client and cache operation
All parties receiving consensus documents should validate previous-consensus lines, and complain loudly if a hash fails to match.
When a party receives a consensus document, it SHOULD check all previous-consensus lines against any previous consensuses it has retained, and if a hash fails to match it SHOULD warn loudly in the log mentioning the specific hashes and valid-after times in question, and store both the new consensus containing the mismatching hashes and the old consensus being checked for later analysis. An option SHOULD be provided to disable operation as a client or as a hidden service if this occurs.
All relying parties SHOULD by default retain all valid consensuses they download plus two; but see "Security considerations" below.
If a hash is not mismatched, the relying party may nonetheless be unable to validate the chain: either because there is a gap in the chain itself, or because the relying party does not have any of the consensuses that the latest consensus mentions. If this happens, the relying party should log a warning stating the specific cause, the hashes and valid-after time of both the consensus containing the unverifiable previous-consensus line and the hashes and valid-after time of the line for each such line, and retain a copy of the consensus document in question. A relying party MAY provide an option to disable operation as a client or hidden service in this event, but due to the risk that breaks in the chain may occur accidentally, such an option SHOULD be disabled by default if provided.
If a relying party starts up and finds only very old consensuses such that no previous-consensus lines can be verified, it should log a notice of the gap along the lines of "consensus (date, hash) is quite new. Can't chain back to old consensus (date, hash)". If it has no old consensuses at all, it should log an info-level message of the form "we got consensus (date, hash). We haven't got any older consensuses, so we won't do any hash chain verification"
- Security Considerations:
Retaining consensus documents on clients might leak information about when the client was active if a disk is later stolen or the client compromised. This should be documented somewhere and an option to disable (but thereby also disable verifying previous-consensus hashes) should be provided.
Clients MAY offer the option to retain previous consensuses in memory only to allow for validation without the potential disk leak.
--- End proposal body ---
Thank you Andrea and Nick for working on this! I think it's very important, but I'm not a fan of the design specified above.
I think it would be preferable to do something similar to what other blockchains do: have a header structure in the consensus document which contains the hash of the body and the hash of the header of the immediately previous consensus. That way, clients could afford to download, store, and verify all of the headers of the whole chain going back (at least) to the release date of their tor binary. They wouldn't need to store multiple full consensus documents (except in the case of a hash mismatch, in which case they should of course keep everything they have and raise the alarm).
~leif
-
Andrea Shepard -
Leif Ryge -
Nick Mathewson -
Sebastian G. <bastik.tor>