Paper 2017/614

Brute–Force Search Strategies for Single–Trace and Few–Traces Template Attacks on the DES Round Keys of a Recent Smart Card

Mathias Wagner, Stefan Heyse, and Charles Guillemet

Abstract

Recently, a new template attack on the DES key scheduling was demonstrated that allows recovery of a sufficiently large portion of the DES key of a widely deployed certified smart card chip using a single EM (electromagnetic) trace during the Exploitation Phase. Firstly, in this paper we show how the results can be improved upon when combining them with the analysis of another leakage channel, the total Hamming distance. Remaining rest entropies as low as approx 13 bits have been found for some single-trace attacks, meaning that effectively 42 bits of a single-key DES were recovered in a single trace. The nature of single-trace attacks has it that conventional software countermeasures are rendered useless by this attack, and thus the only remaining remedy is a hardware redesign. Secondly, various brute-force search strategies are compared with each other and an extensive analysis of the statistics of the rest entropy is presented. The analysis is also extended to two-key TDES. Moreover, the amount of brute-force effort can be drastically reduced when having more than one trace available for the attack. Already as few as N=8 traces during the Exploitation Phase bring about a reduction of the average brute-force effort of the order of 10 bits for single DES, and 22 bits for two-key TDES. For N approx 100 we achieve an average brute-force effort of less than 50 bits for two-key TDES. Further analysis reveals that this attack is not equally strong for all DES keys, but that quite a number of weaker DES keys exist where the attack is much stronger. Naturally, any assessment of the severity of this attack will have to be made based on the weakest keys. [This last part constitutes an update to a previous version of this paper.]

Note: Added an analysis based on the 15-tuple approach, so mainly chapter 5 on Weak Keys, and updated other chapters to be consistent with this; The 15-tuple approach shows how much stronger the attack can be become. Also changed all wording of Hamming weight to Hamming distance ;-)