Hard fault analysis of Trivium

Fault analysis is an attack on stream ciphers with potential power. Up until now, major efforts on fault analysis have been to simplify the cipher by injecting some soft faults, that is, momentarily changing values of some register bits. We call this soft fault analysis. As a hardware-oriented stream cipher, Trivium is weak under soft fault analysis. In this paper we consider another type of fault analysis. It is to simplify the cipher by injecting some hard faults, that is, permanently setting values of some register bits to be zero. We call this hard fault analysis, and use it to analyze Trivium. We classify the faults positions into seven cases, and in five cases the cipher can be broken or be efficiently simplified. We present the following results about such attack on Trivium. In one case with the probability not smaller than 0.2396, the attacker can obtain 69 bits of the 80-bit key. In another case with the probability not smaller than 0.2292, the attacker can recover the full key. In the third case with the probability not smaller than 0.2292, the attacker can partially solve the key. In the fourth case with non-negligible probability, the attacker can obtain a simplified cipher, with smaller number of state bits and slower non-linearization procedure. In the fifth case with non-negligible probability, the attacker can obtain another simplified cipher. The attacker’s computations are simple and immediate, and the cipher can be broken or be efficiently simplified with the probability not smaller than 0.698. Besides, these five cases can be distinguished by observing the keystream.