Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Attacks on the Firekite Cipher

Johansson, Thomas LU orcid ; Meier, Willi and Nguyen, Vu LU orcid (2022) In IACR Transactions on Symmetric Cryptology 2022(3). p.191-216
Abstract
Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security is conjectured to rely on the hardness of the 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 an estimate 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... (More)
Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security is conjectured to rely on the hardness of the 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 an estimate 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 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 266.75 and 2106.75 for Firekite’s parameters corresponding to 80-bit and 128-bit security, respectively. By applying the distinguishing attacks and an additional algorithm we describe, 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 instances of Firekite parameters and has slightly larger complexity, for instance, 269.87 on the 80-bit security parameters n = 16,384, m = 216, k = 216. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IACR Transactions on Symmetric Cryptology
volume
2022
issue
3
pages
191 - 216
publisher
Ruhr-Universität Bochum
external identifiers
  • scopus:85137734260
ISSN
2519-173X
DOI
10.46586/tosc.v2022.i3.191-216
language
Swedish
LU publication?
yes
id
bdfef477-19e1-4216-864e-5d35d019327c
date added to LUP
2022-10-11 11:54:43
date last changed
2024-01-18 10:59:58
@article{bdfef477-19e1-4216-864e-5d35d019327c,
  abstract     = {{Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security is conjectured to rely on the hardness of the 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 an estimate for the bit level security depending on the selected practical parameters.<br/>We propose distinguishing and key-recovery attacks on Firekite by exploiting the structural properties of its PRNG. We adopt several 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 266.75 and 2106.75 for Firekite’s parameters corresponding to 80-bit and 128-bit security, respectively. By applying the distinguishing attacks and an additional algorithm we describe, 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 instances of Firekite parameters and has slightly larger complexity, for instance, 269.87 on the 80-bit security parameters n = 16,384, m = 216, k = 216.}},
  author       = {{Johansson, Thomas and Meier, Willi and Nguyen, Vu}},
  issn         = {{2519-173X}},
  language     = {{swe}},
  number       = {{3}},
  pages        = {{191--216}},
  publisher    = {{Ruhr-Universität Bochum}},
  series       = {{IACR Transactions on Symmetric Cryptology}},
  title        = {{Attacks on the Firekite Cipher}},
  url          = {{http://dx.doi.org/10.46586/tosc.v2022.i3.191-216}},
  doi          = {{10.46586/tosc.v2022.i3.191-216}},
  volume       = {{2022}},
  year         = {{2022}},
}