Fault Attack on SQIsign

Jeonghwan Lee; Donghoe Heo; Hyeonhak Kim; Gyusang Kim; Suhri Kim; Heeseok Kim; Seokhie Hong

doi:10.1007/978-3-031-62746-0_3

Fault Attack on SQIsign

Jeonghwan Lee
, Donghoe Heo
, Hyeonhak Kim
, Gyusang Kim
, Suhri Kim
, Heeseok Kim
, Seokhie Hong^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

In this paper, we introduce the first fault attack on SQIsign. By injecting a fault into the ideal generator during the commitment phase, we demonstrate a meaningful probability of inducing the generation of order. The probability is bounded by one parameter, the degree of commitment isogeny. We also show that the probability can be reasonably estimated by assuming uniform randomness of a random variable, and provide empirical evidence supporting the validity of this approximation. In addition, we identify a loop-abort vulnerability due to the iterative structure of the isogeny operation. Exploiting these vulnerabilities, we present key recovery fault attack scenarios for two versions of SQIsign—one deterministic and the other randomized. We then analyze the time complexity and the number of queries required for each attack. Finally, we discuss straightforward countermeasures that can be implemented against the attack.

Original language	English
Title of host publication	Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings
Editors	Markku-Juhani Saarinen, Daniel Smith-Tone, Daniel Smith-Tone
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	54-76
Number of pages	23
ISBN (Print)	9783031627453
DOIs	https://doi.org/10.1007/978-3-031-62746-0_3
Publication status	Published - 2024
Event	15th International Conference on Post-Quantum Cryptography, PQCrypto 2024 - Oxford, United Kingdom Duration: 2024 Jun 12 → 2024 Jun 14

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14772 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Conference on Post-Quantum Cryptography, PQCrypto 2024
Country/Territory	United Kingdom
City	Oxford
Period	24/6/12 → 24/6/14

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Keywords

Fault Attack
Isogeny
Post-Quantum Cryptography
Quaternion Algebra

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-62746-0_3

Cite this

Lee, J., Heo, D., Kim, H., Kim, G., Kim, S., Kim, H., & Hong, S. (2024). Fault Attack on SQIsign. In M.-J. Saarinen, D. Smith-Tone, & D. Smith-Tone (Eds.), Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings (pp. 54-76). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14772 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-62746-0_3

Fault Attack on SQIsign. / Lee, Jeonghwan; Heo, Donghoe; Kim, Hyeonhak et al.
Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings. ed. / Markku-Juhani Saarinen; Daniel Smith-Tone; Daniel Smith-Tone. Springer Science and Business Media Deutschland GmbH, 2024. p. 54-76 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14772 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lee, J, Heo, D, Kim, H, Kim, G, Kim, S, Kim, H & Hong, S 2024, Fault Attack on SQIsign. in M-J Saarinen, D Smith-Tone & D Smith-Tone (eds), Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14772 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 54-76, 15th International Conference on Post-Quantum Cryptography, PQCrypto 2024, Oxford, United Kingdom, 24/6/12. https://doi.org/10.1007/978-3-031-62746-0_3

Lee J, Heo D, Kim H, Kim G, Kim S, Kim H et al. Fault Attack on SQIsign. In Saarinen MJ, Smith-Tone D, Smith-Tone D, editors, Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 54-76. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-62746-0_3

Lee, Jeonghwan ; Heo, Donghoe ; Kim, Hyeonhak et al. / Fault Attack on SQIsign. Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings. editor / Markku-Juhani Saarinen ; Daniel Smith-Tone ; Daniel Smith-Tone. Springer Science and Business Media Deutschland GmbH, 2024. pp. 54-76 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{660eb10956ef4366a8f57d55e7a442f4,

title = "Fault Attack on SQIsign",

abstract = "In this paper, we introduce the first fault attack on SQIsign. By injecting a fault into the ideal generator during the commitment phase, we demonstrate a meaningful probability of inducing the generation of order. The probability is bounded by one parameter, the degree of commitment isogeny. We also show that the probability can be reasonably estimated by assuming uniform randomness of a random variable, and provide empirical evidence supporting the validity of this approximation. In addition, we identify a loop-abort vulnerability due to the iterative structure of the isogeny operation. Exploiting these vulnerabilities, we present key recovery fault attack scenarios for two versions of SQIsign—one deterministic and the other randomized. We then analyze the time complexity and the number of queries required for each attack. Finally, we discuss straightforward countermeasures that can be implemented against the attack.",

keywords = "Fault Attack, Isogeny, Post-Quantum Cryptography, Quaternion Algebra",

author = "Jeonghwan Lee and Donghoe Heo and Hyeonhak Kim and Gyusang Kim and Suhri Kim and Heeseok Kim and Seokhie Hong",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 15th International Conference on Post-Quantum Cryptography, PQCrypto 2024 ; Conference date: 12-06-2024 Through 14-06-2024",

year = "2024",

doi = "10.1007/978-3-031-62746-0\_3",

language = "English",

isbn = "9783031627453",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "54--76",

editor = "Markku-Juhani Saarinen and Daniel Smith-Tone and Daniel Smith-Tone",

booktitle = "Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Fault Attack on SQIsign

AU - Lee, Jeonghwan

AU - Heo, Donghoe

AU - Kim, Hyeonhak

AU - Kim, Gyusang

AU - Kim, Suhri

AU - Kim, Heeseok

AU - Hong, Seokhie

PY - 2024

Y1 - 2024

N2 - In this paper, we introduce the first fault attack on SQIsign. By injecting a fault into the ideal generator during the commitment phase, we demonstrate a meaningful probability of inducing the generation of order. The probability is bounded by one parameter, the degree of commitment isogeny. We also show that the probability can be reasonably estimated by assuming uniform randomness of a random variable, and provide empirical evidence supporting the validity of this approximation. In addition, we identify a loop-abort vulnerability due to the iterative structure of the isogeny operation. Exploiting these vulnerabilities, we present key recovery fault attack scenarios for two versions of SQIsign—one deterministic and the other randomized. We then analyze the time complexity and the number of queries required for each attack. Finally, we discuss straightforward countermeasures that can be implemented against the attack.

AB - In this paper, we introduce the first fault attack on SQIsign. By injecting a fault into the ideal generator during the commitment phase, we demonstrate a meaningful probability of inducing the generation of order. The probability is bounded by one parameter, the degree of commitment isogeny. We also show that the probability can be reasonably estimated by assuming uniform randomness of a random variable, and provide empirical evidence supporting the validity of this approximation. In addition, we identify a loop-abort vulnerability due to the iterative structure of the isogeny operation. Exploiting these vulnerabilities, we present key recovery fault attack scenarios for two versions of SQIsign—one deterministic and the other randomized. We then analyze the time complexity and the number of queries required for each attack. Finally, we discuss straightforward countermeasures that can be implemented against the attack.

KW - Fault Attack

KW - Isogeny

KW - Post-Quantum Cryptography

KW - Quaternion Algebra

UR - https://www.scopus.com/pages/publications/85197198863

U2 - 10.1007/978-3-031-62746-0_3

DO - 10.1007/978-3-031-62746-0_3

M3 - Conference contribution

AN - SCOPUS:85197198863

SN - 9783031627453

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 54

EP - 76

BT - Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Proceedings

A2 - Saarinen, Markku-Juhani

A2 - Smith-Tone, Daniel

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Conference on Post-Quantum Cryptography, PQCrypto 2024

Y2 - 12 June 2024 through 14 June 2024

ER -