On the practical security of white-box cryptography

À propos

La cryptographie en boîte blanche explore les méthodes permettant de cacher une clé dans un logiciel cryptgraphique déployé dans le monde réel. Toutes les solutions proposées pour construire la cryptographie en boîte blanche se sont révélées inadéquates. Ainsi, l'industrie est poussée à déployer des solutions propriétaires conçues secrètement. Des experts en sécurité ont récemment démontré comment certaines attaques en boîtes grise pouvaient être utilisées pour extraire les clés de plusieurs implémentations en boîte blanche accessibles publiquement. Cette thèse se concentre sur l'analyse et l'amélioration des attaques en boîte grise et des contre-mesures associées pour la cryptographie en boîte blanche. Nous présentons tout d'abord une analyse approfondie des raisons pour lesquelles la technique classique de cryptographie sur boîte blanche est inefficace contre les attaques sur boîte grise. Nous introduisons ensuite une analyse par décodage linéaire qui permet de déjouer toute méthode de protection basée sur un encodage linéaire des variables internes au calcul. Par la suite, nous étudions la combinaison de différentes contre-mesures pour résister aux attaques en boîte grise et analysons en détail la complexité d'attaques avancées contre ces contre-mesures combinées. Nous introduisons enfin une technique d'attaque qui exploite le graphe de calcul de l'implémentation ciblée pour réduire considérablement la complexité des attaques en boîte grise dans ce contexte. En outre, nous rapportons plusieurs expériences d'attaque pratique contre divers implémentations en boîte blanche, y compris les implémentations gagnantes des deux éditions consécutives de la compétition WhibOx.

The security of a cryptosystem depends on the secrecy of the underlying key. White-box cryptography explores methods to hide a cryptographic key into some software deployed in the real world. All proposed candidate solutions to build white-box cryptography have proven ineffective. Thus, the industry is driven to deploy secretly designed proprietary solutions. Security experts have reported how gray-box attacks could be used to extract keys from several publicly available white-box implementations. This thesis focuses on the analysis and improvement of gray-box attacks and the associated countermeasures for white-box cryptography. We first provide an in-depth analysis of why gray-box attacks are capable of breaking the classical white-box designs. Next, we introduce a new gray-box attack named linear decoding analysis and show that linearly encoding sensitive information is insufficient to protect the cryptographic software. Afterward, we describe how to combine state-of-the-art countermeasures to resist gray-box attacks and comprehensively elaborate on the (in)effectiveness of these combined countermeasures in terms of computation complexity. Finally, we introduce a new attack technique that exploits the data-dependency of the targeted implementation to substantially lower the complexity of the existing gray-box attacks on white-box cryptography. In addition to the theoretical analyses and new attack techniques introduced in this thesis, we report some attack experiments against practical white-box implementations. In particular, we could break the winning implementations of two consecutive editions of the well-known WhibOx white-box cryptography competition.e

密码学是一门研究保护数据和通信安全的科学。一个密码系统的安全性取决于其密钥的保密性。白盒密码学探索在现实世界中部署的软件中隐藏密钥的方法。经典密码学仅假定敌手以黑盒的方式访问被研究的密码学原语, 在这种方式中，她只能观察或操作原语的输入和输出，而无法知道或篡改其内部细节。灰盒模型进一步允许敌手利用物理实现执行过程中泄露的与密钥相关的敏感信息。各种侧信道攻击都是利用一些物理信息泄露，比如设备的功耗。白盒模型考虑的是最坏的情况，即敌手完全控制了软件及其执行环境。白盒密码学的目标即是在敌手拥有上述强大能力的情况下，给出密码学原语的安全软件实现。尽管学术界提出了一些构建白盒密码学的候选方案，但事实证明这些方案都无效。因此，自概念提出以来，这个开放问题持续存在了近二十年。白盒密码市场需求的持续增长和新兴的潜在应用促使工业界采用秘密设计的专有解决方案。尽管这种通过模糊来实现安全性的范例与密码学中被广泛接受的 Kerckhoffs 原则相悖，但这是在当前困境中的无奈之举。安全专家报道了如何使用灰盒攻击从几种公开的白盒实现中提取密钥。在灰盒攻击中，敌手将侧信道分析技术应用到白盒密码学中。她的研究对象是从软件运行时收集不带任何噪音计算数据而非带有噪声的物理泄漏。灰盒攻击是一种通用攻击，因为它们不需要关于攻击对象的任何先验知识，从而避免了代价高昂的逆向工程。市场上一些未经公开审阅的工业白盒计划被认为正受到灰盒攻击的威胁。本论文主要研究针对白盒密码学进行的灰盒攻击的分析与改进以及相关对策。首先，我们深入分析了为什么灰盒攻击能够打破经典的基于编码表的白盒设计。接下来，我们介绍了一种新的称为线性解码分析的灰盒攻击，并阐释了仅通过对敏感信息进行线性编码的方式来保护软件中的密钥是不足够的。随后，我们将描述如何通过组合最新的对策来抵抗灰盒攻击， 并从计算复杂性的角度全面阐述这些组合对策的有效性和无效性。最后， 我们介绍了一种新的攻击技术，该技术利用目标实现的数据依赖性来显著降低现有灰盒攻击应用在白盒密码学的复杂性。本论文除了介绍的理论分析和新的攻击技术外，还报告了一些针对实际白盒实现的攻击实验。特别的是，我们连续两届打破了著名的 WhibOx 白盒密码学竞赛中的获胜实现。