Digital signatures are important in many applications to allow the verification of the authenticity of a website, file, or the like. The Elliptic Curve Digital Signature Algorithm (ECDSA) is used to create such signatures, and, while more complex, is believed to give improved security over the Digital Signature
Algorithm, which is a U.S. federal standard and so may be regarded as the state of the art. With uses including Bitcoin, the security of ECDSA has naturally attracted much attention.

At Upgrade 2021, Professor Nadia Heninger (University of California San Diego) presented joint work with Prof. Martin R. Albrecht (University of London) demonstrating that side-channel attacks on ECDSA are more practical than had previously been thought. Side-channel attacks use information like processing time, power usage or electromagnetic radiation to obtain partial information such as the most significant bit(s) of a secret. This partial information can then be used to bootstrap a brute-force attack to obtain the full secret, thus side-stepping the full difficulty of breaking a cipher.

ECDSA applications are a favorite target for such attacks, modeled as follows: the attacker obtains partial information about the one-time nonces used to generate a series of signatures and uses it to obtain the long-term private key of the signer – enabling the attacker to impersonate the signer. The brute-force attack has often been represented as a search for the shortest vector in a high-dimensional lattice, which is a well-studied problem. The assumed difficulty of this search is the so-called lattice barrier, which has previously been taken to be a guarantee of the difficulty of such attacks on ECDSA.

With a more careful analysis of the problem, Heninger argued the difficulty of the attack has been overstated. For example, a solution may not require the shortest vector of the lattice to be discovered, only one whose length is within a small constant multiple of the shortest vector.

Similarly, she showed the previously assumed susceptibility of lattice solving to input noise has been overestimated, and that techniques exist to enable the attacker to overcome this. The techniques presented have been implemented and thoroughly tested: throughout, Heninger presented numerical evidence of the speed-ups possible over standard techniques. As a real-world proof of practicality, her team used these techniques to (benignly) break into some Bitcoin accounts using insufficiently long nonces.

In conclusion, Professor Heninger presented an outline of proposed future work and gave the address where the implemented code can be obtained.