Message Extension Attack against Authenticated Encryptions: Application to PANDA


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.1   pp.49-57
Publication Date: 2016/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.49
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
message extension attack,  internal state recovery,  existential forgery,  nonce misuse,  CAESAR,  PANDA,  

Full Text: PDF(1.1MB)
>>Buy this Article

We present a new cryptanalysis approach to analyze the security of a class of authenticated encryption schemes, which shares similarity with the previous length extension attack against hash-function-based MACs. Hence we name our approach by message extension attack. For an authenticated encryption from the target class, it consists of three phases; initialization with nonce and key as input, state update function with associated data and message as input and tag generation with updated state as input. We will show how to mount a forgery attack in the nonce-repeating model under the chosen-plaintext scenario, when both state update function and tag generation is built based on the same function. To demonstrate the effectiveness of our message extension attack approach, we apply it to a dedicated authenticated encryption called PANDA, which is a candidate of the ongoing CAESAR cryptographic competition. We successfully found an existential forgery attack on PANDA with 25 chosen plaintexts, 264 computations, and a negligible memory, and it breaks the claimed 128-bit security for the nonce-repeating model. We note that this is the first result that breaks the security claim of PANDA, which makes it withdrawn from the CAESAR competition by its designer.