International Association for Cryptologic Research

International Association
for Cryptologic Research


Matthias Krause


The DRACO Stream Cipher: A Power-efficient Small-state Stream Cipher with Full Provable Security against TMDTO Attacks
Stream ciphers are vulnerable to generic time-memory-data tradeoff attacks. These attacks reduce the security level to half of the cipher’s internal state size. The conventional way to handle this vulnerability is to design the cipher with an internal state twice as large as the desired security level. In lightweight cryptography and heavily resource constrained devices, a large internal state size is a big drawback for the cipher. This design principle can be found in the eSTREAM portfolio members Grain and Trivium.Recently proposals have been made that reduce the internal state size. These ciphers distinguish between a volatile internal state and a non-volatile internal state. The volatile part would typically be updated during a state update while the non-volatile part remained constant. Cipher proposals like Sprout, Plantlet, Fruit and Atom reuse the secret key as non-volatile part of the cipher. However, when considering indistinguishability none of the ciphers mentioned above provides security beyond the birthday bound with regard to the volatile internal state. Partially this is due to the lack of a proper proof of security.We present a new stream cipher proposal called Draco which implements a construction scheme called CIVK. In contrast to the ciphers mentioned above, CIVK uses the initial value and a key prefix as its non-volatile state. Draco builds upon CIVK and uses a 128-bit key and a 96-bit initial value and requires 23 % less area and 31 % less power than Grain-128a at 10 MHz. Further, we present a proof that CIVK provides full security with regard to the volatile internal state length against distinguishing attacks. This makes Draco a suitable cipher choice for ultra-lightweight devices like RFID tags.
LIZARD - A Lightweight Stream Cipher for Power-constrained Devices
Matthias Hamann Matthias Krause Willi Meier
Time-memory-data (TMD) tradeoff attacks limit the security level of many classical stream ciphers (like E0, A5/1, Trivium, Grain) to 1/2n, where n denotes the inner state length of the underlying keystream generator. In this paper, we present Lizard, a lightweight stream cipher for power-constrained devices like passive RFID tags. Its hardware efficiency results from combining a Grain-like design with the FP(1)-mode, a recently suggested construction principle for the state initialization of stream ciphers, which offers provable 2/3n-security against TMD tradeoff attacks aiming at key recovery. Lizard uses 120-bit keys, 64-bit IVs and has an inner state length of 121 bit. It is supposed to provide 80-bit security against key recovery attacks. Lizard allows to generate up to 218 keystream bits per key/IV pair, which would be sufficient for many existing communication scenarios like Bluetooth, WLAN or HTTPS.