2102 字

从密码强度到高维诅咒

很多网站在设置密码时会提醒你使用大小写与特殊字符以提高密码强度,这样做对吗?对了一半。

首先,这句话对是因为它提示很多人避免使用简单密码。即便出现了CSDN密码泄漏问题,很多人依然固执的使用生日、电话号码、邮箱、姓名甚至是888888或123456来作为密码。这种密码很容易被破解不是因为它使用的字符简单,而是它本身有规律。就像福尔摩斯利用词频破解跳舞小人的密码一样,本身有规律的字符是可以根据经验来猜测的,这样就会有人将这些规律总结,最后通过一个“字典”提供给想破解密码的人,而破解者会优先考虑使用这个字典中的数据进行猜测,这样就会极大的提高命中率,应该说这是经验性的但却很实用。也许有人会说怎样寻找这种规律,很简单,你去下载一个CSDN泄漏的密码包去归纳总结下就知道了。但就算没有泄漏,想想自己经常用的密码就知道了。但多数负责任的网站通过脚本会直接拒绝你设置密码时使用简单密码,方法与破解一致,写个脚本检查你的密码是否与“字典”中简单密码是否一致就可以,当然“字典”是由无数本的。

其次,这句话不对的地方在于对于一个不用字典而使用暴力破解方式的人而言,666666跟aB#(d3 没有任何区别。每一个字符的可能性跑不出你的键盘上的键盘数×2(因为有上档键),也就是不超过100个,那么6位密码的可能性就是$$100^6$$种可能,这对于现代计算机而言就是几毫秒的事,但密码位数多了就不一样了,在微软的密码检查器中你不断输入1就会发现密码强度开始虽然是弱的,但最终会变为best,也就是说对于暴力破解,一个简单的长密码要比复杂的短密码安全的多。顺便说一下微软也提供了所谓强密码的建立原则,感兴趣看一下。

最后,今天真正想说的就是长密码。现在我们重新来看一下长密码安全的原因,很简单,密码必须要由字符构成,而字符的种类与字符串的长度是密码的基本属性。把这一过程再抽象一下就是我有一个集合,集合里有若干元素,每个元素有若干可能。好了,有点数学常识的就会意识到了,这不就是一个多维向量吗。而密码的安全性无过于就是多维向量的唯一性不被猜测出而已,维度数就是字符长度,每一维的属性值就是字符的种类。那么结果呢?结果就是维度越高唯一性就会越强。换句话讲,当你描述一个物体的特性越多时,这个物体就越不容易被认错。沿着这个思路走,在笛卡尔三维空间里,我们知道一个球的空间坐标后或许就可以确定这个物体是什么了,但我们并不能很好的“描述”这个球,或者说多数情况下“唯一性”只是我们主要用来区别其他物体的一个模糊概念,但从不同角度说的话会有很多判别标准,或者说为了描述一个概念,我们可以调用无数的分类特征,但这有必要吗?

没有,这就是今天要说的高维诅咒 。因为通常多数人不理会那个链接而真正理会那个链接的人又不屑于看我写的东西,我还是解释一下这个基本概念,这个词是“用来描述当(数学)空间维度增加时,分析和组织高维空间(通常有成百上千维),因体积指数增加而遇到各种问题场景”。还不够直观?打比方我去采样测定污染物,在某个10平方米的地方每隔1米取样也就100个样但如果这是个10维空间,我要在除了长、宽以外的维度的8个维度上取样就悲剧了,需要取10的10次方个点,这是什么意思呢?如果污染物只存在某100个点上那在二维空间里我都能测到还可以画一个浓度分布图(这其实多了一个维度)。但如果考虑10维空间,那这些点分布实在太稀疏了,根本看不出什么有规律的分布来,这就是高维诅咒的现象。也许你说这没什么不好,没有两片相同的树叶吗,但当我们真正去了解这个世界时,我们多数情况下是依赖自己的感觉与前人流传的知识,而所谓的知识大都来自于一种总结,这种归纳式的理论有利于我们将其内容应用到以后的生活中(这当然是一种实用主义的说法而已),而感觉也是在总结抽象一些鲜活的实例为知识而已。这样,如果我们打算去了解一个或一类事物并保证从中抽象出的知识是可重复(也就是可实用,当然我也知道罗素的养鸡场悖论,但自从哥德尔之后我们应该可以活得更豁达一些了)的,我们要收集足够的样本,但过于详细的描述却使这项工作变得异常复杂并且远离直观且根本就达不到统计规律所需要的样本数,那这个现象就没用了吗?

不会,高维诅咒对于密码设置很有意义,正因为现在多数人都会在设置密码时使用大小写或特殊字符,所以对于字典不全的破解者而言根本不用区分,把每一个字符当成一个维度,把可能的变化当成维度上的数去试就好了,在大型计算机的帮助下很快就可以了,但维度高了就不一样了,计算量是级数级的增长,当然也许对未来的计算机也不算什么了。但维度过高对于网站也是一种负担,因为存储数据也是要占用服务器资源的,而且多数人也不会去考虑搞一个很长的密码(当年DES密码设计时就有类似考虑而限制了密钥长度)。其实,这些都只是需求对技术的妥协,也许有一天,这一切都不是问题。但是,无论如何,只要我们需要交流或信息流通,加密与解密就必须跟上要求,否则我们就得适应三体人的生活。

那么倒数第二个问题的答案会不会是有必要呢?下一篇打算讨论下这个问题——从高维诅咒到因子分析。希望不会像诺莫图那样一停停一年到现在也没谱。