Two weeks ago, at the 24th Annual Conference on Selected Areas in Cryptography (SAC 2017) in Ottawa, University of Waterloo master’s student Bailey Kacsmar presented research conducted in collaboration with Brandon University Professor Sarah Plosker and CSI’s own Professor Ryan Henry. The Conference on Selected Areas in Cryptography is an international gathering of researchers specializing in cryptographic system design and analysis that has been held annually in various locations across Canada since 1994. (At the same time Bailey was presenting on Ottawa, CSI Professor Xiaofeng Wang was on Canada’s west coast attending the 26th USENIX Security Symposium, where his collaborators presented two papers SmartAuth: User-Centered Authorization for the Internet of Things and Picking Up My Tab: Understanding and Mitigating Synchronized Token Lifting and Spending in Mobile Payment , but that’s a topic for a different blog post!
The new paper, titled Computing Low-Weight Discrete Logarithms, considers two “low-weight” variants of the ubiquitous Discrete Logarithm Problem (DLP) and presents a handful of new algorithms that build on the classical “baby-step giant-step” approach to solve these DLP variants. The DLP is perhaps the most widely used mathematical assumption in public-key cryptography, both in academic papers and in practice: every time you navigate to an HTTPS-enabled website, your web browser and the remote webserver carry out a special handshake in order to establish a secure connection, and the security of this handshake almost always depends on the difficulty of solving the DLP. The DLP variants that the new paper considers were proposed as a lightweight alternative to the more traditional DLP employed by your web browser, thus enabling resource-constrained devices like smartcards, sensor networks, and Internet of Things devices to leverage public-key cryptography. The new algorithms all but put this idea to rest, demonstrating the insecurity of an entire family of password-authenticated key exchange and human-identification protocols and highlighting the inherent riskiness of the low-weight DLP approach.
Next week, Professor Henry will travel to Svolvær-Lofoten, Norway to attend the workshop on Mathematical Methods for Cryptography, where he will admire the Aurora Borealis present a tutorial on the new algorithmic techniques to an international audience of distinguished cryptographers.
Going forward, Professor Henry will lead a team consisting of Bailey and CSI graduate students Swami Ramesh, Omkar Bhide, and Andrew Holland in studying whether adaptations of these algorithmic techniques can lead to better attacks against lightweight variants of post-quantum cryptographic constructions based on lattice problems. Such lightweight lattice constructions are being widely considered as a way to provide long-term security guarantees for the Internet of Things.
