Trace-based schedulability analysis to enhance passive side-channel attack resilience of embedded software

• Published in: Information processing letters 2015-02, Vol.115 (2), p.292-297
• Main Authors: Agosta, Giovanni, Barenghi, Alessandro, Pelosi, Gerardo, Scandale, Michele
• Format: Article
• Language: English
• Subjects: Algorithms; Blocking; Channels; Compilers; Countermeasures; Cryptography; Embedded computer systems; Embedded systems; Embedded systems security; ISO standards; Military technology; Schedules; Scheduling algorithms; Side-channel attacks; Software; Studies; Trace theory
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2014.09.030

•Formalization of the reschedulability based countermeasure against side channel attacks through Foata Normal Form.•Definition of a flexible scheduling algorithm able to achieve higher instruction mobility.•Definition of an efficiently computable lower bound for the number of schedules obtainable and a flexible rescheduling strategy.•Practical implementation of the technique and validation on all the ISO standard block ciphers. Side channel attacks (SCAs) are a practical threat to the security of cryptographic implementations. A well known countermeasure against them is to alter the temporal location of instructions among different executions of the code. In this work we provide an algorithm to generate valid schedules of block cipher implementations. The proposed algorithm relies on a trace-theory based analysis and efficiently generates any valid schedule of the implementation under exam, selecting the ones with higher diversity among them. The algorithm was implemented as a pass in the backend of the LLVM compiler suite, and the results of the automated instruction scheduling are provided to validate its effectiveness as an SCA countermeasure employing the whole ISO standard block cipher suite.