[tor-dev] Padding prop224 REND1 cells to blend them with legacy cells

[George Kadianakis]

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!!! :)

[Ian Goldberg]

Resending from a subscribed address.

Post by George Kadianakis
Hello Ian, (and other cryptographers on the list)
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.
RC Rendezvous cookie [20 octets]
g^y Diffie-Hellman [128 octets]
KH Handshake digest [20 octets]
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?

[Nick Mathewson]

Post by Ian Goldberg
Resending from a subscribed address.

Post by George Kadianakis
Hello Ian, (and other cryptographers on the list)
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.
RC Rendezvous cookie [20 octets]
g^y Diffie-Hellman [128 octets]
KH Handshake digest [20 octets]
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"

[Ian Goldberg]

Post by Nick Mathewson

Post by Ian Goldberg
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?

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
"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.

[teor]

Post by George Kadianakis
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.
...
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?

What's the threat model here?

I ask because regardless of whether the RENDEZVOUS1 cell plaintext is
distinguishable between v2 and v3, the rend point can distinguish v2 and
v3 using this one neat trick:
* if the service extends using TAP, the protocol is v2
* if the service extends using ntor, the protocol is v3

v2 and v3 are also distinguishable in these cases:
* intro points, using the client extend
* Tor2web and single onion services, except that they connect directly,
then do a TAP or ntor handshake.

That said, if you want to make v3 and future (v4+) rend protocols
indistinguishable, then it might be a good idea to pad the entire cell
with random bytes. That allows future protocols to add fields safely, as
long as they are encrypted in a way that is indistinguishable from
random.

T
--
Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B
ricochet:ekmygaiu4rzgsk6n
------------------------------------------------------------------------

[George Kadianakis]

Post by teor

Post by George Kadianakis
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.
...
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?

What's the threat model here?
I ask because regardless of whether the RENDEZVOUS1 cell plaintext is
distinguishable between v2 and v3, the rend point can distinguish v2 and
* if the service extends using TAP, the protocol is v2
* if the service extends using ntor, the protocol is v3

Thanks for the discussion and research, Ian and teor!

I summarized the findings here: https://trac.torproject.org/projects/tor/ticket/23420#comment:5

Not sure what's the right approach here.

Perhaps I'm fine with doing nothing at this point, and figuring this out
in the future if v4 ever comes.

Cheers!