Cryptography筆記3 - stream ciphers

Stream Cipher: 用PRG改良OTP

利用pseudorandom key，而不是random key，我們可以改良OTP變成一個實際可以使用的cipher，稱為stream cipher。

首先什麼是pseudorandom generator PRG?
PRG是一個generator function G，他把seed space mapping到 key space:

例如把 s = 128 bits長度的 {0,1} string map到 n = 1G bytes長度的 {0,1}string，而且 n >>>>> s，所以G 必須是efficient and deterministic，雖然seed是random，此外output必須是"看起來random"。

我們random選了一個seed當作secret key k，然後丟入G function 當作input，ouput出一個G(k)當作OTP的key:

所以對OTP來說，Encryptor / Decryptor的定義都沒改變，變的是OTP中的key此時實際上是G(k):

要注意Stream cipher沒有達成perfect secrecy，因為seed (實際上真正的key) 的長度 < message長度。

PRG必須要Unpredictable

predictable的定義為: 如果已經知道G(k)的前面1~i bits的話，透過某種演算法可以推算出G(k)剩下的i+1 ~ n bits，則稱此PRG為predictable。

所以直覺來看，PRG肯定要unpredictable，因為某些message是有固定的prefix header的，例如mail protocol可能從"from:// .... "開始，如果attack獲得了一段cipher text c，則根據OTP的規則，只要把 c XOR 這個message的prefix header (假設長度i)，就可以得出OTP的key = G(k)前面i個bits，而又若G是predictable的話，則整個G(k)就會被推導出來!

正式的定義generator function is "predictable"，採用機率的觀點如下:

白話來說就是: 任意選擇k from K，存在一有效率的演算法A使得A在input G(k)的前i個bits後，能夠吐出G(k)的第i+1個bits的機率，並非隨機結果，而是>=不可忽略(non-negligible)的機率: 0.5 + epsilon，此epsilon >= 1/(2^30)。

所以unpredictable就是上面陳述不成立的狀態。

舉例來說:

題目意思是說，如果一個generator G的output G(k)，把其中每個bits都XOR起來的話，結果永遠為1，試問is G predictable?

假設n = 1, XOR(G(k)) = XOR( b1 ) = 1，則b1 = 1沒有疑問
假設n = 2, XOR(G(k)) = XOR(b1 b2) = 1，如果b1 = 0，則b2 = 1，如果b1 = 1，則b2 = 0，符合predictable
假設n = 3，XOR(G(k)) = XOR(b1 b2 b3)，把 ( b1 XOR b2 ) 看成一組的話，則跟n=2的case一樣，且之後 n>= 4也都依此類推，都能推論出G(k)第 n個bit

所以此generator G是predictable!

某些weak PRGs，絕對不要拿來當作cryptography用途，例如glibc random()，謹記謹記!