ug环球官方网:这 10 行对照字符串相等的代码给我整懵逼了,不信你也来看看|原创版

admin 1个月前 (09-17) 科技 71 4

负疚用这种题目吸引你点进来了,不外你不妨看完,看看能否让你有所收获。​(有收获,请谈论区留个言,没收获,下周末我直播吃**,哈哈,这你也信)

弥补说明:微信民众号改版,对各个号主影响还挺大的。现在从后台数据来看,对我影响不大,由于我这横竖都是小号,阅读量自己就少的可怜,真相了,狗头(刚从交流群学会的脸色)。

先直接上代码:

boolean safeEqual(String a, String b) { if (a.length() != b.length()) { return false; } int equal = 0; for (int i = 0; i < a.length(); i++) { equal |= a.charAt(i) ^ b.charAt(i); } return equal == 0; } 

上面的代码是我凭据原版(Scala)翻译成 Java的,Scala 版本(最最先吸引程序猿石头注意力的代码)如下:

def safeEqual(a: String, b: String) = { if (a.length != b.length) { false } else { var equal = 0 for (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) // or a(i) != b[i] return false } 

我们常常讲性能优化,从效率角度上讲,岂非不是应该只要中途发现某一位的效果差别了(即为1)就可以立刻返回两个字符串不相等了吗?(如上所示)

这其中一定有……

再再细想一下呢?

连系方式名称 safeEquals 可能知道些眉目,与平安有关。

本文开篇的代码来自playframewok 里用来验证cookie(session)中的数据是否正当(包罗署名的验证),也是石头写这篇文章的由来。

以前知道通过延迟盘算等手段来提高效率的手段,但这种已经算出效果却延迟返回的,照样头一回!

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

public static boolean isEqual(byte[] digesta, byte[] digestb) { if (digesta == digestb) return true; if (digesta == null || digestb == null) { return false; } if (digesta.length != digestb.length) { return false; } int result = 0; // time-constant comparison for (int i = 0; i < digesta.length; i++) { result |= digesta[i] ^ digestb[i]; } return result == 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中的:

// Compares two strings using the same time whether they're equal or not. // This function should be used to mitigate timing attacks; // for instance, when testing crypt() password hashes. bool hash_equals ( string $known_string , string $user_string ) //This function is safe against timing attacks. boolean password_verify ( string $password , string $hash ) 

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

若是刚最先没有用 safeEquals 去实现,后续的版本还会通过打补丁的方式去修复这样的平安隐患。

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

ug环球官方网:这 10 行对照字符串相等的代码给我整懵逼了,不信你也来看看|原创版 第1张

MessageDigest timing attack vulnerabilities

人人可以看看这次调换的的详细信息openjdk中的 bug fix diff[2]为:

ug环球官方网:这 10 行对照字符串相等的代码给我整懵逼了,不信你也来看看|原创版 第2张

MessageDigest.isEqual计时攻击

Timing Attack 真的可行吗?

我以为各大语言的 API 都用这种实现,一定照样有原理的,理论上应该可以被行使的。 这不,学术界的这篇论文就宣称用这种计时攻击的方式破解了 OpenSSL 0.9.7 的RSA加密算法了。关于 RSA 算法的先容可以看看之前本人写的这篇文章。

这篇Remote Timing Attacks are Practical[3] 论文中指出(我大致翻译下摘要,感兴趣的同砚可以通过文末链接去看原文):

计时攻击往往用于攻击一些性能较弱的盘算装备,例如一些智能卡。我们通过实验发现,也能用于攻击通俗的软件系统。本文通过实验证实,通过这种计时攻击方式能够攻破一个基于 OpenSSL 的 web 服务器的私钥。效果证实计时攻击用于举行网络攻击在实践中可行的,因此各大平安系统需要抵御这种风险。

最后,本人究竟不是专研完全偏向,以上形貌是基于本人的明了,若是有纰谬的地方,还请人人留言指出来。谢谢。

弥补说明2:谢谢正在阅读文章的你,让我另有动力继续坚持更新原创。

本人发文不多,但希望写的文章能到达的目的是:占用你的阅读时间,就只管能够让你有所收获。

若是你以为我的文章有所辅助,还请你协助转发分享,另外请别忘了点击民众号右上角加个星标,好让你别错过后续的精彩文章(微信改版了,或许我发的文章都不能推送到你那了)。

​原创至心不易,希望你能帮我个小忙呗,若是本文内容你以为有所启发,有所收获,请协助点个“在看”呗,或者转发分享让更多的小伙伴看到。 ​ 参考资料:

  • Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension
  • Remote Timing Attacks are Practical

参考资料

[1] Release Notes: http://www.oracle.com/technetwork/java/javase/6u17-141447.html

[2] openjdk中的 bug fix diff: http://hg.openjdk.java.net/jdk6/jdk6/jdk/rev/562da0baf70b

[3] Remote Timing Attacks are Practical: http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

,

欧博开户

欢迎进入欧博开户平台(Allbet Game):www.aLLbetgame.us,欧博开户平台开放欧博Allbet开户、欧博Allbet代理开户、欧博Allbet电脑客户端、欧博AllbetAPP下载等业务。

皇冠体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:ug环球官方网:这 10 行对照字符串相等的代码给我整懵逼了,不信你也来看看|原创版

网友评论

  • (*)

最新评论

  • 卡利开户 2020-09-17 00:05:33 回复

    皇冠APP下载是一个提供皇冠代理APP下载、皇冠会员APP下载、皇冠体育最新登录线路、新2皇冠网址的的体育平台。无需手动搜寻皇冠体育登录线路网址,还可以下载皇冠体育APP。走不出来了

    3