- "A New Class of Collision Attacks and Its Application to DES" (Schramm, Wollinger and Paar) [pdf]
- "A Collision-Attack on AES Combining Side Channel- and Differential-Attack" (Schramm, Leander, Felke and Paar) [pdf]
- "Correlation-Enhanced Power Analysis Collision Attack" (Moradi, Mischke and Eisenbarth) [pdf]
To find an internal collision in a block cipher, for example, an attacker might encrypt two plaintexts (under an unknown key) with a small, fixed differential, measuring the power consumption as an intermediate value (for example, an S-Box output) is computed. If the correlation between the two measurement vectors is high, this may indicate a collision. The plaintext differential associated with the collision can be looked up in a table which will give the possible input pairs producing such an output, consequently narrowing down the possible key candidates. Of course, many traces may need to be collected for many different plaintexts before sufficient collisions can be found to deduce the key, and several replicates per plaintext may need to be collected and averaged in order to diminish the confounding effect of noise. Moreover, they are 'chosen message' attacks as opposed to 'known message' attacks, implying a stronger adversary than many typical side-channel strategies. But one significant advantage is that, unlike DPA (say), which relies on a good 'power model' for the device leakage, the attacker does not need to know anything about the form of the device leakage as trace measurements are directly compared with each other rather than with hypothesis-dependent predictions.
The first paper focuses on the DES block cipher, which naturally lends itself to such an approach because of its noninjective (6-4) S-Boxes. However, as the authors explain, the key expansion step makes it impossible to force a collision in the output of any single S-Box within the round function. Collisions in three adjacent S-Boxes can be produced, which means the tested input pairs have a length of 18 bits and the differential tables must be built according to the concatenation of three S-Box differentials. The authors tested their strategy against simulated device leakage and measurements taken from a 8051 compatible microcontroller running a software implementation of DES. The minimum average number of traces required to cause a collision in S-Box triple 2,3,4 was 140, yielding 10.2 out of the 18 targeted key bits. For S-Box triple 7,8,1 the average number to cause a collision was 165, yielding 13.8 key bits.
The second paper tackles the slightly more difficult problem of detecting and exploiting internal collisions in AES -- which rather has an injective S-Box. Fortunately (from an attacker's perspective) it turns out that key-dependent collisions can occur in one of the output bytes of the MixColumns transformation. They show that collisions are produced within an average of only 20 measurements, and propose various ways of reducing trace and storage complexity, finally proving the effectiveness of their strategy in a simulated attack averaged over 10,000 random keys.
The third paper suggests improvements to the efficiency and reliability of the collision detection step, via a strategy which is (superficially) similar to correlation DPA: the key differential associated with a particular input pair is hypothesised and the power consumption of the resulting S-Box outputs are correlated with one another. This is repeated over all possible key differentials (and all time points), and the hypothesis producing the highest correlation is taken to indicate the correct differential (and collision time). Using this method they are even able to extend the attack against AES to a masked scenario, demonstrating (against expectation) that collisions can be found and exploited in a protected implementation.
Some of the points raised for discussion following the presentation of the papers included the applicability of the techniques to other collision detection methods (e.g. cache-based) and the likelihood and impact of false positives in the detection stage.