Vulnerability Found in Widely Used Method for Securing Phone Data
Proving one’s identity amounts to carrying out a certain kind of encryption algorithm. This algorithm involves a series of operations on a secret key called a “nonce,” which can be represented as a binary number, a sequence of ones and zeroes or “bits.” For each operation that a phone’s processor carries out, it emits a weak radio signal, thousands of times weaker than the signal of a Wi-Fi transmitter. These signals are called “side-channel” emissions since they do not come from the primary channels that the phone uses to communicate.
Years ago, researchers realized that these side-channel emissions can leak the value of the nonce. For example, an encryption algorithm might require additional processing steps when a bit of the nonce is a one, making the processor emit a longer lasting signal for those bits. By tracking the pattern of longer and shorter emissions that come from the phone while it is processing the nonce, an attacker can reconstruct the value of each of its bits. From there, they can break a user’s encryption.
Other researchers invented a solution for this problem known as a “constant-time” algorithm. This algorithm ensures that a processor carries out the same sequence of operations for each bit. The radio emissions are therefore indistinguishable for each bit and the nonce cannot be reconstructed. This algorithm was codified in encryption standards like RFC 7748 and widely adopted.
Breaking the Constant-Time Algorithm
In the new work, the researchers discovered a problem with the constant-time algorithm. One particular operation that is carried out for each bit, called a “conditional swap,” has a tell-tale trait. When the operation is performed on a bit with the value of one, the processor emits a slightly stronger radio signal. The researchers realized that if an attacker could listen in on the emissions during this operation, each time it occurs, they could determine the nonce.
The hard part was to figure out whether they could focus in on the specific radio signature of the conditional swap, buried within a sequence of many other emissions. Also, because of the high processing speed of modern phones, the radio signature of the conditional swap only lasts for a brief duration. But, it turns out, it is the constant-time algorithm — meant to be a countermeasure to side-channel attacks — which allows the attack to work in the first place.
The key for the researchers was to carefully observe a phone’s emissions. Because of the constant-time algorithm, these emissions are extremely regular. Each time the phone processes a bit, the same general pattern of emissions takes place. The researchers could therefore automate the process of picking out the tiny piece of emissions corresponding to the conditional swap, like learning to spot a small logo on a fast-moving train car by watching enough train cars passing by. From there, the researchers could measure the strength of the emissions to determine whether each bit was a zero or one, and thereby reconstruct the entire nonce.
The attack works so effectively that researchers found they only needed to listen in on a single secure transaction to steal a phone’s secret key.
“As long as somebody can put a probe or antenna close enough,” said Prvulovic, “We can have your key now.”
To fix the issue, the researchers modified the constant-time algorithm so that the signal corresponding to the conditional swap has the same strength regardless of the value of the bit. After developers implement this fix into cryptographic libraries like OpenSSL, the constant-time algorithm should be secure once again.
