Either based on voltage, LASER or electro-magnetic disturbances, fault attacks represent an ever growing threat to cryptographic implementations, all the more when multiple-fault scenarios are considered. The state-of-the-art of fault countermeasures is essentially divided into two paradigms: Detection-based and infection-based countermeasures. The simple concept of detection-based countermeasures has been proven efficient to counteract fault attacks and easily extendable to handle high-order fault models. On the other hand, the design of infective countermeasures is much more challenging since most proposals have been broken in a single-fault setting. In this paper we present a new infective countermeasure framework fit for any symmetric cryptosystem. This framework takes into account the fatal flaws of previous infective proposals. Our framework can be instantiated in various flavours depending on the context of use and the available software or hardware components. In addition, we describe how our framework can be set-up to handle high-order fault attacks. As far as we know, this is the first time an infective countermeasure proposes such a feature.

Scalar recoding is popular to speed up ECC scalar multiplication: non-adjacent form, double-base number system, multi-base number system. But fast recoding methods require pre-computations: multiples of base point or off-line conversion. In this paper, we present a multi-base recoding method for ECC scalar multiplication based on i) a greedy algorithm starting least significant terms first, ii) cheap divisibility tests by multi-base elements and iii) fast exact divisions by multi-base elements. Multi-base terms are obtained on-the-fly using a special recoding unit which operates in parallel to curve-level operations and at very high speed. This ensures that all recoding steps are performed fast enough to schedule the next curve-level operations without interruptions. The proposed method can be fully implemented in hardware without pre-computations. We report FPGA implementation details and very good performances compared to state-of-art results.