TOPへ戻る

2章 ハッシュ関数

  • ハッシュ関数とセキュリティ特性
  • 現在使われるハッシュ関数
  • ハッシュの仕組み

「どんなものにも、全体の中で重複しない識別情報を結びつける」ことがハッシュ関数の仕事。 任意の文字列から特定のバイト列を生成する。 入力が同じなら、同じハッシュ列を返す。これが強い。

2.1 ハッシュ関数とは何か

アプリのダウンロードとか、パッケージのインストールなどで謎の文字列が生まれる。

たとえば sha256sumとか見たことありそう。これはどのように処理・生成されるのだろうか。

【プロトコル】

  • ボタンをクリックしてファイルをダウンロードする
  • ダウンロードしたファイルを SHA-256 アルゴリズムでハッシュする
  • ハッシュした出力(=ダイジェスト/ハッシュ)を、ウェブページに表示されている文字列と比較する。
    • これが合っている=同じハッシュ値=入力(DLしたファイル)が同じ。

実際にSHA-256を opensslでやってみると確かに一致する。
これをやる目的: ダウンロードしたものが、ダウンロードしようと意図していたファイルに違いないという保証をしたい。

  • 完全性(integrity)
  • 真正性(authenticity)

ハッシュ関数には「第二現像困難性」がある。 - ハッシュ値が同値になるような「別のファイル」を見つけることは難しい。 - ハッシュ値はウェブページの所有者が管理している - ウェブページを書き換えられる人なら、誰でも簡単に差し替えられる点には注意。 - ダイジェストを提供しているページ、所有者、ページ取得に使われる仕組み を信頼する必要がある。 - 書き換えられる状態だとハッシュ関数だけでは完全性を保証出来ない。

ダウンロードされるファイルの完全性は、ダイジェストと、ダイジェストを提供する仕組み(httpsなど)

  • ハッシュ関数の入力: 何でもいい。空白ですらいい。
  • ハッシュ関数の出力: 決定論的に「同じ長さ」になる(SHA-256は256ビット)
    • 16進数の数字列64個で表現される。
    • 一文字かわるだけで全部違う。

2.2 ハッシュ関数のセキュリティ特性

現像計算困難性

  • ある出力が与えられるとき、ハッシュ関数を逆に計算して入力を求めることはできない

    • ミキサーみたいなもん。一回キャベツぶっこんだら終わり。

      入力が小さい場合、たとえば入力が3文字しかない場合は総当たりで試せちゃう。 また、入力の差が小さい場合。「月曜日の午前3時に帰宅する」について、たとえば 「月曜の15時に帰宅する」とか「月曜午後3時に帰宅する」など、色々試せるとすると、 正確な入力が得られるかもしれない。

      正直現像計算困難性は完全に達成することは難しい

第二現像計算困難性

  • ある入力とダイジェストがあるとき、ハッシュして同じダイジェストになるような 「別の入力」を求めることが出来ない。
  • 現像計算困難性を補う特性。
  • 最初の入力は何もコントロールしていない。
    • 攻撃者はファイル管理者の持つダイジェストと同じハッシュ値を持つファイルに 悪意を仕込んで差し替えるような動きが想定できる

衝突困難性（衝突計算困難性/衝突耐性）

  • ハッシュして同じ値になるような2種類の入力は存在しない
  • 衝突困難性では、攻撃者が入力をコントロールする。

    • つまり、同じハッシュ値を持つ2つのファイルを用意して、
      一方に善意、もう一方で悪意を仕込んで、悪意をDLさせる動きができる

      考えてみよう
      衝突困難性と第二現像計算困難性の違いは何だろう？
      → 攻撃者が2つの入力を選ぶことができる点。

ランダムオラクル

ハッシュ関数は一般的に、予測不能でランダムなダイジェストを出力するように設計される。 ハッシュ関数のセキュリティ特性上、プロトコルが安全であると永続的に保証できないので、 ランダムで予測不能に設計する必要がある。 「ランダムオラクル」は架空の構造を想定したモデル。プロトコルはこれを使って安全性を保証する。 ランダムオラクルを使った安全性保証のプロトコルでは、任意の入力を送信すると、ランダムオラクルから
全くランダムな出力が返される。
ただし、ランダムオラクルが、現実的にハッシュ関数に置き換えることができるかは不確実。
でも実際ランダムオラクルによるプロトコル保証は行われているし、ハッシュ関数は理想的なものっぽい。

2.3 ハッシュ関数のセキュリティに関する考察

ハッシュ関数のセキュリティ特性は以下の3つ - 現像計算困難性 - 第二現像計算困難性 - 衝突困難性

ハッシュ関数のセキュリティ特性の「意味」は、ハッシュ関数をどう使うかによって決まる。
ただし、ハッシュ関数の限界も存在する。

上記3つのセキュリティ特性は、ハッシュ関数が合理的に使われていることが前提にある。 特に第二現像計算困難性は、あくまで「とても難しい」「現実的に達成できない」という意味で、
理論上はめちゃくちゃ頑張れば出来てしまう、ということ。

例: 「はい」と「いいえ」のハッシュ化

Aliceが「はい」と「いいえ」のどちらかをハッシュ化して、そのダイジェスト(ハッシュ値)を公開する。
もしBobが「ハッシュ化されているのは『はい』か『いいえ』である」ことを知っていたら、
こちらでハッシュ化して、そのダイジェストを比較すれば、Aliceが何をハッシュ化したのかがわかる。
この場合、AliceとBobとの間に「秘密」はどこにもなくなる。

現像計算困難性を満たさないかもしれないが、ハッシュ関数を利用する際の「ランダム度」が足りなかったという反論も可能。たまたま別の言葉で同じハッシュ値が出てきたとしたら、第二現像計算困難性を破ることになる。

ダイジェストのサイズ

これはハッシュ関数に限った話ではなく、暗号アルゴリズム一般に言えること。
ハッシュ関数は、現代では最低256ビットの値を返すように決まっている。
具体的には以下の条件が「最低条件」となっている。

  • 対衝突困難性には256ビット
  • 現像計算困難性、第二現像計算困難性には128ビット

この大きさはよほどの計算能力を持つコンピュータが出てこなければ覆らない。

ハッシュ関数から離れると、現代暗号は最低128ビットのセキュリティ(\(2^{128}\)の計算を実施する)を目指す
ハッシュ関数が現像計算困難性、第二現像計算困難性、衝突困難性の3つを満たすには、それぞれに対して\(2^{128}\)のセキュリティを求める。
誕生日限界を考えると、\(2^{128}\)のセキュリティを達成するには、\(2^{256}\)のランダムな出力ができるように
設計されなければならない。

誕生日限界

1つの部屋に何人いたら、そのうち2人が同じ誕生日だろうか？というお話。
現実上レアな確率かなと思いがちだが、実際は23人いると、50%の確率で
誕生日がダブる。

\(2^N\)通りの組合せから文字列をランダムに生成する場合、特定の文字列と一致するような文字列を生成するには、
\(2^{N/2}\)の確率で衝突を見つけることができる

例: 2ビットのハッシュ値を返すハッシュ関数

2ビットのハッシュ値を返すハッシュ関数は、その返り値が以下の4つ。

  • 00
  • 01
  • 10
  • 11

適当な文字列でも、多分上記のどれかに変換されるので、現像ができる。

2.4 現実世界でのハッシュ関数

現実世界では、ハッシュ関数単体で使われることはない。
ハッシュ関数と他の機能を組合せて暗号プリミティブ/暗号プロトコルが構築している。

2.4.1 コミットメント

  • 「X社の株が値上がりした！6,000円になる！」ということが分かった。
    • でも法律的にまずいので友人には教えられない。
    • でも「事前に知っていた」ということは自慢したい。
  • 「X社の株は1ヶ月後に6,000円になる」という文を「宣言(Commitment)」しておけば良い。
    • この文をハッシュ化して友人に預け、1ヶ月後にその文を公開する。
    • 同じ文章がハッシュされれているとすれば、友人も信じてくれる。

上記の使われ方を「コミットメント方式」と呼ぶ。
コミットメント方式で達成したい目的

  1. 秘匿性: コミットメントは元の文(平文)を隠さなければならない
  2. 拘束性: コミットメントは1つの値だけを隠すものでなければならない。
    • たとえば文\(x\)をコミットしたら、別の値\(y\)が出てきてはいけない

演習

  • コミットメント方式にハッシュ関数を使ったとき、秘匿性と拘束性は保証されるか？
    • 秘匿性は保証されるかもしれない。
    • 拘束性は微妙。現像計算困難性と衝突困難性を完全に達成することが難しいので。

2.4.2 サブリソース完全性

  • Webページは、外部のJavascriptをインポートしていることが多い
    • コンテンツデリバリーネットワーク(CDN)を使ってJavascriptライブラリ・ Webフレームワーク関連のファイルをページに読み込む。
  • CDNが不正に利用されて、悪意のあるJavascriptファイルを配信すると、大変。
  • ウェブページはサブリソース完全性という性質をもっている
    • 以下のように、インポートタグを使ってダイジェストを指定する。
    <script src="https://code.jquery.com/jquery-2.1.4.min.js" 
integrity="sha256-8WqyJLuWKRBVhxXIL1jBDD7SDxU936ozCnxQbWwJVw="></script>
  • Javascriptファイルを取得すると、Sha-256を利用してファイルをハッシュして、ページにハードコード(別の所で指定・処理するべき内容をソースコードに直接書き込むこと)されているダイジェストに対応するかを検証する。

2.4.3 BitTorrent

  • 世界中のユーザ(ピア)が相互に直接ファイルを共有できる(ピアツーピア)プロトコル。
  • 共有したいファイルを「チャンク」に分割し、チャンクごとにハッシュ化する。
    • このハッシュがダウンロードするファイルを表すファイルを表す「信頼できるソース」として共有される
  • ピアが他のピアから様々なファイルのチャンクを取得する仕組みがある
    • ダウンロードした各チャンクをハッシュして、その出力を、すでにわかっているダイジェストたちと比較することで、ファイル全体の完全性を検証する
      • ここで、ファイル全体を再構成する前に行う。つまり分割した状態での検証が行われている。
  • 以下はUbuntu 19.04のマグネットリンク。
    • マグネットリンクは、ファイル共有のためのリンク。
    • ファイルに対するメタデータと、チャンクのダイジェストすべてをハッシュして得られたダイジェスト
magnet:?xt=urn:btih:b7b0fbab74a85d4ac170662c645982a862826455

2.4.4 Tor(トーア)

  • ブラウザ。
    • 個人が匿名でインターネットを閲覧できるようにすることを目的にしている。
    • 応用で、物理的な所在地を追跡しにくい隠れたウェブページを作成する機能もある。
  • Torで作成したページは、ウェブページの公開鍵を使用するプロトコルで保護される→9章
  • 「麻薬のeBay」と呼ばれたSilk Roadというサイト
    • Torブラウザでアクセスできるonionアドレス(base32)が、Silk Roadの公開鍵のハッシュだった。
    • onionアドレスを知っていれば、アクセスしている隠れウェブページの公開鍵を認証して、アクセス先が正しいページである、つまり「なりすましではない」ことを確認できるというもの

演習

onionアドレスは256ビットではないので、2.3節で考えた内容をそのまま使うにはセキュリティに対応していない。
ではどう保つのか？

  • えー、どう保つんだ。

2.5 標準化されたハッシュ関数

SHA-256は普及しているハッシュ関数のうちの1つ。
暗号学的ハッシュ関数(暗号としての用途に耐えうる強度を持つハッシュ関数)としてみなされていないが、
(なぜか)現実世界で使われている関数について見てみる。

  1. CRC32
    • 誤り検出符号の関数であり、暗号学的ハッシュ関数ではない
      • IT用語辞典によれば、「データを記録・伝送する際に発生する誤りを受け手の側で検出できるように付加される符号」らしい。
      • データの通信では、ノイズなどの様々な理由でデータの欠落や改変が起こりうる。
      • これを防止することは不可能だが、検出はできるので、検出して対処するらしい。
    • 現像計算困難性、第二現像計算困難性、衝突困難性のいずれも満たしていない。
    • チェックサムとも呼ばれる
  2. MD5/SHA-1
    • すでに脆弱性(衝突困難性)が生まれ、攻撃可能であることが示されている。
    • コンピュータの処理性能が上がったことも理由になるが、基本的には設計ミスでもある。
    • MD5はRのパッケージインストールでのチェックサムでも行われている。
      • たとえばここでの議論はまさに「チェックサムとインストールされたパッケージの中身の改ざんの可能性の違い」に関する議論

標準の廃止は難しい

MD5やSHA1は、現像計算困難性に依存したシステムでは未だに使われる。
なぜならば、現像計算困難性と第二現像困難性は、MD5/SHA-1ではまだ破られていないため。
つまり、ハッシュ値からもとの値を計算したり。、同じダイジェストを返すような別の入力を
見つけだしたりすることは難しい。
運用上、レガシーなシステムだったり、後方互換性が必要だったりで、これらを廃止することは難しい。

排他的論理和

2つのビットがあるとき、その排他的論理和を \(bit_A \oplus bit_B\)で表す。
このとき、演算結果は以下のようになる。

\(bit_A\) \(bit_B\) \(\oplus\)
0 0 0
0 1 1
1 0 1
1 1 0

暗号の計算でめちゃくちゃ使われるので、覚えてくれとのこと。 これを勉強するためのゲームがあるよ

2.5.1 SHA-2ハッシュ関数

マークル/ダンガード構成法

  • とりあえず日本語ですぐわかるような記事はなかったので英語版Wikipediaをもってきた

SHA-2は最も広く使われる暗号学的ハッシュ関数。NSAで開発されて、NISTには2001年に標準化される。
4種類のバージョン(224bits, 256bits, 384bits, 512bits)があり、SHA-224~SHA-512とも記述される。
SHA-512/224とか、SHA-512/256など、SHA-512の値を切り詰めて224ビット、256ビットの値を返すようなものもある。 以下は、実際にhello worldという文字列をSHA-2系でハッシュ化した結果。

┌──(kien)-[~]
└─$ echo -n "hello world" | openssl dgst -sha224
SHA2-224(stdin)= 2f05477fc24bb4faefd86517156dafdecec45b8ad3cf2522a563582b

┌──(kien)-[~]
└─$ echo -n "hello world" | openssl dgst -sha256
SHA2-256(stdin)= b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

┌──(kien)-[~]
└─$ echo -n "hello world" | openssl dgst -sha384
SHA2-384(stdin)= fdbd8e75a67f29f701a4e040385e2e23986303ea10239211af907fcbb83578b3e417cb71ce646efd0819dd8c088de1bd

┌──(kien)-[~]
└─$ echo -n "hello world" | openssl dgst -sha512
SHA2-512(stdin)= 309ecc489c12d6eb4cc40f50c902f2b4d0ed77ee511a7c7a9bcd3ca86d4cd86f989dd35bc5ff499670da34255b45b0cfd830e81f605dcf7dc5542e93ae9cd76f

現在はSHA-256が使われる。これによって128ビットのセキュリティが確保できる。

SHA-2の仕組み

  1. 圧縮関数(Compression function)
    • 同じサイズの2つの入力を取り、一方の入力のサイズの値を出力する。
      • 一定のデータを取って小さいデータを返す(図2.7)。
    • SHA-2で用いられているのは、ブロック暗号を使った方法
      • デイビーズ・マイヤー法(図2.8)が用いられる。
      • 詳細は4章(認証付き暗号)。今は「そういう関数がある」として飲み込む。
    • 図2.8の解釈入力①(鍵)と入力②(標準化された固定の値・nothing-up-my-sleeve)を用いて暗号化。
      • 入力②との排他的論理和を取ってダイジェストにする
      • Nothing up my sleeve(私の袖には何もない=袖の下はない=嘘はついていない・切り札はない)
        • SHA-256は最初の方の素数の平方根を使って入力②を計算する。
        • この値はハッシュ関数を弱体化する(バックドアを作る)ために選択されたわけではないという概念

デイビーズ/マイヤー法を用いた圧縮関数の図を関数に置き換えておく

def Compression(inputA, inputB):
  '''
  inputA: 鍵
  inputB: 上記で言うNothing up my sleeve値
  '''
  # 暗号化する(デイビーズ/マイヤー法)
  code = encrypt(inputA, inputB) # ここの暗号化はとりあえずブラックボックスを許す。
  hash = code ^ inputB

  return hash
  1. マークル/ダンガード構成法
    • 圧縮関数を反復的に呼び出してメッセージをハッシュ化する
      • ハッシュしたい入力をパディング
        • パディング: 一定のブロック長の倍数にあたる長さになるように、
          その分のバイトを入力に追加する操作。
        • パディング後の入力を同じブロックサイズのチャンクに分割すると、
          圧縮関数の最初の引数に用いる事ができる。
    • ブロックになった入力メッセージに圧縮関数を反復的に適用する
      • 1つ前の圧縮関数の出力が、次の圧縮関数の入力の1つになる。
      • 最後の出力がハッシュ値のダイジェスト。

コードのイメージを書いておく

def MerkleDamgard(inputA, inputB):
  '''
  inputA: 鍵のリスト
  inputB: 上記で言うNothing up my sleeve値
  '''
  # 暗号化する
  for i in inputA: # ここは謎。
    if i == 0:
      digest = Compression(inputA[i], inputB)
    else:
      digest = Compression(inputA[i], digest)

  return digest

SHA-2の適用範囲

ハッシュ関数として用いること自体に問題はないが、秘密のハッシュ化そのものには向いていない。 SHA-2は、伸長攻撃に脆弱(3章までお楽しみ)

マークル/ダンガード構成法の保証

衝突困難性が保証される条件は、圧縮関数そのものが衝突困難性を備えていることがある。
任意の長さの入力に対するハッシュ関数のセキュリティは、固定サイズの圧縮関数の長さに依存する。
この依存が、設計と解析の容易さを生み出し、マークル/ダンガード構成法の(どういう意味での？)「有利」さをもたらしている

2.5.2 SHA-3ハッシュ関数

スポンジ構造

SHA-2が伸長攻撃に対して脆弱であるということがわかっているので、NISTは2007年にSHA-3の制定のためのコンペを開催する。Keccakが2012年に優勝し、FIPS PUB 202として標準化された。

参考: NISTのPablish

SHA-3の特徴

  • 現像計算困難性、第2現像計算困難性、衝突困難性のすべてを満たす。
  • SHA-2と同じ程度のセキュリティ(128ビット以上)のセキュリティを保証する
  • 伸長攻撃に対しても頑健である

現時点で推奨されるハッシュ関数として用いられている。

考え方のベース: 転置・並べ替えとスポンジ構造

転置(Permutation: 並び替え)

図2.11をよく見て。以下は77ページの引用

矢印の始点でも終点でも、要素はそれぞれ1つずつに限定されることとする。

これは一対一対応・全単射の考えが近いかなと思う。
たとえば○→△だったり、△→□だったりする変換が行われる。
一対一対応であれば良いので、★→★のように、変換後の値が同じでも構わない。

keccak-fという転置設計がベースとなってスポンジ構造をもったSHA-3アルゴリズムをもっている。

8ビットでのスポンジ構造

Pythonの想像をすると、0か1をとる長さ8のリストを考えれば良さそう。
たとえば以下は、図2.12をコード化したもの。

x = [0, 0, 0, 0, 0, 0, 0, 0] 
y =f(x) #転置関数。

y
> [0, 1, 0, 1, 1, 0, 0, 1]

# これが2^8 = 256通りの変換が得られる

スポンジ構造で転置を用いるときには、入力と出力に区切りを用いる。 レート(rate)とキャパシティ(capacity)と呼ばれる。
キャパシティは秘密のように扱われるので、大きいほど良さそう。

以下は図2.13をコードに落とし込んだもの。

rate = [0, 0, 0, 0, 0]
capacity = [0, 0, 0]
x = [rate, capacity]
> [[0, 0, 0, 0, 0], [0, 0, 0]] # 上の例を、明示的に示している。

y = [0, 0]
for i, v in enumerate(x):
  y[i] = f(v)

y
> [[0, 1, 0, 1, 1], [0, 0, 1]]

この関数がハッシュ関数として正しく機能するためには、ハッシュのための演算を組み込む必要がある。 転置の入力のrate部分のXORを求める。rateの初期状態は0のみのリストになり、
キャパシティ部分はXORを求めなくても良い。

図2.14を考える。

val = [0, 0, 1, 0, 1] # 「吸収」したいビット列
x = [rate, capacity]  # [0, 0, 0, 0, 0]のビット列
z = []

for j, v in enumerate(x[0]):
  t = v ^ val[j] # すべて0のビット列とXORを取れば入力がそのまま返る
  z.append(t)

z
> [0, 0, 1, 0, 1]

x_hash = [z, capacity]
y = f(x_hash) # 転置の実行。これによってビットの状態はランダム化する。

y 
>[[1, 1, 1, 0, 0], [0, 1, 0]]

転置によって得られた結果はランダムになっているはずらしい。なぜそうなのかはわからない。
ただ、転置は定義を考えると一対一対応の写像であるから、入力が何かを考えることはできる。
吸収する入力が大きいときは次の手順を踏む。

  1. 必要に応じて入力をパディングして、入力をレートのサイズに合わせたブロックに分割する
  2. 各ブロックと転置入力とのXORを求め、各ブロックのXOR後に中間値を使って反復的に
    転置を実行する。
'''
レートのサイズ(ここでは5)よりも大きな入力を吸収する場合、
スポンジ構造は入力のブロックとレートとのXORを反復して求めていき、
その結果を転置する。
'''
inputs = [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] # 長いビット列
inputs_sep = [[0, 0, 1, 0, 1], [0, 1, 0, 0, 1], [0, 1, 1, 0, 0]] # 5ビットずつに分割(rateと同じ長さ)

rate = [0, 0, 0, 0, 0]
capacity = [0, 0, 0]
y = []
for idx, x in enumerate(inputs_sep):
  if idx == 0:
    z = rate

  tmp_y = x

  for i, v in enumerate(tmp_y):
    t = v ^ z[i] # XORを実行する
  
  tmp_x = [t, capacity]
  z = f(tmp_x) # 転置を実行する。次の入力になる。

z 
> [[1, 1, 0, 1, 0], [1, 1, 0]]

ダイジェストを生成するにはスポンジの最終的な状態のレートを使えば良い。
ダイジェストが長くなる場合は転置を続けながら状態のレート部分を読み取る。

2.16: スポンジ構造でダイジェストを取得するには 反復的に状態を転置していきながら、必要なだけのレートを取得する。

入力を取り込むことを「吸収」、ダイジェストを生成する過程を「搾出」という。
※ 搾り出す、ということだね。

スポンジに指定される転置関数は1600ビット。

SHA-3はランダムオラクル

ランダムオラクルは入力に関して完全にランダムな出力を返して、
同じ入力であれば同じ値を返す仮想的・理論的なデータ構造。
スポンジ構造は、転置関数が十分にランダムである限り、
ランダムオラクルに「近い」動作をすることがわかっている。
セキュリティ特性の証明は「信頼できるまで突破を試みる」という
強引な方法が取られる。

2.5.3 SHAKEとcSHAKE: 2つの可変長出力関数(XOF)

SHA-2とSHA-3は、任意の長さの入力から、ランダムに見える固定長の出力を返す。
一方で、ハッシュ関数のダイジェストが固定長であるという性質が望ましくない場合もあるらしい。 eXtendable Output Function(XOF)という汎用性の高いプリミティブがSHA-3には採用されている。

  • SHAKEはFIPS202で標準化されていて、任意の長さの出力を返すハッシュ関数と考えて差し支えない。
  • SHA-3と同じ構成法だがより高速で、搾出フェイズでいくらでも転置関数を使える。
  • 長さの違う出力の生成では、乱数の生成や鍵の取得などに応用でき、どうやら便利らしい。

cSHAKEはカスタマイズ文字列も取れるSHAKE。2つのダイジェストが同じにはならない(カスタマイズ文字列によって演算が変わるため)。
これは、証明を成立させるために異なるハッシュ関数を使用する必要があるプロトコルで重要。
- ドメイン分離と呼ぶ。

異なる用途で同じ暗号プリミティブを使う場合、同じ鍵や同じドメイン分離を用いてはならないというのが、
暗号に関する大原則である。ドメイン分離の例はまた出てくる。

NISTの指定するパラメータ

NISTはアルゴリズムのパラメータをビットで指定する。
SHA-2もSHA-3も基本は、256ビット長を指定する。
この制約を悪用した攻撃はビット攻撃という

鍵、パラメータ、出力という暗号文字列の長さはセキュリティ強度に大きく関係する。
SHAKEでもcSHAKEでも短い出力は指定しない方がいい。
256ビットを指定していれば安全(衝突攻撃に128ビットのセキュリティが確保できる)だが、
色々の制約上、短い値を使わなければならないときは注意。
短い値を使うプロトコルで衝突困難性に問題がないなら、
現像計算困難性についてはSHAKE/cSHAKEから128ビットの出力でも良い(半分でもおk)

2.5.4 TupleHashによるハッシュで曖昧さを回避する

TupleHashはcSHAKEをベースにしている。タプルをハッシュできるのでTupleHash。

どんなときに便利なのか？

  • 著者の暗号通貨の精査の例
    • 会計処理・決済など一般に求められる機能は備えている。
    • ユーザ間のトランザクションには、誰がいくら、誰に送ったかがわかるメタデータがある。
      • トランザクションネットワーク手数料も発生する。
  • アリスはネットワークにトランザクションを送信する
    • 受け付けてもらうには送信元がアリスである証明も一緒に送る必要があるので、
      トランザクションをハッシュして署名する(1章の例を見よう)
    • 誰でもこのトランザクションをハッシュできるし、ハッシュの署名の検証をすることができる。
    • 中間者攻撃を試みても、ハッシュが変わってしまうので、改ざんされたトランザクションダイジェストは
      署名によって保証されず、改ざんが出来ない。
  • 筋が良さそうだが、「誰が」「誰に」「いくら」「手数料」を1つの文字列にしてハッシュしていた
    • AliceBob10015という値をハッシュしていたとする。
      • 「アリスがボブに100円、手数料15円で送金した」的なトランザクション。
      • 「アリスがボブに1001円、手数料5円で送金した」とも読み取れ、こうしたとしてもハッシュ値は同じ。
    • 中間者がボブに金を受け取らせようとする場合、このようにすることも可能。やばい
  • TupleHashはこれを("Alice", "Bob", "100", "15")というタプルの状態を維持したままハッシュ化できる。
    • ハッシュする前に入力をシリアライズ(順に並べる)する。
    • シリアライズには逆演算(デシリアライズ)が存在する。
    • フィールドの区切りに曖昧さをなくすことができる。

2.6 パスワードのハッシュ

  • ZoomとかのURLで見る、pwd=kofwokwkofみたいな奴。
    • パスワードが平文で保存されている場合、漏洩すると大変
      • ユーザは基本パスワードを使いまわしていると思え。
  • パスワードをハッシュしてダイジェストだけを保存することが一つの解決策
    1. ユーザのパスワードを受け取る
    2. 受け取ったパスワードをハッシュして、ハッシュ値だけを残してパスワード平文は削除
    3. ダイジェストを以前に保存したダイジェストと比較して、一致すればログインできる
  • Webサイトのセキュリティは工場した
    • 多層防御(defense in depth)とかいう。
      • 不完全な防御層を重ねてすべてが破られないことを期待する
  • 多層防御にも問題はある
    1. ハッシュしたパスワードが攻撃者の手に落ちると総当たり攻撃をやられるかもしれない。
    • ハッシュアルゴリズムは「公開」されているので、平文をハッシュ→一致を確認などをされる
      • ハッシュされたパスワードを1回あたり1つ以上を試せないようにしたほうが良い
    • Saltを使って解決する。
      • ユーザに酔って異なる公開のランダム値。cSHAKEでユーザ別カスタマイズ文字列を使うことに似ている。
      • 各ユーザに異なるハッシュ関数が作成される。
      • レインボーテーブルの事前計算によって、パスワードハッシュの全部を試すことは難しい
    1. ハッシュ関数は高速を求められる。高速で計算できるということは、それだけ高速に様々なパスワードを実行できる
    • 総当たり攻撃に対してハッシュ関数の計算速度が仇になる。
    • 総当たり攻撃の実行そのものではなく、総当たり攻撃の試行を遅くするような取り組みがあると、対策はしやすいかもしれない。
    • 低速になるように設計されたパスワードハッシュを使うこともできる。
      • Argon2。RFCでの標準化が進められている。
      • コンペティションはここ。
      • その他、PBKDF2/bcrypt/scryptなどのアルゴリズムもあるが、安全性の低いパラメータを指定する事ができるので、実際にプリミティブとして構成するのは難しい
      • 現状、攻撃者からの最適化攻撃を防げるのはArgon2とscryptのみ。
        • メモリハード性を持つため。
        • メモリハード性: アルゴリズムがメモリアクセスの最適化以外で改善が見込まれないこと。
          • CPU周辺のキャッシュに上限があるので、専用のハードを用いてもこの改善は難しい(らしい)
        • 計算速度の遅さで殴る感じ。