Study group: Side-channel collision attacks

Last week's study group was brought to us by Luke and Valentina on the subject of side-channel collision attacks, with a focus on the following three papers:

• "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]

A 'collision' in cryptanalysis traditionally denotes the noninjective mapping of different inputs to the same output of a cryptographic function. Side-channel collision analysis seeks to exploit collisions in the intermediate values of a function, without requiring that these propagate to the final output. Since cryptographic algorithms have, until recently, been designed to be secure in a block box setting -- i.e. assuming that the attacker cannot 'see' the intermediate values -- such internal collisions can occur quite frequently. Whilst it is true that they are harder to detect than collisions in the output, side-channel methodologies provide the possibility for finding them, so long as sufficient physical trace measurements can be acquired.

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.