Cryptology ePrint Archive: Report 2021/319

Tradeoff attacks on symmetric ciphers

Orhun Kara

Abstract: Tradeoff attacks on symmetric ciphers can be considered as the generalization of the exhaustive search. Their main objective is reducing the time complexity by exploiting the memory after preparing very large tables at a cost of exhaustively searching all the space during the precomputation phase. It is possible to utilize data (plaintext/ciphertext pairs) in some cases like the internal state recovery attacks for stream ciphers to speed up further both online and offline phases. However, how to take advantage of data in a tradeoff attack against block ciphers for single key recovery cases is still unknown. We briefly assess the state of art of tradeoff attacks on symmetric ciphers, introduce some open problems and discuss the security criterion on state sizes. We discuss the strict lower bound for the internal state size of keystream generators and propose more practical and fair bound along with our reasoning. The adoption of our new criterion can break a fresh ground in boosting the security analysis of small keystream generators and in designing ultra-lightweight stream ciphers with short internal states for their usage in specially low source devices such as IoT devices, wireless sensors or RFID tags.

Category / Keywords: secret-key cryptography / symmetric cipher, block cipher, stream cipher, tradeoff attack, keystream, keystream generator, Hellman table, rainbow table, one-way function, preimage

Original Publication (in the same form): Book chapter in Riccardo Bernardini editor: "Cryptography-Recent Advances and Future Developments", Intechopen

Date: received 10 Mar 2021

Contact author: orhunkara at iyte edu tr

Available format(s): PDF | BibTeX Citation

Version: 20210311:184417 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]