Publication

Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints

Philippe Oechslin, Gildas Avoine, Pascal Junod
2005
Conference Papers

Abstract

Since the original publication of Martin Hellman's cryptanalytic time-memory trade-off, a few improvements on the method have been suggested. In all these variants, the cryptanalysis time decreases with the square of the available memory. However, a large amount of work is wasted during the cryptanalysis process due to so-called "false alarms". In this paper we present a method of detection of false alarms which significantly reduces the cryptanalysis time while using a minute amount of memory. Our method, based on "checkpoints", reduces the time by much more than the square of the additional memory used, e.g., an increase of 0.89% of memory yields a 10.99% increase in performance. Beyond this practical improvement, checkpoints constitute a novel approach which has not yet been exploited and may lead to other interesting results. In this paper, we also present theoretical analysis of time-memory trade-offs, and give a complete characterization of the variant based on rainbow tables.

Official source

https://infoscience.epfl.ch/entities/publication/f87d47e5-a73a-4175-bc9d-5f900610775c

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Philippe Oechslin, Gildas Avoine, Pascal Junod
2005
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/f87d47e5-a73a-4175-bc9d-5f900610775c

About this result

Related concepts (24)

Working memory

Working memory is a cognitive system with a limited capacity that can hold information temporarily. It is important for reasoning and the guidance of decision-making and behavior. Working memory is often used synonymously with short-term memory, but some theorists consider the two forms of memory distinct, assuming that working memory allows for the manipulation of stored information, whereas short-term memory only refers to the short-term storage of information.

Data Encryption Standard

The Data Encryption Standard (DES ˌdiːˌiːˈɛs,_dɛz) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography. Developed in the early 1970s at IBM and based on an earlier design by Horst Feistel, the algorithm was submitted to the National Bureau of Standards (NBS) following the agency's invitation to propose a candidate for the protection of sensitive, unclassified electronic government data.

History of cryptography

Cryptography, the use of codes and ciphers to protect secrets, began thousands of years ago. Until recent decades, it has been the story of what might be called classical cryptography — that is, of methods of encryption that use pen and paper, or perhaps simple mechanical aids. In the early 20th century, the invention of complex mechanical and electromechanical machines, such as the Enigma rotor machine, provided more sophisticated and efficient means of encryption; and the subsequent introduction of electronics and computing has allowed elaborate schemes of still greater complexity, most of which are entirely unsuited to pen and paper.

Related publications (30)

Secure and Efficient Cryptographic Algorithms in a Quantum World

Loïs Evan Huguenin-Dumittan

Since the advent of internet and mass communication, two public-key cryptographic algorithms have shared the monopoly of data encryption and authentication: Diffie-Hellman and RSA. However, in the last few years, progress made in quantum physics -- and mo ...

EPFL2024

2D Nanosystems: Applications of 2D Semiconductors for In-Memory Computing

Guilherme Migliato Marega

Machine learning and data processing algorithms have been thriving in finding ways of processing and classifying information by exploiting the hidden trends of large datasets. Although these emerging computational methods have become successful in today's ...

EPFL2023

Computational models of episodic-like memory in food-caching birds

Wulfram Gerstner, Johanni Michael Brea

How the 'what', 'where', and 'when' of past experiences are stored in episodic memories and retrieved for suitable decisions remains unclear. In an effort to address these questions, the authors present computational models of neural networks that behave l ...

Nature Portfolio2023