Re: [tor-dev] Padding prop224 REND1 cells to blend them with legacy cells
Resending from a subscribed address. On Tue, Sep 19, 2017 at 05:44:46PM +0300, George Kadianakis wrote:
Hello Ian, (and other cryptographers on the list)
here is a quick question which you might be able to answer super fast:
Legacy RENDEZVOUS1 cells are bigger than the prop224 ones. The prop224 spec suggests we pad the new cells so that they look similar in size to the legacy ones.
Here is how the legacy ones look like:
RC Rendezvous cookie [20 octets] g^y Diffie-Hellman [128 octets] KH Handshake digest [20 octets]
Here is how the prop224 ones look like:
RENDEZVOUS_COOKIE [20 bytes] HANDSHAKE_INFO [64 bytes]
The suggestion is to pad the prop224 cells to 168 bytes using random data.
Would that work? My main question is whether the g^y part of the legacy cell has any distinguishers that could distinguish it from random data. It's encoded using OpenSSL's BN_bn2bin() and it's a 1024 bit DH public key. Are there any algebraic or openssl structure distinguishers we should be worrying about, or is random data sufficient to mask it out?
Thanks!!! :)
Is your goal that someone who sees the *plaintext* of that cell won't be able to tell if it's a legacy RENDEZVOUS1 cell or a new one? If so, life is a bit complicated, since the g^y field will always be in the prime-order subgroup. (Note: I'm not actually 100% sure Tor uses a generator of the prime-order subgroup for g in this part of the spec. But it should have, and so hopefully did.) If HANDSHAKE_INFO || PADDING_64 (the latter being the first 64 bytes of the padding) is _not_ in the prime-order subgroup, the observer will be sure it's a prop224 cell. If it _is_, the observer can't tell. If that's undesirable, you could always insist that PADDING_64 be chosen such that HANDSHAKE_INFO || PADDING_64 _is_ in the prime-order subgroup. Raise it to the power of the prime order q to check; if the result is 1, you're good. You'll need to try on average (p-1)/q random values of PADDING_64 before you get a good one. (NOTE: *NOT* CONSTANT TIME.) If p = 2q+1, that's just 2, so not *terrible*, but 2 1024-bit modexps might still be annoying. If for some reason p is a DSA modululus or something bizarre like that, life is much more annoying. (I hope it's not.) This is all assuming p is of the form 2^1024 - (some number at most say 2^960), so that HANDSHAKE_INFO || PADDING_64 won't be larger than p itself, which would be another problem. To be sure, what are the g and p values used in this particular Diffie-Hellman?
On Tue, Sep 19, 2017 at 8:13 PM, Ian Goldberg <iang@cs.uwaterloo.ca> wrote:
Resending from a subscribed address.
On Tue, Sep 19, 2017 at 05:44:46PM +0300, George Kadianakis wrote:
Hello Ian, (and other cryptographers on the list)
here is a quick question which you might be able to answer super fast:
Legacy RENDEZVOUS1 cells are bigger than the prop224 ones. The prop224 spec suggests we pad the new cells so that they look similar in size to the legacy ones.
Here is how the legacy ones look like:
RC Rendezvous cookie [20 octets] g^y Diffie-Hellman [128 octets] KH Handshake digest [20 octets]
Here is how the prop224 ones look like:
RENDEZVOUS_COOKIE [20 bytes] HANDSHAKE_INFO [64 bytes]
The suggestion is to pad the prop224 cells to 168 bytes using random data.
Would that work? My main question is whether the g^y part of the legacy cell has any distinguishers that could distinguish it from random data. It's encoded using OpenSSL's BN_bn2bin() and it's a 1024 bit DH public key. Are there any algebraic or openssl structure distinguishers we should be worrying about, or is random data sufficient to mask it out?
Thanks!!! :)
Is your goal that someone who sees the *plaintext* of that cell won't be able to tell if it's a legacy RENDEZVOUS1 cell or a new one? If so, life is a bit complicated, since the g^y field will always be in the prime-order subgroup. (Note: I'm not actually 100% sure Tor uses a generator of the prime-order subgroup for g in this part of the spec. But it should have, and so hopefully did.)
If HANDSHAKE_INFO || PADDING_64 (the latter being the first 64 bytes of the padding) is _not_ in the prime-order subgroup, the observer will be sure it's a prop224 cell. If it _is_, the observer can't tell.
If that's undesirable, you could always insist that PADDING_64 be chosen such that HANDSHAKE_INFO || PADDING_64 _is_ in the prime-order subgroup. Raise it to the power of the prime order q to check; if the result is 1, you're good. You'll need to try on average (p-1)/q random values of PADDING_64 before you get a good one. (NOTE: *NOT* CONSTANT TIME.) If p = 2q+1, that's just 2, so not *terrible*, but 2 1024-bit modexps might still be annoying. If for some reason p is a DSA modululus or something bizarre like that, life is much more annoying. (I hope it's not.) This is all assuming p is of the form 2^1024 - (some number at most say 2^960), so that HANDSHAKE_INFO || PADDING_64 won't be larger than p itself, which would be another problem.
To be sure, what are the g and p values used in this particular Diffie-Hellman?
This is the old, old, old group: For Diffie-Hellman, unless otherwise specified, we use a generator (g) of 2. For the modulus (p), we use the 1024-bit safe prime from rfc2409 section 6.2 whose hex representation is: "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" "8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B" "302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9" "A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE6" "49286651ECE65381FFFFFFFFFFFFFFFF"
On Tue, Sep 19, 2017 at 08:29:41PM -0400, Nick Mathewson wrote:
Is your goal that someone who sees the *plaintext* of that cell won't be able to tell if it's a legacy RENDEZVOUS1 cell or a new one? If so, life is a bit complicated, since the g^y field will always be in the prime-order subgroup. (Note: I'm not actually 100% sure Tor uses a generator of the prime-order subgroup for g in this part of the spec. But it should have, and so hopefully did.)
If HANDSHAKE_INFO || PADDING_64 (the latter being the first 64 bytes of the padding) is _not_ in the prime-order subgroup, the observer will be sure it's a prop224 cell. If it _is_, the observer can't tell.
If that's undesirable, you could always insist that PADDING_64 be chosen such that HANDSHAKE_INFO || PADDING_64 _is_ in the prime-order subgroup. Raise it to the power of the prime order q to check; if the result is 1, you're good. You'll need to try on average (p-1)/q random values of PADDING_64 before you get a good one. (NOTE: *NOT* CONSTANT TIME.) If p = 2q+1, that's just 2, so not *terrible*, but 2 1024-bit modexps might still be annoying. If for some reason p is a DSA modululus or something bizarre like that, life is much more annoying. (I hope it's not.) This is all assuming p is of the form 2^1024 - (some number at most say 2^960), so that HANDSHAKE_INFO || PADDING_64 won't be larger than p itself, which would be another problem.
To be sure, what are the g and p values used in this particular Diffie-Hellman?
This is the old, old, old group:
For Diffie-Hellman, unless otherwise specified, we use a generator (g) of 2. For the modulus (p), we use the 1024-bit safe prime from rfc2409 section 6.2 whose hex representation is:
"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" "8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B" "302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9" "A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE6" "49286651ECE65381FFFFFFFFFFFFFFFF"
I confirm that both things I supposed about the group above are true: g generates the prime-order subgroup, and p is near to 2^1024.
participants (2)
-
Ian Goldberg -
Nick Mathewson