信息安全领域就有大量刻意降低运行效率的算法啊,目的是为了防止旁路攻击和暴力破解。
所谓旁路攻击,就是不走寻常路,不靠传统的暴力攻击或者寻找漏洞。而是另辟蹊径,探测加密系统中的物理参数等信息进行破解,比如运行时间、消耗的功率、声音、电磁信号等。
举一个常见的例子:时序攻击,也就是靠分析程序在处理不同数据时所用的时间来破解密码系统。
比如最简单的字符串比较,就算不懂编程的人靠直觉也能设计出算法来:
首先比较两个字符串长度,如果不同则直接返回「否」;
然后逐个比较字符,只要有任一个不同就返回「否」;
最后全都相同的话才返回「是」。
这样有问题吗?一般情况下当然没有,但是如果在验证密码这类安全场合应用,就有隐患了。
只有在上一个字符相同的情况下才验证下一个,也就是说不同的字符串在这个算法中运行时间是不一样的。
比如原始密码是「1234567890」,那么「2234567890」只要比较一次就会返回「否」,而「1234567891」会比较 10 次,两者的运行时间几乎相差 10 倍。
采用大量数据进行测试的话,首先发现第一位是某个字符时平均比较时间会稍长一些,那就能确定密码的第一位,然后是第二位、第三位……直到试出整个密码。
如果密码特别长或特别复杂,时序攻击的效率可能比暴力破解要高很多。
字符串比较只是最简单的例子。在更复杂的、甚至暴力破解一筹莫展的情况下,时序攻击往往有奇效。比如早在 2003 年斯坦福大学的几位研究者就借助 OpenSSH 早期版本的时序漏洞,花两个小时破解了一个 1024 位 RSA 私钥。
那么如何防范时序攻击呢?
答案就是强行降低效率,在对安全有要求的场合对所有数据保证严格执行相同时间。哪怕第一个字符就不同,也得从头到尾比较一遍。
各语言官方或第三方库里基本都加上了类似功能的比较函数,比如 php 5.6 加入的 hash_equals(但它也不是严格时序安全的,因为在字符串长度不等的情况下直接返回否。好在 hash 的长度基本一致,这种不安全基本可以忽略)
除了旁路攻击之外,对暴力破解的防范也用到了降低效率的原理。
古老的 hash 算法,比如 md5、sha1,虽然不能直接破解还原,但计算和验证速度都是很快的。普通 CPU 一秒钟算个几十上百万次也不是问题,使得进行碰撞猜测或生成彩虹表(预存大量 hash 值,直接查表代替计算破解)的效率极高。常见密码的 md5 甚至不到一秒就能破解一个,完全失去了安全价值。
所以现在符合安全标准的 hash 算法,比如 bcrypt、PBKDF2,都是可以任意增加计算复杂度的「慢 hash」。只要调整参数,无论计算还是验证都能做到几百毫秒一次,极大提高了暴力破解者的成本,甚至可以说根本无法破解。
信息安全领域有大量降低效率换取安全的技术,上面举的只是两个常见的例子。计算机本来是用来提高效率的东西,在很多地方都会尽可能压缩信息、加快速度,唯独在安全面前适当牺牲速度是必要的。
对开发者和服务提供者来说,花费更多计算资源保障用户数据安全才是更负责任的行为。