Cryptology ePrint Archive: Report 2015/516

Key-Recovery Attacks on ASASA

Brice Minaud and Patrick Derbez and Pierre-Alain Fouque and Pierre Karpman

Abstract: The ASASA construction is a new design scheme introduced at ASIACRYPT 2014 by Biruykov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However one of the two public-key cryptosystems was recently broken at CRYPTO 2015 by Gilbert, Plût and Treger. As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexity 2^63 and 2^39 respectively (the security parameter is 128 bits in both cases). Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to an LPN instance with tractable parameters. This allows key recovery in time complexity 2^56. Finally, as a side result, we outline a very efficient heuristic attack on the white-box scheme, which breaks instances claiming 64 bits of security under one minute on a desktop computer.

Category / Keywords: public-key cryptography / ASASA, Algebraic Cryptanalysis, Multivariate Cryptography, LPN

Date: received 29 May 2015

Contact author: brice minaud at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150529:075534 (All versions of this report)

Short URL: ia.cr/2015/516

Discussion forum: Show discussion | Start new discussion