Snitch Cryptography: How to Crack Tamper-Proof Devices

Gonzalo Álvarez Marañón    4 February, 2021
Snitch Cryptography: How to Crack Tamper-Proof Devices

Google’s Titan Security Key or YubiKey from Yubico are the ultimate trend in multi-factor authentication security. According to Google’s own website:

«The keys have a hardware chip with firmware designed by Google to verify that no one has tampered with them. These chips are designed to resist physical attacks that seek to extract the key’s firmware and secret material».

In other words, a Titan or YubiKey key stores your private key and it should be impossible to extract it from the device. It should be. Because to be honest, you can, as several NinjaLab researchers proved it in January in a titanic work (ok, yes, that was a bad joke). How did they achieve it? Using a side-channel attack.

How Do Side Channel Attacks Work

What happens when mathematical algorithms leave the blackboards of cryptographers and are programmed into Real World™ chips? In the crude physical world, far away from ideal platonic bodies, a bit has no choice but to be represented as an electric current passing (“1”) or not passing (“0”) through a transistor. And, however subtly it flows, an electric current inevitably produces effects around it: a small electromagnetic radiation, a small variation in temperature, a small rise in energy consumption, a small displacement of air, an imperceptible sound, …

If you are able to measure these effects, you are able to read keys, intermediate states, memory…. In short, to extract enough information to circumvent the mathematical algorithm. No matter how secure your cryptography is, if the hardware implementation allows a side-channel attack, it will come to nothing.

Figure 1. Traditional (ideal) cryptographic model versus (real) side-channel cryptographic model.

Cryptanalysts have discovered since the birth of mechanical cryptography that every cryptographic device “snitch” on what is going on inside it. Instead of attacking the algorithms, side-channel attacks attack the implementation of the algorithms. In short: if hardware is involved, there will be a side-channel leaking information. It is pure physics. Let’s look at it with an example.

Power Analysis Attack On RSA

In a previous article, I explained mathematical attacks against the popular RSA public key encryption algorithm, although I only briefly mentioned the possibility of side-channel attacks. As you know, to encrypt with RSA, the following operation is performed on the public key, e and n:

c = me mod n

while the private d key is used for decryption:

m = cd mod n

The attacker’s goal is to extract this private key, d, from the device. As you can see, the way RSA works is based on the exponentiation operation. Since RSA uses very, very large integers, mathematicians looked for shortcuts to make the calculation of these operations fast. More precisely, the exponentiation by squaring algorithm, also known as square and multiply, is often used. It is very simple to understand. To calculate 34 = 11100 you can do the following operations:

  • 32 = 9 (square)
  • 92 = 81 (square)

To calculate this result, it was enough to square it twice in a row. Let’s see what happens with another exponent. For 35 = 11101 the algorithm works like this:

  • 32 = 9 (square)
  • 92 = 81 (square)
  • 81 × 3 = 243 (multiply)

In this case, two squares and one multiplication have been performed. Finally, consider 312 = 111100:

  • 32 = 9 (square)
  • 9 × 3 = 27 (multiply)
  • 272 = 729 (square)
  • 2792 = 531.441 (square)

By now, you will have realised how the algorithm works: after ignoring the first “1” in the exponent, if you encounter a “1”, do a square and a multiplication; if you encounter a “0”, do just a square. No matter how big the base and exponent are, you can always exponentiate by these two operations in a remarkably efficient way. In short, always square and only multiply if the exponent bit to be processed is 1.

Now, as you can imagine, square and multiplication are two operations that will take much longer than just square. If you could see how long a circuit is taking to operate, you would figure out what operation it is performing, and therefore what the private exponent, d, is. And the reality is that it is as simple as looking at the power consumption of the device, as shown in the figure below:

Figure 2. Consumption analysis of a chip operating with RSA (source: Understanding Cryptography: A textbook for students).

From the observation of the trace, it is clear that the secret key is:

operations: S SM SM S SM S S SM SM SM S SM …

primate key: 0 1 1 0 1 0 0 1 1 1 0 1 …

Of course, this attack works for keys of any length. Similarly, other encryption algorithms leak information in other ways, but unfortunately, they all leak something. And when the power analysis does not leak the information needed, there are many other attacks.

Types of Side-Channel Attacks

In addition to the side-channel attack based on power consumption, researchers have been discovering many other ways to obtain information from an operating hardware device:

  • Attack on the cache: The cache is an almost instantaneous direct access memory, used to store heavily used data and instructions. When data is loaded into cache for the first time (cache miss) there is a delay, as opposed to when data is already in cache (cache hit), where access is instantaneous. This difference in access times leaks valuable information that can be used by an attacker to obtain sensitive data from memory. The devastating Meltdown and Spectre attacks are examples of this type of attack.
  • Time attack: this is carried out by measuring the time it takes for different instructions of a cryptographic algorithm to execute according to various parameters. Time variations allow information to be extracted from the key.
  • Consumption monitoring attack: not all operations performed by an algorithm are equally complex. In general, the greater the complexity, the greater the consumption. By measuring these variations in consumption, information can be extracted on the algorithm’s arguments, as in the example seen for RSA.
  • Electromagnetic attack: any electronic device leaks electromagnetic radiation, which can directly provide the content of sensitive information. These measurements can be used to infer cryptographic keys using techniques equivalent to power analysis or can be used in non-cryptographic attacks, e.g. TEMPEST, which allows the information on a monitor to be replayed from another room.
  • Sound attack: it is possible to figure out the operation of a device’s processor and break its cryptography by listening with a conventional smartphone to the sound of its capacitors and coils as they operate. There are also non-cryptographic attacks that exploit the sound emitted by the keys on a keyboard when entering a password or the noise of the heads of an ink-jet printer when printing.
  • Differential failure analysis: when hardware is intentionally induced to fail, unexpected responses from the execution of an algorithm can be used to obtain information about its data. The padding oracle attacks against RSA or the length extension attack, based on this technique, are very famous.

Cryptography Does Not Run On Paper, But On Hardware

However, secure an algorithm may be on paper, when executed on hardware it opens the door to side-channel attacks. Although they have been known since the early 20th century, they have gone relatively unnoticed because they require physical proximity to the attacker to carry them out. But thanks to smartphones and drones, it is now easy to implant microphones and sensors anywhere to launch side-channel attacks against victims. Over time, such attacks will become easier and cheaper. Even quantum key distribution is not immune to side-channel attacks.

In addition to those mentioned above, new attacks are continually being discovered: cold boot, software-based, error message-based, optical, etc. There are many countermeasures that can be added to hardware designs to counter these attacks: injecting randomness, adding noise, deleting data, etc. It is a race in which the attackers are always one step ahead of the engineers and which, sadly has apparently no end.

Leave a Reply

Your email address will not be published. Required fields are marked *