Practical lattice reductions for CTF challenges

Last weekend, I gave an intermetiate to advanced training in cryptography to the current “cohort” for ICC team Europe, at the ENISA headquarters in Athens.¹ Since there was bound to be a mix of different experiences among the participants, I set out to be both educative as a (first) introduction to all sorts of lattice attacks, as well as having some practical nuggets of wisdom acquired from my own experiences playing CTFs, and maybe even to have some new concepts for the more advanced crypto players. The goal of the training was to mostly have practical applications of lattice reduction techniques in the context of CTF challenges, so the theory parts are at times more handwavy, and mostly there to provide more intuition about what’s going on under the hood. Nevertheless, if you do happen to come across some blatant mistake or omission I may have made, feedback is always welcome :)

In the spirit of openness and learning — some of the fundamental values CryptoHack and I wish to propagate in this space — and to avoid any potential unfair advantage should you come across challenges written by me in the future again, it seemed appropriate to make the materials for this presentation publicly available. Give them a read if you’re interested!^2,3

Of course, the only true test of your CTF skills are CTF challenges, so I’d like to once again extend my thanks to a community of wonderful people, skillful players and masterful challenge creators. I made a selection among some of the lattice-based or -inspired crypto challenges I could remember and find again, to again get a mix of difficulties, but without any particular order. That means that you’ll have to learn to recognize the correct techniques to apply and try to judge the difficulty by yourself. If you are one of the authors from whom I selected some of these challenges, or if you are one of the many other talented challenge creators out there,⁴ please know you and your work are very much appreciated, and a constant inspiration for when I myself write them! The files needed to attempt the challenges by yourself are gathered here, so you can avoid any potential spoilers from public writeups.