Time memory trade off attack on symmetric ciphers

Abstract

Zaman Hafıza Üleşimi (ZHÜ), amacı başvuru tablosundan daha az hafıza kullanan ve tam kapsamlı aramadan daha az zaman harcayan saldırılar geliştirmek olan bir kriptanaliz yöntemidir. ZHÜ literatürde geniş ölçüde çalışılmış ve bir cok kriptosistemin kırılmasında kullanılmıştır. Bu çalışmada, simetrik şifrelerin tasarım ve analizleri üzerine odaklanılmıştır. Öncelikle, rastlantısal dönüşümlerin istatistiksel özellikleri göz önünde bulundurularak bu methodun uygulanmasında gerekli olan bazı parametrelerin beklenen değerleri daha önce verilen yöntemlerden daha basit bir yaklaşımla yeniden hesaplanarak listelenmiştir. Bilinen tekniklere bazı yeni yapılandırmalar önerilmiş ve rastlantısal dönüşümler üzerinde üç yeni belirleyici tanımlanmıştır. Daha sonra, atağın iki önemli iyileştirmesi olan gökkuşağı (Rainbow) yöntemi ve ayırt edilmiş nokta (Distinguished Point) yöntemlerinin başarı oranları ayrıntılı olarak analiz edilmiştir. Bu sonuçları kullanarak yüksek başarı elde edilebilmesi için parametrelerin nasıl seçilmesi gerektiği üzerinde tartışılmıştır. Yaptığımız teorik çalışmaları desteklemek için güncel şifre algoritmaları üzerinde deneysel sonuçlar sunulmuştur.

Time Memory Trade Off (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.