BRUTUS: Identifying Cryptanalytic Weaknesses in CAESAR First Round Candidates

Abstract. This report summarizes our results from security analysis covering all 57 CAESAR first round candidates and over 210 implementa-tions. We have manually identified security issues with three candidates, two of which are more serious, and these ciphers been withdrawn from the competition. We have developed a testing framework, BRUTUS, to facilitate automatic detection of simple security lapses and susceptible statistical structures across all ciphers. From this testing we have security usage notes on four submissions and statistical notes on a further four. We highlight that some of the CAESAR algorithms pose an elevated risk if employed in real-life protocols due to a class of adaptive chosen plain-text attacks. Although AEADs are often defined (and are best used) as discrete primitives that authenticate and transmit only complete mes-sages, in practice these algorithms are easily implemented in a fashion that outputs observable ciphertext data when the algorithm has not re-ceived all of the (attacker-controlled) plaintext. For an implementor, this strategy appears to offer seemingly harmless and compliant storage and latency advantages. If the algorithm uses the same state for secret keying information, encryption, and integrity protection, and the internal mix-ing permutation is not cryptographically strong, an attacker can exploit the ciphertext-plaintext feedback loop to to reveal secret state informa-tion or even keying material. We conclude that the main advantages of exhaustive, automated cryptanalysis is that it acts as a very necessary sanity check for implementations and gives the cryptanalyst insights that can be used to focus more specific attack methods on given candidates