A paper now out in the public domain, has demonstrated how to accelerate these computations. Entitled "Faster discrete logarithms on FPGAs" the acceleration was sufficient to be used in an attack against the SECG standard curve sect113r2. But before you panic this was removed from the standard in 2010 although it was not disabled in OpenSSL until June 2015. Although you shouldn't panic, neither should you relax, and you certainly shouldn't ignore this research.
Whilst this latest implementation has set a new record for various parts of the computation it is not necessarily that which will draw attention. What is important is the way they have been able to use fewer Look Up Tables (LUT). This reduces the cost not just of this attack but also holds the promise of significantly reduced cost for mounting attacks against larger curves.
The research into using special purpose hardware to attack elliptic curve crypto schemes has been very active of late (excellent example here).
It's also worth pointing out that FPGA optimisation techniques are good predictor of how Application-Specific Integrated Circuits (ASIC) will perform, but it is likely that the technique used in this paper would need to be re-optimised when being moved to ASICs. However, the overall architecture is expected to perform well on ASICs and so points the way to dedicated attack platforms that could become highly effective.
As with previous papers, this attack is based upon what is known as the Pollard Rho algorithm , so the speed advantages gained are highly comparable. It is interesting to note how the technique in this research performs as it is scaled up. To understand why this matters you need to recognise that the NIST standard recommends curves in three different categories:
- Koblitz curves over binary fields
- Random curves over binary fields
- Random curves over prime fields
Some have a much lower computational cost than others which is why it is not surprising that designers of cryptographic hardware tend to prefer certain options that end up in everyday use: choosing a binary field rather than a prime field eliminates a whole set of circuitry that would otherwise be required. Likewise choosing the smallest curve reduces the cost of implementation.
The "cost" of solving a random curve is 10 times more difficult than for a Koblitz curve (when used over the same small relatively small binary field). This can be millions of times more difficult than solving over the smallest binary fields.
The "cost" of solving a random curve is 10 times more difficult than for a Koblitz curve (when used over the same small relatively small binary field). This can be millions of times more difficult than solving over the smallest binary fields.
But (and it is a big but) even with the most computationally costly choses of curve, this research shows these are no longer looking like infeasible computations, especially for a dedicated attacker with significant resources and skills.
Special purpose hardware, combined with well known attacks suggests that designers should not be implementing least computationally costly choices within the standard. It's not time to panic but it is a warning from the foreseeable future that some of what is being implemented today will be vulnerable to attack. We know how long some of these implementations persist, especially in price sensitive equipment, so it's worth taking note.
Special purpose hardware, combined with well known attacks suggests that designers should not be implementing least computationally costly choices within the standard. It's not time to panic but it is a warning from the foreseeable future that some of what is being implemented today will be vulnerable to attack. We know how long some of these implementations persist, especially in price sensitive equipment, so it's worth taking note.