A Practical Universal Forgery Attack against PAES-8

Abstract. PAES is an authenticated encryption scheme designed by Ye et al., and submitted to the CAESAR competition. The designers claim that PAES-8, which is one of the designs of the PAES-family, provides 128-bit security in the nonce misuse model. In this note, we show our forgery attack against PAES-8. Our attack works in the nonce misuse model. The attack exploits the slow propagation of message differences. The attack is very close to the universal forgery attack. As long as the target message is not too short, e.g. more than 10 blocks (160 bytes), a tag is forged only with 211 encryption oracle calls, 211 computational cost, and negligible memory