MAYo or MAY-not: Exploring Implementation Security of the Post-Quantum Signature Scheme MAYO Against Physical Attacks

MAYO is a multivariate signature scheme notable for its efficiency and compact key size. Targeting NIST security level I, MAYO features a public key size of 1168 bytes and a signature size of 321 bytes, making it more compact than leading lattice-based signature schemes like Falcon and Dilithium, thereby easing integration into embedded systems. With the deployment of MAYO in embedded systems, studying the resilience of MAYO implementations against fault injection attacks is of increasing importance. In this paper, we investigate the security of MAYO against fault injection attacks, and present the first end-to-end fault injection attack on the multivariate scheme. The attack introduces a loop-abort fault in the sampling of the vinegar vector. We present two variants: A zero-ing attack, in which the skipped sampling results in an all-zero vinegar vector, and a differential fault attack. In both variants, the faulted signature reveals an oil vector, allowing for full key recovery through techniques borrowed from the reconciliation attack in a few seconds.