ISAP+：实现快速认证的加密方案

# ISAP+：实现快速认证的加密方案 ## 1. 引言 在加密领域，ISAP 是一种备受关注的加密模式。不过，ISAP 需要约 256 位的容量才能满足 NIST 安全标准，这就要求使用状态大小大于 256 位的置换。因此，进一步分析该模式，探讨能否以更小的容量和更高的速率进行设计，从而直接影响吞吐量，显得尤为重要。 ## 2. 提升 ISAP 吞吐量 ### 2.1 ISAP v2 实例 ISAP v2 提出了使用 ASCON - p 和 KECCAK - p 置换的四个实例。以使用 ASCON - p（320 位置换）的 ISAP v2 为例，其设计速率为 64 位。但为了获得更高的吞吐量，实现更高的速率设计是更好的选择，其他实例也存在类似的情况。 ### 2.2 潜在改进方向 一个潜在的改进方向是设计一种算法，提高容量的安全边界，从而在不降低安全级别的前提下提高速率。增加安全边界还能帮助设计者以更小的状态大小实现相同的安全性，进而通过使用状态更小的置换来减小寄存器大小。可以重点分析 ISAP 在超越生日界（BBB）的 NAEAD 安全方面的表现。 ### 2.3 ISAP 安全分析 ISAP 采用了一种高效的方法，先对随机数、关联数据和密文应用无密钥哈希函数，然后对哈希值使用伪随机函数（PRF）。在这种情况下，NAEAD 模式的安全性归结为底层哈希函数的碰撞安全性。该模式可以避免存储主密钥，无需密钥寄存器。然而，哈希碰撞会导致相对较低的安全边界，这在超轻量级应用中可能并不总是可接受的，因为低安全边界会迫使设计采用状态大小较大的原语。因此，提高安全边界有很大潜力显著提高设计的硬件性能。 ### 2.4 安全边界问题 Dobraunig 等人的安全证明表明，ISAP 在容量上的安全性可达生日界，即 $O(T^2/2^c)$，其中 $T$ 是时间复杂度，$c$ 是容量大小（以位为单位）。这一因素源于对随机数、关联数据和随机密文应用的简单海绵型哈希。在随机数和关联数据中容易出现碰撞，攻击者可以利用这些碰撞进行伪造。但随机密文中的碰撞如何导致此类攻击并不明显。因此，我们需要研究在哈希过程中每次置换调用可注入的密文位数，并思考能否提高哈希中密文块的吸收速率。 ## 3. 研究贡献 ### 3.1 提出 EtHM 范式 我们提出了一种基于置换的通用 EtHM（先加密后哈希的消息认证码）类型的 NAEAD 模式，使用 PRF 和无密钥哈希函数。这本质上是 ISAP 类型构造的推广。需要注意的是，这种通用模式并不保证任何侧信道抗性，只有 PRF 的正确实例化才能确保这一点。EtHM 的 NAEAD 安全性可以用固定输入长度、可变输出长度的密钥函数 $F$ 的 PRF 安全性和 $H$ 的 2PI + 安全性来表示。直观地说，2PI + 概念要求在攻击者选择一定长度的挑战随机消息后，攻击者难以计算该随机消息的第二个原像。 ### 3.2 海绵哈希安全分析 - **通用海绵哈希**：对于通用海绵哈希，碰撞攻击可以扩展为 2PI + 攻击。因此，通用海绵哈希的 2PI + 安全性为 $\Omega(T^2/2^c)$，其中 $c$ 是海绵哈希的容量。 - **前馈变体海绵哈希**：考虑一种前馈变体的海绵哈希，它使用通用海绵哈希处理随机数和关联数据，使用前馈变体处理消息。前馈特性确保碰撞攻击无法扩展为 2PI + 攻击。实际上，这种变体的海绵哈希获得了改进的安全性 $O(DT/2^c)$。这里 $D$ 和 $T$ 分别是数据和时间复杂度，通常允许 $T \approx D^2$。因此，基于前馈的海绵在安全性方面表现更好，因为我们从 $D$ 和 $T$ 两个参数来考虑安全性，而不是传统的单参数安全性。 ### 3.3 提出 ISAP + 我们考虑了一种对 ISAP 进行最小修改的简单变体，名为 ISAP +，它是通用 EtHM 模式的一个具体实例。ISAP + 与 ISAP 的区别如下： - **哈希函数**：ISAP + 使用前馈变体的海绵哈希，而不是 ISAP 中使用的通用海绵哈希。 - **容量使用**：在 ISAP + 的认证模块中，处理随机数、关联数据和密文的第一个块时使用 $c'$ 位的容量，处理其余密文块时使用 $c$ 位的容量。 - **消息分离**：根据消息长度是否小于 $r'$ 位对消息进行分离。在最后一次置换调用之前，通过在容量部分添加 0 或 1 来进行域分离。 这些修改确保 ISAP + 实现了改进的安全性 $O(T^2/2^{c'} + DT/2^c)$，其中 $n$ 是状态大小或置换的大小（以位为单位），$c' = n - r$，$c' = n - r'$。这种安全提升使设计者能够有效地选择 $c'$ 和 $c$（$c < c'$）以获得更好的吞吐量。 ## 4. 工作相关性 ### 4.1 实例对比 为了理解改进安全性的相关性，我们考虑使用 ASCON 和 KECCAK 实例化 ISAP，并将其与 ISAP + 进行比较。为了满足 NIST 要求，ISAP + 可以使用 $c = 192$，$c' = 256$，因此其密文注入速率为 128 位，关联数据注入速率为 64 位。以下是 ISAP 和 ISAP + 在认证模块所需置换调用次数方面的比较： | 模式 | 置换参数 | 置换调用次数 | | ---- | ---- | ---- | | ISAP（ASCON） | $r = 64$ | $\lceil\frac{a + m + 1}{64}\rceil$ | | ISAP +（ASCON） | $r = 128$，$r' = 64$ | $\lceil\frac{a + 1}{64}\rceil + \lceil\frac{m}{128}\rceil$ | | ISAP（KECCAK） | $r = 144$ | $\lceil\frac{a + m + 1}{144}\rceil$ | | ISAP +（KECCAK） | $r = 208$，$r' = 144$ | $\lceil\frac{a + 1}{144}\rceil + \lceil\frac{m}{208}\rceil$ | ### 4.2 具体示例 以使用 ASCON 置换加密长度为 1 MB 的消息和长度为 1 KB 的关联数据为例。使用 ISAP 时，认证模块大约需要 131,201 次原语调用；而使用 ISAP + 时，仅需要 65,665 次原语调用，几乎是 ISAP 的一半。这表明在需要处理长消息的应用中，ISAP + 在吞吐量和速度方面优于 ISAP。 ## 5. 预备知识 ### 5.1 符号说明 - 通常使用小写字母（如 $x$，$y$）表示整数和索引，大写字母（如 $X$，$Y$）表示二进制字符串和函数，花体大写字母（如 $\mathcal{X}$，$\mathcal{Y}$）表示集合和空间。 - $\mathbb{N}$ 和 $\mathbb{Z}$ 分别表示自然数集和整数集。$0^x$ 和 $1^y$ 分别表示 $x$ 个 0 和 $y$ 个 1 的序列。 - $\{0, 1\}^x$ 和 $\{0, 1\}^*$ 分别表示长度为 $x$ 的二进制字符串集合和所有二进制字符串的集合。 - 对于任何 $X \in \{0, 1\}^*$，$|X|$ 和 $\|X\|$ 分别表示二进制字符串 $X$ 的位数和块数，块的大小应根据上下文明确。 - 对于两个二进制字符串 $X$ 和 $Y$，$X \| Y$ 表示 $X