[tor-dev] Padding prop224 REND1 cells to blend them with legacy cells
Ian Goldberg
iang at cs.uwaterloo.ca
Wed Sep 20 00:13:54 UTC 2017
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?
More information about the tor-dev
mailing list