[tor-dev] Draft Proposal: Random Number Generation During Tor Voting

[teor]

> On 10 Aug 2015, at 23:07 , George Kadianakis <desnacked at riseup.net> wrote:
> 
> teor <teor2345 at gmail.com> writes:
> 
>>> On 4 Aug 2015, at 22:00 , George Kadianakis <desnacked at riseup.net> wrote:
>>> 
>>> Hello,
>>> 
>>> <snip>
>>> 
>>>>> 3.7. Shared Randomness Disaster Recovery [SRDISASTER]
>>>>> 
>>>>> If the consensus at 12:00UTC fails to be created, then there will be no new
>>>>> shared random value for the day.
>>>>> 
>>>>> Directory authorities should keep including the previous shared random
>>>>> values in the consensus till the next 12:00UTC commit-and-reveal session.
>>>>> The time period needs to be updated to reflect the current time period even
>>>>> if the random value stays the same.
>>>>> 
>>>>> Clients should keep on using this shared random values.
>>>> 
>>>> (If the timestamp is updated, clients wouldn't even know that the protocol had failed, even if they downloaded the shared randomness document, unless they specifically checked for failure.)
>>>> 
>>>> We could instead run an instance of the hash with an empty set of reveals like so:
>>>> 
>>>> V = H("TOR SHARED RANDOMNESS PROTOCOL VERSION 1" | DATE | PREVIOUS_SHARED_RANDOMNESS_VALUE)
>>>> 
>>>> This would gracefully degrade the protocol, and provide a predictable but different value each day, based on the previous value and the date, very much like the current HSDir hash ring.
>>>> 
>>>> But does this gain us anything?
>>>> (The HSDirs would at least move each day, albeit predictably. We might want this property.)
>>>> 
>>> 
>>> I think the result here will be the same.
>>> 
>>> However, I agree that making it hard to detect failure is a bad idea. We should
>>> think of how to make this more obvious.
>> 
>> We could add a shared random status line to the consensus (and SR doc) giving the status of the latest completed shared random round - success, failure, bootstrap 0, or bootstrap 1.
>> 
>> The expected state transitions would be:
>> 
>> (start) -> bootstrap 0 -> bootstrap 1 -> success -> success …
>> (failure in any state) -> failure -> success -> success …
>> 
>> This would allow clients to determine how reliable the shared randomness is at any point in time.
>> 
> 
> OK, please check my `rng-draft-v4-asn` branch again. You can find it here:
> 
>    https://gitweb.torproject.org/user/asn/torspec.git/log/?h=rng-draft-v4-asn
> 
> In 6e74f12, I decided to follow your advice and chain-hash the old SRV in case of disaster.
> 
> I think this makes it a tiny bit harder for an attacker that wants to exploit
> the disaster scenario, since to camp an HS she will need to setup 6*N relays,
> instead of just 6, where N is the number of days she wants to camp. It also
> seemed like an easy engineering change to make, so I did it. I decided to rip
> off the date from the hash inputs, since David persuaded me that dates will make
> this more complex and we should just use the concept of "current SRV" and
> "previous SRV" to define time. Let me know if you think that's a bad idea.

Not being a crypto expert, I was following Nick's "hash all the things (unless there's a good reason not to)" advice.

That said, it seems to me that complexity is a good reason to skip the date, and that the date is simply a known constant which increments by the same value every day. I can't see a value like that being any major benefit to security, it's equivalent to mixing 1, 2, 3, … into the hash each day.

I believe chaining the previous value is an excellent design feature that preserves a sense of time/continuity. It also gives the useful property that the shared random failure mode is no worse than the existing hidden service directory selection algorithm. (Both yield a predictable value every day, but the shared random value is only predictable on failure, rather than for all time.)

Also, FWIW, an attacker would need to setup up to 6*(N+2) relays to cover N periods of 24 hours, due to the (not-shared) random switchover times. Which is significant if N is 1 (the most likely failure mode).

> Also in b03fc9c, I decided to add an indicator on the freshness of the SRV to
> increase auditability. I did not add a new line as you suggested, because this
> means that I would need to add more walls of text to the proposal defining how
> to vote for these lines, and how to carry them, etc. Instead, I just added a
> status field to the shared-rand-{previous,current}-value lines. Let me know if
> you think that's a terrible idea as well.

In general, I think a status field is great, and it allows us to label each random value differently, too. This is useful for clients which might want to tolerate 1 failure, but not a sequence of failures.

I think clients can determine if the SR system is bootstrapping as specified:

If the status of the current SR value is "non-fresh", SR is in failure mode.
If the status of the previous SR value is "non-fresh", SR was in failure mode yesterday.
(If both, there has been a sequence of failures.)
If there is no previous SR value, SR is (day 1) bootstrapping.
If there is no current SR value, SR is either inactive or (day 0) bootstrapping.

Excellent! Looking forward to the implementation.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
pgp ABFED1AC
https://gist.github.com/teor2345/d033b8ce0a99adbc89c5

teor at blah dot im
OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 832 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150812/34a6ad0b/attachment.sig>