Cryptanalysis of Draco

Abstract

Draco is a lightweight stream cipher designed by Hamann et al. in IACR ToSC 2022. It has a Grain-like structure with two state registers of size 95 and 33 bits. In addition, the cipher uses a 128-bit secret key and a 96-bit IV. The first 32 bits of the key and the IV forms a non-volatile internal state that does not change during the time that the cipher produces keystream bits.
The authors claim that the cipher is provably secure against Time-Memory-Data (TMD) Tradeoff attacks. However in this paper, we first present two TMD tradeoff attacks against Draco. Both attacks leverage the fact that for certain judiciously chosen IVs the state update function of the cipher depend on only a small fraction of the non-volatile internal state. This makes the state update function in Draco essentially a one way function over a much smaller domain and range. The first attack requires around 2^114.2 Draco iterations and requires that the adversary has access to 2³² chosen IVs. The second attack is such that the attack parameters can be tuned as per the requirements of the attacker. If the attacker prioritizes that the number of different chosen IVs is limited to 2²⁰ say, then the attack can be done in around time proportional to 2¹²⁶ Draco rounds. However if the total attack complexity is to be optimized, then the attack can be performed in 2¹⁰⁷ time using around 2⁴⁰ chosen IVs.