𝖄𝕺🌎𝕿𝕽𝕺¥

XOR#

XOR 是 “异或” 运算的简称，是一种基本的位运算。它的运算规则是对两个比特位进行比较，如果两个比特位相同，则结果是 0；如果两个比特位不同，则结果是 1。

因为≠ 0.5，所以是有信息的。那么即使只有一个子集的值，也能以大致相同的方式利用偏差。甚至 0.5000001。

source of info = 如果输入表达式与输出表达式的一致程度不超过 0.5，那么其中一个表达式就是另一个表达式的信息源。

Linear Cryptanalysis#

• 明文和密文可见
• 是 known plaintext attack
• 足够多的明文和密文对来寻找输入位和输出位之间的线性关系。
• 要求足够好的线性逼近。
• 指 针对块密码发起的一类攻击。
• 通过线性表达式（用 mod-2 比特运算表示的一些变量）来逼近块密码。
• 这些表达式的真（或假）带有一定的偏差，利用这种偏差来发现关键比特。

Substitution Boxes (S-box)#

1. 确定 S 框的偏差、构建 LAT。
2. 用 (有偏差的）线性表达式。
3. 链接表达式从初始明文到中间密码文本。
4. 通过 Matsui 的偏差定理。
5. 对于最后的子键，确定表达式的成立频率
6. 如果匹配偏差，你就发现了密钥！
7. 对每个子键重复上述步骤。

以查找表的形式实现的，但不能随着输入量的增加而扩展，因此必须以不同的方式计算输出，即以输入位的表达式来计算。e.g.

Approximating Sboxes#

one key XORing and one Substitution Box

假设 X3 ⊕ X4 = Y1 ⊕ Y4，

那么 K3 ⊕ K4 = P3 ⊕ P4 ⊕ Y1 ⊕ Y4

Linear Approximation Table (LAT) for S-boxes#

分析：

• x 表示输入，y 表示输出
• 这是偏差表：
  • 0 表示无偏，则 probability 为 0.5。
  • + 表示实际出现比预期多了，- 表示实际出现比预期少了
• 不为 0 则表示有信息，绝对值越大包含信息越多

A [1,2] 意味着输入掩码为 '01'，这意味着我们只关心输入的第二位。输出掩码为 '10'，这意味着我们只关心输出的第一位。

计算每个输入对应的输出位的 XOR 值#

我们需要对每个输入执行以下子步骤：

1. 查看 S-box 中该输入的输出值。
2. 将输入掩码应用于输入值，只保留掩码对应位为 1 的位。
3. 将输出掩码应用于输出值，同样只保留掩码对应位为 1 的位。
4. 计算这两个位的 XOR 值。

01 00 11 10 → 1010

11 01 10 00 → 1010

XOR → 0000 = 4/4

so answer is +2

also for B answer is -2

Matsui’s Piling Up Lemma#

用来计算多个变量的偏差

• e.g. ：bias 不为 0

• e.g.： 只要有一个为 0，最终结果就是无偏。例子 Z2 是无偏的，有效地随机化了 Z1 ⊕ Z2

• 结论：公式如下

Linking S-box Approximations#

步骤：

• 如何计算 probability？根据input而不是 output，如图例子得出 G2 的近似值
• 有了近似值，减去预期概率（一般是 1/2）得到 bias
• 共同 XOR，消掉中间节点变到等号右边，变成求 = 0 的概率
• 带入 Matsui’s Lemma 公式求该值

• 继续算整体的，例子如下
  • Substituting 步骤中都出现了 G2，所以 XOR 变成 0，变到等号右边
  • 同时求出 = 1 的概率为 5/8

• 转换例子

• 计算例子

• 上例 XOR 公式的转换，所以结果一样

• 以上转换的总结

Discovering Keys#

可见？#

• 该系统只有 plaintext P 和 ciphertext C 可见，毕竟是线性密码分析

Final Round Key#

最后一轮 S-box 是可逆的 invertible，所以可以算出对应的 U

对于密码分析者猜测的任何一轮密钥，他们都能生成 U

1. 假设一个最后一轮密钥，得到中间密文，这代表了加密过程中的 U1, U2, U3, U4 等中间步骤。
2. 如果猜测的密钥是正确的，那么中间密文就是正确的。
3. 接下来，有了 P 和 U 和 C 计算近似表达式（approx. expression），它有一定的偏差（bias），比如 1/8 或者 3/8。
4. 如果这个近似表达式与观察到的偏差匹配，那么可以认为假设的密钥是正确的。
5. 如果猜测的密钥是错误的，则中间密文也是错误的。
6. 如果一个或多个密钥位猜错了，那么这个近似表达式将只会有 1/2 的时间成立，因为结果是随机化的。

因此，通过比较假设密钥下的近似表达式与 1/2 的偏差，可以区分出正确或错误的密钥猜测。最后，尝试所有可能的最后一轮密钥，看看哪一个的 (P,U) 近似值与 1/2 的偏差最不一致，这个密钥很可能就是实际的密钥。

Applying#

Substitution Permutation Network( Hey’s Cipher)#

• 在这个体系中，Heys' Cipher 通过重复的替代和置换操作以及密钥混合来增强加密的安全性。
• 3 轮 S-box: XORing，所有的 S-box 都是相同的。
• P-box: 置换盒，permuting，它按照特定的规则重新排列位，以扩散每轮中输入的任何变化。
• 16 位子密钥: 假设为独立生成，通常是通过密钥计划得到，类似于 DES（数据加密标准）中的做法。
• 例子：每个 probability 都是 input
• 密钥混合采用的是逐位异或操作。

• E2E 指的是端到端的近似，从明文到密文的整个加密流程。

  

  

  如果你拥有足够多的明文 - 密文对，理论上你可以利用这种线性近似来解密或更准确地猜测密钥。

• 如何计算？ 同样 Matsui’s Lemma

  

  

  关键子块和反推：

  • 目标：生成 Intermediate Ciphertexts，通过 K5 和 C（第二和四个 subset）
  • 和 1st 和 3rd subset 无关，所以 interest 是 2nd 和 4th。

  C 到 U，正确 K 得到正确 U，反之亦然

  

  

  Try All Subkeys#

  • 表中只展示了一部分子建，假设有 64 个 subkeys
  • 假设有 10000 个 ptxt-ctxt 对，使用 64 个 subkeys
  • 对于每个 p-c 对，c 和 subkey 生成 p，计算 bias
  • 偏差最大的子键通常是正确的，但并不总是。
  • 可以看到 subkeys 为 24 时 bias 最大，候选