Cryptography筆記5 - real-world Stream Ciphers

CSS Broken!!

CSS是一個stream cipher，已經被破解的不要不要的。首先介紹LFSR(linear feedback shift register)，CSS是建立在此機制上(使用了2個LFSR)。

每一個register cell是一個bit，每一個clock cycle，register會把內容shift right移出register，而最左邊的bit就塞入某幾個cell的XOR結果，這樣就是一個map seed space to key space機制。

initial seed就是LFSR的initial state。
GSM也是stream cipher，用了3個LFSR，而藍芽用了四個，但都被破解了，不安全!

CSS Attack!!

CSS LFSR seed只有40 bits，先天不良的原因是因為美國禁止出口超過40 bits crypto algorithms!(當時)。

CSS用了兩個 LSFR，一個17 bit，一個25 bit，初始值如下:
1 || seed的前兩個bytes => 17 bit LFSR
1 || seed的後三個bytes => 25 bit LFSR

CSS PRG: 剛說過每個cpu cycle會shift right 1 bit，經過以下步驟，8個cycle之後就會形成1 byte key:

我們已經知道MPEG的檔頭是什麼，舉例來說相當於知道20bytes的plain text m，假設加密過的影片前20 bytes為c，則由於:
c = m XOR PRG(seed)
=> PRG(seed) = c XOR m

所以我們可以知道前20bytes的 PRG(seed)，而這正是上面的兩個LFSR產出來的20 bytes，所以我們如果暴力去try 2^17種 可能在 17-bit LFSR的initial state話，做20個bytes p出來，則利用PRG(seed) - p 的逆向+mod256 的算法可以算出每一種搭配17-bit LFSR的25-bit LFSR的可能產出的20 bytes q。

接下來有個關鍵點，就是有簡易的演算法測試q 是否是25-bit LFSR所產出! (詳情不知)
但是一但此檢驗成功，代表我們找出了兩個LFSR的initial state，等於seed洩漏了。

Modern Stream Cipher:eStream

Salsa! 有興趣可以多了解此eStream open source project。