^領導說了必須得有圖^
Author:[email protected]
2016年1月28日，OpenSSL官方發布了編號為?CVE-2016-0701?的漏洞。該漏洞發生在OpenSSL?1.0.2?版本中(OpenSSL?1.0.2f和以后版本不受影響)，在使用DH算法時對不同客戶端使用了相同私鑰和不安全的大素數，導致攻擊者可以通過降階的攻擊方式(或者是秘鑰恢復估計)來獲取服務器端的私鑰，從而解密tls。
360云安全團隊的au2o3t對官網和發現者Antonio?Sanso提供的實現存在疑惑，并提供了一份我們認為是正確的漏洞分析(歡迎反饋)。
hf
^領導說了必須得有圖^
看了CVE-2016-0701?發現者Antonio?Sanso的博文(參考1)，?對其中的攻擊步驟“calculate?yb?=?g*xa?(mod?p)?*?B”和“yb^xa?*?B^xa?(mod?p)”的由來百思而始終不得其解，并且一直對文檔中以及openssl官方中所描述需要“多次握手”頗有疑惑（參考2）。
經過一番研究，總算實現了攻擊并找到了理論證明。
事實上，攻擊者并不需要多次握手。只要握手一次，獲得服務器公鑰即可。
而Antonio?Sanso文中出現的“calculate?yb?=?g*xa?(mod?p)?*?B”和“yb^xa?*?B^xa?(mod?p)”依舊不知所云，似是毫無用處。 ? 所謂私鑰恢復攻擊，實質上是對不安全素數的降階攻擊。
安全素數也叫蘇菲·姬曼（Sophie?Germain）素數，如果?p1?是素數，p2?=?p1*2+1?也是素數，那么?p2?就是安全素數，反之則是不安全的。 ? DH密鑰交換算法的安全性基于有限域上離散對數的難解性，而其保障正是強素數模。 ? 服務器隨機產生私鑰?xb，計算公鑰?yb?=?g^xb?mod?p?（DH中，素數?p?和?g?是公開的）。
若其中?p?不夠強（不是安全素數），則?p-1?可被分解為若干素因子，這正是攻擊者可利用之處。
攻擊者已知?g，p，yb?的情況：
若p-1可被因式分解為若干小因子，則可進行降階攻擊。 ? 原式（yb?=?g^xb?mod?p）中，由于?orb(g)?值很大，難以暴力破解。
但?p-1?可分解的情況，可對其降階：
令?g’?=?g^((p-1)/q)?mod?p，其中?q?是?p-1?的一個素因子，則?g’?的階降低為?q，
那么?g’^xb?mod?p?=?g’^(xb?mod?q)?mod?p?=?yb^((p-1)/q)。 ? 至多?q?次，可以暴力得到?x’?=?xb?mod?q?值（其實至多?q^(1/2)次可得）, ? 按此法，若能得到?p-1?的若干素因子?q1，q2，q3。。。
則同理可得，g1，g2，g3。。。及?y1，y2，y3。。。
即可以較低復雜度計算出?x1?=?xb?mod?q1，x2?=?xb?mod?q2，x3?=?xb?mod?q3。。。 ? 于是由中國剩余定理可得：
xb?= （?x1*q1’*q2*q3*...+?x2*q1*q2’*q3*...+?x3*q1*q2*q3’...+?...?）?mod?q1*q2*q3*....
（q1’*q2*q3*...=?1?mod?q1，q1*q2’*q3*...?=?1?mod?q2?...?見“中國剩余定理”）
實現攻擊的時間復雜度取決于?p-1?分解出的最大素因子長度。
驗證：
為方便快速驗證原理，不妨取一較小?p?值，如?p?=?192271，g?=?2。
易知，p-1?可分解為?2?*?3?*?5?*?13?*?17?*?29。 ? 假設服務器取隨機私鑰?xb?=?34567，那么其公鑰?yb?=?2^34566?mod?192271?=?44402。 ?
則攻擊方已知量為?p?=?192271，g?=?2，?yb?=?44402，由此3量我們來嘗試計算其私鑰?xb： ? 由于?p-1?可分解為?2?*?3?*?5?*?13?*?17?*?29，
設?q1?=?2，q2?=?3，q3?=?5，q4?=?13，q5?=?17，q6?=?29。 ? 依上面公式?g’?=?g^((p-1)/q)?mod?p，可計算：
g1?=?g^((p-1)/q1)?mod?p?=?2^(192270/2)?mod?192271?=?1，同理：
g2?=?2^(192270/3)?mod?192271?=?136863，
g3?=?2^38454?mod?192271?=?118548，
g4?=?2^14790?mod?192271?=?95011，
g5?=?2^11310?mod?192271?=?141591，
g6?=?2^6630?mod?192271?=?148926，
? ? 同樣計算?y’?=?yb^((p-1)/q)?可得：
y1?=?1，
y2?=?136863，
y3?=?156372，
y4?=?1，
y5?=?188120，
y6?=?190612，
? ? 根據?g’^(xb?mod?q)?mod?p?=?yb^((p-1)/q)?即：
g1^(xb?mod?q1)?mod?p?=?y1，
g2^(xb?mod?q2)?mod?p?=?y2，
g3^(xb?mod?q3)?mod?p?=?y3，
……
? 即可算出：
x1?=?xb?mod?2?=?1,
x2?=?xb?mod?3?=?1,
x3?=?xb?mod?5?=?2,
x4?=?xb?mod?13?=?0,
x5?=?xb?mod?17?=?6,
x6?=?xb?mod?29?=?28,
? ? 由中國剩余定理：
#!bash
xb?=?x1*q1’*q2*q3*q4*q5*q6?+?x2*q1*q2’*q3*q4*q5*q6?+?x3*q1*q2*q3’*q4*q5*q6?+?x4*q1*q2*q3*q4’*q5*q6?+ x5*q1*q2*q3*q4*q5’*q6?+?x6*q1*q2*q3*q4*q5*q6′?mod?(q1*q2*q3*q4*q5*q6）
? 易算得：
q1’=1，
q2’=1，
q3’=4，
q4’=3，
q5’=7，
q6’=21，
? 則?xb?=?1*96135?+?1*64090?+?2*4*38454?+?0?+?6*7*11310?+?28*21*6630?mod?192270
=?4841317?mod?192270
=?34567
即實現了已知?p，g，yb，求?xb。
如前言所述，我們在堅信自己認為是正確的路上前進著。
gl