Ondrej Mikle (at Saturday, January 11, 2014, 11:19:30 PM): > a) Ladders > Does this mean that an implementation of secp256k1 is likely to have timing > side-channel attacks?
"likely" might be a strong word. for some curves, an implementor must choose between a safe and a fast and simple implementation. there is a temptation to use a faster implementation on resource constrained platforms. for luckier curves, safe implementations are not less efficient. djb suggested curves use a fix series of instructions, accessing the same memory locations in the same order, regardless of the data. just to dismiss any claims like, jeez, nobody would use an unsafe implementation, let me just point to AES, and ask how many safe implementations are out there. do you have information for example what implementation the windows crpyto API has? let me guess it uses lookup tables. the terrible situation is only alleviated by the arrival of the aes-ni instruction set. also ask yourself how many libraries boast X MB/s encryption speed, and how many boasts implementation correctness. > Is there some suitable analogy of RSA blinding that could > be used (multiplication by a random number, then its inverse, to hide timing)? RSA blinding is an active effort, djb suggested curves don't need that. the algorithms are inherently insensitive to any timings / cache analysis. RSA blinding is actually a good analogy to NIST curves: you can make RSA safer adding more cycles and more code. or you can implement it without blinding, and call it a day. it is inconceivable that nobody ever will choose the latter "strategy". > b) Completeness > Like in "ladders" case, this implies that a timing branch/cache side channel > is > likely in an actual implementation due to the need to check for special cases? yep, but i would question the use of "likely" again. unlucky curves lead to an implementation nightmare, which will, no doubt, be trimmed down every now and again, especially because it doesn't affect normal operations, and speeds things up. sooner or later we can expect most implementations be decent, but we can't expect them all to be perfect from the onset. why have this risk, if we have better curves? as a side note: for any readers thinking "but this is nitpicking", besides it is not, there are other, worse problems with NIST curves. _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
