Side channel attacks

Previously we introduced the BIGNUM feature of the OpenSSL Library that allows arbitrarily large cryptographic keys. This post is about how a quirk in the way BIGNUM is implemented opens a theoretical side-channel attack on any cryptographic algorithm that uses it.

Breaking a cryptographic code doesn't always mean brute force attacks with lots of compute power (traditional or quantum). One promising technique (from the perspective of an eavesdropper) can be used when a cryptographic system sends a signal in addition to the encrypted message. If the message itself is the main channel, leaked information would be a side channel.

By analogy, it would be easy to win at poker if you could peek at other people's cards. Naturally, they don't want you to do that. So getting information about another person's hole cards via that direct method tends to be hard. But people might leak information about their cards without being aware they are doing it. For instance, they might show signs of excitement when they see especially good cards. In poker, inadvertently leaked information is called a tell and in cryptography, it's a side channel.

Following the first World War, government agencies began using electronic cipher devices to protect communication. Probably the most famous of these devices was the Enigma machine which was used by Nazi Germany. Cryptographers in Poland and Britain were able to directly decrypt messages directly using knowledge of how the machines work and cryptanalysis. 

In the years following the second World War, electronic cryptography machines became more sophisticated and harder to defeat directly. However, one of the suppliers of equipment in the United States, The Bell System, discovered it was possible to intercept plaintext messages at a distance because of electromagnetic radiation produced by their machines. As a result, NATO countries initiated codename TEMPEST to develop standards for cryptographic equipment to protect it against these side-channel attacks.

In 1985, Wim van Eck wrote a paper called "Electromagnetic Radiation from Video Display Units: An Eavesdropping Risk?" He discovered that it was possible to use an ordinary TV receiver to remotely capture the picture displayed on a cathode ray tube (CRT) monitor. This is possible because the process that puts an image on the screen also leaks electromagnetic signals that travel beyond the screen itself. These analogue technologies aren't commonly used these days, but a more recent paper describes a similar exploit using mobile phones. Any signal that escapes could potentially be an attack vector.

In 2011, Billy Bob Brumley and Nicola Tuveri presented a paper called "Remote Timing Attacks are Still Practical". They demonstrated a method that collected data from a remote server via Transport Layer Security (TLS), a core function of OpenSSL. The attack depends on a quirk of how one algorithm, ECDSA with binary curves, was implemented.  By carefully measuring the time it takes to sign or produce a digital signature, an attack can estimate which bits are zero because that part of the calculation takes less time. Based on this data, and by repeating the process enough times, it's possible to use mathematical techniques to recover the private key of the server. That, to put it mildly, would not be good.

Fortunately this was not a commonly used algorithm. The timing problem was fixed with a patch that makes sure the calculation takes the same amount of time no matter what numbers are used as input. When a researcher finds a potential timing attack in an algorithm implementation, they notify the OpenSSL according to the security policy which can be resolved with a onetime fix for the affected algorithm. From a practical point of view, timing attacks are difficult and we don't know of any algorithms that can be exploited in supported versions of the library.

So that brings us to BIGNUM. In order to accommodate large cryptographic keys, OpenSSL needs to do math on much larger integers than computers natively handle. The way the BIGNUM code is written, calculation times vary based on properties, especially size, of the numbers in the calculation. That variation in time is a signal that can be used in a side channel attack. That means every algorithm that employs BIGNUM has the potential to be vulnerable to a timing attack. To be clear, this is all theoretical at the moment.

But just because we don't know any exploitable vulnerabilities doesn't mean they don't exist. So that's why the OpenSSL Foundation, with an investment from the Sovereign Tech Fund, is implementing a more general fix.

Next time: constant-time BIGNUMs.

‍

Thanks to OpenSSL advisory committee members Nicola Tuveri, Doctoral Researcher at Tampere University, and Billy Brumley, Endowed Professor at the Rochester Institute of Technology, for consulting on this post.

‍

Photo by Michał Parzuchowski on Unsplash