delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

04 Sep 2012

多次使用同一个一次性密码本的破解

正确地使用一次性密码本进行加密,在理论上是无法破解的。需要注意的是,许多对称式加密算法本质上是通过一定的算法来将密钥作为伪随机数发生器的种子来产生(近似于)一次性密码本的序列,因此类似的问题也需要予以重视:不要重复使用同一个一次性密码本(或密钥)来加密不同的明文数据。

以基本的一次性密码本加密算法,即按字节做 XOR 来看,由于在这个算法中明文和密文的字节位置是一一对应的,很明显,同一个位置的两份密文之间做 XOR,可以知道两份明文之间的 XOR 值(因为在这个过程中,密钥 k 被 XOR 消去了)。

假如明文碰巧又没有做任何压缩处理,实际上我们可以用程序来穷举出部分的密码本,并逐步解出全部明文。具体方法大致如下:

首先是尝试初步地破解。明文如果是英文的话,出现空格或e的可能性非常地高。对于每一条明文的同一个位置的内容,假定明文内容是空格,可以得到密钥可能是 密文 XOR 0x20,然后用这个可能的密钥去解其它的密文。假如解出来的明文都是字母、数字、标点或空格的话,则说明这个密钥很可能就是真正的密钥。用程序可以迅速对此作出判断。

接下来是找一组常见的英文单词。通常来说,the, to, then 这样的单词出现的频率非常高,因此,以它们作为突破口。以 the 为例,加上前后的空格,一共是5个字符。用穷举的方法去搜索每一个密文串来解出可能的密钥,然后再用这个密钥尝试解密其它密文在同一位置的字符串。如果解密出来的字符串看起来都像是英文(这里可以设置比较严苛的条件,例如只允许出现大小写字母、标点和数字),则记下密钥的位置和内容。反复搜索高频词,就可以恢复相当一部分明文的内容。

接下来,根据已知的明文内容去猜测可能的未知明文内容,并使用猜测的内容去尝试算出可能的密钥解密其它密文数据。

一些想法:

  1. 不要反复使用同一个一次性密码本,或者同一个对称密钥;
  2. 加密之前应先做压缩;
  3. 类似全盘加密这样的应用,密文也是需要保护的。

Archived: 3 Comments

dullgull | September 5, 2012 2:59 AM

你谈的是最简单的单表加密概率分析。

Frank Lin | September 6, 2012 8:15 AM

加密之前先压缩,是为了减少待加密明文长度,而不是增加保密性。明文与伪随机序列异或后得到的序列将不包含常见冗余,难以再次压缩。基于semantic security的假定,安全的加密方法不得泄漏关于明文除了大致长度外的任何信息。即使先对明文压缩,如果使用了同一one time pass也是不安全的,因为泄漏了两段明文异或后的值的信息。

https://www.google.com/accounts/o8/id?id=AItOawkwP_nyzB3_9dA9kWMohbQlpPlB8jvTsD0 | September 8, 2012 10:28 PM

像AES这样的算法,它是基于块进行加密的,比如aes的每个块都是16个字节。但是,假如原文的长度大于16个字节怎么办?你这样的攻击方式基于一个假定:相同的算法、相同的密钥、相同的原文块(16个字节)一定产生相同的密文。其实未必。如果我们在加密的时候,在块与块之间加入一定的反馈,就会使得你的攻击难度大大提高。
不过有一个极端情况,文件系统中存在大量的碎文件,每个都是16个字节以下,全采用同样的密钥加密,那就没辙了。