我开发了一个基于 Beancount 的账本托管服务 HostedBeans,欢迎大家来了解纯文本复式记账并试用我的服务。
标签 #教程

笔记:散列算法的使用场景

大家都知道散列算法,如 MD5, SHA, 但是对其具体特性恐怕都很模糊。说不准哪些用法是可靠的,哪些用法是不可靠的,只是通过加 salt, 或者反复散列的方式提高可靠性。本文将精确地讨论它们在各种使用方法下的可靠性,本文不讨论原理,只讨论使用,以下部分资料来自网络,感谢 wxy 帮忙检验文中的论断。

MD5 和 SHA 系列算法都属于同一类——我还没给这类算法找到一个足够贴切的名字。首先在大的分类上,它们都是散列算法。
散列是怎么个定义呢?典型的散列算法可以是任何一个:具有无限的定义域,且具有有限的值域的函数。甚至,宽松的广义散列算法可以是任何一个(数学意义上的)函数,因为函数本身的概念就是将一个或多个值映射到一个唯一的值。

从具体特征上来说,它们(的目标)都是足够安全的信息摘要算法。究竟何谓安全?
MD5 和 SHA 系列函数所追求的安全,在于下面两个方面。

  • 单向性
  • 抗冲突性

所谓单向性,就是指明文 M, 经过散列后的 hash(M). 从 hash(M) 无法推算出 M. 这是大部分摘要算法都具有的特征,因为大多数情况下,被摘要的信息长度要大于散列值,因为缺少信息,且值域明显小于定义域,即一个散列值会对应多个(无限个)原文,所以天然地就无法从散列值反向计算出原文。MD5 和 SHA 系列函数在单向性方面目前都还没有被发现明显的漏洞。

但是以上讨论的只是理论上的单向性,实际使用中,攻击者可以通过穷举,即暴力破解的方式推算出可能的原文。这种情况适用于已知信息原文定义域且范围较小的情况。例如如果直接对用户的密码进行散列,因为密码大多在十位字母左右,攻击者可以以很低的成本计算所有密码组合的散列值,以得到可能的信息原文。

从散列算法的角度,应对暴力破解攻击没有明显有效的手段,但也可以通过『提高计算成本』和『减少散列值长度』的方式提升单向性。

提高计算成本即通过将算法设计得更为复杂,增加更多次计算,来提高对单个信息进行散列的时间。对于正常单次散列来讲,即使增加十倍的计算时间,仍然是可以接受的。但当攻击者进行暴力破解时,同样需要原来十倍的计算时间,这个成本对攻击者来说可能无法接受。除此之外,还可以改造算法,使其只能运行于 CPU 上,无法使用显卡或专用芯片进行计算,以提高暴力破解的计算成本。
但似乎这种方式并没有被业界接受,SHA 系列函数中的新成员均减少而不是提高了计算成本。

减少散列值长度,即通过减少散列值的长度来使得多个(大量)信息原文映射到同一个散列值,使攻击者无法分辨究竟哪个才是真正的原文。
例如将散列值减少到 8 bit, 这样密码组合中 1/256 的密码都会映射到同一个散列值,根本无法分别哪个才是真正的密码。
这种方式显然很扯淡,因为这种方式会明显降低下面要提到的抗冲突性。

实际使用中,我们可以通过提高定义域范围的方式,来增强单向性。同样是散列用户密码的例子,我们可以将原来的 hash(M) 改为 hash(hash(M)). 因为 hash 的值域范围通常要比密码(约 10 位字母,即约 60 bit)大, 如 MD5 的值域是 128 bit, SHA-1 的值域是 160 bit. 因此我们通过第一次散列将第二次散列的定义域提高到了 2-4 倍,一定程度上提高了攻击者暴力破解的成本。

但是,攻击者会将 hash(hash(x)) 视为一个独立的散列函数 hash2(x), 除了正常地增加了一倍的计算时间,并没有受到我们增加作用域的影响。因此,这时我们需要引入 salt(佐料,干扰), 将散列算法改为 hash(hash(x + salt)), salt 需要与散列值一同储存。

在已知 salt 的情况下,对攻击者其实没有任何影响,因为这个函数依旧可以转换为 hash2(x + salt), 当然,有些攻击者会通过 Rainbow Table(彩虹表) 的方式进行协作和缓存,加 salt 会使他们无法使用 Rainbow Table.

Rainbow Table, 即事先对预定范围的数据进行散列,储存散列结果。然后通过数据库或者分布式技术(小型 Rainbow Table 就不需要了), 来优化从散列值到原文的『反向』查询。相似的技术还有『字典』,即收集大家常用的原文(密码,或其他短语), 代替穷举,以提高暴力破解的效率。

而在这个场景中,将 hash(hash(x + salt)) 更换为 hash(hash(x) + salt) 会获得更好的效果。因为前一种情况,攻击者可以将密码和 salt 视为一个整体来使用 Rainbow Table (虽然在 Rainbow Table 中很可能查不到这些信息); 后者则不能。因为后者是一个散列值加一个 salt, 长度已经远远超出了 Rainbow Table 的范围。当然,单纯加长 salt 也可以实现 hash(hash(x) + salt) 的效果。

在攻击者不知道 salt 的情况下,有两种选择。
一是将 hash2(x) 改为 hash2(x, salt), 这种情况适用攻击者知道 salt 的长度或范围的情况,因为这个函数有两个参数,因此破解成本与 x 或 salt 的长度呈指数函数,只要 salt 足够长,那么可以认为攻击者即使暴力破解也无能为力。
二是将第二个 hash 的输入视为一个散列值,换言之就是进行两次爆破,这种方式的计算成本相比于前一种会更高,因为暴力破解的成本同原文长度也是呈指数关系的。

所以,在未知 salt 的情况下,可以防御所有暴力破解,除非攻击者拥有极其惊人的计算力。
举个例子,如果密码为 10 位的字母,salt 为 3 位的字母,暴力破解需要相当于 Bitcoin 全网计算力的约 60 天时间。

虽然我们还拥有更强大的变种,例如:

hash(x, salt[]) = hash(hash(x + salt[1]) + hash(x + salt[2]) + ...)

但是我们认为,使用 hash(hash(x) + salt) 和足够长的 salt(大致相当于散列值的长度), 已经足够安全。

接下来,那么如何生成 salt 呢?是否有必要为每条数据(还是前面的例子,每个用户)使用单独的 salt 呢。通过前面的讨论我们看到,要保证单向性,对 salt 进行保密十分必要。如果你能够保证 salt 的绝对安全的话,那么是否使用单独的 salt 其实无关紧要。不要担心使用相同的 salt 会让攻击者找到某种规律而计算出 salt(当然前提是 salt 足够长), 因为 MD5, SHA 系列函数保证了单向性,攻击者无法从散列值推测出原文的任何信息。

至于 salt 的取值,没有什么特别的要求,基于保密的考虑,通常要使用随机生成的字符串,然后就是足够长(大约等于散列值的长度).

但我们认为仍有必要为每条数据使用单独的 salt, 这是基于下面两点考虑。
一是虽然暴力破解需要惊人的计算力,但是如果只需破解一个散列值,就可以获知所有数据的 salt, 这个破解也是值得的,也许攻击者就能够提供这么多的计算力也说不定,虽然如果你使用足够长的 salt 的话,这种可能性极小。
二是也许你不能保证 salt 的绝对安全,当你的 salt 泄漏后,每条数据使用不同的 salt 将会为攻击者制造最后一道障碍。

如果你所有的数据都使用同样的 salt, 那么攻击者在拿到数据后,只需进行一次暴力破解,即可破解出所有的数据(如果都命中了的话), 但如果你为每条数据使用不同的 salt, 那么攻击者将不得不为每条数据单独运行一次暴力破解,因为每条数据相当于在使用不同的散列函数,因为 salt 是不同的。

综上,我们认为网站的用户系统使用下面的散列即可保证安全性:

hash(hash(passwd) + salt)

其中 salt 是随机生成的,长度等于散列值长度的字符串。hash 可以是 MD5 或 SHA 系列函数。


我们接着来谈抗冲突性,所谓抗冲突性即从计算上不可能找到两个有同样散列值的原文。抗冲突性分为抗强冲突性,和抗弱冲突性。
抗强冲突性,即给定一个散列值,无法找到另一个具有同样散列值的信息原文。
抗弱冲突性,即无法找到两个具有同样散列值的信息原文。

加上单向性,这三条特性是呈阶梯状的,满足『抗弱冲突性』就一定满足『抗强冲突性』也就一定满足『单向性』同时也就满足『散列映射具有随机性和均匀性』。MD5 和 SHA 系列函数在设计上都满足这三条特征,但目前已经被发现了存在某些漏洞。

抗冲突性的主要应用场景就是为信息原文进行摘要,鉴别两段信息原文是否相同。
而攻击者的目标就是,对信息原文进行修改,然后在信息原文后(或者修改信息原文)添加给定的数据段,使其能够生成与之前相同的散列值,实现伪造数据原文。

在这种场景下攻击者是否也能够进行暴力破解呢?很难,因为在这种情况下,攻击者需要不断更换附加在信息原文后的数据,以获得和之前相同的散列值,在不理想的情况下,需要尝试所有的散列值,这个计算力被认为是无法接受的。但通过算法的一些漏洞,可以降低这个暴力破解的成本。

抗冲突性是检验散列算法设计是否优秀的重要指标,很多散列算法被淘汰都是因为抗冲突性存在漏洞。

目前 MD5 已在 2005 年被中国数学家王小云发现有抗强冲突性的漏洞,给定一个散列值,可以在几分钟内用普通计算机找到一个碰撞,即具有相同散列值的信息原文。

SHA-0 被发现漏洞可以将寻找碰撞的难度从 2^80 次暴力破解降低到 2^39 次,SHA-1 被发现漏洞可以将寻找碰撞的难度从 2^80 次降低到 2^63 次,SHA-2 系列函数还未发现漏洞。

因此目前使用 MD5 进行信息摘要并不安全,攻击者可以轻易地伪造一段散列值相同,但内容不同的原文,虽然攻击者还不能够自由地修改原文。
而 SHA-1 和 SHA-2 系列函数目前来讲是足够安全的。

利用 Bitcoin 网络进行时间区间证明

有这样一个有趣的话题,如果我在今天,2013 年 12 月 31 日,截取一张截图,那么在事后如何证明这张截图是今天所截取的呢?

同时我希望这个证明足够可靠,关键信息不掌握在少数人手中,任何人无法篡改已经证明的信息,证明不会因为某些机密信息的泄露而失效,且任何人都要可以非常方便地验证这个证明。

乍一看,简单。但细一想,又似乎不可能。

其实这个问题可以分解成两个问题:

  • 首先要证明这张图必须在某个时间之后才能被截取出来
  • 然后需要证明这张图必须在某个时间之前才能被截取出来

「证明这张图必须在某个时间之后才能被截取出来」这个问题简单,只需在截图中包含一些「只有在该时间后才能获取到的信息」,比如当天双色球的中奖号码等等。

这很好理解,如果我在截图中包含了 2013.12.31 的双色球中奖号码,就可以毫无疑问地证明这张图是在 2013.12.31 之后被截取的。

但是,这并不能妨碍我在 2014.1.1 重新截取一张截图,加入 2013.12.31 的双色球号码。所以我们还必须证明「这张图必须在某个时间之前才能被截取出来」。

解决这个问题的关键是要把这张截图的信息,永久地保存到某个可以随时查证的地方,比如我们可以让这张图片登上报纸头条,它就是永远可被查证的了,今后我们可以随时把需要证明的图片与 2013.12.31 的报纸进行对比,证明图片的真伪。

综上只需要在截图中加入当日的双色球号码,并且让它登上报纸头条即可。

——等等,你在开玩笑么。

好吧,所以我要提 Bitcoin, Bitcoin 给我们提供了这样的一个机会,它既是双色球,又是报纸。使用下文的方法进行一次证明只需花费你几分钟的时间,和一点点金钱(几分钱).

首先我们准备一张图片(记作 PIC).

pic.png

因为图片本身很大,对整张图片应用各种加密算法很不划算,所以我们要对这张图片进行散列,如果散列算法足够可靠,我们可以认为散列值就代表了这张图片(记作 HASH), 我们选用在今后很长一段时间都足够可靠的 SHA-256 算法,Bitcoin 网络使用的也是该算法。

HASH = sha256(PIC) = 896c53284a04c3df2c5fe81b1fa228d421ed6c87190da60e153562786346af75

然后我们去瞧一眼 Bitcoin 网络最新的区块(Block) 的散列值,Bitcoin 的区块大约每隔十分钟出现一个,除非你控制了世界上几乎全部的(参与 Bitcoin, 下略)的计算机,否则没有人能预测到它。同时新生成的 Block 会马上被同步到世界上所有的计算机上,事后同样没有人能够篡改。它在此起到了「双色球」的作用。

北京时间 2013.12.31 21:32 产生的最新一个区块的散列值如下,记作 BBH(Bitcoin Block Hash):

BBH = 0000000000000001149d2d7b4fcc693095fef279a1300f938e9cbeec1b43c034

然后我们将最新区块的散列值加到图片上,记作 HASH2:

HASH2 = sha256(HASH1 + BBH) = 277e31d0a5495dbeb642f459be2bcb768d728a7c1e9e008c4d6276dc938d4195

以后我们需要用 HASH2 来表示这张图片(而不是HASH), 因为 HASH2 中包含了最新区块的信息。

至此,我们完成了后向证明。

即,我们证明了「HASH2 只有在拥有 HASH(即 PIC) 且晚于北京时间 2013.12.31 21:32 的情况下才能取得」。

然后,我们使用 HASH2 作为钱包私钥,来生成对应的 Bitcoin 收款地址,因为比特币钱包私钥和收款地址本质上是一对公钥加密算法(如 RSA)的私钥和公钥,因此从公钥无法推出私钥。我们得到了这个收款地址,即证明了我们拥有私钥,再进一步证明了我们拥有 HASH2, HASH, 和 PIC.

在这个过程中,Bitcoin 网络起到了「报纸」的作用,(理想情况下)每笔交易会在下一个区块「截稿」的时候被定格,成为区块的一部分,被同步到世界上所有的计算机上,随时可以查证,又无人可以篡改。

在这一步我使用了 blockchain.info 提供的导入私钥的服务,暂时我还未查证 blockchain.info 以何种格式理解该私钥,但这不影响结论。

我由 HASH2 得出了对应的 Bitcoin 收款地址(记作 PUB):

1ALtyqivh8VgnefQ8okroJUFuNqJYFgSac

然后我向该地址汇入了 0.0001 个 Bitcoin, 以证明我在此时就已经获知了该收款地址,同时支付了 0.0001 个 Bitcoin 的交易手续费(其实可以更少一点), 该交易被收录到了于北京时间 2013.12.31 21:49 产生的新区块中。

至此,我们完成前向证明。

即,我们证明了「我在北京时间 2013.12.31 21:49 之前,就已经拥有该图片了」。

也即,我们在北京时间 2013.12.31 21:49 钱通过向 PUB 中汇款的方式,证明了我们在此刻之前已经获知了 PUB, 而获知 PUB 的前提是 获知 HASH2, HASH, 和 PIC.

至此我我们完成了整个证明过程,证明了我在北京时间 2013.12.31 21:32 - 21:49 这 17 分钟的时间段拥有这张截图,而在这之前或者之后,即使我拥有这种图片,和以上全部信息,也无法做出同样的证明,世上只此一份。

当然,你在今后出示这种图片的同时需要出示 HASH2.

或者你也可以通过某种方式把 HASH2 嵌入到原始图片中(这个工作需要你在做前向证明之前完成).

最后的福利:那个钱包里用于证明的 0.0001 Bitcoin 我没有取走,谁要就拿去吧。

妹纸说不要我搞社工库

这个博客创建于精子 7 岁第一天上学的时候,之后的十几年里精子的成长和价值观的改变是很大的。
所有的日志发布之后除了错别字都不会再修改,因此他可能并不完全同意早期日志中的观点。

简单说,社工库是这样一个神奇的东西,你只需要输入一丁点信息,如QQ号,或姓名,手机,就可以查到一个人的其他个人信息。除了QQ, 姓名,手机外,还会有身份证,住址等等,甚至包括他在各大网站的帐号和密码。

行外人可能惊奇于它是如何实现的。事实上网络比你想象得要险恶得多,各大互联网公司时刻都在收集你的个人信息。一个人,一个公司,总会有疏忽,这些资料一旦被泄露出来便无法挽回。久而久之,从这些泄露的资料中找到一个人显得十分简单。

所谓社工库就是要将这些泄露的资料汇总到一起,让查询更为方便,自动化。同时通过计算,在这些资料中挖掘出更多的关联。已经有人在这么做了,但我觉得我能做得更好,所以我开始对这个项目感兴趣。现在流行谈“大数据”,一个人掌握百G级别的数据并加以利用,是很有诱惑力的。

但这种项目的法律风险是显而易见的,我意识到,一旦我付出了努力,我绝不会放弃,也不会甘心于“内部使用”,我一定会(视图)将它做大,但相应的风险是我承受不了的。

于是我决定放弃这个项目,但我依然希望有人能够实现它,所以接下来我将描述关于这个项目我所设想到的所有技术细节,如果有人感兴趣,我可以进一步提供技术方面的指导,不感兴趣的看到这里可以洗洗睡了。

我决定给它起个代号叫做 BC.

BC计划由PHP编写,PHP是最通用,最容易部署的Web语言之一。事实上BC中,PHP的逻辑很少,大部分工作是数据库来完成的,所以使用PHP之外的其他语言来实现也没有问题。当然,如果你需要收费的话,还需要引入一个用户系统。

我决定使用三款数据库:MySQL, MongoDB, Memcached.

MySQL用于储存用户数据,和其他的一些数据量较少的信息。这是因为相比于MongoDB, MySQL还是更为稳定和成熟的。

社工库的主体由MongoDB储存,MongoDB在平时是只读的(平时需写入的数据在MySQL中).

每一份泄露出来的资料都有不同的格式,比如 .mdb, .xls, .sql, 纯文本等等。

我们必须将它们以统一的格式导入到MongoDB中,否则一切都是空谈。

我能想到的最为通用的格式是CSV, 上述各种格式都可以很轻松地被转换到CSV, 而PHP内置了对CSV的支持,更何况自行解析简单的CSV也并不复杂。

我们需要为每一份导出的CSV编写PHP脚本,以将这些数据逐条导入到MongoDB中,好在各个CSV差不多只是字段顺序上的区别。

每一份资料所包含的字段都可能不同,不过这也没有关系,反正MongoDB是无模式的。

至于查询,就很简单了,接下来我们讨论性能优化。

如果不对MongoDB进行索引,那么每次查询都需要遍历百G级别的数据,这是无法容忍的。

BC的情况略为复杂,用户名,QQ, 手机号,这些字段都可能被用作查询。

所以我建议,先使用1G左右,较为典型的数据进行实验,根据结果对查询量最高的2-3个字段添加索引。

分片是MongoDB的重要功能之一,通过分片可以将查询均衡到多台服务器,利用更多的内存来加速查询。

借助于分片,理论上BC可以实现无限扩充,至于片键,还需要通过之前的实验来选择,当然,我觉得更大的可能性是选择用户名做片键。

除了最为基本的查询,我们还可以提供更多的功能。

如通过用户名,查询到了一个手机号,我们可以自动地根据这个手机号继续查下去,挖掘出更多可能同属一个人的信息。

但这样,原来一次简单的查询就可能变成十几次查询,这将会对数据库造成极大的压力。

细想一下,如果没有新的信息(泄露资料)加入,那么查询的结果是不会改变的,所以我们要引入缓存。

Memcached是一种选择,不过实际上,使用文件来缓存已经足够。

我们缓存每一次查询的结果(可以直接是HTML输出)到文件,再有重复的查询时,我们无需经过数据库,只需访问文件缓存即可。

而每当有新的泄露资料加入时,我们要清空缓存。

对于服务器选择,我的建议是选择同在内网的若干台服务器,一台提供Web服务,其他的作为MongoDB以及缓存服务器。

选择2G内存的服务器,每台储存50G的数据。数据服务器不接入外网,Web服务器通过内网向数据服务器进行查询。

至于盈利模式可以选择会员制,以下功能都是收费点:

  • 是否可以使用索引之外的字段进行查询
  • 是否自动查找关联帐号
  • 是否仅可以查看缓存

附我前几天在邪红色论坛发的帖子:

我也想搞个社工库,大家意向如何

如题

我一毛钱的库都没有,但我有资金,有技术,有兴趣。

我对社工什么的不是很了解,我主要是对“大量的数据”感兴趣。

功能:

一个搜索框,可以搜用户名,QQ,邮箱,手机号码等。

查询结果可显示符合条件的帐号的更多信息。

同时,还会显示和这个帐号相关联的其他帐号(例如他们都使用了同一个手机号码).

同时利用这些数据我们还会搞一些公益的项目,如统计最为常用的密码等等。

盈利模式:

每月收取会员费,不限查询次数,未付费用户限每天1-10次查询。

显示关联帐号也算会员的高级功能。

上传新数据可抵会员费。

技术细节:

数据库使用MongoDB, 服务器打算用Linode的服务器,使用Linode的主要原因是数据服务器不用外网IP,直接用内网。

我会为每一个社工库写脚本,统一转入我们的数据库,进行统一的分析。

工期:

一个月出雏形,两个月正式运营。

FAQ:

Q:会员费大概多少?

A:预计如果是100G左右的数据,会员费大概在10元/月,如果数据量增加,会员费显然也要加。

Q:如何防御攻击?

A:因为数据服务器没有公网IP,不会被DDOS. 提供Web服务的服务器即使被DDOS,也可以随时再开一台新的服务器。

Q:不限查询次数的会员帐号如何防止被人互相借用,导致没人购买新的会员

A:登录帐号即可直接修改密码,对被盗帐号不予找回,看谁还敢借别人——敢借的都是真朋友,我们就不管了…

Q:邪红色有特别福利么?

A:有,等着。

精子生于 1995 年,英文 ID jysperm.

订阅推送

通过 Telegram Channel 订阅我的博客日志、产品和项目的动态:

王子亭的博客 @ Telegram


通过邮件订阅订阅我的博客日志、产品和项目的动态(历史邮件):

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-ND  授权发布。最后生成于 2023-12-20.