JPAAWG 6 th General Meeting

耐量⼦計算機暗号（PQC）のココントコ
2023年11⽉6⽇

菅野 哲
GMOサイバーセキュリティ byイエラエ株式会社
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

1

⾃⼰紹介
• 名前
• 菅野 哲（かんの さとる）
• 所属
• GMOサイバーセキュリティ byイエラエ株式会社• 取締役CTO of Development• どんなことやっていた／やっているの︖• 学⽣時代• 暗号プロトコルの研究、セキュリティベンチャーで技術担当/営業担当• 社会⼈時代• 暗号ライブラリや情報セキュリティ関連システム開発• IETFなどでブロック暗号Camelliaに関する標準化活動• 外部活動• CRYPTREC 暗号鍵管理ガイダンスWG 委員• Trusted Computing Group Invited Expert（2018年10⽉〜）
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

2

会社紹介
• 「誰もが犠牲にならない社会を創る」がミッション• デジタルネイティブの時代に⽣きるすべての⼈が安全に暮らせるインターネッ
ト社会創りに貢献します。

https://gmo-cybersecurity.com/
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

3

本講演の概要とそのポイントを整理
本講演でどんな話のトピックスは︖• なんでPQCが必要になったの︖• 暗号アルゴリズムの安全性• 暗号の危殆化とは︖• 耐量⼦計算機暗号（PQC）とは︖• 暗号移⾏とは︖
Ø 暗号移⾏というイベントは未体験なのか︖
Ø 2つの「暗号の2030年問題」• IETFでのPQCに関する動向

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

4

Agenda• 暗号の危殆化• 暗号移⾏を招く︖︕ 2つの「暗号の2030年問題」• 我々を取り巻く環境

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

5

Agenda• 暗号の危殆化• 暗号移⾏を招く︖︕ 2つの「暗号の2030年問題」• 我々を取り巻く環境

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

6暗号の危殆化とは• 「暗号アルゴリズムへの攻撃の進歩やコンピュータの性能向上によって、設計時に想定された「セキュリティ上の性質」がより低いコストで確保できない状態」のこと• 暗号を危殆化させる脅威/要因• 暗号解析⼿法（攻撃）の進歩• 計算量的な脅威

︓差分解読法、線形解読法など
︓ムーアの法則、量⼦コンピュータなど• 過去に危殆化した主な暗号アルゴリズム• ハッシュ関数（MD5）、共通鍵暗号（DES）、公開鍵暗号（RSA-512）

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

7暗号の危殆化への対処⽅法とは「危殆化した暗号アルゴリズムを安全なアルゴリズムに差し替える」のみ︕
実施することは明確ではあるけど・・・「移⾏コスト」や「社会的インパクト」が⼤きい
影響範囲の例︓
インターネットサービス、仮想通貨、ブロックチェーン、情報家電製品、 OS、アプリケーション、ネットワーク機器など
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

8暗号の安全性とは• 細かいことをすっ⾶ばして安全性のキモチを⽰すと・・・

性
全安論的情報理

計算量的安全性

その暗号を最も効率のよいアルゴリズムで解読した時に必要な計算量のこと
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

9計算量的安全性って︖ その１• 暗号技術の安全の根拠となる数学的問題が「現実的な計算リソース、計算時間では解けない事実を利⽤」した安全性のこと• 無限のリソース、無限の時間があれば解読• RSAの場合は素因数分解問題を利⽤

サマーウォーズ（2009年）では暗算で暗号解読している︕

画像 削除
https://www.wikiwand.com/en/RSA_numbers#RSA-2048

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

※ サマーウォーズで登場した仮想世界では2056桁（約6825bit）の暗号鍵によって暗号化されている︖︕

10

計算量的安全性って︖その2
Invited talk at CRYPTO 2017 by John Martinis
RSA-2048解読するには︖
• 期間
• 10年

• データセンタの敷地• 北⽶の1/4のサイズ• 費⽤︓• 10^6 兆USD

• 電⼒︓

• 10^6 Tワット

https://www.youtube.com/watch?v=vOkC856dJrg

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

11

それぞれ異なる暗号技術を同じ指標で評価• ビットセキュリティという概念が「NIST SP800-57 “Recommendation onKey Management”」で提唱• 異なる種類の暗号アルゴリズムに対して安全性を評価するための指標• 「等価安全性」という表現を使っていることもある
https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final• ビットセキュリティはどう表されるの︖• 対象の暗号アルゴリズムへの攻撃に必要な計算量が2^nである時、この暗号アルゴリズムの安全性は「nビット安全性（n-bits of security）」とする•例• 共通鍵暗号 ︓秘密鍵を探索する計算量• 公開鍵暗号 ︓安全性が基づく問題（素因数分解、離散対数問題など）を解く計算量• ハッシュ関数︓衝突ペアを探索する計算量

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

12具体例︓nビット安全性（n-bits of security）• NIST SP800-57 “Recommendation on Key Management”

128bit安全性が求められる世界へ︕
例1: オレンジ⾊で⽰された80bit以下の強度では情報を保護することは認められていません。
例2︓ 3DESは112bit securityを持つとされていますが、そのアルゴリズムの利⽤は2023年まで推奨とされています。（参照︓NIST SP800-131A）
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

13⽇本語での情報はないの︖という声に向けて• 暗号強度要件（アルゴリズム及び鍵⻑選択）に 関する設定基準• 前ページにある「NIST SP800-57」と同様なドキュメント
CRYPTREC暗号リストのアルゴリズムが例⽰

https://www.cryptrec.go.jp/list/cryptrec-ls-0003-2022.pdf
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

14現⾏暗号に脅威になる量⼦コンピュータ• どんな量⼦コンピュータでも暗号の安全性に影響あるの︖

答えは「No」︕• 具体的には「誤り訂正機能を有する⼤規模な量⼦ゲート型量⼦コンピュータ」が必要となる• 別名「CRQC: Cryptographically Relevant Quantum
Computer / 暗号解読可能な量⼦コンピュータ」と呼ばれる

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

15

では、CRQCによるリスクはどんなもの︖

攻撃とリスク例
ハーベスト攻撃• 攻撃者が⼊⼿していた過去の暗号化データを⼀気に解読デジタル署名の改ざん• 過去のデジタル署名付き⽂書の信頼が喪失する

これらのリスクが許容できないならば暗号の更新（=PQC）などが必要
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

16

現⾏暗号への影響
No

暗号の種類

現⾏暗号例

脅威となる
量⼦アルゴリズム

効率的に解ける問題

暗号への脅威望ましい対策

1

共通鍵暗号

AES

Groverʼs Alg

データ探索問題

限定的Simonʼs Alg

周期探索問題限定的

鍵⻑の伸⻑/暗号利⽤モードの変更

RSA暗号

Shorʼs Alg

素因数分解

⾮常に⼤きいPQCへの移⾏

4DSA/ECDSA

Shorʼs Alg

離散対数問題

5PQC（現状）未発⾒ー

現在なしー

23

公開鍵暗号

CRQCが実現されたら現⾏暗号は全てダメになるの︖と気になる• 共通鍵暗号への影響は限定的
この⼤きな影響に対策を• 公開鍵暗号への影響が⼤きい計画する必要がある
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

17

Agenda• 暗号の危殆化• 暗号移⾏を招く︖︕ 2つの「暗号の2030年問題」• 我々を取り巻く環境

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

18暗号移⾏︓ 暗号の「2010年問題」とは︖• 2010年問題のきっかけ ⇨“NISTʻs Policy on Hash Functions - March 2006”

https://csrc.nist.gov/projects/hash-functions/nist-policy-on-hash-functions「2010年末でSHA-1の利⽤停⽌、SHA-2への全⾯移⾏」という声明※背景: SHA-1を含む複数アルゴリズムへの攻撃が公開された
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

19暗号移⾏の事例: TLS 1.2• 2008年発⾏RFC5246「TLS1.2」に注⽬。2014年の利⽤率 ⇨ 28%
2011年頃から様々な攻撃が公表された状況だが時間はかかった...
100.0
90.0
対応実績（%）

80.0
70.0
60.0
50.0
40.0

SSL 2.0

30.0

SSL 3.0

20.0

TLS 1.0

10.00.0

TLS 1.1
2012.05 2013.02 2014.02 2015.02 2016.02 2017.02 2018.02 2019.02 2020.02 2021.02 2022.01 2023.05

SSL 2.0

32.7

28.3

24.2

14.4

9.1

5.4

3.4

2.0

1.3

0.6

0.4

0.2

SSL 3.0

99.9

99.8

99.4

47.3

28.2

17.9

12.7

8.2

6.0

3.8

3.1

1.9

TLS 1.0

99.4

99.4

99.3

99.7

98.4

95.2

89.6

70.0

61.5

48.7

44.0

31.6

TLS 1.1

1.0

9.4

25.7

51.5

70.7

81.5

84.9

78.5

71.5

54.5

48.1

34.3

TLS 1.2

1.4

11.9

28.2

54.5

72.9

84.2

90.1

94.7

96.8

99.3

99.6

99.9

11.6

25.0

42.9

51.4

62.1

TLS 1.3
年数Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

TLS 1.2
TLS 1.3

SSL Labs Pulseのデータにより講演者がグラフ化

202つの「暗号の2030年問題」とは︖「暗号の2010年問題」の再来として、異なる移⾏観点で襲来︕︖
暗号の2030年問題の根っこ将来的な「暗号解読の進展」や「計算機環境の変化」を考慮し112bit安全の移⾏計画

1つ目
128bit安全な暗号への移⾏※ NIST SP 800-57 で記述

CRQCによる現⾏暗号へのリスクが許容できない
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

2つ目

PQCへの移⾏21

暗号の2030年問題︓ 128bit安全性への移⾏• 128bit安全なアルゴリズム ⇨ 「RSA-3072」や「RSA-4096」• RSA暗号だとデータサイズが⼤きい・・・。

• DKIMからの視点だと「 DNS の UDPパケット (512 byte) 」の制約あり• データサイズが⼤きい際には「楕円曲線暗号/ECC」が活⽤

EdDSA※ ECDSAでないことに注意

https://datatracker.ietf.org/doc/html/rfc8463
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

22

暗号の2030年問題︓ PQCへの移⾏• 「PQCへの暗号移⾏」の期⽇が2030年 ⇨ 「暗号の2030年問題」• NISTが2024年にPQCに関する標準仕様を公開• 2030年までに暗号移⾏を実⾏（あと6年弱︕︕）• 守るべきデータは︖ 移⾏するシステムの順番は︖ セキュリティ
レベルは︖ など決定する必要ある
イマココ

DHS「Preparing for Post-Quantum Cryptography: Infographic」より
https://www.dhs.gov/sites/default/files/publications/post-quantum_cryptography_infographic_october_2021_508.pdf
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

23

NIST PQC標準化（1/2）• 2016年にNISTがPQC標準化計画の発表を⾏い、2022年7⽉にRound 3の結果として4つのアルゴリズムが選定• Round 4として標準化が⾒送られた4⽅式に対して追加評価が⾏わられており、少なくとも１⽅式は選定される⽅針。
選定アルゴリズム（2022年）

公開鍵暗号/鍵共有

デジタル署名• CRYSTALS-KYBER• CRYSTALS-DILITHIUM• FALCON• SPHINCS+

Round 4（追加評価） ••
•
•

BIKE
Classic McEliece
HQC
SIKEー• 現在、上記に加えて「 Additional Digital Signature Schemes Round 1 」が実施されている。
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

24

NIST PQC標準化（2/2）• Round4として公開鍵暗号/鍵共有は検討されているが・・・
検討中のデジタル署名候補は残っていない︕ 格⼦ベース以外を急募• 現在、40⽅式が提案中• 実現⼿段も様々︕

Ø 符号ベース、同型写像、多変数多項式など6種類以上

https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

25具体的なPQCアルゴリズムとデータサイズ※ 128bit安全相当を実現した際のデータサイズ

カテゴリー

アルゴリズム名利⽤する問題データサイズ（byte）
公開鍵

公開鍵暗号/KEM

デジタル署名CRYSTALS-KYBER

Module-LWE問題

BIKE

QC-MDPC符号のSDP

Classic McEliece

Gappa符号のSDP

HQC

秘密鍵

暗号⽂/署名736

1,6328002,542

267

2,542

319,488

9,216

128

Quasi-Cycle符号のSDP

2,819

2,859

5,622

CRYSTALSDILITHIUM

Module-LWE問題

1,184

2,800

2,044

FALCONSIS問題

897

4,097

690

SPHINCS+

ハッシュ関数の衝突探索問題

3264

8,080

“https://www.jstage.jst.go.jp/article/isciesci/65/2/65_60/_pdf/-char/ja”の第１表より作成• DKIM視点では「 DNS の UDPパケット (512 byte=4096bit) 」の制約があるので、このまま素直に移⾏は厳しそう
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

26

FIPS20x 発⾏に向けた現状• NISTは2023年8⽉24⽇に初版が公開済み︕

FIPS 203 〜 205 の3つ公開• 暗号化/KEM• 格⼦ベース• デジタル署名• 格⼦ベース• ハッシュ関数ベース
https://csrc.nist.gov/news/2023/three-draft-fips-for-post-quantum-cryptography
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

27

いきなり「PQCへの移⾏」実施する︖• 4つのアルゴリズムが存在するので「PQCへの完全移⾏」ができるのでは︖ という疑問が残る

PQCの安全性

製品/実装の準備
モヤモヤする点

既存環境への影響
このモヤモヤを解決するのが「ハイブリッドモード」
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

28

ハイブリッドモードとは• 多くの標準化団体等でPQCへの暗号移⾏に関連して、ハイブリッドモードが取り上げられているが、統⼀された定義は存在しない。
• NISTØ 「利⽤されるコンポーネントが⼀つでも壊れていない限り、期待されたセキュリティプロパティを確保すること」と「Backwards compatibility（下位互換性）」が⼤事• IETFØ 現⾏暗号によって達成される安全性にPQC の性質を付与し、それぞれのアルゴリズムで独⽴した処理するのではなく、どちらかが安全ではない状態になっても、いずれかのアルゴリズムによって守られることが担保されるような構成法
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

29

ハイブリッドモードの構成法︓鍵交換• 概念的には「現⾏暗号」と「PQC」をシンプルに組合わせる
現⾏暗号
鍵交換

PQC
鍵交換

鍵導出
暗号化鍵

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

例えば、次のようなケースを考える＜量⼦計算機が登場︕＞• 現⾏暗号は解読されるが、PQCは安全なので守られる＜PQCに脆弱性が発⾒︕＞• PQCは機能しないが、⻑年利⽤されている現⾏暗号は安全なので守られる
ハイブリッドモードのメリット• 新技術であるPQCを実社会で運⽤することができ、改善を⾏える。
30

実社会でのハイブリッドモード
実社会での利⽤法は「ハイブリッド暗号」が主流。
• 「共通鍵暗号」と「公開鍵暗号」を組み合わせた暗号利⽤⽅法• 構成技術の特徴は以下のとおり
Ø 共通鍵暗号︓処理が⾼速だが、安全な鍵交換（配布）が困難
Ø 公開鍵暗号︓処理は低速だが、鍵交換（配布）が容易• 具体的な事例︓SSL/TLS
データ

A

B
PQCを追加鍵交換（公開鍵暗号）

暗号化
データ

暗号化（共通鍵暗号）

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

31

Agenda• 暗号の危殆化• 暗号移⾏を招く︖︕ 2つの「暗号の2030年問題」• 我々を取り巻く環境

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

32

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

33

IETF概要（1/3）• Internet Engineering Task Force• インターネットに関する技術の国際標準を策定する組織

1986 年1⽉が第1回︕︕• 理念• “We reject kings, presidents and voting. We believe in rough consensus
and running code.” David Clark (1992)• ⽣産物• RFC （Request for Comments）を発⾏• インターネットを技術的な側⾯を⽀えている• 活動• 年3回開催（3⽉、7⽉、11⽉）で１週間• 参加者数︓1500〜2000⼈• 参加費︓右図参照⇨• 参加資格︓誰でもOK
https://registration.ietf.org/118/
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

34

IETF概要（2/3）
IETFARTWG

WG

WG

7 Area145 WGs
15 RGs(2023.9現在)

INT
WG

WG

IRTF
SEC

WG WG

WG

TSV
WG

WG

WG

WG

RG

RG

RG

GEN （General） : 2
ART （Applications and Real-Time） :37
INT （Internet） : 16
OPS （Operations and Management） : 15
RTG （Routing） : 25
SEC （Security）︓25
TSV （Transport and Services） : 10https://datatracker.ietf.org/wg/
https://datatracker.ietf.org/rg/
IRTF ︓ 15

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

35

IETF概要（3/3）• IETF/IRTFで主にPQCが関係するWG/RGは以下のとおり
エリア
IETF

IRTF

GENARTINTOPSRTG
SEC
TSV

代表的なWG
gendispatch, shmoo
httpbis, satp, uta, cbor etc.
6man, 6lo, lpwan, lwig etc.
iotops, dnsop, v6ops etc.
PQC移⾏を検討
idr, manet, ospf, roll etc.
privacypass, tls, rats, mls, lake, pquip etc.
quic, tcpm etc.
pearg, t2trg, ufmrg, cfrg etc.
暗号⾃体を検討

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

36

pquip (Post-Quantum Use In Protocols)• 2023年3⽉開始。PQC移⾏の問題、IETFでのPQC対応について議論
Ø PQCへの移⾏をサポートするための運⽤や設計ガイドラインを作成

https://datatracker.ietf.org/wg/pquip/about/
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

37

pquipにおける技術動向• IETF117（2023年7⽉開催）でPQCへの移⾏に必要な情報が共有

https://datatracker.ietf.org/meeting/117/materials/slides-117-pquip-pqt-hybridterminology-00

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

https://github.com/ietf-wg-pquip/state-of-protocols-and-pqc

38cfrg (Crypto Forum)• 将来のインターネットで利⽤する暗号技術を検討
Ø いくつかPQCに関する検討が実施

https://datatracker.ietf.org/rg/cfrg/about/
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

39

参考情報: CRYPTREC 外部評価報告書• ハイブリッドモードについて詳細を把握したい⽅へ• ハイブリッドモードの技術動
向を整理
Ø 標準化動向Ø 利⽤可能なアルゴリズム
候補Ø ハイブリッドモードの取り扱い
Ø 安全性及び評価 など
https://www.cryptrec.go.jp/ex_reports.html
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

40

参考情報: 技術ブログ• PQC関連やIETFにおける最新の技術動向が気になる⽅へ• GMOイエラエの技術ブログでPQC関連の技術動向は随時発信していきます︕

https://gmo-cybersecurity.com/blog/ietf117-pquip-report/
Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

41

まとめ
「耐量⼦計算機暗号（PQC）のココントコ」として、お話しさせていただきました。
• なんでPQCが必要になったの︖• 暗号アルゴリズムの安全性• 暗号の危殆化とは︖• 耐量⼦計算機暗号（PQC）とは︖• 暗号移⾏とは︖
Ø 我々は暗号移⾏というイベントは未体験なのか︖
Ø 2つの「暗号の2030年問題」• IETFでのPQCに関する動向

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

42何か気になることなどあれば・・・• E-mail• satoru.kanno@gmo-cybersecurity.com• SNS• X (旧 Twitter)• https://twitter.com/satorukanno• Facebook• https://www.facebook.com/satoru.kanno

お気軽にご連絡ください︕

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

43

Copyright © GMO Cybersecurity by Ierae, Inc. All Rights Reserved.

44