Randomized Arithmetics – ARRAND

The leaks of informations appearing during the execution of an application represent the biggest weakness for a cryptographic tool. Side channel attacks or faults attacks exploit them to recover some secrets. As sophisticated as the mathematical model could be for proving the robustness, unprotected implementation could leak out some fundamental clues for an attacker. Among the most efficient attacks, we find those establishing correlations between consumption, electromagnetic radiation , etc, recorded during successive runs with the same secret. These leaks are informative mainly due to the variations from value "one" to "zero" of the memory points during the calculation. The commonly accepted model is based on the differences of Hamming weight between the successive execution states. An attacker can make a guess on the secret; with respect to the input values, then he/she can determine what could be the state transition, and he/she ranks the observed leakages into two sets: in the first one, he/she puts the ones which should give a low level transition, and the others in the second set. If his assumption about the secret is correct, then a peak should appear when we evaluate the difference between the curves of the two sets, else he/she gets a uniform noise which would be not exploitable.

The state transitions depend clearly of the data representations. Thus the validity of such attacks are based on the assumption made by the attacker about the data representation. Our goal is to select an arithmetic system such that all the computations involved in the execution use different representations from one execution to another, avoiding by this way any prediction about the state transitions by an attacker. The Hamming Distance (number of different bits) between two consecutive states can be detected in the consumption or in any other kind of leaks. Thus the knowledge of the representation of the variables can help an attacker who wants to make predictions. Hence, we propose to avoid the use of the same representation between two executions, we want to randomize the choice of the arithmetic, making unpredictable the data representation and the state transitions.

In this proposal, we suggest to work directly at the number systems levels. We propose to deal with two approaches that are of interest for the cryptographic implementations relative to finite fields: the Residue Number Systems(RNS) and the Modular Arithmetic Adapted Bases (MAAB). Residue Number Systems are related to the Chinese Remainder Theorem, each value is coded by its residues over a set of co-prime numbers named the base of the system. The main idea of the Modular Arithmetic Adapted Bases is to consider large radices with a set of small digits taking into account the modulo which characterizes the field or the ring.

For the two number systems RNS or MAAB, we must study the effect of the random selection of the bases on the representations. We need to obtain random sequences of representations to assume that it will be difficult to establish a correlation between successive executions with the same inputs. It is not easy to ensure this property, we will probably be obliged to determine subsets of bases for which this property holds. One of our goals is to obtain, at this level, some fundamental results about these explicit random sequences, which will be described with the help of extractors. Another point concerns the execution traces of the algorithms used, which needs also to produce independent execution logs.

Our study can be considered as primary, based on theoretical results and numerical simulations, and must be pursued in the future with industrial collaborations to enter into an experimental validation process. Our ambition is to propose to the industry an inner generic protection
against side channel and fault attacks.