分享好友

×
取消 复制
字符串比较,居然暗藏玄机(没收获你锤我)
2020-06-27 20:38:24
面试编程基本功的时候,很常见的一个题目是:
判断两个字符串是否完全相同?
画外音:先别急着退,没收获你锤我。

很多同学能够很快的写出对应的代码:

public static boolean isEqual(byte[] a, byte[] b) {

    // 先判断长度是否相同

    if (a.length != b.length) {

        // 长度不同,返回false

        return false;

    }


    // 一个一个字符,循环遍历判断

    for (int i = 0; i < a.length; i++) {

        if (a[i] != b[i]) {

            // 只要一个字符不同,返回false

            return false;

        }

    }

    // 全部字符相同,返回true

    return true;

}


代码没有问题,甚至JDK底层,也是这么实现的。

然而,MessageDigest.isEqual却被报了bug,并在JDK 1.6.0_17中被fix成了以下的版本:
public static boolean isEqual(byte[] a, byte[] b) {
    // 先判断长度是否相同
    if (a.length != b.length) {
        // 长度不同,返回false
        return false;
    }

    // 返回结果初始化
    int result = 0;
    // 一个一个字符,循环遍历判断
    for (int i = 0; i < a.length; i++) {
        // 字符串比较,采用了“按位异或”
        // 每一个比较结果,都“按位或”给了返回结果
        result |= a[i] ^ b[i];
    }
    // 返回结果为0,说明字符串全部相同,返回true
    return (result == 0);
}

初看代码,是不是觉得蒙圈?
下面我们来一步步分析一下。

首先,字符比较,升级成了“按位异或”。
这个不难理解,对于两个字符x和y:
(1)如果x == y,则有 x^y == 0
(2)如果x != y,则有 x^y != 0

其次,就代码的正确性来说,新代码并没有问题:
(1)当所有字符都相同时,result必为0,两个字符串才完全相同,返回true;
(2)只要有两个字符不同,result必不为0,一定会返回false;

同时,当输入的参数,是两个相同的字符串时,新旧算法的时间复杂度是相同的:都需要遍历每一个字符,然后返回true。

可是,当输入的参数,是两个不同的字符串时:
(1)旧版本代码,只要发现两个字符串有1个字符不同,直接返回false;
(2)新版本代码,会坚持检查完所有字符,再返回false;

这里大家就要有疑问了,新版本的代码,性能不是降低了吗?
要更彻底的解释这个问题,先得从计时攻击(Timing Attack)说起。

传统的hacker,如何破解密码?
最常见的,采用暴力穷举破解。但当密码位数较长,字符值域较广的时候,破解难度较大。

新型计时攻击(Timing Attack),是怎么破解密码?
第一步,要猜测密码的长度。

hacker不停的测试不同长度的“探测密码”,然后对执行时间进行计时

hacker可以使用:

a

aa

aaa

aaaa

...

作为探测密码。

在进行完N倍放大(执行很多遍)之后,hacker会发现,有一个长度为N的“探测密码”,执行的时间比其他时间都更长一些。以此来定位,密码的长度为N位。

为什么执行时间更长的N位“探测密码”,就代表真正的密码也是N位呢?
仔细观察旧版本的isEqual代码实现。

(1)如果探测密码与真实密码长度不同
代码执行到
(a.length != b.length)
就返回false了。

(2)如果探测密码与真实密码长度相同
代码会进入到for循环,执行到
(a[i] != b[i])
才会返回false。

正是利用了这一点点执行时间的差异,hacker就能够确定真实密码的长度。

确定了真实密码的长度之后,第二步,确定密码的第一位字符。
画外音:假设第一步探测出真实密码的长度N=4。

hacker不停的测试首位不同的“探测密码”,然后对执行时间进行计时

hacker使用:

aaaa

baaa

caaa

daaa

...

作为探测密码。

在进行完N倍放大(执行很多遍)之后,hacker会发现,有一个首位字母为x的“探测密码”,执行的时间比其他时间都更长一些。以此来定位,真实密码的首位为x。

为什么执行时间更长的,首位字母为x的“探测密码”,能够确认真实密码的首位为x呢?
仔细观察旧版本的isEqual代码实现。

(1)如果探测密码与真实密码首位字母不同
代码在for循环里,第一次
(a[i] != b[i])
就返回false了。

(2)如果探测密码与真实密码首位字母相同
代码在for循环里,第二次
(a[i] != b[i])
才会返回false。

正是利用了这一点点执行时间的差异,hacker就能够确定真实密码的首位为x。

采用相同的方法,通过N次不断的计时攻击,hacker最终能够破解出真实密码的每一位字符。

只能说,hacker太牛逼了!!!
画外音,一定有杠精说攻击不可行:
(1)已经有hacker用此方法破解了OpenSSL 0.9.7的RSA,以及基于此OpenSSL的web-server;
(2)各大语言的字符串安全比较,基本都已经升级;

如何抵御计时攻击呢?
这就要回到新版本的isEqual代码了。

新版本的isEqual,采用了一种固定时间的字符串比较方法(time-constant comparison)。

for (int i = 0; i < a.length; i++) {

    result |= a[i] ^ b[i];

}

不管探测密码与真实密码第几位不同,进行比较的时间,都是相同的。

这是一个效率与安全性的设计折衷。
画外音:非攻击者输入正确的密码时,新版本isEqual效率没有损失。

帅气不帅!!!

希望这1分钟,大家有收获,转发在看

相关文章
不敢相信,技术栈,居然被P站秒了
动静分离架构,究竟是啥?
分享好友

分享这个小栈给你的朋友们,一起进步吧。

架构师之路
创建时间:2019-12-19 10:54:22
架构师之路,沈剑和他的朋友们,聊聊职场,聊聊互联网,聊聊管理,聊聊架构,聊聊人生
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 58沈剑
    栈主
  • hwayw
    嘉宾
  • 唐川ITPUB
    嘉宾
  • 渔人
    嘉宾

小栈成员

查看更多
  • ☀️
  • 山中老狐狸
  • gaokeke123
  • 栈栈
戳我,来吐槽~