Cryptanalysis

The evaluation deals with attempting to attack K2 in several different ways corresponding to the state-of-the art in the modern cryptanalysis of stream ciphers. This report includes analysis with respect to linear attacks, algebraic attacks, correlation and fast correlation attacks, differential attacks including the related-key setting, guess-and-determine attacks, statistical properties, period considerations as well as distinguishing attacks.

1. Linear Attacks
Designed using a combination of a linear and a non-linear part. The output of the non-linear part is masked by the linear part. In this way the correlation between subsequent outputs of the non-linear part is removed.
The attack involves mainly 2 steps:
i. A linear approximation of the non-linear part is found. It relates bits of the output keystream for one clock to some bits of the internal state.
ii. A linear combination of the outputs of the linear part at several clocks is found
with the property that the outputs cancel out.

Finally, the approximation of the non-linear part is expressed for the same clocks for which the outputs of the linear part cancel. The result is a linear combination of some bits of the output keystream for several clocks, that has some bias.

Major components of K-Cipher include FSR-A, FSR-B, DFC and NLF.
First, linear approximations for FSR-A and FSR-B in which their outputs cancel is identified. Next, a linear approximation of the NLF is evaluated and estimate bias. Finally, the complexity of an attack that would use those relations.

Complexity Estimation
Since the linear approximation with maximum correlation of the AES S-box is 2^(-3), we deduce that the correlation for one clock of the NLF is (2^(-3))^4 = 2^(-12). As per 13 linear approximations, the estimation for its it’s correlation to be c = (2^-12)^13 = 2^(-156). Its bias is ϵ = | c^2| = 2^(-157). Therefore N ≈ ϵ^-2 = 2^314 words of the key stream are required in order to distinguish the output sequence of K2 from random.