yuuki_cryptography: A repository from thash

暗号の世界の言葉

暗号化 (encrypt) / 復号化 (decrypt)
- 暗号化と符号化 (encoding) を間違えないこと. 符号化は, m -> 01101101, というようなビット列への対応付にすぎない.
平文 (plaintext) / 暗号文 (ciphertext)
送信者 (sender) / 受信者 (receiver) / 盗聴者 (eavesdropper)
対称暗号 (symmetric cryptography) / 公開鍵暗号 (public-key cryptography)
- 対称暗号 (共通鍵暗号): 1 つの鍵で暗号化, 同じ鍵で復号化
一方向ハッシュ関数 (one-way hash function)
- 正真性 (integrity) を提供する. ハッシュ関数をかけることで機密性 (confidentiality) が守られるわけではない.
- たとえばデータが改ざんされていないことを調べるために利用する.
メッセージ認証コード (message authentication code)
- そのメッセージが改ざんされていないこと, および期待する通信相手からのものであることを確かめる.
- 正真性 (integrity) と認証を提供する.
デジタル署名 (digital signature)
- 正真性 (integrity) を確かめ, 認証と否認 (repudiation) 防止を行う. なりすまし (spoofing) を防ぐ.
  - 否認 (repudiation) ... 自分の主張をあとで翻すこと. 「そんなこと言ってません」的すっとぼけ, など.
擬似乱数生成器 (pseudo random number generator)
- 乱数は暗号技術において, 鍵の生成という重要な役割を担う
暗号 (cryptography) / ステガノグラフィ (steganography)
- 暗号は内容を隠す技法, ステガノグラフィはメッセージの存在そのものを隠す技法. 単純なステガノグラフィの例はタテ読み.
どんな暗号もいつかは解読される. 弱い暗号化は暗号化しないよりも危険. 暗号はセキュリティのほんの一部.

脅威と特性と道具箱

セキュリティに対する脅威	脅かされる特性	防衛のための暗号技術
盗聴 (秘密が漏れる)	機密性 (confidentiality)	対称暗号 (symmetric cryptography), 公開鍵暗号 (public-key cryptography)
改竄 (情報が書き換えられる)	正真性 (integrity)	一方向ハッシュ関数, メッセージ認証コード, デジタル署名
なりすまし (正しい送信者のふりをする)	認証 (authentication)	メッセージ認証コード, デジタル署名
否認 (後から私じゃないと言う)	否認不可能性	デジタル署名

問題

Q: 平文を暗号文に変換することを暗号化と呼ぶ ○/×
Q: 平文は人間が読むデータで, 暗号文はコンピュータが読むデータ ○/×
Q: 対称暗号では, 暗号化の鍵と復号化の鍵は等しい ○/×

暗号アルゴリズムと鍵

暗号	暗号アルゴリズム	鍵
シーザー暗号	平文の各文字を「指定した文字数」ずらすこと	ずらす文字数
単一換字暗号	「換字表」に従ってアルファベットを変換する	換字表
エニグマ	エニグマ機械によるアルファベット変換	日替わりの鍵 (各種パーツ)

暗号アルゴリズムと鍵を分ける意味. 鍵は毎回交換するけど, 暗号アルゴリズムは繰り返し使用する.

XOR

XOR (排他的論理和) は, 二回かけるともとに戻る.

0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0

あるふたつのビット列の XOR は, それぞれの桁数の bit ごとに XOR 演算してその結果.

使い捨てパッド (one-time pad)

無条件に安全 (unconditionally secure) であり理論的に解読不可能 (theoretically unbreakable) な暗号. 絶対に解読できない. バーナムによって考案され特許が取られている (失効済). なぜ解読できないかというと, たとえ Brute-force の途中で使い捨て鍵にたどり着いて正解の平文をゲットできたとしても, それが正しいことを判定することが出来ないから.

それでも実用的ではない. ∵ 以下のような問題がある:

鍵を安全に配送する事ができない. もし鍵を安全に配送できるなら, 別に暗号を使わず平文そのものを安全に送れるはずである
鍵自体は鍵として平文なので, これをどこかに安全に保管しておく必要がある. もし鍵を安全に保管できるなら, 別に暗号化したかったデータも安全に保管できるはずである
鍵の再利用が出来ない. "過去の通信記録の秘密を守る" ため, いつでもいつまでも使った鍵は秘密でなければならない
平文の長さに応じて鍵も長くなる
鍵の生成には擬似乱数ではなく, 再現性のない真の乱数を使う必要がある

=> 使い捨てパッド自体は使われていないが, アイディアはストリーム暗号 (Stream Chiper) に活かされている. ストリーム暗号では真のランダムなビット列の代わりに擬似乱数生成器によるビット列を使う

対象暗号

DES & AES

DES: Data Encryption Standard. 1977 アメリカで連邦情報処理標準規格に採用された対称暗号 (FIPS 46-3). 現在は Brute-force によって現実的な時間で解読できるため, 過去の暗号を復号化する目的以外で DES を使うべきではない.

DES は 64 bit の平文を 64 bit の暗号文に暗号化する.
DES の基本構造はファイステルネットワーク. この構造は便利で, 他のいろいろな暗号アルゴリズムで採用されている
DES はファイステルネットワークを 16 ラウンド繰り返す.

AES: Advanced Encryption Standard. DES に代わる新しい暗号アルゴリズムで, 提出された複数の候補の中から Rijndeal (らいんだーる) が選ばれた

Rijndeal はファイステルネットワークの代わりに SPN 構造というものを使う

ブロック暗号アルゴリズムであり, ブロック長 128bit (= 16 bytes) で, 1 byte ごとに subbytes 処理を行う. 次に出力を混ぜてくっつける. これで 1 ラウンド, 実際は 10-14 ラウンド実行する. 鍵の長さは 128,192,256 bit から選択可能.

ref: 暗号アルゴリズムには「ブロック暗号」と「ストリーム暗号」のパターンがある. ブロック暗号は状態を持たないけど, ストリーム暗号はどこまで処理したか, という状態を持つ必要がある

対象暗号を使うためには「通信相手に安全に鍵を送らないといけない」という課題が残る (鍵配送問題). これを解決するのが後で見る公開鍵暗号.

ブロック暗号のモード: 繰り返しの方法

DES, AES はブロック暗号. あるブロックをどう扱うか, を示したもの. 例えば AES (Rijndeal) で 128bit より長いデータを暗号化するのであれば、何回も AES を使う必要がある. 複数回使うときの繰り返し方をモードという.

最後のブロックがブロック長に満たないときはなんかで埋める. padding と言う

ECB: Electric CodeBook Mode

最初から順々にブロックに分けて暗号化していく一番簡単なモードが ECB (Electric CodeBook Mode).

ECB モードでは、平文ブロックと暗号ブロックが 1:1 対応する. つまりデータ中にたまたま全く同じ bit 列のブロックがあったとしたら, その 2 ブロックを暗号化したブロックは全く同じになる. これによって, 暗号を解読せずとも, ブロックにどんなデータが含まれるか, という情報さえあればある程度の操作が可能になってしまう.

たとえば銀行間送金で a から b に送金するというところを, a,b それぞれのアカウント情報が個々のブロックになっていると仮定すれば (この仮定ってどの程度現実的なの), 別に複合化しなくても送金側と受け取り側を入れ替えれば意味ある操作が可能.

[OK] CBC: Cipher Block Chaining Mode

一つ前の暗号文ブロックと平文ブロックの XOR をとってから暗号化を行う. 最初のブロックに対して「一つ前」の代わりに使うビット列が必要になるんだけどこれを "初期化ベクトル (initialization vector)" と呼ぶ. 初期化ベクトルには暗号化のたびに異なるランダムなビット列を用いる

これによって, たとえ平文が同じでも, ひとつ前のブロックが違えば暗号化結果も違ってくる. 攻撃者は初期化ベクトルのビット反転とかはできるけど, 暗号化ブロックに対して望む変化・操作を行うことは困難.

IPsec では CBC モードが使われている. トリプル DES を CBC モードで繰り返した "3DES-CBC" とか, AES に適用した "AES-CBC" とか. あとは Kerberos v5 でも利用されてる. シンプルだけど普通に実用的なモード.

CFB: Cipher FeedBack Mode

一つ前の暗号文ブロックを, 暗号アルゴリズムの入力に戻す (入力に戻す, とはつまりあるブロックの暗号化結果を暗号化アルゴリズムに渡して, それによって暗号アルゴリズムが毎回異なる, ということ).

CFB モードでは平文ブロックは暗号アルゴリズムによって直接暗号化されているわけではない. 平文ブロックから暗号文ブロックになるまでに作用しているのは, XOR だけ. 暗号化を行っていない.

CFB モードでは, 鍵ストリーム (key stream) を生成するための擬似乱数生成器として暗号アルゴリズムを用いている. 暗号アルゴリズムの出力をランダム (疑似) なビット列として見ると, 構造は使い捨てパッドと似ている. CFB はブロック暗号ではあるが, ブロック暗号を使ってストリーム暗号を作っていると考えることもできる.

CFB モードに対しては "再生攻撃 (replay attack)" が効く. 暗号文を解読しなくても, ブロックを保存しておいて次回の通信時に古いブロックで差し替える, ということが可能. 古い文を差し込む継ぎ目のブロックはエラーになるんだけど, 受け手は「通信エラーによるのか差し替えられてエラーになってるのか」判断できない.

再生攻撃に備えるには, メッセージ認証コード (8 章で説明) を使う必要がある.

現在では使われておらず, CTR モードを用いたほうが良い.

OFB: Output-FeedBack Mode

OFB モードはストリーム暗号. (あれ? ブロック暗号のブロック繰り返しの方法がモードの定義ではなかったのか)

CFB: 一つ前の暗号文ブロックを暗号アルゴリズムの入力にフィードバックする
OFB: 暗号アルゴリズムの出力を暗号アルゴリズムの入力にフィードバックする

CFB モードではブロックを順々に暗号化していく必要があるのだが, OFB モードでは平文ブロックとは無関係に暗号アルゴリズムをぐるぐる回し, XOR するためのビット列 (key stream) を予め準備しておくことが可能. 結果として, 暗号化が高速！

CTR モードを用いたほうが良い.

[OK] CTR: CounTeR モード

カウンターモード. 3 文字略語無理矢理だな. CTR モードはストリーム暗号で, 1 つずつ増加していくカウンタを暗号化して, 鍵ストリームを作り出す.

Practical Cryptography (Schneier, 2003) では CBC もしくは CTR が推奨モードとされている.

公開鍵暗号

1976 年, Whitfield Diffie と Martin Hellman がアイディアを発表. 1978 年, Rivest, Shamir, Adleman が具体的なアルゴリズム, RSA 暗号を発表.

対象暗号は暗号化のための鍵イコール復号化のための鍵だった.
一方公開鍵暗号は両者が別物. イメージはコインロッカー. コインはロッカーを閉じるための鍵 (暗号化のための鍵), 文字通りの鍵はロッカーを空けるための鍵 (復号化のための鍵)

鍵配送問題: 復号化してもらうための鍵を相手に渡すのだが, 鍵を安全に渡せるならそもそも暗号化しなくてもいいじゃん的な問題.

対策はいくつかあって

事前共有 (現実的には限界がある)
鍵配布センターを**に設け, 通信に際してセッションキーを生成, 各々の登録された鍵で暗号化して渡す (弱点になる, 負荷が集中する)
Diffie-Hellman 鍵交換 (11 章で取り扱う)
公開鍵暗号 (本章のテーマ)

公開鍵暗号では「暗号化のための鍵」は誰に知られても良いので「公開鍵」とか呼ばれる. 「復号化のための鍵」は「プライベートキー」と呼称. 秘密鍵, というと対象暗号の文脈でも使われたりするのでちょっと曖昧.

mod 演算

時計演算. 7^x mod 13 = 8 となるような x を求めるのは難しく, 時間を要する (離散対数). 離散対数は公開鍵アルゴリズムのひとつである ElGamal 方式で用いられている.

7^16 mod 12 を求める:

$ ruby -e 'p (7**16) % 12'
1

ハイブリッド暗号

対象暗号 + 公開鍵暗号．公開鍵暗号は速度が圧倒的に遅いという問題があった．そこでハイブリッド暗号では，以下のような方法を採用する

メッセージ自体は対象暗号で暗号化して速度を確保
対象暗号の暗号化で使うセッション鍵 (これは擬似乱数生成器で生成) を，公開鍵暗号で暗号化する

PGP や SSL/TLS でもハイブリッド暗号が採用されている

ハイブリッド暗号の他にも，複数の暗号技術を組み合わせたものはいろいろとある．たとえば

デジタル署名 = 一方向ハッシュ関数 + 公開鍵暗号
証明書 = 公開鍵 + デジタル署名
メッセージ認証コード = 一方向ハッシュ関数 + 鍵

他の例が知りたければシュナイアー『暗号技術大全』おすすめ，とのこと

一方向ハッシュ関数

入力 (メッセージ) と出力 (ハッシュ値) がひとつずつ
ハッシュ値の長さはメッセージとは無関係. "一方向ハッシュ関数は固定サイズのハッシュ値を計算する"

"一方向ハッシュ関数" は "固定長の出力" と言ってしまって正しいか? => 正しそう

衝突耐性

衝突 (collision): 2 つの異なるメッセージが同じハッシュ値を持つこと
衝突耐性 (collision resistance): 衝突を見つけることが困難な性質
- 強衝突耐性: ハッシュ値が一致するような (ハッシュ値はなんでもよい), 異なる 2 つのメッセージを見つけることが非常に困難
- 弱衝突耐性: あるハッシュ値が与えられたとき, そのハッシュ値を持つ別のメッセージを見つけ出すことが非常に困難

SHA-1

元メッセージは 2^64 bit 未満である必要がある. 出力は 160 bit.

パディングで 512 bit の倍数にそろえて, 512 bit をブロックとして扱い 32 bit の値を 80 個 (W0-W79) 計算 (※). 入力ブロックに対して 80 step ずつの処理を行い, "内部状態" (A,B,C,D,E... それぞれ 32 bit の値) を計算

※ 部分: 512 bit を 32 bit x 16 個に分解して W0-W15 を作る. W16-W79 は W16 = (W0 AND W2 AND W8 AND W13) を 1 ビット回転. みたいに作る. 1 bit 回転するとは, 最上位 bit を最下位に移すこと.

一般化すると Wt = (W(t-16) AND W(t-14) AND W(t-8) AND W(t-3)) を 1 ビット回転

一方向ハッシュ関数への攻撃

攻撃者は, データを改竄しつつ, ハッシュ値を同じにすることを考える. 文章の末尾に空白を追加したりして "意味を変えずに違うデータに調整する" 方法はいろいろある. 目的の嘘データに書き換えたうえで, ハッシュ値が元と同じものになるように調整する方法を探し出す.

同じ意味のデータを大量に作ってハッシュ値がおなじになるものを探す. すなわちブルートフォースアタック. これは "弱衝突耐性" を破ろうとするもの (ハッシュ値が与えられてからの攻撃ストーリーなので)

"弱衝突耐性" は既にデータがひとつあり, そのハッシュ値があるところが攻撃のスタート. じゃあ "強" は? => 攻撃者がふたつともデータを作れるようなケース. なるほどそれならかなりやり放題に思える, 攻撃者がふたつのデータを作り得る状況でもハッシュ値が同じものがどうしても出てこない... となると, 直感的にも "強" 衝突耐性であることが理解しやすい

メッセージ認証コード

メッセージ認証 (authentication) とは「メッセージが正しい送信者からのものである」と確認すること. メッセージ認証コード (message authentication code: MAC) は，正真性 (integrity) を確認し, メッセージの認証を行う技術.

メッセージ認証コードの入力:
- 任意長のメッセージ
- 送信者と受信者が共有する鍵
メッセージ認証コードの出力:
- 固定ビット値の出力

入力に "共有する鍵" が含まれるのが, 一方向ハッシュ関数との違い. ところで "鍵を共有" ということは例の "鍵配送問題" が持ち上がってくる. 鍵自体の共有には共有鍵暗号やらDiffie-Hellman 鍵交換やらを使いましょうね

問題: 「共有してる鍵を持っている相手からのメッセージ」であることを確認するだけなら, 単にその鍵で暗号化して送受信すればいいのでは? 何か問題がある?

=> 回答: 暗号化されたデータを誰か第三者が保管しておいて, それを (送信者の意図しないタイミングで) 送って来たとすると, 送り主が鍵を共有しているその人である, という前提が破綻する.
=> 反論: でもこれメッセージ認証コードを付けたところで事情は一緒では... うーん違うな
=> 解答: 解読したメッセージが「読めたら正しい」「読めなかったら鍵が違う」という判断は危険. これだとランダムな情報を送り合うことができなくなる.
- ここで, メッセージ本体とは別途送られてくる MAC 値を調べることでメッセージを正しく認証することが可能.

メッセージ認証コードで解決できない問題:

その 1.「第三者に対する証明」: "このメッセージはアリス本人から受け取ったものだよ" とボブが第三者に証明できない. MAC 値を検証するためにはふたりだけの共有鍵を第三者に教えないといけないため. 仮に教えたとしても「MAC 値は正しいけど別にこれボブが作ったんじゃね」という疑惑は否定しきれない
その 2.「否認防止」: 上述の理由により, 送信者アリスが後から "そんなメッセージ送ってない" と, しらばっくれることが可能.

これら問題を解決するにはデジタル署名を使います. 9 章.

メッセージ認証コードの利用例

IPsec, SSL/TLS, SWIFT で使われている. SWIFT とは Society for Worldwide Interbank Financial Telecommunication, 国際銀行間通信協会のことで 1973 設立の団体. メッセージ認証コードを利用. 公開鍵暗号ができるまでは共有鍵を人間が配送していた (!)

メッセージ認証コードの「実現方法」

一方向ハッシュ関数 (MD5 とか SHA-1) を使って実現. 例: HMAC
ブロック暗号 (トリプル DES や AES) を使って実現. ブロック暗号の鍵をメッセージ認証コードの共有鍵として使い, CBC モード (一つ前の暗号文ブロックと平文ブロックの XOR をとってから暗号化を行うやつ) で暗号化する. CBC の最終ブロックをメッセージ認証コードとして使う. CBC モードはメッセージ全文 + 鍵のビット列によって決まるので, メッセージ認証コードとして利用できる.

HMAC とは

"Hash Message Authentication Code". RFC2104. HMAC: Keyed-Hashing for Message Authentication (RFC 2104) - IETF

強い一方向ハッシュ関数なら何を使ってもよいので, HMAC-SHA1, HMAC-MD5, HMAC-RIPEMD などいろいろなバリエーションがある

デジタル署名

"ある人にしか作れない情報" を添えることで, 送り手が "その人" であることを疑いなきものにする.

お話にはふたつのアクションが出て来る. メッセージの署名を「作成」することと, メッセージの署名を「検証」すること. 「作成」と「検証」それぞれに専用の個々の鍵がある.

ここまで来ると公開鍵暗号と同じ考え方が使えることがわかる. すなわち公開鍵暗号における「誰でも暗号化に使っていい公開鍵」は, デジタル署名においては「誰でも検証に使っていい署名作成用の鍵」に対応する. 一方で公開鍵暗号における「メッセージの複合に使うプライベート鍵」がデジタル署名では「署名作成に使う鍵」となる. 冒頭の "ある人にしか作れない情報" の答え合わせ.

もっと単純化すると, デジタル署名は公開鍵暗号の「自分・他人」を "逆" に使っている.

公開鍵暗号: 相手が送って来たものをプライベート鍵で復号化する
デジタル署名: こっちがプライベート鍵で「署名作成」してから送る

ぱぶりっく方面を見ると

公開鍵暗号: こっちが公開鍵で暗号化して相手に送る
デジタル署名: 相手が送ってきたものを公開鍵で「検証」する

デジタル署名の方法

メッセージに直接署名する
メッセージのハッシュ値に対して署名する

10 章: 証明書

TODO: update memo

11 章: 鍵