Paper 2022/148

Attacks on the Firekite cipher

Thomas Johansson, Willi Meier, and Vu Nguyen

Abstract

Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security relies on the hardness of the \textit{Learning Parity with Noise} (LPN) problem. It is one of a few LPN-based symmetric encryption schemes and it can be very efficiently implemented on a low-end SoC FPGA. The designers, Bogos, Korolija, Locher, and Vaudenay, demonstrated appealing properties of Firekite such as requiring only one source of cryptographically strong bits, small key size, high attainable throughput, and a concrete measurement for the bit level security depending on the selected practical parameters. We propose distinguishing and key-recovery attacks on Firekite by exploiting the structural properties of its PRNG. We adopt several \textit{birthday-paradox} techniques to show that a particular sum of Firekite's output has a low Hamming weight with higher probability than the random case. We achieve the best distinguishing attacks with complexities $2^{66.75}$ and $2^{106.75}$ for Firekite's parameters corresponding to $80$-bit and $128$-bit security, respectively. By applying the distinguishing attacks and an additionally suggested algorithm, one can also recover the secret matrix used in the Firekite PRNG, which is built from the secret key bits. This key recovery attack works on most large parameter sets and has slightly larger complexity, for example $2^{69.87}$ on the $80$-bit security parameters $n=16384, m = 216, k = 216$.

Note: - Fix references list. -Page 20, line 1, "a non-repeating" -> "no non-repeating".

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
PRNGFirekite PRNGBirthday paradoxk-list algorithmLPNLPN-based symmetric encryption
Contact author(s)
thomas johansson @ eit lth se
vu nguyen @ eit lth se
willi meier @ fhnw ch
History
2022-02-15: revised
2022-02-12: received
See all versions
Short URL
https://ia.cr/2022/148
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/148,
      author = {Thomas Johansson and Willi Meier and Vu Nguyen},
      title = {Attacks on the Firekite cipher},
      howpublished = {Cryptology ePrint Archive, Paper 2022/148},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/148}},
      url = {https://eprint.iacr.org/2022/148}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.