improvement and analysis of vdp method in time/memory tradeoff applications | |
Wang Wenhao ; Lin Dongdai ; Li Zhenqi ; Wang Tianze | |
2011 | |
会议名称 | 13th International Conference on Information and Communications Security, ICICS 2011 |
会议日期 | November 2 |
会议地点 | Beijing, China |
关键词 | Algorithms Cryptography |
页码 | 282-296 |
中文摘要 | In many cases, cryptanalysis of a cryptographic system can be interpreted as the process of inverting a one-way function. TMTO is designed to be a generic approach that can be used on any one-way function independent of the structure of the specific target system. It was first introduced to attack block ciphers by Hellman in 1980. The distinguished point (DP) method is a technique that reduces the number of table look-ups performed by Hellman's algorithm. A variant of the DP (VDP) method is introduced to reduce the amount of memory required to store the pre-computed tables while maintaining the same success rate and online time. Both the DP method and VDP method can be applied to Hellman tradeoff or rainbow tradeoff. We carefully examine the technical details of the VDP method and find that it is possible to construct functions for which the original method fails. Based on the analysis, we propose a modification of the VDP method. Furthermore, we present an accurate version of the tradeoff curve that does not ignore the effect of false alarms and takes storage reduction techniques into consideration. We find optimal parameter sets of this new method by minimizing the tradeoff coefficient. A more exact and fair comparison between tradeoff algorithms is also given, which shows that our method applied to the Hellman tradeoff performs best among them. © 2011 Springer-Verlag. |
英文摘要 | In many cases, cryptanalysis of a cryptographic system can be interpreted as the process of inverting a one-way function. TMTO is designed to be a generic approach that can be used on any one-way function independent of the structure of the specific target system. It was first introduced to attack block ciphers by Hellman in 1980. The distinguished point (DP) method is a technique that reduces the number of table look-ups performed by Hellman's algorithm. A variant of the DP (VDP) method is introduced to reduce the amount of memory required to store the pre-computed tables while maintaining the same success rate and online time. Both the DP method and VDP method can be applied to Hellman tradeoff or rainbow tradeoff. We carefully examine the technical details of the VDP method and find that it is possible to construct functions for which the original method fails. Based on the analysis, we propose a modification of the VDP method. Furthermore, we present an accurate version of the tradeoff curve that does not ignore the effect of false alarms and takes storage reduction techniques into consideration. We find optimal parameter sets of this new method by minimizing the tradeoff coefficient. A more exact and fair comparison between tradeoff algorithms is also given, which shows that our method applied to the Hellman tradeoff performs best among them. © 2011 Springer-Verlag. |
收录类别 | EI ; SPRINGER |
会议主办者 | National Natural Science Foundation of China (NNSFC); The Microsoft Corporation; Beijing Tip Technology Corporation; Trusted Computing Group (TCG) |
会议录 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
语种 | 英语 |
ISSN号 | 0302-9743 |
ISBN号 | 9783642252426 |
内容类型 | 会议论文 |
源URL | [http://ir.iscas.ac.cn/handle/311060/16208] |
专题 | 软件研究所_软件所图书馆_会议论文 |
推荐引用方式 GB/T 7714 | Wang Wenhao,Lin Dongdai,Li Zhenqi,et al. improvement and analysis of vdp method in time/memory tradeoff applications[C]. 见:13th International Conference on Information and Communications Security, ICICS 2011. Beijing, China. November 2. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论