## CryptoDB

### Matthias Krause

#### Publications

Year
Venue
Title
2017
TOSC
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.
2015
EPRINT
2015
EPRINT
2011
ASIACRYPT
2006
FSE
2003
CRYPTO
2002
EUROCRYPT
2001
EPRINT
Many of the keystream generators which are used in practice are LFSR-based in the sense that they produce the keystream according to a rule $y=C(L(x))$, where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel linear feedback shift registers (LFSRs), and $C$ denotes some nonlinear compression function. We present an $n^{O(1)} 2^{(1-\alpha)/(1+\alpha)n}$ time bounded attack, the FBDD-attack, against LFSR-based generators, which computes the secret initial state $x\in\booln$ from $cn$ consecutive keystream bits, where $\alpha$ denotes the rate of information, which $C$ reveals about the internal bitstream, and $c$ denotes some small constant. The algorithm uses Free Binary Decision Diagrams (FBDDs), a data structure for minimizing and manipulating Boolean functions. The FBDD-attack yields better bounds on the effective key length for several keystream generators of practical use, so a $0.656n$ bound for the self-shrinking generator, a $0.6403 n$ bound for the A5/1 generator, used in the GSM standard, a $0.6n$ bound for the $E_0$ encryption standard in the one level mode, and a $0.8823n$ bound for the two-level $E_0$ generator used in the Bluetooth wireless LAN system.