[tor-dev] Shared random value calculation edge cases (proposal 250)

[Jacob Appelbaum]

On 11/21/15, Tim Wilson-Brown - teor <teor2345 at gmail.com> wrote:
>
>> On 20 Nov 2015, at 10:59, George Kadianakis <desnacked at riseup.net> wrote:
>>
>> David Goulet <dgoulet at ev0ke.net <mailto:dgoulet at ev0ke.net>> writes:
>>
>>> On 19 Nov (14:30:47), Jacob Appelbaum wrote:
>>>> Hi George,
>>>>
>>>> On 11/12/15, George Kadianakis <desnacked at riseup.net> wrote:
>>>>> Hello there believers of prop250,
>>>>>
>>>>> you can find the latest version of the proposal in the upstream torpec
>>>>> repo:
>>>>>
>>>>> https://gitweb.torproject.org/torspec.git/tree/proposals/250-commit-reveal-consensus.txt
>>>>
>>>> I reviewed your fine document and I wondered about section 4.1.1. and
>>>> specifically about the generation of RN "where RN is a 256-bit random
>>>> value."
>>>>
>>>> I'd like to propose a change that is minimal and adds only one small
>>>> change:
>>>>
>>>>   The value REVEAL is computed as follows:
>>>>
>>>>      REVEAL = base32-encode( TIMESTAMP || H(RN) )
>>>>
>>>>      where RN is a 256-bit random value and where H is the hashing
>>>> algorithm "sha256".
>>>>
>>>> This would ensure that the raw random bytes from the PRNG are never
>>>> revealed to the network which seems like a reasonable thing[0] to
>>>> prevent.
>>>
>>> Interesting! This sounds like a good thing to do and very little change
>>> needed for additional security.
>>>
>>> George, if you are OK with this, I can change the proposal and push it
>>> upstream. Will change the code after that.
>>>
>>
>> Sounds good to me.
>>
>> The commitment structure will also have to change to commit H(H(RN)).
>>
>> For spec readability, maybe we could have:
>>
>> RN = 255-bit random number
>> REVEAL_VALUE = H(RN)
>>
>> and then use REVEAL_VALUE in REVEAL and COMMIT.
>
> Jacob/David/George,
>
> We typically add a distinguishing value to hashes and signatures in prop224
> - can/should we do that for the shared random proposal as well?

I don't think so?

>
> It would look like:
>
> RN = 255-bit random number
> REVEAL_VALUE = H("derive-reveal" | RN)
> COMMIT_VALUE = H("derive-commit" | REVEAL_VALUE)
>

My suggestion shouldn't impact such a choice in any case. I merely
suggest that the 256-bit (surely you don't mean 255 bit?) random
number is hashed before we consider it a valid candidate RN value.

The following are equivalent and should be indistinguishable uniformly
random values:

(RN = H(gen_random(256)) ~= (RN = gen_random(256))

The cost is an extra full sha256 but the resulting output is
different. The key difference is that we do not reveal the raw outputs
of the (P)RNG directly to the network or to a potential adversary.

All the best,
Jake