2023年7月31日发(作者：)
第２８卷第２期 ２０１１年２月 计算机应用与软件 Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ Ｖｏ１．２８ Ｎｏ．２ Ｆｅｂ．２０１１ 基于分布式环境下的彩虹表密码攻击 李 昕 ， 曹天杰 米国粹 邹静 （中国矿业大学计算机学院。（中国科学院软件研究所江苏徐州２２１００８） 北京１０００８０） 摘要 密码安全是被经常讨论的问题。分析了基于彩虹表的密码破解的基本原理，首先介绍了哈希链，分析了其原理和缺点， 即容易出现链冲突。随后引出彩虹链，分析了其工作原理及优势。并使用分布式计算环境对彩虹表的分布式计算、分布式存储，分 布式攻击等进行了相关研究。 关键词 密码安全分布式攻击 彩虹表 ＰＡＳＳＷＯＲＤ ＣＲＡＣＫＩＮＧ ＢＡＳＥＤ ｏＮ ＲＡＩＮＢＯＷ ＴＡＢＬＥ ＩＮ ＤＩＳＴＲＩＢＵＴＥＤ ＣｏＭＰＵＴＩＮＧ ＥＮＶＩＲｏＮＭＥＮＴ Ｌｉ Ｘｉｎ ＇ Ｃａｏ Ｔｉａｎｊｉｅ Ｍｉ Ｇｕｏｃｕｉ Ｚｏｕ Ｊｉｎｇ （ＣｈｉｎａＭｉｎｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ａｃａｄｅｍｙ ｏｆＣｏｍｐｕｔｅｒ ａｎｄ Ｓｃｉｅｎｃｅ，Ｘｕｚｈｏｕ ２２１００８，Ｊｉａｎｇｓｕ，Ｃｈｉｎａ） （Ｉｎｓｔｉｔｕｔｅ ｏｆＳｏｔｗａｒｆｅ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｉｆｎｇ １０００８０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｐａｓｓｗｏｒｄ ｓｅｃｕｒｉｔｙ ｉｓ ａ ｔｏｐｉｃ ｆｒｅｑｕｅｎｔｌｙ ｄｉｓｃｕｓｓｅｄ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ．ｗｅ ａｎａｌｙｚｅ ｔｈｅ ｒａｔｉｏｎａｌｅ ｏｆ ｐａｓｓｗｏｒｄ ｃｒａｃｋｉｎｇ ｂａｓｅｄ Ｏｎ ｒａｉｎｂｏｗ ｔａｂｌｅ．Ｆｉｒｓｔｌｙ ｗｅ ｉｎｔｒｏｄｕｃｅ ｔｈｅ ｈａｓｈ ｃｈａｉｎ，ａｎａｌｙｚｅ ｉｔｓ ｔｈｅｏｒｙ ａｎｄ ｉｔｓ ｓｈｏｒｔｃｏｍｉｎｇｓ，ｉ． ｉｔ ｉｓ ｅａｓｙ ｔｏ ｃｏｍｅ ｆｏｒｃｅ ｔｈｅ ｃｈａｉｎ ｃｏｎｆｌｉｃｔ．Ｔｈｅｎ ｗｅ ｉｎｔｒｏ— ｄｕｃｅ ｔｈｅ ｒａｉｎｂｏｗ ｃｈａｉｎ，ａｎａｌｙｚｅ ｉｔｓ ｏｐｅｒａｔｉｏｎ ｔｈｅｏｒｙ ａｎｄ ａｄｖａｎｔａｇｅｓ．Ｂｙ ｕｓｉｎｇ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔａｔｉｏｎ ｅｌｌｖｉｒｏｎｍｅｎｔ，ｃｏｒｒｅｌａｔｅｄ ｓｔｕｄｉｅｓ ｏｎ ｄｉｓ— ｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔｉｎｇ，ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ａｎｄ ｄｉｓｔｉｒｂｕｔｅｄ ａｔｔａｃｋｉｎｇ ｏｎ ｒａｉｎｂｏｗ ｔａｂｌｅ ａｒｅ ｄｉｓｃｕｓｓｅｄ． Ｋｅｙｗｏｒｄｓ Ｐａｓｓｗｏｒｄ ｓｅｃｕｒｉｔｙ Ｄｉｓｔｒｉｂｕｔｅｄ ａｔｔａｃｋｉｎｇ Ｒａｉｎｂｏｗ ｔａｂｌｅ ０引 言 Ｗｉｎｄｏｗｓ操作系统的密码安全一直以来都是引人关注的热 门话题。操作系统一般会把密码作为哈希函数的输出值来存 １ Ｒａｉｎｂｏｗ攻击简介 １．１ ｈａｓｈ链 彩虹表的基本思想来自ｈａｓｈ链。对于一个Ｑ：Ｈ（Ｐ）（日 储。哈希（ｈａｓｈ）是单向操作，即使攻击者能够读取密码的哈希 表，他也不可能仅仅通过那个哈希表来重构密码。这样，破解 ｈａｓｈ的任务就是：对于给出的一个ｑ，反算出一个Ｐ来满足ｑ＝ ｈａｓｈ（Ｐ）。通常我们能想到的两种办法，一种就是暴力破解法， 把明文Ｐ中的每一个Ｐ都算一下ｈａｓｈ（Ｐ），直到结果等于ｑ；另 一为某个ｈａｓｈ算法，如ＭＤ５），建立另一个算法Ｒ：使得Ｐ＝Ｒ （Ｑ），然后对于一个Ｐ，这样进行计算：．ｐｏ一日 ｇｌ—Ｒ— １一日 ｑ２一只— ｐ２一日－－＋ｇ３一 叶ｐ３……一月Ｌ＋ｑ（ｎ一１）一 一＋Ｐ （凡一１） 一 — ｇｎ—Ｒ 凡。 即把ｑ用Ｈ、Ｒ依次迭代运算，最后得到ｐｎ，ｎ可能比较大。 种是查表法，把每个Ｐ和对应的ｑ都记录下来，按ｑ做一下索 最后我们把ｐｏ和ｐｎ都存储下来，把其他的结果都丢弃。然后 用不同的 代入计算，得到多个这样的ｅｏｐｎ的对子。 引，到时候查一下就知道了。这两种办法理论上都是可以的，但 是前一种可能需要海量的时问，后一种需要海量的存储空问，以 我们在破解的时候，给出了一个ｑ，我们来寻找Ｐ。我们先 把ｑ作一次Ｒ运算得到一个值例如叫ｃｌ，然后把ｃｌ和每一个Ｐ 对的最后一个作比较，假如和某一个Ｐ 相等，那么有可能这个 ｐｎ所对应的Ｐ（ｎ一１）就是我们在追寻的ｑ，为了验证我们把Ｐｎ 对应的ｐ０再做一次链式计算，比对ｑｎ是否就是给出的ｑ，如果 是，很明显Ｐ（ｎ一１）就是我们在追寻的Ｐ，因为Ｐ（ｎ １）一日 至于以目前的人类资源无法实现。 举例来说，对于１４位的大小写加数字（不算特殊字符）组 成的密码的集合为（２６×２＋ｌｏ） １４：６２ １４：１．２４×１０ ２５， 即使我们每纳秒可以校验一个明文，暴力破解法也需要大概４ 亿年；如果我们采用查表法，假定Ｈａｓｈ的结果是１２８位即ｌ６字 节的，光存放ｈａｓｈ值（不存放明文Ｐ）就需要１０ ２６字节的存储 ’ｇ 。 如果不是，我们再算．ｇ— —ｃｌ一日一一Ｒ—ｃ２，再比对ｃ２ 空间。彩虹表的根本原理就是组合了暴力法和查表法，并在这 两者之中取得一个折中，用可以承受的时间和存储空间进行 破解。 收稿日期：２００９—０８—０４。中国矿业大学青年科研基金项目 （２００７Ａ０３９） 李昕，博士 主研领域：信息安全。 第２期 李昕等：基于分布式环境下的彩虹表密码攻击 ２９１ 是否是ｇｎ，如果是，那么Ｐ（ｎ一２）就可能是Ｐ；再算ｃ３、Ｄ４直到ｃ （ｎ一１），如果都不是就继续寻找，直到遍历所有的９０ｇｎ对。 总的来说，就是用一个ｐＯｐｎ对存储一个链子的数据，如果ｎ 很大，就可以大大减小存储的空间。这样带来的问题是必须作 ｎ次比对，时间更长，但是我们不需要瞬间破解，等待几秒乃至 始元素，生成一个长度为ｔ的链。如果生成密文Ｃ的密钥确实 在表中出现，肯定能在表中找到一个与链尾元素匹配的链。由 于只有链首和链尾元素被保存了，所以需要从链首元素开始重 构这个链，在Ｒ（Ｃ）之前的那个密钥就是生成密文Ｃ的密钥。 在一个有ｍ个链，每个链长度为ｔ的表中，查找一个密钥成 功的概率为： ｍ ｔ一１ ． ，几天破解一个密码都是可以接受的。 下面我们给出一个ｈａｓｈ链攻击的例子： １）假设明文空间是６个小写字母字符，而ｈａｓｈ值为３２ｂｉｔ， 则一条可能的ｈａｓｈ链可能如下： ａａｕａａａ—日一２８１ＤＡＦ４０一Ｒ＿÷ｓｇｆｎｙｄ—日＿＋９２０ＥＣＦｌＯ Ｐｍ ≥＿＿１ （１一昔 单个表的查找成功率随着表的增大而快速降低。为了得到 ～ ＿＿＋ｋｉｅｂｇｔ ２）我们只存储起始点ａａａａａａ和终点ｋｉｅｂｇｔ。对于一个给定 的ｈａｓｈ值ｈ，若想求其对应的密码，我们对ｈ反复进行Ｒ和Ｈ操 作。如果在某个 操作后，我们发现其值等于某条链的终点，于 是，我们回到其对应的起点，去重新生成该链。 ３）假如我们给的ｈａｓｈ为９２０ＥＣＦｌＯ，而９２０ＥＣＦ１０一Ｒ— ｋｉｅｂｇｔ，于是我们回到起点ａａａａａａ，重新计算ｈａｓｈ链： ａａａａａａ一日一２８１ＤＡＦ４０一只＿ｓｇｆｎｙｄ一日＿９２０ＥＣＦｌＯ ４）一旦发现ｈａｓｈ值９２０ＥＣＦｌＯ，显然其对应的密码就 是ｓＪｎｙｄ。 ５）但假如从ａａａａａａ重新恢复的ｈａｓｈ链中没有９２０ＥＣＦ１０， 于是我们继续对９２０ＥＣＦｌＯ做Ｒ和日操作，然后去匹配彩虹表中 别的ｈａｓｈ链。 ６）在对ｈ进行Ｒ和 操作 次后（假设ｋ为ｈａｓｈ链长），若 所有的ｈａｓｈ链都不匹配，则无法恢复密码。 但ｈａｓｈ链有一个明显的缺点，即在生成链的过程中可能出 现，从不同的链首开始得到相同的元素。这是由于映射函数 （ｒｅｄｕｃｔｉｏｎ ｆｕｎｃｔｉｏｎ）Ｒ是密文空间（大空间）到密钥空间（小空 间）的一个映射。研究表明，表越大，出现这种链碰撞的可能性 越高。这样就减少了表所能覆盖的密钥的大小。如第二条链的第 三个值和第七条链的第二个值相等，则其链后面的元素完全相 等，尽管这两条链的终点不等。 １．２彩虹链 为了更好地描述彩虹链，我们先给出形式化说明。 给定一个明文尸ｎ和与之对应的密文 ，试图找到用密码算 法Ｓ加密 时所需要的密钥ｋ Ｎ（Ｎ为密钥空间），使得： Ｃｏ＝５ （ ） 我们使用所有可能的ｋ ｅ Ｎ的密钥去加密 ，这样就预计 算出所有可能的密文。而所有的密文是按链的方式组织的，在 内存中只保存链首和链尾，这样就表现出了时间和空间的折中 策略。这个链是使用映射函数 来生成的，映射函数将一个密 文映射到一个密钥。链的组织如下： ｋ —二一＿＿＋ Ｃ — ｋ ＋ｌ 用八ｋ）来表示Ｒ（Ｓ （Ｐｏ）），这样就得到了一个密钥的链： ｋ 上 上 一… 生成一个表，表中包含ｍ个链，每个链的长度为ｔ，但是为 了节约空间，只保存这ｍ个链的链首和链尾元素。给定一个密 文Ｃ，在这个表中找出生成这个密文的密钥。首先以Ｒ（Ｃ）为开 更高的成功率，我们采用多个表，每个表使用不同的映射函数。 这样ｚ个表成功率表示为： ． ｍ ｔ—１ ． … ≥１一（１一万１ （１一号）ｐ ） 上面方法的主要局限是，当在一个表中出现碰撞时必须进 行合并。０ｅｃｈｓｌｉｎ提出了一种被称之为ｒａｉｎｂｏｗ链的新链，在这 种链中即使出现碰撞时也不需要合并。此方法在ｒａｉｎｂｏｗ链中 使用了连续的映射函数，即从映射函数１到映射函数ｔ一１。这 样一来，两个链碰撞时，合并仅发生在两个链的对应位置上元素 相等的情况下。如果位置不相同，因为后面使用了不同的映射 函数，所以不需要合并。对于一个长度为ｔ的链，碰撞发生并需 要合并的概率为１／ｔ。 对于一个ｍ×ｔ的彩虹表，查找成功的概率为： ＝１－兀（１一 ）ｍ。＝ｍ ＝Ｎ（Ｊ ） 实际上ｔ个大小为ｍ×ｔ的经典表和一个大小为ｍｔ×ｔ的彩 虹表的查询成功率相当。在两种方法中，表都覆盖了ｍｔ 个密 钥，使用了ｔ个不同的映射函数。他们的对应关系如图１所示。 ？ 图１ 经典表与彩虹表对应关系 在彩虹表中查找密钥采用如下的方式进行：首先将Ｒ 一 应 用到密文上得到结果，然后将结果与彩虹表中的链尾匹配。如 果找到匹配了，可以从链首重构整个链。如果找不到，我们接着 对结果应用Ｒ 一 一 ，然后将结果与彩虹表中倒数第二个元素 进行匹配。下面接着对结果应用 一 一 一。，以此类推。整 ．，． １、 个过程中需要计算次数是 ，这只是经典表的一半左右。 顺便指出彩虹表的出处即为在彩虹表的每一列采用了不同的 ｒｅｄｕｃｔｉｏｎ函数的缘故。 图２所示给出一个彩虹链攻击的例子： １）假设我们要破解的密码ｈａｓｈ是“ｒｅ３ｘｅｓ”，首先对该值用 ２９２ 计算机应用与软件 ２０１１血 臣口鐾＿① —● 回 圈Ｈ ■ 融 ． ＳＴＯＰ 吕 －＠ 图２彩虹表攻击例子 Ｒ３运算处理一下，得到明文“ｒａｍｂｏ”。然后看是否在每一个链 的终点有明文“ｒａｍｂｏ”出现。 ２）如果ｒａｍｂｏ没有出现在表的任一链的终点，则继续用 Ｒ２运算处理，紧跟着用Ｈ和Ｒ３运算处理，这次算得的 “ｌｉｎｕｘ２３”恰好在最后一个链的终点出现。如果没出现，则反复 应用类似运算处理。 ３）从最后一个链的起点“ｐａｓｓｗｄ”恢复整条链，我们看到 “ｒｅ３ｘｅｓ”是“ｃｕｌｔｕｒｅ”的ｈａｓｈ结果，所以，密码就是“ｃｕｌｔｕｒｅ”。 ２ Ｒａｉｎｂｏｗ攻击的分布式设计 彩虹表攻击有三部分可考虑分布式。 １）Ｒａｉｎｂｏｗ表的分布式计算 服务器仅仅分发给客户端产生彩虹表时所需要的各项参 数，然后由客户端来进行彩虹表计算。这样做有如下两点好处： ａ）服务器可以根据需要预计算出各项参数。 服务器端根据所需计算的彩虹表的各项参数及客户端计算 能力，来决定每个客户端所需产生的彩虹表的参数，以及达到某 个成功率所需要产生的彩虹表的个数。设ｍ为每张表中彩虹 链个数，ｔ为彩虹链长度，ｚ为彩虹表个数，则各项参数之问的关 系满足如下方程： ～ Ｐ ＝ｌ—ｎ（‘ ｌ １一等）ｍ ：ｍ ’ ｍ （ｍ ＋Ｌ＝＾ （１一ｅ－ ）Ｐ… ≥１一（１一Ｐ 。 ） 这样，服务器根据想要达到的成功率让每个吝户端产生不 同表数、不同链数的彩虹表，每个彩虹表由不同的随机值开始生 成。尽管各个表之间可能存在冗余，但总的来说，由公式可推 出，表越多，成功率越大。 ｂ）在计算过程中，客户端不需要与服务器进行交互。 Ｊ．Ｂｏｍｔ提出了一种基于ＤＰ（ｄｉｓｔｉｎｇｕｉｓｈｅｄ ｐｏｉｎｔｓ）技术的分 布式攻击，由于ＤＰ技术固有的缺点，客户端在产生彩虹表时要 与服务器交互，来验证ＤＰ的有效性。在基于彩虹表的分布式 攻击中客户端在计算彩虹表的过程中不需要与服务器交互，减 少了交互的代价。． ２）Ｒｍｎｂｏｗ表的分布式存储 当前国际上也有分布式计算彩虹表的项目，叫做ＯｉｓｔｒＲＴｇｅｎ。 它的原理是客户端计算一个８兆的彩虹表，然后回传给服务器，由 服务器将其保存在某个安全的地方。这种方法的缺点是： ａ）传输大量数据浪费时间； ｂ）由于彩虹表涉及到敏感信息，在传输过程中还需要进行 加密。 我们先择将彩虹表保存在客户端本地，供后继分布式查询 时使用。这种方法能适用于计算客户端相对比较稳定的网络， 即客户端断开服务器的概率比较低的网络。 ３）Ｒａｉｎｂｏｗ的分布式攻击 分布式攻击可以采用两种方式，一种是由服务器负责分发 已经计算好的彩虹表，客户端接收到彩虹表后进行彩虹表攻击， 这样做有以下缺点： ａ）在应用中，服务器存有大量数据，可能成为整个系统的 瓶颈；再者，彩虹表的网络传输代价很高。 ｂ）这些彩虹表，如果在网络传输中被篡改，有可能将导致 攻击失败，这又增加了加密和解密的代价。 所以我们采用了服务器只负责传输相应参数，即待破解密 码的哈希值，客户端再收到指令后，先进行攻击，如果攻击失败， 则再根据需要产生部分彩虹表，继续查找。这样做可能会增加 攻击的平均时间。一旦某个客户端找到密码，通知给服务器。 服务器然后通知其他客户端密码已找到，攻击结束。在实际攻 击中，由于彩虹表之间存在冗余，有可能多个客户端都会找密 码。这样服务器取第一个找到密码的结果即可。 ３实验结果 ３．１ Ｒａｉｎｂｏｗ分布式计算和存储实验 分布式计算和存储测试所用的参数如下： ：［ＡＢＣＤＥＦ－ ＧＨＩＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺＯ１２３４５６７８９］； ；［ＡＢＣＤＥＦＧＨＩ－ ＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺ］，分别表示要产生密钥的字符集。令 ｍ为每张表中彩虹链个数，ｔ为彩虹链长度，Ｚ为彩虹表个数。 我们对生成基于 算法的密钥长度可为１—７位字符的彩虹表 的生成进行了单机版和分布式版的测试。数据参数如表１、表２ 所示。 表１ Ｒａｉｎｂｏｗ分布式存储测试数据参数 表２ Ｒａｉｎｂｏｗ分布式存储测试结果 实验表明，对于大的彩虹表，用单机生成不仅速度慢，而且 因为彩虹表一般很大，很难存储。同时由于对于太大的文件，操 作系统很难把它一次性读到内存，这样在进行查找时，给系统造 成很大负担。我们用５个计算节点同时生成彩虹表，得到了很 好的加速比。同时，也缓解了单机上存过大彩虹表的问题。 ３．２ Ｒａｉｎｂｏｗ分布式攻击实验 分布式攻击实验采用第三方提供的Ｒａｉｎｂｏｗ表，Ｒａｉｎｂｏｗ表 的各参数如表３所示。 第２期 李昕等：基于分布式环境下的彩虹表密码攻击 ２９３ 表３ Ｒａｉｎｂｏｗ分布式攻击实验数据 实验中，我们使用了字母、数字、包括特殊字符的密钥空间， 这基本涵盖了一般的密码所包含的字符。结果表明，用５台 Ｃｏｒｅ Ｄｕｏ２．４Ｇ的计算机，对于任意１４位以内的ＷｉｎｄｏｗｓＸＰ系 统密码都可以在平均５分钟以内破解出来。这里之所以是１４ 位以内的密码，是因为ＷｉｎｄｏｗｓＸＰ的密码ｈａｓｈ算法是７位一个 单元进行的。 ４结束语 本文对基于彩虹表的分布式密码攻击进行了探讨，分析了 彩虹表的基本原理，即ｈａｓｈ链和彩虹链。并使用分布式计算环 境对彩虹表的分布式存储、分布式攻击等进行了相关研究。实 验表明，彩虹表对于密码破解的确是强有力的武器。不过，如果 在生成哈希表之前，给密码加个唯一的前缀，然后再ｈａｓｈ。这 样，攻击者就无法用彩虹表来攻击了。因为“密码”和“加了前 缀的密码”生成的哈希结果是不匹配的。除非知道所有的哈希 表都加了这个前缀。即使真的知道，也得专门针对你的机器生 成一个定制的彩虹表。 另外基于ＧＰＵ的计算日益成熟，在一台普通ＰＣ上辅以 ＮＶｉｄｉａ ＣＵＤＡ技术，对于ＮＴＬＭ算法可以达到最高每秒１０３， ８２０，０００，０００次明文尝试（超过一千亿次），对于广泛使用的 ＭＤ５也接近一千亿次。下一步的研究计划是把具有ＧＰＵ计算 能力的计算节点整和到系统中来，以增强系统的计算能力。 参考文献 ［１］Ｈｅｌｌｍａｎ Ｍ Ｅ．Ａ ｃｒｙｐｔａｎａｌｙｔｉｃ ｔｉｍｅ－ｍｅｍｏｒｙ ｔｒａｄｅ ｏｆｆ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ— ａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ＩＴ－２６，１９８０：４０１—４０６． ［２］Ｏｅｃｈｓｌｉｎ Ｐ．Ｍａｋｉｎｇ ａ Ｆａｓｔｅｒ Ｃｒｙｐｔａｎａｌｙｔｉｃ Ｔｉｍｅ—Ｍｅｍｏｒｙ Ｔｒａｄｅ—Ｏｆｆ［Ｊ］， Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｖｏｌｕｍｅ ２７２９，２００３：６１７—６３０． ［３］Ｂｏｍｔ Ｊ，Ｐｒｅｎｅｅｌ Ｂ，Ｖａｎｄｅｗａｌｌｅ Ｊ．Ｏｎ ｔｉｍｅ—ｍｅｍｏｒｙ ｔｒａｄｅｏｆｆ ｂｅｔｗｅｅｎ ｅｘ— ｈａｕｓｔｉｖｅ ｋｅｙ ｓｅａｒｃｈ ａｎｄ ｔａｂｌｅ ｐｒｅｃｏｍｐｕｔａｔｉｏｎ［Ｊ］．Ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅ— ｏｒｙ ｉｎ ｔｈｅ Ｂｅｎｅｌｕｘ，１９９８：１１１—１１８． ［４］Ｃｏｓｎａｒｄ Ｍ，ＰＨＩＬＩＰＰＥ Ｊ Ｌ．Ｄｉｓｔｒｉｂｕｔｅｄ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｅｃｉｐｈｅｒｉｎｇ［Ｊ］． ［Ｓ．１．］：［Ｓ．ｎ．］，２００７． ［５］ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｒａｉｎｂｏｗ—ｔａｂｌｅｓ． （上接第２８３页） ／／教师冲突检测每冲突一次Ｃｏｎｆｌｉｃｔ＋１。 ｉｆ ＦＡｒｒａｎｇｅ［Ｊ］［ｎ］．１ｎｆｏ．ＴｅａｃｈｅｒｌＤ＝ＦＡｒｒａｎｇｅ［ｉ］［ｎ］． Ｉｎｆｏ．ＴｅａｃｈｅｒＩＤ ｔｈｅｎ｛ ＦＡｒｒａｎｇｅ［ｊ］［ｎ］．Ｃｏｎｆｌｉｃｔ：＝ＦＡｒｒａｎｇｅ［Ｊ儿ｎ］．Ｃｏｎｆｌｉｃｔ＋１； ＦＡｘＴａｎｇｅ［ｉＨ ｎ］．Ｃｏｎｆｌｉｃｔ：＝ＦＡｒｒａｎｇｅ［ｉ］［ｎ］．Ｃｏｎｆｌｉｃｔ＋１； ／／班级冲突检测每冲突一次Ｃｏｎｆｌｉｃｔ＋１。 ｉｆＧｒｏｕｐＣｏｎｆｌｉｃｔ（ＦＡｒｒａｎｇｅ［ｉ］［ｎ］，ＦＡ￣ａｎｇｅ［Ｊ］［ｎ ）ｔｈｅｎ ＦＡ￣ａｎｇｅ［ｊ］［ｎ］．Ｃｏｎｆｌｉｃｔ：：ＦＡｒｒａｎｇｅ［ｊ］【ｎ］．Ｃｏｎｆｌｉｃｔ＋１； ＦＡｒｒａｎｇｅ［ｉ］［ｎ］．Ｃｏｎｆｌｉｃｔ：＝ＦＡｒｒａｎｇｅ［ｉ¨【ｎ］．Ｃｏｎｆｌｉｃｔ＋１； Ｒｅｓｕｌｔ： Ｔｒｉｌｅ： ｏｆｒ Ｆｈｅｍ ｄｏ Ｒｅｓｕｌｔ：＝Ｒｅｓｕｈ ａｎｄ（ＦＩｔｅｍ［ｉ］．Ｃｏｎｆｌｉｃｔ＝０）； ｆ ｎｃｔｉｏｎ Ｅｎｄ ４．５ 交叉和变异（Ｍｕｔａｔｅ／ＣｒｏｓｓＯｖｅｒ） 交叉和变异是遗传算法的重点，关于它们的选择算法更是 关键之处。许多排课算法就是按照“物竞天择、适者生存”的思 想，选择出适应度高的染色体进行交叉变异，最终使排课问题得 以成功解决。而本算法在进行时间冲突检测时发现，如果一个 课程项在本时问列上冲突值高，那么其相关的课程多存在于这 个时间列，相对应其它时间列的冲突情况可能就会减小。按照 这一思想，本算法在交叉时选择每个时间列上冲突值不为零的 最大课程项，然后针对这些项进行交叉。 实际上这种交叉变异算法也是经过多种算法对比后决定 的，其交叉率并不高（最大只有１／ＦＥｎａｂｌｅＣｏｕｎｔ，最小可能为 ０），但是其交叉效率令人满意。变异操作也针对有冲突的课程 项进行，测试发现取值不宜过小，确定为５０％。 定义函数原型： ｐｒｏｃｅｄｕｒｅ Ｍｕｔａｔｅ； ｐｒｏｃｅｄｕｒｅ ＣｒｏｓｓＯｖｅｒ； 算法伪码如下： ｐｒｏｃｅｄｕｒｅ ＣｒｏｓｓＯｖｅｒ ｏｆｒ ＦＥｎａｂｌｅＴｉｍｅ ｄｏ ｛ ＧｅｔＭａｘ Ａｈｅｍ．Ｃｏｎｆｌｉｃｔ； Ａｄｄ Ａｈｅｍ ｔｏ ＰＭａｘ；｝ ｏｆｒ ＰＭａｘ ｄｏ Ｅｘｃｈａｎｇｅ（ＰＭａｘ［ｉ］，ＰＭａｘ［ｉ＋１］）； ｐｒｏｃｅｄｕｒｅ Ｅｎｄ ｐｒｏｃｅｄｕｒｅ Ｍｕｔａｔｅ ｆｏｒ Ｆｈｅｍ ｄｏ ｉｆ Ｆｈｅｍ［ｉ］．Ｃｏｎｆｌｉｃｔ＜＞０ ｔｈｅｎ ｉｆ Ｒａｎｄｏｍ（１００）＜５０ ｔｈｅｎ Ａｒｒａｎｇｅｌｔｅｍ（Ｆｌｔｅｍ［ｉ］）； ｐｒｏｃｅｄｕｒｅ Ｍｕｔａｔｅ Ｅｎｄ ５结束语 计算机排课可以提高排课质量，把教务工作者从繁重的工 作中解脱出来，而且课表中的信息也非常清楚，对于优化学生在 校学习进程，评估每位教师对教学的贡献，领导合理决策等都具 有重要的意义，必将会大大推动教学的良性循环。 参考文献 ［１］汪祖柱，程家兴，刘慧婷．基于遗传算法求解时间表问题［Ｊ］．计算 机工程与应用，２００４（２４）：９２—９４． ［２］吴政，汪峰坤．基于遗传算法的排课系统［Ｊ］．计算机与数字工程， ２００８（１１）：２９—３２． ［３］袁礼海，宋建社，毕义明，等．混合遗传算法及与标准遗传算法对比 研究［Ｊ］．计算机工程与应用，２００３（１２）：１２３—１２４． ［４］周洪伟，原锦辉，张来顺．遗传算法“早熟”现象的改进策略［Ｊ］．计 算机工程，２００７（１９）：２０１—２０３． ［５］Ｃｈｕ Ｐ Ｃ，Ｂｅａｓｌｅｙ．Ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ａｓｓｉｇｎｍｅｎｔ ｐｒｏｂｌｅｍ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎ，１９９５：２０—２２． ［６］滕姿，邓辉文，杨久俊．基于遗传算法的排课系统的设计与实现 ［Ｊ］．计算机应用，２００７（２７）：１９９—２０４． ［７］冯冬表，王非，马雁．遗传算法中选择交叉策略的改进［Ｊ］．计算机 工程，２００８（１９）：１８９—１９１． ［８］胡义伟，郑金华，谢勇．遗传算法在大学排课系统中的应用［Ｊ］．计 算机系统应用，２００８（０９）：６６—６９．
2023年7月31日发(作者：)
第２８卷第２期 ２０１１年２月 计算机应用与软件 Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ Ｖｏ１．２８ Ｎｏ．２ Ｆｅｂ．２０１１ 基于分布式环境下的彩虹表密码攻击 李 昕 ， 曹天杰 米国粹 邹静 （中国矿业大学计算机学院。（中国科学院软件研究所江苏徐州２２１００８） 北京１０００８０） 摘要 密码安全是被经常讨论的问题。分析了基于彩虹表的密码破解的基本原理，首先介绍了哈希链，分析了其原理和缺点， 即容易出现链冲突。随后引出彩虹链，分析了其工作原理及优势。并使用分布式计算环境对彩虹表的分布式计算、分布式存储，分 布式攻击等进行了相关研究。 关键词 密码安全分布式攻击 彩虹表 ＰＡＳＳＷＯＲＤ ＣＲＡＣＫＩＮＧ ＢＡＳＥＤ ｏＮ ＲＡＩＮＢＯＷ ＴＡＢＬＥ ＩＮ ＤＩＳＴＲＩＢＵＴＥＤ ＣｏＭＰＵＴＩＮＧ ＥＮＶＩＲｏＮＭＥＮＴ Ｌｉ Ｘｉｎ ＇ Ｃａｏ Ｔｉａｎｊｉｅ Ｍｉ Ｇｕｏｃｕｉ Ｚｏｕ Ｊｉｎｇ （ＣｈｉｎａＭｉｎｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ａｃａｄｅｍｙ ｏｆＣｏｍｐｕｔｅｒ ａｎｄ Ｓｃｉｅｎｃｅ，Ｘｕｚｈｏｕ ２２１００８，Ｊｉａｎｇｓｕ，Ｃｈｉｎａ） （Ｉｎｓｔｉｔｕｔｅ ｏｆＳｏｔｗａｒｆｅ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｉｆｎｇ １０００８０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｐａｓｓｗｏｒｄ ｓｅｃｕｒｉｔｙ ｉｓ ａ ｔｏｐｉｃ ｆｒｅｑｕｅｎｔｌｙ ｄｉｓｃｕｓｓｅｄ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ．ｗｅ ａｎａｌｙｚｅ ｔｈｅ ｒａｔｉｏｎａｌｅ ｏｆ ｐａｓｓｗｏｒｄ ｃｒａｃｋｉｎｇ ｂａｓｅｄ Ｏｎ ｒａｉｎｂｏｗ ｔａｂｌｅ．Ｆｉｒｓｔｌｙ ｗｅ ｉｎｔｒｏｄｕｃｅ ｔｈｅ ｈａｓｈ ｃｈａｉｎ，ａｎａｌｙｚｅ ｉｔｓ ｔｈｅｏｒｙ ａｎｄ ｉｔｓ ｓｈｏｒｔｃｏｍｉｎｇｓ，ｉ． ｉｔ ｉｓ ｅａｓｙ ｔｏ ｃｏｍｅ ｆｏｒｃｅ ｔｈｅ ｃｈａｉｎ ｃｏｎｆｌｉｃｔ．Ｔｈｅｎ ｗｅ ｉｎｔｒｏ— ｄｕｃｅ ｔｈｅ ｒａｉｎｂｏｗ ｃｈａｉｎ，ａｎａｌｙｚｅ ｉｔｓ ｏｐｅｒａｔｉｏｎ ｔｈｅｏｒｙ ａｎｄ ａｄｖａｎｔａｇｅｓ．Ｂｙ ｕｓｉｎｇ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔａｔｉｏｎ ｅｌｌｖｉｒｏｎｍｅｎｔ，ｃｏｒｒｅｌａｔｅｄ ｓｔｕｄｉｅｓ ｏｎ ｄｉｓ— ｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔｉｎｇ，ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ａｎｄ ｄｉｓｔｉｒｂｕｔｅｄ ａｔｔａｃｋｉｎｇ ｏｎ ｒａｉｎｂｏｗ ｔａｂｌｅ ａｒｅ ｄｉｓｃｕｓｓｅｄ． Ｋｅｙｗｏｒｄｓ Ｐａｓｓｗｏｒｄ ｓｅｃｕｒｉｔｙ Ｄｉｓｔｒｉｂｕｔｅｄ ａｔｔａｃｋｉｎｇ Ｒａｉｎｂｏｗ ｔａｂｌｅ ０引 言 Ｗｉｎｄｏｗｓ操作系统的密码安全一直以来都是引人关注的热 门话题。操作系统一般会把密码作为哈希函数的输出值来存 １ Ｒａｉｎｂｏｗ攻击简介 １．１ ｈａｓｈ链 彩虹表的基本思想来自ｈａｓｈ链。对于一个Ｑ：Ｈ（Ｐ）（日 储。哈希（ｈａｓｈ）是单向操作，即使攻击者能够读取密码的哈希 表，他也不可能仅仅通过那个哈希表来重构密码。这样，破解 ｈａｓｈ的任务就是：对于给出的一个ｑ，反算出一个Ｐ来满足ｑ＝ ｈａｓｈ（Ｐ）。通常我们能想到的两种办法，一种就是暴力破解法， 把明文Ｐ中的每一个Ｐ都算一下ｈａｓｈ（Ｐ），直到结果等于ｑ；另 一为某个ｈａｓｈ算法，如ＭＤ５），建立另一个算法Ｒ：使得Ｐ＝Ｒ （Ｑ），然后对于一个Ｐ，这样进行计算：．ｐｏ一日 ｇｌ—Ｒ— １一日 ｑ２一只— ｐ２一日－－＋ｇ３一 叶ｐ３……一月Ｌ＋ｑ（ｎ一１）一 一＋Ｐ （凡一１） 一 — ｇｎ—Ｒ 凡。 即把ｑ用Ｈ、Ｒ依次迭代运算，最后得到ｐｎ，ｎ可能比较大。 种是查表法，把每个Ｐ和对应的ｑ都记录下来，按ｑ做一下索 最后我们把ｐｏ和ｐｎ都存储下来，把其他的结果都丢弃。然后 用不同的 代入计算，得到多个这样的ｅｏｐｎ的对子。 引，到时候查一下就知道了。这两种办法理论上都是可以的，但 是前一种可能需要海量的时问，后一种需要海量的存储空问，以 我们在破解的时候，给出了一个ｑ，我们来寻找Ｐ。我们先 把ｑ作一次Ｒ运算得到一个值例如叫ｃｌ，然后把ｃｌ和每一个Ｐ 对的最后一个作比较，假如和某一个Ｐ 相等，那么有可能这个 ｐｎ所对应的Ｐ（ｎ一１）就是我们在追寻的ｑ，为了验证我们把Ｐｎ 对应的ｐ０再做一次链式计算，比对ｑｎ是否就是给出的ｑ，如果 是，很明显Ｐ（ｎ一１）就是我们在追寻的Ｐ，因为Ｐ（ｎ １）一日 至于以目前的人类资源无法实现。 举例来说，对于１４位的大小写加数字（不算特殊字符）组 成的密码的集合为（２６×２＋ｌｏ） １４：６２ １４：１．２４×１０ ２５， 即使我们每纳秒可以校验一个明文，暴力破解法也需要大概４ 亿年；如果我们采用查表法，假定Ｈａｓｈ的结果是１２８位即ｌ６字 节的，光存放ｈａｓｈ值（不存放明文Ｐ）就需要１０ ２６字节的存储 ’ｇ 。 如果不是，我们再算．ｇ— —ｃｌ一日一一Ｒ—ｃ２，再比对ｃ２ 空间。彩虹表的根本原理就是组合了暴力法和查表法，并在这 两者之中取得一个折中，用可以承受的时间和存储空间进行 破解。 收稿日期：２００９—０８—０４。中国矿业大学青年科研基金项目 （２００７Ａ０３９） 李昕，博士 主研领域：信息安全。 第２期 李昕等：基于分布式环境下的彩虹表密码攻击 ２９１ 是否是ｇｎ，如果是，那么Ｐ（ｎ一２）就可能是Ｐ；再算ｃ３、Ｄ４直到ｃ （ｎ一１），如果都不是就继续寻找，直到遍历所有的９０ｇｎ对。 总的来说，就是用一个ｐＯｐｎ对存储一个链子的数据，如果ｎ 很大，就可以大大减小存储的空间。这样带来的问题是必须作 ｎ次比对，时间更长，但是我们不需要瞬间破解，等待几秒乃至 始元素，生成一个长度为ｔ的链。如果生成密文Ｃ的密钥确实 在表中出现，肯定能在表中找到一个与链尾元素匹配的链。由 于只有链首和链尾元素被保存了，所以需要从链首元素开始重 构这个链，在Ｒ（Ｃ）之前的那个密钥就是生成密文Ｃ的密钥。 在一个有ｍ个链，每个链长度为ｔ的表中，查找一个密钥成 功的概率为： ｍ ｔ一１ ． ，几天破解一个密码都是可以接受的。 下面我们给出一个ｈａｓｈ链攻击的例子： １）假设明文空间是６个小写字母字符，而ｈａｓｈ值为３２ｂｉｔ， 则一条可能的ｈａｓｈ链可能如下： ａａｕａａａ—日一２８１ＤＡＦ４０一Ｒ＿÷ｓｇｆｎｙｄ—日＿＋９２０ＥＣＦｌＯ Ｐｍ ≥＿＿１ （１一昔 单个表的查找成功率随着表的增大而快速降低。为了得到 ～ ＿＿＋ｋｉｅｂｇｔ ２）我们只存储起始点ａａａａａａ和终点ｋｉｅｂｇｔ。对于一个给定 的ｈａｓｈ值ｈ，若想求其对应的密码，我们对ｈ反复进行Ｒ和Ｈ操 作。如果在某个 操作后，我们发现其值等于某条链的终点，于 是，我们回到其对应的起点，去重新生成该链。 ３）假如我们给的ｈａｓｈ为９２０ＥＣＦｌＯ，而９２０ＥＣＦ１０一Ｒ— ｋｉｅｂｇｔ，于是我们回到起点ａａａａａａ，重新计算ｈａｓｈ链： ａａａａａａ一日一２８１ＤＡＦ４０一只＿ｓｇｆｎｙｄ一日＿９２０ＥＣＦｌＯ ４）一旦发现ｈａｓｈ值９２０ＥＣＦｌＯ，显然其对应的密码就 是ｓＪｎｙｄ。 ５）但假如从ａａａａａａ重新恢复的ｈａｓｈ链中没有９２０ＥＣＦ１０， 于是我们继续对９２０ＥＣＦｌＯ做Ｒ和日操作，然后去匹配彩虹表中 别的ｈａｓｈ链。 ６）在对ｈ进行Ｒ和 操作 次后（假设ｋ为ｈａｓｈ链长），若 所有的ｈａｓｈ链都不匹配，则无法恢复密码。 但ｈａｓｈ链有一个明显的缺点，即在生成链的过程中可能出 现，从不同的链首开始得到相同的元素。这是由于映射函数 （ｒｅｄｕｃｔｉｏｎ ｆｕｎｃｔｉｏｎ）Ｒ是密文空间（大空间）到密钥空间（小空 间）的一个映射。研究表明，表越大，出现这种链碰撞的可能性 越高。这样就减少了表所能覆盖的密钥的大小。如第二条链的第 三个值和第七条链的第二个值相等，则其链后面的元素完全相 等，尽管这两条链的终点不等。 １．２彩虹链 为了更好地描述彩虹链，我们先给出形式化说明。 给定一个明文尸ｎ和与之对应的密文 ，试图找到用密码算 法Ｓ加密 时所需要的密钥ｋ Ｎ（Ｎ为密钥空间），使得： Ｃｏ＝５ （ ） 我们使用所有可能的ｋ ｅ Ｎ的密钥去加密 ，这样就预计 算出所有可能的密文。而所有的密文是按链的方式组织的，在 内存中只保存链首和链尾，这样就表现出了时间和空间的折中 策略。这个链是使用映射函数 来生成的，映射函数将一个密 文映射到一个密钥。链的组织如下： ｋ —二一＿＿＋ Ｃ — ｋ ＋ｌ 用八ｋ）来表示Ｒ（Ｓ （Ｐｏ）），这样就得到了一个密钥的链： ｋ 上 上 一… 生成一个表，表中包含ｍ个链，每个链的长度为ｔ，但是为 了节约空间，只保存这ｍ个链的链首和链尾元素。给定一个密 文Ｃ，在这个表中找出生成这个密文的密钥。首先以Ｒ（Ｃ）为开 更高的成功率，我们采用多个表，每个表使用不同的映射函数。 这样ｚ个表成功率表示为： ． ｍ ｔ—１ ． … ≥１一（１一万１ （１一号）ｐ ） 上面方法的主要局限是，当在一个表中出现碰撞时必须进 行合并。０ｅｃｈｓｌｉｎ提出了一种被称之为ｒａｉｎｂｏｗ链的新链，在这 种链中即使出现碰撞时也不需要合并。此方法在ｒａｉｎｂｏｗ链中 使用了连续的映射函数，即从映射函数１到映射函数ｔ一１。这 样一来，两个链碰撞时，合并仅发生在两个链的对应位置上元素 相等的情况下。如果位置不相同，因为后面使用了不同的映射 函数，所以不需要合并。对于一个长度为ｔ的链，碰撞发生并需 要合并的概率为１／ｔ。 对于一个ｍ×ｔ的彩虹表，查找成功的概率为： ＝１－兀（１一 ）ｍ。＝ｍ ＝Ｎ（Ｊ ） 实际上ｔ个大小为ｍ×ｔ的经典表和一个大小为ｍｔ×ｔ的彩 虹表的查询成功率相当。在两种方法中，表都覆盖了ｍｔ 个密 钥，使用了ｔ个不同的映射函数。他们的对应关系如图１所示。 ？ 图１ 经典表与彩虹表对应关系 在彩虹表中查找密钥采用如下的方式进行：首先将Ｒ 一 应 用到密文上得到结果，然后将结果与彩虹表中的链尾匹配。如 果找到匹配了，可以从链首重构整个链。如果找不到，我们接着 对结果应用Ｒ 一 一 ，然后将结果与彩虹表中倒数第二个元素 进行匹配。下面接着对结果应用 一 一 一。，以此类推。整 ．，． １、 个过程中需要计算次数是 ，这只是经典表的一半左右。 顺便指出彩虹表的出处即为在彩虹表的每一列采用了不同的 ｒｅｄｕｃｔｉｏｎ函数的缘故。 图２所示给出一个彩虹链攻击的例子： １）假设我们要破解的密码ｈａｓｈ是“ｒｅ３ｘｅｓ”，首先对该值用 ２９２ 计算机应用与软件 ２０１１血 臣口鐾＿① —● 回 圈Ｈ ■ 融 ． ＳＴＯＰ 吕 －＠ 图２彩虹表攻击例子 Ｒ３运算处理一下，得到明文“ｒａｍｂｏ”。然后看是否在每一个链 的终点有明文“ｒａｍｂｏ”出现。 ２）如果ｒａｍｂｏ没有出现在表的任一链的终点，则继续用 Ｒ２运算处理，紧跟着用Ｈ和Ｒ３运算处理，这次算得的 “ｌｉｎｕｘ２３”恰好在最后一个链的终点出现。如果没出现，则反复 应用类似运算处理。 ３）从最后一个链的起点“ｐａｓｓｗｄ”恢复整条链，我们看到 “ｒｅ３ｘｅｓ”是“ｃｕｌｔｕｒｅ”的ｈａｓｈ结果，所以，密码就是“ｃｕｌｔｕｒｅ”。 ２ Ｒａｉｎｂｏｗ攻击的分布式设计 彩虹表攻击有三部分可考虑分布式。 １）Ｒａｉｎｂｏｗ表的分布式计算 服务器仅仅分发给客户端产生彩虹表时所需要的各项参 数，然后由客户端来进行彩虹表计算。这样做有如下两点好处： ａ）服务器可以根据需要预计算出各项参数。 服务器端根据所需计算的彩虹表的各项参数及客户端计算 能力，来决定每个客户端所需产生的彩虹表的参数，以及达到某 个成功率所需要产生的彩虹表的个数。设ｍ为每张表中彩虹 链个数，ｔ为彩虹链长度，ｚ为彩虹表个数，则各项参数之问的关 系满足如下方程： ～ Ｐ ＝ｌ—ｎ（‘ ｌ １一等）ｍ ：ｍ ’ ｍ （ｍ ＋Ｌ＝＾ （１一ｅ－ ）Ｐ… ≥１一（１一Ｐ 。 ） 这样，服务器根据想要达到的成功率让每个吝户端产生不 同表数、不同链数的彩虹表，每个彩虹表由不同的随机值开始生 成。尽管各个表之间可能存在冗余，但总的来说，由公式可推 出，表越多，成功率越大。 ｂ）在计算过程中，客户端不需要与服务器进行交互。 Ｊ．Ｂｏｍｔ提出了一种基于ＤＰ（ｄｉｓｔｉｎｇｕｉｓｈｅｄ ｐｏｉｎｔｓ）技术的分 布式攻击，由于ＤＰ技术固有的缺点，客户端在产生彩虹表时要 与服务器交互，来验证ＤＰ的有效性。在基于彩虹表的分布式 攻击中客户端在计算彩虹表的过程中不需要与服务器交互，减 少了交互的代价。． ２）Ｒｍｎｂｏｗ表的分布式存储 当前国际上也有分布式计算彩虹表的项目，叫做ＯｉｓｔｒＲＴｇｅｎ。 它的原理是客户端计算一个８兆的彩虹表，然后回传给服务器，由 服务器将其保存在某个安全的地方。这种方法的缺点是： ａ）传输大量数据浪费时间； ｂ）由于彩虹表涉及到敏感信息，在传输过程中还需要进行 加密。 我们先择将彩虹表保存在客户端本地，供后继分布式查询 时使用。这种方法能适用于计算客户端相对比较稳定的网络， 即客户端断开服务器的概率比较低的网络。 ３）Ｒａｉｎｂｏｗ的分布式攻击 分布式攻击可以采用两种方式，一种是由服务器负责分发 已经计算好的彩虹表，客户端接收到彩虹表后进行彩虹表攻击， 这样做有以下缺点： ａ）在应用中，服务器存有大量数据，可能成为整个系统的 瓶颈；再者，彩虹表的网络传输代价很高。 ｂ）这些彩虹表，如果在网络传输中被篡改，有可能将导致 攻击失败，这又增加了加密和解密的代价。 所以我们采用了服务器只负责传输相应参数，即待破解密 码的哈希值，客户端再收到指令后，先进行攻击，如果攻击失败， 则再根据需要产生部分彩虹表，继续查找。这样做可能会增加 攻击的平均时间。一旦某个客户端找到密码，通知给服务器。 服务器然后通知其他客户端密码已找到，攻击结束。在实际攻 击中，由于彩虹表之间存在冗余，有可能多个客户端都会找密 码。这样服务器取第一个找到密码的结果即可。 ３实验结果 ３．１ Ｒａｉｎｂｏｗ分布式计算和存储实验 分布式计算和存储测试所用的参数如下： ：［ＡＢＣＤＥＦ－ ＧＨＩＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺＯ１２３４５６７８９］； ；［ＡＢＣＤＥＦＧＨＩ－ ＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺ］，分别表示要产生密钥的字符集。令 ｍ为每张表中彩虹链个数，ｔ为彩虹链长度，Ｚ为彩虹表个数。 我们对生成基于 算法的密钥长度可为１—７位字符的彩虹表 的生成进行了单机版和分布式版的测试。数据参数如表１、表２ 所示。 表１ Ｒａｉｎｂｏｗ分布式存储测试数据参数 表２ Ｒａｉｎｂｏｗ分布式存储测试结果 实验表明，对于大的彩虹表，用单机生成不仅速度慢，而且 因为彩虹表一般很大，很难存储。同时由于对于太大的文件，操 作系统很难把它一次性读到内存，这样在进行查找时，给系统造 成很大负担。我们用５个计算节点同时生成彩虹表，得到了很 好的加速比。同时，也缓解了单机上存过大彩虹表的问题。 ３．２ Ｒａｉｎｂｏｗ分布式攻击实验 分布式攻击实验采用第三方提供的Ｒａｉｎｂｏｗ表，Ｒａｉｎｂｏｗ表 的各参数如表３所示。 第２期 李昕等：基于分布式环境下的彩虹表密码攻击 ２９３ 表３ Ｒａｉｎｂｏｗ分布式攻击实验数据 实验中，我们使用了字母、数字、包括特殊字符的密钥空间， 这基本涵盖了一般的密码所包含的字符。结果表明，用５台 Ｃｏｒｅ Ｄｕｏ２．４Ｇ的计算机，对于任意１４位以内的ＷｉｎｄｏｗｓＸＰ系 统密码都可以在平均５分钟以内破解出来。这里之所以是１４ 位以内的密码，是因为ＷｉｎｄｏｗｓＸＰ的密码ｈａｓｈ算法是７位一个 单元进行的。 ４结束语 本文对基于彩虹表的分布式密码攻击进行了探讨，分析了 彩虹表的基本原理，即ｈａｓｈ链和彩虹链。并使用分布式计算环 境对彩虹表的分布式存储、分布式攻击等进行了相关研究。实 验表明，彩虹表对于密码破解的确是强有力的武器。不过，如果 在生成哈希表之前，给密码加个唯一的前缀，然后再ｈａｓｈ。这 样，攻击者就无法用彩虹表来攻击了。因为“密码”和“加了前 缀的密码”生成的哈希结果是不匹配的。除非知道所有的哈希 表都加了这个前缀。即使真的知道，也得专门针对你的机器生 成一个定制的彩虹表。 另外基于ＧＰＵ的计算日益成熟，在一台普通ＰＣ上辅以 ＮＶｉｄｉａ ＣＵＤＡ技术，对于ＮＴＬＭ算法可以达到最高每秒１０３， ８２０，０００，０００次明文尝试（超过一千亿次），对于广泛使用的 ＭＤ５也接近一千亿次。下一步的研究计划是把具有ＧＰＵ计算 能力的计算节点整和到系统中来，以增强系统的计算能力。 参考文献 ［１］Ｈｅｌｌｍａｎ Ｍ Ｅ．Ａ ｃｒｙｐｔａｎａｌｙｔｉｃ ｔｉｍｅ－ｍｅｍｏｒｙ ｔｒａｄｅ ｏｆｆ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ— ａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ＩＴ－２６，１９８０：４０１—４０６． ［２］Ｏｅｃｈｓｌｉｎ Ｐ．Ｍａｋｉｎｇ ａ Ｆａｓｔｅｒ Ｃｒｙｐｔａｎａｌｙｔｉｃ Ｔｉｍｅ—Ｍｅｍｏｒｙ Ｔｒａｄｅ—Ｏｆｆ［Ｊ］， Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｖｏｌｕｍｅ ２７２９，２００３：６１７—６３０． ［３］Ｂｏｍｔ Ｊ，Ｐｒｅｎｅｅｌ Ｂ，Ｖａｎｄｅｗａｌｌｅ Ｊ．Ｏｎ ｔｉｍｅ—ｍｅｍｏｒｙ ｔｒａｄｅｏｆｆ ｂｅｔｗｅｅｎ ｅｘ— ｈａｕｓｔｉｖｅ ｋｅｙ ｓｅａｒｃｈ ａｎｄ ｔａｂｌｅ ｐｒｅｃｏｍｐｕｔａｔｉｏｎ［Ｊ］．Ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅ— ｏｒｙ ｉｎ ｔｈｅ Ｂｅｎｅｌｕｘ，１９９８：１１１—１１８． ［４］Ｃｏｓｎａｒｄ Ｍ，ＰＨＩＬＩＰＰＥ Ｊ Ｌ．Ｄｉｓｔｒｉｂｕｔｅｄ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｅｃｉｐｈｅｒｉｎｇ［Ｊ］． ［Ｓ．１．］：［Ｓ．ｎ．］，２００７． ［５］ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｒａｉｎｂｏｗ—ｔａｂｌｅｓ． （上接第２８３页） ／／教师冲突检测每冲突一次Ｃｏｎｆｌｉｃｔ＋１。 ｉｆ ＦＡｒｒａｎｇｅ［Ｊ］［ｎ］．１ｎｆｏ．ＴｅａｃｈｅｒｌＤ＝ＦＡｒｒａｎｇｅ［ｉ］［ｎ］． Ｉｎｆｏ．ＴｅａｃｈｅｒＩＤ ｔｈｅｎ｛ ＦＡｒｒａｎｇｅ［ｊ］［ｎ］．Ｃｏｎｆｌｉｃｔ：＝ＦＡｒｒａｎｇｅ［Ｊ儿ｎ］．Ｃｏｎｆｌｉｃｔ＋１； ＦＡｘＴａｎｇｅ［ｉＨ ｎ］．Ｃｏｎｆｌｉｃｔ：＝ＦＡｒｒａｎｇｅ［ｉ］［ｎ］．Ｃｏｎｆｌｉｃｔ＋１； ／／班级冲突检测每冲突一次Ｃｏｎｆｌｉｃｔ＋１。 ｉｆＧｒｏｕｐＣｏｎｆｌｉｃｔ（ＦＡｒｒａｎｇｅ［ｉ］［ｎ］，ＦＡ￣ａｎｇｅ［Ｊ］［ｎ ）ｔｈｅｎ ＦＡ￣ａｎｇｅ［ｊ］［ｎ］．Ｃｏｎｆｌｉｃｔ：：ＦＡｒｒａｎｇｅ［ｊ］【ｎ］．Ｃｏｎｆｌｉｃｔ＋１； ＦＡｒｒａｎｇｅ［ｉ］［ｎ］．Ｃｏｎｆｌｉｃｔ：＝ＦＡｒｒａｎｇｅ［ｉ¨【ｎ］．Ｃｏｎｆｌｉｃｔ＋１； Ｒｅｓｕｌｔ： Ｔｒｉｌｅ： ｏｆｒ Ｆｈｅｍ ｄｏ Ｒｅｓｕｌｔ：＝Ｒｅｓｕｈ ａｎｄ（ＦＩｔｅｍ［ｉ］．Ｃｏｎｆｌｉｃｔ＝０）； ｆ ｎｃｔｉｏｎ Ｅｎｄ ４．５ 交叉和变异（Ｍｕｔａｔｅ／ＣｒｏｓｓＯｖｅｒ） 交叉和变异是遗传算法的重点，关于它们的选择算法更是 关键之处。许多排课算法就是按照“物竞天择、适者生存”的思 想，选择出适应度高的染色体进行交叉变异，最终使排课问题得 以成功解决。而本算法在进行时间冲突检测时发现，如果一个 课程项在本时问列上冲突值高，那么其相关的课程多存在于这 个时间列，相对应其它时间列的冲突情况可能就会减小。按照 这一思想，本算法在交叉时选择每个时间列上冲突值不为零的 最大课程项，然后针对这些项进行交叉。 实际上这种交叉变异算法也是经过多种算法对比后决定 的，其交叉率并不高（最大只有１／ＦＥｎａｂｌｅＣｏｕｎｔ，最小可能为 ０），但是其交叉效率令人满意。变异操作也针对有冲突的课程 项进行，测试发现取值不宜过小，确定为５０％。 定义函数原型： ｐｒｏｃｅｄｕｒｅ Ｍｕｔａｔｅ； ｐｒｏｃｅｄｕｒｅ ＣｒｏｓｓＯｖｅｒ； 算法伪码如下： ｐｒｏｃｅｄｕｒｅ ＣｒｏｓｓＯｖｅｒ ｏｆｒ ＦＥｎａｂｌｅＴｉｍｅ ｄｏ ｛ ＧｅｔＭａｘ Ａｈｅｍ．Ｃｏｎｆｌｉｃｔ； Ａｄｄ Ａｈｅｍ ｔｏ ＰＭａｘ；｝ ｏｆｒ ＰＭａｘ ｄｏ Ｅｘｃｈａｎｇｅ（ＰＭａｘ［ｉ］，ＰＭａｘ［ｉ＋１］）； ｐｒｏｃｅｄｕｒｅ Ｅｎｄ ｐｒｏｃｅｄｕｒｅ Ｍｕｔａｔｅ ｆｏｒ Ｆｈｅｍ ｄｏ ｉｆ Ｆｈｅｍ［ｉ］．Ｃｏｎｆｌｉｃｔ＜＞０ ｔｈｅｎ ｉｆ Ｒａｎｄｏｍ（１００）＜５０ ｔｈｅｎ Ａｒｒａｎｇｅｌｔｅｍ（Ｆｌｔｅｍ［ｉ］）； ｐｒｏｃｅｄｕｒｅ Ｍｕｔａｔｅ Ｅｎｄ ５结束语 计算机排课可以提高排课质量，把教务工作者从繁重的工 作中解脱出来，而且课表中的信息也非常清楚，对于优化学生在 校学习进程，评估每位教师对教学的贡献，领导合理决策等都具 有重要的意义，必将会大大推动教学的良性循环。 参考文献 ［１］汪祖柱，程家兴，刘慧婷．基于遗传算法求解时间表问题［Ｊ］．计算 机工程与应用，２００４（２４）：９２—９４． ［２］吴政，汪峰坤．基于遗传算法的排课系统［Ｊ］．计算机与数字工程， ２００８（１１）：２９—３２． ［３］袁礼海，宋建社，毕义明，等．混合遗传算法及与标准遗传算法对比 研究［Ｊ］．计算机工程与应用，２００３（１２）：１２３—１２４． ［４］周洪伟，原锦辉，张来顺．遗传算法“早熟”现象的改进策略［Ｊ］．计 算机工程，２００７（１９）：２０１—２０３． ［５］Ｃｈｕ Ｐ Ｃ，Ｂｅａｓｌｅｙ．Ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ａｓｓｉｇｎｍｅｎｔ ｐｒｏｂｌｅｍ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎ，１９９５：２０—２２． ［６］滕姿，邓辉文，杨久俊．基于遗传算法的排课系统的设计与实现 ［Ｊ］．计算机应用，２００７（２７）：１９９—２０４． ［７］冯冬表，王非，马雁．遗传算法中选择交叉策略的改进［Ｊ］．计算机 工程，２００８（１９）：１８９—１９１． ［８］胡义伟，郑金华，谢勇．遗传算法在大学排课系统中的应用［Ｊ］．计 算机系统应用，２００８（０９）：６６—６９．
发布评论