CHES 2018 Side Channel Contest CTF - Solution of the AES Challenges.

We propose two heuristic polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group G. The first one is a direct adaptation of the Becker-Coron-Joux (BCJ) algorithm for subset sum to the discrete logarithm setting. The second one significantly improves on this adaptation for all possible weights using a more involved application of the representation technique together with some new Markov chain analysis. In contrast to other low weight discrete logarithm algorithms, our second algorithm’s time complexity interpolates to Pollard’s \(|G|^{\frac{1}{2}}\) bound for general discrete logarithm instances.