Existing attacks refined to attack elliptic curve algorithm
Researchers have demonstrated how existing attacks against the ECDSA cryptographic algorithm can be improved to reduce the required nonce leakage by exploiting side-channel vulnerabilities.
The Elliptic Curve Digital Signature Algorithm (ECDSA), an alternative to RSA, offers improved security with smaller key sizes.
No algorithm is protected against every form of exploit, and in ECDSA’s case it is possible to take advantage of the nonce that’s generated as part of the signing process.
However, many attacks rely on a minimum of two-bit nonce bias to extract or recover full keys.
A new method has now been proposed by academics from Aarhus University, the University of Campinas, the University of Adelaide, NTT, and Data61 that is able to break ECDSA with less than one bit of nonce leakage.
Climbing the ladder
Published on May 25, the paper (PDF), penned by Diego Aranha, Felipe Rodrigues Novaes, Akira Takahashi, Mehdi Tibouchi, and Yuval Yarom, explores a new theoretical attack called ‘LadderLeak’.
“Due to the very sensitive nature of the [nonce] generated as part of the signing algorithm, it is known that any small amount of nonce exposure or nonce bias can in principle lead to a full key recovery: the key recovery is then a particular instance of Boneh and Venkatesan’s hidden number problem (HNP),” the researchers explain.
A novel class of side-channel vulnerabilities found in implementations of the Montgomery ladder – a method used to compute scalar multiplication in elliptic curves – exist in ECDSA systems, including some older versions of OpenSSL.
The vulnerabilities only leak less than one bit of nonce information, “in the sense that it reveals the most significant bit of the nonce, but with probability <1,” the team says, a factor which would otherwise exclude the bugs from being used in cryptographic attacks designed to break ECDSA.
However, by revising previous techniques that exploit one-bit leaks in 192-bit and 160-bit elliptic curves, the academics were able to “practically” break LadderLeak-vulnerable ECDSA implementations.
Ahead of the curve
The key factors were optimizing Fourier approaches – based on Bleichenbacher attack procedures (PDF) – to solve the HNP, while also using reasonable computing resources. Methods included exploiting small timing differences, cache-timing attacks using a Flush+Reload strategy, and the FR-Trace program.
The targets chosen were ECDSA instantiated over NIST P-192 and sect163r1. A unified time-space-data trade-off formula was created to find “optimal attack parameter choices” for group sizes and a given amount of nonce biases.
In theory, at least, the vulnerability affects numerous ECDSA implementations, including the widely deployed NIST P-256 curve.
“Our analysis also provides significant improvements to the data complexity for leaks of more than 1-bit, allowing the side-channel attacker to recover the ECDSA key given only several thousand signatures in many cases, or even several hundreds in some scenarios,” the paper states.
According to the researchers, this may be the first time that 192-bit ECDSA has been broken with one bit of leakage or less, and breaking P-224 with a one-bit leak – or P-256 with a two-bit leak – is possible using “relatively modest data complexity”.
Abandon obsolete parameters
Speaking to The Daily Swig, Aranha said the research should be considered of “academic interest“ rather than as real-world attack exploration, due to the necessity of collecting many signatures made using the same key in order to mount an attack.
“For larger parameters like the widely deployed NIST P-256 curve, the attack in principle applies but it’s still computationally too expensive,” the researcher added.
The team reported their findings to the OpenSSL development team. A patch was then created to fix the issue in version 1.0.2.
The same bug “in principle” also applies to the FIPS module of OpenSSL – as it is based on the same branch – but data complexities mean that attacks would require far more time to be successful.
The refactored 1.1 branch is not affected.
“If there is very small leakage/bias in selecting or processing the algorithm's secret nonce, no matter what side-channel is used to exploit that, Bleichenbacher's attack (and future potential improvements) becomes a threat again,” Aranha said.
“We are currently investigating other libraries. Our practical advice is: upgrade OpenSSL, abandon obsolete parameters.”
INTERVIEW Shodan founder John Matherly on IoT security, dual-purpose hacking tools, and information overload
