Hatena::ブログ(Diary)

Plus Le Tool

13/04/27

初期seedから日時を求める無謀な挑戦

まだ結果が出るところまでたどり着けていないので、読むだけ時間の無駄ですよ。
話が抽象的すぎるし。途中から詭弁っぽくなるし。


まずは、SHA−1に渡すメッセージデータを確認しておく。
(初期seedの求め方の解説は既に他の人がやってるので省略。)
入力nazo1
byte00010203
bit00000100200300400500600700800900a00b00c00d00e00f01001101201301401501601701801901a01b01c01d01e01f
種類
入力nazo2
byte04050607
bit02002102202302402502602702802902a02b02c02d02e02f03003103203303403503603703803903a03b03c03d03e03f
種類
入力nazo3
byte08090a0b
bit04004104204304404504604704804904a04b04c04d04e04f05005105205305405505605705805905a05b05c05d05e05f
種類
入力nazo4
byte0c0d0e0f
bit06006106206306406506606706806906a06b06c06d06e06f07007107207307407507607707807907a07b07c07d07e07f
種類
入力nazo5
byte10111213
bit08008108208308408508608708808908a08b08c08d08e08f09009109209309409509609709809909a09b09c09d09e09f
種類
入力timer0VCount
byte14151617
bit0a00a10a20a30a40a50a60a70a80a90aa0ab0ac0ad0ae0af0b00b10b20b30b40b50b60b70b80b90ba0bb0bc0bd0be0bf
種類
入力(定数)MAC5MAC6
byte18191a1b
bit0c00c10c20c30c40c50c60c70c80c90ca0cb0cc0cd0ce0cf0d00d10d20d30d40d50d60d70d80d90da0db0dc0dd0de0df
種類0000000000000000
入力MAC(1,2,3,4) xor GxStat xor Frame
byte1c1d1e1f
bit0e00e10e20e30e40e50e60e70e80e90ea0eb0ec0ed0ee0ef0f00f10f20f30f40f50f60f70f80f90fa0fb0fc0fd0fe0ff
種類
入力曜日
byte20212223
bit10010110210310410510610710810910a10b10c10d10e10f11011111211311411511611711811911a11b11c11d11e11f
種類0000000000
入力(定数)
byte24252627
bit12012112212312412512612712812912a12b12c12d12e12f13013113213313413513613713813913a13b13c13d13e13f
種類00000000000
入力(定数)
byte28292a2b
bit14014114214314414514614714814914a14b14c14d14e14f15015115215315415515615715815915a15b15c15d15e15f
種類00000000000000000000000000000000
入力(定数)
byte2c2d2e2f
bit16016116216316416516616716816916a16b16c16d16e16f17017117217317417517617717817917a17b17c17d17e17f
種類00000000000000000000000000000000
入力キー入力(定数)
byte30313233
bit18018118218318418518618718818918a18b18c18d18e18f19019119219319419519619719819919a19b19c19d19e19f
種類0010110000000000000000
入力(定数)
byte34353637
bit1a01a11a21a31a41a51a61a71a81a91aa1ab1ac1ad1ae1af1b01b11b21b31b41b51b61b71b81b91ba1bb1bc1bd1be1bf
種類10000000000000000000000000000000
入力(定数)
byte38393a3b
bit1c01c11c21c31c41c51c61c71c81c91ca1cb1cc1cd1ce1cf1d01d11d21d31d41d51d61d71d81d91da1db1dc1dd1de1df
種類00000000000000000000000000000000
入力(定数)
byte3c3d3e3f
bit1e01e11e21e31e41e51e61e71e81e91ea1eb1ec1ed1ee1ef1f01f11f21f31f41f51f61f71f81f91fa1fb1fc1fd1fe1ff
種類00000000000000000000000110100000
(厳密にはメッセージデータは52(0x34)byte目までだが、細かいことは気にしない。)

表の種類欄で、「変」は変数(求めたい値)、「媒」は媒介変数(実行時に値を代入する)、「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上位
byte00010203
bit000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
種類
出力初期seed下位
byte04050607
bit202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f
種類
出力(未使用)
byte08090a0b
bit404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f
種類
出力(未使用)
byte0c0d0e0f
bit606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f
種類
出力(未使用)
byte10111213
bit808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f
種類

表の種類欄で、「媒」は媒介変数(実行時に値を代入する)、「任」は任意の値である。
この表より、出力データ160bitのうち64bitが媒介変数、96bitが任意の値だと分かる。
入力データと同様に、160個のbool型変数 y_{00},y_{01},¥dots,y_{9f} を、上の表の各bitに順に割り当てることにする。


ここからは数式を使った話になるが、その前に使う記号の確認をしておく。
SHA−1の計算過程で必要な演算子は、論理積論理和排他的論理和,論理否定,算術和,循環シフト,および代入の7種類である。
ここでは、それらを次の記号を使って表すことにする。(別記事に移動しました。→id:plusletool:20130427:p2


さて今、SHA−1への入力値 x_{000},x_{001},¥dots,x_{1ff} と、それに対するSHA−1の出力値 y_{00},y_{01},¥dots,y_{9f} の関係について考える。
いかに計算過程が複雑なSHA−1とはいえ、やっていることは論理積論理和排他的論理和,論理否定,算術和,循環シフト,代入の有限回の組み合わせにすぎない。
よって、その計算過程を全部まとめて1つの関数とみなして、次のように表すことができる。

(*1)
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)
……
y_{9f} = SHA_{9f}¥left(x_{000},x_{001},¥dots,x_{1ff}¥right)

(※関数 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)
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)
……
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)
……
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)


この式(*2)を変形していき、最終的に次のような形にすることが目標である。

(*3)
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)
……
u_{53} = func_{53}¥left(p_{1},p_{2},¥dots,p_{240},s_{1},s_{2},¥dots,s_{64}¥right)

つまり、未知変数 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)
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)
……
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)
……
v_{j_{96}} = SHA_{9f}’’¥left(p_{1},p_{2},¥dots,p_{240},u_{1},u_{2},¥dots,u_{53}¥right)


次に、式(*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)
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)
……
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)
……
0 = f_{64}¥left(p_{1},p_{2},¥dots,p_{240},s_{1},s_{2},¥dots,s_{64}¥right)

これを(*4)の方程式の下96本の u_{1},u_{2},¥dots,u_{53} に代入して整理すると、次のようになる。

(*6)
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)
……
v_{96} = f_{160}¥left(p_{1},p_{2},¥dots,p_{240},s_{1},s_{2},¥dots,s_{64}¥right)


ここで改めて、式(*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から、起動日時とキー入力を逆算する式
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)
……
u_{53} = f_{53}¥left(p_{1},p_{2},¥dots,p_{240},s_{1},s_{2},¥dots,s_{64}¥right)

(*B)nazoなどのパラメータと初期seedが満たすべき関係式(解の存在条件)
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
……
f_{64}¥left(p_{1},p_{2},¥dots,p_{240},s_{1},s_{2},¥dots,s_{64}¥right) = 0



以上で、SHA−1の計算過程である式(*1)から、それを逆算する式(*A)と、解の存在条件(*B)に変形できた。
式中に使われている媒介変数の数は304個で、関数 f_{i} の内部では算術和や論理積を含むので、最大で304次の項を含むことになる。
最悪のケース(0次から304次まですべての項を含む積和標準系の式)では、項数は 2^{304} にもなり、演算回数は論理積 ¥sum_{i=0}^{304}¥left(i-1¥right)¥cdot{}_{304}C_{i} 回、論理和 2^{304}-1 回、論理否定 ¥frac{1}{2}¥cdot¥sum_{i=0}^{304}i¥cdot{}_{304}C_{i} 回(期待値)にもなる。
これほどの計算に要する時間と、逆算ではなく順当に総当りで計算するのに要する時間とでは、どちらの方が短いのか? ……という問題があるが、それはまた別の記事で書く(予定)。
それよりも、後回しにしていたもっと重要な問題について考えなければならない。
つまり、

(*4)再掲
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)
……
s_{i_{64}} = SHA_{3f}’’¥left(p_{1},p_{2},¥dots,p_{240},u_{1},u_{2},¥dots,u_{53}¥right)

u_{1},u_{2},¥dots,u_{53} について解いて

(*5)再掲
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)
……
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)
……
0 = f_{64}¥left(p_{1},p_{2},¥dots,p_{240},s_{1},s_{2},¥dots,s_{64}¥right)

の形に変形することが本当に可能なのか、ということだ。
また、ただ変形するだけではなく、プログラムに実装しやすいような変形方法を考えなければならない。
そして、それを考えるためには、そもそも

(*1)再掲
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)
……
y_{9f} = SHA_{9f}¥left(x_{000},x_{001},¥dots,x_{1ff}¥right)

関数 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} は任意の値を取ることができるのではなく、いくつかの拘束条件を満たす値でなければならない。
見方を変えれば、この拘束条件は元の連立方程式の解の存在条件とも言える。
このことついては、別の記事で(気が向いたら)書く。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/plusletool/20130427/p1
Connection: close