我知道现代加密算法尽可能接近完全随机数据(密文不可区分性),并且试图检测它是毫无用处的。但是,我们可以对弱加密(例如异或加密)做什么?特别是如果我们可以对加密的内容进行统计研究?
哪些方法是最有效的(以及在什么假设下)?最后,如何有效地破解这种加密(仅基于对加密内容的统计知识)?
我知道现代加密算法尽可能接近完全随机数据(密文不可区分性),并且试图检测它是毫无用处的。但是,我们可以对弱加密(例如异或加密)做什么?特别是如果我们可以对加密的内容进行统计研究?
哪些方法是最有效的(以及在什么假设下)?最后,如何有效地破解这种加密(仅基于对加密内容的统计知识)?
使用短填充(即比明文短)的 XOR 加密基本上是 Vigenère 密码。因此,破解 Vigenère 的标准技术应该破解 xor 加密。
基本思想是,如果加密密钥的长度为d 个符号,则每个第d个符号都使用相同的填充加密。因此,取每个第d个密文符号并将其视为简单的替换密码,将其破解,您将获得密钥的第一个符号。对第d+1个密文符号、第d+2个密文符号等重复。最终您将拥有密钥的所有d 个符号。
要破解简单的替换密码,您可以尝试蛮力(如果符号集很小)并将可能的明文与您知道的统计数据进行比较。对于某些明文(例如英语),您通常可以更快地破解其中的大部分内容(例如,对于英语文本,密文中最常见的符号可能会映射回e等)。
现在,您可能在想,如果您不知道d怎么办。通常对于 Vigenère,键的长度是蛮力的。尝试 d=1, d=2, d=3,... 对于每个 d,查看输出明文与统计数据的匹配程度。返回明文与统计数据最匹配的密钥。
在多字节 XOR 频率分析的情况下是要走的路。
众所周知,常规英文文本中最常用的字符是 E(etaoinshrdlu 是前 12 个),但在某些情况下,空格(ascii 中的 0x20)可能更频繁,尤其是在较短的消息中。
另一方面,对于可执行代码,虽然我找不到参考,但最常见的字符是 0x00 或 0xFF,这两者对于整数都是常见的。请注意,对于可执行代码和二进制文件,您可以使用一些快捷方式。例如,如果您知道在密文中的某个位置必须出现 0x00 字节(或序列),它将泄漏密钥的一部分。
在单字节异或的情况下,密钥空间显然限制在 256 个字符。
hellman有一个简单的 python 工具,称为xortool,它对于 CTF 挑战特别方便:)
做一些异或分析的工具:
- 猜测密钥长度(基于相等字符的数量)
- 猜测密钥(基于最常见字符的知识)
只是为了添加到列表中。大约一周前,SANS 发布了一篇关于 XOR 加密的不同工具的博客。该列表非常好,它提供了几种工具,我认为所有这些工具都很好。
这是链接:XOR 工具上的 SANS 博客