Time memory trade off attack on symmetric ciphers

Download

index.pdf

Date

2009

Author

Saran, A. Nurdan

Metadata

Show full item record

Item Usage Stats

130
views

60
downloads

Time Memory Trade O (TMTO) is a cryptanalytic method that aims to develop an attack which has a lower memory complexity than lookup table and a lower online time complexity than exhaustive search. TMTO methods are widely studied in the literature and used for inverting various cryptosystems. We focus on the design and the analysis of TMTO on symmetric ciphers in this thesis. Firstly, the summary of the random mapping statistics from the view point of TMTO is presented. We also recalculate some expected values with a simpler approach than the existing proofs. Then, we propose some variant constructions and also present three new distinguishers based on random mappings. Next, we provide a detailed analysis of the success rate of two main improvements of the attack; Distinguished Point Method and Rainbow Method. Finally, we discuss the adjustment of the parameters to achieve a high success rate. To support our theoretical framework, we also present empirical results of our analysis to actual ciphers.

Subject Keywords

Cryptography., Mathematics., Random mappings.

URI

http://etd.lib.metu.edu.tr/upload/12610437/index.pdf
https://hdl.handle.net/11511/18486

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Frequent itemset minning with trie data structure and parallel execution with PVM Guner, Levent; Karagöz, Pınar (2007-10-03) Apriori algorithm is one of the basic algorithms introduced to solve the problem of frequent itemset mining (FIM). Since there is a new generation of affordable computers with parallel processing capability and it is easier to set up computer clusters, we can develop more efficient parallel FIM algorithms for these new systems. This paper investigates the use of trie data structure in parallel execution of Apriori algorithm, the potential problems during implementation, performance comparison of several par...
Mutual correlation of randomness test and analysis of test outputs of transformed and biased sequences Akcengiz, Ziya; Doğanaksoy, Ali; Department of Cryptography (2014) Randomness is one of the most important parts of the cryptography because key generation and key itself depend on random values. In literature, there exist statistical randomness tests and test suites to evaluate randomness of the cryptographic algorithm. Although there exist randomness tests, there is no mathematical evidence to prove that a sequence or a number is random. Therefore, it is vital to choose tests in the test suites due to independency and coverage of the tests used in the suites. Sensitivity...
WEIGHTED MATRIX ORDERING AND PARALLEL BANDED PRECONDITIONERS FOR ITERATIVE LINEAR SYSTEM SOLVERS Manguoğlu, Murat; Sameh, Ahmed H.; Grama, Ananth (Society for Industrial & Applied Mathematics (SIAM), 2010-01-01) The emergence of multicore architectures and highly scalable platforms motivates the development of novel algorithms and techniques that emphasize concurrency and are tolerant of deep memory hierarchies, as opposed to minimizing raw FLOP counts. While direct solvers are reliable, they are often slow and memory-intensive for large problems. Iterative solvers, on the other hand, are more efficient but, in the absence of robust preconditioners, lack reliability. While preconditioners based on incomplete factor...
Optimizing Parameters of Signal Temporal Logic Formulas with Local Search Aydin, Sertac Kagan; Aydın Göl, Ebru (2019-08-22) Signal temporal logic (STL) is a formal language for expressing temporal and real-time properties of real valued signals. In this paper, we study the problem of generating an STL formula from a labeled dataset. We propose a local search algorithm to synthesize parameters of a template formula. Starting from a random initial point, the parameter space is explored in the directions improving the formula evaluation. In addition, the local search method is integrated to the genetic algorithms developed for form...
FPGA implementation of graph cut method for real time stereo matching Sağlık Özsaraç, Havva; Ünver, Baki Zafer; Ulusoy, İlkay; Department of Electrical and Electronics Engineering (2010) The present graph cut methods cannot be used directly for real time stereo matching applications because of their recursive structure. Graph cut method is modified to change its recursive structure so that making it suitable for real time FPGA (Field Programmable Gate Array) implementation. The modified method is firstly tested by MATLAB on several data sets, and the results are compared with those of previous studies. Although the disparity results of the modified method are not better than other methods’,...

Citation Formats

A. N. Saran, “Time memory trade off attack on symmetric ciphers,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.