Board logo

标题: 开发者的软件安全性：一次性密码本 [打印本页]
作者: 黑色海岸线    时间: 2004-3-29 00:43     标题: 开发者的软件安全性：一次性密码本

开发者的软件安全性：一次性密码本 这种历经考验的真正加密算法在今天仍有意义 Gary McGraw 和 John Viega Cigital （前身是 Reliable Software Technologies） 2000 年 10 月 内容： 一次性密码本 有什么蹊跷？ 一些历史 本子的生成 结束语 参考资料 关于作者 在这一部分中，Gary 和 John 仔细研究了一次性密码本 (one-time pad)，如果使用得当的话，它是一种无懈可击的加密算法。一次性密码本已证实被间谍广泛使用，其历史可以追溯到第二次世界大战 -- 但它对如今的软件应用有什么切实的意义吗？ 是否真有一种完美的加密算法？从理论上说，有的。如果使用正确的话，一次性密码本就是不易破解的。但这种算法在实践中用得并不多。在这篇文章中，我们将谈谈一次性密码本、其优缺点，以及为什么有其它加密算法存在。 密码术有时更是一种艺术而非科学。例如，我们无法确切回答一个象“Rijndael 算法有多安全？”这种看似简单的问题。因为 Rijndael 使用 128 位（或更大）密钥，我们甚至可以用到数字 2128。但在现实中，没人真的知道 Rijndael 有多安全，因为要证明有关算法的安全性保证相当困难。要假设没有一种攻击能成功破坏任何给定的算法几乎是不可能的。有一个困难是每隔一段时间，新的密码攻击就会被发现。但当我们考虑到想证明一种密码术能经受得住 任何未来的攻击，甚至包括以后几个世纪都不会被发现时，事情就变得更加困难了。 在现实中，那些确信安全的常用密码术实际上有可能安全，也有可能不安全。我们信任密码术是因为还没有人能破解它，而不是因为 知道它是安全的。这就是为什么密码专家更倾向于推荐那些已被深入审查过的密码术，而不是更新或专用的密码算法。工作原理是，如果许多聪明的脑瓜都无法破解一种算法，那么比起没人仔细看过的那些算法来，它更有可能是安全的。关于一个问题思考的人越多，我们越有可能信任一种算法。这意味着我们最终讨论的是算法的“最佳情况”安全性特性。使用对称密钥密码术，“最佳情况”时常与密钥空间的大小相关 -- 除非已经知道有比尝试每个可能的密钥来公开数据（蛮力攻击）更好的办法。以上这些方法的结果可能会引起一些不安： 所有对称密钥算法都可以被破解，只要有足够的时间。 最终，我们将希望寄托在一种想法上，即没有人能有足够的时间来破译我们的代码！例如，如果我们使用的是 256 位的加密算法，没有仅比蛮力攻击更有效的攻击来对付它，我们就可以认为一个攻击者在有限时间内破解密码的几率相当小。 从数学上证明有关公钥算法的问题比对称算法要来得容易。这是因为公钥算法往往基于详细定义的数学问题（例如由质数组成的因式分解组合）。与之相反，对称算法往往是一组 特别的替代与排列，要在上下文中分析它们比较困难。因此，假设有种完美的实现，我们知道破解 RSA 算法的困难与对非常大的数字进行因子分解的困难是紧密联系在一起的。数学家相信对大的数字进行因式分解在相当长的一段时间内也不能完成。不幸的是，至今没有一个人能 证明因式分解确实那么难。 即使我们知道因式分解是那么的困难（并假设没有其它的实现或设计问题），对于 RSA 是可破解的仍然有一些理论限制，与对称算法的情况一样。如果在有限时间内尝试出密钥的同时空等，那么绝对能破译 RSA 密钥！ 一次性密码本 获得完美的数据私密性看上去不太可能，尤其是在潜在攻击者有了大量时间的情况下（可以并行运行蛮力搜索）。但非常奇怪的是有一种加密算法，如果使用恰当就是不可破解的：一次性密码本。更奇怪的是这种算法难以想象的简单。 一次性密码本后面的基本思想是密钥材料与文本一样多。加密操作可以是简单的模加。在基于计算机的使用中，它通常是 XOR。 有一个用于一次性密码本的简单算法：对于每条纯文本消息，生成一个随机秘钥。密钥的长度应该与纯文本消息的长度完全一样。密码术文本就是通过使用密钥对纯文本执行 XOR 操作来创建的。 举例说明，比如我们希望加密以下消息： "One-time pads are cool." 纯文本消息可以以 8 位 ASCII 编码，产生以下十六进制表示： 4f 6e 65 20 74 69 6d 65 20 70 61 64 73 20 61 72 65 20 63 6f 6f 6c 2e 假设以十六进制表示的随机密钥是： 9d 90 93 e7 4f f7 31 d8 2d 0d 22 71 b6 78 12 9d 60 74 68 46 6c c0 07 执行了 XOR 操作后，我们得到以下密文： d2 fe f6 c7 3b 9e 5c bd 0d 7d 43 15 c5 58 73 ef 05 54 0b 29 03 ac 29 因为在纯文本中每一位都是通过密钥中单个唯一位来编码的，所以没有可以被密码专家在攻击中利用的重复信息。因为密钥是随机选择的，所以我们为以上显示的纯文本流编码的结果很可能与为以下消息编码的结果一样： 86 96 93 e7 49 f7 33 c9 2d 1f 26 72 ac 36 00 cf 64 20 2b 46 6d c9 07 而它解密成 "the riot begins at one."。因为位是一一对应的，假设加密密钥从不重复使用，那么密码专家无法获得任何信息可以使一种解密比任何其它解密更恰当。 下面的 C 代码可以用于使用一次性密码本来加密和解密。纯文本做了适当的修改。因此不适合于传递到常数字符串中。 void otp(char *text, char *key, int len) { int i; /* XOR sizeof(int) bytes at a time (4 on most machines). */ for(i=0;i^=((int *)key); /* If the number of bytes isn't divisible by sizeof(int), XOR the rest.*/ i = len%sizeof(int); while(i){ text[len-i] ^= key[len-i]; --i; } } 有什么蹊跷？ 一次性密码本听上去相当不错，因此当您发现它们在实际使用当中难得见到时就会很惊讶。确实有一些原因会造成这种情况。 首先，安全地分发密钥极其困难，特别是在它们必须与消息一样长的情况下。如果希望使用一次性密码本通过不可信媒体向朋友发送 12 GB 的数据，需要的密钥则有 12 GB 长！这是个巨密钥。 其次，并且更为重要的原因是，密码术要求完全不可预测的数字。当然， rand() 及其同类是完全不值得考虑的，因为它们是完全可预料的。 我们已经谈到在这种长度要获得高质量的随机数有多么困难，特别是在很高的带宽情况下。想象一下必须取得 12 GB 的随机数据！如果尝试从 /dev/random 获得这么大量数据，很可能在存储中等待的时间长得无法想象。硬件来源的随机性非常不切实际。 您可能会问，为什么不使用 /dev/urandom 呢，因为它尽可能快地生成数字吗？问题是它使用一种密码机制生成的数字。结果，您大大削弱加密的强度，本来它是不可破解的，现在要破解它所花费的力气不比破解最好的对称密钥算法花费的更多。因此为什么不在一开始就使用对称算法呢？如果这样做，将得到较短的密钥。 一些历史 一次性密码本比计算机的历史还要早，可以回溯到 1917 年。它们是在第二次世界大战期间偶然用于高安全通信中的。“一次性密码本”中的“密码本”来源于密码术的最初形式：密钥材料打印在厚厚的本子上，每页一个字母。 数字台 有许多用于发送加密消息的无线电“台”都与它类似。所吸引的一些业余爱好者将它称为“数字台”。 一次性密码本在今天仍在一些有限的范围内使用。许多政府部门使用短波无线电将加密的消息传达给战场上的间谍。特工人员有一个短波接收器，知道要调到哪个台以及何时调。无线电台只不过广播了自动声音读出一系列数字。这些数字被断开的方式清楚地表明有多条消息，每条消息都有一个有关消息的头信息。这种信息通常包括消息的长度和想要的接收者。间谍收听第一组数字，以确定是否有消息在等着他。如果有，他接收到消息的密文，并根据头信息来确定从他的那本一次性密码本的哪里开始。然后将消息译码，最后销毁消息和在一次性密码本中任何使用过的页。 在军事和政府部门应用中使用的加密算法与我们在计算机上使用的略有不同，但在实际中都是一样有效的。我们将给出一个算法示例，假设一条消息只由从 A 到 Z 中的 26 个可能的字母组成。密码本应该用从 1 到 26 的数字填充，可能少到每页一个数字，但通常一页有 4 到 5 个数字。要加密消息的第一个字母，将等价数（例如，"A" = 1， "Z" = 26）与密码本上显示的第一个值相加。如果得出的数字大于 26，从该值中减去 26。结果被转换回一个字母，然后写下它。对该页上的每个数字执行这一操作，然后密码本的最上一页被撕下销毁。随后为第二组及以后组的字母重复这一过程。根据这种组织，密码本每页上最少可以包含一个数字。通常他们在每页包含 5 个数字的组。总而言之，使用这种方法编码消息是种单调乏味的工作。 解密消息需要的密码本和用于加密消息所用的密码本一模一样。从密码本的第一页开始，密文的第一个字母被转换成一个数字，从密码本上的数中减去这个值。如果结果是零或小于零的数，在结果上加 26。然后这个数再被转换回字母。（这种简单的算法总是能产生和原始纯文本第一个字符相同的字母。）本子的最上面一页就用完了，撕下并销毁。然后，继续对本子第二页进行解密。这又是单调乏味的工作。 举例说明，考虑这样一条消息："One-time pads are cool."。我们必须把它写成： O N E T I M E P A D S A R E C O O L 转换成数字，消息就是： 15 14 05 20 09 13 05 16 01 04 19 01 18 05 03 15 15 12 假设本子上的前 18 个数字是： 02 15 18 24 02 14 24 09 20 14 09 10 01 17 19 02 19 13 对于第一个字母，我们将 15 和 2 相加得到 17。"Q" 是字母表中第 17 个字母，因此是密文的第一个字符。对于第二个字母，我们将 14 和 15 相加得到 29。因为该数大于 26，我们减去 26，得到 3，它转换成字母 "C"。最终我们得到以下密文： Q C W R K A C Y U R B K S V V Q H Y 要解密这条消息，首先将密码术文本转换回数字： 17 03 23 18 11 01 03 25 21 18 02 11 19 22 22 17 08 25 我们所使用的本子和用来加密消息的本子完全一样。因此，本子上的第一个数字是 2。从 17 中减去 2，得到 15。将 15 转换回字母 "O"。下一步，从密文中取出第二个数字 3，从中减去 15，因为 15 是本子上的第二个数。结果是 -12。因为这个结果小于 1，在这个数上加 26，得出 14。第 14 个字母是 "N"。以那种方法继续，最后我们就恢复了整条消息。 密码本的生成 生成密码本是另一个难题。使用 War and Peace 这段文本作为密码本的基础不是好主意。因为密钥不是随机的，那么密文就不是随机的。已使用的一种技术与今天的抽奖活动使用的方法相同。编了号的球被放在一个封闭的箱子中，空气将球吹得到处都是。一个操作员使用这个箱子来创建两个相同的密码本。对于密码本上的第一个字符，操作者看都不看就从箱子中抽取出一个球。在两个密码本上记录下球上的数字，然后将球放回到箱子中。然后重复这个过程。乏味的工作。 即使象选球这样的技术在现实世界中也不是很实用的。事实上，生成和分发密码本的困难正是在第二次世界大战中选择几百个不那么安全的密码代码的一个主要原因。 一次性密码本在战场中使用时就显示了非常多的问题。首先，密码本必须在两个通信方之间同步。请考虑当 Alice 向 Bob 发送消息，而 Bob 同时又向 Alice 发送消息的情况。他们两个人使用了某些密钥来进行加密。如果每一方都精确地遵照算法操作，那么两个人就都不能有正确的用于解密任何一方消息的密码本了！ 更糟糕的是，使用相同的密钥加密两条消息会泄露算法的安全性。如果某个人要猜两条使用相同本子加密的消息，这个人就可以同时恢复这两条原始消息。这种风险经常会产生。懒惰的士兵偶尔会使用用过的本子，有目的的密码专家注意到了，就会使通信双方认为非常安全的消息，此时也不怎么安全了。 要解决这个问题，有必要给 Alice 和 Bob 两个人每人一组两本一次性密码本。一组本子特定于从 Alice 到 Bob 的消息，另一组特定于从 Bob 到 Alice 的消息。现在，只要密码本不被重用，并且只要密码本在使用后被销毁，使得没人能够泄露用过的密码本，所有内容就都是安全的了。 不幸的是仍然有另一个问题 -- 数据完整性。让我们设想一下 Alice 在早上 10:00 向 Bob 发送了一条消息，然后在下午 1:00 发送了一条，最后在晚上 5:00 又发送了一条消息。如果早上 10:00 的消息由于送信人中弹而永远不能到达，Bob 要解密后面两条消息就非常困难了。不是不可能，但这是主要的不便，因为 Bob 在尝试解密下午 1:00 的消息时，必须猜出要从本子中的什么地方开始。一种解决这种问题的办法是为消息编号，并对每条消息只使用一个本子。另一个解决方案是每天使用一个本子；这样一次只能扰乱一天的通信。 结束语 第二次世界大战密码员的经验教训对于今天来说仍然非常宝贵。最重要的教训是一次性密码本不是非常方便。实际当中，以完美的安全性换取可用性的风险通常还是很值得的。 一次性密码本还很容易犯错。要记住，密码本必须使用一次而且只能一次，这就是一次性密码本名称的由来。并且密钥数据必须是完全不可预测的。 在实践中，大多数人不希望以安全方式交换巨大的密钥。在大的数据流中某处丢失数据的可能尤其可怕。如果流在从 1 字节到 1 GB 字节之间任何地方都有可能丢失，再同步就不太可能了。不过，如果您在听完了所有告诫之后仍对一次性密码本情有独钟的话，我们建议以下策略： 有一个能产生随机位的高质量的硬件随机数发生器。 使用密码散列函数对这些位进行散列，以消除任何数据源中的潜在模式。例如，可以使用 SHA-1 进行散列。从发生器中取 160 位，然后对它进行散列以从 SHA-1 中获得 160 位的输出。 将这些位存储在两张 CD 上，直至将 CD 填满。两张 CD 应该是等同的。 分发和使用 CD。 确保新 CD 在需要更多数据时可用。重用相同的 CD 会导致泄露。 用完后销毁 CD。



欢迎光临 黑色海岸线论坛 (http://bbs.thysea.com/) Powered by Discuz! 7.2