On Sat, May 7, 2016 at 12:41 PM, lukep <[email protected]> wrote: > Jeff Burdges <burdges@...> 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 > [email protected] > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev -- "Man is born free, but everywhere he is in chains". --Rousseau. _______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
