天天看點

這 10 行比較字元串相等的代碼給我整懵了,不信你也來看看

碼農唐磊 程式猿石頭

這 10 行比較字元串相等的代碼給我整懵了,不信你也來看看

抱歉用這種标題吸引你點進來了,不過你不妨看完,看看能否讓你有所收獲。(有收獲,請評論區留個言,沒收獲,下周末我直播吃**,哈哈,這你也信)

補充說明:微信公衆号改版,對各個号主影響還挺大的。目前從背景資料來看,對我影響不大,因為我這反正都是小号圖檔閱讀量本身就少的可憐,真相了,圖檔(剛從交流群學會的表情)。

先直接上代碼:

上面的代碼是我根據原版(Scala)翻譯成 Java的,Scala 版本(最開始吸引程式猿石頭注意力的代碼)如下:

剛開始看到這段源碼感覺挺奇怪的,這個函數的功能是比較兩個字元串是否相等,首先“長度不等結果肯定不等,立即傳回”這個很好了解。

再看看後面的,稍微動下腦筋,轉彎下也能明白這其中的門道:通過異或操作1^1=0, 1^0=1, 0^0=0,來比較每一位,如果每一位都相等的話,兩個字元串肯定相等,最後存儲累計異或值的變量equal必定為 0,否則為 1。

我們常常講性能優化,從效率角度上講,難道不是應該隻要中途發現某一位的結果不同了(即為1)就可以立即傳回兩個字元串不相等了嗎?(如上所示)。

這其中肯定有……

這 10 行比較字元串相等的代碼給我整懵了,不信你也來看看

結合方法名稱 safeEquals 可能知道些眉目,與安全有關。

本文開篇的代碼來自playframewok 裡用來驗證cookie(session)中的資料是否合法(包含簽名的驗證),也是石頭寫這篇文章的由來。

以前知道通過延遲計算等手段來提高效率的手段,但這種已經算出結果卻延遲傳回的,還是頭一回!

我們來看看,JDK 中也有類似的方法,如下代碼摘自 java.security.MessageDigest:

看注釋知道了,目的是為了用常量時間複雜度進行比較。

但這個計算過程耗費的時間不是常量有啥風險?(腦海裡響起了背景音樂:“小朋友,你是否有很多問号?”)

這 10 行比較字元串相等的代碼給我整懵了,不信你也來看看

再深入探索和了解了一下,原來這麼做是為了防止計時攻擊(Timing Attack)。(也有人翻譯成時序攻擊)

這 10 行比較字元串相等的代碼給我整懵了,不信你也來看看

計時攻擊是邊信道攻擊(或稱"側信道攻擊", Side Channel Attack, 簡稱SCA) 的一種,邊信道攻擊是一種針對軟體或硬體設計缺陷,走“歪門邪道”的一種攻擊方式。

這種攻擊方式是通過功耗、時序、電磁洩漏等方式達到破解目的。在很多實體隔絕的環境中,往往也能出奇制勝,這類新型攻擊的有效性遠高于傳統的密碼分析的數學方法(某百科上說的)。

這種手段可以讓調用 safeEquals("abcdefghijklmn", "xbcdefghijklmn") (隻有首位不相同)和調用 safeEquals("abcdefghijklmn", "abcdefghijklmn") (兩個完全相同的字元串)的所耗費的時間一樣。防止通過大量的改變輸入并通過統計運作時間來暴力破解出要比較的字元串。

舉個