Cryptography筆記4 - Attacks on Stream Ciphers

Attack 1: Two-time pad!

"one-time" pad顧名思義就是一次性使用的pad (或是說key/seed)，只能用來enrypt一個message，如果用第二次在不用的message上的話，有危險!

理由很簡單，如果attacker同時拿到了兩個cipher text，假設他知道pad是一樣的:

c1 XOR c2 = (m1 XOR PRG(k)) XOR (m2 XOR PRG(k))
= m1 XOR (PRG(k) XOR PRG(k)) XOR m2
= m1 XOR 0 XOR m2
= (m1 XOR m2) XOR 0
= m1 XOR m2 //因為任何東西XOR 0就是其本身值

對英文來說，因為redundancy太多，所以如果知道兩個plaintext 的XOR結果，是可以回復這兩個m1 m2的!

802.11b WEP (2-time pad!!)

其實WEP設計者是有注意到one-time pad不能用同一個key去encrypt兩個message，所以client 要跟wifi AP講話時，會prepend一個24-bit string IV到兩端都知道的key上，問題是IV只有2^24種可能，所以將會在超過2^24個frame之後重複，此時就變成了2-time pad!

另外由於丟進PRG的string其實都有相同的suffix，也就是k (104 bits)，而且某些不好的implementation把IV用簡單的序號(從1開始往上累加1，換句話說IV無隨機性)，而WEP所使用的PRG稱為RC4又對這種很接近(closely related)的key string缺乏安全性，現在attackers只要約40000 frames的擷取就能完整還原secrect key k!!!!

另一個one-time pad誤用是在encrypt disk，由於檔案存在磁區相同，如果每次都用同樣的key encrypt，attacker事實上很容易就拿到兩個編輯前後同樣磁區的cipher text，這樣又有可能洩漏原本的file content。

Attack 2: 竄改cipher text

攻擊者無法得知 m XOR k的內容，但是他可以竄改:
(m XOR k) XOR p

當解密方解密時:
((m XOR k) XOR p) XOR k
= m XOR p XOR 0
= m XOR p

解秘方無從得知cipher text已經被竄改了!

舉例來說"Bob"要怎麼竄改成"Eve"? (假設知道Bob出現在cipher text何處)
假設"Bob"被encrypt成c1
令p = "Bob" XOR "Eve"
如果把某已知位置的c1換成 c1 XOR p
則解碼方解碼時會得到 "Bob" XOR ("Bob" XOR "Eve") = "Eve" (見上方算式)