is the consensus document unpredictable / unique?
Hello everyone, I couldn't find a detailed description of the Tor consensus, so I'm checking that my understanding of it is correct. Basically, would it be correct to assume that the consensus document (or a hash thereof) for a date in the future is an unpredictable value that will also be unique to all nodes inquiring about it at that time? I'm thinking of using a hash of the consensus document - like http://171.25.193.9:443/tor/status-vote/current/consensus - as a descriptor cookie in a hidden service. This way, an attacker cannot generate or publish a hidden service descriptor for the future (one with a correct cookie). A client can fetch the consensus at the time it wants to connect, hash it, then use that as the descriptor cookie to determine the correct descriptor id and decrypt the introduction point list. Does anyone see any issues with this? In my project, the hidden service private key is on a smartcard, so it can't be copied, you can only ask the smartcard to sign something with it for you - and I'm trying to prevent an attacker from generating hidden service descriptors in advance,to be used without the smartcard. If future descriptors depend on an unpredictable future value (the hash of the consensus at that time), an attacker can only generate descriptors for past and current time periods. Thank you, Razvan -- Razvan Dragomirescu Chief Technology Officer Cayenne Graphics SRL
Hi Razvan, The consensus has signatures from all directory operators on it, and computing those ahead of time requires a lot of private keys. Because they also all contain the date, they're all unique. So yea, they're both unique and unpredictable. As for your idea: it should be noted that there is not a single valid consensus. At any time there may be several valid ones and clients may have different active ones, as all consensuses are valid for a few hours but generated hourly. Using the hash as a descriptor cookie may thus be troublesome. Tom
Hi Razvan,
On 26 Jun 2016, at 07:52, Razvan Dragomirescu <razvan.dragomirescu@veri.fi> wrote:
I couldn't find a detailed description of the Tor consensus, so I'm checking that my understanding of it is correct. Basically, would it be correct to assume that the consensus document (or a hash thereof) for a date in the future is an unpredictable value that will also be unique to all nodes inquiring about it at that time?
The future values of consensuses can be influenced by each of the 9 directory authorities, individually. A malicious authority has ~5 minutes between receiving other authorities' votes and creating its own to calculate a vote that creates a consensus hash that achieves a desired outcome. While it can't control the exact consensus hash, it can choose between many possible hashes, only limited by the available computing time. And it can farm out these computations to other computers. A shared random commit-and-reveal scheme, like the one in proposal 250, gives each authority a single choice: to reveal, or not reveal. This means that a malicious authority can only choose between two different output hashes, rather than choosing between many millions of possible hashes. This is why OnionNS switched from using a hash of the consensus, to the shared random value in the consensus.
On 26 Jun 2016, at 08:18, Tom van der Woerdt <info@tvdw.eu> wrote:
The consensus has signatures from all directory operators on it, and computing those ahead of time requires a lot of private keys. Because they also all contain the date, they're all unique. So yea, they're both unique and unpredictable.
The signed part of the consensus is the (hash of) everything up until the first signature. So while the consensus eventually contains up to 9 signatures, and some legacy signatures, it's not created or initially distributed between authorities that way. There's a few reasons you shouldn't rely on the hash of the signatures: * while the consensus is produced by up to 9 authority signatures, each signature is only produced by 1 authority; * a client only needs 5 of the 9 signatures to use a consensus, so it's not guaranteed to have them all; * signatures are distributed encoded, in PKCS1-padded format that ignores additional whitespace (and various other extraneous characters), so a malicious authority can control (some bits in) the hash of its own signature; * PKCS1.5-padding allows arbitrary pseudorandom inputs as part of the padding, so a malicious authority can try multiple values for this pseudorandom input until it gets a has that it wants; A malicious authority also has ~5 minutes between receiving other authorities' signatures and creating its own to calculate a signature that creates a consensus + signatures hash that achieves a desired outcome. This doesn't necessarily mean that your scheme will be insecure, but it would need to be constructed very carefully to avoid giving one malicious authority the ability to break it. And you might want to get some cryptographers to review it. (I can imagine an attack where a service creates many keys in advance with random values as the consensus hash, and a malicious authority then tries to vote or sign to match the consensus hash to one of the random values used to create one of the keys.) On the other hand, you could wait until there's a shared random value in the tor consensus, and use it. This may be ready a lot sooner than the entire next-generation hidden service protocol (proposal 224). It could be released in 0.2.9, and it could be running on enough authorities some time in 2017. Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
Thank you Tim, As long as a malicious authority cannot choose a hash that is identical to an older consensus hash, I think the system should be fine. In addition, I can have the the smartcard look at one of the valid-* dates in the consensus and hash that into the descriptor cookie as well - I'm guessing a rogue authority can mess with the consensus hash but cannot change the valid-after, valid-until, etc dates. If I enforce increasing dates (so that you cannot go back in time, once you've seen a consensus for Jan 2017 for instance you cannot sign another one from June 2016), if you attempt to pre-generate a signature for a future date, you lose connectivity until that particular date. I also plan to enforce an upper limit on the number of RSA signatures the card can perform with a given key. SIM cards already do this to prevent brute force attacks. If you don't have access to the smartcard and if you've somehow pre-generated some signed descriptors, those will only work for 1 hour (a very specific hour in the future that you've simulated consensus for and somehow tricked an authority into making the consensus hash be exactly the one you're expecting). What I like about the consensus (vs shared random value) is that it's regenerated every hour, so a successful attack would have very limited impact (1 hour sometime in the future). Shared random values are generated once per day, so if the attacker somehow guesses them successfully, he can pretend to be another node for a full day. As a second security layer, once the communication is established, the two nodes can negotiate a shared symmetrical key (based on the same RSA keypairs they use as permanent keys for hidden services or a different keypair). This way, a successful attacker can only launch a Denial of Service type of attack (preventing the legitimate node from getting the traffic) but cannot decrypt or encrypt traffic from/to that node. Thanks again, Razvan On Mon, Jun 27, 2016 at 9:02 AM, Tim Wilson-Brown - teor <teor2345@gmail.com
wrote:
Two clarifications/questions: 1. I've just realized that hashing the current valid-* dates into the descriptor cookie doesn't help - those values are known to the attacker and he can tweak his vote to generate a certain hash regardless of that date. The rest of what I've said applies just fine. 2. How would a Directory Authority be able to tweak its vote to generate multiple valid consensus documents? I'm not familiar with the voting process (just read about it a bit at http://jordan-wright.com/blog/2015/05/14/how-tor-works-part-three-the-consen... ) . Can a rogue DA pretend that it has knowledge of additional relays that the other DAs don't know about and tweak their fingerprints to try to match a precomputed hash? Do the DAs simply merge all relay lists with no other checks? Is there any legitimate situation where a single DA would know about a given relay? Or am I missing some random data that the DA includes in its vote that could be used for this? Thank you, Razvan -- Razvan Dragomirescu Chief Technology Officer Cayenne Graphics SRL On Mon, Jun 27, 2016 at 10:30 PM, Razvan Dragomirescu < razvan.dragomirescu@veri.fi> wrote:
On 28 Jun 2016, at 06:16, Razvan Dragomirescu <razvan.dragomirescu@veri.fi> wrote:
2. How would a Directory Authority be able to tweak its vote to generate multiple valid consensus documents? I'm not familiar with the voting process (just read about it a bit at http://jordan-wright.com/blog/2015/05/14/how-tor-works-part-three-the-consen... ) . Can a rogue DA pretend that it has knowledge of additional relays that the other DAs don't know about and tweak their fingerprints to try to match a precomputed hash? Do the DAs simply merge all relay lists with no other checks?
The consensus generation algorithm is deterministic, based on the content of the (up to) 9 votes. A majority of directory authorities need to vote for a relay to have it included in the consensus.
Is there any legitimate situation where a single DA would know about a given relay?
Perhaps it's the only reachable directory authority from that relay. But, in that case, the other authorities would see that relay in a vote, and ask each other authority for a copy of its descriptor. If they don't get the descriptor, they won't vote for the relay.
Or am I missing some random data that the DA includes in its vote that could be used for this?
Yes. Not random data, but an authority can freely choose to vote for (or not vote for) certain attributes, like relay flags, or other values. Sometimes, changing a vote in this way will change the resulting consensus. If 4/9 authorities vote for an attribute, the final authority gets to choose whether it goes in or not. There are 7000 relays in the consensus. https://consensus-health.torproject.org/ Each relay can be included or excluded from the consensus (the Running flag). Each relay can have zero or more of the following 6 flags: Fast Exit Guard HSDir Stable V2Dir. (For simplicity, I'm ignoring the Valid and BadExit flags.) By my quick count, 12 flags could be manipulated this way out of the first 50 relay entries. Extrapolating, 12 * 7000 / 50 = 1680 flags in the entire consensus which depend on a single authority's vote. Therefore, each authority could affect 1680 / 9 = 186 consensus flags on average. This gives each authority the ability to produce 2 ^ 186 possible consensus outcomes. But it gets worse - there are 5 bandwidth authorities. Each bandwidth authority can choose an arbitrary value as the measured bandwidth of a relay, and the median value is included in the consensus. There are 6900 measured relays in the consensus. https://collector.torproject.org/recent/relay-descriptors/ On average, this means that a bandwidth authority can choose from a range of bandwidth values for 1 in 5 relays, or 1380 relays. Bandwidths in the consensus are reported to 3 significant figures. Let's assume an authority can arbitrarily choose the final one of those figures. This gives each bandwidth authority the ability to produce 10 ^ 1380 possible consensus outcomes, which must be multiplied by the 2 ^ 186 possibilities above. Therefore, the number of possible consensus outcomes that can be produced by one malicious authority exceeds the number of possible hash outputs, for almost all current cryptographically secure hashes. While an authority could in theory generate a consensus with any hash, this is bounded by available processor time to hash consensuses. Here's an efficient algorithm for producing consensus hashes: * hash most of the consensus, up to the last point where you can make a bandwidth change, or a few flag changes * store the state of the hash * use the state to quickly compute the hash of each consensus variant * if you haven't found a hash that does what you want, try changing something slightly further back, and repeat The reason that this isn't secure for hidden service descriptor assignments to hidden service directories is that there are only ~5000 possible hidden service directories. So you only need to be able to generate ~5000 hashes to get the descriptor you want on your hidden service directory. It might work with your scheme, if you use a large enough hash, that takes long enough to calculate, and you use all the bits of the hash, and you check the dates you're signing, and you rate-limit signing. But that means a lot of moving pieces which can go wrong. And it likely means some attacks you haven't thought of. Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
On 28 Jun 2016, at 06:16, Razvan Dragomirescu <razvan.dragomirescu@veri.fi> wrote:
1. I've just realized that hashing the current valid-* dates into the descriptor cookie doesn't help - those values are known to the attacker and he can tweak his vote to generate a certain hash regardless of that date. The rest of what I've said applies just fine.
You could have your smart card parse a consensus and check the dates are on or after previous signed dates, before signing a descriptor for those dates. But text parsing is error-prone.
I also plan to enforce an upper limit on the number of RSA signatures the card can perform with a given key. SIM cards already do this to prevent brute force attacks.
You might actually want to limit the number of signatures per-hour as well. But no-one has statistics for the number of hidden service descriptors per service per hour, as far as I know. It's likely somewhere between 0 and 10.
If you don't have access to the smartcard and if you've somehow pre-generated some signed descriptors, those will only work for 1 hour (a very specific hour in the future that you've simulated consensus for and somehow tricked an authority into making the consensus hash be exactly the one you're expecting).
What I like about the consensus (vs shared random value) is that it's regenerated every hour, so a successful attack would have very limited impact (1 hour sometime in the future). Shared random values are generated once per day, so if the attacker somehow guesses them successfully, he can pretend to be another node for a full day.
An hour is enough to de-anonymise a lot of clients. The shared random value lasts for a day, because all clients and hidden services and hidden service directories need to agree on it, and need to cache valid descriptors for a reasonable period of time. If an attacker is capable of guessing a 256-bit random value… seems exceedingly unlikely. If an attacker is capable of calculating a 256-bit shared random value, which depends on the private state of the 9 directory authorities, and even that state is only created 24 hours in advance… again, seems unlikely, and it only works 24 hours in advance.
As a second security layer, once the communication is established, the two nodes can negotiate a shared symmetrical key (based on the same RSA keypairs they use as permanent keys for hidden services or a different keypair). This way, a successful attacker can only launch a Denial of Service type of attack (preventing the legitimate node from getting the traffic) but cannot decrypt or encrypt traffic from/to that node.
An attacker can prevent the node from getting some of the traffic. Typically, the attacker will control the descriptor on each of the 6 hidden service directories until the hidden service uploads a new one. All connections made by clients using attacker-controlled descriptors will go to the attacker's introduction points. Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
Thank you Tim, I've been thinking about it and it looks like an easy fix for the problem would be to prevent the rogue DA from farming out the hash calculations or generating a lot of them in the 5 min voting window. If the hash only depends on public info (consensus data, current date, etc), you can't prevent this. But if the hash includes a shared secret key _inside the smartcard_, the attacker has to ask the smartcard to compute the hash and that's orders of magnitude slower than a computer (and can be made artificially slower by burning some CPU cycles inside the card doing RSA key generations or something - it has no internal clock so you can't just "sleep", but you can give it something time-consuming to do before it computes the hash). So here's the new setup I have in mind: 1. Each card can be provisioned with a "network key". This is a value that all cards (and nodes) that are part of a given network share. It can only be set, not read and can be used in the computation of the Descriptor Cookie. 2. The descriptor cookie will be calculated as H ( network-key | timestamp (rounded down to a full hour) | H (consensus) ) The terminal provides the current consensus hash and a timestamp. The card checks that the timestamp is greater than the last timestamp it has used. It then concatenates the secret network-key, the given timestamp and the consensus hash and returns the hash of the result. This means a few things: 1. An attacker can no longer generate a hash independently or farm it out to other computers. It has to ask a smartcard to do it. We can make this arbitrarily slow since the operation is only meant to be done once an hour, so I could make it take a minute per hash inside the card. 2. Generating a hash for a future date would lock you out until that date/time (since decreasing timestamps will be refused by the card). You could compute the correct hash for the current timestamp and consensus on another card, but you would not be able to generate a signed descriptor with that correct hash (you can't inject a hash computed somewhere else into the signed descriptor). 3. The card doesn't have to parse the consensus - it just uses it as a shared random value (the hash of the consensus). Makes sense? Thank you, Razvan On Tue, Jun 28, 2016 at 6:02 AM, Tim Wilson-Brown - teor <teor2345@gmail.com
wrote:
There are now so many moving parts in this scheme, I think you need to specify it all in one place, and then convince a cryptographer to review it. (I am not a cryptographer.) And then have your implementation reviewed against the spec. How is the card you're using for side-channels? Keys have beed extracted using power usage information, or electromagnetic emissions, or even audio. Tim
Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n
Fair enough, this needs to be reviewed by a cryptographer once the dust settles. I'm just trying to get a good grasp of what's possible within the boundaries of the TOR network and how that translates to cryptographic/security primitives I can use in this particular project (like using the consensus hash as a future unpredictable value, etc). As of last night, I have a very basic proof of concept, it needs a bit of polish and then I'll start showing it off and submitting it to external analysis. Thank you! Razvan -- Razvan Dragomirescu Chief Technology Officer Cayenne Graphics SRL On Wed, Jun 29, 2016 at 2:22 AM, Tim Wilson-Brown - teor <teor2345@gmail.com
wrote:
Hello, If you hash the consensus entirely, yes that should produce unique hashes every time that are unpredictable until the consensus is available. However, you cannot guarantee it will be the same value for everyone at a given time, because consensus documents overlap and two clients/relays might work properly but not use exactly the same consensus at a given time (at 13:45 "Y" uses consensus document valid after 12:00 and "Z" uses consensus document valid after 13:00. Both are within their valid-until limits). I don't recommend that your rely on what you've suggested because of pour security properties and too complicated design with too many possible failure cases to be worth it. Very soon Tor will include an unique random value we call "Consensus Shared Randomness [SRVALUE]" in every consensus, you can just use that. This is proposal 250. This seams like a better standardized upstream solution with infinite better security properties, so I'd use this as a cookie. This has the advantage of having the same unique value on all nodes all the time: just filter and pair consensus SRVALUE + consensus valid-after timestamp and everyone will be requesting the SRVALUE of the same consensus, therefor producing the same result or fail if none. Last but not least, how will your system work in practice? The hidden service private key will be stored on a smartcard and it cannot be copied, it will only sign descriptors at the request of the host. So far so good, but the smartcard has to stay plugged in the host all the time, or at least all the time the hidden service is running, so what's the security property here? If you think you can manually plug in the smartcard rarely just to sign descriptors and keep it somewhere else physically most of the time, this will not work. In the wild things happen that demand new descriptors to be signed in an unpredictable way: introduction points go offline; HSDirs go offline, too many INTRODUCE2 cells received on a single introduction point circuit. And if the private key is on a smartcard, and the smartcard is plugged in the host all the time, what's the gain? I am not saying there isn't any, I just don't see it at this moment. One I can think of is that malware and/or someone hacking can't copy the private key and hijack the hidden service, but the risk remains in case someone physically sizes the server ("host"). Do note that next generation of hidden services will support natively offline keys and actually allow the hidden service to run properly: the offline keys will generate blinded signing keys, which are used to sign descriptor signing keys. On 6/26/2016 12:52 AM, Razvan Dragomirescu wrote:
Hello again, I am sorry, too tired and written something wrong: On 6/26/2016 1:29 AM, s7r wrote:
This is not true. The SRVALUE will be the same for an entire day. So you still need to hash the entire consensus if you need an unique value for _every_ consensus or use SRVALUE if you need an unique value for a day. Sorry again for not double reading my previous email.
Thank you s7r, Tom, I'll try to explain what I'm doing - I'm working on something called SIM4Things - it's an Internet of Things project, giving Internet-connected objects a persistent, cryptographically secure identity and a way to reach similar objects. The closest analogy is the SIM card in the GSM / mobile world (hence the name :) ). The identity is actually an RSA keypair, stored in a tamper-resistant microSD form factor secure element (like this one https://www.swissbit.com/ps-100u/ ). The project does multiple things - first, it gives the node an identity - the RSA private key inside is used to sign a hidden service descriptor (a la OnionBalance) that is then published. As long as the device has access to the smartcard, it can sign descriptors. Once the card is removed, it can no longer do that. Second, using hidden services means that the devices become accessible at a single .onion address regardless of how they connect to the Internet and how many firewalls and/or NAT gateways they are behind. I'm very close to having a fully functional proof of concept on this tiny board https://labs.mediatek.com/site/global/developer_tools/mediatek_linkit_smart_... . It runs OpenWRT. A Python script using STEM connects to Tor and to the internal smartcard, fetches the hidden service descriptor as published by Tor and modifies / re-signs it to point to the address associated with its public key (keeps the introduction points, rewrites everything else). I know this will no longer work with Prop 224 but afaik Prop224 is still 1-2 years away. Once the new descriptor is published, the node can talk to any other similar node over the Tor network. I want to offer the same guarantees that a regular SIM card inside your phone would offer - as long as you have the SIM, you can join the network and talk to other nodes. Once the SIM is gone, you should no longer be able to do so. It should also be impossible (or very hard) to clone such a SIM card and it should be impossible (or hard) to generate hidden service descriptors in advance (that would allow you to join the network even after the SIM has been removed). So, to summarize - I'm doing a SIM card for the Internet of Things. The SIM is a microSD tamper-resistant secure element with an RSA key inside. It gives the node an identity (strongly tied to the physical SIM) and a way to talk to similar nodes, with no central server or censorship opportunity. If you have any questions, feel free to ask. Thanks, Razvan -- Razvan Dragomirescu Chief Technology Officer Cayenne Graphics SRL On Sun, Jun 26, 2016 at 1:29 AM, s7r <s7r@sky-ip.org> wrote:
A better link for the Mediatek Linkit 7688 board I'm using for PoC is https://www.seeedstudio.com/item_detail.html?p_id=2573 . I'm also doing a second PoC on a Raspberry Pi Zero - https://www.raspberrypi.org/products/pi-zero/ - far more powerful than the Linkit 7688 above and also cheaper, but a lot harder to find. Razvan On Sun, Jun 26, 2016 at 3:32 PM, Razvan Dragomirescu < razvan.dragomirescu@veri.fi> wrote:
participants (5)
-
Ivan Markin -
Razvan Dragomirescu -
s7r -
Tim Wilson-Brown - teor -
Tom van der Woerdt