专栏首页架构师之路字符串比较,居然暗藏玄机(没收获你锤我)

字符串比较,居然暗藏玄机(没收获你锤我)

面试编程基本功的时候,很常见的一个题目是:

判断两个字符串是否完全相同?

画外音:先别急着退,没收获你锤我。

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

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分钟,大家有收获,转发,在看。

本文分享自微信公众号 - 架构师之路(road5858),作者:58沈剑

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

原始发表时间:2020-06-24

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 巧用CAS解决数据一致性问题

    缘起:在高并发的分布式环境下,对于数据的查询与修改容易引发一致性问题,本文将分享一种非常简单但有效的优化方法。 一、业务场景 业务场景为,购买商品的过程要对余额...

    架构师之路
  • 抢红包统计学(技术贴,知道为啥自己越抢越穷了吧)

    抢红包统计学(技术贴,知道为啥自己越抢越穷了吧) 一、引言 过年前微信群里面流行起来一种“红包接力”的玩法,大概的规则是:群里面先由一人发一个红包,然后大家开始...

    架构师之路
  • 跨公网调用的大坑与架构优化方案

    第三方接口挂掉,我们的服务会受影响么? 一、缘起与大坑 很多时候,业务需要跨公网调用一个第三方服务提供的接口,为了避免每个调用方都依赖于第三方服务,往往会抽象一...

    架构师之路
  • 使用密码记录工具keepass来保存密码

    在第一章,曾经给过您建议,密码不要保存在文档中,那样不安全,如果密码很多而且又很复杂,人的大脑是不可能很容易记住的,只能记录下来,如果不能记在文档中那记在哪里呢...

    张善友
  • 焦点访谈深谈《密码法》,腾讯李滨解密云数据加密防护之道

    在12月30日央视《焦点访谈》栏目播出的《守护安全,密码在你身边》密码法专题节目中,腾讯云安全首席架构师与业内专家一同详细解读了我国首部《密码法》的发布意义并...

    云鼎实验室
  • 关于密码测评,你必须了解的10个基本问题

    近年来,国内外大规模数据泄露事件频发,尤其是国际国内安全形势的变化,使国家、企业和个人层面做好网络与信息安全的必要性更加突出,对网络与信息安全要求日趋严格, 也...

    云数据安全
  • 为什么汉字不能当密码,你想过吗?假如用汉字做密码,又会怎样?

    日常生活中,密码的使用十分常见。基本上,登录APP、手机支付、开机解锁,都需要使用密码。密码的形式也多种多样:数字密码,指纹密码,字母密码等,却唯独没有汉字,这...

    JAVA葵花宝典
  • 10万条泄露密码里藏着爱?先看看你自己的密码安不安全吧

    导读:今年4月,某知名字母站的代码不幸“被开源”,同时泄露的还有部分用于测试的真实用户密码。然而在刚刚经历过铁路抢票平台470万个人信息泄露风波的人们看来,这些...

    华章科技
  • 最烂密码、神级密码和逆天改命密码,我已经跪下叫爸爸了!

    马上就要年终了,在这辞旧迎新的时刻,让我们一起回望2018,展望2019,看看今年的“最烂密码榜单”,这次你上榜了吗?

    FB客服
  • 我们分析了10万条泄露密码,发现了这样的套路

    上个月,某知名字母站的代码不幸“被开源”,同时泄露的还有部分用于测试的真实用户密码。然而在刚刚经历过铁路抢票平台470万个人信息泄露风波的人们看来,这些都不过是...

    CDA数据分析师

扫码关注云+社区

领取腾讯云代金券