专栏首页艾小仙这 10 行比较字符串相等的代码给我整懵了,不信你也来看看

这 10 行比较字符串相等的代码给我整懵了,不信你也来看看

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

补充说明:微信公众号改版,对各个号主影响还挺大的。目前从后台数据来看,对我影响不大,因为我这反正都是小号

阅读量本身就少的可怜,真相了,

(刚从交流群学会的表情)。

先直接上代码:

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的修复,如下图所示:

MessageDigest timing attack vulnerabilities

大家可以看看这次变更的的详细信息openjdk中的 bug fix diff[2]为:

MessageDigest.isEqual计时攻击

Timing Attack 真的可行吗?

我觉得各大语言的 API 都用这种实现,肯定还是有道理的,理论上应该可以被利用的。这不,学术界的这篇论文就宣称用这种计时攻击的方法破解了 OpenSSL 0.9.7 的RSA加密算法了。关于 RSA 算法的介绍可以看看之前本人写的这篇文章。

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

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

最后,本人毕竟不是专研安全方向,以上描述是基于本人的理解,如果有不对的地方,还请大家留言指出来,感谢。

补充说明2:感谢正在阅读文章的你,让我还有动力继续坚持原创。 本人发文不多,但希望写的文章能达到的目的是:占用你的阅读时间,就尽量能够让你有所收获。 如果你觉得我的文章有所帮助,还请你帮忙转发分享,另外请别忘了点击公众号右上角加个星标,好让你别错过后续的精彩文章(微信现在改版了,或许我发的文章都不能推送到你那了)。

原创真心不易,希望你能帮我个小忙呗,如果本文内容你觉得有所启发,有所收获,请帮忙点个“在看”呗,或者转发分享让更多的小伙伴看到。

参考资料

[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

本文分享自微信公众号 - 艾小仙(aixiaoxianren)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-08-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 这 10 行比较字符串相等的代码给我整懵了,不信你也来看看

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

    程序猿石头
  • VBA字符串介绍,这篇就够了

    是的,所有语言的数据类型就那么几种,而字符串就是其中重要的一种,也是基础中的基础,值得我们好好研究。

    猴子数据分析
  • 这可能是全网最简单的KMP了(上篇)

    KMP 其实已经念念叨叨挺长时间了,一直没写的原因是我觉得自己可能写不好。与其误人子弟,宁可错失良机。毕竟自己懂是一码事,能讲清楚是另一码事。

    程序员小浩
  • 南京渣硕求职路(网易美团头条百度面经)+Java学习路线(拙见)

    首先自我介绍一下,楼主南京渣硕一枚,秋招主要投递JAVA后台岗位,面过以下公司:网易+美团+头条+百度+华为+中兴,拿下了网易和中兴提前批offer,华为依旧泡...

    Java架构技术
  • 字符串: KMP是时候上场了(一文读懂系列)

    因为是由这三位学者发明的:Knuth,Morris和Pratt,所以取了三位学者名字的首字母。所以叫做KMP

    代码随想录
  • 程序员使用"位运算"装逼指南

    运算可谓是与编程息息相关,我们编写的每一个程序可能都带有加减乘除,当然这是最基础的运算了。在大一下的时候学了第一门编程语言C,随着也学到了取余(%)和三目运算符...

    程序IT圈
  • 重学KMP!

    https://leetcode-cn.com/problems/implement-strstr/

    代码随想录
  • 字符串:总结篇!

    其实我们已经学习了十天的字符串了,从字符串的定义到库函数的使用原则,从各种反转到KMP算法,相信大家应该对字符串有比较深刻的认识了。

    代码随想录
  • 谈谈 Python 那些不为人知的冷知识(三)

    这是 Python 中好玩但比较冷门的知识点第三篇,一篇只分享五个,不想错过的,千万记得关注一下。

    张俊红
  • Java架构师六大互联网公司面试经历总结

    Java架构师面试经历从58同城——华为 ——招商银行网络中心——金蝶互联网公司GR——苏宁易购 ——蚂蚁金服,看完鬼知道我经历了什么,但是每一次都是成长。本人...

    Java知音
  • python基础面试题整理---从零开始 每天十题(01)

      最近在弄flask的东西,好久没写博客的,感觉少了点什么,感觉被别人落下好多,可能渐渐的养成了写博客的习惯吧。也是自己想学的东西太多了(说白了就是基础太差了...

    小菜的不能再菜
  • Think in 递归

         网上写递归的文章可以用汗牛充栋来形容了,大多数都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可以说一直是我的某种死穴,原理...

    一心一怿
  • 关于暗链那些不得不说的事儿

    最近研究暗链比较多,也看了看最近网上的一些分析暗链的文章,发现关于暗链的文章还是比较少,内容大多不太深,比较粗糙,而且很多植入手法也比较落后了。所以我就想来写一...

    FB客服
  • Android小知识10则(下)

    sean_yang
  • RxJava2.x 创建操作符之 create & just (打怪升级版)!!!

    哈喽,朋友们,好久不见了,有段时间没推文了。从今天开始,我将计划更新 RxJava2.x 系列的文章,RxJava 是什么东西,我想也不用给大家介绍了吧。

    Vance大飞
  • 字符串比较

    网上看到有人也说是他遇到的一道笔试题,那我想这道题目其实还考过很多人。只不过当时是给我笔让我写出来,一下子懵住了,没缓过神来。写的算法时间复杂度为O(n*m),...

    meteoric
  • 第2课 python数据类型与转换

    是的,我们主要是3类数据 类型。。 3者之间可以转换,但是有条件,我们先一个个说吧。

    py3study
  • 奇怪的 Python 整数缓存机制。

    当 a 和 b 的值皆为 1024 的时候,a is b 为 False,那这里我有一个问题:当 a 和 b 的值皆为 6 的时候,a is b 的输出结果是什...

    编程文青李狗蛋
  • 聊一聊让我蒙蔽一晚上的各种常量池

    在写之前我们先来看几个问题,假如你对这些问题已经很懂了的话,那大可不用看这篇文章,如果不大懂的话,那么可以看看我的想法。

    帅地

扫码关注云+社区

领取腾讯云代金券