Revisiting the Security of the ALRED Design and Two of Its Variants: Marvin and LetterSoup

The Alred construction is a lightweight strategy for constructing message authentication algorithms from an underlying iterated block cipher. Even though this construction´s original analyses show that it is secure against some attacks, the absence of formal security proofs in a strong security model still brings uncertainty on its robustness. In this paper, aiming to give a better understanding of the security level provided by different authentication algorithms based on this design strategy, we formally analyze two Alred variants—the Marvin message authentication code and the LetterSoup authenticated-encryption scheme,—bounding their security as a function of the attacker´s resources and of the underlying cipher´s characteristics.