【文章】8.1 密钥生成: 密钥的空间 字典攻击

8.1 密钥生成

    算法的安全性依赖于密钥，如果你用一个弱的密钥生成方法，那么你的整个体制是弱的。因为能破译你的密钥生成算法，所以Eve就不需要试图去破译你的加密算法了。

减少的密钥空间

    DES有56比特的密钥，正常情况下任何一个56比特的数据串都能成为密钥，所以共有2⁵⁶（10¹⁶）种可能的密钥。Norton Discreet for MS-DOS（8.0版或更低的版本）仅允许ASCII码的密钥，并强制每一字节的最高位为零。该程序将小写字母转换成大写（使得每个字节的第5位是第6位的逆），并忽略每个字节的最低位。这样就导致该程序只能产生2⁴⁰个可能的密钥。这些糟糕的密钥生成程序使DES的攻击难度比正常情况低了一万倍。

    表8.1给出了在不同输入限制下可能的密钥数。表8.2给出了在每秒一百万次测试的情况下，寻找所有这些密钥消耗的时间，记住，穷举搜索8字节密钥与搜索4、5、6、7、8字节密钥在所费时间上有很小的区别。

表8.1  不同密钥空间的可能密钥数

表8.2  不同密钥空间穷举搜索时间（假设每秒测试一百万次）

    特定的穷举攻击硬件和并行工具将在这里工作，每秒测试一百万次（或是一台机器或是多台机器并行运转），那么将能破译小写字母和小写字母与数字的8字节的密钥，7字节的字母数字符号密钥，6字节长的印刷字符和ASCII字符密钥，5字节长的8比特—ASCII—字符密钥。

    记住，计算机的计算能力每18个月翻倍。 如果你期望你的密钥能够抵抗穷举攻击10年，那么你最好相应的做出计划。

弱密钥选择

    人们选择自己的密钥时，通常选择一个弱密钥。他们常常喜欢选择“Barney”而不是“*9（hH/A。”。并不能总归罪于不良的安全实践，而是“Barney”的确比“*9（hH/A。”更容易记忆。最安全的密码体制也帮不了那些习惯用他们配偶的名字作为密钥或者把密钥写下来揣在兜里的人。一个聪明的穷举攻击并不按照数字顺序去试所有可能的密钥，它们首先尝试最可能的密钥。

    这就是所谓的“字典攻击”，因为攻击者使用一本公用的密钥字典。Daniel V.Klein用这个系统能够破译一般计算机上40%的口令[847，848]。试图登录时，他并不是一个口令接一个口令的试验，他把加密的口令文件副本下来然后进行离线攻击。下面是他所试验的：

    （1） 用户的姓名、简写字母、帐户姓名和其他有关的个人信息都是可能的口令，基于所有这些信息可以尝试到130个口令。对于一个名叫“Daniel V.Klein”， 帐户名为“Klone”的用户 ，用来尝试口令的一些词是“klone，klone0，klonel， klone123，dvk ，dvkdvk，dklein，Dklein， leinad，nielk，dvklein，danielk，DvkkvD，DANIEL-KLEIN，(klone)，KleinD等等。

    （2） 使用从各种数据库中得到的单词。这些单词是男人和女人的姓名名单（总共约达16，000）；地点（包括像“spain”、“spanish”和“spaniard”这样的排列也全被考虑在内）；名人的姓名；卡通漫画和卡通人物；电影和科幻小说故事的标题、有关人物和地点；神话中的生物名字（从《Bulfinch神话故事》和神话动物字典中产生出的）；体育活动（包括球队名、一些浑名，和职业队名称）；数字（比如“2001”和写出的“twelve”）；一串字母和数字（“a”“aa”“aaa”“aaaa”，等等）；中文音节（选自汉语拼音字母或在英文键盘上输入中文的国际标准系统）；《圣经》的权威英译本；生物术语；公用的粗话（如“fuckyou”、“ibmsux”和“deadhead”）；键盘模式（如“qwerty”、“asdf”和“zxcvbn”）；缩写（如“roygbiv”——彩虹的七种颜色和“ooottafagvah”——帮助记忆头部十二条神经的东西）；机器名称（可从letc/hosts中获得）；莎士比亚作品中的人物、戏剧和地点；常用的犹太语；小行星名称和Klein以前出版的技术论文中搜集到的单词。综上，每个使用者可以考虑超过66，000个独立的单词（舍弃字典内外复制的那些）。

    （3）第（2）步得到的单词的不同置换形式。这包括使第一个字母大写或作为控制符，使整个单词大写，颠倒单词的顺序（不管前面有无大写），将字母“O”换成数字“0”（使得单词“scholar”变作“sch0lar”），将字母“l”换成数字“1”（使单词“scholar”变成“scho1ar”），以及进行同样操作将字母“Z”换成数字“2”，“S”换成“5”。另一种测试是将单词变为复数形式（不管它是否为名词），非常聪明的将“dress”变为“dresses”、“house”变为“houses”，并且“daisy”变为“daisies”， Klein并不考虑复数规则，“datum”可以变为“datums”（不是“data”）“sphynx”变为“sphynxs”（而不是“sphynges”），同样地，将后缀“-ed”，“-er”和“-ing”加到单词上，如“phase”变为“phased”，“phaser”和“phasing”。这些附加的测试使得每一位使用者可能的口令清单增加了的1,000,000个单词。

    （4）从第（2）步得到的单词的不同的大写置换形式，不考虑第（3）步。这包括所有单字母的单个大写置换（如“michael”可换为“mIchael”，“miChael”，“michAel”等等）双字母大写置换（“MIchael”，“MiChael”，“MicHael” ……“mIChael”，“mIcHael”等等）。三字母置换，等等。对于每一个使用者，单字母置换增加了大约400,000个单词，双字母置换增加1,500,000个单词，三字母置换增加至少3,000,000个单词。必须要有足够的时间来完成测试，测试完成4，5，6个字母的置换没有充足的计算机“马力”是不可能的。

    （5） 对外国用户要尝试外语单词，对有中文名称的用户要使用中文口令来进行特别的测试。汉语拼音字母组成单音节、双音节或三音节的单词，但由于不能测试确定它们是否是实际存在的，所以要启动穷举搜索。(在汉语拼音中共有298个音节，158,404个双音节词，稍多于16,000,000个三音节词。) 一种类似的攻击方式，就是穷举构造出来的可以发音但并不存在的单词，可以很容易的被用于英语中。

    （6） 尝试词组。自然测试所耗费的数字量是令人惊愕的。为了简化测试，只有在/usr/ dict / words中存在，且仅有3，4个字母长的才被测试。即使这样，词组数目也有千万。

    当字典攻击被用作破译密钥文件而不是单个密钥时就显得更加有力。单个用户可以很机灵地选择到好密钥，如果一千个人各自选择自己的密钥作为计算机系统的口令，那么至少有一个人将选择攻击者字典中的词作为密钥。

随机密钥

    好密钥是指那些由自动处理设备生成的随机的比特串。如果密钥为64比特长，每一个可能的64比特密钥必须具有相等可能性。这些密钥比特串要么从可靠的随机源中产生（见17.14 节），要么从安全的伪随机比特发生器中产生（见16和17章）。如果自动处理办不到，就抛硬币或掷骰子吧！

    这是非常重要的，但不要太拘泥于声源产生的随机噪音和放射性衰减产生的噪音谁更随机。这些随机噪声源都不是很完美的，但已经是足够好了。用一个好的随机数发生器产生密钥是很重要的，然而更加重要的是要有好的加密算法和密钥管理程序。如果你对密钥的随机性产生怀疑的话，请用后面讲的密钥碾碎技术。

    许多加密算法有弱的密钥：特定的密钥往往比其它密钥的安全性差。建议对这些弱密钥进行测试，并且发现一个就用一个新的代替。DES在2⁵⁶个密钥中仅有16个弱密钥，因此生成这些密钥的机会小。已经证明，密码分析者对使用弱密钥一无所知，因而也就不能从这个偶然的使用中获得什么，不用弱密钥加密反而给密码分析者提供了信息。然而，对几个弱密钥进行检测是如此容易以至让我们轻率地不去做它 。

    对公钥密码体制来说，生成密钥更加困难，因为密钥必须满足某些数学特征（必须是素数的，是二次剩余的，等等）。11.5节讨论了产生大随机素数的技术。从密钥管理的观点看，发生器的随机种子也必须是随机的，这一点是应该记住的。

    产生一个随机密钥并不总是可能的。有时你需要记住密钥（看你用多长时间能记住这串字符：25E856F2E8BAC820）。如果你必须用一个容易记忆的密钥，那就使它苦涩难懂。比较理想的情况是该密钥既容易记忆，又难以被猜中。下面是一些建议：

    ——词组用标点符号分开，例如“turtle*moose”或者“zorch! splat”。

    ——由较长的短语的首字母组成字母串。例如由“Mein Luftkissenfahrzeug ist voller Aale”产生密钥“MlivA！”。

通行短语

    一个比较好的办法是利用一个完整的短语代替一个单词，然后将该短语转换成密钥。这些短语被称为通行短语。一项称为密钥碾碎的技术可以把容易记忆的短语转换为随机密钥，使用一个单向Hash函数可将一个任意长度的文字串转换为一个伪随机比特串。

    例如，易于记忆的文本串：

        My name is Ozymandias，king of kings。Look on my works，ye  mighty，and despair。

    可以被碾碎成一个64比特密钥：

        E6C1 4398 5AE9 0A9B

    当然，向一个显示关闭的计算机输入完整的短语是很困难的，所以，解决该问题的好建议是值的推荐的。

    如果这个短语足够长，所得到的密钥将是随机的。“足够长”的确切涵义还有待解释。信息论讲到，在标准的英语中平均每个字符含有1.3比特的信息（参见11.1节）。对于一个64比特的密钥来说，一个大约有49个字符或者10个一般的英语单词的通行短语应当是足够的。通常地讲，每4个字节的密钥就需要5个单词。这是保守的假设，因为字母的大小写、空格键、及标点符号并没有考虑之内。

    这种技术甚至可为公开密钥体制产生私钥：文本串被“碾碎”成一个随机种子，该种子被输入到一个确定性系统后就能产生公钥/私钥对。

    如果你正打算选择一个通行短语的话，就选择独特而容易记忆的，最好别在文学著作里面选取——如，“Ozymandias”就是很差的。莎士比亚的全本著作和《星球大战》里的对话都在线提供，并且很容易被用来进行字典攻击。要选择难懂，但有个性的词，包括一些标点和大写字母，如果能够，还可以包括数字和非字母符号。糟糕的或者不正确的英语，甚至一门外语都会使通行短语对字典攻击缺乏敏感性。对使用通行短语有一个建议就是“鬼扯”：容易记住但不可能被写出的胡言乱语。

    不管上面怎么叙述，难懂决不是真正随机的代替品。最好的密钥还是随机密钥，尽管很难记住。

X9.17 密钥生成

    ANSI X9.17标准规定了一种密钥生成方法（见图8.1）[55]。它并不生成容易记忆的密钥，它更适合在一个系统中产生会话密钥或伪随机数。用来生成密钥的加密算法是三重--DES，它就像其它算法一样容易。

    设E _k（X）表示用密钥K对X进行三重DES加密。K是为密钥产生器保留的一个特殊密钥。V ₀是一个秘密的64比特种子，T是一个时间邮戳。欲产生随机密钥R_i，计算：

R _i= E _k (E _k (T _i)⊕V_i)

    欲产生V_i+1 ，计算：

V_i+1=E _k (E _k (T _i)⊕R _i)

    要把R _i转换为DES密钥，简单地调整每一个字节第8位奇偶性就可以。如果你需要一个64比特密钥，按上面计算就可得到。如果你需要一个128比特的密钥，产生一对密钥后再把它们串接起来便可。

DoD 密钥生成

    美国国防部建议用DES在OFB方式（参见9.8节）下生成随机密钥[1144]。由系统中断向量、系统状态寄存器和系统计数器生成DES密钥；由系统时钟、系统ID号、日期、时间生成初始化向量；外部生成的64-比特量可作为明文输入（V₀）：如，系统管理员键入的8个字符。这样，其输出就可作为你的密钥。