[en] In the area of white-box cryptography implementations, many existing protections are susceptible to attacks derived from physical cryptanalysis, which can be applied with minimal human effort and no prior design knowledge. The absence of a clear and comprehensive security model hinders the development of effective countermeasures against these attacks.
We introduce the Haystack ciphers, a formal model for the security of white-box countermeasures against such attacks. In this model, the countermeasures are represented simply as symmetric-key encryption schemes. We show that their chosen-plaintext (IND-CPA) security is closely related to the resistance of the countermeasures against computational trace-based attacks. Similarly, their chosen-ciphertext (IND-CCA) security is closely associated with the resistance against fault injection attacks in the white-box model. Secure Haystack ciphers constitute the next formal milestone for advancing white-box designs and countermeasures, the minimal requirement that is not currently clearly achieved but is plausibly feasible with available tools.
We review the white-box literature with respect to our model and bridge the gap between white-box and fault attacks, which are very powerful but were only partially considered in the white-box literature so far. We study known fault protections from the physical cryptography literature and present new fault attacks in the white-box setting, which raises the need and shapes the requirements for future secure countermeasures against fault attacks.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > CryptoLUX – Cryptography
Disciplines :
Computer science
Author, co-author :
CHARLÈS, Alex ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
UDOVENKO, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux
External co-authors :
no
Language :
English
Title :
Haystack Ciphers: White-Box Countermeasures as Symmetric Encryption
Publication date :
08 December 2025
Event name :
Asiacrypt 2025
Event organizer :
International Association for Cryptologic Research
Event place :
Melbourne, Australia
Event date :
8 - 12 December 2025
Audience :
International
Main work title :
Advances in Cryptology – ASIACRYPT 2025
Main work alternative title :
[en] 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8–12, 2025, Proceedings, Part II
Alpirez Bock E Treff A Bertoni GM Regazzoni F Security assessment of white-box design submissions of the CHES 2017 CTF challenge Constructive Side-Channel Analysis and Secure Design 2021 Cham Springer 123 146 10.1007/978-3-030-68773-1_7 12244
Baksi, A., Bhasin, S., Breier, J., Jap, D., Saha, D.: A survey on fault attacks on symmetric key cryptosystems. ACM Comput. Surv. 55(4), (2022). https://doi.org/10.1145/3530054
Barthe, G., et al.: Strong non-interference and type-directed higher-order masking. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds), ACM CCS 2016, pp. 116–129. ACM Press, October 2016. https://doi.org/10.1145/2976749.2978427
Bar-El H Choukri H Naccache D Tunstall M Whelan C The sorcerer’s apprentice guide to fault attacks Proc. IEEE 2006 94 2 370 382 10.1109/JPROC.2005.862424
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th FOCS, pp. 394–403. IEEE Computer Society Press, October 1997. https://doi.org/10.1109/SFCS.1997.646128
Billet O Gilbert H Ech-Chatbi C Handschuh H Hasan MA Cryptanalysis of a white box AES implementation Selected Areas in Cryptography 2004 Heidelberg Springer 227 240 10.1007/978-3-540-30564-4_16 3357
Bos JW Hubain C Michiels W Teuwen P Gierlichs B Poschmann AY Differential computation analysis: hiding your white-box designs is not enough Cryptographic Hardware and Embedded Systems – CHES 2016 2016 Heidelberg Springer 215 236 10.1007/978-3-662-53140-2_11 9813
Both L May A Lange T Steinwandt R Decoding linear codes with high error rate and its impact for LPN security Post-Quantum Cryptography 2018 Cham Springer 25 46 10.1007/978-3-319-79063-3_2 10786
Bellare M Namprempre C Okamoto T Authenticated encryption: relations among notions and analysis of the generic composition paradigm Advances in Cryptology — ASIACRYPT 2000 2000 Heidelberg Springer 531 545 10.1007/3-540-44448-3_41 1976
Bogdanov A Rivain M Vejre PS Wang J Polian I Stöttinger M Higher-order DCA against standard side-channel countermeasures Constructive Side-Channel Analysis and Secure Design 2019 Cham Springer 118 141 10.1007/978-3-030-16350-1_8 11421
Biham E Shamir A Kaliski BS Differential fault analysis of secret key cryptosystems Advances in Cryptology — CRYPTO ’97 1997 Heidelberg Springer 513 525 10.1007/BFb0052259 1294
Biryukov A Udovenko A Peyrin T Galbraith S Attacks and countermeasures for white-box designs Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 373 402 10.1007/978-3-030-03329-3_13 11273
Biryukov A Udovenko A Canteaut A Standaert F-X Dummy shuffling against algebraic attacks in white-box implementations Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 219 248 10.1007/978-3-030-77886-6_8 12697
Chow S Eisen P Johnson H van Oorschot PC Feigenbaum J A white-box DES implementation for DRM applications Digital Rights Management 2003 Heidelberg Springer 1 15 10.1007/978-3-540-44993-5_1 2696
Chow S Eisen P Johnson H Van Oorschot PC Nyberg K Heys H White-box cryptography and an AES implementation Selected Areas in Cryptography 2003 Heidelberg Springer 250 270 10.1007/3-540-36492-7_17 2595
Clavier C Paillier P Verbauwhede I Secret external encodings do not prevent transient fault analysis Cryptographic Hardware and Embedded Systems - CHES 2007 2007 Heidelberg Springer 181 194 10.1007/978-3-540-74735-2_13 4727
Coron, J.-S., Prouff, E., Rivain, M., Roche, T.: Higher-order side channel security and mask refreshing. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 410–424. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43933-3_21
Chen, X., Shu, W., Zhou, Z.: Algorithms for sparse lpn and lspn against low-noise (extended abstract). In: Haghtalab, N., Moitra, A. (eds.), Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 1091–1093. PMLR, 30 Jun–04 Jul 2025. https://proceedings.mlr.press/v291/chen25f.html
Charlès, A., Udovenko, A.: LPN-based attacks in the white-box setting. IACR TCHES 2023 (4), 318–343 (2023). https://doi.org/10.46586/tches.v2023.i4.318-343
Charlès, A., Udovenko, A.: White-box filtering attacks breaking SEL masking: from exponential to polynomial time. IACR Tches 2024(3), 1–24 (2024). https://doi.org/10.46586/tches.v2024.i3.1-24
Charlès, A., Udovenko, A.: A light white-box masking scheme using dummy shuffled secure multiplication. Cryptology ePrint Archive, Report 2025/171 (2025). https://eprint.iacr.org/2025/171
Charls, A., Udovenko, A.: HaystackCiphers - supporting code, September 2025. https://doi.org/10.5281/zenodo.17078398
Dobraunig, C., Eichlseder, M., Korak, T., Mangard, S., Mendel, F., Primas, R.: SIFA: exploiting ineffective fault inductions on symmetric cryptography. IACR Tches 2018(3), 547–572 (2018). https://tches.iacr.org/index.php/TCHES/article/view/7286, https://doi.org/10.13154/tches.v2018.i3.547-572
Data encryption standard. National Bureau of Standards, NBS FIPS PUB 46, U.S. Department of Commerce, January 1977
Daemen, J., Rijmen, V.: The design of Rijndael: AES-the advanced encryption standard. Information Security and Cryptography. Springer, Berlin, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04722-4
De Mulder Y Roelse P Preneel B Knudsen LR Wu H Cryptanalysis of the xiao – Lai white-box AES implementation Selected Areas in Cryptography 2013 Heidelberg Springer 34 49 10.1007/978-3-642-35999-6_3 7707
Emmanuel, P., Guenael, R., Matthieu, R., Colin, O.: Embedded Cryptography, chapter 3. Wiley (2025). https://www.wiley.com/en-us/Embedded+Cryptography+3-p-9781394351923
Esser A Kübler R May A Katz J Shacham H LPN decoded Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 486 514 10.1007/978-3-319-63715-0_17 10402
Fuhr, T., Jaulmes, É., Lomné, V., Thillard, A.: Fault attacks on AES with faulty ciphertexts only. In: Fischer, W., Schmidt, J.-M. (eds.), 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography, Los Alamitos, CA, USA, August 20, 2013, pp. 108–118. IEEE Computer Society (2013). https://doi.org/10.1109/FDTC.2013.18
Goubin L Paillier P Rivain M Wang J How to reveal the secrets of an obscure white-box implementation J. Cryptogr. Eng. 2019 10 1 49 66 10.1007/s13389-019-00207-5
Grigorescu E Reyzin L Vempala S Kivinen J Szepesvári C Ukkonen E Zeugmann T On noise-tolerant learning of sparse parities and related problems Algorithmic Learning Theory 2011 Heidelberg Springer 413 424 10.1007/978-3-642-24412-4_32 6925
Ishai Y Sahai A Wagner D Boneh D Private circuits: securing hardware against probing attacks Advances in Cryptology - CRYPTO 2003 2003 Heidelberg Springer 463 481 10.1007/978-3-540-45146-4_27 2729
Kocher P Jaffe J Jun B Wiener M Differential power analysis Advances in Cryptology — CRYPTO’ 99 1999 Heidelberg Springer 388 397 10.1007/3-540-48405-1_25 1666
Karppa, M., Kaski, P., Kohonen, J.: A faster subquadratic algorithm for finding outlier correlations. In: Krauthgamer, R. (ed.) 27th SODA, pp. 1288–1305. ACM-SIAM, January 2016. https://doi.org/10.1137/1.9781611974331.ch90
Kocher PC Koblitz N Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems Advances in Cryptology — CRYPTO ’96 1996 Heidelberg Springer 104 113 10.1007/3-540-68697-5_9 1109
Lashermes, R., Reymond, G., Dutertre, J.-M., Jacques, J.A., Fournier, B.R., Tria, A.: A DFA on AES based on the entropy of error distributions. In: Bertoni, G., Gierlichs, B. (eds.), 2012 Workshop on Fault Diagnosis and Tolerance in Cryptography, Leuven, Belgium, September 9, 2012, pp. 34–43. IEEE Computer Society (2012). https://doi.org/10.1109/FDTC.2012.18
Lepoint, T., Rivain, M., De Mulder, Y., Roelse, P., Preneel, B.: Two Attacks on a White-Box AES Implementation. In: Lange, T., Lauter, K., Lisoněk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 265–285. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43414-7_14
Li Y Sakiyama K Gomisawa S Fukunaga T Takahashi J Ohta K Mangard S Standaert F-X Fault sensitivity analysis Cryptographic Hardware and Embedded Systems, CHES 2010 2010 Heidelberg Springer 320 334 10.1007/978-3-642-15031-9_22 6225
Piret G Quisquater J-J Walter CD Koç ÇK Paar C A differential fault attack technique against SPN structures, with application to the AES and Khazad Cryptographic Hardware and Embedded Systems - CHES 2003 2003 Heidelberg Springer 77 88 10.1007/978-3-540-45238-6_7 2779
Rivain, M., Wang, J.: Analysis and improvement of differential computation attacks against internally-encoded white-box implementations. IACR Tches 2019(2), 225–255 (2019). https://tches.iacr.org/index.php/TCHES/article/view/7391, https://doi.org/10.13154/tches.v2019.i2.225-255
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 10.6) (2025). https://www.sagemath.org
Shrimpton, T.: A characterization of authenticated-encryption as a form of chosen-ciphertext security. Cryptology ePrint Archive, Report 2004/272 (2004). https://eprint.iacr.org/2004/272
Sanfelix, E., Mune, C., de Haas, J.: Unboxing the white-box. Practical attacks against obfuscated ciphers. Black Hat Europe 2015 (2015)
Strassen V Gaussian elimination is not optimal Numer. Math. 1969 13 4 354 356 248973 10.1007/BF02165411
Tang, Y., Gong, Z., Chen, J., Xie, N.: Higher-order DCA attacks on white-box implementations with masking and shuffling countermeasures. IACR Tches 2023(1), 369–400 (2023). https://doi.org/10.46586/tches.v2023.i1.369-400
Tang, Y., Gong, Z., Li, B., Zhao, L.: Revisiting the computation analysis against internal encodings in white-box implementations. IACR Tches 2023(4), 493–522 (2023). https://doi.org/10.46586/tches.v2023.i4.493-522
Wang, W., Méaux, P., Cassiers, G., Standaert, F.-X:. Efficient and private computations with code-based masking. IACR Tches 2020 (2), 128–171 (2020). https://tches.iacr.org/index.php/TCHES/article/view/8547, https://doi.org/10.13154/tches.v2020.i2.128-171
Wiggers, T., Samardjiska, S.: Practically solving LPN. In: 2021 IEEE International Symposium on Information Theory (ISIT), pp. 2399–2404, July 2021. https://doi.org/10.1109/ISIT45174.2021.9518109
