Improving Time Memory Trade Off Methodology for Key Space Larger than Block Space

Abstract

Cryptanalysis is the science of attacking cryptosystems. Many people believe that cryptanalysis only done by attackers but nowadays many researchers perform cryptanalysis to check the security of the cryptosystem in public domain. Block ciphers have been the most popular cryptosystems so far hence they must go through a lot of cryptanalysis work to check their security. Many attack models has been proposed so far for attacking block cipher. The intuitive attack is Exhaustive key search, searching for secret key by trying all possible keys but this method consume a lot of time. For lengthy keys like 128 bit implementing exhaustive key search may take several decades in absence of quantum computers. Tabulation attacks are a step ahead of exhaustive key search, here we store some pre computation and avoid repeated computation but requires a lot of memory. So Time Memory Trade off (TMTO) attack were the key to solve this problem, here we try to make balance between time and memory requirements. Hellman in 1980, proposed a TMTO method to attack most popular block cipher at that time DES also this research contributed in inverting the one way functions. But this method was proposed for the block ciphers whose key length was smaller as compared to block length. So in thesis, I proposed a method that can attack block ciphers whose key length is larger than block length by extending Hellman’s TMTO attack Model. In this method a general Substitution Permutation Network, with key length of 16 bit and block length of 8 bit, is used as block cipher and achieved the success probability of 0.58 in case of ideal parameters suggested by Hellman, which is comparable to Hellman’s existing work.