さて、前回整理したとおり、まずはSHA-1が破られた件を改めて確認し、その上でSHA-256を見ていきましょう。
先に書いておきますが、ここまで踏み込んで書けているということは、対処法を含めて現時点では問題ないことを確認できている（SHA-256）という意味です。
もちろん、それでもこの状態を……そうですね、このまま七年以上放置した場合には、どうなるかは誰にもわかりません。したがって、適切な対応は必須ですよ。
結果
- SHA-1 に衝突が成立した
- 必要となった計算量はこのオーダーだった
→ ここまでは公開されています
構造
- 差分パス
- 条件式など
→ これも論文として公開されています
兆候
- どの物理量・統計量を見て「怪しい」と判断したのか
- どの段階で「ここを深掘りする価値がある」と分かったのか
→ この部分は共有されていません
そのため、「同じ構造を持つ兄弟であるSHA-256は本当に大丈夫なのか」という疑問が、どうしても残ることになります。
よって、この 兆候を何とかして見つける必要がありました。
これが見えない限り、やはり 差分パスや量子探索は怖いままだからです。
そして、ようやくです。ありました。みつけましたよ。
見つけた手法をSHA-1に適用した結果が以下の結果Aです。ご覧のとおり、反転しないビットがはっきりと浮かび上がっています。しかも連続しています。
これは、ちょうどh3に該当する領域です。これだけ連続して弱い部分があれば、差分パスで狙われ、破られてしまった理由も自然に説明がつきます。
さらに、その計算量も合致します。
弱い部分はh3全体で32ビット。全部で160ビットですから、160 – 32 = 128となります。
ここから差分パス総当たりで(n/2)として2^64あたりで1つはヒットするだろう、ですね。
そして、SHA-1が破られた計算量もこの付近でした。
そして、兆候を捉える手法が分かった以上、次に考えるべきは
「これを SHA-256 に適用するとどうなるのか」 です。
この種の話題について、当事者側が自ら口にすることはまずありません。
よって、こちらから自分で調べ、整理し、こうして共有していく必要があるのです。
結果A
=== Avalanche Analysis SHA-1: A method was adopted to isolate regions with weak bit-flip behavior. As a result, bit flips in the range [96] — [127] effectively ceased. ===
Pairs : 600000
Hash bits : 160
Mean distance : 64.011078 (expected 80.000000)
Variance : 32.007159 (expected 40.000000)
Chi² (Binom 0.5) : 142954694.630923 dof=96 approx p=0.000e+00
— Hamming distance histogram (k : count) —
0 : 0
1 : 0
2 : 0
3 : 0
4 : 0
5 : 0
6 : 0
7 : 0
77 : 3003
78 : 1975
79 : 1280
80 : 836
81 : 413
82 : 255
83 : 141
…
153 : 0
154 : 0
155 : 0
156 : 0
157 : 0
158 : 0
159 : 0
160 : 0
— Per-bit flip rate (MSB-first) —
bit[0] : 0.500942
bit[1] : 0.500233
bit[2] : 0.498808
bit[3] : 0.499670
bit[4] : 0.499513
bit[5] : 0.500322
bit[6] : 0.499333
bit[7] : 0.499827
bit[8] : 0.498802
bit[9] : 0.499515
bit[10] : 0.500908
bit[11] : 0.499640
bit[12] : 0.501067
bit[13] : 0.500175
bit[14] : 0.500120
bit[15] : 0.500847
bit[16] : 0.500295
bit[17] : 0.500697
bit[18] : 0.501340
bit[19] : 0.499262
bit[20] : 0.499370
bit[21] : 0.500155
bit[22] : 0.499972
bit[23] : 0.500368
bit[24] : 0.500593
bit[25] : 0.498722
bit[26] : 0.498842
bit[27] : 0.499488
bit[28] : 0.500617
bit[29] : 0.500847
bit[30] : 0.499490
bit[31] : 0.500285
bit[32] : 0.500063
bit[33] : 0.500953
bit[34] : 0.501737
bit[35] : 0.500057
bit[36] : 0.499797
bit[37] : 0.499862
bit[38] : 0.499645
bit[39] : 0.500287
bit[40] : 0.500732
bit[41] : 0.500988
bit[42] : 0.500507
bit[43] : 0.500715
bit[44] : 0.500125
bit[45] : 0.501055
bit[46] : 0.499698
bit[47] : 0.499852
bit[48] : 0.499728
bit[49] : 0.499810
bit[50] : 0.499665
bit[51] : 0.500078
bit[52] : 0.501485
bit[53] : 0.499725
bit[54] : 0.499808
bit[55] : 0.500932
bit[56] : 0.499912
bit[57] : 0.499878
bit[58] : 0.500590
bit[59] : 0.499895
bit[60] : 0.499230
bit[61] : 0.499712
bit[62] : 0.499630
bit[63] : 0.500177
bit[64] : 0.499187
bit[65] : 0.501142
bit[66] : 0.500417
bit[67] : 0.499418
bit[68] : 0.500075
bit[69] : 0.500692
bit[70] : 0.500648
bit[71] : 0.500415
bit[72] : 0.499070
bit[73] : 0.500388
bit[74] : 0.499638
bit[75] : 0.499870
bit[76] : 0.500727
bit[77] : 0.500032
bit[78] : 0.500203
bit[79] : 0.500518
bit[80] : 0.500320
bit[81] : 0.499033
bit[82] : 0.499737
bit[83] : 0.500545
bit[84] : 0.500073
bit[85] : 0.500312
bit[86] : 0.499952
bit[87] : 0.500452
bit[88] : 0.499762
bit[89] : 0.500343
bit[90] : 0.500207
bit[91] : 0.499883
bit[92] : 0.500187
bit[93] : 0.499517
bit[94] : 0.498203
bit[95] : 0.499937
bit[96] : 0.000000
bit[97] : 0.000000
bit[98] : 0.000000
bit[99] : 0.000000
bit[100] : 0.000000
bit[101] : 0.000000
bit[102] : 0.000000
bit[103] : 0.000000
bit[104] : 0.000000
bit[105] : 0.000000
bit[106] : 0.000000
bit[107] : 0.000000
bit[108] : 0.000000
bit[109] : 0.000000
bit[110] : 0.000000
bit[111] : 0.000000
bit[112] : 0.000000
bit[113] : 0.000000
bit[114] : 0.000000
bit[115] : 0.000000
bit[116] : 0.000000
bit[117] : 0.000000
bit[118] : 0.000000
bit[119] : 0.000000
bit[120] : 0.000000
bit[121] : 0.000000
bit[122] : 0.000000
bit[123] : 0.000000
bit[124] : 0.000000
bit[125] : 0.000000
bit[126] : 0.000000
bit[127] : 0.000000
bit[128] : 0.499962
bit[129] : 0.499903
bit[130] : 0.501248
bit[131] : 0.500265
bit[132] : 0.499897
bit[133] : 0.500522
bit[134] : 0.499882
bit[135] : 0.500123
bit[136] : 0.498602
bit[137] : 0.500745
bit[138] : 0.500147
bit[139] : 0.498855
bit[140] : 0.500337
bit[141] : 0.499142
bit[142] : 0.499943
bit[143] : 0.500707
bit[144] : 0.499738
bit[145] : 0.499828
bit[146] : 0.499822
bit[147] : 0.500003
bit[148] : 0.500198
bit[149] : 0.499393
bit[150] : 0.500922
bit[151] : 0.499355
bit[152] : 0.500637
bit[153] : 0.500768
bit[154] : 0.499465
bit[155] : 0.499955
bit[156] : 0.500755
bit[157] : 0.500288
bit[158] : 0.500533
bit[159] : 0.501847
