EuroCrypt'12, Day 2: Collisions and Statistics

The EuroCrypt conference has a rather theoretic reputation and only very few papers on Side Channel (SC) Attacks have been accepted to the conference over the last decade. This year, there is exactly one paper covering Side Channel Attacks, namely "Statistical Tools Flavor Side-Channel Collision Attacks" by Amir Moradi, compared e.g. to four papers that refer to Fully Homomorphic Encryption in their titles.

Simple SC Collision Attacks have been known since 2003 but have never really been in the focus of attention of the Side Channel community. They aren't the most efficient Side Channel Attacks as long as a reasonably good power leakage model for the device under attack (DUA) is known. However, Simple SC Collision Attacks do not require a power leakage model at all so they are useful if the attacker has no power leakage model of the DUA. Without a power model, one could also use Mutual Information Analysis (MIA) but the quality of MIA results depend very much on the attacker's choice of distinguishers which complicates MIA a lot. But SC Collision Attacks hold the promise to be a more efficient solution to the problem.

Simple SC Collision Attacks focus only on one component of a cipher, i.e. a key-XOR followed by a sbox [Notation: sbox(m XOR k)] as they exist in the AES and PRESENT ciphers. Thus, like the classical Side Channel Attacks, they recover the secret key in small chunks one at a time (divide-and-conquer), reducing the complexity of all necessary brute forcing. Simple Collision Attacks operate (extremely simpliefied) as follows:

1. Many (millions!) measurements of the power consumption (only the attacked part of the cipher) have to be recorded. E.g. 20 million measurements of sbox(m XOR k).
2. For all those measurements, try to find instances of
   
   sbox(m₁ XOR k₁) = sbox(m₂ XOR k₂) <=> m₁ XOR k₁ = m₂ XOR k₂
   
   by comparing their power traces; if the computations are equal, the power traces should be equal (up to noise), if the results are unequal, the power traces should be different. From each of these instances we learn something about the keys k₁, k₂:
   m₁ XOR m₂ = k₁ XOR k₂
   
   (We already know m₁ and m₂.)
3. When a sufficient amount of relations between various k_i,j (i = rounds, j = full chunk of the round key) have been found, a fully determined system of equations can be built and solved to find the correct key used for en-/decryption by the DUA.

In his paper, Amir focuses on the second step, improving what could be done so far. Previous works used the mean of the power traces for the comparison or the means of multiple parts of the trace. However, a lot of fundamentally different power traces can have the same mean and the mean of a power leakage does not necessarily depend on the data that is being processed while other aspects (higher order moments or the probability density) of the trace, e.g. its variance, may well do. For example, popular countermeasures such as masked sboxes (in software) or threshold implementations (in hardware) defeat simple SC Collision Attacks.

So the next logical step is to explore the usefulness of higher order moments in attacking implementations with these protections and that is just what Amir does in his paper. He shows how to compute the comparisons using the variance, skewness, kurtosis and probability density functions of the traces. This isn't obvious -- you have to keep in mind that my above description of simple SC Collision Attacks is quite simplified. He then tested these theoretic results by attacking Threshold Implementations of AES and PRESENT implemented on a Xilinx Virtex II FPGA and a masked s-box implementation of AES on a Atmel Microcontroller as you might find it on a smart card. All three implementations would have withstood a simple SC Collision Attacks and first order DPA but using his new methods, Amir was able (given enough traces) to recover the secret keys.

So this is indeed an impressive achievement and will most certainly influence the development and evaluation of security-certified devices such as credit cards or authentication tokens.