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

[Nick Mathewson]

On Tue, Sep 19, 2017 at 8:13 PM, Ian Goldberg <iang at 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"