A Cryptanalytic Time-Memory Tradeoff: First FPGA Implementation
(2002) Proceedings of FPL2002 — Location: Montpellier, France
Files
3.pdf
Open Access - Adobe PDF
- 497.88 KB
Details
- Authors
Legat, Jean-Didier 
- Abstract
- A cryptanalytic time-memory tradeoff allows the cryptanal- ysis of any N key symmetric cryptosystem in O(N^2/3 ) operations with O(N^2/3 ) storage, if a precomputation of O(N) operations has been done in advance. This procedure is well known but did not lead to any realistic implementations. In this paper, the experimental results for the crypt- analysis of DES (Data Encryption Standard) that are presented are based on a time-memory tradeoff using distinguished points, a method which is referenced to Rivest [2]. For this task, a fast hardware implementation of DES was designed using FPGA technology. The target is a 40-bit DES which is obtained from DES by fixing 16 key bits to arbitrary values. The precomputation task is performed with a purpose-built FPGA design, whereas the search al- gorithm corresponding to the online attack is reported to be feasible on any PC within about 10 seconds, with a success rate of 72%. The cost of an expansion to 56-bit DES is evaluated.
- Affiliations
Citations
Quisquater, J.-J., Standaert, F.-X., Rouvroy, G., David, J.-P., & Legat, J.-D. (2002). A Cryptanalytic Time-Memory Tradeoff: First FPGA Implementation. Proceedings of FPL2002, Montpellier, France.