ASASA-based Whitebox Cryptography
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. 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.
Whitebox through Circuit Obfuscation
Alex Biryukov, Aleksei Udovenko. Attacks and Countermeasures for White-box Designs, In 24th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018. Springer International Publishing.
Supporting code is available at github.com/cryptolu/whitebox.
We present multiple generic attacks against masked white-box implementations. We use the term “masking” in a very broad sense. As a result, we deduce new constraints that any secure white-box implementation must satisfy.
Based on the new constraints, we develop a general method for protecting white-box implementations. We split the protection into two independent components: value hiding and structure hiding. Value hiding must provide protection against passive DCA-style attacks that rely on analysis of computation traces. Structure hiding must provide protection against circuit analysis attacks. In this paper we focus on developing the value hiding component. It includes protection against the DCA attack by Bos et al. and protection against a new attack called algebraic attack.
We present a provably secure first-order protection against the new algebraic attack. The protection is based on small gadgets implementing secure masked XOR and AND operations. Furthermore, we give a proof of compositional security allowing to freely combine secure gadgets. We derive concrete security bounds for circuits built using our construction.
Whib0x 2017 Competition
We participated in the Whib0x/CHES CTF 2017 competition. Our ad-hoc implementation has won the competition with a significant advantage. It has survived 28 days of reverse-engineering and cryptanalysis, after which it was broken by the CryptoExperts team (Louis Goubin, Pascal Paillier, Matthieu Rivain and Junwei Wang. How to Reveal the Secrets of an Obscure White-Box Implementation).
We also were first to break the other top 4 competing designs in the competition.