Statistical Model of the Statistical Saturation Attack

Abstract

The statistical saturation attack (SSA) introduced by Collard and Standaert focuses on the non-uniformity of certain bits in the ciphertext space by fixing certain bits in the plaintext space. It exploits this non-uniformity by distinguishing an observed distribution among two known distributions: one is uniform and the other is non-uniform. To do so, a statistical test, based on a statistical distinguisher is required. There exists such statistical distinguishers based on the links in between SSA and other statistical cryptanalytic techniques. Instead of using such links, in this thesis we look directly in SSA and develop a statistical distinguisher and propose a statistical test based on this distinguisher. The statistical distinguisher denoted by T is primarily chi-square distributed. Theoretical approximation of the distribution of T is derived in terms of the size and capacity of the distribution considering both of the cases of a single fixation and a set of fixations. The developed model is applied on SMALLPRESENT-[4] for the case of single fixation and the evolution of the distinguisher is observed both theoretically and experimentally as the number of encrypted plaintexts increases. In addition to this, a connection between the error probability of the statistical test and the number of required plaintexts (in other words data complexity) is also presented and showed that this theoretical data complexity is in close correspondence to the observed data complexity in the experiments on SMALLPRESENT-[4].