2015年9月17日 星期四

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。

2015年9月16日 星期三

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

2015年7月12日 星期日

使用Google App Engine 處理前端ajax request

最近在學用GAE寫一個簡單的服務,結果一直鬼打牆,這時候就要來跟我念一遍:前.端.超.難.

這次是用了google app engine來處理ajax post,送一些base64 encode後的字串把資料送到server去,用的是ajax 來達成,ajax 其實跟一般的post, get沒什麼兩樣,只是它不需要重新整理網頁,可以做到網頁內容即時的變換。

使用時先產生一個XMLHttpRequest物件,如果是IE5跟IE6就直接放棄支援(其實要用舊語法,不過…算了管它去死),並用它開啟一個GET, POST的要求,指定server 的URL跟是否同步傳送,並用send()發送
還可以用setReqeustHeader來指定post 的內容,總之有許多的設定可以選用,我用的就很直接,一個非同步的post 把資料送去server 就是
xmlhttp = new XMLHttpRequest()
xmlhttp.open(“POST”, “upload?data=” + data, true);
xmlhttp.send();

建立python handler,其實就是post handler,GAE已經把post分解為request物件,直接取裡面的內容就好了:
class UploadHandler(webapp2.RequestHandler):
    def post(self):
        data = self.request.get("data")

註:後來發現這裡的內容有錯,這樣寫會動沒錯,但因為data 仍然在open() 的URL 裡面,為GET method,會視瀏覽器遇到幾KB 的長度限制,data 很長的話應該要放在send() 裡面,才是POST method ,理論上的長度上限是 GB 等級。
上面應該要改成:
xmlhttp = new XMLHttpRequest()
xmlhttp.open(“POST”, “upload", true);
xmlhttp.send(data);

class UploadHandler(webapp2.RequestHandler):
    def post(self):
        data = self.request.body

如果要回應什麼東西給ajax,用return送回去就是了,並在routing rule 建立對應的規則:
app = webapp2.WSGIApplication([
('upload', UploadHandler),
], debug=True)

這樣一個極簡單的ajax post handler就完成了,雖然說我python後端無法解開前端javascript編碼的base64字串,不知道又是哪裡有問題,反正前端超難我什麼都不會

其他ajax請見w3schools
http://www.w3schools.com/ajax/default.asp

本文感謝世恩大神的指導。

2015年6月27日 星期六

從MoPtt事件認識自由軟體

前些陣子發生了現稱的MoPtt事件,大抵就是手機Ptt瀏覽器MoPtt會過濾掉對手JPtt的簽名檔'Sent from JPTT on',也有鄉民把MoPtt的Java 嘔吐物打開來檢視,發現的確有過濾的程式碼,只要是該文字開頭該行(還是該文?)就會直接消失:
if (!flag && !s.trim().startsWith("Sent from JPTT on")) goto _L5;
else goto _L4
_L4:
return;
_L5:

其實這件事整體來看沒什麼大不了的,會鬧大比較像是MoPtt作者危機處理的問題,大部分人擔心的,都是所謂的「見微知著」:如果今天可以屏蔽一行,明天能不能屏蔽特定詞彙?

我們可以從這個事件來認識一下所謂的自由軟體(Free Software)的理念。

自由軟體是Richard Stallman 這位Hacker所創立(我還記得在黑客列傳:電腦革命俠客誌他被列在最後一章:最後的真正黑客),最重要的GPL授權,大抵上保障了每個使用者可以自由取得軟體和它的原始碼、複製、修改、再發行的權利

現今大部分的軟體都是直接包裝執行檔,這樣的情況是可以隱藏一些實作的細節。
例如,如果我們天天使用的M$ word,裡面其實有一個監控子程式,會在存檔的時候把你打的文件保留下來,在你連網的時候傳送給政府?或者你的瀏覽器會像中國的防火長城一樣擋掉關鍵字,把你的瀏覽歷史記錄下來送給警察局?

古老一點的信件審查,我們可以透過朋友轉送;禁止公開演講我們可以選擇私下演講;可是軟體不同,它已經深入我們的生活,軟體本身隱誨、編譯過後的特性又讓逆向工程、替代方案、注意到被監控不像實體生活這般簡易,這次的MoPtt事件也是在偶然之間被糾出才會爆發,事實上這樣的行為持續了多久根本未知。
為了防止這樣的權利被軟體工程師壟斷,編輯、編譯軟體的權利應該釋放到每一位大眾的手中,所謂「陽光是最好的消毒劑」,軟體的實作應該公開在所有人面前,使用者可依自己的需要去編譯自己合用的軟體,如果MoPtt會擋掉特定詞彙,我們應該要有能力修改它,弄一個YAMoPtt(應該有人知道這什麼梗XD)
這也是為何Richard Stallman開始了gcc計劃,讓每個人都有自由的編譯器可以使用

我的同學盈志大神對這個事件的看法是這樣的:「這種程度的言論過濾我認為是可以接受的,這就跟某些電視台不報其他家電視台的新聞一樣沒什麼大不了的,況且又不是完全沒有其他的程式可以看ptt……如果只是商業利益考量我認為完全沒問題」
我的看法正好相反,這樣的行為其實跟過去報紙審查或是把書本關鍵頁面塗黑其實是類似的,而且更加可怕,以前你會看到書本是黑的,你會知道有某些東西不見了,軟體的審查卻是無影無蹤,除非,軟體自由開放大家檢驗。
誠然我們有其它軟體可以選擇,但難道我們可以說老三台時代的人們都有選擇,所以他們都有言論自由?又如何去定義「只是商業利益考量」呢?想要進入中國市場而擋掉特定文章算不算「只是商業利益考量」?我支持所謂「防微杜漸」說,自由該是努力守護的目標,而非苟且接受已有的現實,如果我們要一個理想的自由社會,我們就需要能夠讓人人守護自由的環境,無從妥協。
一個對照組就是我同學qcl做了它的qclean 插件,它會擋掉Facebook廣告,但它會公告周知實作方式:
https://github.com/qcl/QCLean
這確保了,雖然被屏蔽,我們還是能夠選擇的自由。就如在NSA事件爆發時,有人資疑windows跟openBSD裡面可能藏了FBI的後門,FreeBSD的原始碼立即被開發者們檢視,但windows的使用者卻無從選擇,他們的言論自由可能正受威脅,如果我們無法接受書籍審查、任意登門搜察,就應無法接受非自由軟體。

有了自由軟體,才能往下談資安、隱私、自由,其餘都是免談。

這也是我為何認為自由軟體的理念其實比開放原始碼更為崇高、範圍更廣,它的目的是要確保未來,每個人可以保有珍貴的言論、隱私 ,人類的歷史以成千上萬的人命作祭品召喚了言論自由,不該斷在軟體的執行檔下,如果想要進一步了解自由軟體,歡迎到自由軟體基金會和Gnu官方頁面,我一時之間找不到相關中文文件:
http://www.fsf.org/
或者可以參考洪朝貴教授的網站http://people.ofset.org/~ckhung/a/c_83.php
有更多深入的內容。

MoPtt事件相關記錄:
http://zh.pttpedia.wikia.com/wiki/MoPTT%E5%B1%8F%E8%94%BDJPTT%E7%B0%BD%E5%90%8D%E6%AA%94%E4%BA%8B%E4%BB%B6%E8%88%87Mo%E4%B9%8B%E4%BA%82

2015年6月16日 星期二

駭客與畫家:電腦世紀的大觀念

這本書是當兵前傳說中的 jserv 大神送的,雖然說當兵有很多零碎時間,但能利用的時間不太多,19 天也才差不多看完這本書。
作者paul graham 是位程式設計師,創立了第一個提供網頁端服務的新創公司viaweb ,後來被Yahoo 收購轉變成yahoo store,他同時是Y combinator 的共同創辦人

內容沒什麼主軸,序言也自承各章間沒有關係,比較像作者寫的散文集,介紹他的想法、viaweb 的運作…,可以從字裡行間看出作者對網際網路獨到的眼光,例如本書寫在2004 裡,可是它仍精準的預見了網路應用程式的興起:「『我的電腦』這程概念正在遠去…我們應該能透過任何電腦取得我們的資料」、「用戶端不應該儲存資料,應該像是電話一樣…資料和應用程式都不需保存於用戶端」、「如果微軟的應用程式只能用在某些用戶端,競爭者將能藉由提供其他用戶端所需的版本而取勝」
對照現今的dropbox, chromebook, 行動裝置,幾乎都預測到現今的科技走向,作者也用viaweb 的營運來解釋網站型應用程式的特性,包括滾動式的出貨更新、極低的營運成本、小程式的組合而非單一大程式、為了在競爭中取勝而被迫無時無刻工作,如果是相關領域的人一定會看得猛點頭。

後面有一大部分則用來抒發作者對於「程式」這樣東西的看法,作者本身就是程式語言設計師,專精的語言是Lisp(他甚至設計了一個Lisp 的方言),書中對Lisp 的先進特性著墨許多,他覺得學Lisp就算用不上,也能鍛鍊自己對程式的想法,或許之後應該利用下部隊的閒暇時間來學習一下傳說中的危險剃刀。

依作者的看法,他認為理想的語言應該有下面這幾個特性:
  • 可以很快用很短的原始碼完成雛型產品,不需慢慢堆出成品
  • 可以快速分析原始碼,找到需要最佳化的焦點
  • 夠直覺,可以輕易上手,不需要長篇大論的使用說明
  • 核心夠小而且強大,不對使用者作出額外限制

當然不用說Lisp 應該是作者理想語言的首選;以我個人的觀點,我認為python 是目前最符合這樣描述的語言,但新的語言不斷出世,時時刻刻都要保持學習的心情,就像作者警告的:你學會一種語言,你會用那種語言在思考,於是你只會覺得其他語言只是「多了一些不一樣的語法,可以達到相同功能」的語言,卻會忽視了其他語言的強大之處。

整體來說,這本書還是可以看,不過我覺得不太需要太過認真,選幾章看起來有趣的章節讀就好了,不過話說回來這本書好像已經絕版了,只能看網路上的電子全文了:

相關資料:
paul graham 的個人網頁
viaweb條目:

噢,附帶一提,這本書裡面錯字其實不少,而且依據錯字錯的方式,我認為翻譯的人可能是用嘸蝦米輸入法,像是運算(ZMR)變成運些(ZFR),決定(NEZ)變成決正(EZ)