Fault-assisted side-channel analysis of HMAC-Streebog

Abstract

Streebog is a family of hash functions defined in the Russian cryptographic standard GOST R 34.11–2012. HMAC-Streebog, which is defined in RFC 7836, is a Streebog-based message authentication code. It supports keys of size ranging from 256 bits to 512 bits. In this article, we present fault-assisted side channel attacks on HMAC-Streebog-256 and HMAC-Streebog-512 that can recover the keys in real-time with $2^{12.98}$ and $2^{14.97}$ average number of fault injections, respectively, to ensure 95% success. The attacker is assumed to be able to simultaneously flip at the most 181 chosen bits of the inner hash if it is a 256–bit variant and 361 chosen bits of the hash otherwise. In comparison to existing fault attacks on HMAC-Streebog, our attacks have a larger temporal window for fault injection, target a more accessible location, and cannot be mitigated with output redundancy countermeasures. Some of the latest hardware vulnerabilities make the HMAC-Streebog implementations vulnerable to our attacks.

Keywords:

• carry flag
• fault analysis
• HMAC-Streebog
• side-channel
• Streebog

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 The data to be altered is available for more than 2t time, where t is the time taken by the compression function of Streebog, as the targeted modular addition is executed after two compression operations.

2 In output redundancy countermeasures, data is processed via redundant channels and the output will not be generated unless all of them agree to it. Still, the carry flag side-channel remains unaffected.

3 We assume that $x_{(i-1)},y_{(i-1)}$ and $c_{(i-1)}$ are independent, and $\mathrm{\text{Pr}}(x_{(i-1)}=0)=\mathrm{\text{Pr}}(y_{(i-1)}=0)=0.5.$

4 A random oracle is a theoretical black box that responds to every unique query with a response chosen uniformly at random from its output domain.

5 Since x and y are independent and distributed uniformly at random, $y{\prime }_u\parallel x{\prime }_l$ and $x\prime ,$ which constitute the chosen x’s, are also uniformly distributed. The definitions of $y{\prime }_u,x{\prime }_l$ and $x\prime$ are given in Algorithm 3.

6 Success probability $:=\frac{1}{4}·1+\frac{3}{4}·\frac{2}{3}=0.75.$

7 The success rate of the passive analysis and the number of bits recovered increases with the number of messages authenticated using the same key.

Additional information

Notes on contributors

Gautham Sekar

Gautham Sekar is the PGDM Chair at the Madras School of Economics, India, and a Director of Madras Fintech Services Pvt. Ltd, India. He holds a PhD from KU Leuven in the area of cryptology. His interests include information security, data science and financial technology.

Mabin Joseph

Mabin Joseph is working as a Scientist at Indira Gandhi Centre for Atomic Research, Tamil Nadu, India. He completed his Ph.D. from the Homi Bhabha National Institute, India. His research interests are in cryptology, network security and data analytics.

R. Balasubramanian

R. Balasubramanian is a Retired Professor and former Director of the Institute of Mathematical Sciences, Chennai, India. He obtained his Ph.D. in Mathematics from the University of Bombay. His interests include number theory and cryptology. He is the recipient of several national and international accolades including the Padma Shri by the Government of India and the Chevalier de l’Ordre National du Merite by the Government of France.