String 类型 equals比较初步理解,以及 safeEquals 比较 两种不同风格的方式

    技术2022-07-10  120

    文章部分引用自  https://mp.weixin.qq.com/s/XlBXwsCzNf_tUkTnuX3bnA

    先贴一段代码,代码点进equals源码就能看到

    public boolean equals(Object var1) { if (this == var1) { return true; } else { if (var1 instanceof String) { String var2 = (String)var1; int var3 = this.value.length; if (var3 == var2.value.length) { char[] var4 = this.value; char[] var5 = var2.value; for(int var6 = 0; var3-- != 0; ++var6) { if (var4[var6] != var5[var6]) { return false; } } return true; } } return false; } }

    首先 两个字符串用等号比较是否相等,这个没毛病。

    不相等的话,var1 instanceof String  判断是否能转换为String类型,不能就拜拜。

    接下来就是转化为String 类型字符串去比较长度了var3 == var2.value.length,长度不一样,拜拜。

    最后把他们转化为两个数组去比较每一位是否相等,不同直接返回false,相同返回true。

    ok,结束。

    另外看到一篇有意思的比较方法,大家估计都不了解,地址放这儿了https://mp.weixin.qq.com/s/XlBXwsCzNf_tUkTnuX3bnA

    代码如下,下面是大佬的理解,大家可以康康

    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; }

    首先第一步比较长度相等,没毛病,过。

    第二步定义变量,也是比较每一位是否相等,不过这里不同的是假若不想等不直接返回,他会在最外面返回与0的比较结果,

    这样的话,逻辑也可以说通,但和上面一比较是不是有些繁琐呢???

    结合方法名称 safeEquals 大家可能知道些眉目,与安全有关

    我们来看看,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 服务器的私钥。结果证明计时攻击用于进行网络攻击在实践中可行的,因此各大安全系统需要抵御这种风险。

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

    好了,大佬讲解完了,有问题可以提问。

    文章部分引用自  https://mp.weixin.qq.com/s/XlBXwsCzNf_tUkTnuX3bnA

    Processed: 0.010, SQL: 9