Attacking Code-Based Cryptosystems with Information Set Decoding Using Special-Purpose Hardware

Stefan Heyse, Ralf Zimmermann, Chris­tof 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 [7], Leon [8], Stern [15] and recently [9] (May et al.) and [2] (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[5], discuss its shortcomings and possible enhancements.

[DOI] [BibTeX] [pdf] [bib]