撲克牌版的 「公鑰夾帶部分私鑰」密碼破解術

作者/洪朝貴(任教朝陽科技大學資訊管理系)

(本文轉載自作者部落格「資訊人權貴ㄓ疑」)

監聽,是很受統治者歡迎的技術。40年前美國總統尼克森頗好此道,也因此羞愧下臺。今天的美國政府掌握更先進的科技,並藉反恐、打擊犯罪之名,更全面地對國內外公民違法監聽。史諾登(Edward 『Snowden』) 因為在今年六月間揭發NSA(國安局)的監聽弊案而『獲頒揭密者獎』,但後續記者及電腦專家仍在持續分析尚未爆完的資料。最近又有好幾彈爆開,其中一彈嚇死人:『加密對NSA無效』。即使紐約時報跟華盛頓時報都報出來了(『NSA foils encryption』),即使資安『專家』都因此而跳出來呼籲必須『更改網安標準』,很多人還是不相信NSA辦得到。NSA到底可能採取哪些神奇的方式破解密碼?大推資安教授『Matthew Green On the NSA』 一文。本文只針對其中一種很明確可行的可能性,拿撲克牌當比喻,讓大家知道:當你所採用的加解密軟體來自一家「與NSA過從甚密的廠商」而你又看不到原始碼的時候,「NSA可以破解你的密碼」這完全是辦得到的事。 (一月份後續發展: 已證實 『RSA backdoor』 確實存在,資安界集體抗議。)

把網路上的加解密活動極度簡化,想像成是一桌撲克牌局。這個牌局的遊戲規則細節我們就省略了,只需要知道:

1. 有兩副撲克牌,一副是藍色,另一副是橘色。

2. 遊戲一開始,莊家會發給每個人一張藍色牌、一張橘色牌。

3. 每個人把手上的橘色牌攤在牌桌上,但藍色牌不給別人看。

如果你對於這兩張牌所代表的詳細意義有興趣,可以參考『白話版的非對稱式加解密』 一文;但就本文而言,其實只需要知道:橘色牌代表加解密演算法當中的公鑰(大家都看得見),而藍色牌則代表私鑰(只有自己看得見)。

現在的問題是:莊家有沒有可能知道每個人手中的藍色牌是哪張?如果莊家照規矩來,雖然發牌的時候他一定會看見牌,但理論上他不應該記牌。但是如果他發牌的時候動一點手腳,自己加一點潛規則進去,把藍色牌的資訊藏到橘色牌裡面去,那他就比不知情的玩家要佔一些便宜了。例如他發牌的時候,可以先抽一張橘色牌,然後根據橘色牌的數字大小來決定要發什麼花色的藍色牌給玩家。更具體地舉例,比方他自己暗中決定:

1. 如果橘色牌是A或2或3,那麼他就不斷地重抽藍色牌,直到抽到梅花,才把它跟橘色牌一起發給玩家。

2. 如果橘色牌是4/5/6,那就一定要抽到一張方塊的藍色牌才發牌。

3. 如果橘色牌是7/8/9,那就一定要抽到一張紅心的藍色牌才發牌。

4. 如果橘色牌是10或人頭, 那就一定要抽到一張黑桃的藍色牌才發牌。

因為橘色牌攤在桌上,所以大家都看得見;但是因為只有莊家知道發牌的潛規則,所以只有他可以從攤在桌面上的橘色牌,推測出蓋著的藍色牌的花色。

(撲克牌圖形取材自 OpenClipart.org)

以上就是我對Claude Crépeau與Alain Slakmon的論文〈Simple Backdoors for RSA key generation〉的「撲克牌比喻版」白話翻譯。當然,真實的狀況要複雜很多,理解上述比喻之後,還需要略微修正如下。

「莊家」在真實世界裡,就是密碼產生器/亂數產生器。拿「NSA要求微軟安裝在Windows裡的後門」來說,如果運作方式真的類似本文所述的話,它也不太可能記牌(記住每位Windows 用戶所產生的所有公私鑰),因為「每當金鑰一產生就出現(回傳NSA的)網路活動」太容易被識破。所以採取本文的策略比較合理可行——一般人不會想到私鑰的部分訊息會被藏在公鑰裡,更不會想到只洩漏私鑰的部分訊息,密碼就會被完全破解。

從一副撲克牌當中抽一張,只能傳遞不到6個bits的資訊(52 < 64 = 26),雖然比2.3 bits 的『教學品保量化指標』更有意義一點,但跟實際應用上幾十或幾百個bits的資訊還是差很多。在上述的比喻中,莊家很老千地把(理應是私密的)藍色牌其中2個bits的資訊(22 = 4 種花色)暗藏到橘色牌的5.8個bits裡面去。

在實際的RSA 加解密演算法當中,藍色牌跟橘色牌之間本來就不能任意組合、莊家(密碼產生器)本來就合理地必須篩選出某些有意義組合的一雙「藍色牌/橘色牌」。也因此,會浪費掉一些bits。RSA Security 公司表示:1024 bits的RSA密碼,大約只有80 bits(完全自由隨意亂碼的)對稱加密密碼的強度;3072 bits 的RSA 密碼,大約等同於128 bits完全亂碼的強度。

「玩了一陣子之後,莊家的潛規則會不會被觀察力敏銳的玩家發現呢?例如玩家可能發現:為什麼每當我拿到點數小的橘色牌時,藍色牌就一定是梅花?」因為真實世界的bits數太多,可以排列組合的方式太多,所以莊家可以採用很複雜的潛規則把資訊打很亂地藏到橘色牌裡,讓玩家很難看出與正常隨機發牌有何不同。

「只知道藍色牌的花色,還是無法精確地指出藍色牌是哪一張啊!(所以無法破解密碼)」嗯,到這裡,就幾乎必須把比喻丟掉了。Simple Backdoors 論文其實是建立在Boneh、Durfee 與Frankel 的〈An attack on RSA given a small fraction of the private key bits〉及其他更數學的論文之上。如前所述,藍色牌與橘色牌之間其實並不是完全隨意組合。也就是說,就算莊家不耍老千,任何人從桌面上對手的橘色牌還是可以稍微推算一下他手中可能有哪些藍色牌、不可能是哪些藍色牌。如果進一步知道藍色牌更多一點資訊,就更可以縮小範圍了。這篇attack 論文指出:只要可以取得藍色牌(bits 數)1/4 的資訊,那麼要精確指出藍色牌到底是哪一張,就變得「相對很簡單」。(所需破解時間從指數時間exponential time大幅降到多項式時間polynomial time)他們並且真的跑程式測試,在500 MHz 的Intel P3機器上,試著破解1024 bits 的RSA 密碼(假設已知其中最高的 256 bits)只需要21小時。如果說原先破解RSA的困難度就像想要出大氣層旅遊一樣——不是不可能,但你我做不到——那麼「已知部分密碼」版的破解困難度,就像花個一兩千塊搭高鐵旅遊一樣輕鬆。

這裡雖然是舉RSA為例,但我相信網路上一定還可以找得到更多破解其他「非對稱式加解密」的論文。當然,像是RSA 這類歷經長時間驗證的加解密演算法,都不太可能被徒手直接攻破——比較可能是在「部分機密被偷偷巧妙洩漏」的前提之下,才會被破解。而最簡單的「偷偷巧妙洩漏」方式,就是如本文所說,把私鑰的一部分資訊藏在公鑰裡面。最有可能被惡意動手腳的地方,就是密碼產生器與亂數產生器,而美國NSA與FBI等等情治單位,過去不斷在這方面出手惹議,早為關心資安人士知悉。小格(指作者部落格)先前提及的兩個案例:『NSA』要求微軟暗植的 『Windows 後門』以及『OpenBSD』被懷疑遭FBI 植『後門』(但後來證實並沒有),最終都追蹤到這個地方。差別在於:OpenBSD 的原始碼攤在陽光下,所以大家可以仔細檢查可疑的地方;而Windows的程式碼看不見,所以用戶就只好自求多福了。我們一直強調:為什麼社會應該要採用自由軟體∕開放原始碼軟體?除了免費跟好用之外,還有其他更重要的原因——資訊安全也是其中之一。採用開放原始碼軟體,並不必然就100%安全;但若採用看不見原始碼的軟體,那根本就不必談什麼資訊安全了。

(請用文中『關鍵詞』或鄰近的『關鍵』雙『詞組』搜尋近一步參考資料。)

沒有留言:

張貼留言