This session was on elliptic curve cryptography. The first speaker (Jonathan Taverne) pointed out a long history on ECC at CHES. However, with new architectures come new challenges. For instance, past performance figures tended to concentrate on elliptic curves over prime fields, but with the new Intel PCLMULQDQ one would expect a performance boost for binary curves. When looking at the field arithmetic, this new operation will make multiplication less expensive compared to other operations, such as squaring or taking roots. When looking at curves, this has the effect that a double-and-add will gain more from the new instruction set than a halve-and-add method, so perhaps the former will once again be the new speed champion? This turned out not to be the case (and nor did the binary curves beat the prime curves yet), but along the way a very neat trick was presented: by cleverly writing the curve scalar multiplication, it turns out possible to perform half the computation using double-and-add and the other half using halve-and-add in parallel. This reminded me of a similar trick by Marcelo Kaihara and Naofumi Takagi, who split a modular multiplication in two (bipartite modular multiplication). Great fun!
Peter Schwabe continued the session in high speed. The topic here was high speed, high security signatures. A variant of Schnorr signatures were chosen, but with some interesting design choices. Remember that underlying a Schnorr signature is a (honest-verifier) zero-knowledge protocol of knowledge with the Fiat-Shamir heuristic applied to it. Conventional wisdom has it to send the hash value and the response value (both elements in the exponent group), but here instead the hash function was chosen to produce twice as many bits as one would expect plus group elements could be compressed efficiently. Thus sending the initial commitment suddenly made more sense than the hash value. Other small tweaks were the doubling up of the hash function as pseudorandom function to determine this initial commitment and the use of the hash function as pseudorandom generator to expand an initially smaller secret. The result were very fast and compact digital signatures. As a note on security, I think it was still random oracle, but generic collisions would not lead to a forgery. However, given the structure of the signature, my hunch is that chosen prefix collisions (as can be found for MD5) would lead to an existential forgery. In general, I'm somewhat skeptical of proofs in the random oracle where you can waiver some standard property, as usually whenever some non-trivial attack is presented, this is due to some structural flaw that might also be exploited otherwise.
The final talk of the session, and the first day of CHES'11, was by Junfeng Fan. He described an attack that combined fault injection and a side-channel to find a discrete logarithm. The underlying observation was very simple: if P is a point on a curve, change it by a fault injection into P' on the same curve, but such that P' has low order, say order 4. If P' is subsequently used in an exponentiation routine, repeated squarings lead to the point at infinity, which one can normally detect using a side-channel. A lot of the ideas that went into this attack seemed known to me, but the combination required an oracle that, given a curve, provided you with P and P' that were close together (to make the fault injection work). Even many implementations that are secure against side channels and fault injection separately, fall foul against this combination.
This was an enjoyable session and especially the trick of the first talk was rather neat!
No comments:
Post a Comment