WEKO3
アイテム
ECDSAに対する4-list sum algorithmを用いた攻撃の評価
https://ipsj.ixsq.nii.ac.jp/records/228682
https://ipsj.ixsq.nii.ac.jp/records/2286828fa4e35c-b5e2-4eb6-a34a-03a6a6467202
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-CSS2023069.pdf (429.5 kB)
2025年10月23日からダウンロード可能です。
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, CSEC:会員：¥0, SPT:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Symposium(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-10-23 | |||||||||
| タイトル | ||||||||||
| タイトル | ECDSAに対する4-list sum algorithmを用いた攻撃の評価 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Evaluation of attack against ECDSA using 4-list sum algorithm | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | ECDSA，フーリエ解析ベース攻撃，Generalized birthday probelm，サイドチャネル攻撃 | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
| 資源タイプ | conference paper | |||||||||
| 著者所属 | ||||||||||
| 筑波大学大学院システム情報工学研究群 | ||||||||||
| 著者所属 | ||||||||||
| 筑波大学システム情報系 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Degree Programs in Systems and Information Engineering, University of Tsukuba | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Institute of Systems and Information Engineering, University of Tsukuba | ||||||||||
| 著者名 |
大﨑, 俊輔
× 大﨑, 俊輔
× 國廣, 昇
|
|||||||||
| 著者名(英) |
Shunsuke, Osaki
× Shunsuke, Osaki
× Noboru, Kunihiro
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 楕円曲線を用いたデジタル署名アルゴリズム（ECDSA）はSSL/TLS やBitcoin など非常に広い分野で使用されている．ECDSA の署名時に一度だけ用いられるランダムな値であるnonce のエラー付き上位ビットが署名，ハッシュ値と共に複数組漏洩した場合の攻撃方法が提案されている．Aranha らはACMCCS2020 で上位 1 ビットがエラー付きで漏洩しいてる192-bit のECDSA に対して，フーリエ解析ベース攻撃を行い，秘密鍵の復元に成功している．Aranha らはフーリエ解析ベース攻撃でのrange reduction に4-list sum algorithm を用いている．彼らは和の分布の一様性を仮定して見積もりなどを行っていたが，実際には一様ではないため，必要な署名数を過小に評価していた．本研究では，和の分布を正確に導出した上で，その分布を組み込んだアルゴリズムの提案を行う．さらに，nonce の上位 2 ビットがエラー率 0.111434 で漏洩している場合は，上位1 ビットがエラー無しで漏洩している場合と秘密鍵を復元するのに必要となる署名数が同程度であることを指摘し，実際に，131-bit ECDSA の秘密鍵の復元ができることを示す． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | Elliptic Curve Digital Signature Algorithm (ECDSA) is used in a vast range of applications, including SSL/TLS and Bitcoin. Several methods have been proposed to attack the case where the MSBs of the nonce in an ECDSA signature, contain errors and are compromised along with the signature and hash value. Aranha et al. successfully recovered a 192-bit ECDSA secret key from the MSB with an error by using Fourier analysis based attack. In their Fourier analysis-based attack, Aranha et al. used a 4-list sum algorithm for collision search. They assumed that the distribution of the sums was uniform, but in fact, it was not, resulting in an underestimation of the number of required signatures. In this study, we derive the exact distribution of the sum and propose an algorithm that incorporates the distribution. Furthermore, we point out that the number of signatures required to recover the secret key when the upper two bits of the nonce are compromised with an error rate of 0.111434 is comparable to that when the upper 1 bits are compromised without error. We then show that it is possible to recover the secret key of a 131-bit ECDSA. | |||||||||
| 書誌情報 |
コンピュータセキュリティシンポジウム2023論文集 p. 500-507, 発行日 2023-10-23 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
