Cryptography 1：攻擊stream cipher

密碼學中，有一種極簡的密碼，就是stream cipher(流加密XD)，對各式的明文，隨機產生一組和它一樣長的key並和明文xor 起來，就是一個夠好的加密，只要該密鑰是隨機產生，如同上一篇所說，密文也會夠隨機。
按：事實上我是聽課才知道這種加密，不像強者我同學曾奕恩大大，完全無師自通，看來我該讓賢了。
在實務上，通常不會用真的random密鑰，因為這會讓密鑰的長度要跟訊息一樣長，不實用，你能想像要先交換一組GB等級的密鑰嗎？我們會用pseudorandom generator，把短密鑰生成為長密鑰，來解決這個問題。

這個加密系統有一大弱點，就是密鑰是一次性的，若一把密鑰重覆使用，而密文遭人攔截，則攻擊者可以利用：

c1 ⊕ c2 = (m1 ⊕ k) ⊕ (m2 ⊕ k) = m1 ⊕ m2

若明文是以ascii 儲存，m1 ⊕ m2 已經有足夠資訊讓人猜出內容。

例如，明文常有的space，ascii 是0x20或32，它跟英文字母xor 起來的結果，大多會落在大小寫轉換的英文字母範圍內，我們用python 來試試：

uppercase = list(range(65,91))
lowercase = list(range(97,123))
msg = uppercase + lowercase
print("".join([chr(c ^ 32) for c in msg]))
print("".join(chr(c) for c in msg))

會得到：

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

其實它X的根本就是一個對上一個，這和一般最可能發生的字母xor 字母產生的結果相差頗大，例如a xor z = 27還在不可視字元範圍內，所以如果xor 的結果落在字母內，很可能表示c1, c2中有space。
我們可以先產生一個字典，以常用ascii 和space xor的結果為鍵，以便用來反查該ascii 的值：

xorSpace = {}
for c in msg:
    xorSpace[c^32] = c

然後對各截到的密文，假設是c0, c1 … cn，c0 xor c1 中存在字典中的字元位置，就有可能是c0或c1在這裡有space，將這些位置存下來，跟c0, c2 有space 位置取交集，就能得到c0中space的位置了。

def listspace(c0, c1):
    spacepos = []
    for idx, chars in enumerate(zip(c0, c1)):
        if (chars[0] ^ chars[1]) in xorSpace:
            spacepos.append(idx)
    return spacepos

可以用

c01 = listspace(c0, c1)
c02 = listspace(c0, c2)
list(set(c01).intersection(c02))

輕鬆得到交集結果。

有了space 位置，我們就可以把攻擊對象的字元，一個一個和space 位置xor ，再用先前建的字典轉出可能的字串，例如我們隨便轉一組密文的結果：

Yolal###,##a ##rb###. #eazest xwrcy#c#n th# worl#.

亂碼(我讓它輸出#表示查不到該xor的結果)還不少，但一些字元已足夠我們去猜出明文，例如最後面的the world.；這還只是用只有一組密文的space 位置當標準，如果我們測試所有密文的space位置，結果的開頭如下，每行密文該字元表示和不同密文測試的結果，例如第一行表示第一個字元和另外三個密文測試，兩個沒找到字元，一個轉出Y：

"##Y"
"##o"
"d##dl"
"aaa"
"l"
"#e,,##,#"
"ee#"
"#"
"i,,"
"####s###"
"tt #"
"a"
" "

已經看得出明文大概是’yodalee is a’，如果再用這明文m0 = m1 xor c0 xor c1，可以試著解其它的明文，找出更多粢訊把亂碼的部分消掉，完成攻擊。
例如用下面這段簡短的python code，就可以快速測試已知答案的話，其他密文的內容：

ans0 = "xxx" print("".join([chr(ord(c) ^ c0[i] ^ c1[i]) for i, c in enumerate(ans)])

附帶一提，我加密的訊息是：

"Yodalee is a garbage. Weakest person in the world."

其實不算什麼祕密XD。

Cryptography 1：密碼學裡的隨機

小弟最近消失了好一段時間，都沒在更新文章，其實小弟是掉到陰間去了，在陰間時間變很少，都不寫code（也沒電腦Orz），也不再看相關的東西，例如rust 的文件了，因為我知道一年後出來，rust-lang 搞不好都翻了兩翻，而且看了也不能直接練習，看了等於白看。
最近把時間花在一些比較不會變的東西，像是計算理論、密碼學、數學等等的東西，請我的好友強強林寄列印的書給我，利用放島休的時間聽coursera 上stanford 的cryptography，就算在陰間還是要定期充電，不然出來都變白痴了（雖然說本來就非常弱）。

下面這是聽密碼，關於其中隨機這件事的一些體悟：

密碼學的重點，其實就在「燙」…啊不對，是在「隨機」(random) 兩字，普通的訊息加密變成隨機，讓竊聽者猜不出訊息的內容，才能達成密碼學最重要的目的。
在密碼學裡很常看到xor，就是因為xor 的特性：當你把任何東西X跟隨機的訊息Y xor 起來，出來的東西的機率分佈會跟Y 一樣隨機，因此只要準備一個夠好的Y夠隨機，一個xor 就能把X 給加密好，所以問題就出在Y到底夠不夠隨機上。
當然我們可以用硬體雜訊產生器之類的東西，製造一個真隨機的來源當作密碼，但這在密碼學上不實用，如果是真隨機，表示加、解密雙方無法重現這個密碼，就無法加、解密啦；因此我們需要pseudorandom(偽隨機)，用有規則、可重現的方式製造一個很像隨機的東西。

無論是pseudorandom generator/function/permutation，都是設法設計一個夠亂的變法，並讓它們儘可能像random，並讓攻擊者在有限的運算資源限制下，分不出兩者的差異。但總歸來說，兩者還是不同的，以pseudorandom generator 為例，我們會設計很多統計上的測試，像是 0, 1 的數量不能差太多；不能有太長的0序列……讓這些測試無法分出兩者的差異。

千萬不要小看隨機這件事，小小的不隨機，都能讓攻擊者找出一絲絲突破的空間，例如Caesar cipher 隨機性不夠，用頻率攻擊法可以快速破解；enigma 只因為輸入跟輸出不會是同一個字，也能利用這點，配合電子計算機在幾十分鐘內破解；課程中有個例子是DES 有一個問題，可以用線性運算找到一個發生率小於1/2^21 不隨機事件，利用這點，就足以大幅削弱DES 的安全性，也就是說，我們發現這個pseudo-random不是真random，用這個運算預測pseudorandom下一個輸出時，可以比瞎猜好1/2^21。

----

至於random跟pseudorandom是不是一樣呢？

理論上，如果給定無限多組的統計檢定，終究可以驗出真隨機和偽隨機的差異，但同樣的在"有限的運算資源"限制下，能進行的終究只有有限組統計檢定（這個教授倒是有提到，如果P=NP的話，我們就可以……），也就是因為"有限的運算資源"限制，保護了現行的加密系統不被輕易破解。

以真實例子來看，我們可以斷言，pseudorandom不會出現全0這樣罕見的序列，但這樣的序列在random 的狀況是確確實實會發生的，所以pseudorandom 和random 真的有差，但這差異的發生率之小，除非我們能窮盡所有檢查，才能檢出這種差異。
我們在做的事情，就像往霧裡一指，說：來，這是random的產出，然後我們放出另一團pseudorandom 霧，自問：你覺得你這團pseudorandom霧和這random霧像不像？有限的檢查下，我們可能只能驗一下外觀，兩個當然一樣；但給我無限的檢查，會發現random霧裡有幾顆是硫酸、幾顆是氫氧化鈉，他們和你的霧當然不一樣，但把兩團霧混在一起，其實這根本就沒差。