Projektowanie ataku z kompromisem czasu i pamięci na przykładzie szyfru A5/1

• Autorzy: Kanciak K. , Misztal M.

Warianty tytułu

EN

Time memory trade off attack on symmetric ciphers optimization

• Języki publikacji: PL

Abstrakty

PL

W artykule przeanalizowano różne warianty ataku brutalnego z fazą obliczeń wstępnych (lub inaczej ataku kompromisu czasu-pamięci) na przykładzie algorytmu strumieniowego A5/1. Omówiono również teoretyczną skuteczność różnych wariantów ataku, przedstawiono wyniki optymalizacji parametrów ataku, sformułowano wnioski dotyczące projektowania ataku kompromisu czasu-pamięci. Przedstawione zostały także otrzymane wyniki kryptoanalizy algorytmu A5/1 w zestawieniu z oczekiwanymi wartościami teoretycznymi.

EN

The paper discusses variants of time memory tradeoff attack. The article uses A5/1 stream cipher as an example. The article describes known variants of the attack with their theoretical effectiveness. Results of tradeoff parameters optimization are presented. The article covers conclusions on tradeoffs design and comparison of obtained A5/1 algorithm cryptanalysis results with expected theoretical values.

Słowa kluczowe

PL

kryptologia; kryptoanaliza; szyfr strumieniowy; atak z fazą obliczeń wstępnych; kompromis czasu-pamięci

EN

cryptology; cryptanalysis; stream cipher; TMTO; time-memory tradeoff

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Biuletyn Wojskowej Akademii Technicznej
• Rocznik: 2013
• Tom: Vol. 62, nr 4
• Strony: 77--94
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Kanciak K.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Matematyki i Kryptologii, 01-980 Warszawa, ul. gen. S. Kaliskiego 2

autor

Misztal M.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Matematyki i Kryptologii, 01-980 Warszawa, ul. gen. S. Kaliskiego 2

Bibliografia

• [1] M. Hellman, A Cryptanalytic Time-Memory Tradeoff, IEEE Transactions on Information Theory, 26, 1980.
• [2] P. Oechslin, Making a Faster Cryptanalytic Time-Memory Trade-Off, Advances in Cryptology, Springer-Verlag, 2003.
• [3] S. Babbage, A Space/Time Tradeoff in Exhaustive Search Attacks on Stream Ciphers; European Convention on Security and Detection, IEE Conference Publication 408, 1995.
• [4] J. Borst, B. Preneel, J. Vandewalle, On the Time-Memory Tradeoff between ex-haustive key search and table precomputation, Proc. of the 19th Symposium in Information Theory in the Benelux, WIC, 1998, 111-118.4.
• [5] D.E. Denning, Cryptography and Data Security, 100, Addison-Wesley, 1982.
• [6] J. Borst, B. Preneel, J. Vandewalle, A Time-Memory Tradeoffs using Distinguished Points, Technical report ESAT-COSIC Report 98-1, 1998.
• [7] K. Nohl, C. Paget, GSM – SRSLY?, 26th Chaos Communication Congress (26C3) Berlin, 2009.
• [8] J. Hongy, K. Chul Jeongz, E. Young Kwony, Variants of the Distinguished Point Method for Cryptanalytic Time Memory Trade-offs, Cryptology ePrint Archive, Report 054, 2008.
• [9] E. Barkan, E. Biham, A. Shamir, Rigorous Bounds on Cryptanalytic Time-Memory Tradeoffs, Advances in Cryptology, Proceedings of Crypto 2006, Springer-Verlag, 2006.
• [10] G. Avoine, P. Junod, P. Oechslinl, Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables, ACM Transactions on Information and System Security (TISSEC), 11, 4, July 2008, Article 17.
• [11] K. Kusuda, T. Matsumoto, Optimization of Time-Memory Trade-Off Cryptanalysis and Its Application to DES, FEAL-32, and Skipjack, IEICE Transactions on Fundamentals, E79-A(1), 1996, 35-48.
• [12] Kim T. Matsumoto, Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size, IEICE Transactions on Communications/Electronics/Information and Systems, 1999.
• [13] A. Biryukov, Some Thoughts on Time-Memory-Data Tradeoff, IACR ePrint Report 207, 2005.
• [14] A. Fiat, M. Naor, Rigorous Time-Space Tradeoffs for Inverting Functions, SIAM J. Computing, 29(3), 1999, 790-803.
• [15] A. Biryukov, A. Shamir, D. Wagner, Real Time Cryptanalysis of A5/1 on a PC, Proceedings of Fast Software Encryption 2000.