Shared random value calculation edge cases (proposal 250)
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-c... Implementation is also constantly moving forward as you can see in the ticket: https://trac.torproject.org/projects/tor/ticket/16943 Now that we have ironed out the whole voting procedure, it's time to finish this up by figuring out the last details of the shared random value calculation. The logic in the current proposal seems reasonable (see section 3.3), but I have some doubts that I wanted to communicate with you. - I'm afraid of edge cases where different authorities will calculate different shared random values. This is bad because if it happens at the wrong moment, it might break the consensus. For example, imagine that there are 5 authorities that are doing the prop250 protocol. Since there are 5 auths, they can create a valid consensus on their own with SR info in it. Now imagine that one of them, Alice, has a different view of the previous_SRV than the others (maybe because she _just_ booted up before voting and she doesn't have a previous consensus). In this case, Alice will calculate a different SRV than the other 4, and hence the consensus will break because 5 signatures could not be collected. Is this something likely to happen? If yes, a way to protect against it is to add a flag on the votes denoting support for the SR protocol, and have dirauths toggle it off if they are voting for 00:00UTC and they don't know the previous_SRV or if they don't have a consensus. This can also be used as a torrc-enabled killswitch, if the SR protocol bugs out completely and we need to disable it for the sake of the network. What do you think? - Another bothersome thing is the disaster SRV calculation. Specifically, the proposal says: =============================== prop 250: ==================================== If the consensus at 00:00UTC fails to be created, then there will be no fresh shared random value for the day. In this case, and assuming there is a previous shared random value, directory authorities should use the following construction as the shared random value of the day: SRV = HMAC(previous_SRV, "shared-random-disaster") where "previous_SRV" is the previous shared random value. =============================================================================== this logic is not implemented in the current code, and it's not straightforward to implement. Again because the previous_SRV is blended in the formula, but also because it's not easy to know that "the consensus at 00:00UTC fails to be created". For example, if you are a dirauth that just started up at 00:30UTC, and you asked for the previous consensus and you were given the 23:00UTC consensus, then you won't know that the 00:00 consensus was not created and that you need to do the disaster procedure. This will again break the consensus. Not sure if this is a likely scenario as well, and if we should protect against it. What do you think? It depends on the logic that authorities have for fetching consensuses. Do they ensure that they always have the latest consensus? Do we need to add such logic as part of prop250? :/ A way to protect against it is to use the "SR support" vote flag I talked about before, and toggle it off if you are a dirauth and you don't have the latest consensus. Terrible? Would that even allow dirauths to bootstrap SR? - Another interesting part of prop250 is: =============================== prop 250: ==================================== If the shared random value contains reveal contributions by less than 3 directory authorities, it MUST NOT be created. Instead, the old shared random value should be used as specified in section [SRDISASTER]. =============================================================================== do you think this is useful? The fact that we use consensus methods, ensures us that at least 5 dirauths understand the SR protocol, otherwise we don't do it. Should we care about the number of reveal values? And why should the constant be 3, and not 5 or 2? Those were my doubts. Sorry for the extra confusion, but I'm currently reading the proposal and trying to minimize the amount of edge cases that can happen in the implementation (especially if they result in breaking the consensus for everyone). Maybe I'm trying too hard, and there are already multiple such edge cases in the consensus protocol that just never happen and are not worth fixing. In any case, the shared random value calculation seems to be the last piece of the puzzle here, so let's figure it out and finish up! Thanks!
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hello, Saw the content of this section in master was corrected, yet the subtitle is little confusing: 4.1.6. Including the ed25519 shared randomness key in votes [SRKEY] - From the content of this section I understand that we are going to include the ed25519 medium term signing key, certificate and master identity key. The content is clear, but maybe we should change the subtitle too, since there's no SR key: 4.1.6. Including the ed25519 medium term signing key and master identity key in votes [ED25519ID] Edge cases are the main reason I suggested in my previous emails to require at least 2 or 3 reveal rounds in order to allow a dirauth to participate in the shared randomness calculation for that day. However this won't help in case a dirauth needs to vote at 01:00 UTC and doesn't know anything. The idea of adding flags in the votes so each dirauth can advertise if it is participating (has an opinion for the <current> SR or not) is great and helps us build more defenses, probably make it easier in the future too if we decide to change anything. What if the consensus for SR calculation would define majority based on dirauths actually participating (and advertising so with a flag in the vote). Also, the participating or not participating flag should be used per vote/consensus and split into: a) we know current SR value for today so we vote it or we know previous SR value and we know for sure if we should follow the disaster protocol or not (in case we are about to vote at 01:00 UTC). so We participate in the vote for <current SR>. b) we are able to participate in this protocol run which will calculate the SR value for next day (after 00:00 UTC) so we send our commits/reveals. This is useful in case we are a dirauth that joined at 00:30 UTC and we couldn't get the _latest_ consensus (to find out if the 00:00 UTC consensus was created, and if not, previous SR value so we can follow the disaster procedure) we will not have an opinion for the <current> SR value at 01:00 UTC, but we can start participating in the protocol run for the next day - send our commit values. Once we decided on a <current> SR value for that day we save it and vote normally next time. So, if we have 5 dirauths running/signing consensus in total, out of which only 4 participate in the shared randomness protocol, the 4 participating ones should be able to create a valid consensus themselves with the insurance that the 5th one won't break consensus. One way to do this is: the dirauth which is not participating will take the SR value voted by the majority of the participating dirauths and include that in its consensus and sign. We need at least 3 dirauths agreeing on a SR value in order to accept it. Is this crazy? It shouldn't open the door new attacks, since this doesn't allow a single actor to game it, only the majority could game it. Some more comments inline. On 11/12/2015 4:25 PM, George Kadianakis 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-c...
Implementation is also constantly moving forward as you can see in the ticket:
https://trac.torproject.org/projects/tor/ticket/16943
Now that we have ironed out the whole voting procedure, it's time to finish this up by figuring out the last details of the shared random value calculation.
The logic in the current proposal seems reasonable (see section 3.3), but I have some doubts that I wanted to communicate with you.
- I'm afraid of edge cases where different authorities will calculate different shared random values. This is bad because if it happens at the wrong moment, it might break the consensus.
For example, imagine that there are 5 authorities that are doing the prop250 protocol. Since there are 5 auths, they can create a valid consensus on their own with SR info in it.
Now imagine that one of them, Alice, has a different view of the previous_SRV than the others (maybe because she _just_ booted up before voting and she doesn't have a previous consensus). In this case, Alice will calculate a different SRV than the other 4, and hence the consensus will break because 5 signatures could not be collected.
Is this something likely to happen?
If yes, a way to protect against it is to add a flag on the votes denoting support for the SR protocol, and have dirauths toggle it off if they are voting for 00:00UTC and they don't know the previous_SRV or if they don't have a consensus. This can also be used as a torrc-enabled killswitch, if the SR protocol bugs out completely and we need to disable it for the sake of the network. What do you think?
- Another bothersome thing is the disaster SRV calculation. Specifically, the proposal says:
=============================== prop 250: ==================================== If the consensus at 00:00UTC fails to be created, then there will be no fresh shared random value for the day.
In this case, and assuming there is a previous shared random value, directory authorities should use the following construction as the shared random value of the day:
SRV = HMAC(previous_SRV, "shared-random-disaster")
where "previous_SRV" is the previous shared random value. ===============================================================================
this logic is not implemented in the current code, and it's not straightforward to implement. Again because the previous_SRV is blended in the formula, but also because it's not easy to know that "the consensus at 00:00UTC fails to be created".
For example, if you are a dirauth that just started up at 00:30UTC, and you asked for the previous consensus and you were given the 23:00UTC consensus, then you won't know that the 00:00 consensus was not created and that you need to do the disaster procedure. This will again break the consensus.
Not sure if this is a likely scenario as well, and if we should protect against it. What do you think?
It depends on the logic that authorities have for fetching consensuses. Do they ensure that they always have the latest consensus? Do we need to add such logic as part of prop250? :/
I don't think I understand this the way I should. If we join at 00:30 UTC, instead of asking for previous consensus, why don't we ask for _latest_ consensus from every other dirauth? And if we are given the 23:00 UTC consensus at 00:30 UTC, we know the consensus at 00:00 UTC was not created and we need to follow the disaster procedure. If we have the 23:00 UTC consensus, we know the previous SR value so we can participate. If we couldn't get it, we advertise that we are not participating and sign whatever the participating majority agrees so we don't break consensus.
A way to protect against it is to use the "SR support" vote flag I talked about before, and toggle it off if you are a dirauth and you don't have the latest consensus. Terrible? Would that even allow dirauths to bootstrap SR?
I don't see why would this be terrible. What's a plausible thing that can happen so a dirauth can't get the latest consensus?
- Another interesting part of prop250 is:
=============================== prop 250: ==================================== If the shared random value contains reveal contributions by less than 3 directory authorities, it MUST NOT be created. Instead, the old shared random value should be used as specified in section [SRDISASTER]. ===============================================================================
do you think this is useful?
The fact that we use consensus methods, ensures us that at least 5 dirauths understand the SR protocol, otherwise we don't do it. Should we care about the number of reveal values? And why should the constant be 3, and not 5 or 2?
Yes, I think this is useful and 3 is a fair constant, especially combined with the participating or not participating flags. I guess the argument here is that it should be quite hard to have 3 dirauths colluding for an attack.
Those were my doubts.
Sorry for the extra confusion, but I'm currently reading the proposal and trying to minimize the amount of edge cases that can happen in the implementation (especially if they result in breaking the consensus for everyone). Maybe I'm trying too hard, and there are already multiple such edge cases in the consensus protocol that just never happen and are not worth fixing.
Your concerns make sense to me, however this could also be true. I don't know enough to confirm or infirm it, but looking forward for more comments.
In any case, the shared random value calculation seems to be the last piece of the puzzle here, so let's figure it out and finish up!
Thanks! -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (MingW32)
iQEcBAEBCAAGBQJWS2aOAAoJEIN/pSyBJlsRPCQIALUKqo1nvVTYV0WQqrlvnRpm ilSulg+WZNuiyB/uxxTfk6DtmBz6oqwsO2hPwr5BPzJO8SYBHm7jSGxalTOUh0nR MEgVbjRYMOJZGqECsioxjhdOqoB7p8oK+rhnSRmBy/HxTVqb6FkkGr5Psil+RrQL JPOlkm6r0ptF10Fg+lVbYXyiM2GGB4Ggup76MOX4MZ0Lr12aWJmrLk17JUhXk2r5 k7akAREBhwmsHnkJ1XA27lVMcBYX9gz1IR85wDUgBFdf8WI3FDVck2MPUTsp2eai xeLs6XAfvBfKcaQMolxsJ01rxUps0V8no8sjqOH4McdYJhXDfpdLnObFqoSj3no= =wRgo -----END PGP SIGNATURE-----
s7r <s7r@sky-ip.org> writes:
Hello,
Saw the content of this section in master was corrected, yet the subtitle is little confusing:
4.1.6. Including the ed25519 shared randomness key in votes [SRKEY]
From the content of this section I understand that we are going to include the ed25519 medium term signing key, certificate and master identity key. The content is clear, but maybe we should change the subtitle too, since there's no SR key:
4.1.6. Including the ed25519 medium term signing key and master identity key in votes [ED25519ID]
You are right. We need to fix this. Noted.
Edge cases are the main reason I suggested in my previous emails to require at least 2 or 3 reveal rounds in order to allow a dirauth to participate in the shared randomness calculation for that day. However this won't help in case a dirauth needs to vote at 01:00 UTC and doesn't know anything.
The idea of adding flags in the votes so each dirauth can advertise if it is participating (has an opinion for the <current> SR or not) is great and helps us build more defenses, probably make it easier in the future too if we decide to change anything.
What if the consensus for SR calculation would define majority based on dirauths actually participating (and advertising so with a flag in the vote). Also, the participating or not participating flag should be used per vote/consensus and split into:
a) we know current SR value for today so we vote it or we know previous SR value and we know for sure if we should follow the disaster protocol or not (in case we are about to vote at 01:00 UTC). so We participate in the vote for <current SR>.
b) we are able to participate in this protocol run which will calculate the SR value for next day (after 00:00 UTC) so we send our commits/reveals.
I'm not sure exactly what you are suggesting here. That the participation flag should not simply be 0 or 1, and that it should have more purposes?
This is useful in case we are a dirauth that joined at 00:30 UTC and we couldn't get the _latest_ consensus (to find out if the 00:00 UTC consensus was created, and if not, previous SR value so we can follow the disaster procedure) we will not have an opinion for the <current> SR value at 01:00 UTC, but we can start participating in the protocol run for the next day - send our commit values. Once we decided on a <current> SR value for that day we save it and vote normally next time.
So, if we have 5 dirauths running/signing consensus in total, out of which only 4 participate in the shared randomness protocol, the 4 participating ones should be able to create a valid consensus themselves with the insurance that the 5th one won't break consensus.
One way to do this is: the dirauth which is not participating will take the SR value voted by the majority of the participating dirauths and include that in its consensus and sign. We need at least 3 dirauths agreeing on a SR value in order to accept it.
Is this crazy? It shouldn't open the door new attacks, since this doesn't allow a single actor to game it, only the majority could game it.
Yes, that *could* be a way to do it. Have dirauths who don't know the current/previous SRV get it from votes. I think we all agree that dirauths who don't know the current/previous SRV should get it from the previous consensus (even though this logic has not been implemented yet). Getting it directly from the votes would be a different scheme that maybe we should think about.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On 11/19/2015 3:57 PM, George Kadianakis wrote:
s7r <s7r@sky-ip.org> writes:
I'm not sure exactly what you are suggesting here. That the participation flag should not simply be 0 or 1, and that it should have more purposes?
Sorry for the confusion. The participation flag should be 0 or 1 yes, but it should only refer to current consensus SR value. If our participation flag is 0, we don't vote a SR value for the next consensus. This doesn't prevent us from participating in the protocol run related to the SR value for the next day (after 00:00 UTC).
One way to do this is: the dirauth which is not participating will take the SR value voted by the majority of the participating dirauths and include that in its consensus and sign. We need at least 3 dirauths agreeing on a SR value in order to accept it.
Is this crazy? It shouldn't open the door new attacks, since this doesn't allow a single actor to game it, only the majority could game it.
Yes, that *could* be a way to do it. Have dirauths who don't know the current/previous SRV get it from votes.
I think we all agree that dirauths who don't know the current/previous SRV should get it from the previous consensus (even though this logic has not been implemented yet). Getting it directly from the votes would be a different scheme that maybe we should think about.
Yes, agreed. I have another crazy idea which maybe will help, or if not, hopefully at least will inspire us with another, better idea. Here goes: Divide the consensus into 2 sections with separate signatures: 1) main section - general consensus with all the data as we have it today 2) SR section - which will include previous consensus SR value, current consensus SR value and separate signatures. In the consensus main section we include in addition: Each dirauth participation flag (0 or 1) for current SR value and commits/reveals for the next SR value. Dirauths who don't know previous SR value / current SR value or if the consensus at 00:00 UTC was created or not (disaster or not), simply publish a participation flag 0. They don't vote anything in the SR section. In the consensus SR section we include: - - participating dirauths and their identities (ed25519, RSA) - - previous consensus SR value, current consensus SR value - - separate signatures for this section The number of signatures required for the SR section to be valid will be the exact number of dirauths that published a participation flag 1, but not less than 3 signatures will be accepted. Please don't shoot me if this is terrible - I am only trying hard to ensure a dirauth cannot break consensus accidentally if it is just out of sync and misses some information (edge cases) while also using a logic that won't over complicate stuff. -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (MingW32) iQEcBAEBCAAGBQJWTfziAAoJEIN/pSyBJlsRd2gH/1TgJawIc1dOEabN2kzfn7Q+ RNQQxawge+XM3vLjf4mkkUp+uvUd98Qe49vmT8gHRyeTO/lfjYrZdbNoCiv3iGSE y7FJ2Zg0r6tw32ggRm812tyufcYrFwN1eV8OVxvKz0QUiAhchFFwHZCWGsICU63y NqsWc5mB98Y5ptTnP85Fwdn0rv3nH6lzt95pxjL6/SO0gE4s/QuzeaYAwwxtxkG+ Nx5U5emz8paIsMRa/668LlNG+lwkEuHR3VondZHUTe+OfLc4UqlKNsHNjNEdMoJ6 h4Is4a1mjH/SqSKwTOkrVvtzq5avnP3rgWG3Ukmt/bEdtMQUHZGVKX0SnFqE/ac= =VgM1 -----END PGP SIGNATURE-----
s7r <s7r@sky-ip.org> writes:
Hello,
<snip>
The idea of adding flags in the votes so each dirauth can advertise if it is participating (has an opinion for the <current> SR or not) is great and helps us build more defenses, probably make it easier in the future too if we decide to change anything.
What if the consensus for SR calculation would define majority based on dirauths actually participating (and advertising so with a flag in the vote). Also, the participating or not participating flag should be used per vote/consensus and split into:
a) we know current SR value for today so we vote it or we know previous SR value and we know for sure if we should follow the disaster protocol or not (in case we are about to vote at 01:00 UTC). so We participate in the vote for <current SR>.
b) we are able to participate in this protocol run which will calculate the SR value for next day (after 00:00 UTC) so we send our commits/reveals.
This is useful in case we are a dirauth that joined at 00:30 UTC and we couldn't get the _latest_ consensus (to find out if the 00:00 UTC consensus was created, and if not, previous SR value so we can follow the disaster procedure) we will not have an opinion for the <current> SR value at 01:00 UTC, but we can start participating in the protocol run for the next day - send our commit values. Once we decided on a <current> SR value for that day we save it and vote normally next time.
So, if we have 5 dirauths running/signing consensus in total, out of which only 4 participate in the shared randomness protocol, the 4 participating ones should be able to create a valid consensus themselves with the insurance that the 5th one won't break consensus.
One way to do this is: the dirauth which is not participating will take the SR value voted by the majority of the participating dirauths and include that in its consensus and sign. We need at least 3 dirauths agreeing on a SR value in order to accept it.
Is this crazy? It shouldn't open the door new attacks, since this doesn't allow a single actor to game it, only the majority could game it.
Thanks for the suggestions. Let me try to suggest a procedure here based on your ideas and some other ideas. [Notation: SRV = shared random value] The goal here is to minimize the edge cases during SRV calculation and disaster SRV calculation. The edge cases here appear because there is no clear view on whether other dirauths know the current or previous SRVs, or whether the SRV for this period was ever created. The disaster recovery scenario is especially annoying here. Here are some edge cases for example: * Dirauth boots up at 02:00UTC and the 01:00UTC consensus does not contain any SR information (maybe because not enough SR-enabled dirauths participated at that time). Should the dirauth do the disaster recovery procedure, or just play it cool and put no SR information on the consensus? If it has to do disaster recovery, then what previous SRV does it use (the 01:00UTC consensus did not contain such info)? This type of edge case is my main concern, since with dirauths upgrading and going offline at random times, it's likely that we will eventually create a consensus without SR info in the middle of the protocol run. * Dirauth boots up at 23:55UTC without having a previous consensus. It is supposed to vote and form a 00:00UTC consensus without knowing any previous SRVs. How does it figure out whether all the other dirauths are also bootstrapping, or whether the other dirauths actually know the previous SRVs? Here are some prerequisites for the logic I'm going to suggest. The two first suggestions are useful in any case, I think: - First of all, we treat consensuses as trusted, so dirauths MUST learn previous/current SRVs they didn't know about from any consensus they fetch. - We are also going to assume that we have some sort of "SR flag" on votes to denote whether the dirauth participates in the protocol. - We are introducing another 'status' for shared random values (see [SRVOTE]). Specifically, if a dirauth witnessed a 00:00UTC consensus failing to be created, or it did not contain any SRV information, then it sets the status of "shared-rand-current-value" in its votes to "none". Now we are going to use the SRV lines in the votes as an indicator on how the consensus creation should play out. ================================================================================ Here is some logic for the consensus at 00:00UTC: if majority of votes have disabled the SR flag: then don't write anything SR-related to consensus exit If the majority of votes contain the previous SRV value: then calculate SRV as detailed in section [SRCALC] else: then calculate SRV as in [SRCALC] but with previous_SRV set to 0 And here is some logic for all the other consensuses (to figure out when dirauths should perform the disaster procedure): if majority of votes have disabled the SR flag: then don't write anything SR-related to consensus exit if we know the current SRV: then write it on the consensus exit if the majority of votes have the current SRV status as "none" _AND_ those votes also contain the previous SRV value: then do the disaster SRV procedure else: then don't write anything SR-related to consensus ================================================================================ This _might_ work for fixing a good bunch of edge cases. But is it far too complex? Should we just assume that these things will never happen on the real network and avoid baking additional complexity? What do you think? :/
On 20 Nov (16:06:59), George Kadianakis wrote:
s7r <s7r@sky-ip.org> writes:
Hello,
<snip>
The idea of adding flags in the votes so each dirauth can advertise if it is participating (has an opinion for the <current> SR or not) is great and helps us build more defenses, probably make it easier in the future too if we decide to change anything.
What if the consensus for SR calculation would define majority based on dirauths actually participating (and advertising so with a flag in the vote). Also, the participating or not participating flag should be used per vote/consensus and split into:
a) we know current SR value for today so we vote it or we know previous SR value and we know for sure if we should follow the disaster protocol or not (in case we are about to vote at 01:00 UTC). so We participate in the vote for <current SR>.
b) we are able to participate in this protocol run which will calculate the SR value for next day (after 00:00 UTC) so we send our commits/reveals.
This is useful in case we are a dirauth that joined at 00:30 UTC and we couldn't get the _latest_ consensus (to find out if the 00:00 UTC consensus was created, and if not, previous SR value so we can follow the disaster procedure) we will not have an opinion for the <current> SR value at 01:00 UTC, but we can start participating in the protocol run for the next day - send our commit values. Once we decided on a <current> SR value for that day we save it and vote normally next time.
So, if we have 5 dirauths running/signing consensus in total, out of which only 4 participate in the shared randomness protocol, the 4 participating ones should be able to create a valid consensus themselves with the insurance that the 5th one won't break consensus.
One way to do this is: the dirauth which is not participating will take the SR value voted by the majority of the participating dirauths and include that in its consensus and sign. We need at least 3 dirauths agreeing on a SR value in order to accept it.
Is this crazy? It shouldn't open the door new attacks, since this doesn't allow a single actor to game it, only the majority could game it.
Thanks for the suggestions.
Let me try to suggest a procedure here based on your ideas and some other ideas.
[Notation: SRV = shared random value]
The goal here is to minimize the edge cases during SRV calculation and disaster SRV calculation. The edge cases here appear because there is no clear view on whether other dirauths know the current or previous SRVs, or whether the SRV for this period was ever created. The disaster recovery scenario is especially annoying here.
Here are some edge cases for example:
* Dirauth boots up at 02:00UTC and the 01:00UTC consensus does not contain any SR information (maybe because not enough SR-enabled dirauths participated at that time).
Should the dirauth do the disaster recovery procedure, or just play it cool and put no SR information on the consensus? If it has to do disaster recovery, then what previous SRV does it use (the 01:00UTC consensus did not contain such info)?
This type of edge case is my main concern, since with dirauths upgrading and going offline at random times, it's likely that we will eventually create a consensus without SR info in the middle of the protocol run.
* Dirauth boots up at 23:55UTC without having a previous consensus. It is supposed to vote and form a 00:00UTC consensus without knowing any previous SRVs. How does it figure out whether all the other dirauths are also bootstrapping, or whether the other dirauths actually know the previous SRVs?
Here are some prerequisites for the logic I'm going to suggest. The two first suggestions are useful in any case, I think:
- First of all, we treat consensuses as trusted, so dirauths MUST learn previous/current SRVs they didn't know about from any consensus they fetch.
Yes ++. A dirauth booting up should always try to learn the current and previous SRV from the latest consensus (< 24h) and update the disk state accordingly _even_ if the disk state has SRV values in there. We should trust the consensus voted by majority before our disk state imo.
- We are also going to assume that we have some sort of "SR flag" on votes to denote whether the dirauth participates in the protocol.
The requirements for having that flag "on" or "off" eludes me a bit. I assume that this SR flag is "on" when a dirauth thinks its able to compute a valid SRV that is I have enough commits. We can't make "having the previous SRV" a requirement else we will never bootstrap properly ever since in the first runs, previous SRV is alway 0.
- We are introducing another 'status' for shared random values (see [SRVOTE]).
Specifically, if a dirauth witnessed a 00:00UTC consensus failing to be created, or it did not contain any SRV information, then it sets the status of "shared-rand-current-value" in its votes to "none".
Hrm... I'm wondering here if "none" status is instead the same of having the dirauth putting the disaster value in the vote? I would argue that a dirauth should _always_ try to compute a SR value at any time (even when booting). Between having no line because we couldn't compute due to lack of commits or a line that is the disaster, I think the former simplifies things that is "We always have a SRV value at 00:00 from a dirauth". Here is what I propose: 1) Like you said, we always try to learn SRV values from previous consensus. If we can't get one from a consensus or our state, compute disaster at 00:00. 2) We do _not_ use a SR flag for vote, a dirauth always tries to compute a current SRV value at 00:00. If it's 13:00, it simply doesn't put anything in the vote since no SRV data. The big issue I see here is when a dirauth does _not_ have the previous SRV. Without it, both disaster and current SRV computation will end up not matching the majority. So let's explore this binary state: - I have the previous SRV (either I can get it from my state or consensus). This seems a non issue, dirauth will use it, carry it in the vote and compute the current SRV if enough commits have been seen. At 00:00, if majority wasn't reached for the current SRV value, we have a consensus without it which is a valid use case but we at least have the previous one in the consensus flagged as non-fresh so it can be used for disaster or SRV computation at the next protocol run. - I don't have a previous SRV (couldn't get it in the latest consensus and I have _no_ disk state). For instance, if this happens at 23:30, a dirauth won't have the chance to participate in the SR protocol because it didn't see any commits to compute SRV value thus disaster mode engage. If that dirauth was the 5th one out of 9 (meaning the majority breaker), we end up with no SRV values at all at 00:00 (not even the previous SRV since only 4/9 had it). So a new protocol run starts, we'll end up with a valid current SRV in 24 hours and both values in 48 hours. Essentially, we end up back in bootstrap mode. IMPORTANT note here: I think a dirauth MUST NOT keep any SRV values that aren't in the 00:00 consensus. Question is, how big of a deal it is to have this issue where if we don't reach majority because a dirauth rebooted and for some magical reason didn't get the latest consensus to at least get the previous SRV, we return in bootstrap? Cheers! David
Now we are going to use the SRV lines in the votes as an indicator on how the consensus creation should play out.
================================================================================
Here is some logic for the consensus at 00:00UTC:
if majority of votes have disabled the SR flag: then don't write anything SR-related to consensus exit
If the majority of votes contain the previous SRV value: then calculate SRV as detailed in section [SRCALC] else: then calculate SRV as in [SRCALC] but with previous_SRV set to 0
And here is some logic for all the other consensuses (to figure out when dirauths should perform the disaster procedure):
if majority of votes have disabled the SR flag: then don't write anything SR-related to consensus exit
if we know the current SRV: then write it on the consensus exit
if the majority of votes have the current SRV status as "none" _AND_ those votes also contain the previous SRV value: then do the disaster SRV procedure else: then don't write anything SR-related to consensus
================================================================================
This _might_ work for fixing a good bunch of edge cases. But is it far too complex?
Should we just assume that these things will never happen on the real network and avoid baking additional complexity? What do you think? :/
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On 20 Nov (10:19:07), David Goulet wrote:
On 20 Nov (16:06:59), George Kadianakis wrote:
s7r <s7r@sky-ip.org> writes:
Hello,
<snip>
The idea of adding flags in the votes so each dirauth can advertise if it is participating (has an opinion for the <current> SR or not) is great and helps us build more defenses, probably make it easier in the future too if we decide to change anything.
What if the consensus for SR calculation would define majority based on dirauths actually participating (and advertising so with a flag in the vote). Also, the participating or not participating flag should be used per vote/consensus and split into:
a) we know current SR value for today so we vote it or we know previous SR value and we know for sure if we should follow the disaster protocol or not (in case we are about to vote at 01:00 UTC). so We participate in the vote for <current SR>.
b) we are able to participate in this protocol run which will calculate the SR value for next day (after 00:00 UTC) so we send our commits/reveals.
This is useful in case we are a dirauth that joined at 00:30 UTC and we couldn't get the _latest_ consensus (to find out if the 00:00 UTC consensus was created, and if not, previous SR value so we can follow the disaster procedure) we will not have an opinion for the <current> SR value at 01:00 UTC, but we can start participating in the protocol run for the next day - send our commit values. Once we decided on a <current> SR value for that day we save it and vote normally next time.
So, if we have 5 dirauths running/signing consensus in total, out of which only 4 participate in the shared randomness protocol, the 4 participating ones should be able to create a valid consensus themselves with the insurance that the 5th one won't break consensus.
One way to do this is: the dirauth which is not participating will take the SR value voted by the majority of the participating dirauths and include that in its consensus and sign. We need at least 3 dirauths agreeing on a SR value in order to accept it.
Is this crazy? It shouldn't open the door new attacks, since this doesn't allow a single actor to game it, only the majority could game it.
Thanks for the suggestions.
Let me try to suggest a procedure here based on your ideas and some other ideas.
[Notation: SRV = shared random value]
The goal here is to minimize the edge cases during SRV calculation and disaster SRV calculation. The edge cases here appear because there is no clear view on whether other dirauths know the current or previous SRVs, or whether the SRV for this period was ever created. The disaster recovery scenario is especially annoying here.
Here are some edge cases for example:
* Dirauth boots up at 02:00UTC and the 01:00UTC consensus does not contain any SR information (maybe because not enough SR-enabled dirauths participated at that time).
Should the dirauth do the disaster recovery procedure, or just play it cool and put no SR information on the consensus? If it has to do disaster recovery, then what previous SRV does it use (the 01:00UTC consensus did not contain such info)?
This type of edge case is my main concern, since with dirauths upgrading and going offline at random times, it's likely that we will eventually create a consensus without SR info in the middle of the protocol run.
* Dirauth boots up at 23:55UTC without having a previous consensus. It is supposed to vote and form a 00:00UTC consensus without knowing any previous SRVs. How does it figure out whether all the other dirauths are also bootstrapping, or whether the other dirauths actually know the previous SRVs?
Here are some prerequisites for the logic I'm going to suggest. The two first suggestions are useful in any case, I think:
- First of all, we treat consensuses as trusted, so dirauths MUST learn previous/current SRVs they didn't know about from any consensus they fetch.
Yes ++.
A dirauth booting up should always try to learn the current and previous SRV from the latest consensus (< 24h) and update the disk state accordingly _even_ if the disk state has SRV values in there. We should trust the consensus voted by majority before our disk state imo.
- We are also going to assume that we have some sort of "SR flag" on votes to denote whether the dirauth participates in the protocol.
The requirements for having that flag "on" or "off" eludes me a bit. I assume that this SR flag is "on" when a dirauth thinks its able to compute a valid SRV that is I have enough commits. We can't make "having the previous SRV" a requirement else we will never bootstrap properly ever since in the first runs, previous SRV is alway 0.
- We are introducing another 'status' for shared random values (see [SRVOTE]).
Specifically, if a dirauth witnessed a 00:00UTC consensus failing to be created, or it did not contain any SRV information, then it sets the status of "shared-rand-current-value" in its votes to "none".
Hrm... I'm wondering here if "none" status is instead the same of having the dirauth putting the disaster value in the vote?
I would argue that a dirauth should _always_ try to compute a SR value at any time (even when booting). Between having no line because we couldn't compute due to lack of commits or a line that is the disaster, I think the former simplifies things that is "We always have a SRV value at 00:00 from a dirauth".
Here is what I propose:
1) Like you said, we always try to learn SRV values from previous consensus. If we can't get one from a consensus or our state, compute disaster at 00:00.
2) We do _not_ use a SR flag for vote, a dirauth always tries to compute a current SRV value at 00:00. If it's 13:00, it simply doesn't put anything in the vote since no SRV data.
The big issue I see here is when a dirauth does _not_ have the previous SRV. Without it, both disaster and current SRV computation will end up not matching the majority. So let's explore this binary state:
- I have the previous SRV (either I can get it from my state or consensus).
This seems a non issue, dirauth will use it, carry it in the vote and compute the current SRV if enough commits have been seen. At 00:00, if majority wasn't reached for the current SRV value, we have a consensus without it which is a valid use case but we at least have the previous one in the consensus flagged as non-fresh so it can be used for disaster or SRV computation at the next protocol run.
- I don't have a previous SRV (couldn't get it in the latest consensus and I have _no_ disk state).
For instance, if this happens at 23:30, a dirauth won't have the chance to participate in the SR protocol because it didn't see any commits to compute SRV value thus disaster mode engage.
If that dirauth was the 5th one out of 9 (meaning the majority breaker), we end up with no SRV values at all at 00:00 (not even the previous SRV since only 4/9 had it). So a new protocol run starts, we'll end up with a valid current SRV in 24 hours and both values in 48 hours. Essentially, we end up back in bootstrap mode.
IMPORTANT note here: I think a dirauth MUST NOT keep any SRV values that aren't in the 00:00 consensus.
Question is, how big of a deal it is to have this issue where if we don't reach majority because a dirauth rebooted and for some magical reason didn't get the latest consensus to at least get the previous SRV, we return in bootstrap?
Ok more thoughts on this, asn asked that I make an algorithm so here is a try at that: -- Booting up Conditions -- - A dirauth MUST try to acquire both previous and current SRV from the last consensus. If it can't, get it from disk state. If nothing is available, none exists for this protocol run. -- Algorithm -- At 16:00 (arbitrary time which is _not_ the current SRV calculation): # Voting if dirauth has previous SRV: put it in vote if dirauth has current SRV: put it in vote Output: Consensus is created # Consensus (This goes for both previous and current SRV) if SRV in consensus: dirauth MUST keep it even if the one they have doesn't match. Majority has decided what should be used. else: dirauth MUST discard the SRV it has. At 00:00 # Voting if current SRV can't be created because lack of commits: current SRV == disaster mode (previous SRV or not) else: compute current SRV (with or without a previous SRV) (Proceed like the 16:00 period) # Consensus if majority agrees on SR value(s): put in consensus else: No SR value(s) in consensus Output: consensus is created (Proceed like the 16:00 period) Side effect of only keeping SRV that are in the consensus. If one voting round goes bad for X reason and consensus end up with no SRV, we end up in bootstrapping mode that is no previous nor current SRV in the consensus which is problematic because for 48 hours, we won't have a previous SRV which is the one used by everyone. I don't see a way to get out of this because consensus is decided from the votes deterministically thus if not enough vote for SR values, we'll end up with a consensus with none so this is why client/HS have to fallback to a disaster value by themselves I think which can NOT be based on the previous SRV. David
Cheers! David
Now we are going to use the SRV lines in the votes as an indicator on how the consensus creation should play out.
================================================================================
Here is some logic for the consensus at 00:00UTC:
if majority of votes have disabled the SR flag: then don't write anything SR-related to consensus exit
If the majority of votes contain the previous SRV value: then calculate SRV as detailed in section [SRCALC] else: then calculate SRV as in [SRCALC] but with previous_SRV set to 0
And here is some logic for all the other consensuses (to figure out when dirauths should perform the disaster procedure):
if majority of votes have disabled the SR flag: then don't write anything SR-related to consensus exit
if we know the current SRV: then write it on the consensus exit
if the majority of votes have the current SRV status as "none" _AND_ those votes also contain the previous SRV value: then do the disaster SRV procedure else: then don't write anything SR-related to consensus
================================================================================
This _might_ work for fixing a good bunch of edge cases. But is it far too complex?
Should we just assume that these things will never happen on the real network and avoid baking additional complexity? What do you think? :/
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On 20/11/15 16:24, David Goulet wrote:
# Consensus (This goes for both previous and current SRV) if SRV in consensus: dirauth MUST keep it even if the one they have doesn't match. Majority has decided what should be used. else: dirauth MUST discard the SRV it has.
This seems like an excellent idea. Relying on the consensus ensures that no matter what crazy shit happens to the individual dirauths, they can eventually converge on the same previous and current SRV values (or agree that no such SRV values exist) by sharing the valid consensus documents they've seen.
Side effect of only keeping SRV that are in the consensus. If one voting round goes bad for X reason and consensus end up with no SRV, we end up in bootstrapping mode that is no previous nor current SRV in the consensus which is problematic because for 48 hours, we won't have a previous SRV which is the one used by everyone.
I don't see a way to get out of this because consensus is decided from the votes deterministically thus if not enough vote for SR values, we'll end up with a consensus with none so this is why client/HS have to fallback to a disaster value by themselves I think which can NOT be based on the previous SRV.
If there's no consensus on a fresh SRV for a while, clients and relays can keep producing emergency SRVs by hashing the last fresh SRV they know about, right? It doesn't have to be yesterday's SRV - if the last fresh SRV was produced a week ago, they keep hashing based on that (which is not ideal of course). As above, using the consensus seems like a good idea because it allows the network to converge on the same values just by sharing valid consensus documents. Cheers, Michael
On 21 Nov 2015, at 04:14, Michael Rogers <michael@briarproject.org> wrote:
On 20/11/15 16:24, David Goulet wrote:
# Consensus (This goes for both previous and current SRV) if SRV in consensus: dirauth MUST keep it even if the one they have doesn't match. Majority has decided what should be used. else: dirauth MUST discard the SRV it has.
This seems like an excellent idea. Relying on the consensus ensures that no matter what crazy shit happens to the individual dirauths, they can eventually converge on the same previous and current SRV values (or agree that no such SRV values exist) by sharing the valid consensus documents they've seen.
Side effect of only keeping SRV that are in the consensus. If one voting round goes bad for X reason and consensus end up with no SRV, we end up in bootstrapping mode that is no previous nor current SRV in the consensus which is problematic because for 48 hours, we won't have a previous SRV which is the one used by everyone.
I don't see a way to get out of this because consensus is decided from the votes deterministically thus if not enough vote for SR values, we'll end up with a consensus with none so this is why client/HS have to fallback to a disaster value by themselves I think which can NOT be based on the previous SRV.
If there's no consensus on a fresh SRV for a while, clients and relays can keep producing emergency SRVs by hashing the last fresh SRV they know about, right? It doesn't have to be yesterday's SRV - if the last fresh SRV was produced a week ago, they keep hashing based on that (which is not ideal of course). As above, using the consensus seems like a good idea because it allows the network to converge on the same values just by sharing valid consensus documents.
If there's no consensus on a fresh SRV, why not just use the disaster recovery procedure? That is: # Consensus if majority agrees on SR value(s): put in consensus else: put disaster recovery SR value (based on last round's agreed SR value, if any) in consensus Output: consensus is created (Proceed like the 16:00 period) That way, clients and relays don't need to do anything special: there will always be a SRV in the consensus. This means that the SR consensus method will always produce a SR value, which I believe is a much better property than occasionally failing to produce a value. Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
Tim Wilson-Brown - teor <teor2345@gmail.com> writes:
On 21 Nov 2015, at 04:14, Michael Rogers <michael@briarproject.org> wrote:
On 20/11/15 16:24, David Goulet wrote:
# Consensus (This goes for both previous and current SRV) if SRV in consensus: dirauth MUST keep it even if the one they have doesn't match. Majority has decided what should be used. else: dirauth MUST discard the SRV it has.
This seems like an excellent idea. Relying on the consensus ensures that no matter what crazy shit happens to the individual dirauths, they can eventually converge on the same previous and current SRV values (or agree that no such SRV values exist) by sharing the valid consensus documents they've seen.
Side effect of only keeping SRV that are in the consensus. If one voting round goes bad for X reason and consensus end up with no SRV, we end up in bootstrapping mode that is no previous nor current SRV in the consensus which is problematic because for 48 hours, we won't have a previous SRV which is the one used by everyone.
I don't see a way to get out of this because consensus is decided from the votes deterministically thus if not enough vote for SR values, we'll end up with a consensus with none so this is why client/HS have to fallback to a disaster value by themselves I think which can NOT be based on the previous SRV.
If there's no consensus on a fresh SRV for a while, clients and relays can keep producing emergency SRVs by hashing the last fresh SRV they know about, right? It doesn't have to be yesterday's SRV - if the last fresh SRV was produced a week ago, they keep hashing based on that (which is not ideal of course). As above, using the consensus seems like a good idea because it allows the network to converge on the same values just by sharing valid consensus documents.
If there's no consensus on a fresh SRV, why not just use the disaster recovery procedure?
That is:
# Consensus if majority agrees on SR value(s): put in consensus else: put disaster recovery SR value (based on last round's agreed SR value, if any) in consensus
Output: consensus is created
(Proceed like the 16:00 period)
True. However, if the majority cannot agree on SR values, how can a majority be formed to agree on disaster recovery SRVs? The problem here is that the disaster SRVs are derived from the previous SRV.
That way, clients and relays don't need to do anything special: there will always be a SRV in the consensus.
This means that the SR consensus method will always produce a SR value, which I believe is a much better property than occasionally failing to produce a value.
Indeed, that's something very important. Yesterday, we were discussing with David how bad it would be if 2-3 SR-enabled dirauths drop offline during voting, and the rest dirauths generate a consensus without an SR value (because the consensus method requirement for SR failed or something). In this case, some clients will have a consensus with an SR value, and some other clients will have a consensus with no SR value. Those two client sets will use a different formula to connect to hidden services, bringing out terrible reachability consequences. I wonder what's the solution here. We don't want a single consensus to break reachability for all hidden services. I wonder what should we do? Should we just make it ultra unlikely that a consensus will be generated without SR values? For exmaple, we could require every dirauth to participate in the protocol so that we either have a consensus with SR or no consensus at all. This will slow down deployment, but it might make the system more bullet proof.
On 21/11/15 12:05, George Kadianakis wrote:
If there's no consensus on a fresh SRV, why not just use the disaster recovery procedure?
That is:
# Consensus if majority agrees on SR value(s): put in consensus else: put disaster recovery SR value (based on last round's agreed SR value, if any) in consensus
Output: consensus is created
(Proceed like the 16:00 period)
True. However, if the majority cannot agree on SR values, how can a majority be formed to agree on disaster recovery SRVs? The problem here is that the disaster SRVs are derived from the previous SRV.
Would it help if we defined the disaster SRV as being derived from the last SRV for which there was a consensus, rather than from the previous round's SRV? That would allow the network to converge on the same sequence of disaster SRVs, and then switch back from disaster mode to business-as-usual mode, just by sharing valid consensuses.
That way, clients and relays don't need to do anything special: there will always be a SRV in the consensus.
This means that the SR consensus method will always produce a SR value, which I believe is a much better property than occasionally failing to produce a value.
Indeed, that's something very important.
Yesterday, we were discussing with David how bad it would be if 2-3 SR-enabled dirauths drop offline during voting, and the rest dirauths generate a consensus without an SR value (because the consensus method requirement for SR failed or something).
In this case, some clients will have a consensus with an SR value, and some other clients will have a consensus with no SR value. Those two client sets will use a different formula to connect to hidden services, bringing out terrible reachability consequences.
When the failed dirauths come back online they should accept the consensus that was generated in their absence. So in the following round, all dirauths will vote for an SRV based on the one that was agreed while the failed dirauths were offline. Cheers, Michael
I wonder what's the solution here. We don't want a single consensus to break reachability for all hidden services. I wonder what should we do? Should we just make it ultra unlikely that a consensus will be generated without SR values? For exmaple, we could require every dirauth to participate in the protocol so that we either have a consensus with SR or no consensus at all. This will slow down deployment, but it might make the system more bullet proof. _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Hi George, On 11/12/15, George Kadianakis <desnacked@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-c...
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. All the best, Jacob [0] http://projectbullrun.org/dual-ec/ext-rand.html
On 19 Nov (14:30:47), Jacob Appelbaum wrote:
Hi George,
On 11/12/15, George Kadianakis <desnacked@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-c...
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. Thanks! David
All the best, Jacob
[0] http://projectbullrun.org/dual-ec/ext-rand.html _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
David Goulet <dgoulet@ev0ke.net> writes:
On 19 Nov (14:30:47), Jacob Appelbaum wrote:
Hi George,
On 11/12/15, George Kadianakis <desnacked@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-c...
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.
On 20 Nov 2015, at 10:59, George Kadianakis <desnacked@riseup.net> wrote:
David Goulet <dgoulet@ev0ke.net <mailto:dgoulet@ev0ke.net>> writes:
On 19 Nov (14:30:47), Jacob Appelbaum wrote:
Hi George,
On 11/12/15, George Kadianakis <desnacked@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-c...
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? It would look like: RN = 255-bit random number REVEAL_VALUE = H("derive-reveal" | RN) COMMIT_VALUE = H("derive-commit" | REVEAL_VALUE) Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
On 11/21/15, Tim Wilson-Brown - teor <teor2345@gmail.com> wrote:
On 20 Nov 2015, at 10:59, George Kadianakis <desnacked@riseup.net> wrote:
David Goulet <dgoulet@ev0ke.net <mailto:dgoulet@ev0ke.net>> writes:
On 19 Nov (14:30:47), Jacob Appelbaum wrote:
Hi George,
On 11/12/15, George Kadianakis <desnacked@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-c...
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
On 22 Nov 2015, at 01:09, Jacob Appelbaum <jacob@appelbaum.net> wrote:
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?
I tend to agree - there's no need for a distinguishing value here. As far as I understand, a distinguishing value is used to make hashes used for different purposes unique, even if they have the same input data. It also means that any precomputed matches or hash confirmations have to be done for each hash and purpose. But random inputs don't suffer from either of these issues (the input is random, and precomputing 256 random bits is infeasible). Also, adding a distinguishing value would mean that more than 256 bits are hashed into 256 bits, which I assume would be slower, for no net gain.
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.
Ugh, I copy-pasted the original mistake. You're right, it should be 256.
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.
I'll see if I can write a patch for this. It's something we should do with all our random values, not just the ones for prop250. Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
participants (6)
-
David Goulet -
George Kadianakis -
Jacob Appelbaum -
Michael Rogers -
s7r -
Tim Wilson-Brown - teor