Time memory trade off attack on symmetric ciphers

Saran, A. Nurdan
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.


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...
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...
Joint linear complexity of multisequences consisting of linear recurring sequences
Fu, Fang-Wei; Niederreiter, Harald; Özbudak, Ferruh (Springer Science and Business Media LLC, 2009-04-01)
The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. In this paper, we study the joint linear complexity of multisequences consisting of linear recurring sequences. The expectation and variance of the joint linear complexity of random multisequences consisting of linear recurring sequences are determined. These results extend the ...
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...
Conditional Random Fields for Land Use/Land Cover Classification and Complex Region Detection
Can, Gulcan; Firat, Orhan; Yarman Vural, Fatoş Tunay (2012-11-09)
Developing a complex region detection algorithm that is aware of its contextual relations with several classes necessitates statistical frameworks that can encode contextual relations rather than simple rule-based applications or heuristics. In this study, we present a conditional random field (CRF) model that is generated over the results of a robust local discriminative classifier in order to reveal contextual relations of complex objects and land use/land cover (LULC) classes. The proposed CRF model enco...
Citation Formats
A. N. Saran, “Time memory trade off attack on symmetric ciphers,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.