A timing attack against Patterson algorithm in the McEliece PKC

Abdulhadi Shoufan; Falko Strenzke; H. Gregor Molter; Marc Stöttinger

doi:10.1007/978-3-642-14423-3_12

A timing attack against Patterson algorithm in the McEliece PKC

Abdulhadi Shoufan, Falko Strenzke, H. Gregor Molter, Marc Stöttinger

Electrical Engineering

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

43 Scopus citations

Abstract

The security of McEliece public-key cryptosystem is based on the difficulty of the decoding problem which is NP-hard. In this paper we propose a timing attack on the Patterson Algorithm, which is used for efficient decoding in Goppa codes. The attack is based on the relation between the error vector weight and the iteration number of the extended Euclidean algorithm used in Patterson Algorithm. This attack enables the extraction of the secret error vector with minimal overhead. A countermeasure is proposed and verified for a FPGA implementation.

Original language	British English
Title of host publication	Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers
Pages	161-175
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-14423-3_12
State	Published - 2010
Event	12th International Conference on Information Security and Cryptology, ICISC 2009 - Seoul, Korea, Republic of Duration: 2 Dec 2009 → 4 Dec 2009

Publication series

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

Conference

Conference	12th International Conference on Information Security and Cryptology, ICISC 2009
Country/Territory	Korea, Republic of
City	Seoul
Period	2/12/09 → 4/12/09

Keywords

code-based cryptography
post quantum cryptography
Side channel attack
timing attack

Access to Document

10.1007/978-3-642-14423-3_12

Cite this

Shoufan, A., Strenzke, F., Molter, H. G., & Stöttinger, M. (2010). A timing attack against Patterson algorithm in the McEliece PKC. In Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers (pp. 161-175). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS). https://doi.org/10.1007/978-3-642-14423-3_12

Shoufan, Abdulhadi ; Strenzke, Falko ; Molter, H. Gregor et al. / A timing attack against Patterson algorithm in the McEliece PKC. Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. pp. 161-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1f3dee617f0f405d8afd774cff8fa4df,

title = "A timing attack against Patterson algorithm in the McEliece PKC",

abstract = "The security of McEliece public-key cryptosystem is based on the difficulty of the decoding problem which is NP-hard. In this paper we propose a timing attack on the Patterson Algorithm, which is used for efficient decoding in Goppa codes. The attack is based on the relation between the error vector weight and the iteration number of the extended Euclidean algorithm used in Patterson Algorithm. This attack enables the extraction of the secret error vector with minimal overhead. A countermeasure is proposed and verified for a FPGA implementation.",

keywords = "code-based cryptography, post quantum cryptography, Side channel attack, timing attack",

author = "Abdulhadi Shoufan and Falko Strenzke and Molter, {H. Gregor} and Marc St{\"o}ttinger",

year = "2010",

doi = "10.1007/978-3-642-14423-3_12",

language = "British English",

isbn = "3642144225",

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

pages = "161--175",

booktitle = "Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers",

note = "12th International Conference on Information Security and Cryptology, ICISC 2009 ; Conference date: 02-12-2009 Through 04-12-2009",

}

Shoufan, A, Strenzke, F, Molter, HG & Stöttinger, M 2010, A timing attack against Patterson algorithm in the McEliece PKC. in Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5984 LNCS, pp. 161-175, 12th International Conference on Information Security and Cryptology, ICISC 2009, Seoul, Korea, Republic of, 2/12/09. https://doi.org/10.1007/978-3-642-14423-3_12

A timing attack against Patterson algorithm in the McEliece PKC. / Shoufan, Abdulhadi; Strenzke, Falko; Molter, H. Gregor et al.
Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. p. 161-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS).

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

TY - GEN

T1 - A timing attack against Patterson algorithm in the McEliece PKC

AU - Shoufan, Abdulhadi

AU - Strenzke, Falko

AU - Molter, H. Gregor

AU - Stöttinger, Marc

PY - 2010

Y1 - 2010

N2 - The security of McEliece public-key cryptosystem is based on the difficulty of the decoding problem which is NP-hard. In this paper we propose a timing attack on the Patterson Algorithm, which is used for efficient decoding in Goppa codes. The attack is based on the relation between the error vector weight and the iteration number of the extended Euclidean algorithm used in Patterson Algorithm. This attack enables the extraction of the secret error vector with minimal overhead. A countermeasure is proposed and verified for a FPGA implementation.

AB - The security of McEliece public-key cryptosystem is based on the difficulty of the decoding problem which is NP-hard. In this paper we propose a timing attack on the Patterson Algorithm, which is used for efficient decoding in Goppa codes. The attack is based on the relation between the error vector weight and the iteration number of the extended Euclidean algorithm used in Patterson Algorithm. This attack enables the extraction of the secret error vector with minimal overhead. A countermeasure is proposed and verified for a FPGA implementation.

KW - code-based cryptography

KW - post quantum cryptography

KW - Side channel attack

KW - timing attack

UR - http://www.scopus.com/inward/record.url?scp=77954596095&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14423-3_12

DO - 10.1007/978-3-642-14423-3_12

M3 - Conference contribution

AN - SCOPUS:77954596095

SN - 3642144225

SN - 9783642144226

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

SP - 161

EP - 175

BT - Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers

T2 - 12th International Conference on Information Security and Cryptology, ICISC 2009

Y2 - 2 December 2009 through 4 December 2009

ER -

Shoufan A, Strenzke F, Molter HG, Stöttinger M. A timing attack against Patterson algorithm in the McEliece PKC. In Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. p. 161-175. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-14423-3_12

A timing attack against Patterson algorithm in the McEliece PKC

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this