Emin ANARIM, Orhun KARA, İmran ERGULER

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

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.

PDF

___

[1] Hellman ME. A cryptanalytic time-memory trade-off. IEEE T Inform Theory 1980; 4: 401-406.
[2] Babbage S. A space/time tradeoff in exhaustive search attacks on stream ciphers. In: Proceedings of European Convention on Security and Detection; 1618 May 1995; Brighton, England. London, England: IEE No:408. pp. 161- 166.
[3] Golic J. Cryptanalysis of alleged A5 stream cipher. In: Proceedings of the 16th Annual International Conference on Theory and Application of Cryptographic Techniques EUROCRYPT97; 1115 May 1997; Konstanz, Germany. New York, NY, USA: Springer-Verlag LNCS 1233. pp 239-255.
[4] Biryukov A, Shamir A. Cryptanalytic time/memory/data tradeoffs for stream ciphers. In: Proceedings of Advances in Cryptology ASIACRYPT 2000; 37 December 2000; Kyoto, Japan. New York, NY, USA: Springer-Verlag LNCS 1976. pp 1-13.
[5] Batina L, Lano J, Mentens N, Ors SB, Preneel B, Verbauwhede I. Energy, Performance, Area Versus Security Trade-offs for Stream Ciphers. In: Proceedings of the State of the Art of Stream Ciphers SASC-2004, ECRYPT Workshop Record. pp. 302310.
[6] Biryukov A, Shamir A, Wagner D. Real time cryptanalysis of A5/1 on a PC. In: Proceedings of the 7th International Workshop on Fast Software Encryption FSE 2000. New York, NY, USA: Springer-Verlag LNCS 1978. pp. 1-18.
[7] Hell M, Johansson T, Meier W. Grain: a stream cipher for constrained environments. International Journal Of Wireless And Mobile Computing 2007; 2: 86-93.
[8] Good T, Benaissa M. Hardware results for selected stream cipher candidates. In: Proceedings of the State of the Art of Stream Ciphers, ECRYPT Workshop Record SASC-2007; 31 January1 February 2007; Bochum, Germany. pp. 191-204.
[9] Bogdanov A, Knudsen LR, Leander G, Paar C, Poschmann A, Robshaw MJ, Seurin Y, Vikkelsoe C. PRESENT: an ultra-lightweight block cipher. In: Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems CHES07. New York, NY, USA: Springer-Verlag LNCS 4727. pp 450-466.
[10] De Canni`ere C, Dunkelman O, Kneˇzevi´c M. KATAN and KTANTAN A family of small and efficient hardwareoriented block ciphers. In: Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems CHES 2009. New York, NY, USA: Springer-Verlag LNCS 5747. pp 272-288.
[11] Knudsen LR, Leander G, Poschmann A, Robshaw MJB. PRINTcipher: a block cipher for IC-printing. In: Proceedings of International Conference on Cryptographic Hardware and Embedded Systems CHES 2010. New York, NY, USA: Springer-Verlag LNCS 6225. pp 16-32.
[12] McEliece RJ. A public key cryptosystem based on algebraic coding theory. DSN Progress Report 1978; 44: 114-116.
[13] Hopper NJ, Blum M. Secure human identification protocols. In: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology ASIACRYPT 2001. New York, NY, USA: Springer-Verlag LNCS 2248. pp 52-66.
[14] Aumasson JP, Finiasz M, Meier W, Vaudenay S. TCHo: a hardware-oriented trapdoor cipher. In: Proceedings of the 12th Australasian Conference on Information Security and Privacy ACISP07. New York, NY, USA: SpringerVerlag LNCS 4586. pp 184-199.
[15] Mihaljevic MJ, Imai H. An approach for stream ciphers design based on joint computing over random and secret data. Computing 2009; 85: 153-168.
[16] Mihaljevic MJ, Imai H. A stream cipher design based on embedding of random bits. In: Proceedings of International Symposium on Information Theory and its Applications ISITA2008; 710 December 2008, Auckland, New Zealand. pp. 1492-1502.
[17] Mihaljevic MJ, Imai H. A stream ciphering approach based on the wire-tap channel coding. In: Proceedings of 8th Central European Conference on Cryptography; 24 July 2008, Graz, Austria.
[18] Kara O, Erguler I. A new approach to keystream based cryptosystems. In: Proceedings of Information Security and Cryptology Conference ISCTurkey 2007; Ankara, Turkey. pp. 163-170.
[19] Kara O, Erguler I. A new approach to keystream based cryptosystems. In: Proceedings of the State of the Art of Stream Ciphers. ECRYPT Workshop Record SASC 2008; Lausanne, Switzerland. pp. 205-221.
[20] Kara O, Erguler I, Anarim E. A stream cipher model for hardware constraint environments. In: Proceedings of Extended Abstracts, International Conference on Applied and Computational Mathematics ICACM2012, Ankara, Turkey: METU.
[21] Trichina E, Bucci M, Seta DD, Luzzi R. Supplemental cryptographic hardware for smart cards. IEEE Micro 2001; 6: 26-35.
[22] Tavas V, Demirkol AS, Ozoguz S, Zeki A, Toker A. Integrated cross-coupled chaos oscillator applied to random ¨ number generation. IET Circuits, Devices & Systems 2009; 1: 1-11.
[23] Wu W, Zhang L. LBlock: a lightweight block cipher. In: Proceedings of Applied Cryptography and Network Security ACNS 2011. New York, NY, USA: Springer-Verlag LNCS 6715. pp 327-344.
[24] Shibutani K, Isobe T, Hiwatari H, Mitsuda A, Akishita T, Shirai T. Piccolo: an ultra-lightweight blockcipher. In: Proceedings of the 13th International Conference on Cryptographic Hardware and Embedded Systems CHES 2011. New York, NY, USA: Springer-Verlag LNCS 6917. pp 342-357.
[25] Guo J, Peyrin T, Poschmann A, Robshaw MJB. The LED block cipher. In: Proceedings of the 13th International Conference on Cryptographic Hardware and Embedded Systems CHES 2001. New York, NY, USA: SpringerVerlag LNCS 6917. pp 326-341.
[26] Satoh A, Morioka S, Takano K, Munetoh S. A compact Rijndael hardware architecture with S-box optimization. In: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology ASIACRYPT 2001. New York, NY, USA: Springer-Verlag LNCS 2248. pp 239-254.
[27] Good T, Chelton W, Benaissa M. Review of stream cipher candidates from a low resource hardware perspective. In: Proceedings of the State of the Art of Stream Ciphers, ECRYPT Workshop Record SASC 2006; 23 February 2006; Leuven, Belgium.
[28] Chien HY. SASI: A new ultralightweight RFID authentication protocol providing strong authentication and strong integrity. IEEE T Depend Secure 2007; 4: 337-340.
[29] Peris-Lopez P, Castro JCH, Est´evez-Tapiador JM, Ribagorda A. EMAP: an efficient mutual-authentication protocol for low-cost RFID tags. In: Proceedings of OTM Federated Conferences and Workshop; 29 October3 November 2006; Montpelier, France. IS Workshop. pp. 352-361.
[30] Peris-Lopez P, Castro JCH, Est´evez-Tapiador JM, Ribagorda A. M2 AP: A minimalist mutual-authentication protocol for low-cost RFID tags. In: Proceedings of International Conference on Ubiquitous Intelligence and Computing UIC06. New York, NY, USA: Springer-Verlag LNCS 4159. pp 912-923