当前位置:网站首页>【Cryptography/Cryptanalysis】Cryptanalysis method based on TMTO
【Cryptography/Cryptanalysis】Cryptanalysis method based on TMTO
2022-08-01 00:32:00 【Tyfrank】
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,密钥空间为2k,Then the time complexity of preprocessing is O(tm)=2k.
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.
边栏推荐
- Web API Introduction and Types
- thymeleaf迭代map集合
- qlib量化源码分析:qlib/qlib/contrib/model/gbdt.py
- Application of integrated stepper motor in UAV automatic airport
- In 2022, the latest eight Chongqing construction members (electrical construction workers) simulation question bank and answers
- Named Entity Recognition - Model: BERT-MRC
- Classes and Objects: Medium
- 一行代码解决CoreData托管对象属性变更在SwiftUI中无动画效果的问题
- C# Rectangle基本用法和图片切割
- MYSQL主从复制
猜你喜欢
Carefully organize 16 MySQL usage specifications to reduce problems by 80% and recommend sharing with the team
Recommendation system: Summary of common evaluation indicators [accuracy rate, precision rate, recall rate, hit rate, (normalized depreciation cumulative gain) NDCG, mean reciprocal ranking (MRR), ROC
RTL8762DK 使用DebugAnalyzer(四)
Key Points Estimation and Point Instance
MYSQL查询截取优化分析
从零造键盘的键盘超级喜欢,IT人最爱
【云驻共创】【HCSD大咖直播】亲授大厂面试秘诀
一行代码解决CoreData托管对象属性变更在SwiftUI中无动画效果的问题
虹科分享|如何用移动目标防御技术防范未知因素
cobaltstrike
随机推荐
ROS2系列知识(4): 理解【服务】的概念
leetcode:126. 单词接龙 II
The role of /etc/resolv.conf
Automated machine learning pycaret: PyCaret Basic Auto Classification LightGBM
游戏安全03:缓冲区溢出攻击简单解释
Unity3D学习笔记10——纹理数组
Web3.0: Building an NFT Market (1)
MYSQL主从复制
网关gateway跨域
Notes on how to use zeno
Xinao Learning Plan The Road to Informatics Competition (2022.07.31)
自动化机器学习pycaret: PyCaret Basic Auto Classification LightGBM
如何编辑epub电子书的目录
命名实体识别-模型:BERT-MRC
SVN server construction + SVN client + TeamCity integrated environment construction + VS2019 development
面试突击69:TCP 可靠吗?为什么?
2022年CSP-J1 CSP-S1 第1轮初赛 报名指南
Thinking and Implementation of Object Cache Service
MYSQL查询截取优化分析
谷歌『云开发者速查表』;清华3D人体数据集;商汤『通用视觉框架』公开课;Web3极简入门指南;高效深度学习免费书;前沿论文 | ShowMeAI资讯日报