2016年6月10日 星期五

亂玩雜湊函數

當你學密碼學的雜湊函數時,你爸爸媽媽爺爺奶奶叔叔嬸嬸舅舅阿姨,就連你男朋友女朋友啊不對我沒有女朋友全部都會跟你說:好的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 家族的雜湊函數以保證更高的安全強度。

2016年6月6日 星期一

字幕產生器 Subtitle Generator

六月初參加PyCon ,因為第一天開幕睡過頭了,用One Punch Man 超商大特賣的畫面做了兩張搞笑圖,用gimp 做不熟練,花了不少時間,決定來寫個:「字幕產生器」

成品在此:
http://yodalee.github.io/subtitle-gen.html

這個網頁基於之前qcl 大神所寫的「大師語錄產生器」,大體架構沒什麼改:
http://qcl.github.io/master-quote-gen.html

同時我還參考了以下的stack overflow,老實說要是沒有網路跟stack overflow,我應該寫得出一點C跟python,可是html 和javascript 我大概會完全卡住,一行都寫不出來:

上傳圖片到canvas裡面:
http://stackoverflow.com/questions/22255580/javascript-upload-image-file-and-draw-it-into-a-canvas
canvas 裡面大圖縮小:
http://stackoverflow.com/questions/2303690/resizing-an-image-in-an-html5-canvas
canvas裡寫字有邊框:
http://stackoverflow.com/questions/13627111/drawing-text-with-an-outer-stroke-with-html5s-canvas
指定input/color 預設顏色:
http://stackoverflow.com/questions/14943074/html5-input-colors-default-color

其實寫出來覺得有點對不起qcl 大神,其實就是「大師語錄產生器」的變種,應該要貢獻回qcl 大神的github 的,只是我不知道怎麼調和自行上傳圖片和預設圖片的衝突,也不知道要怎麼處理使用者決定文字在圖內或圖下時,canvas要怎麼處理,乾脆算了。

不過既然做出來了,表示好處多多,可以好好利用:
除了本來PyCon 兩張可以快速做出來

還可以玩一些其他的:


Future Work:等我想到再來寫

2016年5月30日 星期一

The man who knew infinity (有電)

星期日下午去看了電影<The man who knew infinity>,中譯<天才無限家>,是二十世紀初數學家Ramanujan 的傳記電影。

都是傳記電影,不免要跟2015/2的Imitation game 相比較,這類科學人物知名度不高,也還沒收入所謂<偉人傳記>中,對普羅大眾來說都相當陌生,Turing 因為是電機與資訊界的祖師,至少新聞報個Turing Award還聽過(等等,有新聞會報這個嗎…),Ramanujan則更狹隘,大概只剩下純數領域的人會知道他哪位了。

電影算是平鋪直敘,從Ramanujan 在印度懷才不遇,來到劍橋和Prof. Hardy 工作,證明出一系列公式,最終取得劍橋大學院士資格回到印度,卻英年早逝。
電影集中在他待在劍橋的5年間,要克服種族歧視、生活、戰爭種種困難,取得成就,又要掛心千里外的妻子,整體俐落大方,適時加上Hardy 無神論與Ramanujan 身為虔誠教徒的思想辯證;Hardy為Ramanujan 爭取fellow,以純數領域純粹的美讓眾人跨越種族與人身的岐視,導演在這處理得洽到好處,強而有理卻又不顯突兀。
當Ramanujan接受fellow 資格時,也是回過頭來為數學在科學界至高無上的地位,表達最高的敬意。

在處理上,我認為The man who knew infinity 勝過 Imitation Game,後者畢竟商業氣息過重,為求戲劇化改編了太多東西,多到該片wiki 條目必須加上Accuracy一段,回想起來,就會覺得該片有點假,而傳記電影卻要求那個<真>;The man who knew infinity 就不會有這種感覺。
https://en.wikipedia.org/wiki/The_Imitation_Game#Accuracy

Ramanujan 一生留下大量數學研究,電影並未多加著墨,大部分都是紙上的數學式子帶過,也造成看完後看不出片名knew infinity 是指什麼
畢竟純數學的概念實在不好解釋,導演選擇Hardy 和Ramanujan 合作研究,比較好懂的Partition 問題;利用Hardy展示P(4) = 5和P(100) = 190,569,292,讓大家感受一下問題有多難;不然Ramanujan其他研究…真正讓他贏得knew infinity之名的那堆無限級數,觀眾大概只會覺得「呃…三小?很厲害嗎?」

是說partition 的數列有收錄在oeis 裡呢XD
https://oeis.org/A000041
numberphile 也有相關的介紹:
https://www.youtube.com/watch?v=NjCIq58rZ8I

雖然本片個人評價正向,還是覺得有些敗筆:
  • 翻譯問題,不知道為啥Fellow 都翻譯成<研究員>,雖然說是沒翻錯啦,但這樣就超弱的Orz,明明應該翻皇家學院<院士>,劍橋學院<院士>比較好呀
  • 無法理解的轟炸場景:這段很顯然是改寫史實,一次世界大戰時英國雖然在戰場上損失慘重,但本土轟炸少之又少,遑論劍橋地區,這段來得快去得也快,感覺是為了有點聲光效果加上去,讓學VFX 的血汗工程師糊口飯吃,讓人覺得一頭霧水。
  • 另一個敗筆是結尾,傳記電影到結尾總是要來點真實事蹟作個點綴,展示一下Ramanujan 和妻子的真實照片、展示在圖書館的手稿,旁白字幕大概是這麼寫的:「1976年,Ramanujan 一份手稿被發現,他的數學公式現今被應用到理解黑洞運作上」
結尾來看,這段話還是說了:Ramanujan的天才發現,仍然是「有用的」「可應用的」,可是整部片不斷闡述的觀念是啥?不就是Hardy、Ramanujan等人對數學的追求,不為什麼,為了就是那個純粹超脫世俗的「美」,那個低調卻又凌駕萬物的真理?
正如片頭引用Russel 的話:Mathematics, rightly viewed, possesses not only truth, but supreme beauty
純數學不問有何用,只是欣賞、讚嘆它的規則,明明全片表現得可圈可點,卻在最後錯了一個音符。

總歸來說,這部片大概註定一個小眾片,我看的電影院只用5排的小廳在播,也不像Imitation Game 有Benedict撐腰(?,票房大概也就不上不下,不過如果受夠了充滿了VFX特效電影,想看一點純粹敘事電影放鬆心靈,The man who knew infinity 應該是近期不錯的選擇,就算太無聊,睡個2小時也可以當作休養身心(X。
這倒是讓我想到,之前看美國隊長3,Cast 的部分做VFX 的公司至少有10家以上,The man who knew infinity:兩家XD

從Imitation Game 到The man who knew infinity(其實之前還有The Theory of Everything,不過那部我沒看),都是以特定領域知名科學家為藍本,讓我開始懷疑Hollywood 是不是把目光轉向這類故事了?
自己的感覺,值得搬上大螢幕的,像是那位身處男性強勢的資訊學界,卻一手開啟高階語言,「大家都不相信我,我寫了個編譯器卻沒人要碰它」的Grace Hopper;科技界兩位工程師競爭發明積體電路,二十世紀初太多科學家的故事未被世人所知。
https://en.wikipedia.org/wiki/Grace_Hopper
//美國海軍竟然有一艘驅逐艦(DDG-70 Hopper)以她為名lolololol
儘管科學家的故事通常…有點沉悶,但就如Imitation Game 選用同性戀當切入,The man who knew infinity 選用數學跨越種族與世俗的鴻溝,經過適當改編和潤飾,仍然能讓劇情富有張力,進而讓世人認識他/她們,就讓我們期待編劇們的功力吧。

2016年5月23日 星期一

一樁因為版本升級引發的慘案

Minecraft升上1.9板已經有一段時間了,因為1.9版加入了戰鬥功能,玩家能在左手跟右手上放置不同的物品,也因此造成了一些悲劇。

故事是這樣子的,之前寫的Minecraft plugin fastbuild,放置方塊時可以大量放置的功能
http://yodalee.blogspot.tw/2014/02/minecraft-plugin-fastbuild.html
設計上我是先取得玩家手上的物品,一個ItemStack 的物件。
計算所能放置的數量,從ItemStack 減去放置的數量,再call API將玩家手上的物品設為ItemStack。

問題出在現在Minecraft 1.9允許有兩隻手,如果將物品放在左手,則放置會將右手設為ItemStack,若右手空手就變成憑空複製物品。

解決方式是判斷玩家在放置物品是從左手放還是右手放,在設定手上物品時設定為玩家使用的那隻手,新的API 針對兩種手有不用的設定function,用新的API 解掉即可。
不過在修掉之前,server 上已經有人用這樣的複製功能弄了一大堆鑽石磚,還在我家旁蓋了一座鑽石塔,根本嘲諷點滿了XD (不過這座塔因為衝到旁邊的建案,應該會被我都更掉)


總之,當主程式和API 的不斷更新的時候,自己寫的程式是也要時時跟上最新,否則不知不覺中就會噴出bugs 來。

當然這樣的升級也不是不好,之前每個block 的型態是用 int 來表示,要比對型態就要自己去查每個物品的編號,新版的API 已經將所有物品用Enum 再包一層,使用真實名字來代表物品,撰寫時不再需要自己查編號值,相對來說好寫得多。

2016年5月22日 星期日

使用GAE python自幹Facebook Bot

話說最近各種Bot 的傳聞,又看到如<參考文件1>有人弄了一個建在Flask 上面的Facebook Bot,強者我同學qcl 也弄了傳說中的libGirlfriendFramework,就想來弄一個回應產生器,以下是大概的開發流程:

首先先在Facebook 頁面上申請一個粉絲專頁,可以先使用「未發佈專頁」大家就不會搜到這個專頁;另外要申請應用程式,其實Facebook 的說明文件已經寫得滿清楚了,申請的部分照著做就是了
https://developers.facebook.com/docs/messenger-platform/quickstart

進到應用程式主控板,選左列<+新增產品>並選擇<messenger>,使用Facebook messenger platform。
接著在messenger 裡,粉絲專頁選擇自己的粉絲專頁,拿到粉絲專頁的token,記起來下面會用;下方設定webhook-edit event,回呼網址是你伺服器的網址,必須透過https 連線,驗證權杖則隨你喜好設定一段字串。

如果有看下面<參考文件1>,因為它的server 看來是買自己網域建在自家主機上面,所以在https 的部分比較麻煩,要自己用Let's encrypt 去生一個CA出來,因為我們是用GAE,網域直接走Google 的CA,所以這步可以省下來;這步卡了我卡超久,Let's encrypt 跟GAE 不太合,怎麼裝都裝不上去;經強者我同學qcl 大神提醒才發現根本不用理這個,這時上午已經過去了,當下覺得蠢。

第一步就是把webhook 裝上去,首先連接webhook 的route:
app = webapp2.WSGIApplication([
  ('/webhook', FBwebhook),
], debug=True)

並實作 get handler,所謂verificaion token就是上面寫驗證權杖,寫到這裡可以如參考資料1用Postman去檢驗是否有問題:
class FBwebhook(webapp2.RequestHandler):
  def get(self):
    verification_code = "Verification Token Here"
    verify_token = self.request.get('hub.verify_token')
    verify_challenge = self.request.get('hub.challenge')
    if verification_code == verify_token:
      self.response.write(verify_challenge)

實作完成後連接webhook 的地方應該就能通過了,四個選項依自己的需要選擇:
  • messages:接收訊息的callback,最基本都有這個,這個都沒勾你連接messenger 幹嘛XD
  • message_deliveries:傳送訊息的callback
  • messaging_optins:連接Send-to-Messenger plugin
  • messaging_postbacks:連接postback button的事件
上面四個我只勾了messages 可是也可以正常接受、發送訊息,其他三個光看說明看不懂是要幹嘛,有人知道的話歡迎解惑。

連接了webhook 就能向Facebook 註冊你的應用程式了,依照getting started 的頁面指示發送要求,token請換成你粉絲專頁的token:
curl -ik -X POST "https://graph.facebook.com/v2.6/me/subscribed_apps?access_token=<token>

理應會收到
{“success”: true}
現在可以真的在facebook粉絲頁丟訊息了,它會向webhook設定的回呼網址發送Post,getting started 的頁面有介紹傳來的json 格式,可在webhook中建post handler然後 print(self.request.body),就能從google cloud platform 的紀錄中撈到:

以下是撈到的內容:
{
"object":"page",
"entry":[
  {
  "id":"page id",
  "time":1463907808653,
  "messaging":[
    {
    "sender":{"id":"sender id"},
    "recipient":{"id":"recipient id"},
    "timestamp":1463907808591,
    "message":{
      "mid":"mid.1463907808584:503df60b4ad4529365",
      "seq":7,
      "text":"XDDD"}
    }
  ]}
]}

處理訊息用python json 就行了:
message_entry = json.loads(self.request.body)['entry']
for entry in message_entry:
    messagings = entry['messaging']
    for message in messagings:
        sender = message['sender']['id']
        if message.get('message'):
            text = message['message']['text']
            print(u"{} says {}".format(sender, text))

到這裡應該可以在你的google cloud platform 紀錄中找到你發送訊息的內容,下一步就是回訊息,只要向粉絲專頁的網址,搭配token發送post 訊息即可,很容易…個頭:
def send_fb_message(self, to, message):
  post_url = "https://graph.facebook.com/v2.6/me/messages?access_token={token}"
    .format(token=FBtoken)
  response_message = json.dumps(
    {"recipient": {"id": to},
     "message": {"text": message}})
  result = urlfetch.fetch(
    url=post_url,
    headers={"Content-Type": "application/json"},
    payload=response_message,
    method=urlfetch.POST)

  print("[{}] reply to {}: {}".format(result, to.encode('utf-8'), message))

要注意的一個是,因為google appengin python 一直停留在python2.7 ,所以unicode handler不若python3 這麼完整,上面很多encode('utf-8')都是不斷錯誤後加上去的,也曾經發送訊息「太強啦」結果GAE 整個當掉,因為這三個字一直引發handler crash,handler沒有回音導致Facebook又發送一次「太強啦」過來,然後就無限loop 了,這時要用上面的curl 命令,把你註冊的程式refresh 一下,讓Facebook 不要再發訊息過來。

為了這堆unicode 又花掉一個下午,寫這個簡單的Bot 一天就用掉了…寫到這裡我突然想到那篇傳奇文章「軟體工程師的鄙視鏈」裡面那句:
用 Python 3 的工程師鄙視還在用 Python 2 的工程師,用 Python 2 的工程師鄙視遇到 UnicodeEncodeError 的工程師。
完了我要被鄙視了QAQ

總之最後結果像這樣:

我曾經很認真地想過這個功能到底有什麼用,後來我想到,例如中央氣象局的粉絲頁就能加入註冊跟發送訊息的功能,我們可以發送訊息給該粉絲頁:「註冊/台北」或「註冊/高雄」
後端的handler 在接受這樣的訊息時,將發送者的ID跟地點加入後端的資料庫中,如地震通報或是每日當地的氣象預報就能自動發訊息給每位註冊的使用者。

不過目前沒看到非常印象深刻的應用就是了。

Project 放在這裡,星星就…隨便啦,其實沒有很需要=_=
https://github.com/yodalee/IPban-bot

順帶一提,強者我同學qcl 也有一個類似的project,現在亟需開發者貢獻,據說已經辦了兩次全球開發者大會,各種生猛:
https://github.com/libGF/libGirlfriendFramework

參考文件:
1.使用Flask開發Facebook Message Bot:
http://enginebai.logdown.com/posts/733000/python-facebook-bot
2. Facebook message platform 文件:
https://developers.facebook.com/docs/messenger-platform