Sarah2 是一个简单的密码系统，可以用简单的工具加密解密。这篇文章则介绍了如何用一种叫 slide attack 的攻击手法破解 Sarah2。

加密步骤如下：

  1. 生成一个 27x27 的 S-box，代表一个 的双射，也就是对 a-z,_ 双字符组合的 permutation，一个 automorphism。这个 S-box 就是要用到的密钥。
  2. 对文本中每个双字母组合，加密之。
  3. 最后交换中间所有奇数位和偶数位。
1 2 3 4 5 6 7 8  or  a b c d e f g h
1 3 5 7 2 4 6 8      a c e g b d f h

这一套步骤需要重复多次，作者推荐的重复次数如下：

  • : 只加密若干消息，攻击者没有机会让我加密他们提供的消息。

第三条没懂。怎么才能在不知道密钥的情况下加密和解密？通过某个公开接口的程序吗？

  • : 加密大量消息，攻击者有一定可能让我加密他们提供的消息。

  • : 攻击者可以用我的密钥加密和解密，但不知道我的密钥。？

Confusion

Confusion 的意思是，

Confusion means that each binary digit (bit) [letters in Sarah2’s case] of the ciphertext should depend on several parts of the key, obscuring the connections between the two. The property of confusion hides the relationship between the ciphertext and the key. This property makes it difficult to find the key from the ciphertext and if a single bit in a key is changed, most or all the bits in the ciphertext will be changed. Confusion increases ambiguity of ciphertext and it is used by both block and stream ciphers.

减弱密钥和密文之间的联系，这样就算只修改了密钥里的 1 bit，密文也会剧烈变化。

Sarah2 通过多次替换字符保证了这一点，因为多轮加密会用到很多密钥信息（也就是查不同位置的表）。

Diffusion

Diffusion 则指

Diffusion means that if we change a single bit [letter] of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change.[2] Since a bit can have only two states, when they are all re-evaluated and changed from one seemingly random position to another, half of the bits will have changed state. The idea of diffusion is to hide the relationship between the ciphertext and the plain text. This will make it hard for an attacker who tries to find out the plain text and it increases the redundancy of plain text by spreading it across the rows and columns; it is achieved through transposition of algorithm and it is used by block cipher only.

减弱明文和密文的相关性，如果修改明文的 1 bit，密文里至少一半的 bits 都会变化，反之，修改密文的 1 bit，解密出的明文也有一半 bits 和原来不同。注意这里的 bit 只有 1 和 0 两个可能的值。Diffusion 主要通过移位算法实现，需要改变字符的位置，所以只能用在一次性加密一整块文本的 block cipher 中。

Sarah2 通过 permutation step 来实现 diffusion，据称这种方法可以让 1 bit 变化在 轮内扩散到全文。

Slide Attack

The slide attack is a form of cryptanalysis designed to deal with the prevailing idea that even weak ciphers can become very strong by increasing the number of rounds, which can ward off a differential attack. The slide attack works in such a way as to make the number of rounds in a cipher irrelevant. Rather than looking at the data-randomizing aspects of the block cipher, the slide attack works by analyzing the key schedule and exploiting weaknesses in it to break the cipher. The most common one is the keys repeating in a cyclic manner.

Key schedule 的意思是多轮加密中每一轮用到的 key 的次序。所以 slide attack 的原理就是找到 key 轮换的规律，来破解这种加密多次的密码。

The key insight is that this cipher, at its core, is the same round operation applied a whole bunch of times.

这篇文章的作者用如下方法破解该密码：

  1. 每一轮的 substitution+permutation 步骤完全相同，将这一加密步骤称为 ，做 次加密记为 。
  2. 假如我们有能力加密任何文本，但没有密钥，那么我们可以把任意 明文 加密为 。
  3. 现假设（猜测），那么可以得到 这组新的对应关系。由此，我们可以产生很多关于 的对应关系，从而猜出密钥。
  4. 如何做出对 的猜测？由于 Sarah2 只用到 27 个字符，这一步可以暴力枚举，比如令 以此类推。

以上就是 slide attack 的原理。

如何改进

Slide attack 利用了某些多轮密码每轮使用同一个 的弱点，因此可以考虑在每一轮对 作一些修改。例如：

  • 像 AES 和 DES 一样，用 main key 生成每一轮的 subkey。
  • 把每一个双字母组合理解为一次凯撒移位（例如 ），然后每轮结尾按表格次序 apply 这个移位。
  • LC-4 则是直接对 S-box 进行移位。

Thoughts

看文章的时候对 slide attack 和群论的联系产生了兴趣：

A bijective function from a set to itself is also called a permutation, and the set of all permutations of a set forms a **symmetry group **[sic].

也就是说，Sarah2 的所有密钥会构成一个 symmetric group of order 。

直觉告诉我用这个密钥反复加密后，会走进一个 orbit。于是这个密码系统里最安全的密钥，应该拥有最长的 orbit。于是问题就变成怎么找到某个 permutation 对应的 orbit 长度。