[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

[Watson Ladd]

On Sat, May 7, 2016 at 12:41 PM, lukep <lukep at tutanota.com> wrote:
> Jeff Burdges <burdges at ...> writes:
>
>>
>> On Fri, 2016-05-06 at 19:17 +0000, isis wrote:
>>
>> >   --- Description of the Newhope internal functions ---
>> >
>> >   gen_a(SEED seed) receives as input a 32-byte (public) seed.  It expands
>> >   this seed through SHAKE-128 from the FIPS202 standard. The output of
> SHAKE-128
>> >   is considered a sequence of 16-bit little-endian integers. This
> sequence is
>> >   used to initialize the coefficients of the returned polynomial from
> the least
>> >   significant (coefficient of X^0) to the most significant (coefficient of
>> >   X^1023) coefficient. For each of the 16-bit integers first eliminate the
>> >   highest two bits (to make it a 14-bit integer) and then use it as the next
>> >   coefficient if it is smaller than q=12289.
>> >   Note that the amount of output required from SHAKE to initialize all 1024
>> >   coefficients of the polynomial varies depending on the input seed.
>> >   Note further that this function does not process any secret data and
> thus does
>> >   not need any timing-attack protection.
>>
>> Aren't the seed and polynomial a actually secret for negotiation with
>> any node after your guard?
>>
>> An adversary who can do a timing attack on a user's tor process would
>> gain some deanonymizing information from knowing which a elements get
>> skipped.  I suppose this adversary has already nailed the user via
>> correlation attack, but maybe worth rewording at least.
>>
>> And maybe an adversary could employ different attack infrastructure if
>> they can learn some skipped elements of a.
>
> I agree with Jeff: usually in Ring-LWE, a isn't a secret value, so timing
> attacks don't matter. But when the value of a is shared only between Alice
> and Bob, then it is identifying information which could be used in a
> deanonymyzation attack, so it should be viewed as secret. So it's generation
> should be secure against timing attacks - the same amount of SHAKE output
> should be consumed every time.

I'm not sure I understand the concern here. An attacker sees that we
got unlucky: that doesn't help them with recovering SEED under mild
assumptions we need anyway about SHAKE indistinguishability.

>
> It's hard to guarantee that any fixed, finite amount of SHAKE output will be
> sufficient for any rejection sampling method like gen_a. So maybe an
> arithmetic coding like scheme could be used? That would get much closer to
> log_2(12289) bits being used for each coefficient. Or let a be a system-wide
> parameter changing say on a daily basis? (Cuts down marginally on bandwidth
> and computation time at the expense of a many-for-the-price-of-one attack so
> as others have observed probably not a good idea).
>
> rec(poly f, NEWHOPE_REC r) / Decode(v0,v1,v2,v3):
> This function operates on secret data - the values of t0,t1,t2,t3 must be
> kept secret, so must also be timing-attack-resistant. Also the calculation
> of t is incorrect as stated (copy-and-paste error; needs to be a function of
> v1,v2,v3,t1,t2,t3 etc.)
>
> If I ever get chance to play with the code I'd like to have a go a producing
> some test vectors.
>
> Thanks isis for this, it looks really good, I look forward to seeing a
> similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !)
>
> -- lukep
>
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.