ハッシュ長拡張攻撃に対して脆弱なアルゴリズム

ハッシュ長拡張攻撃に対して脆弱なアルゴリズム

ハッシュは、一般的に「ハッシュ」と翻訳され、「ハッシュ」と直接書き起こされることもあります。ハッシュは、ハッシュ アルゴリズムを使用して、任意の長さの入力 (プレマッピング、プレイメージとも呼ばれます) を固定長の出力に変換します。出力はハッシュ値です。この変換は圧縮マッピングです。つまり、ハッシュ値のスペースは通常、入力のスペースよりもはるかに小さく、異なる入力が同じ出力にハッシュされる可能性があるため、ハッシュ値から入力値を一意に判断することは不可能です。簡単に言えば、任意の長さのメッセージを固定長のメッセージ ダイジェストに圧縮する機能です。

ハッシュ長拡張攻撃は単純に次のようになります。

1. 秘密のハッシュを知る

2. 暗号文の長さを知る（SECRET LENGTH）

暗号文を知らなくても、暗号文＋パディング＋追加メッセージ（SECRET＋PADDING＋EXTRA）のハッシュを計算することができます。つまり、暗号文の長さと暗号文のハッシュさえわかれば、暗号文と別のメッセージのハッシュを予測することができます。

0x01 ハッシュアルゴリズムのプロセスを理解する

ハッシュ長拡張攻撃に対して脆弱なハッシュ アルゴリズム: SHA ファミリと MD ファミリ。両方のハッシュ アルゴリズム ファミリには共通点が 1 つあります。それは、Merkle-Damgård 構造に基づいていることです。

上の図からわかるように、Merkle-Damgård アルゴリズムのプロセスは次のとおりです。

1. メッセージをn個のメッセージブロックに分割する

2. 最後のメッセージブロックに長さを入力します

3. 各メッセージブロックは入力ベクトルに対して演算を実行し、この演算の結果を次のメッセージブロックの入力ベクトルとして使用します。

0x02 MD5アルゴリズムのプロセスを理解する

Merkle-Damgård アルゴリズムのプロセスがわかったので、MD5 アルゴリズムのプロセスを詳しく見てみましょう。RFC 1321 (http://www.ietf.org/rfc/rfc1321.txt) を参照できます。

MD5 アルゴリズムは次の 4 つのステップで構成されます。

  • パディングビットの追加
  • 長さを追加
  • MDバッファを初期化する
  • 16ワードブロックでメッセージを処理する（複雑な関数計算）

主に、MD5 アルゴリズムのパディングと初期化ベクトルの生成という最初の 3 つのステップを理解する必要があります。まず、MD5 のビットを埋めるアルゴリズムを見てみましょう。アルゴリズムは次のように機能します。

1. メッセージの長さ、つまりパディング後のメッセージの長さ（mod 512bit = 448bit）に基づいて、パディングするバイト数を決定します。たとえば、メッセージが「message」の場合、メッセージは 56 ビットなので、392 ビットを埋める必要があります。

2. メッセージ長 mod 512 = 448 ビットの場合でも、最小パディングは 1 ビット、最大パディングは 512 ビットです。つまり、メッセージの長さに関係なくパディングを実行する必要があります。

3. パディング情報の最初のバイトは 0x80 で、残りのデータは 0x00 で埋められます。

次に、長さを埋めるプロセスを見てみましょう。

パディングの長さは 64 ビットです。

長さはリトルエンディアンで保存されます。つまり、上位バイトは上位アドレスに配置されます。

メッセージの長さが 2^64 より大きい場合、つまり 2048PB より大きい場合。 64 ビットでメッセージの長さを格納できない場合は、下位 64 ビットが使用されます。

次の図はパディングの例です。ハッシュされるメッセージは文字列「message」なので、次のようになります。

最後に、初期化ベクトルは固定値です。

01 23 45 67 0x67452301

B 89 AB CD EF 0xEFCDAB89

C FE DC BA 98 0x98BADCFE

76 54 32 10 0x10325476

次に、初期化ベクトルとパディングされたメッセージを使用して複雑な関数演算が実行され、最終的にメッセージ「message」の MD5 値は 78e731027d8fd50ed642340b7c9a63b3 になります。

0x03 MD5 長さ拡張攻撃を理解する

メッセージが 512 ビットより長い場合、メッセージは 512 ビットに分割され、最後のメッセージ ブロックがパディングされます。

7 バイトまたは 56 ビットのメッセージの MD5 値が 78e731027d8fd50ed642340b7c9a63b3 であるとします。

MD5アルゴリズムがこれを処理すると、まずビットを埋めます。メッセージの内容がわからないため、埋めた結果は次のようになります。

次に、初期ベクトルを使用して複雑な関数演算を実行します。MD5値は78e731027d8fd50ed642340b7c9a63b3なので、結果は次のようになります。

A=0x0231e778

0x0ed58f7d ...

0x0b3442d6 の続きを読む

0xb3639a7c の続きを読む

パディングされたメッセージにメッセージ文字列「admin」が追加されると、文字列がパディングされ、前の操作で計算された値が関数操作の初期ベクトルとして使用されます。最終的な MD5 値は e53a681a30ff99e3f6522270ca7db244 です。

これにより、メッセージがわからなくても、メッセージ + パディング + 追加されたメッセージの MD5 値の計算が完了します。

ユーザーのログインを確認するプログラムは次のようになります。

  1. インポートシステム
  2.   urllibから引用符をインポート
  3.  
  4.   defログイン(パスワード、hash_val):
  5.  m =ハッシュライブラリ.md5 ()
  6.  secret_key = "メッセージ"  
  7.       m.update(秘密キー + パスワード)
  8.       (m.hexdigest() == hash_val)の場合:
  9.           「ログインに成功しました！」と印刷します。
  10.       それ以外：
  11.           「ログインに失敗しました」と印刷する
  12.    
  13.   __name__ == "__main__" の場合:
  14. パスワード=引用符なし(sys.argv[1])
  15.  hash_val =引用符なし(sys.argv[2])
  16.       ログイン(パスワード、ハッシュ値)

現在、私たちが知っているのはユーザー名とハッシュのセット、rootとf3c36e01c874865bc081e4ae7af037eaだけです

分析から、secret_key の長さがわかれば、パディングを偽造し、文字列を追加することで secret+padding+追加文字列の MD5 値を計算できることがわかります。追加する文字列が admin であると仮定すると、ハッシュ拡張攻撃を通じて md5(secret+padding+appended string) = e53a681a30ff99e3f6522270ca7db244 を計算できます。次にテストすると、ログインが成功したことが示されます。

md5 拡張攻撃コードは次のとおりです (インターネットから若干変更、使用法: python md5.py attack md5 appended message secret length):

  2.     # コーディング:utf-8
  3.     インポートシステム
  4.     構造体をインポートする
  5.     ハッシュライブラリをインポートする
  6.     binascii をインポートする
  7.         
  8.     定義 F(x, y, z):
  9.         (x & y) | ((~x) & z) を返す
  10.      
  11.      
  12.     G(x, y, z)を定義します。
  13.         (x & z) | (y & (~z)) を返します
  14.      
  15.      
  16.     H(x, y, z)を定義します。
  17.         x ^ y ^ z を返す
  18.      
  19.      
  20.     定義I(x, y, z):
  21.         y ^ (x | (~z)) を返す
  22.      
  23.      
  24.     def _rotateLeft(x,n):
  25.         戻り値 (x < <   n ) | (x > > (32-n)) 
  26.      
  27.      
  28.     def XX(関数、a、b、c、d、x、s、ac):
  29. 解像度= 0L  
  30.  res res = res + a + func(b, c, d)
  31. 解像度解像度= 解像度 + x
  32.  res res = res + ac
  33.  res res = res & 0xffffffffL
  34.  res = _rotateLeft (res, s)
  35.  res res = res & 0xffffffffL
  36.  res res = res + b 
  37.      
  38.         res & 0xffffffffL を返す
  39.      
  40.      
  41.     クラスmd5():
  42.         __init__(self)を定義します。
  43.             自己.A、自己.B、自己.C、自己.D = (0x67452301L、0xefcdab89L、0x98badcfeL、0x10325476L) 
  44.      
  45.         md5_compress(self, buf)を定義します。
  46.             len(buf) != 64の場合:
  47.                 ValueError が発生します。「長さ %d の無効なバッファ: %s」% (len(buf), repr(buf))
  48.  inp =構造体.unpack("I"*16, buf)
  49.             a、b、c、 d =自分.A、自分 .B、自分 .C、自分 .D 
  50.      
  51.             # ラウンド1。
  52.             S11、 S12 、S13、 S14 = 7、12、17、22 
  53.      
  54.  a = XX (F, a, b, c, d, inp[0], S11, 0xD76AA478L) # 1
  55.  d = XX (F, d, a, b, c, inp[1], S12, 0xE8C7B756L) # 2
  56.  c = XX (F, c, d, a, b, inp[2], S13, 0x242070DBL) # 3
  57.  b = XX (F, b, c, d, a, inp[3], S14, 0xC1BDCEEEL) # 4
  58.  a = XX (F, a, b, c, d, inp[4], S11, 0xF57C0FAFL) # 5
  59.  d = XX (F, d, a, b, c, inp[5], S12, 0x4787C62AL) # 6
  60.  c = XX (F, c, d, a, b, inp[6], S13, 0xA8304613L) # 7
  61.  b = XX (F, b, c, d, a, inp[7], S14, 0xFD469501L) # 8
  62.  a = XX (F, a, b, c, d, inp[8], S11, 0x698098D8L) # 9
  63.  d = XX (F, d, a, b, c, inp[9], S12, 0x8B44F7AFL) # 10
  64.  c = XX (F, c, d, a, b, inp[10], S13, 0xFFFF5BB1L) # 11
  65.  b = XX (F, b, c, d, a, inp[11], S14, 0x895CD7BEL) # 12
  66.  a = XX (F, a, b, c, d, inp[12], S11, 0x6B901122L) # 13
  67.  d = XX (F, d, a, b, c, inp[13], S12, 0xFD987193L) # 14
  68.  c = XX (F, c, d, a, b, inp[14], S13, 0xA679438EL) # 15
  69.  b = XX (F, b, c, d, a, inp[15], S14, 0x49B40821L) # 16 
  70.      
  71.             # 第2ラウンド。
  72.             S21 、S22、S23、 S24 = 5、9、14、20 
  73.      
  74.  a = XX (G, a, b, c, d, inp[1], S21, 0xF61E2562L) # 17
  75.  d = XX (G, d, a, b, c, inp[6], S22, 0xC040B340L) # 18
  76.  c = XX (G, c, d, a, b, inp[11], S23, 0x265E5A51L) # 19
  77.  b = XX (G, b, c, d, a, inp[0], S24, 0xE9B6C7AAL) # 20
  78.  a = XX (G, a, b, c, d, inp[5], S21, 0xD62F105DL) # 21
  79.  d = XX (G, d, a, b, c, inp[10], S22, 0x02441453L) # 22
  80.  c = XX (G, c, d, a, b, inp[15], S23, 0xD8A1E681L) # 23
  81.  b = XX (G, b, c, d, a, inp[4], S24, 0xE7D3FBC8L) # 24
  82.  a = XX (G, a, b, c, d, inp[9], S21, 0x21E1CDE6L) # 25
  83.  d = XX (G, d, a, b, c, inp[14], S22, 0xC33707D6L) # 26
  84.  c = XX (G, c, d, a, b, inp[3], S23, 0xF4D50D87L) # 27
  85.  b = XX (G, b, c, d, a, inp[8], S24, 0x455A14EDL) # 28
  86.  a = XX (G, a, b, c, d, inp[13], S21, 0xA9E3E905L) # 29
  87.  d = XX (G, d, a, b, c, inp[2], S22, 0xFCEFA3F8L) # 30
  88.  c = XX (G, c, d, a, b, inp[7], S23, 0x676F02D9L) # 31
  89.  b = XX (G, b, c, d, a, inp[12], S24, 0x8D2A4C8AL) # 32 
  90.      
  91.             # 第3ラウンド。
  92.             S31、S32、S33、 S34 = 4、11、16、23 
  93.      
  94.  a = XX (H, a, b, c, d, inp[5], S31, 0xFFFA3942L) # 33
  95.  d = XX (H, d, a, b, c, inp[8], S32, 0x8771F681L) # 34
  96.  c = XX (H, c, d, a, b, inp[11], S33, 0x6D9D6122L) # 35
  97.  b = XX (H, b, c, d, a, inp[14], S34, 0xFDE5380CL) # 36
  98.  a = XX (H, a, b, c, d, inp[1], S31, 0xA4BEEA44L) # 37
  99.  d = XX (H, d, a, b, c, inp[4], S32, 0x4BDECFA9L) # 38
  100.  c = XX (H, c, d, a, b, inp[7], S33, 0xF6BB4B60L) # 39
  101.  b = XX (H, b, c, d, a, inp[10], S34, 0xBEBFBC70L) # 40
  102.  a = XX (H, a, b, c, d, inp[13], S31, 0x289B7EC6L) # 41
  103.  d = XX (H, d, a, b, c, inp[0], S32, 0xEAA127FAL) # 42
  104.  c = XX (H, c, d, a, b, inp[3], S33, 0xD4EF3085L) # 43
  105.  b = XX (H, b, c, d, a, inp[6], S34, 0x04881D05L) # 44
  106.  a = XX (H, a, b, c, d, inp[9], S31, 0xD9D4D039L) # 45
  107.  d = XX (H, d, a, b, c, inp[12], S32, 0xE6DB99E5L) # 46
  108.  c = XX (H, c, d, a, b, inp[15], S33, 0x1FA27CF8L) # 47
  109.  b = XX (H, b, c, d, a, inp[2], S34, 0xC4AC5665L) # 48 
  110.      
  111.             # 第4ラウンド。
  112.             S41 、 S42、S43、 S44 = 6、10、15、21 
  113.      
  114.  a = XX (I, a, b, c, d, inp[0], S41, 0xF4292244L) # 49
  115.  d = XX (I, d, a, b, c, inp[7], S42, 0x432AFF97L) # 50
  116.  c = XX (I, c, d, a, b, inp[14], S43, 0xAB9423A7L) # 51
  117.  b = XX (I, b, c, d, a, inp[5], S44, 0xFC93A039L) # 52
  118.  a = XX (I, a, b, c, d, inp[12], S41, 0x655B59C3L) # 53
  119.  d = XX (I, d, a, b, c, inp[3], S42, 0x8F0CCC92L) # 54
  120.  c = XX (I, c, d, a, b, inp[10], S43, 0xFFEFF47DL) # 55
  121.  b = XX (I, b, c, d, a, inp[1], S44, 0x85845DD1L) # 56
  122.  a = XX (I, a, b, c, d, inp[8], S41, 0x6FA87E4FL) # 57
  123.  d = XX (I, d, a, b, c, inp[15], S42, 0xFE2CE6E0L) # 58
  124.  c = XX (I, c, d, a, b, inp[6], S43, 0xA3014314L) # 59
  125.  b = XX (I, b, c, d, a, inp[13], S44, 0x4E0811A1L) # 60
  126.  a = XX (I, a, b, c, d, inp[4], S41, 0xF7537E82L) # 61
  127.  d = XX (I, d, a, b, c, inp[11], S42, 0xBD3AF235L) # 62
  128.  c = XX (I, c, d, a, b, inp[2], S43, 0x2AD7D2BBL) # 63
  129.  b = XX (I, b, c, d, a, inp[9], S44, 0xEB86D391L) # 64 
  130.      
  131. 自己.A = (自己.A + a) & 0xffffffffL
  132. 自己.B = (自己.B + b) & 0xffffffffL
  133. 自己.C = (自己.C + c) & 0xffffffffL
  134. 自己.D = (自己.D + d) & 0xffffffffL
  135.             # ' A =%s\ nB =%s\ nC =%s\ nD =%s\n' を出力 % (hex(self.A), hex(self.B), hex(self.C), hex(self.D)) 
  136.      
  137.         パディングを定義します(self, n, sz = None ):
  138.             sz が None の場合:
  139.  sz = n  
  140. 前= 64 -8
  141.  sz =構造体.pack("Q",sz*8)
  142. パッド= '\x80'  
  143.             1 + = 1
  144.             n % 64 < = preの場合:
  145.                 パッド += '\x00' * (前 - n % 64)
  146.                 パッド += sz
  147.             それ以外：
  148.                 パッド += '\x00' * (プレ + 64 - n % 64)
  149.                 パッド += sz
  150.             リターンパッド
  151.      
  152.         def pad(自分自身、メッセージ):
  153.             msg + self.padding(len(msg)) を返します。 
  154.      
  155.         md5_iter を定義します(self、padding_msg):
  156.             len(padding_msg) % 64 == 0 をアサートする
  157.             iが範囲(0、len(padding_msg)、64)内である場合:
  158. ブロック= padding_msg [i:i+64]
  159.                 自己.md5_compress(パディングメッセージ[i:i+64]) 
  160.      
  161.         defダイジェスト(自己):
  162.             return struct.pack(' < IIII ', self.A, self.B, self.C, self.D) def hexdigest(self): return binascii.hexlify(self.digest()).decode() def my_md5(self, msg): padding_msg = self .pad(msg) self.md5_iter(padding_msg) return self.hexdigest() # md5 値を使用して、最後のラウンドのマジックナンバーを逆算します。 def compute_magic_number(self, md5str): self.A = struct .unpack("I", md5str[0:8].decode('hex'))[0] self.B = struct .unpack("I", md5str[8:16].decode('hex'))[0] self.C = struct .unpack("I", def extension_attack(self, md5str, str_append, lenth): self.compute_magic_number(md5str) p = self .padding (lenth) padding_msg = self .padding ( len ( str_append ), lenth + len(p) + len(str_append) ) self.md5_iter ( str_append + padding_msg ) __name__ == 'の場合、self.hexdigest()を返します。 "__main__": m = md5 () if len(sys.argv) != 4: #print m.my_md5("123456") src = m .pad(sys.argv[1]) + sys.argv[2] print 'md5 padding - > ',m.my_md5(src)
  163.         それ以外：
  164.             'md5 extension_attack - > ',m.extension_attack(sys.argv[1], sys.argv[2], を印刷します。

0x04 概要

この攻撃方法の原理は、暗号文の md5 と暗号文の長さがわかれば、連結された暗号文と拡張メッセージの md5 を推測できるというものです。予防方法も非常に簡単です。

方法 1: HMAC アルゴリズムを使用する HMAC(secret||padding)=H(secret||H(secret||padding))

方法2: シークレットとパディングの位置を入れ替える、つまりMAC(パディング||シークレット)

通常、署名として使用できるのは md5 です。過去には Amazon AWS と Flicker の署名の脆弱性が 2 つありましたが、どちらも md5 ハッシュ長を拡張することで攻撃される可能性があります。最近では、ハッシュ長拡張を使用して悪用される可能性のある PHPWind の脆弱性も発見されました。

しかし、この攻撃方法の現在の開発傾向はCTF 233333に留まるはずです。

0x05 参照

翻訳元:

http://blog.chinaunix.net/uid-27070210-id-3255947.htm

<<:  データサイエンティストが最もよく使用するアルゴリズム10選

>>:  顔認識のゴッドファーザー、李自青氏：技術革新が業界の未来を力づける

ブログ    

推薦する

ByteDanceがCowClipをオープンソース化：推奨モデルのシングルカードトレーニングを最大72倍高速化可能

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載...

Baiduの李振宇氏：Apollo 3.0のリリースはApolloのオープン性の新たな出発点です

自動車業界から大きな注目を集めるアポロオープンプラットフォームは、新たな量産時代を迎えました。 7月...

...

業界の洞察 | スマート シティと省エネ通信インフラ

スマートグリッドはエネルギー配給と通信ネットワークに革命をもたらす以下では、スマートグリッドの主な特...

能力と信頼性の両方を備えることはできますか? GPT-4やGeminiなどのマルチモーダルモデルの評価レポートはこちら

2023 年には、マルチモーダル大規模モデルの飛躍的な発展が見られるでしょう。マルチモーダル大規模言...

...

人工知能と機械学習がビジネスに及ぼす影響

[[400670]]人工知能と機械学習が今日のテクノロジー業界のあらゆる部分に影響を与えていることは...

...

...

LeCun が予測した自己教師モデルはここにあります: 最初のマルチモーダル高性能自己教師アルゴリズム

自己教師あり学習は、さまざまなタスクで階層的な特徴を学習し、実生活で利用可能な膨大なデータをリソース...

...

虐殺後に行方不明になった親族をAIで探す！ Googleのエンジニアが第二次世界大戦の70万枚以上の古い写真を識別できる顔認識プログラムを開発

AI顔認識の分野で新たなビジネスが開拓されているのでしょうか？今回の課題は、第二次世界大戦の古い写真...

...

人工知能を理解していないかもしれませんが、次の3つのポイントを知っておく必要があります

人工知能は人間の弱点を補うものであり、人間に代わるものではない多くの人が「人工知能が人間に取って代わ...

テレンス・タオ：2026 年には、GPT が数学論文の共著者となる予定です。 GPT-4の「フルバージョン」を事前に試してみたら衝撃を受けた

3か月前、OpenAIのGPT-4がデビューし、注目を集めました。そのマルチモーダル機能は人類に衝撃...