8
$\begingroup$

What is the best known attack on the stream cipher Trivium?

And is there is any good reason to not use it?

By googling the good key words, I've found this paper, but I'm not enough expert to judge the relevancy of this paper.

$\endgroup$
1
  • 3
    $\begingroup$ That's a side channel attack on a hardware implementation. I'm not sure if that applies for your use case or not. $\endgroup$
    – Maarten Bodewes
    Dec 13, 2022 at 11:07

2 Answers 2

12
$\begingroup$

There is no better than brute force attack in the open literature on the full version of Trivium which consists of 1152 "rounds" (iterations of the state machine after loading with the key and the IV).

If we consider the best known non-side channel attacks, there are some attacks out there on reduced round (weakened) versions of Trivium.

As of 2015, the best known attack on a reduced round version of Trivium was an attack of complexity $\sim 2^{ 62}$ which is an optimized cube attack on 799 rounds. See https://eprint.iacr.org/2015/312. This is a key recovery attack.

There is a more recent paper from 2022 claiming a key recovery attack also based on optimizing the cube attack with a complexity of $\sim 2^{53 }$ on 820 rounds. See https://eprint.iacr.org/2022/1518 for details.

$\endgroup$
1
  • 5
    $\begingroup$ (for OP) A "reduced round version" is a made-up, less secure version of the algorithm. Attacks against these are not attacks against the actual algorithm, but they can be used as stepping-stones for future attacks. $\endgroup$ Dec 13, 2022 at 19:10
11
$\begingroup$

I would say that Trivium is still secure, but the ASIC example given in the paper is not. The security of an ASIC implementation is only as good as the person who created the design for the ASIC. Generally, if you give me:

  • reset control
  • clock control
  • VDD control

I likely will be able to extract information from a single-rail, synchronous system. (note: A single-rail system is what you learn about in school. You have logic between two latches that are controlled by a clock.) You will find that most every attack for hardware uses these three items. One of the reason is that HDLs generally target single-rail, synchronous systems. In the paper, a VHDL generated layout for TSMC 90nm was used, and this is an easier case as the pFET device are much weaker on this this process compared to nFETs so you can easily create glitches. (FYI, this attack won't work on TSMC 7nm because the matching is too close due to the fully-depleted channels to create the glitches, so maybe you could get away with a secure single-rail implementation?)

In order to have ASICs that are robust to these sorts of attacks, you need to minimize access to the list above. When I do a SIMON implementation, I use dual-rail encoding (note: dual-rail encoding is where you pass the logic S and the compliment, !S. In this way, you can guarantee the integrity of the data, it also guarantees constant current draw, zeroth order ), so I pass around complimentary lines which means that you cannot do a power trace or glitch based on the clock because you get an XOR check that the logic is inverse of the other. This allows protection from glitches in a synchronous system. (There's something called RAZR from the University of Michigan that uses something similar and can show you the circuits.) Also, if I have a dual-rail implementation, I generally use asynchronous approaches which are clockless where you load the data into the register and then say "go" and you get an answer that is robust to clock and VDD changes.

edit: I looked for, and couldn't find, the HDL used to create the IC in the paper.

edit2: A paper that shows the effects of dual rail encoding, figure 15.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.