前記

こんにちは。42 Tokyoというエンジニア養成機関の 2023 年度アドベントカレンダー 9日目も担当します、在校生のyokawadaと申します。

ft_sslという課題でハッシュ関数と暗号アルゴリズムの再実装を行いました。

この記事では、課題を進める中で調べた・体感したことのうち、ハッシュ関数に関する事項を簡単にまとめていきます。

ハッシュ関数

様々な引数に対して、決まった値を返す関数。
・・・これだけだと大体の関数がそうだろう、ということになるが、
一般には次のような条件が科されることが多い:

定義域に対して値域が狭いこと
- たとえば、文字列を取って64bit整数を返す、など。
決定論的であること
- 同じ引数に対しては同じ結果を返す。
衝突可能性が低いこと
- 異なる引数に対しては、同じ結果をなるべく返さないようにする。
容易に計算できること
- 言い換えると高速に計算できること。

「暗号学的」ハッシュ関数

通常のハッシュ関数に加えて、さらにいくつかの要件が加わる。
どのような要件なのかは用途等にもよるが、最低限、以下の3つの耐性は備えているべきとされる:

強衝突耐性
弱衝突耐性
原像攻撃耐性

雑に言ってしまえば、「計算結果から元の値を求めることが事実上不可能である(一方向性)」という感じ。

強衝突耐性(あるいは単に衝突耐性)

何も与えられていない状態で、
$\mathrm{hash}(m_1) = \mathrm{hash}(m_2)$となる入力のペア$m_1, m_2$が容易に見つからないこと。

「容易に」とは？

$2^n$通りのくじを引く時, 重複が発生するまでにくじを引く回数の期待値は $2^{n/2}$ で近似される。
ハッシュ関数に当てはめると、ハッシュ値の長さを$n$ビットとして、$2^{n/2}$通りの入力を試せば衝突が見つかることが期待できる。
ということは、もし$2^{n/2}$よりも明らかに小さなオーダーで衝突を見つけられる方法があるなら、衝突耐性が破れたことになる。

強衝突耐性がないと何が可能か？

→ ただちに具体的な攻撃ができるわけではない。
が、将来的により危険な抜け穴が見つかる可能性が示唆される。

弱衝突耐性(第2種原像攻撃耐性)

ハッシュ関数の入力$m_1$が与えられる時、
$\mathrm{hash}(m1) = \mathrm{hash}(m2)$となる別の入力$m_2$が容易に見つけられないこと。

※ 強衝突耐性とは異なり、入力の一方$m_1$は指定されることに注意。

第2種原像攻撃耐性がないと何が可能か？

→ あるファイルと同じハッシュ値を生成するが、内容は全く異なるファイルが生成できる。つまりハッシュ値による改竄チェックが成立しなくなる。

(第1種)原像攻撃耐性

ハッシュ関数の結果$r$が与えられる時、
$\mathrm{hash}(m) = r$ となる入力$m$が容易に見つけられないこと。

第1種原像攻撃耐性がないと何が可能か？

→ パスワードハッシュから「元のパスワード」もしくは「元のパスワードの代わりに使えるパスワード」が得られる。

どう考えてもまずい。

ハッシュアルゴリズムの概要

(この資料を読めばいいんじゃないかという気がする・・・)

ハッシュ関数は多数存在するが、特に有名なのはMD５とSHAシリーズなのではないかと思う。
SHAシリーズはSHA-1(SHA-0), SHA-2, SHA-3に大別されるが、SHA-2まではMD5の延長線上にある(筆者の見解です)一方、SHA-3はSHA-2以前とは明確に異なっている。
この辺りの比較はWikipediaに見やすい表がある。

MD5 〜 SHA-2とSHA-3の違いについて

雑に言うと、MD5 〜 SHA-2 はMerkle-Damgård構造をベースにしているが、SHA-3は全く別の構造(Sponge構造)を持つ。

Merkle-Damgård構造

入力データをある一定サイズのブロックの列に分割し、先頭のブロックから順にある関数$f$を繰り返し適用していく、という構造のこと。

前処理として、サイズがブロックサイズの倍数になるよう入力データを伸ばすパディングが行われるのが普通。
(ちなみにMD5とSHA-1, SHA-2のパディング処理は、エンディアンが異なる以外は全く同じ処理。)

Sponge構造

実装できたら書きます。いつになるやら。

応用

HMAC

HMACとは"Hash-based MAC"の略称。そしてMACは"Message Authentication Code"の略称。
"Authentication"は「認証」であり、ここでは「本物であることの証明」のような意味合いとなる。
あるデータ(メッセージ)が本物であること、つまり改竄されていないことを短いデータ(コード)で証明する仕組みがMAC。
認証するための方法はいろいろあるが、そのうちハッシュ関数を用いるものがHMACということになる。

基本的なアイディア

まず秘密鍵$K$を用意する。
秘密鍵は、HMACを生成する人間と、HMACを検証したい(認証を行いたい)人間だけが知っている必要がある。

暗号学的ハッシュ関数$H()$がある時、メッセージ$m$に対して$code = H(K || m)$でハッシュ値を計算し、メッセージとハッシュ値を組$(m, code)$にして取り扱う。

$code$と$m$の間には等式$code = H(K || m)$が成り立つはずだが、$code$と$m$のうち片方だけを変更するとほぼ確実に等式が成り立たなくなる。
$code$の変更に合わせて$m$を変更するには原像攻撃ができる必要があるし、$m$の変更に合わせて$code$を変更するには秘密鍵$K$を知っている必要がある。

よって、$(m, code)$を受け取った側は、等式$code = H(K || m)$を(秘密鍵$K$は知っているものとして)手元で確認することで、
「メッセージの$m$が秘密鍵$K$を知っている存在であること」を確かめることができる。

アルゴリズム

実際のHMACでは、$H(K || m)$をそのままMACとして用いるわけではない。
計算の流れは下図のようになる:

青いボックスはパラメータ。
HMACは内部で使用するハッシュ関数自体は特に指定しないので、$H$自体もパラメータとみなせる。
また、アウターパディング・インナーパディングは、HMACの仕様で決められた定数である。
XORはビット単位排他的論理和, Concatはビット列の連結。
ブロック長Bは、ハッシュ関数$H$内部のブロックの大きさだが、ブロックの概念を持たないハッシュ関数の場合どうなるかはよくわからない(調べよう・・・)。
$H$の出力のサイズではないことに注意。

HMAC1回の計算で、ハッシュ関数を2回または3回使用する。

マークル木

「マークル」とはMerkle-Damgård構造のMerkleさんのことだが、マークル木とMerkle-Damgård構造には直接の関係はない。

$n = 2^m$個のデータがある時、$n$個の葉ノードを持つ完全二分木を作る。
葉ノードはハッシュ関数$H$によるデータのハッシュ値を持つ。
また葉でないノードは「左右の子ノードが持つハッシュ値を結合したものの$H$によるハッシュ値」を持つ。

1つのデータが変更された場合、$n$個のノードのうち$O(\mathrm{log}_2 n) = O(m)$個のノード(オレンジ色)についてのみ再計算することで、木全体のハッシュ値を更新できる。
またその際に参照すべきノード(水色)も$O(m)$個で済む。

もし全データの結合に対して直接ハッシュを計算している場合、1つのデータが変更されるとハッシュ値の再計算には$O(n) = O(2^m)$の時間がかかる。
一方、マークル木ならば$O(m)$で全体のハッシュ値が更新できるので、マークル木はデータの部分更新に強いと言える。

マークル木は、そこからさらにgitやブロックチェーンなどに派生する重要技術なのだが、そこまでカバーしている時間はなかった・・・

後記

明日は @nemukyoku さんが Haskell の記事を書くそうです。楽しみですね。

余談

原像攻撃の「原像」って何やねん

数学的には「逆像」の方がメジャーかも？

ある関数(写像)$f$の定義域が$S$, 値域が$T$であるとする。
$T$上の集合$B$について, 「$f$で$B$上に移る$S$上の要素からなる集合」のことを、$B$の$f$による逆像あるいは原像(Preimage)あるいは引き戻しと呼ぶ。
原像は、$f$が全単射でなくても、つまり逆関数(逆写像)を持っていなくても定義できる。

$f$がハッシュ関数であるとすると、$S$はハッシュ関数の引数, $T$がハッシュ値となる。
原像攻撃は「あるハッシュ値から、それを与えるメッセージの集合を求める」みたいなイメージ。

伸長攻撃(Length-Extension Attack)

主にMerkle-Damgård構造を持つハッシュ関数に対して、(非常に限定的ながら)ハッシュ値が予測できるようになる攻撃。
別記事にした。

UUID

UUIDは、ハッシュ値と見た目が似ていることが多いので混同しがちだが、ハッシュ値とは全く異なるものである。

特に最もポピュラーなUUIDv4は乱数である(全体がランダムなわけではないが・・・)。
また一部のバージョンは、生成アルゴリズムの一部にハッシュを用いている。