使用"旁通道攻擊"攻擊腳踏車

Bob 和Alice 兩位都是T大的學生，Alice 暗戀Bob 已久，發現Bob 下課在校園間移動，都騎著他那台紅色小腳踏車。Alice 於是心生一計：如果她偷走Bob 的腳踏車，Bob 下課找不到腳踏車的時候，她就能騎著腳踏車出現在Bob 身邊，好心載他一程，以拉近兩人的關係
問題是Bob 的腳踏車用了密碼鎖，想要破解或試出密碼，或找到大剪剪斷塑膠的部分都不是那麼容易的事，那到底該如何解開密碼鎖，偷走腳踏車呢？

這時Alice 靈機一動，想起上週在聽密碼學導論時，教授提到有關旁通道攻擊（Side Channel Attack, SCA）的內容，為何不能利用旁通道攻擊來破解密碼鎖呢？
所謂旁通道攻擊，就是不正攻防禦系統中最強的部分，像是用暴力法直接試密碼鎖10,000 種不同的組合，或者拿大剪直接斷塑膠的部分，前者要試很久，後者有點太明目張膽了；反之旁通道攻擊從每次加解密時流出來的資訊，推敲出金鑰全部或部分，從1996年Kocher那篇 Timing attacks on implementations of Diffie-Hellman發表至今，無論從電源消耗、近場輻射，甚至聲音，旁通道攻擊攻破無數數學上完全的密碼系統，那麼腳踏車呢？

前情提要到此：
理論還滿簡單的，密碼鎖上有4個0-9的數字，上鎖之後要把數字撥亂，其他人才猜不到真正的密碼；可是，撥亂這件事－或稱亂數產生器－卻不一定有被認真對待。
Bob 上鎖時，可能大手一轉就以為鎖好了，很可能4個數字轉盤裡面有2到3個都是一起轉的，或者因為Bob 是右撇子，都用右手向右撥，也因此，只要持續記錄Bob 每次鎖車時轉盤上的數字，就可以推測出密碼的數值
這是Alice 努力不懈每天記下Bob 停腳踏車後密碼鎖的數值：

1752 4852 5941 5652 4869 4830 5941 4841

其實結果還滿明顯的，轉的數值真的跟習慣有關，甚至多次轉出一樣的數字，我光用看的都能看出來ABCD 四個數字間的關係，AB 差4 (B-A)，CD差7 (D-C)，BC 比較看不出來，但算眾數的話是差8，如果有更多筆資料就能更精準的看出關係，這可能是我習慣上會四個一起轉之後，CD兩位再轉一些，導致BC差值通常不固定。
由上猜測，腳踏車的密碼可能是 0429，以及四個數字一起轉的其他結果：1530, 2641……9318，很不巧，0429真的是Bob 的腳踏車鎖密碼。

試過其他解法，例如假設真正的密碼是ABCD，觀察到的數值是A’B’C’D’，個別數字的距離：X-X’ 應該會相當接近才對，我寫了個小程式去算 0000-9999 取 X-X’ 的標準差，然後算所有測試結果的標準差總合，愈小的愈可能是答案。
後來發現這招沒用，例如密碼0000 被轉成 6688，這樣比起正確的密碼0000，0011這個錯誤解在這個算法下就會勝過0000。

無論如何，記錄了8組數據就能把10,000組密碼組合縮減到10 組，旁通道攻擊果然有用啊。
可惜後來Bob 發現腳踏車不見了，就跑去借公共腳踏車(NT)Ubike，功敗垂成不禁讓Alice 感嘆：偷得走心上人的腳踏車，卻偷不走他的心。

反思：
* 人類其實不是一個很好的亂數產生器，就如上面的例子，轉盤轉的數字看似亂數，其實隱藏了內部規則，就像現在請人在1到100中選一個數，大家通常認為人腦選的數字是亂的，其實受限一些人腦的想法，我想結果應該也不是<真的>亂數；另外，依照人的習慣，轉出來的數字，通常也不會跟原有密碼重複，由這也會流出一些線索。
* 如果要比較安全的腳踏車鎖，請使用鑰匙鎖，密碼鎖上鎖都該用真的亂數產生器產生密碼，或者每次轉密碼不能偷懶，一格一個好好的亂轉。
其實，每次上鎖都把它轉成 0000 也是不錯防範方式XD
* 其實我不確定有沒有更好的攻擊方法，只能從數字的規則中推敲出密碼間的關係，但資料量一多關係就很明顯了，這也是統計的效應：資料的數量才是重點，就算裡面垃圾很多，透過大量資料也能篩出有意義的資訊，某種程度上來說，統計或Big Data 也是從垃圾裡淘出黃金，算是現代的回收業吧XD。

後記：
其實幾個月前，我鑰匙型的車鎖不見了，換了新的密碼鎖，多轉了幾次之後，想到這個點子。本篇文中的例子，都是這一個星期來，每次停腳踏車時就記錄一次，累積一個星期的資料就猜出密碼了。當然文中提到的密碼也是真的，只是我現在已經換了一個，所以大家要是看到我的小紅，就別用文中的密碼去試了。
也要提醒大家，如果看到有人在看你腳踏車密碼鎖，而且過幾天又看到他，很可能他就是要對你的腳踏車實施旁通道攻擊，腦袋中一定響個警鈴：「噹噹，你的腳踏車正遭受攻擊」，一定要記得換個密碼。

不過話說回來，我猜直接搬走腳踏車比這個方法容易多了。

亂玩雜湊函數

當你學密碼學的雜湊函數時，你爸爸媽媽爺爺奶奶叔叔嬸嬸舅舅阿姨，就連你男朋友女朋友啊不對我沒有女朋友全部都會跟你說：好的Hash 帶你上天堂，不好的Hash 帶你住套房不要用安全性不足的Hash，可是說到不好的Hash 到底會怎麼樣，卻也沒人說個準。

我決定來做個試驗，來玩一下安全性不足的Hash 究竟會發生什麼事情？

首先是實作iSHA1，名稱來自 In-Secure Hash Algorithm，i之所以要小寫是為了潮偽裝成蘋果公司最新的產品，輸出長度為32 bits ，因此利用生日攻擊法尋找這個Hash 的碰撞只需要2^16 的計算複雜度。
實作就懶得實作了，自己設計hash function 有夠麻煩，拿個SHA1 然後只取前32 bits 就好了啦XD

大概就像這樣：

iSHA1.hexdigest():
    sha1.hexdigest()[:8]

現在有了這個就可以玩很多亂七八糟的東西啦，例如破密碼，我們選用一個最簡化的保存密碼方式：把輸入的密碼經過iSHA1 之後保存，因為iSHA1 的size 不夠，因此比較容易找到碰撞，即便如此應該還是比明文保存好一點，至少不會一眼看出密碼是啥XD

我們選一個強式密碼：

Y@kum0Yuk@r!G@D@!Suk!

經過iSHA1，它會變成：

0e14c36a

超短的對不對，為了這個我寫了個網頁
http://isha1-1338.appspot.com/attack1
大家可以在上面找碰撞，我還懶得找，但相信不會有SHA1 這麼困難…個屁

我用了以下的 python code，為了可以輸入還是用string.printable，而非跑全部的可能性：

for length in range(10):
  print("test string with length %d" % (length))
  for s in itertools.combinations(string.printable, length):
    h = iSHA1.iSHA1().update("".join(s).encode('utf-8')).hexdigest()
    if h == answer:
      print("Collision found: %s" % "".join(s))

跑了至少1 hr 才跑出一個7 characters length 的collision

well 我這是用Python ，如果用C 來試驗也許就先快100 倍，再加上類似Hashcat 這樣的專用軟體，還能擴增128 張GPGPU lolololol，可以衝到37336 Mh/s：
https://hashcat.net/oclhashcat/
至少這是個例子，無論用了多強的密碼，Hash 爆了還是沒用，噗滋一下密碼照樣給人試出來，現在SHA1 已經出現可行的攻擊，意即它的強度已經達不到理論上2^80 的安全強度，雖然這不表示SHA1 變得多不安全，不過實務上一般都建議改用SHA2 家族的雜湊函數以保證更高的安全強度。

雜湊、訊息鑑別碼與簽章

最近剛翻完Understanding Cryptography這本書，內容真的是淺顯易懂，每章的最後也都會附上相關的參考跟深入研究可讀的參考資料，是本適合當入門的好書，看完之後，想通了雜湊、訊息鑑別碼與簽章三者的差別，在這裡筆記一下，這三個對應的英文分別是 Hash, Message Authentication Code (MAC) 和 Signature，都是訊息傳遞時，用來檢查訊息內容有無「問題」的演算法，三者相似但有些許不同，主要是要對付的問題不一樣。

當我們要傳送一大筆資料時，我們必須要驗證傳送的正確性，沒有錯誤或遭人修改，最基本的就是使用Hash 雜湊，概念就是把傳送端的資料攪一攪，吐出一段代表這份資料的值，接收端再把收到的資料攪一攪，看看出來的值是否一樣。

我們要求Hash 至少要有這些特性：
* 任意長度的輸入，固定長度的輸出
* 要快：如果傳資料要花一秒，算Hash 要十秒，有人要用嗎
* 輸入少量——即便是一個bit 的變動——也應該要讓output 完全不一樣
拿果汁機當比喻，好的果汁機要能攪拌任何輸入的食物並給你一杯新鮮可口的果汁，還要很快攪好，最後，當你攪蘋果汁時加了一些些咖哩，它也要把咖哩分子均勻散佈到每一口蘋果汁裡，打成一杯美味的咖哩蘋果汁(X

另外有Hash三個安全性的要求：
* 從輸出推不出輸入(preimage resistance)
* 給定一個輸入和它的輸出，攻擊者無法產生另一個輸入有同樣的輸出(second preimage resistance)
* 攻擊者無法產生兩個輸入有同樣的輸出(conllision resistance)

知名的Hash如md5, SHA-2，在傳檔案不希望有毀損時，用這些雜湊驗一下是不錯的檢查。

要注意的是，hash 的演算法都是公開的，所以如果有心人Oscar偽造一筆資料跟它的Hash值送給接收端，這筆資料會被誤信為真的資料，Hash 無法對付有心的第三方偽造的攻擊，要對付這種狀況就需要MAC。
MAC和hash 一樣，對一組輸入產生代表的輸出，但MAC除了Hash 的特性外，還會要求一把key，在共同擁有這把的key 的雙方，能驗證訊息完整(integrity)，也能確定訊息無法被沒有key的第三方偽造，因此MAC 有時又稱為Keyed Hash Function。
再拿果汁機當例子，共有的key 就像某種獨門配方…像金克拉吧，攪咖哩蘋果汁的時候放點金克拉進去，只有用了金克拉才能吸收土壤兩米下的氮磷鉀攪出金克拉風味咖哩蘋果汁，其他人就無法偽造出這獨特的金克拉風味。

但再進一步，MAC並不提供”不可否認性”，MAC雙方共有這把key，他們都可以產生可被驗證的MAC訊息，這就像有人可以故意打出「有杏仁味的金克拉風味咖哩蘋果汁」然後說是我打的，那我不是冤大頭？這時我們就需要簽章Signature：
簽章跟MAC差異不大，只是我們把hash value 用非對稱演算法的私錀加密過，並公布它的結果，這樣所有有公錀的人都能驗證這份資料是我簽的，卻無法偽造這份簽章；另一方面，我也無法否認這份資料是我簽的，這就是”不可否認性”，這在晶片卡、網路交易上有極大的應用。
就像攪果汁的時候，吐點口水進去，所有人都能驗我的DNA，證實是我攪的果汁；但DNA就只有我有，任何人都無法偽造。

簡而言之，如果你拿訊息過來攪一攪，那是雜湊；攪一攪的同時加上一把通常是對稱性的金錀，這變成MAC；如果產生的過程用上你的私錀，用非對稱加密演算法處理過，就成了簽章。

Coursera cryptography 1

在陰間為了殺時日，總要找點書來看，因為自知不能看一些會變的東西，例如程式Rust；這種東西等我返陽搞不好都翻了兩翻，現在我主力放在兩個方向，一是修coursera 的cryptography 課程，二是閱讀Logan 大大推薦的Enginnering a compiler，前一個cryptography 1 課程剛結束，這裡記錄一下心得。

這門課不算太難，帶過密碼學上幾個重要的概念：Stream cipher, Block cipher, Asymmetirc cipher，人人都怕的數學只在非對稱式加密前帶過一些。
上課的內容還有授課方向，跟這本<understanding cryptography>非常相似，打書名就能找到這本書的全文電子檔；兩者搭配來看，可以補線上課程內容的不足。

程式作業有6題，只有一個是要求用現有的AES lib 來實作CBC 跟CTR 加密，另外五個都是利用已知的漏洞去破解某些密文，就跟教授上課不斷提醒的：”Don’t invent your own ciphers or modes”，作業藉實際攻擊讓大家了解，即使數學理論上安全的加密，在不正確的實作下，仍會導致安全性流失，寫程式會需要一些底子，不過只要會python 或C++應該不算太難。
從程式作業，真的可以體會密碼的設計是一門高深的學問，倒也不是說不要去實作和修改，否則一些知名的lib 像openSSL是誰在維護？而是要先學好基本概念，了解可能的弱點與攻擊方式，多和大家討論分享實作方式，有討論才有進步。

俗話說得好：「三個臭皮匠勝過一個諸葛亮」，密碼學因為攻擊方式千變萬化，絕非一位天才能掌握全部面向，許多科技領域也是如此，在這個年代作為一個工程師，我認為最有效的學習是先學會基本概念，用一些簡單的例子實作驗證這些概念，再去找其他一流的project參與，之所以不要一口氣去跳進一流的project，是因為那裡一定藏了一堆實作細節，會遮掩掉基本概念；千萬不要閉門造車，分享你的想法，才有更大的進步空間。

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霧裡有幾顆是硫酸、幾顆是氫氧化鈉，他們和你的霧當然不一樣，但把兩團霧混在一起，其實這根本就沒差。