Choosing Parameters to Achieve A Higher Success Rate for Hellman Time Memory Trade Off Attack

2009-03-19
Saran, Ayşe Nurdam
Doğanaksoy, Ali
In 1980, Hellman proposed the Time Memory Trade Off (TWTO) attack and applied it on block cipher DES (Data Encryption Standard). Time Memory Trade Off attack is one of the methods that inverts a one way function. The resistance to TWO attacks is an important criterion in the design of a modern cipher Unlike the exhaustive search and table lookup methods, TWO is a probabilistic method, that is, the search operation may not find a preimage even if there exists one. Up to now, there are some approximate bounds for success rates of Hellman table by Hellman and Kusuda et al. In this study, we give a more precise approximation for the coverage of a single Hellman table. There is no precise guideline in the literature that points out how to choose parameters for Hellman TWO. We present a detailed analysis of the success rate of Hellman table via new parameters and also show how to choose parameters to achieve a higher success rate. The results are experimentally confirmed. We also discuss the Hellman's TMTO Curve.

Suggestions

Basic cryptanalysis methods on block ciphers
Çelik, Dilek; Doğanaksoy, Ali; Department of Cryptography (2010)
Differential cryptanalysis and linear cryptanalysis are the first significant methods used to attack on block ciphers. These concepts compose the keystones for most of the attacks in recent years. Also, while designing a cipher, these attacks should be taken into consideration and the cipher should be created as secure against them. Although di fferential cryptanalysis and linear cryptanalysis are still important, they started to be ine cient due to the improvements in the technology. So, these attacks are ...
An Analysis on efficient polynomial multiplication algorithms for cryptographic purposes
İlter, Murat Burhan; Cenk, Murat; Department of Cryptography (2016)
The idea of Public Key Cryptography showed up after the studies conducted by W. Diffie and M. Hellman in 1976. In the light of these works, RSA, the first Public Key Cryptography algorithm, came into play. In this algorithm, modular exponentiation is highly costly. In addition to this, key sizes of public key cryptography algorithms has become longer in order to ensure the security as the time passes. For these reasons, the speed of algorithms is relatively slower when it is compared to the speed of ones in...
Impossible differential cryptanalysis of reduced round HIGHT
Tezcan, Cihangir; Doğanaksoy, Ali; Department of Cryptography (2009)
Design and analysis of lightweight block ciphers have become more popular due to the fact that the future use of block ciphers in ubiquitous devices is generally assumed to be extensive. In this respect, several lightweight block ciphers are designed, of which HIGHT is proposed by Hong et al. at CHES 2006 as a constrained hardware oriented block cipher. HIGHT is shown to be highly convenient for extremely constrained devices such as RFID tags and sensor networks and it became a standard encryption algorithm...
Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT
Ozen, Onur; Varici, Kerem; Tezcan, Cihangir; Kocair, Celebi (2009-07-03)
Design and analysis of lightweight block ciphers have become more popular due to the fact that the future use of block ciphers in ubiquitous devices is generally assumed to be extensive. In this respect, several lightweight block ciphers are designed, of which PRESENT and HIGHT are two recently proposed ones by Bogdanov et al. and Hong et al. respectively. In this paper, we propose new attacks on PRESENT and HIGHT. Firstly, we present the first related-key cryptanalysis of 128-bit keyed PRESENT by introduci...
Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber
Aksoy, Berkin; Cenk, Murat; Department of Cryptography (2022-2-28)
Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptography (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type {Z}_{q}[x] / f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC S...
Citation Formats
A. N. Saran and A. Doğanaksoy, “Choosing Parameters to Achieve A Higher Success Rate for Hellman Time Memory Trade Off Attack,” 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/47411.