A Little LESS Secure - Side-Channel Attacks Exploiting Randomness Leakage

Schnorr and (EC)DSA signatures famously become completely insecure once a few bits of the random nonce are revealed to an attacker. In this work, we explore whether the Fiat-Shamir based post-quantum signature scheme LESS is vulnerable to analogous attacks. In particular, we investigate the impact of partial leakage of the commitment randomness – a scenario that falls under the broader class of Hidden Number Problems – on the security of the secret key. We present an efficient attack on LESS that requires knowledge of a single bit of the randomness with less than 1200 signatures to fully recover the secret key. Our attack leverages the observation that knowledge of one bit is sufficient to distinguish secret key entries from random candidates. In addition, we describe a variant of this attack that requires one-bit leakage of multiple randomness values, but succeeds with only two signatures. To demonstrate the practicality of our attacks, we identify and exploit two different side-channels that are present in the reference implementation: One timing-based attack and one exploiting the power side-channel leakage. Both show that the assumptions regarding the required single-bit leakage can be obtained in practice and that our attack poses a realistic threat to the current implementation of LESS. To our knowledge, these are the first practically verified side-channel attacks on LESS.