Improved Timing Attacks against the Secret Permutation in the McEliece PKC

International audienceIn this paper, we detail two side-channel attacks against the McEliece public-key cryptosys-tem. They exploit timing differences on the Patterson algorithm used for binary Goppa codes decoding in order to reveal one part of the secret key: the support permutation. The first one is improving two existing timing attacks and uses the correlation between two different steps of the decoding algorithm. This improvement can be deployed on all error-vectors with Hamming weight smaller than a quarter of the minimum distance of the code. The second attack targets the evaluation of the error locator polynomial and succeeds on several different decoding algorithms. We also give an appropriate countermeasure