A new security relation between information rate and state size of a keystream generator

Authors: ORHUN KARA, İMRAN ERGÜLER, EMİN ANARIM

Abstract: Wireless communication in near field applications is becoming widespread. Most of the devices such as sensor networks or RFID applications are operated in constraint environments and some of these prevalent technologies require security applications. As one conclusion, the design and analysis of lightweight cryptographic algorithms has been one of the favorite research subjects over the last decade. We have seen that mostly lightweight block ciphers have been designed as symmetric encryption algorithms. The main reason is that stream ciphers are supposed to have large internal states due to the strict requirement related to their resistance against tradeoff attacks (time--memory--data tradeoff (TMDT)). In this work, we introduce a new stream cipher encryption mode by making use of error correcting codes, constituting a new tradeoff between information rate of the employed code and the internal state size of the keystream generator. This tradeoff enables us to decrease the state size without sacrificing the security against TMDT attacks. The classical stream cipher encryption relies on deterministic keystream generation both at transmission and at receiver sides. On the other hand, we propose a noisy and nondeterministic keystream production, which we call the noisy keystream encryption (NKE). The receiver does not need the noise sequence to decrypt the ciphertext. However, it is a difficult problem for an attacker to recover the keystream sequence under the known plaintext scenario. We show that this gives a significant advantage in resisting attacks that require the keystream perfectly without any error. Particularly we prove that adding noise improves the security level in terms of internal state size against TMDT-type attacks.

Keywords: Encryption, error-correcting codes, stream cipher, TMDT time--memory--data tradeoff attacks, keystream, internal state size

Full Text: PDF