PKI Day 2018 事前資料 ( 発表資料 ), Tokyo, Japan before ROCA / after ROCA / beyond ROCA から見えてくる RSA 暗号実装の闇セキュリティ本部セキュリティ情報統括室須賀祐治 Internet In

Size: px

Start display at page:

Download "PKI Day 2018 事前資料 ( 発表資料 ), Tokyo, Japan before ROCA / after ROCA / beyond ROCA から見えてくる RSA 暗号実装の闇セキュリティ本部セキュリティ情報統括室須賀祐治 Internet In"

まいえなかきむら
4 years ago
Views:

1 PKI Day 2018 事前資料 ( 発表資料 ), Tokyo, Japan before ROCA / after ROCA / beyond ROCA から見えてくる RSA 暗号実装の闇セキュリティ本部セキュリティ情報統括室須賀祐治 Internet Initiative Japan Inc. 1

2 2018 Internet Initiative Japan Inc. 2

3 鍵生成 RSA 公開鍵暗号どでかい素数 p, q を 2 つ選択 N:= pq, e:= 65537( 例えば ) 公開鍵 N を素因数分解することは困難 e は φ(n)=(p-1)(q-1) と素 d:= e -1 mod (p-1)(q-1) 秘密鍵 p か q が分かると d も導出可能暗号化 c = m e mod N 復号 c d mod N = m まだまだ圧倒的に利用されている一方で TLS1.3 では排除 ( 鍵交換署名として ) 逆に使えばデジタル署名にもなる 2018 Internet Initiative Japan Inc. 3

4 サーバ証明書も RSA は大きなシェアを持ってはいるけど 2018 Internet Initiative Japan Inc. 4

5 秘密鍵が漏洩したときの影響影響の分類 (1) 暗号化された通信の暴露 (2) サーバのなりすまし (3) 不正ログインもしくはクライアントのなりすまし詳細 SSL/TLS や SSH サーバとクライアントの通信を傍受できる環境において, 暗号化を行っているにも関わらず通信内容を把握することができる DNS 詐称やネットワークの乗っ取りが可能な環境において, SSL/TLS や SSH サーバになりすますことができる SSL/TLS でのクライアント認証のように公開鍵証明書を用いたログインが可能になる (4) 不正プログラムへのコード署名コードサイニング用の公開鍵証明書の秘密鍵が漏洩することで, 当該証明書によって保証されたプログラムであるかのように見せることができる大前提 : 秘密鍵は漏洩しないという仮定 2018 Internet Initiative Japan Inc. 5

脱線 : これと混同しないように Return Of Bleichenbacher's Oracle Threat (ROBOT) The ROBOT Attack https://robotattack.

6 脱線 : これと混同しないように Return Of Bleichenbacher's Oracle Threat (ROBOT) The ROBOT Attack Padding Oracle 攻撃 BEAST 攻撃とか POODLE 攻撃とかと同様に何度もトライ & エラーを繰り返し過去のメッセージを復元するという類の攻撃よく知られている Bleichenbacher 攻撃の亜種 2018 Internet Initiative Japan Inc. 6

7 脱線 : これと混同しないように PKCS#1 v1.5 暗号化の問題 TLS や S/MIME,JOSE(JSON 暗号化 ), XML 暗号化などで利用される暗号化形式で潜在的な脆弱性を抱えてた回避する実装方法が TLS 仕様にも書かれているがそれが複雑で分かりにくいから対応しきれなかった古い実装 ( 例えば JSSE: CVE ) も露呈 RSA PKCS #1 v1.5 暗号化は CRYPTREC では互換性維持のために継続利用を容認 1 軍でも 2 軍でもなく戦力外通告を出されている方式 2018 Internet Initiative Japan Inc. 7

8 2018 Internet Initiative Japan Inc. 8

9 Debian OpenSSL(2008) Debian の特定バージョンにおける OpenSSL を使って鍵生成を行った場合, 極端に少ない鍵空間からしか秘密鍵を導出していないという問題年にアドバイザリが発行されていたにも関わらず, 現在でもその脆弱な鍵を利用しているサイトが存在している Internet Initiative Japan Inc. 9

10 ある意味 RSAの致命的な問題 (Ron was Wrong 2012) 公開鍵 1 公開鍵 2 N (= p q) N1 = p1 q N2 = p2 q ユークリッド互除法 p q q 素因数分解は困難 (RSA はこの困難性に安全の根拠を置いている ) 因数を見つけるのは容易 N1 N2 p1 q p2 q 2つの公開鍵が素因数分解できてしまう Internet Initiative Japan Inc. 10

11 この状況をグラフ表現するとグラフ表現頂点 : 素数辺 : 2 素数を結ぶ辺の存在 = 公開鍵の存在 N N1 N2 p q p1 q p Internet Initiative Japan Inc. 11

12 あるべき姿 2 素数を選んで辺を結んだら (N を計算したら ) ほかのグラフと頂点を共有していない N1 N2 p1 q1 p2 q Internet Initiative Japan Inc. 12

13 しかし急にこういうことにほかのグラフと頂点を共有していなかったのに勝手に結ばれてしまうこともありうる N1 N3 N2 p1 q1 p2 q Internet Initiative Japan Inc. 13

14 選んだ素数が偶然重なる可能性ランダムに選択したつもりの素数がほかと偶然重なる可能性が 0 ではないことは RSA アルゴリズムの根本的な問題素数定理素数がどのくらい存在するか知る指標 2048 ビット RSA で用いられる 1024 ビット素数の候補は素数定理から約個も存在容易に重複するものではないしかし素数生成時のアルゴリズムに偏りがある = 個の全空間から素数を抽出していない場合にこの問題が起き得る 2018 Internet Initiative Japan Inc. 14

PRNG の問題素数生成時に用いられる擬似乱数生成モジュールがまずいと問題が起きる 9 つの素数しか生成しないデバイスの存在 36(= 9 C 2 ) 個の公開鍵は異なる 9 個の秘密鍵の組み合わせで構成 Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W.

15 PRNG の問題素数生成時に用いられる擬似乱数生成モジュールがまずいと問題が起きる 9 つの素数しか生成しないデバイスの存在 36(= 9 C 2 ) 個の公開鍵は異なる 9 個の秘密鍵の組み合わせで構成 Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, Christophe Wachter, Ron was wrong, Whit is right, Internet Initiative Japan Inc. 15

16 PKI Day 2012 での私案 Internet Initiative Japan Inc. 16

17 Rump session at CRYPTO2013 Heninger らが報告 Factoring RSA keys from certified smart cards: Coppersmith in the wild Factoring as a service 2018 Internet Initiative Japan Inc. 17

18 Taiwan Citizen Digital Certs 300 万枚の証明書を国営 LDAP サーバから入手うち 230 万枚は 1024-bit RSA, 70 万枚は 2048-bit 2018 Internet Initiative Japan Inc. 18

19 素数の特徴がひどい 2018 Internet Initiative Japan Inc. 19

20 2018 Internet Initiative Japan Inc. 20

21 ここまで RSA をディスってきたけど間違えてはいけないのは暗号アルゴリズムそのものとしての RSA はまだ大丈夫死亡 :DES/MD4/MD5 環境によっては利用可 :RC4/SHA Internet Initiative Japan Inc. 21

22 技術的要因以外の問題問題の本質は技術的なことだけではないコスト負担の問題お互いに押し付けあわないでそれぞれの立ち位置でカバーしあうことが大切まだまだ啓蒙活動が必要なのかもしれない一例 ) 暗号学者と実装者との理解の乖離ツールの使用者 : 使い方がまずいツールの実装者 : 実装がまずいツールの設計者 : 設計仕様がまずい - PRNG - 暗号 - CBC 2018 Internet Initiative Japan Inc. 22

23 Predictions (December 2012) ほかのアルゴリズムプロトコルへの横展開楕円暗号などほかのプリミティブでも起こる POP/SMTP/FTP over SSL etc こっちの方が検証系はやばそうな気も Low entropy を利用した攻撃 DSA 署名生成時のように一時鍵セッション鍵の鍵空間の狭さを利用した脆弱性の発見公開鍵系に依存しないはず ( ハードコーディング系 ) CA や主要サイトの鍵生成時の環境を特定し鍵生成アルゴリズムをぶん回して鍵を特定 2018 Internet Initiative Japan Inc. 23

24 DSA でも同じことが起こる秘密鍵生成時ではなく署名生成時に発生共通パラメータ (p, q, g, y) 秘密鍵 x, 公開鍵 y = g x mod p 署名生成一時鍵 (ephemeral key) k をランダムに選択 r:= (g k mod p) mod q s:= k -1 (H(m)+xr) mod q (r,s): 署名 2018 Internet Initiative Japan Inc. 24

25 DSA における k 選択時の問題もし k がばれると署名 (r,s) から秘密鍵 x が暴露 x= r -1 (ks-h(m)) mod q cf) s:= k -1 (H(m)+xr) mod q を式変形したら上が得られる同じ k を用いて 2 つの署名を生成すると r:= (g k mod p) mod q これが共通 s1:= k -1 (H(m1)+xr) mod q s2:= k -1 (H(m2)+xr) mod q k= (H(m1)-H(m2))(s1-s2) -1 mod q 2018 Internet Initiative Japan Inc. 25

26 富樫風で申し訳ないが ECDSA でも同じ問題がある 2018 Internet Initiative Japan Inc. 26

27 Internet Initiative Japan Inc. 27

28 2013 年 12 月 2018 Internet Initiative Japan Inc. 28

29 実際に盗難にあっている 2018 Internet Initiative Japan Inc. 29

30 Internet Initiative Japan Inc. 30

31 The Return of Coppersmith's Attack ROCA: Vulnerable RSA generation (CVE ) KRACKsと同じくACMCCS2017で発表 2018 Internet Initiative Japan Inc. 31

32 ROCA RSA 鍵生成モジュール (Infineon Technologies AG 製 ) の問題を指摘 750,000のエストニアIDカードに影響実は 1 ヶ月前の 9 月に既報だった Internet Initiative Japan Inc. 32

33 影響度 ( 論文で指摘されているもののみ ) もっと精査すると, 他にも出そうな感じ TPM (Trusted Platform Module) : 基本的なセキュリティ関連の機能 ( 主に暗号化キー ) を提供するように設計されたマイクロチップ Internet Initiative Japan Inc. 33

34 日本のベンダーでも影響あり 2018 Internet Initiative Japan Inc. 34

35 著者によるツールの公開 RSAlib( 今回問題となったモジュール ) で生成されたものかどうかをチェック可能オンライン版や S/MIME 版 (roca@keychest.net) もある Internet Initiative Japan Inc. 35

36 Fingerprinting 驚くほどシンプル (38 個の素数でチェック ) Internet Initiative Japan Inc. 36

37 ROCA の本質 ( ここは論文中の主張を尊重 ) PRNG の問題ではない鍵生成アルゴリズムのバグである PRNG 生成プログラム乱数列バギーな鍵生成プログラム 2018 Internet Initiative Japan Inc. 37

もうひとつ面白い事実ビット数によっては安全なものもあるのが興味深い https://crocs.fi.muni.

38 もうひとつ面白い事実ビット数によっては安全なものもあるのが興味深い Internet Initiative Japan Inc. 38

39 再掲 :PKI Day 2012 での私案 Internet Initiative Japan Inc. 39

40 2018 Internet Initiative Japan Inc. 40

41 PKI Day 2012 での予言 Internet Initiative Japan Inc. 41

公開鍵から鍵生成ライブラリを推定 ACSAC2017 で ROCA の次を発表 https://crocs.fi.muni.

42 公開鍵から鍵生成ライブラリを推定 ACSAC2017 で ROCA の次を発表 Internet Initiative Japan Inc. 42

43 すごいぃぃぃというか怖い Internet Initiative Japan Inc. 43

44 まとめ 2018 Internet Initiative Japan Inc. 44

45 参考 Internet Initiative Japan Inc. 45

46 RSA はどうなるん? 量子計算機で素因数分解 1994 年 :Shor アルゴリズム RSA は素因数分解の困難性,(EC)DH は離散対数問題の困難性が前提量子計算機を用いることにより, これら 2 つの問題が多項式時間で解けることが示された 1996 年 :Grover アルゴリズムこの 2 つの事実で暗号屋さんが動 ( 働 ) いてるもちろんお金も ( 例 :EU Horizon 2020 Projects) 2018 Internet Initiative Japan Inc. 46

47 見積もり現在のアーキテクチャの計算機でnビット安全性を有していた暗号アルゴリズムは量子計算機の解読能力によるとn/2ビット安全性しか確保できない Internet Initiative Japan Inc. 47

耐量子 (Post Quantum) 暗号量子計算機が完成したらどうなるの? 量子計算機ができても大丈夫なようにしよう https://csrc.

48 耐量子 (Post Quantum) 暗号量子計算機が完成したらどうなるの? 量子計算機ができても大丈夫なようにしよう Internet Initiative Japan Inc. 48

49 NIST PQC Standardization 2025 年くらいを目処に標準化 Internet Initiative Japan Inc. 49

50 NIST 曰くコンペティションじゃないポートフォリオの作成だけ理論ベースが違うものがたくさん並んでてよい一方で軽量暗号 (80 ビット安全性 ) 自動車? IoT デバイス向け? これ本当に要るのか議論してなくない? CRYPTRECにも調査 WGあり 2018 Internet Initiative Japan Inc. 50

51 お問い合わせ先 IIJ インフォメーションセンター TEL: (9:30~17:30 土 / 日 / 祝日除く ) info@iij.ad.jp Internet Initiative Japan Inc. 51

Internet Infrastructure Review Vol.39 - フォーカス・リサーチ（1）

Internet Infrastructure Review Vol.39 - フォーカス・リサーチ（1） 2. フォーカスリサーチ (1) RSA アルゴリズム鍵生成モジュールの実装問題 (ROCA) 2.1 はじめに 2017 年 10 月 ACM CCS 2017 *1 の論文発表予定をトリガーとして暗号技術に関連する大きな報道がありました 1つは KRACKsと呼ばれるWPA/WPA2の仕様上の問題に起因する攻撃の報道です *2 プロトコルそのものの問題であったことから大きな問題になると予想され

PKI Day 2018 事前資料 ( 発表資料 ), Tokyo, Japan before ROCA / after ROCA / beyond ROCA から見えてくる RSA 暗号実装の闇 セキュリティ本部セキュリティ情報統括室須賀祐治 Internet In

PKI Day 2018 事前資料 ( 発表資料 ), Tokyo, Japan before ROCA / after ROCA / beyond ROCA から見えてくる RSA 暗号実装の闇セキュリティ本部セキュリティ情報統括室須賀祐治 Internet In