Given an ideal I in a polynomial ring K[x1,…,xn] over a field K, we present a complete algorithm to compute the binomial part of I, i.e., the subideal Bin(I) of I generated by all monomials and binomials in I. This is achieved step-by-step. First we collect and extend several algorithms for computing exponent lattices in different kinds of fields. Then we generalize them to compute exponent lattices of units in 0-dimensional K-algebras, where we have to generalize the computation of the separable part of an algebra to non-perfect fields in characteristic p. Next we examine the computation of unit lattices in finitely generated K-algebras, as well as their associated characters and lattice ideals. This allows us to calculate Bin(I) when I is saturated with respect to the indeterminates by reducing the task to the 0-dimensional case. Finally, we treat the computation of Bin(I) for general ideals by computing their cellular decomposition and dealing with finitely many special ideals called (s,t)-binomial parts. All algorithms have been implemented in SageMath.

A prototype of the framework AutoFault, which automatically constructs fault-injection attacks for hardware realizations of ciphers, is presented. AutoFault can be used to quickly evaluate the resistance of security-critical hardware blocks to fault attacks and the adequacy of implemented countermeasures. The framework takes as inputs solely the circuit description of the cipher and the fault(s) and produces an algebraic formula that can be handed over to an external solver. In contrast to previous work, attacks constructed by AutoFault do not incorporate any cipher-specific cryptoanalytic derivations, making the framework accessible to users without cryptographic background. We report successful application of AutoFault in combination with a state-of-the-art SAT solver to LED-64 and to small-scale AES. To the best of our knowledge, this is the first time that a state-of-the-art cipher (LED-64) was broken by a fault attack with no prior manual cryptanalysis whatsoever.

Mobile and embedded systems increasingly process sensitive data, ranging from personal information including health records or financial transactions to parameters of technical systems such as car engines. Cryptographic circuits are employed to protect these data from unauthorized access and manipulation. Fault-based attacks are a relatively new threat to system integrity. They circumvent the protection by inducing faults into the hardware implementation of cryptographic functions, thus affecting encryption and/or decryption in a controlled way. By doing so, the attacker obtains supplementary information that she can utilize during cryptanalysis to derive protected data, such as secret keys. In the recent years, a large number of fault-based attacks and countermeasures to protect cryptographic circuits against them have been developed. However, isolated techniques for each individual attack are no longer sufficient, and a generic protective strategy is lacking.