Alex Biryukov, Dmitry Khovratovich, Charles Bouillaguet, Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key, In 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014. Springer International Publishing.
We design several encryption schemes based on the ASASA structure ranging from fast and generic symmetric ciphers to compact public key and white-box constructions based on generic affine transformations combined with specially designed low degree non-linear layers. We describe four instances of the ASASA scheme:
- Black-box ASASA cipher based on random secret S-boxes. Claimed security level: 120 bits.
- White-box ASASA and ASASASA ciphers based on black-box ciphers with small blocks (so just a few S-boxes). Claimed security level: 64 bits for ASASA, 128 bits for ASASASA.
- Public-key ASASA scheme based on random expanding S-boxes with perturbations. Claimed security level: 128 bits.
- Public-key ASASA scheme based on the chi-boxes with perturbations. Claimed security level: 128 bits.
- "Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-boxes", Henri Gilbert and Jérôme Plût and Joana Treger, to appear at CRYPTO 2015. The authors showed an attack on the public-key ASASA with expanding S-boxes with complexity 2^41.
- Decomposing the ASASA Block Cipher Construction, Itai Dinur and Orr Dunkelman and Thorsten Kranz and Gregor Leander. The authors showed that the white-box ASASA instance with n-bit block can be decomposed at the cost of about 2^(3n/2).
- Key-Recovery Attacks on ASASA, Brice Minaud and Patrick Derbez and Pierre-Alain Fouque and Pierre Karpman. The authors demonstrated an attack of complexity 2^(n/2) on the black-box ASASA cipher with n-bit block. They also attack the chi-instance with complexity 2^57. Finally, they describe a practical attack on some white-box instances with claimed 64-bit security level.
Status of ASASA after cryptanalysis
All the ASASA schemes were found weak with security level halved compared to the original claims. The ASASASA white-box scheme remains unbroken.