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:
- 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).
- For all those measurements, try to find instances ofsbox(m1 XOR k1) = sbox(m2 XOR k2) <=> m1 XOR k1 = m2 XOR k2by 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 k1, k2:m1 XOR m2 = k1 XOR k2(We already know m1 and m2.)
- When a sufficient amount of relations between various ki,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.
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.