ZIP Attacks with Reduced Known-Plaintext を読む

1.1 The PKZIP Stream Cipher

{
    unsigned short temp;
    key0 = crc32 (key0, pt);
    key1 = (key1+LSB(key0)) * 0x08088405 + 1;
    key2 = crc32 (key2, MSB(key1));
    temp = (key2 & 0xFFFF) | 2;
    return LSB( (temp * (temp ^ 1)) >> 8);
}

CRC32 の定義
crc32(32bit crc, 8bit b)
  rerutn ((crc >> 8) ^ crctab[LSB(crc) ^ b])

crctab[a ^ b] = crctab[a] ^ crctab[b]

crc32(a,b) = (a >> 8) ^ crctab[LSB(a) ^ b]
                   = (a >> 8) ^ crctab[LSB(a)] ^ crctab[b]
                   = crc32(a,0) ^ crctab[b]

        key0 の 8bit(LSB) が key1 に
LSB(crc32(key0,0)) ^ LSB(crctb[p])

key1 の 8bit(MSB) が key2 に
key2 が 出力に影響する。

3 Divide and Conquer

key01 を推測するのに key00 の 16bit は必要ない。
LSB(key01) を推測するためにLSB(crc32(key00,0))を推測する。

LSB(key01) = LSB(crc32(key00,p1))
           = LSB(crc32(key00,0)) ^ LSB(crctab[p1])

MSB(key11) = MSB( (key10 + LSB(key01)) * 0x08088405 + 1 )
       (A) = MSB( LSB(key01) * 0x08088405) +
       (B) MSB( key10 * 0x08088405) + possible carry bit.

(B) の 9bit を推測する。

key2i 2..15(14bit)を推測

si+1 と key2i の 10..15(6bit) で
key2i の 2..9(8bit) を参照する。
256*64バイト の preimage table

key2i の 14bit で si+1 の 8bit を作る

crc32(key20,0) の 10..15(6bit) を推測
s2 preimage table crcab[MSB(key11)] で crc32(key20,0) の 2..9(8bit) を推測

key21 = crc32(key20,MSB(key11))

preimage から key2 を推測
key1 を推測
key0 を推測

2^63 個のキー

[ 固定リンク ] [ トラックバック(818) ]