How to invert one-way functions: Time-memory trade-off method

Abstract

Birçok şifreleme yönteminin, kimlik doğrulama algoritmalarının ve kriptografikprotokollerin güvenliği tek yönlü fonksiyonların çevrilmesinin zorluğunadayanır. Hellman tarafından önerilen [11] zaman-hafıza ödünleşimi (TMTO) tekyönlü fonksiyonların çevrimi için genel bir metotdur. Bu tezde, TMTO metodununanalizi yapılmış ve metodun simetrik anahtarlı sistemler ve özetlemefonksiyonlarına uygulanması gösterilmiştir. Metodun başarı oranını hesaplamayayardımcı olan, bir Hellman tablosunun kapsama oranını veren yeni birasimptotik ifade tanıtılmıştır. Bir uygulama olarak TMTO metodu SHA-1özetleme algoritmasına uygulanmıştır.

Security of various encryption schemes, authentication mechanisms and othercryptographic protocols depend on the hardness of inverting one-way functionswhich they are based on. Time-Memory Trade-off (TMTO) method, proposedby Hellman [11], is a generic method to invert one-way functions, by enablinga trade-off to be made between the memory and the time required to find aninverse, at the expense of a precomputation effort. In this thesis, an analysis ofthe TMTO method is made and the application of the method to symmetric-keycryptosystems and hash functions is presented. A new asymptotic expression forthe coverage of a single Hellman table which helps to approximate the successprobability of the method is introduced. As an application, the method isapplied to SHA-1 hash algorithm and the results are presented.