# A cryptanalytic time-memory trade-off

@article{Hellman1980ACT, title={A cryptanalytic time-memory trade-off}, author={Martin E. Hellman}, journal={IEEE Trans. Inf. Theory}, year={1980}, volume={26}, pages={401-406} }

A probabilistic method is presented which cryptanalyzes any N key cryptosystem in N^{2/3} operational with N^{2/3} words of memory (average values) after a precomputation which requires N operations. If the precomputation can be performed in a reasonable time period (e.g, several years), the additional computation required to recover each key compares very favorably with the N operations required by an exhaustive search and the N words of memory required by table lookup. When applied to the… Expand

#### Figures and Topics from this paper

#### 680 Citations

A Cryptanalytic Time-Memory Tradeoff: First FPGA Implementation

- Computer Science
- FPL
- 2002

The experimental results for the cryptanalysis of DES that are presented are based on a time-memory tradeoff using distinguished points, a method which is referenced to Rivest [2]. Expand

A New Cryptanalytic Time-Memory Trade-Off for Stream Ciphers

- Computer Science
- ISCIS
- 2005

The application of the rainbow chain model as a time-memory trade-off attack for stream ciphers is presented. Expand

The Full Cost of Cryptanalytic Attacks

- Computer Science, Mathematics
- Journal of Cryptology
- 2003

The full costs of several cryptanalytic attacks are determined, including Shanks’ method for computing discrete logarithms in cyclic groups of prime order n, which requires n1/2+o(1) processor steps but, when all factors are taken into account, has full cost n2/3+ o(1). Expand

A time memory trade off attack against A5/1 algorithm

- Computer Science
- Proceedings of the IEEE 12th Signal Processing and Communications Applications Conference, 2004.
- 2004

Two types of attacks against the GSM security algorithm, A5/1, are discussed, which obtain the initial state of the LFSRs just after the encryption key (Kc) and frame number are loaded, in the light of known plaintext. Expand

Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers

- Computer Science
- ASIACRYPT
- 2000

This paper shows that a combination of the two approaches has an improved time/memory/data tradeoff for stream ciphers of the form TM2D2 = N2 for any D2 ≤ T ≤ N. Expand

Making a Faster Cryptanalytic Time-Memory Trade-Off

- Computer Science
- CRYPTO
- 2003

A new way of precalculating the data is proposed which reduces by two the number of calculations needed during cryptanalysis and it is shown that the gain could be even much higher depending on the parameters used. Expand

Distributed Cryptanalytic Time-Memory Trade-Offs

- 2020

Information security is usually based on secrets known by authorized parties only, e.g., passwords, PIN codes, and cryptographic keys. Breaking a system means either circumventing the security… Expand

Applying Time-Memory-Data Trade-Off to Plaintext Recovery Attack

- Computer Science
- ICICS
- 2012

A new attack for block ciphers is proposed by applying the well known time-memory-data (TMD) trade-off to plaintext recovery attack (PRA), thus creating two new schemes: TMD-PRA-I and T MD- PRA-II, which have favourable performance. Expand

Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE

- Computer Science
- EUROCRYPT
- 2015

The FX-construction increases the security of an \(n\)-bit core block cipher with a \(\kappa \)-bit key by using two additional \(n\)-bit masking keys, proving to guarantee about \(127-d\) bits of security. Expand

FPGA Implementation of a Cryptanalytic Time-Memory tradeoff

- 2002

There are two naive approaches to breaking a block cipher with k-bit keys: exhaustive key search and precomputation table. Exhaustive key search is a knownplaintext attack. Given a ciphertext C, the… Expand

#### References

SHOWING 1-10 OF 12 REFERENCES

An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (Corresp.)

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1978

An improved algorithm is derived which requires O =(\log^{2} p) complexity if p - 1 has only small prime factors and such values of p must be avoided in the cryptosystem. Expand

Hiding information and signatures in trapdoor knapsacks

- Computer Science
- IEEE Trans. Inf. Theory
- 1978

Specific instances of the knapsack problem that appear very difficult to solve unless one possesses "trapdoor information" used in the design of the problem are demonstrated. Expand

New directions in cryptography

- Computer Science
- IEEE Trans. Inf. Theory
- 1976

This paper suggests ways to solve currently open problems in cryptography, and discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing. Expand

Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard

- Computer Science
- Computer
- 1977

This paper presents a meta-modelling system that automates the very labor-intensive and therefore time-heavy and expensive process of manually cataloging and cataloging individual pieces of data to provide real-time information about their owners. Expand

Privacy and authentication: An introduction to cryptography

- Computer Science
- Proceedings of the IEEE
- 1979

The basic information theoretic and computational properties of classical and modern cryptographic systems are presented, followed by cryptanalytic examination of several important systems and an examination of the application of cryptography to the security of timesharing systems and computer networks. Expand

Group codes for the Gaussian broadcast channel with two receivers

- Computer Science
- IEEE Trans. Inf. Theory
- 1980

The two-receiver Gaussian broadcast channel is a model of a communication system where a single codeword is transmitted over two distinct Gaussian channels that have different signal-to, noise… Expand

An Introduction To Probability Theory And Its Applications

- Computer Science
- 1950

A First Course in Probability (8th ed.) by S. Ross is a lively text that covers the basic ideas of probability theory including those needed in statistics. Expand

An improved algorithm for NLY 1980 computing logarithms over GF(p) and its cryptographic significance

- IEEE TRANSACTIONS ON INFORMATION THEORY IEEE Tram. Inform Theory
- 1978

Exhaustive cryptanalysis of the NBS data encryption standard

- Comput
- 1977