Hellman`s TMTO

基于文章对 TMTO (Time Memory Trade-off) 方法的简介

1. 预计算

使用确定的明文 P₀ 使用其约定的加密方式 S_k 产生密文 C₀ <需要知道 P₀ 和 C₀ 以及加密方式 ,或者 hash 函数>

并定义压缩函数 R ，将 C₀ 压缩 <保证输入输出等长，以方便 f 函数的迭代>依此来构造 函数

对输入的密钥Key <令为 X_i> ，有如下公式：

2. 查找密钥Key

随机选择一个密钥，用其对明文 P₀ 依给定规则进行一次 f 运算 得到 Y₁ 如下

将 Y₀ 与 EP_i 匹配，如果匹配到，则从SP_i开始恢复该条密钥链，此时该条链的元素 X_i 即为所需要的Key；若未匹配到，则将 Y₁ 带入 f 函数，即 Y₂ = f (Y₁)；此次若找到 Y₂ 与 EP_i 匹配，同样恢复该条链，此时， X_{i t−k}为 Y 的下标>即为所需要的 Key.

依此迭代，直到 k 大于 t ，即整条链寻找完仍然没有找到匹配

复杂度/成功概率 分析

如果对所有 mt 个元素 均不同，即k是均匀而随机的从包含所有密钥的全空间选择的，那么得到一个 理想化 的查找成功概率 P= $\frac{mt}{N}\backslash frac\{mt\}\{N\}$ ; Tn = O(t) ; Sn = O(m)

对成功概率的下限，也有

并且由此得出，对于特殊的m和t，mt² = N 成功概率是比较均衡的
若mt² << N，P(s) 会很大，但产生数据量很小，对全密钥空间的覆盖率很低
若mt² >> N , P(s)会很小，显然这是不行的
也即我们用以上公式对 P(s) 依据 m 与 t 的值进行了限制

NOTE：

1. 以上对概率Pr(X_ij is new)的计算，需满足集合内元素有Markov性，该式也是由其Markov性进行推导；
   
2. 同时其参考了生日攻击的原理，具体生日悖论的推导见：Ptr`s blog:
   https://blog.nowcoder.net/n/b3e805b7d01143529cc059198837b629

实验

文章中，Hellman 将 DES 的输出<也即输入密钥>压缩为 10 bit 即 2¹⁰ = 1024 种可能，m = t = 10 预估的成功概率的下界为

而实际选取 20 个 R 函数进行测试，得到的结果也确实在该值附近 <当然这是在一般情况下，如果在理想情况下，成功概率应该会提高到 9.8

让 m = t = N^{$\frac{1}{3}\backslash frac\{1\}\{3\}$} 这样 成功概率就可以达到 Pr⁡(s)= $\frac{mt}{N}\backslash frac\{mt\}\{N\}$ = N^{$\frac{-1}{3}\backslash frac\{-1\}\{3\}$}
Sn = Tn = O (N^{$\frac{2}{3}\backslash frac\{2\}\{3\}$} ) <需要使用不同的R生成 N^{$\frac{1}{3}\backslash frac\{1\}\{3\}$} 张表 来保证全体密钥空间的覆盖程度>

3. 误报

在 EP 点产生重叠，或者说EP的原象不止一个 文中给出了 误报的概率上界

Hellman在他的文章 “A Cryptanalytic Time - Memory Trade-Off ” 中指出了他所建的密钥链会产生重叠，也在一般情况下做了数据分析，从他的表述可以大致看出，他并未提出了一种很直接的减少重叠的方式，而是改变 Reduction function 来生成多个 TMTO 表，这种方式能够在当时很大程度上提高对全密钥空间的覆盖，但查找起来会比较麻烦。

关注后续对TMTO的改进请移步

[1]Hellman, M. A cryptanalytic time-memory trade-off[J]. IEEE Transactions on Information Theory, 1980, 26(4):401-406.
[2] Oechslin P . Making a Faster Cryptanalytic Time-Memory Trade-Off[C]// 23rd Annual International Cryptology Conference. OAI, 2003.
[3]荣凯, 邱卫东, 李萍. 基于彩虹表的Hash攻击研究[J]. 信息安全与通信保密, 2011(04):79-81+84.