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

[Ian Goldberg]

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?