初期seedから日時を求める無謀な挑戦
(初期seedから日時を求める無謀な挑戦 - Plus Le Toolから移動しました。)
まだ結果が出るところまでたどり着けていないので、読むだけ時間の無駄ですよ。
話が抽象的すぎるし。途中から詭弁っぽくなるし。
まずは、SHA-1に渡すメッセージデータを確認しておく。
(初期seedの求め方の解説は既に他の人がやってるので省略。)
入力 | nazo1 | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
byte | 00 | 01 | 02 | 03 | ||||||||||||||||||||||||||||
bit | 000 | 001 | 002 | 003 | 004 | 005 | 006 | 007 | 008 | 009 | 00a | 00b | 00c | 00d | 00e | 00f | 010 | 011 | 012 | 013 | 014 | 015 | 016 | 017 | 018 | 019 | 01a | 01b | 01c | 01d | 01e | 01f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | nazo2 | |||||||||||||||||||||||||||||||
byte | 04 | 05 | 06 | 07 | ||||||||||||||||||||||||||||
bit | 020 | 021 | 022 | 023 | 024 | 025 | 026 | 027 | 028 | 029 | 02a | 02b | 02c | 02d | 02e | 02f | 030 | 031 | 032 | 033 | 034 | 035 | 036 | 037 | 038 | 039 | 03a | 03b | 03c | 03d | 03e | 03f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | nazo3 | |||||||||||||||||||||||||||||||
byte | 08 | 09 | 0a | 0b | ||||||||||||||||||||||||||||
bit | 040 | 041 | 042 | 043 | 044 | 045 | 046 | 047 | 048 | 049 | 04a | 04b | 04c | 04d | 04e | 04f | 050 | 051 | 052 | 053 | 054 | 055 | 056 | 057 | 058 | 059 | 05a | 05b | 05c | 05d | 05e | 05f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | nazo4 | |||||||||||||||||||||||||||||||
byte | 0c | 0d | 0e | 0f | ||||||||||||||||||||||||||||
bit | 060 | 061 | 062 | 063 | 064 | 065 | 066 | 067 | 068 | 069 | 06a | 06b | 06c | 06d | 06e | 06f | 070 | 071 | 072 | 073 | 074 | 075 | 076 | 077 | 078 | 079 | 07a | 07b | 07c | 07d | 07e | 07f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | nazo5 | |||||||||||||||||||||||||||||||
byte | 10 | 11 | 12 | 13 | ||||||||||||||||||||||||||||
bit | 080 | 081 | 082 | 083 | 084 | 085 | 086 | 087 | 088 | 089 | 08a | 08b | 08c | 08d | 08e | 08f | 090 | 091 | 092 | 093 | 094 | 095 | 096 | 097 | 098 | 099 | 09a | 09b | 09c | 09d | 09e | 09f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | timer0 | VCount | ||||||||||||||||||||||||||||||
byte | 14 | 15 | 16 | 17 | ||||||||||||||||||||||||||||
bit | 0a0 | 0a1 | 0a2 | 0a3 | 0a4 | 0a5 | 0a6 | 0a7 | 0a8 | 0a9 | 0aa | 0ab | 0ac | 0ad | 0ae | 0af | 0b0 | 0b1 | 0b2 | 0b3 | 0b4 | 0b5 | 0b6 | 0b7 | 0b8 | 0b9 | 0ba | 0bb | 0bc | 0bd | 0be | 0bf |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | (定数) | MAC5 | MAC6 | |||||||||||||||||||||||||||||
byte | 18 | 19 | 1a | 1b | ||||||||||||||||||||||||||||
bit | 0c0 | 0c1 | 0c2 | 0c3 | 0c4 | 0c5 | 0c6 | 0c7 | 0c8 | 0c9 | 0ca | 0cb | 0cc | 0cd | 0ce | 0cf | 0d0 | 0d1 | 0d2 | 0d3 | 0d4 | 0d5 | 0d6 | 0d7 | 0d8 | 0d9 | 0da | 0db | 0dc | 0dd | 0de | 0df |
種類 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | MAC(1,2,3,4) xor GxStat xor Frame | |||||||||||||||||||||||||||||||
byte | 1c | 1d | 1e | 1f | ||||||||||||||||||||||||||||
bit | 0e0 | 0e1 | 0e2 | 0e3 | 0e4 | 0e5 | 0e6 | 0e7 | 0e8 | 0e9 | 0ea | 0eb | 0ec | 0ed | 0ee | 0ef | 0f0 | 0f1 | 0f2 | 0f3 | 0f4 | 0f5 | 0f6 | 0f7 | 0f8 | 0f9 | 0fa | 0fb | 0fc | 0fd | 0fe | 0ff |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
入力 | 年 | 月 | 日 | 曜日 | ||||||||||||||||||||||||||||
byte | 20 | 21 | 22 | 23 | ||||||||||||||||||||||||||||
bit | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 10a | 10b | 10c | 10d | 10e | 10f | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 11a | 11b | 11c | 11d | 11e | 11f |
種類 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 0 | 0 | 0 | 変 | 変 | 変 | 変 | 変 | 0 | 0 | 変 | 変 | 変 | 変 | 変 | 変 | 0 | 0 | 0 | 0 | 0 | 変 | 変 | 変 |
入力 | 時 | 分 | 秒 | (定数) | ||||||||||||||||||||||||||||
byte | 24 | 25 | 26 | 27 | ||||||||||||||||||||||||||||
bit | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 12a | 12b | 12c | 12d | 12e | 12f | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 13a | 13b | 13c | 13d | 13e | 13f |
種類 | 0 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 0 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 0 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
入力 | (定数) | |||||||||||||||||||||||||||||||
byte | 28 | 29 | 2a | 2b | ||||||||||||||||||||||||||||
bit | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 14a | 14b | 14c | 14d | 14e | 14f | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 15a | 15b | 15c | 15d | 15e | 15f |
種類 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
入力 | (定数) | |||||||||||||||||||||||||||||||
byte | 2c | 2d | 2e | 2f | ||||||||||||||||||||||||||||
bit | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 16a | 16b | 16c | 16d | 16e | 16f | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 17a | 17b | 17c | 17d | 17e | 17f |
種類 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
入力 | キー入力 | (定数) | ||||||||||||||||||||||||||||||
byte | 30 | 31 | 32 | 33 | ||||||||||||||||||||||||||||
bit | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 18a | 18b | 18c | 18d | 18e | 18f | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 19a | 19b | 19c | 19d | 19e | 19f |
種類 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 変 | 0 | 0 | 1 | 0 | 1 | 1 | 変 | 変 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
入力 | (定数) | |||||||||||||||||||||||||||||||
byte | 34 | 35 | 36 | 37 | ||||||||||||||||||||||||||||
bit | 1a0 | 1a1 | 1a2 | 1a3 | 1a4 | 1a5 | 1a6 | 1a7 | 1a8 | 1a9 | 1aa | 1ab | 1ac | 1ad | 1ae | 1af | 1b0 | 1b1 | 1b2 | 1b3 | 1b4 | 1b5 | 1b6 | 1b7 | 1b8 | 1b9 | 1ba | 1bb | 1bc | 1bd | 1be | 1bf |
種類 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
入力 | (定数) | |||||||||||||||||||||||||||||||
byte | 38 | 39 | 3a | 3b | ||||||||||||||||||||||||||||
bit | 1c0 | 1c1 | 1c2 | 1c3 | 1c4 | 1c5 | 1c6 | 1c7 | 1c8 | 1c9 | 1ca | 1cb | 1cc | 1cd | 1ce | 1cf | 1d0 | 1d1 | 1d2 | 1d3 | 1d4 | 1d5 | 1d6 | 1d7 | 1d8 | 1d9 | 1da | 1db | 1dc | 1dd | 1de | 1df |
種類 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
入力 | (定数) | |||||||||||||||||||||||||||||||
byte | 3c | 3d | 3e | 3f | ||||||||||||||||||||||||||||
bit | 1e0 | 1e1 | 1e2 | 1e3 | 1e4 | 1e5 | 1e6 | 1e7 | 1e8 | 1e9 | 1ea | 1eb | 1ec | 1ed | 1ee | 1ef | 1f0 | 1f1 | 1f2 | 1f3 | 1f4 | 1f5 | 1f6 | 1f7 | 1f8 | 1f9 | 1fa | 1fb | 1fc | 1fd | 1fe | 1ff |
種類 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
表の種類欄で、「変」は変数(求めたい値)、「媒」は媒介変数(実行時に値を代入する)、「0」と「1」は定数である。
この表より、入力データ512bitのうち53bitが変数、240bitが媒介変数、219bitが定数だと分かる。
とりあえず、512個のbool型変数 \(x_{000},x_{001},\dots,x_{1ff}\) を、上の表の各bitに順に割り当てることにする(分かりにくいけど添字は16進)。
もちろん、例えば \(x_{0c0}\) は定数で、常に \(x_{0c0}=0\) である。他の定数も同様。
次に、SHA-1からの出力値と初期seedの関係を見てみる。
出力 | 初期seed上位 | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
byte | 00 | 01 | 02 | 03 | ||||||||||||||||||||||||||||
bit | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0a | 0b | 0c | 0d | 0e | 0f | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1a | 1b | 1c | 1d | 1e | 1f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
出力 | 初期seed下位 | |||||||||||||||||||||||||||||||
byte | 04 | 05 | 06 | 07 | ||||||||||||||||||||||||||||
bit | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 2a | 2b | 2c | 2d | 2e | 2f | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 3a | 3b | 3c | 3d | 3e | 3f |
種類 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 | 媒 |
出力 | (未使用) | |||||||||||||||||||||||||||||||
byte | 08 | 09 | 0a | 0b | ||||||||||||||||||||||||||||
bit | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 4a | 4b | 4c | 4d | 4e | 4f | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 5a | 5b | 5c | 5d | 5e | 5f |
種類 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 |
出力 | (未使用) | |||||||||||||||||||||||||||||||
byte | 0c | 0d | 0e | 0f | ||||||||||||||||||||||||||||
bit | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 6a | 6b | 6c | 6d | 6e | 6f | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 7a | 7b | 7c | 7d | 7e | 7f |
種類 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 |
出力 | (未使用) | |||||||||||||||||||||||||||||||
byte | 10 | 11 | 12 | 13 | ||||||||||||||||||||||||||||
bit | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 8a | 8b | 8c | 8d | 8e | 8f | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 9a | 9b | 9c | 9d | 9e | 9f |
種類 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 | 任 |
表の種類欄で、「媒」は媒介変数(実行時に値を代入する)、「任」は任意の値である。
この表より、出力データ160bitのうち64bitが媒介変数、96bitが任意の値だと分かる。
入力データと同様に、160個のbool型変数 \(y_{00},y_{01},\dots,y_{9f}\) を、上の表の各bitに順に割り当てることにする。
ここからは数式を使った話になるが、その前に使う記号の確認をしておく。
SHA-1の計算過程で必要な演算子は、論理積,論理和,排他的論理和,論理否定,算術和,循環シフト,および代入の7種類である。
ここでは、それらを次の記号を使って表すことにする(→補題:数式中で使う記号の定義 - Plus Le Blog)。
さて今、SHA-1への入力値 \(x_{000},x_{001},\dots,x_{1ff}\) と、それに対するSHA-1の出力値 \(y_{00},y_{01},\dots,y_{9f}\) の関係について考える。
いかに計算過程が複雑なSHA-1とはいえ、やっていることは論理積,論理和,排他的論理和,論理否定,算術和,循環シフト,代入の有限回の組み合わせにすぎない。
よって、その計算過程を全部まとめて1つの関数とみなして、次のように表すことができる。
(*1)
\begin{eqnarray*}
y_{00}&=&SHA_{00}\left(x_{000},x_{001},\dots,x_{1ff}\right)\\
y_{01}&=&SHA_{01}\left(x_{000},x_{001},\dots,x_{1ff}\right)\\
&\vdots&\\
y_{9f}&=&SHA_{9f}\left(x_{000},x_{001},\dots,x_{1ff}\right)
\end{eqnarray*}
(※関数 \(SHA_{t}\) が具体的にどんな式かはまだ分からないが、それについては別の記事で考える(予定)。)
この160本の方程式には672(=512+160)個の変数が含まれるが、実際に求めたい値は53個だけで、残りの619個の変数は任意の値か、定数か、逆算実行時には判明している値(媒介変数)のいずれかである。
よって(*1)は、未知変数53個の160連方程式である。
(※念のため補足しておくと、関数 \(SHA_{t}\) の中には算術和や論理積を含むので、 \(x_{i_{1}}x_{i_{2}}\dots x_{i_{n}}\) のような高次の項を持っている。よってこれらの方程式の次数はそれぞれ512と考える。ただし定数などのため実際の次数は512より低くなる。)
式(*1)では入力か出力かによって文字(変数)を分けているため、この先の議論に不便である。
そこで、次のように文字(変数)の置き換えをする(※添字が10進になったことに注意)。
- 240個の媒介変数(nazoなどのパラメータ): \(x_{000}\)~\(x_{0bf}\),\(x_{0d0}\)~\(x_{0ff}\)
- → \(p_{1},p_{2},\dots,p_{240}\)
- 64個の媒介変数(初期seed): \(y_{00}\)~\(y_{3f}\)
- → \(s_{1},s_{2},\dots,s_{64}\)
- 53個の未知変数: \(x_{100}\)~\(x_{107}\),\(x_{10b}\)~\(x_{10f}\),\(x_{112}\)~\(x_{117}\),\(x_{11d}\)~\(x_{11f}\),\(x_{121}\)~\(x_{127}\),\(x_{129}\)~\(x_{12f}\),\(x_{131}\)~\(x_{137}\)
- → \(u_{1},u_{2},\dots,u_{53}\)
- 96個の任意の値: \(y_{40}\)~\(y_{9f}\)
- → \(v_{1},v_{2},\dots,v_{96}\)
- 219個の定数値: \(x_{0c0}\)~\(x_{0cf}\),\(x_{108},x_{109},x_{10a}\),\(x_{110},x_{111}\),\(x_{118},x_{119},x_{11a},x_{11b},x_{11c}\),\(x_{120}\),\(x_{128}\),\(x_{130}\),\(x_{138}\)~\(x_{17f}\),\(x_{188}\)~\(x_{18d}\),\(x_{190}\)~\(x_{1ff}\)
- → \(a_{1},a_{2},\dots,a_{219}\)
(※どの文字をどの文字に置き換えるかは具体的に計算する段階で決めればいいので、今は深く考えなくていい。)
(※媒介変数を\(p_{i}\)と\(s_{i}\)の2種類に分けたのには理由があるが、それはまた後ほど。)
この文字の置き換えによって、式(*1)は次のように書き換えられる。
(*2)
\begin{eqnarray*}
s_{i_{1}}&=&SHA_{00}'\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53},a_{1},a_{2},\dots,a_{219}\right)\\
s_{i_{2}}&=&SHA_{01}'\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53},a_{1},a_{2},\dots,a_{219}\right)\\
&\vdots&\\
s_{i_{64}}&=&SHA_{3f}'\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53},a_{1},a_{2},\dots,a_{219}\right)\\
v_{j_{1}}&=&SHA_{40}'\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53},a_{1},a_{2},\dots,a_{219}\right)\\
v_{j_{2}}&=&SHA_{41}'\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53},a_{1},a_{2},\dots,a_{219}\right)\\
&\vdots&\\
v_{j_{96}}&=&SHA_{9f}'\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53},a_{1},a_{2},\dots,a_{219}\right)
\end{eqnarray*}
この式(*2)を変形していき、最終的に次のような形にすることが目標である。
(*3)
\begin{eqnarray*}
u_{1}&=&func_{1}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
u_{2}&=&func_{2}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
u_{53}&=&func_{53}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)
\end{eqnarray*}
つまり、未知変数 \(u_{1},u_{2},\dots,u_{53}\) を媒介変数 \(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\) の関数で表すということだ。
もしもこの形への変形ができるならば、初期seedから日時の逆算が可能ということになる。
では、どうすれば式(*2)を式(*3)の形に変形できるか考えてみる。
とりあえず、定数文字を消去しておく。
最初に書いた表の値を定数 \(a_{1},a_{2},\dots,a_{219}\) に代入し整理すると、次のようになる。
(*4)
\begin{eqnarray*}
s_{i_{1}}&=&SHA_{00}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
s_{i_{2}}&=&SHA_{01}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
&\vdots&\\
s_{i_{64}}&=&SHA_{3f}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
v_{j_{1}}&=&SHA_{40}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
v_{j_{2}}&=&SHA_{41}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
&\vdots&\\
v_{j_{96}}&=&SHA_{9f}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)
\end{eqnarray*}
次に、式(*4)を \(u_{1},u_{2},\dots,u_{53},v_{1},v_{2},\dots,v_{96}\) について解く。
と言っても、(*6)の160本の方程式のうち下96本はすでに \(v_{1},v_{2},\dots,v_{96}\) について解いた形になっている。
なので、(*4)の方程式の上64本だけを使って \(u_{1},u_{2},\dots,u_{53}\) について解き、それらを下96本に代入すればよい。
しかしここで1つ問題がある。
それは「 \(u_{1},u_{2},\dots,u_{53}\) について解く」ことが実際に可能なのかが、現段階ではまだ分からないことだ。
だが今の目的はあくまで大まかな方針の確認であり、細かい話は後で考えればいい。
ということで、解くことができるという前提でとりあえず話を進める。
(*4)の方程式の上64本が次のように変形できたとする。
(*5)
\begin{eqnarray*}
u_{1}&=&f_{1}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
u_{2}&=&f_{2}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
u_{53}&=&f_{53}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
0&=&f_{54}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
0&=&f_{55}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
0&=&f_{64}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)
\end{eqnarray*}
これを(*4)の方程式の下96本の \(u_{1},u_{2},\dots,u_{53}\) に代入して整理すると、次のようになる。
(*6)
\begin{eqnarray*}
v_{1}&=&f_{65}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
v_{2}&=&f_{66}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
v_{96}&=&f_{160}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)
\end{eqnarray*}
ここで改めて、式(*5)(*6)中に出てくる各文字の意味を確認してみる。
右辺にある文字のうち、 \(p_{1},p_{2},\dots,p_{240}\) はnazoやMACなどのパラメータを表す媒介変数であり、 \(s_{1},s_{2},\dots,s_{64}\) は初期seedを表す媒介変数である。
また、左辺にある \(u_{1},u_{2},\dots,u_{53}\) は起動日時およびキー入力を表す未知変数(求めたい値)であり、 \(v_{1},v_{2},\dots,v_{96}\) はSHA-1の出力値のうち未使用の下位96bitを表す任意の値だった。
これらより式(*5)(*6)の表す意味は、次のようにまとめられる。
- (*5)の方程式の上53本は、nazoなどのパラメータと初期seedから起動日時およびキー入力を得るための式である。
- (*5)の方程式の下11本は、nazoなどのパラメータと初期seedの満たすべき関係を表す式である。言い換えると、この11本の式は元の連立方程式の解の存在条件である。
- 式(*6)は、nazoなどのパラメータと初期seedから、SHA-1の出力値の下位96bitを得るための式である。
ここで注目したいのが、式(*6)の96本の方程式だ。
SHA-1の出力値の下位96bitは一切使われずに捨てられる値であるため、実際には任意の値でよい。
するとこの96本の方程式は不要な値を求める式、つまり無意味な式ということになる。
よって式(*6)は不要となるので、必要な式は(*5)のみとなる。
式(*5)を少し書き換えて、次式を得る。
(*A)nazoなどのパラメータと初期seedから、起動日時とキー入力を逆算する式
\begin{eqnarray*}
u_{1}&=&f_{1}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
u_{2}&=&f_{2}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
u_{53}&=&f_{53}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)
\end{eqnarray*}
(*B)nazoなどのパラメータと初期seedが満たすべき関係式(解の存在条件)
\begin{eqnarray*}
f_{54}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)&=&0\\
f_{55}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)&=&0\\
&\vdots&\\
f_{64}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)&=&0
\end{eqnarray*}
以上で、SHA-1の計算過程である式(*1)から、それを逆算する式(*A)と、解の存在条件(*B)に変形できた。
式中に使われている媒介変数の数は304個で、関数 \(f_{i}\) の内部では算術和や論理積を含むので、最大で304次の項を含むことになる。
最悪のケース(0次から304次まですべての項を含む積和標準系の式)では、項数は \(2^{304}\) にもなり、演算回数は論理積 \(\displaystyle\sum_{i=0}^{304}\left(i-1\right)\cdot{}_{304}C_{i}\) 回、論理和 \(2^{304}-1\) 回、論理否定 \(\displaystyle\frac{1}{2}\cdot\sum_{i=0}^{304}i\cdot{}_{304}C_{i}\) 回(期待値)にもなる。
これほどの計算に要する時間と、逆算ではなく順当に総当りで計算するのに要する時間とでは、どちらの方が短いのか? ……という問題があるが、それはまた別の記事で書く(予定)。
それよりも、後回しにしていたもっと重要な問題について考えなければならない。
つまり、
(*4)再掲
\begin{eqnarray*}
s_{i_{1}}&=&SHA_{00}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
s_{i_{2}}&=&SHA_{01}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
&\vdots&\\
s_{i_{64}}&=&SHA_{3f}''\left(p_{1},p_{2},\dots,p_{240},u_{1},u_{2},\dots,u_{53}\right)\\
\end{eqnarray*}
を \(u_{1},u_{2},\dots,u_{53}\) について解いて
(*5)再掲
\begin{eqnarray*}
u_{1}&=&f_{1}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
u_{2}&=&f_{2}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
u_{53}&=&f_{53}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
0&=&f_{54}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
0&=&f_{55}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)\\
&\vdots&\\
0&=&f_{64}\left(p_{1},p_{2},\dots,p_{240},s_{1},s_{2},\dots,s_{64}\right)
\end{eqnarray*}
の形に変形することが本当に可能なのか、ということだ。
また、ただ変形するだけではなく、プログラムに実装しやすいような変形方法を考えなければならない。
そして、それを考えるためには、そもそも
(*1)再掲
\begin{eqnarray*}
y_{00}&=&SHA_{00}\left(x_{000},x_{001},\dots,x_{1ff}\right)\\
y_{01}&=&SHA_{01}\left(x_{000},x_{001},\dots,x_{1ff}\right)\\
&\vdots&\\
y_{9f}&=&SHA_{9f}\left(x_{000},x_{001},\dots,x_{1ff}\right)
\end{eqnarray*}
の関数 \(SHA_{t}\) が具体的にどんな式なのかを先に考えないといけない(もちろんこれも、実装しやすいように)。
その辺りの話を次回の記事で書こうと思う。
……メドが立ってないので何年先になるかは分からんけど。
【余談】
53個の未知変数のうち \(x_{100},x_{101},\dots,x_{107}\) の8個は「年」を表すのに使われている。
しかしこれらの変数はそれぞれが自由な値を取ることができるのではない。
例えば、年の一の位を表す4つの変数 \(x_{104},x_{105},x_{106},x_{107}\) は、 \(\left(x_{104}x_{105}x_{106}x_{107}\right)_{2}\) が0以上9以下になるような組み合わせでなければならない。
具体的には、 \(x_{104}=0\) ならば \(x_{105},x_{106},x_{107}\) は任意の値を取ることができるが、 \(x_{104}=1\) の時は \(x_{105}=x_{106}=0\) でなければならない( \(x_{107}\) は任意の値でよい)。
これを式で表すと次のようになる。
(☆)
\[
x_{104}\left(x_{105}\,\cup\,x_{106}\right)=0
\]
言い換えると、 \(x_{104},x_{105},x_{106},x_{107}\) は式(☆)を拘束条件に持つ、と言える。
同様に、「月」「日」「時」「分」「秒」にもそれぞれ拘束条件がある。
また、曜日は年,月,日から一意に決まるので、曜日を表す未知変数 \(x_{11d},x_{11e},x_{11f}\) にも拘束条件がある。
このように、53個の未知変数 \(u_{1},u_{2},\dots,u_{53}\) は任意の値を取ることができるのではなく、いくつかの拘束条件を満たす値でなければならない。
見方を変えれば、この拘束条件は元の連立方程式の解の存在条件とも言える。
このことついては、別の記事で(気が向いたら)書く。