Time-Memory Trade-off Cryptanalysis for Limited Key on FPGA-Based Parallel Machine RASH

概要

論文の詳細を見る
We designed an FPGA-based parallel machine called "RASH"(Reconfigurable Architecture based on Scalable Hardware) for high speed and flexible signal/data processing machines because huge amounts of logical and/or simple arithmetic operations are required and FPGA is suitabie for this. One of the well-known activities in cryptanalysis is the DES (Data Encryption Standard) cracking contest conducted by RSA Data Security. TMTO (Time-Memory Trade-Off) Cryptanalysis is a practical method to dramatically shorten the time for key search when plaintext is given in adovance. A string of ASCII characters is used as the key much like a password. The ASCII character is 7-bit character and is changed to 96 kinds of value. The 56-bit DES key is given with a string of 8 ASCII characters. Although the DES key has 64 trillion(=2^<56>) possibilities, the key that is given with a string has only 6.4 trillion(=96^8) possibilities. Therefore, we improve TMTO Cryptanalysis so that we search only the limited key by ASCII characters and reduce the quantity of computation. in this paper, we demonstrate how TMTO cryptanalysis for limited key is well suited to our FPGA-based RASH machine. By limiting the key to a string, DES key will be found at 80% probability within 45 minutes after ciphertext is given on 10 units of RASH. The precomputation before starting key search takes 3 weeks on the same RASH configuration.
社団法人電子情報通信学会の論文
2003-05-01