pkcrackの仕組み
知ってもCTFにはあんまり役立たなさそう
論文とスライドで上位ビットが逆なので注意(桁の大きい方がbit 0として進めます)
…流石にそれは雑すぎるので、斜め読みしてまとめてみます
一旦圧縮のことは置いておいて、暗号化だけに注目します
前提知識
bit, byte
鍵(パスワード)、平文、暗号文
ビット演算
A OR B→A | B
A AND B→A & B
A XOR B→A ^ B
NOT A→~A
と表記します
論文をまとめてみる
一般的に使われるZIPの暗号化方式はPKZIPというものです
1バイトずつ処理するので「ストリーム暗号」に分類されます
内部に32bit = 4byte長の鍵を$ key0, key1, key2の3つを持っています
定義
平文を$ P、暗号文を$ Cとします
$ P_i(Pのiバイト目)を暗号化する鍵を$ key0_i のように書きます
コード中では$ P_iはP[i]のように書きます
process_keys(key)関数
パスワードから内部で利用する鍵を生成
lenはパスワードの長さ(byte)
1-lenはマイナスだけれど、まず$ key0_{-len}に定数を入れて
$ key0_{-len+1}, key0_{-len+2} ... $ key0_{-len+len} = key0_0 を漸化式っぽく求めていくイメージでOK
$ key1, key2, key3も同じです
この処理を逆に行えばkey0, key1, key2からパスワードが求められる!
code:text
function process_keys(password, len) {
for i in 0..len {
update_keys(-len+i, passwordi) }
}
update_keys(i, char)関数
byte単位で暗号化するときに、平文の一部を使って鍵をコロコロ書き換えます
$ key0, key1, key2, chrから8bit = 1byteの$ key3を生成
code:text
function update_keys(i, chr) {
key0i+1 = crc32(key0i, chr) key1i+1 = ((key1i + LSB(key0i+1)) * 134775813 + 1) % 2**32 key2i+1 = crc32(key2i, MSB(key1i+1)) tempi+1 = (key2i+1 | 3) & 0xffff key3i+1 = LSB((tempi+1 * (tempi+1 | 1)) >> 8) }
crc32(temp, i)関数
その名の通りCRC32を計算します
CRC32とは誤り訂正に使われるsomethingです
code:text
function crc32(temp, i) {
t = temp ^ i
...ごにょごにょ...
}
事前にcrc32(0, i)の対応をとって表として保存しておきます(iは1byteなので0~255)
繰り返し計算しなくて済むように
逆に使えば、CRC32からtempを求められる→この表をCRCinverseとでも呼ぶことにします
また時間あったら補足書いときます
暗号化・復号
code:text
function encrypt(P, len) {
for i in 0...len {
}
return P0..11 + C // 先頭に平文の12バイトを付け加える }
function decrypt(C, len) {
for i in 0...len {
}
return P12.. // 最初の12バイトを取り除く }
ここで、$ C_i = P_i \oplus key3_iより$ key3_i = P_i \oplus C_i
update_keys関数では「$ key0, key1, key2, chrから8bit = 1byteの$ key3を生成」している
ここで$ chrは$ P_i
update_keys関数は平文の長さだけ実行されるので$ key0, key1, key2, P, key3に関するたくさんの等式が出てくると見ることができる
$ update\_keys(key0_0, key1_0, key2_0, P_0) = (key0_1, key1_1, key2_1, key3_1)
$ update\_keys(key0_1, key1_1, key2_1, P_1) = (key0_2, key1_2, key2_2, key3_2)
$ ...
$ update\_keys(key0_i, key1_i, key2_i, P_i) = (key0_{i+1}, key1_{i+1}, key2_{i+1}, key3_{i+1})
連立方程式のノリで解けば$ key0, key1, key2出るんじゃね?
とりあえず$ key2から考えてみよう
update_keys関数を逆に辿っていこう
code:update_keys
tempi+1 = (key2i+1 | 3) & 0xffff key3i+1 = LSB((tempi+1 * (tempi+1 ^ 1)) >> 8) 1つの$ key3から$ tempの候補は64通り考えられる
https://gyazo.com/f405abf35cdeaac3ced62b6ca062b4d0
上2つの斜線部分は同じ値、tはtempのことです
結構パソコンで図を書くのってだるいよね
ちなみにこのノートはラムー横の薬局にあったもので、10冊入りで400円です。書き心地は普通に良い
まず$ key2から$ tempに取り出されるのはbit 16〜bit 29の14bit (一番上位・左の桁をbit 0とします)
次に↑の2行目を(擬似的に)変形してみる
$ key3 = LSB((temp * (temp \oplus 1)) >> 8) より、
$ key3 << 8 = temp * (temp \oplus 1)
上の画像の3行目のようになります
tempの16bitのうち、下位2bitは$ (11)_2 \oplus (10)_2 = (10)_2で固定
上位8bitは$ key3なのでわかっている
→わからないのは残り6bit→$ 2^6 = 64通り!
このとき$ key2(=画像1行目)は何通り考えられるか?
上位の16bitが加わって$ 2^{22} = 4194304通り
こんな感じで$ key2_nと$ key2_{n+1}の一部を求めたとする
update_keys関数に戻って、$ key2_{n+1}の下位2bit以外(bit 0~bit 29)がわかっていると考えてみましょう
→$ key2_nは以下のようにも求められます(表を利用)
$ key2_{n+1} = crc32(key2_n, MSB(key1_{n+1}))
$ key2_{n+1} = (key2_n >> 8) \oplus CRCtable(LSB(key2_n) \oplus MSB(key1_{n+1}))
表を逆に使って、
$ key2_n = (key2_{n+1} << 8) \oplus CRCinverse(MSB(key2_{n+1})) \oplus MSB(key1_{n+1})
???????? あとで書き加えます
上の等式で、
左辺の$ key2_nはbit 16~bit 29がわかっている
右辺はbit 0~bit 21がわかる
$ (key2_{n+1} << 8)→上位22bitがわかる(8bit消えるので、30-8=22)
$ CRCinverse(MSB(key2_{n+1})→32bitすべてわかる
$ MSB(key1_{n+1})→$ key1についてはなにもわからないが、MSBなので上位24bitはすべて0とわかる
左辺と右辺を比べると、6bitだけ共通している
…(力尽きた)(更新しとくんで各自読んどいてください)