Indepth Analysis of a Side-Channel Message Recovery Attack Against FrodoKEM

FrodoKEM is a post-quantum Key Encapsulation Mechanism (KEM) selected by the Bundesamt für der Sicherheit in der Informationstechnik (BSI) and the Agence Nationale de la Sécurité des Systémes d’Information (ANSSI). Although its theoretical security is still intact to this day, the FrodoKEM sensitive message can be recovered through other means, such as Side-Channel Analysis (SCA). In this work, we expand on a previous attack by Ravi et al. by detailling its effect on the different security levels of FrodoKEM. We study several strategies to recover its message in a minimal number of chosen ciphertexts queries.