Overcoming Dragonblood: Hashing Data To An Elliptic Curve Point (or Scalar) In A Constant Time
Let’s say we have almost 2²⁵⁶ integer point values. This will give us 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 different (x,y) points. Can we find a way to hash some data onto one of these points, and so it is not possible to know the data that resulted in that point, and that it is highly unlikely for two different data elements to end up with the same data point?
In ECC (Elliptic Curve Cryptography) we often have to hash our data to a scalar value or to a point on the curve. Once hashed, it is difficult to reverse the operation (unless we did a brute-force search for it). We can either encode-to-curve (non-uniform) to hash-to-curve. Overall we often use the method of encoding/hashing to a curve with PAKE (password-authenticated key exchange), IBE (Identity-based Encryption) and within Verifiable Random Functions (VRF) and Oblivious Pseudorandom Functions (VOPRF).
One method of doing this is to hash to a value, and then find the nearest point — known as “try-and-increment” or “hunt-and-peck”. Unfortunately, these do not have a constant time implementation and could be open to side-channel analysis. One example of an attack against this is with WPA3, and where the Dragonblood vulnerability exploited…
