Single-trace template attacks on permutation-based cryptography

The Template Attack introduced by Chari, Rao, and Rohatgi has been widely used in Side-Channel Attacks on cryptographic algorithms running on microcontrollers. In 2014, Choudary and Kuhn successfully optimized a variant of this technique, based on Linear Discriminant Analysis (LDA), to reconstruct the actual values of a byte handled by a single microcontroller machine instruction, instead of only its Hamming weight. While their attack targeted single LOAD instructions, I believe this method can be even more powerful when attackers target intermediate values inside a cryptographic algorithm, for such values can be related to more than single instructions, and further mathematical tools can be applied for value enumeration or error correction when multiple target values can be checked against one another. In my dissertation, I first describe how I successfully built LDA-based templates for full-state recovery on target intermediate bytes in the SHA3-512 hash function implemented on an 8-bit device, which I combined with a three-layer enumeration technique for error correction to recover all the input values of this hash function from a single trace recording. To demonstrate an alternative technique, I also combined these template recovery results with a modified belief-propagation procedure for error recovery, adapting a 2020 design by Kannwischer et al. In combination, these techniques reached success rates near 100% in recovering all SHA3-512 input bytes. Secondly, I introduce the fragment template attack to make this technique feasible for targeting 32-bit microcontrollers. It cuts a 32-bit intermediate value into smaller pieces, applying the LDA-based template attack by independently building templates for these pieces. For a SHA-3 implementation on a 32-bit device, the quality of these fragment templates is good enough that their predictions can reconstruct the full arbitrary-length SHA-3 or SHAKE inputs with a very high success rate when combined with belief propagation. Thirdly, I also show that a combination of fragment template attack, belief propagation, and key enumeration can recover the key used in an Ascon-128 implementation. My experiments show how LDA-based templates can pose a threat to cryptographic algorithms once it is combined with belief propagation and key enumeration, even when they are implemented on a 32-bit device and in applications where keys are only used once. Therefore, we should not underestimate these risks and it is important to analyze the resilience against template attacks, in addition to DPA-style correlation attacks, when designing or implementing cryptographic algorithms and evaluating their security level.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2022

Author dc:creator

• You, Shih-Chun

Advisor dc:contributor.advisor

• Kuhn, Markus

• computer security
• side-channel attacks

Licence

• https://www.repository.cam.ac.uk/bitstreams/bcc79067-165f-4a60-b440-30d33fdaf3cd/download
• https://creativecommons.org/licenses/by/4.0/

Language dc:language

eng

Author Identifier

0000-0002-6359-7866

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/355720