Attacking Code-Based Cryptosystems with Information Set Decoding Using Special-Purpose Hardware
Stefan Heyse, Ralf Zimmermann, Christof Paar
Post-Quantum Cryptography - 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014
In this work, we describe the first implementation of an information set decoding (ISD) attack against code-based cryptosystems like McEliece or Niederreiter using special-purpose hardware. We show that in contrast to other ISD attacks due to Lee and Brickel , Leon , Stern  and recently  (May et al.) and  (Becket et al.), reconfigurable hardware requires a different implementation and optimization approach: Proposed time-memory trade-off techniques are not possible in the desired parameter sets. We thus derive new parameter sets from all steps involved in the ISD attack, taking a near cycle-accurate runtime estimation as well as the communication overhead into account.
Finally, we present the implementation of a hardware/software co-design – based on the Stern’s attack –, evaluate it against the challenges from the Wild-McEliece website, discuss its shortcomings and possible enhancements.[DOI] [BibTeX] [pdf] [bib]