サイバーセキュリティ・リレー講座 (初級)2020年9月15日

暗号技術に基づくサイバーセキュリティ五十部 孝典
兵庫県立大学大学院 応用情報科学研究科

本講義の内容
1. 暗号技術基礎
2. 暗号起因の攻撃の例
3. 暗号の適切な利用1. 暗号技術基礎

本講演で紹介する暗号技術• 共通鍵暗号• メッセージ認証コード• 公開鍵暗号• ハッシュ関数

現代暗号の特徴• 古典暗号• 暗復号アルゴリズム非公開• アルゴリズムを隠すことで秘匿性を確保• 秘匿の機能が中心• 現代暗号• 暗復号アルゴリズム公開• 鍵さえ秘密にすればよい• 計算量的安全性• 計算量の限られた攻撃者に対して安全• 鍵長に強度が依存 = 鍵を探すコスト• 128 bit key = 2128の探索コスト(スパコン京で宇宙が誕生してから計算しても終わらない）• 秘匿だけでなく，署名や認証といった様々な機能が実現可能共通鍵暗号• 暗号化と復号に共通の鍵を用いる方式• 特徴: 一般的に高速だが，事前鍵共有が必要• 用途: データ暗号化，改竄検知(MAC)，認証など• 代表的アルゴリズム: DES, AES, HMAC, CMAC
秘密鍵 K
平文
暗号アルゴリズム

暗号化

=暗号文

秘密鍵 K
平文
復号アルゴリズム

復号

公開鍵暗号• 暗号化と復号に異なる鍵を用いる方式• 特徴: 事前鍵共有不要(片方の鍵公開可能)．一般的に低速• 用途: 共通鍵の鍵共有，デジタル署名，認証など• 代表的アルゴリズム: RSA, ECC
公開可能(誰に知られても問題ない)≠

A の公開鍵平文

A だけが知っている
A の秘密鍵平文

数学的に困難な問題
暗号アルゴリズム

暗号化

暗号文

復号アルゴリズム

復号

“暗号学的”ハッシュ関数• 任意長のデータを固定長データに圧縮• データの “指紋” を取る技術と呼ばれることもある• 用途: デジタル署名，パスワード保護など• 一般的に共通鍵暗号技術を応用しているため高速• 代表的アルゴリズム: MD5, SHA-1, SHA-256, Keccak, ...
暗号学的ハッシュ関数 H
任意長データ : m0xA993E36F47..

固定長データ : H(m)(160bit, 256bit,…)

“暗号学的”ハッシュ関数の特徴• 原像復元困難性(Preimage resistance)• ハッシュ値のみから元々のメッセージを計算(復元)することが困難• ビットコインのマイニングに利用

暗号学的ハッシュ関数 H
任意長データ : m

計算量的に困難

0xA993E36F47..

固定長データ : H(m)(160bit, 256bit,…)

“暗号学的”ハッシュ関数の特徴• 衝突困難性(Collision resistance)• 同じハッシュ値になる 異なる 2 つのメッセージを見つけることが困難
暗号学的ハッシュ関数 H
任意長データ : m

暗号学的ハッシュ関数 H
任意長データ : m’

0xA993E36F47..

固定長データ : H(m)(160bit, 256bit,…)

0xA993E36F47..

固定長データ : H(m’)(160bit, 256bit,…)2. 暗号起因の攻撃の例

Keeloqへの攻撃• キーレスエントリーシステム• 80年代にMicrochip Technology Inc.により設計.

• 主要メーカで使われていた exp. Toyota, Honda, GM など.

• 64 bit keyのブロック暗号を使用．
• 暗号解読 [S+08]• 64 bit security→44 bit securityへ• 50 dual core computerで 2日で秘密鍵が導出可能．

問題点 : 弱い暗号 + 短い鍵長
[S+08] S.Indesteege et al “A Practical Attack on Keeloq”, EUROCRYPT 2008

MYFARE Classicへの攻撃• NXP製の非接触ICカード• ロンドンの公共交通で利用されるなど，2億以上のカードが流通．

• 非公開の独自暗号を利用．

• CRYPTO-1 (ストリーム暗号)• 暗号解読[N+08]• リバースエンジニアリングにより秘密の暗号アルゴリズムが露呈• 48 bit keyの暗号だと分かり，総当りで求めることができる.
• 更に暗号解読がされて，秒のorderで鍵導出可.

問題点 : 弱い暗号 + 短い鍵長 + アルゴリズム秘匿 (第三者評価ができない）[N+08]Nohl et al “Reverse Engineering a Cryptgraphic RFID Tag”, 17-th USENIX 2008

SSL/TLS• セキュリテイプロトコルSSL/TLSでストリーム暗号RC4が使用• 暗号解読[I+13]• 暗号文から平文を求めることが可能• SSLの場合，cookieが導出可能

問題点 : 弱い暗号 (脆弱性は知られていた)[I+13] T. Isobe et al., “Full Plaintext Attack on Broadcast RC4”, FSE 2013

Apple iMessageへの攻撃• AppleのiMessageの End-to-End Encryptionに対する攻撃[G+16]• 平文回復攻撃• 選択暗号文攻撃で，218のクエリで，平文に含めれる添付ファイルの256ビット鍵の232ビットを特定可能(時間は35時間)• 修正にはAppleの30人の技術者で4ヶ月

問題点 : 独自暗号プロトコル+ 非標準的な暗号利用[G+16]Christina Garman et al, “Dancing on the lip of the volcano: Chosen ciphertext attacks on apple imessage”. USENIX 2016

LINEの暗号化 Letter Sealingへの攻撃• LINEの暗号化モードLetter Sealingに対する攻撃[IM18]• 独自の暗号方式を使っており，その使い方に問題があり，なりすましやメッセージ改ざん攻撃が可能

問題点 : 独自暗号プロトコル+ 非標準的な暗号利用[IM18]T. Isobe and K. Minematsu, “Breaking the Message Integrity of E2E encryption of LINE”, ESORICS 2018

その他の攻撃事例• APOP• メールサーバ, クライアント間のPassword認証方式• ハッシュ関数MD5 の脆弱性 (衝突攻撃)により,Passwordが導出可• 問題 : 弱い暗号の利用• WEP• 無線LANの暗号化方式• ストリーム暗号RC4の脆弱性により，鍵が導出可．
• 問題 : 弱い暗号の利用 + 誤った使い方• Xbox• ブート時のプログラムの改ざんチェック• ブロック暗号TEAをハッシュ関数として利用• 問題 ：弱い暗号の利用 +誤った使い方

暗号を正しく使うことが重要その他の攻撃事例• APOP• メールサーバ, クライアント間のPassword認証方式• ハッシュ関数MD5 の脆弱性 (衝突攻撃)により,Passwordが導出可• 問題 : 弱い暗号の利用脆弱性が見つかった場合，• WEP暗号を正しく•修正には多くの金銭的，人的リソースが必要
無線LANの暗号化方式• ストリーム暗号RC4の脆弱性により，鍵がP導出可．
• 問題 : 弱い暗号の利用 + 誤った使い方• Xbox• ブート時のプログラムの改ざんチェック• ブロック暗号TEAをハッシュ関数として利用• 問題 ：弱い暗号の利用 +誤った使い方

使うことが重要原因• 暗号の正しくない使い方• 弱い暗号，独自暗号• 短い鍵長• まずい組み合わせ• まずい実装

正しい利用をすれば，これらの攻撃は簡単に防げる3.暗号の適切な利用について

暗号技術の不適切利用における脅威をふせぐには？
• 暗号技術の適切な利用が必要• 適切な「アルゴリズム」• 適切な「鍵長」• 適切な実装

暗号の危殆化ある暗号アルゴリズムについて，コンピュータの性能向上や解読技術の向上などに伴い，当初想定した安全性(セキュリティ上の性質)を保てない状況が発生すること
例えば• 計算機の発展を受けて• 解読技術の進化を受けて

計算機の発展を受けて• 鍵の全数探索の計算量• Keylength.com

解読技術による危殆化• ハッシュ関数SHA-1• 2005年に差分攻撃法により，期待より少ない計算量で衝突ペアを発見可能• SHA-1 の後継として，国際的なコンペを経てKeccakがSHA-3として選定• ストリーム暗号RC4• 2013年ストリーム暗号RC4は，出力の偏りより，現実的な計算量で暗号文から平文を回復可能• CRYPTRECはRC4を監視対象暗号へ，Google, Microsoftは使用を取りやめた．

• ロシア標準暗号 GOST
• 2011年，ロシア標準暗号GOSTが期待より少ない計算量で鍵導出可能• ISOから脱落，ロシアは新たな暗号を開発し国内標準化

電子政府推奨暗号リスト

適切な鍵長を選択する• 計算量的安全性と鍵長• 暗号アルゴリズムの安全性は「計算量的安全性」に基づく• 計算量的安全性• 実現可能な計算能力で解読可能か否かを評価する• 例えば，世界中のスパコンを集めても解読に1億年かかる...

• 鍵長が計算量的安全性を決める• 解読にかかる計算量は暗号の鍵長に依存する

NIST（米国立標準技術研究所 ）の推奨鍵長• 推奨鍵長に関する NIST 勧告(NIST SP 800-57)に従って選定
年

共通鍵

公開鍵

ECC～2013

ハッシュ(A)

ハッシュ(B)

80

1024

160

160

160

2014～2030

112

2048

224

224

160

2031～

128

3072

256

256

160
(単位はビット)

・「共通鍵」: 共通鍵暗号技術の鍵長，および HMAC で利用する鍵長
・「公開鍵」: 公開鍵暗号技術の RSA や DH 系スキームの法のサイズ
・「ECC」: 楕円曲線暗号技術における利用される体のサイズ
・「ハッシュ」: ハッシュ関数の出力サイズ(A): デジタル署名，ハッシュ関数単体での使用(B): HMAC, 鍵導出関数，擬似乱数生成

CRYPTREC推奨暗号リスト

安全性が80 bit

まとめ
本講義では以下のことを説明
1. 暗号技術基礎
2. 製品に対する暗号起因のサイバー攻撃• 弱い暗号や間違った使い方をした場合，実際に大きな被害• iMessageの場合修正にはAppleの30人の技術者で4ヶ月

3. 暗号の適切な利用• 暗号アルゴリズムと鍵長を適切に選択• 暗号の危殆化や計算機の進歩を考慮• 何か不明な点等ありましたら，お気軽にご連絡ください．
• takanori.isobe@ai.u-hyogo.ac.jp