新的時間空間取捨攻擊法於單向雜湊函數預存映像

New Time-Memory Tradeoffs of Preimage Attacks to One-Way Hash Functions

陳麒元(Chi-Yuan Chen)

指導教授 ： 張仁俊 ； 吳信龍

國立臺北大學/電機資訊學院/電機工程研究所/碩士(2010年)

摘要

預存映像攻擊的目標是找到一個加密函數的輸入值，該輸入值對應到加密函數的一個輸出值，在此篇論文我們運用預存映像攻擊來破解輸入值k是大於輸出值n的單向雜湊函數，使用以往time memory trade-off方法中Hellman與Oechslin的方法來應用於預存映像攻擊，離線階段需要Ω(2^k)的計算步驟，線上階段需要Ω(2^(2k/3))的計算步驟與Ω(2^(2k/3))儲存單位，當k大於或等於2n時Ω(2^(2k/3))遠大於〖O(2〗^n)，在這個情況下以往的time memory trade-off的方法並不是非常的有效率，因此我們修改Oechslin的方法並且設計一個新的方法，我們的方法在離線階段減少為〖O(2〗^n)，線上階段的時間與儲存空間減少為O(2^(2k/3)) 此外我們提出了我們方法的成功率理論界限並實作結果與理論相符。

關鍵字

時間空間取捨攻擊法 ； 預存映像 ； 單向雜湊函數

並列摘要

The objective of the preimage attack to a cryptographic function is to find a possible input value which is mapped to a given output value of the cryptographic function. In this thesis, we consider preimage attacks to one-way hash functions where the input length k is larger than the output length n. By applying Hellman's or Oechslin's previous cryptanalytic time memory tradeoffs directly to the preimage attacks, the offline preprocessing phase needs Ω(2^k) computation steps, and the online phase requiresΩ(2^(2k/3)) computation steps andΩ(2^(2k/3)) memory units. Note that when k is greater than or equal to 2n, Ω(2^(2k/3)) is far larger than 〖O(2〗^n). That is, the previous cryptanalytic time-memory trade-offs are not efficient. Here we modify Oechslin's time-memory tradeoff based on rainbow tables and design a new time-memory trade-off method. With our method, the time complexity of the offline preprocessing phase is reduced to 〖O(2〗^n), and the time complexity and memory complexity of the online phase are both reduced to O(2^(2k/3)). Furthermore, we analyze and give a theoretical bound for the success probability of our method. Finally, the experimental result gives us a strong evidence to support our theoretical bound.

並列關鍵字

time memory trade-off ； pre-image ； one-way hash function

參考文獻

[2] Alex Biryukov, Sourav Mukhopadhyay, Palash Sarkar, Improved Time-

Memory Tradeo s with Multiple Data, proceedings of Selected Areas in

Cryptography 2005, Lecture Notes in Computer Science 3897, pp. 245-260,

[3] Alex Biryukov, Adi Shamir, Cryptanalytic Time/Memory/Data Tradeo s for

Lecture Notes in Computer Science 1976, pp. 1-13, Springer-Verlag, 2000.