鍵付きハッシュ関数の存在的偽造とパスワードハッシュに対する脅威の評価
鍵付きハッシュ関数 (keyed hash functions) を改竄検知、MACを生成する関数として使う場合、攻撃者の目標としては鍵を知らずしてMACを計算する (偽造する) こととなる。
改竄検知ではなく、オフライン攻撃に耐性を持たせるために秘密鍵を使って (pepperというらしい) パスワードハッシュなどをとっている場合も、鍵を知らずにハッシュ値を計算できてしまうと「秘密鍵が漏れていなければオフライン攻撃ができない」というセキュリティの前提が崩れてしまう。
本エントリでは、鍵を知らずに鍵付きハッシュ関数のハッシュ値 (MAC) を計算する攻撃法であるLength Extension Attackについてざっくりと説明し、この攻撃法はパスワードハッシュのオフライン攻撃からの保護というコンテクストでは現実的な脅威とならないことを示す。
MD5, SHA1, SHA2-familyなどのよく使われている暗号学的ハッシュ関数 (cryptographic hash functions) は、衝突耐性を持たせるために、Markle Damgard Constructionという構成法で構成されている。
Markle Damgard Constructionは「ハッシュ関数の構成要素である圧縮関数が衝突耐性をもつならばハッシュ関数全体としても衝突耐性をもつ」という性質が証明できるため衝突耐性のあるハッシュ関数を構成するのに便利である。(なお、SHA3-familyはSponge CosntructionというMarkle Damgardでない構成法によって構成される)
なお、圧縮関数自体はDavies Myer構成法という構成法によって構成されるが、大雑把には、ハッシュ関数のために構成されたブロック暗号を使っているという理解で問題ないし、この記事を読むにはそれを知る必要はない (し、ぼくも調査中で説明できない。Unbalanced Feistel Structureがハッシュ関数構成に何故使われるかとか説明できない)
Markel Damgard Constructionは構成要素となる圧縮関数という関数 h を使って、下図のように平文を複数ブロックに分割した上で反復して適用して最終的なハッシュ値を得る。Initial valuesは固定値である。
図について簡単に説明する。入力のメッセージは、SHA1の場合はまず64バイトの倍数長になるようにpaddingをとってから、64バイト毎のブロックに分割される。各ブロックは、ハッシュ関数の初期値 (上図のInitial values) あるいは一つ前の圧縮関数の出力と共に圧縮関数 h に入力されて、その出力は次の圧縮関数 h の入力として使われる。これをブロックの個数だけ反復して最後の圧縮関数 h に出力された160bitのバイト列がハッシュ値として出力される。
鍵を知らない限り計算できないハッシュ関数 (MAC) の実装として、素朴に次のような構成を考えてしまうかもしれない。すなわち、秘密鍵のバイト列をメッセージのバイト列に連結してハッシュをとるという構成を。
しかし、このように鍵付きハッシュ関数を設計するとLength Extension Attackという攻撃に脆弱になる。
Length Extension Attackでは、攻撃者は標的となる鍵付きハッシュ関数によって計算されたハッシュ値 Hash Value を少なくとも一つ知っているものとする。ここで、攻撃者は自らの用意したメッセージ Msg’ と適当なパディング Pad’ を連結し、既知のハッシュ値 Hash Value とともに圧縮関数 h に入力する (下図。) その出力 Hash Value’ は、明らかに ハッシュ値 Hash Value を生成した元のメッセージを Msg、パディングをPad として、 Msg || Pad || Msg’ に対する鍵付きハッシュ値と一致する (下図。)
こうして、上記のような素朴な鍵付きハッシュ関数では、秘密鍵を知らずに何らかのメッセージ (メッセージの内容全体は完全には制御できないが) に対するハッシュ値 (MAC) を計算することができてしまう。このように「鍵を知らずして何らかのメッセージのMACを計算する攻撃」を存在的偽造 (existential forgery) といい、具体的に上のように既知のハッシュ値にメッセージとパディングを付加してMACを偽造する攻撃をLength Extension Attackという。
で。これは冒頭で想定したような脅威、すなわちpepperによってオフライン攻撃から保護されているパスワードのハッシュを脅かすものだろうか。
結論からいえば、SHA1やSHA2-familyなど現状としてよく使われているハッシュ関数を使う限りは安全だと言える。
こういうのは動くものを見ながらの方が理解が深まるので、SHA-1をサクッとPythonで実装してみた。SHA-1のパディングやMessage Schedule, 圧縮関数をそれぞれ独立して呼び出すこともできる。これを使って検討してみよう。
def K(t): if t < 20: return 0x5a827999 elif t < 40: return 0x6ed9eba1 elif t < 60: return 0x8f1bbcdc else: return 0xca62c1d6 def f(t): def ch(x, y, z): return (x & y) ^ ((~x & 0xffffffff) & z) def parity(x, y, z): return x ^ y ^ z def maj(x, y, z): return (x & y) ^ (y & z) ^ (z & x) if t < 20: return ch elif t < 40: return parity elif t < 60: return maj else: return parity def rotl(n): def _rotl(word): return ((word << n) & 0xffffffff) | (word >> (32 - n)) return _rotl def schedule(M): w = [int.from_bytes(M[4*i:4*i + 4], 'big') for i in range(16)] rotl1 = rotl(1) for t in range(16, 80): a = w[t - 3] b = w[t - 8] c = w[t - 14] d = w[t - 16] w.append(rotl1(a ^ b ^ c ^ d)) return w # これが圧縮関数 def compression(H, M): W = schedule(M) H = [int.from_bytes(H[4*i:4*i + 4], 'big') for i in range(5)] a = H[0] b = H[1] c = H[2] d = H[3] e = H[4] rotl5 = rotl(5) rotl30 = rotl(30) for t in range(0, 80): T = (rotl5(a) + f(t)(b, c, d) + e + K(t) + W[t]) & 0xffffffff e = d d = c c = rotl30(b) b = a a = T H[0] = (a + H[0]) & 0xffffffff H[1] = (b + H[1]) & 0xffffffff H[2] = (c + H[2]) & 0xffffffff H[3] = (d + H[3]) & 0xffffffff H[4] = (e + H[4]) & 0xffffffff return b''.join(H[i].to_bytes(4, 'big') for i in range(5)) # メッセージMと、長さlを与えると適当にMにパディングを付加して返す def pad(M, l): k = (448 - l - 1) % 512 zeros = (k // 8) * b'\x00' length = l.to_bytes(8, 'big') if k % 8 == 7: return M + b'\x80' + zeros + length else: x = M[-1] | (1 << ((k % 8) + 1)) return M[:-1] + x.to_bytes(1, 'big') + zeros + length initial_values = [ 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0, ]
では、このSHA1の圧縮関数compression等を使って、実際にLength Extension Attackをやってみよう。
さて。さて、だ。本題に戻ろう。
確かに鍵付きハッシュ関数の設計に問題があると、既知のハッシュ値を使って他の何らかのメッセージのハッシュ値を計算できることが確認できたが、これは「パスワードハッシュをオフライン攻撃から保護する」という目標を損なうものだろうか。
答えとしては、否、となる。
上のkeyed_hash関数の入力 In [14] のあたりを見ていただきたいのだが、neko というパスワードに連結する文字列にNULL文字 (\x00) を複数含むのがわかるだろうか。これは偶然ではなく、パスワードのような短い文字列のハッシュをとると必ず入り込むものである。
SHA1やSHA2-familyなどのハッシュ関数は、入力の長さが512ビット (64バイト) の倍数長になるようにパディングを付加する。さらに、必ずブロック末尾に64ビット長の「メッセージ長」のフィールドが入ることになっている。64ビット長でメッセージ長を表そうとすると、パスワードのような高々数十文字程度の文字列のハッシュをとると、必ずこのフィールドにはNULL文字 (\x00) が入ることになる。
すなわち、パスワードのオフライン攻撃からの保護のためにpepperを使ったハッシュ関数によってハッシュ値をとっていた場合は、「パスワードの途中に6, 7バイトのNULL文字を含むのが当然であるようなパスワードポリシーを採用しているようなシステム」という猫が設計してもありえないシステムでない限りはLength Extension Attackによる脅威 (すなわち、攻撃者にとって既知のメッセージ・ハッシュ値の組み合わせから、他のメッセージのハッシュ値までオフラインで計算されてしまうという脅威) は存在しない。
