Search

International audience

Pre-prints; We revisit the popular adage that side-channel countermeasures must be combined to be efficient, and study its application to bitslice masking and shuffling. Our contributions are threefold. First, we improve this combination: by shuffling the shares of a masked implementation rather than its tuples, we can amplify the impact of the shuffling exponentially in the number of shares, while this impact was independent of the masking security order in previous works. Second, we evaluate the masking and shuffling combination's performance vs. security tradeoff under sufficient noise conditions: we show that the best approach is to mask first (i.e., fill the registers with as many shares as possible) and shuffle the independent operations that remain. Third, we discuss the challenges for implementing masking and shuffling under low noise conditions: we recall that such algorithmic countermeasures cannot be implemented securely without a minimum level of physical noise. We conclude that with moderate but sufficient noise, the bitslice masking + shuffling combination is relevant, and its interest increases when randomness is expensive and many independent operations are available for shuffling. When these conditions are not met, masking only is the best option. As a side result, we improve the best known attack against shuffling from Asiacrypt 2012, which we use in our concrete evaluations.

International audience

International audience

International audience

One important open question in side-channel analysis is to find out whether all the leakage samples in an implementation can be exploited by an adversary, as suggested by masking security proofs. For attacks exploiting a divide-and-conquer strategy, the answer is negative: only the leakages corresponding to the first/last rounds of a block cipher can be exploited. Soft Analytical Side-Channel Attacks (SASCA) have been introduced as a powerful solution to mitigate this limitation. They represent the target implementation and its leakages as a code (similar to a Low Density Parity Check code) that is decoded thanks to belief propagation. Previous works have shown the low data complexities that SASCA can reach in practice. In this paper, we revisit these attacks by modeling them with a variation of the Random Probing Model used in masking security proofs, that we denote as the Local Random Probing Model (LRPM). Our study establishes interesting connections between this model and the erasure channel used in coding theory, leading to the following benefits. First, the LRPM allows bounding the security of concrete implementations against SASCA in a fast and intuitive manner. We use it in order to confirm that the leakage of any operation in a block cipher can be exploited, although the leakages of external operations dominate in known-plaintext/ciphertext attack scenarios. Second, we show that the LRPM is a tool of choice for the (nearly worst-case) analysis of masked implementations in the noisy leakage model, taking advantage of all the operations performed, and leading to new tradeoffs between their amount of randomness and physical noise level. Third, we show that it can considerably speed up the evaluation of other countermeasures such as shuffling., IACR Transactions on Cryptographic Hardware and Embedded Systems, Volume 2020, Issue 4

International audience; Power and electromagnetic based side-channel attacks are serious threats against the security of cryptographic embedded devices. In order to mitigate these attacks, implementations use countermeasures, among which masking is currently the most investigated and deployed choice. Unfortunately, commonly studied forms of masking rely on underlying assumptions that are difficult to satisfy in practice. This is due to physical defaults, such as glitches or transitions, which can recombine the masked data in a way that concretely reduces an implementation's security. We develop and implement an automated approach for verifying security of masked implementations in presence of physical defaults (glitches or transitions). Our approach helps to recover the main strengths of masking: rigorous foundations, composability guarantees, automated verification under more realistic assumptions. Our work follows the approach of (Barthe et al, EUROCRYPT 2015) and thus contributes to demonstrate the benefits of language-based approaches (specifically probabilistic information flow) for masking.

International audience; In this paper, we provide a necessary clarification of the good security properties that can be obtained from parallel implementations of masking schemes. For this purpose, we first argue that (i) the probing model is not straightforward to interpret, since it more naturally captures the intuitions of serial implementations, and (ii) the noisy leakage model is not always convenient, e.g. when combined with formal methods for the verification of cryptographic implementations. Therefore we introduce a new model, the bounded moment model, that formalizes a weaker notion of security order frequently used in the side-channel literature. Interestingly , we prove that probing security for a serial implementation implies bounded moment security for its parallel counterpart. This result therefore enables an accurate understanding of the links between formal security analyses of masking schemes and experimental security evaluations based on the estimation of statistical moments Besides its consolidating nature, our work also brings useful technical contributions. First, we describe and analyze refreshing and multiplication algorithms that are well suited for parallel implementations and improve security against multivariate side-channel attacks. Second, we show that simple refreshing algorithms (with linear complexity) that are not secure in the continuous probing model are secure in the continuous bounded moment model. Eventually, we discuss the independent leakage assumption required for masking to deliver its security promises, and its specificities related to the serial or parallel nature of an implementation.

International audience

International audience

International audience; Symmetric ciphers purposed for Fully Homomorphic Encryption FHE have recently been proposed for two main reasons. First, minimizing the implementation time and memory overheads that are inherent to current FHE schemes. Second, improving the homomorphic capacity, i.e. the amount of operations that one can perform on homomorphic ciphertexts before bootstrapping, which amounts to limit their level of noise. Existing solutions for this purpose suggest a gap between block ciphers and stream ciphers. The first ones typically allow a constant but small homomorphic capacity, due to the iteration of rounds eventually leading to complex Boolean functions hence large noise. The second ones typically allow a larger homomorphic capacity for the first ciphertext blocks, that decreases with the number of ciphertext blocks due to the increasing Boolean complexity of the stream ciphers' output. In this paper, we aim to combine the best of these two worlds, and propose a new stream cipher construction that allows constant and smaller noise. Its main idea is to apply a Boolean filter function to a public bit permutation of a constant key register, so that the Boolean complexity of the stream cipher outputs is constant. We also propose an instantiation of the filter function designed to exploit recent 3rd-generation FHE schemes, where the error growth is quasi-additive when adequately multiplying ciphertexts with the same amount of noise. In order to stimulate further investigation, we then specify a few instances of this stream cipher, for which we provide a preliminary security analysis. We finally highlight the good properties of our stream cipher regarding the other goal of minimizing the time and memory complexity of calculus delegation for 2nd-generation FHE﾿schemes. We conclude the paper with open problems related to the large design space opened by these new constructions.

International audience; Side-channel analysis is long known as a real threat on unprotected and even protected devices. While template attacks are admittedly the most powerful ones, most practical attacks are of a different kind, such as Kocher’s difference of mean or correlation power analysis. It is the imprecision of the a priori leakage model that accounts for the discrepancy between theory and practice. A closer look into the math- ematical expression of template attacks reveals conditions under which practical distinguishers may approach optimality. A metric aiming at quantifying the amount of leakage in an information-theoretic con- text has been recently put forward as the perceived information. We show that this metric also corresponds to the likelihood computed by a template attack using an imperfect model. We thus consolidate the published literature about optimal (template) attacks and optimal distinguishers by clarifying the state-of-the-art about the strongest side-channel adversarial strategies, with emphasis on the importance of the initial knowledge of the system under attack, which is typically accessed through profiling.

International audience

Evalutation d'Attaques par Canaux Cachés : Template VS Machine Learning

International audience; The design and analysis of lightweight block ciphers has been a very active research area over the last couple of years, with many innovative proposals trying to optimize di erent performance gures. However, since these block ciphers are dedicated to low-cost embedded devices, their implementation is also a typical target for side-channel adversaries. As preventing such attacks with countermeasures usually implies signi cant performance overheads, a natural open problem is to propose new algorithms for which physical security is considered as an optimization criteria, hence allowing better performances again. We tackle this problem by studying how much we can tweak standard block ciphers such as the AES Rijndael in order to allow e cient masking (that is one of the most frequently considered solutions to improve security against side-channel attacks). For this purpose, we rst investigate alternative S- boxes and round structures. We show that both approaches can be used separately in order to limit the total number of non-linear operations in the block cipher, hence allowing more e cient masking. We then combine these ideas into a concrete instance of block cipher called Zorro. We further provide a detailed security analysis of this new cipher taking its design speci cities into account, leading us to exploit innovative techniques borrowed from hash function cryptanalysis (that are sometimes of independent interest). Eventually, we conclude the paper by evaluating the e ciency of masked Zorro implementations in an 8-bit microcontroller, and exhibit their interesting performance gures.

Part 5: Implementations and Hardware Security 2; International audience; Allowing good performances on different platforms is an important criteria for the selection of the future sha-3 standard. In this paper, we consider the compact implementations of blake, Grøstl, jh, Keccak and Skein on recent fpga devices. Our results bring an interesting complement to existing analyzes, as most previous works on fpga implementations of the sha-3 candidates were optimized for high throughput applications. Following recent guidelines for the fair comparison of hardware architectures, we put forward clear trends for the selection of the future standard. First, compact fpga implementations of Keccak are less efficient than their high throughput counterparts. Second, Grøstl shows interesting performances in this setting, in particular in terms of throughput over area ratio. Third, the remaining candidates are comparably suitable for compact fpga implementations, with some slight contrasts (in area cost and throughput).

Part 3: New Algorithms and Protocols; International audience; Security-aware embedded systems are widespread nowadays and many applications, such as payment, pay-TV and automotive applications rely on them. These devices are usually very resource constrained but at the same time likely to operate in a hostile environment. Thus, the implementation of low-cost protection mechanisms against physical attacks is vital for their market relevance. An appealing choice, to counteract a large family of physical attacks with one mechanism, seem to be protocol-level countermeasures. At last year’s Africacrypt, a fresh re-keying scheme has been presented which combines the advantages of re-keying with those of classical countermeasures such as masking and hiding. The contribution of this paper is threefold: most importantly, the original fresh re-keying scheme was limited to one low-cost party (e.g. an RFID tag) in a two party communication scenario. In this paper we extend the scheme to n low-cost parties and show that the scheme is still secure. Second, one unanswered question in the original paper was the susceptibility of the scheme to algebraic SPA attacks. Therefore, we analyze this property of the scheme. Finally, we implemented the scheme on a common 8-bit microcontroller to show its efficiency in software.

Cryptography studies how to secure communications and information. 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.Classical cryptography only assumes that the adversary accesses the target cryptographic primitive in a black-box manner in which she can only observe or manipulate the input and output of the primitive, but cannot know or tamper with its internal details. The gray-box model further allows an adversary to exploit key- dependent sensitive information leaked from the execution of physical implementations. All sorts of side-channel attacks exploit some physical information leakage, such as the power consumption of the device. The white-box model considers the worst-case scenario in which the adversary has complete control over the software and its execution environment. The goal of white-box cryptography is to securely implement a cryptographic primitive against such a powerful adversary. Although the scientific community has proposed some candidate solutions to build white-box cryptography, all have proven ineffective. Consequently, this problem has remained open for almost two decades since the concept was introduced.The continuous growth in market demand and the emerging potential applications have driven the industry to deploy secretly-designed proprietary solutions. Al- though this paradigm of achieving security through obscurity contradicts the widely accepted Kerckhoffs' principle in cryptography, this is currently the only option for white-box cryptography. Security experts have reported how gray-box attacks could be used to extract keys from several publicly available white-box implementations. In a gray-box attack, the adversary adapts side-channel analysis techniques to the white-box context, i.e., to target computation traces made of noise-free run-time information instead of the noisy physical leakage. Gray-box attacks are generic since they do not require any a priori knowledge of the implementation and hence avoid costly reverse engineering. Some non-publicly scrutinized industrial white-box schemes in the market are believed to be under the threat of gray-box attacks.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 design which is based on table encodings. 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., La cryptographie est la science de la protection des communications et des données. La sécurité d’un cryptosystème dépend du secret de la clé sous-jacente. La cryptographie en boîte blanche explore les méthodes permettant de cacher une clé dans un logiciel cryptographique déployé dans le monde réel.La cryptographie classique suppose que l’adversaire accède à la primitive cryptographique ciblée en boîte noire. Cela signifie qu’elle ne peut qu’observer et manipuler les entrées et les sorties de la primitive, mais ne peut pas connaître ou altérer son état interne. Le modèle en boîte grise permet en outre à un adversaire d’observer des informations sensibles qui sont divulguées lors de l’exécution d’une implémentation de la primitive. Toutes sortes d’attaques par canaux auxiliaires exploitent certaines fuites d’informations physiques, telles que la consommation électrique de l’appareil. Le modèle en boîte blanche considère le scénario le plus défavorable dans lequel l’adversaire a un contrôle total sur le logiciel cryptographique et sur son environnement d’exécution. Le rôle de la cryptographie en boîte blanche est d’implémenter une primitive cryptographique de façon à protéger la clé secrète contre un tel adversaire. Bien que la communauté scientifique ait tenté à plusieurs reprises de solutionner ce problème, ces tentatives se sont toutes révélées inadéquates. Par conséquent, la construction d’une solution de cryptographie en boîte blanche est resté un problème ouvert depuis l’introduction du concept il y a deux décennies.L’émergence d’applications avec de fortes contraintes de sécurité logicielle a poussé l’industrie à développer des solutions propriétaires dont la sécurité repose (en partie) sur des secrets de conception. Bien que ce paradigme de sécurité par l’obscurité contredise le principe de Kerckhoffs largement admis en cryptographie, c’est actuellement la seule option s’offrant à l’industrie pour répondre au besoin de cryptographie en boîte blanche. 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. Dans une attaque en boîte grise, l’adversaire adapte des techniques d’analyse par canaux auxiliaires au contexte boîte blanche, en replaçant la fuite physique par des traces de calcul faites des valeurs intermédiaires non-bruitées observées lors de l’exécution. Les attaques en boîte grise sont génériques car elles ne nécessitent aucune connaissance a priori de l’implémentation et évitent ainsi la nécessité pour l’attaquant de recourir à une rétro-ingénierie coûteuse. Il semble que certaines solutions de cryptographie en boîte blanche actuellement déployée et n’ayant pas fait l’objet d’un examen public soient menacées par ce type d’attaques en boîte grise.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 les attaques en boîte grise basiques sont capables de casser la technique classique de cryptographie en boîte blanche basée sur les encodages de tables. Nous proposons également de nouvelles techniques d’attaque en boîte grise significativement plus efficace contre ce type d’encodages. Nous introduisons ensuite une nouvelle attaque en boîte grise appelée 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 nouvelle 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 sur la cryptographie en boîte blanche. Outre les analyses théoriques et nouvelles techniques d’attaque introduites dans cette thèse, nous rapportons plusieurs expériences d’attaque pratique contre divers implémentations en boîte blanche. Nous démontrons notamment comment nous avons pu casser les implémentations gagnantes des deux éditions consécutives de la compétition WhibOx., 密码学是一门研究保护数据和通信安全的科学。一个密码系统的安全 性取决于其密钥的保密性。白盒密码学探索在现实世界中部署的软件中隐 藏密钥的方法。经典密码学仅假定敌手以黑盒的方式访问被研究的密码学原语, 在这 种方式中，她只能观察或操作原语的输入和输出，而无法知道或篡改其内 部细节。灰盒模型进一步允许敌手利用物理实现执行过程中泄露的与密钥 相关的敏感信息。各种侧信道攻击都是利用一些物理信息泄露，比如设备 的功耗。白盒模型考虑的是最坏的情况，即敌手完全控制了软件及其执行 环境。白盒密码学的目标即是在敌手拥有上述强大能力的情况下，给出密 码学原语的安全软件实现。尽管学术界提出了一些构建白盒密码学的候选 方案，但事实证明这些方案都无效。因此，自概念提出以来，这个开放问 题持续存在了近二十年。白盒密码市场需求的持续增长和新兴的潜在应用促使工业界采用秘密 设计的专有解决方案。尽管这种通过模糊来实现安全性的范例与密码学中 被广泛接受的 Kerckhoffs 原则相悖，但这是在当前困境中的无奈之举。安 全专家报道了如何使用灰盒攻击从几种公开的白盒实现中提取密钥。在灰 盒攻击中，敌手将侧信道分析技术应用到白盒密码学中。她的研究对象是 从软件运行时收集不带任何噪音计算数据而非带有噪声的物理泄漏。灰盒 攻击是一种通用攻击，因为它们不需要关于攻击对象的任何先验知识，从 而避免了代价高昂的逆向工程。市场上一些未经公开审阅的工业白盒计划 被认为正受到灰盒攻击的威胁。本论文主要研究针对白盒密码学进行的灰盒攻击的分析与改进以及相 关对策。首先，我们深入分析了为什么灰盒攻击能够打破经典的基于编码 表的白盒设计。接下来，我们介绍了一种新的称为线性解码分析的灰盒攻 击，并阐释了仅通过对敏感信息进行线性编码的方式来保护软件中的密钥 是不足够的。随后，我们将描述如何通过组合最新的对策来抵抗灰盒攻击， 并从计算复杂性的角度全面阐述这些组合对策的有效性和无效性。最后， 我们介绍了一种新的攻击技术，该技术利用目标实现的数据依赖性来显著 降低现有灰盒攻击应用在白盒密码学的复杂性。本论文除了介绍的理论分 析和新的攻击技术外，还报告了一些针对实际白盒实现的攻击实验。特别 的是，我们连续两届打破了著名的 WhibOx 白盒密码学竞赛中的获胜实现。

Since the late 90s, the implementation of cryptosystems on smart card faces two kinds of attacks : side-channel attacks and fault injection attacks. Countermeasures are then developed and validated by considering a well-defined attacker model. This thesis focuses on the protection of symmetric cryptosystems against side-channel attacks. Specifically, we are interested in masking countermeasures in order to tackle high-order attacks for which an attacker is capable of targeting t intermediate values. After recalling the analogy between masking countermeasures and secret sharing schemes, the construction of secret sharing schemes from linear codes introduced by James L. Massey in 1993 is presented.By adapting this construction together with tools from the field of Multi-Party Computation, we propose a generic masking countermeasure resistant to high-order attacks. Furthermore, depending on the cryptosystem to protect, this solution optimizes the cost of the countermeasure by selecting the most appropriate code. In this context, we propose two countermeasures to implement the AES cryptosystem. The first is based on a family of evaluation codes similar to the Reed Solomon code used in the secret sharing scheme of Shamir. The second considers the family of self-dual and self-orthogonal codes generated by a matrix defined over GF(2) or GF(4). These two alternatives are more effective than masking countermeasures from 2011 based on Shamir's secret sharing scheme. Moreover, for t=1, the second solution is competitive with usual solutions.; Depuis la fin des années 90, les cryptosystèmes implantés sur carte à puce doivent faire face à deux grandes catégories d'attaques : les attaques par canaux cachés et les attaques par injection de fautes. Pour s'en prémunir, des contre-mesures sont élaborées, puis validées en considérant un modèle d'attaquant bien défini. Les travaux réalisés dans cette thèse se concentrent sur la protection des cryptosystèmes symétriques contre les attaques par canaux cachés. Plus précisément, on s'intéresse aux contre-mesures de masquage permettant de se prémunir des attaques statistiques d'ordre supérieur pour lesquelles un attaquant est capable de cibler t valeurs intermédiaires. Après avoir rappelé l'analogie entre les contre-mesures de masquage et les schémas de partage de secret, on présente la construction des schémas de partage de secret à partir de codes linéaires, introduite par James L. Massey en 1993. En adaptant cette construction et des outils issus du calcul multi-parties, on propose une méthode générique de contre-mesure de masquage résistante aux attaques statistiques d'ordre supérieur. De plus, en fonction des cryptosystèmes à protéger et donc des opérations à effectuer, cette solution permet d'optimiserle coût induit par les contre-mesures en sélectionnant les codes les plus adéquats. Dans cette optique, on propose deux contre-mesures de masquage pour implanter le cryptosystème AES. La première est basée sur une famille de code d'évaluation proche de celle utilisée pour le schéma de partage de secret de Shamir, tandis que la seconde considéré la famille des codes auto-duaux et faiblement auto-duaux ayant leur matrice génératrice à coefficient sur F2 ou F4. Ces deux alternatives se révèlent plus efficaces que les contremesures de masquage publiées en 2011 et basées sur le schéma de partage de secret de Shamir. De plus la seconde s'avère compétitive pour t=1 comparée aux solutions usuelles.