【Cryptography/Cryptanalysis】Cryptanalysis method based on TMTO

1 背景

TMTO全称Time-memory Trade-off,Translates to time-Storage compromise attack.TMTOFind a compromise between computational space and computational time,The computational efficiency can be greatly improved、降低计算成本,Good for a range of search tasks such as knapsack and discrete logarithm problems.这种时间-The method of storing tradeoffs is a probabilistic model, 无法确保100%成功率, The size of the success rate will depend on the time allocated and the size of the memory.

2 TMTO过程

for fixed plaintextPand some ciphertextC0,Known encryption algorithmS,The goal is to recover the key used in the encryption processK0：

针对这个问题, Martin Hellman 在 1980 Year presented time-Storage compromise attack(TMTO)的方法.

2.1 加密链

The ciphertext is used as the key for the next iteration,Use the same in each iteration（所选择的）明文P.
Similar to a rainbow table,选取tdifferent conversion functions,预计算mencrypted chain,Each chain has a length of t+1,Only the beginning and end of the chain are stored.

to the endpointEPi（0≤i≤m-1）的低nBit is the index,will total storage spaceM划分为2n块.storage per blockk个二元组,Here the dyad is （SPi,HPi）,HPi为EPi的高s-n比特.
当EPi的低nThe decimal size of bits is z时, will be a 2-tuple (SPi, HPi) Save to the starting address of Pz的块中, 如果HPialready exists in this block, then discard the 2-tuple, if the block is fullk个二元组, The binary is also discarded.To speed up table searches during the online analysis phase, Finally, the bigrams in each block start with HPi排序.

2.3 在线检索

In the process of retrieving the keytab online, for any ciphertext Ci , If the key corresponding to it is included in the above key table, Then the key can be retrieved in the following ways.
Choose the same plaintextP,Get its corresponding ciphertextC,计算

把Xiend node with storageEP0,EP1,……,EPm-1相比较,假设Xi=EPj

则从SPj开始,构造

3 理想TMTO算法

TMTOThe critical steps are expected to be a one-time effort,The results are stored in a table.Use precomputed results to make each subsequent computation faster,The goal of balancing memory and time as much as possible is achieved.一般来说,Larger precomputes require more initial work and larger“内存”,But required for each calculation“时间”越少.
理想情况下,All chains do not overlap each other.
Let the length of the chain be t,The number of chains is m,密钥空间为2^k,Then the time complexity of preprocessing is O（tm）=2^k.
The time complexity of a single crack is O（t）,空间复杂度为O（m）,A compromise between time and space is achieved.

4 Example of rainbow table method

4.1 Rainbow table algorithm

Rainbow table algorithm by Oechslin于2003年提出,This method can greatly reduce chain-to-chain collisions and merges.在原始的TMTO 方法中, Hellman Use different reduction functions in different tables to improve coverage,然而, Chain-to-chain collisions and mergers still abound.To avoid such situations, The rainbow table makes a slight change in its structure: Design different reduction functions{R1,……, R(t−1)}, 对每一列, The hash chain calls different ones in turnRi. The iterative formula for constructing the hash chain becomes:

在彩虹表中,The aforementioned collisions and mergers will be drastically reduced.
彩虹表(Rainbow Table)The technology can be understood as a cracking technology for the hash algorithm.The core idea is to map the ciphertext to the password in the plaintext space according to certain rules,This rule is called a reduction function（R1,R2,R3,…,Rk）.
During the construction stage of the rainbow table,First use a hashing algorithm to put a password in the plaintext spacem0Map to ciphertextC1,Then use the reduce functionR1,将密文C1Mapped to another plaintextm1,使用哈希函数、The reduction function iterates sequentially,得到m0,C1,C2,…,mk-1,Ck,mk.m0和mkare the first and last nodes of the chain, respectively,Store both nodes,Multiple rainbow chains make up a rainbow table.
for a known ciphertextC来说,Want to get its corresponding ciphertext,It can be done in the following three process steps.

• 步骤一:对密文CUse a reduce function,计算出明文m1,Retrieve rainbow tables,If included in the end nodem1,则说明CThe corresponding plaintext may exist in the rainbow chain,The hash function is performed from the first node of the chain、The reduction function iterates sequentially,if present in the chainCk与C相等,Then the calculation result of the previous stepmk-1则为CThe corresponding correct plaintext,破解成功.
• 步骤二:If not found in end nodem1,则以m1为起点,Use the hash function and the reduction function in turn to calculate the plaintext once,Follow the process of step 1 to find the end node,If not found, repeat step 2 to continue searching.
• 步骤三:When the number of repetitions is greater than the total number of chains in the rainbow table,Describe the ciphertextCNot stored in this rainbow table,破解失败.
  

4.2 Practical verification of rainbow table algorithm

首先使用Python脚本,md5加密一个字符串.

使用RainbowCrack,Generate rainbow tables for password cracking.RainbowCrack与“常规”The brute force method is different,它使用名为Rainbow Tableslarge precomputed tables to greatly reduce the time required to crack passwords.
Generate a rainbow table.

对彩虹表进行排序.

Cracking the pre-obtained ciphertext,得到16进制结果“6b616c69”,对照acsii表,得到明文“kali”.

5 参考文献

[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[J]. In: Advances in Cryptology—CRYPTO 2003. Springer Berlin Heidelberg, 2003: 617–630. [DOI: 10.1007/978-3-540-45146-4_36]
[3]in Hongbo,何乐,Cheng Zijie.Research on the improvement of checkpoint algorithm based on perfect rainbow table[J].密码学报,2021,8(01):76-86.DOI:10.13868/j.cnki.jcr.000421.
[4]Zheng Zhongxiang,Ji Qingbing,in Hongbo.Rainbow table based time-Storage compromise attack improved algorithm[J].密码学报,2014,1(01):100-110.DOI:10.13868/j.cnki.jcr.000010.
[5]Luo Jiang Stone,I wish you leap,Gu Chunxiang.A space-time compromise method for rainbow tables based on block storage structure[J].计算机工程,2012,38(15):111-113.
[6]Zhang Dongfang,Guan Lei,Dai Xiaomiao.The design and implementation of the rainbow table lookup system for password cracking[J].网络空间安全,2020,11(11):1-5.