Haseeb Qureshi：看我如何用Ruby來破解我的Reddit密碼

最近想開一個專欄，用於介紹一些我個人學到的、看到的一些有意思的技術話題。他們不一定涉及非常複雜的技術，又或者要使用高深的理論，總之，趣味性是第一要義。由於專欄的題目還沒想好，就現以文章的形式不定期的整理、發布一些類容，希望給各位程序設計愛好者，特別是程序設計初心者一些幫助。

本次的分享來自於 RubyConf 2017 上 Haseeb Qureshi 的演講，有條件的同學可以親自去油管上觀看：https://youtu.be/ywiwq9IpDEU。

在 RubyConf 2017 上，Haseeb Qureshi 分享了他的一個親身經歷。這哥們兒呢，特別喜歡上一些並沒有什麼卵用的網站，比如 Reddit 。有一天，老哥覺得不能再這麼墮落下去，但是他也清楚自己缺乏自制力，於是他痛定思痛，便效法古人奧德修斯「作繭自縛」。

具體怎麼操作呢？首先他修改了賬戶口令，當然，這個相當長的口令是隨意輸入的：

另外，一不做，二不休。為了確保把自己逼上絕路，老哥順便把密保郵箱給改了。

老哥覺得，不能總是不上這些網站。學習、工作一段時間後，還是可以適當上這些網站摸摸魚的。於是呢，老哥就找到了一個叫做 LetterMeLater.com 的網站，把這個「隨機的」密碼放在郵件中，並讓它在一個設定的日期（通常是一兩個月）後發送到老哥的郵箱。這個網站提供了一個「Hide」選項，如果選中了這個選項，直到郵件發出後，才能看到郵件的正文。

老哥很滿意這個系統，而且還用了好一段時間，直到老哥正式入職 Airbnb 。Airbnb 是個大公司，有很多的 Test Case ，而運行這些個 Test Case 又非常耗時，於是老哥想：「這個時候我又不能正常工作，在這兒乾等測試完成太煞筆了，為啥不逛逛 Reddit 呢？」

老哥歡天喜地地打開郵箱，查看密碼。可一打開就傻眼了：「為啥還是灰色的？」結果定睛一看，發送日期一不小心就被設在了2018年。

這下就很尷尬了，測試是在太多了，老哥等不了那麼久。但由於當時勾選了「Hide」選項，他自己也看不了正文。老哥十分糟心，於是在這個網站上瞎逛一通。突然，老哥注意到了右上角有個搜索欄。

搜索欄能幹什麼呢？

• 老哥先輸入了自己的名字 haseeb ，發現沒有結果。說明這個系統沒有把發件人的名字放入索引。
• 然後老哥輸入了字元 a ，結果他發送的郵件出現了。但是這個 a 可能來自於郵件的主題（Subject）。
• 然後老哥輸入了 password ，結果他發送的郵件出現了。證實了資料庫索引了郵件的主題。
• 然後老哥又嘗試搜索了三個不在主題中的字元：e、1、2。對於前兩個字元，搜索都沒有結果。而對於字元 2 ，返回了他發送的郵件。這說明什麼？說明郵件的正文裡面有字元 2 ！

老哥想了想，等等，不對啊，好像有什麼不得了的事情。老哥頓時發現他發現了一個預言機（Oracle）：

我們每次把一個字元串作為挑戰送入預言機，預言機會告訴我們郵件的主題和內容中是否包含該字元串。這看起來是一個非常強的預言機，要記住，郵件的內容就是口令，因此我們實質上可以做口令字的子字元串查詢。

老哥又演算了一會兒，推導出了下列演算法：

1. 首先確定兩個字母表 和 ，其中 。也就是說如果 是所有可能的字元的話（字母、數字），那麼 就是排除標題使用過的字元後的字符集合。
2. 首先用 詢問預言機，會得到字元 。但我們並不知道這個字元的具體位置，我們假設它處於口令的中間，基於這個字元構造新的挑戰。
3. 首先向後搜索，方法是，使用 （注意這裡使用的是整個字元表），向預言機詢問 ，有兩種可能：
1. 我們會找到一個字元 ，使得 是口令字的子字元串。那麼就繼續使用這個方法，基於字元串 向後搜索；
2. 找不到這樣的字元，說明目前的字串已經是口令字的後綴了，這樣我們就需要尋找口令字的前綴；
4. 向前搜索方法類似，不過對於 ，我們要把 串接在已經找到的字串之前。搜索的終止條件也與向後搜索類似。

由於每次只猜測一個字元，並且每個字元之間的分布是獨立的，因此整個複雜度是線性的（這個猜解過程有點類似於 Blind ROP 中猜解 Canary的技術；老哥再對複雜度進行分析時犯了一點小錯，讀者可以思考一下整個猜解過程的複雜度。），這樣完全可以通過編程實現。

於是說干就干，老哥當場來了個 Live Coding 。整個 Coding 過程非常常規，大概是演示了一下 fadady 這個 Ruby Gem 的使用、cookie 的一些小知識。

同時，老哥一開始把整個過程劃分成了 Api 和 PasswordCracker 兩部分：前者是預言機的實現，包括如何發送 HTTP 請求，如何判斷子字元串是否存在，後者是破解演算法的實現。為了測試的方便，老哥還額外設計了一個 StubApi 用於測試，這樣就不會發送大量的 HTTP 請求。另外，根據 DRY 原則，老哥還重新重構了一下 PasswordCracker 中的演算法，用一個參數來標識搜索的方向，而不是把向前搜索和向後搜索寫成兩個方法。

光說不練假把式，拔劍吧！

最後，經過403次查詢，找出了口令：

這簡直是太棒了！

雖然整件事兒並沒有用到什麼高深的技術，但老哥還是覺得成就感爆棚——因為這是他第一次通過」編程「來解決自己的問題。期初他以為自己的口令就這麼丟了，結果沒想到通過編程給找回來了。特別是，自己設計的演算法確確實實有用，這讓老哥覺得是魔法。

之所以非常想同大家分享這個 Talk ，是因為老哥的演講讓我找回了當年編程的快樂與成就感，還有那種激情。

讓夢想照進現實，或許，這正是程序設計的迷人之所在吧？