两个字符串比较是否相等(实现两个字符串的比较)-众学网

先直接上代码：

booleansafeEqual(Stringa,Stringb){if(a.length()!=b.length()){returnfalse;}intequal=0;for(inti=0;i<a.length();i ){equal|=a.charAt(i)^b.charAt(i);}returnequal==0;}

上面的代码是我根据原版（Scala）翻译成Java的，Scala版本（最开始吸引我注意力的代码）如下：

defsafeEqual(a:String,b:String)={if(a.length!=b.length){false}else{varequal=0for(i<-Array.range(0,a.length)){equal|=a(i)^b(i)}equal==0}}

刚开始看到这段源码感觉挺奇怪的，这个函数的功能是比较两个字符串是否相等，首先“长度不等结果肯定不等，立即返回”这个很好理解。

再看看后面的，稍微动下脑筋，转弯下也能明白这其中的门道：通过异或操作1^1=0, 1^0=1, 0^0=0，来比较每一位，如果每一位都相等的话，两个字符串肯定相等，最后存储累计异或值的变量equal必定为 0，否则为 1。

再细想一下呢？for(i<-Array.range(0,a.length)){if(a(i)^b(i)!=0)//ora(i)!=b[i]returnfalse}

我们常常讲性能优化，从效率角度上讲，难道不是应该只要中途发现某一位的结果不同了（即为1）就可以立即返回两个字符串不相等了吗？(如上所示)。

这其中肯定有……

再再细想一下呢？

结合方法名称safeEquals可能知道些眉目，与安全有关。

本文开篇的代码来自playframewok 里用来验证cookie(session)中的数据是否合法(包含签名的验证)，也是石头写这篇文章的由来。

以前知道通过延迟计算等手段来提高效率的手段，但这种已经算出结果却延迟返回的，还是头一回！

我们来看看，JDK 中也有类似的方法，如下代码摘自java.security.MessageDigest：

publicstaticbooleanisEqual(byte[]digesta,byte[]digestb){if(digesta==digestb)returntrue;if(digesta==null||digestb==null){returnfalse;}if(digesta.length!=digestb.length){returnfalse;}intresult=0;//time-constantcomparisonfor(inti=0;i<digesta.length;i ){result|=digesta[i]^digestb[i];}returnresult==0;}

看注释知道了，目的是为了用常量时间复杂度进行比较。

但这个计算过程耗费的时间不是常量有啥风险？（脑海里响起了背景音乐：“小朋友，你是否有很多问号？”）

真相大白

再深入探索和了解了一下，原来这么做是为了防止计时攻击（Timing Attack）。（也有人翻译成时序攻击）

计时攻击(Timing Attack)

计时攻击是边信道攻击(或称”侧信道攻击”， Side Channel Attack，简称SCA) 的一种，边信道攻击是一种针对软件或硬件设计缺陷，走“歪门邪道”的一种攻击方式。

这种攻击方式是通过功耗、时序、电磁泄漏等方式达到破解目的。在很多物理隔绝的环境中，往往也能出奇制胜，这类新型攻击的有效性远高于传统的密码分析的数学方法（某百科上说的）。

这种手段可以让调用safeEquals(“abcdefghijklmn”, “xbcdefghijklmn”)（只有首位不相同）和调用safeEquals(“abcdefghijklmn”, “abcdefghijklmn”)（两个完全相同的字符串）的所耗费的时间一样。防止通过大量的改变输入并通过统计运行时间来暴力破解出要比较的字符串。

举个??，如果用之前说的“高效”的方式来实现的话。假设某个用户设置了密码为password，通过从a到z（实际范围可能更广）不断枚举第一位，最终统计发现p0000000的运行时间比其他从任意a~z的都长（因为要到第二位才能发现不同，其他非p开头的字符串第一位不同就直接返回了），这样就能猜测出用户密码的第一位很可能是p了，然后再不断一位一位迭代下去最终破解出用户的密码。

当然，以上是从理论角度分析，确实容易理解。但实际上好像通过统计运行时间总感觉不太靠谱，这个运行时间对环境太敏感了，比如网络，内存，CPU负载等等都会影响。

但安全问题感觉更像是 “宁可信其有，不可信其无”。为了防止(特别是与签名/密码验证等相关的操作)被timing attack，目前各大语言都提供了相应的安全比较函数。各种软件系统（例如 OpenSSL）、框架（例如 Play）的实现也都采用了这种方式。

例如 “世界上最好的编程语言”（粉丝较少，评论区应该打不起架来）—— php中的:

//Comparestwostringsusingthesametimewhetherthey’reequalornot.//Thisfunctionshouldbeusedtomitigatetimingattacks;//forinstance,whentestingcrypt()passwordhashes.boolhash_equals(string$known_string,string$user_string)//Thisfunctionissafeagainsttimingattacks.booleanpassword_verify(string$password,string$hash)

其实各种语言版本的实现方式都与上面的版本差不多，将两个字符串每一位取出来异或(^)并用或(|)保存，最后通过判断结果是否为 0 来确定两个字符串是否相等。

如果刚开始没有用safeEquals去实现，后续的版本还会通过打补丁的方式去修复这样的安全隐患。

例如JDK 1.6.0_17 中的Release Notes[1]中就提到了MessageDigest.isEqual中的bug的修复，如下图所示：