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

[lukep]

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. 

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