Jeff Burdges transcribed 3.1K bytes:
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.
Hey Jeff,
At first, I wasn't convinced that guarding against an adversary who is both capable to run a spy process on a client machine, as well as be the middle/exit relay in the client's circuit, was within Tor's threat model. However, if it isn't within our threat model, it should be, because e.g. who knows what crap JS a browser is executing. Let's just assume this is within the model.
I haven't given it much thought yet, but the performance cost to making polynomial initialisation constant time may not actually be so bad. My naïve, I'm-still-finishing-my-breakfast solution would be to oversample (say 2048 uint16_ts) from SHAKE-128, shove them into a stable sorting network with a comparator which says "not equal" for x[i]>q and "equal" otherwise.