Linear Repairing Codes and Side-Channel Attacks 📺
To strengthen the resistance of countermeasures based on secret sharing,several works have suggested to use the scheme introduced by Shamir in 1978, which proposes to use the evaluation of a random d-degree polynomial into n ≥ d + 1 public points to share the sensitive data. Applying the same principles used against the classical Boolean sharing, all these works have assumed that the most efficient attack strategy was to exploit the minimum number of shares required to rebuild the sensitive value; which is d + 1 if the reconstruction is made with Lagrange’s interpolation. In this paper, we highlight first an important difference between Boolean and Shamir’s sharings which implies that, for some signal-to-noise ratio, it is more advantageous for the adversary to observe strictly more than d + 1 shares. We argue that this difference is related to the existence of so-called linear exact repairing codes, which themselves come with reconstruction formulae that need (much) less information (counted in bits) than Lagrange’s interpolation. In particular, this result implies that the choice of the public points in Shamir’s sharing has an impact on the countermeasure strength, which confirms previous observations made by Wang et al. at CARDIS 2016 for the so-called inner product sharing which is a generalization of Shamir’s scheme. As another contribution, we exhibit a positive impact of the existence of linear exact repairing schemes; we indeed propose to use them to improve the state-of-the-art multiplication algorithms dedicated to Shamir’s sharing. We argue that the improvement can be effective when the multiplication operation in the sub-fields is at least two times smaller than that of the base field.
Trusted-HB: a low-cost version of HB+ secure against Man-in-The-Middle attacks
Since the introduction at Crypto'05 by Juels and Weis of the protocol HB+, a lightweight protocol secure against active attacks but only in a detection based-model, many works have tried to enhance its security. We propose here a new approach to achieve resistance against Man-in-The-Middle attacks. Our requirements - in terms of extra communications and hardware - are surprisingly low.
Identification and Privacy: Zero-Knowledge is not Enough
At first glance, privacy and zero-knowledgeness seem to be similar properties. A scheme is private when no information is revealed on the prover and in a zero-knowledge scheme, communications should not leak provers' secrets. Until recently, privacy threats were only partially formalized and some zero-knowledge (ZK) schemes have been proposed so far to ensure privacy. We here explain why the intended goal is not reached. Following the privacy model proposed by Vaudenay at Asiacrypt 2007, we then reconsider the analysis of these schemes and thereafter introduce a general framework to modify identification schemes leading to different levels of privacy. Our new protocols can be useful, for instance, for identity documents, where privacy is a great issue. Furthermore, we propose efficient implementations of zero-knowledge and private identification schemes based on modifications of the GPS scheme. The security and the privacy are based on a new problem: the Short Exponent Strong Diffie-Hellman (SESDH) problem. The hardness of this problem is related to the hardness of the Strong Diffie-Hellman (SDH) problem and to the hardness of the Discrete Logarithm with Short Exponent (DLSE) problem. The security and privacy of these new schemes are proved in the random oracle paradigm.
Strengthening the Tree-Based Hash Protocols against Compromise of some Tags
In 2004, Molnar and Wagner introduced in  a very appealing scheme dedicated to the identification of RFID tags. Their protocol relies on a binary tree of secrets which are shared -- for all nodes except the leaves -- amongst the tags. Hence the compromise of one tag also has implications on the other tags with whom it shares keys. We introduce a modification of the initial scheme to allow us to strengthen RFID tags by implementing secrets with Physical Obfuscated Keys (POK). This doing, we augment tags and tree resistance against physical threats.
White Box Cryptography: Another Attempt
At CMS 2006 Bringer et al. show how to conceal the algebraic structure of a ``traceable block cipher'' by adding perturbations to its description. We here exploit and strengthen their ideas by further perturbing the representation of a cipher towards a white box implementation. Our technique is quite general, and we apply it -- as a challenging example in the domain of white box cryptography -- to a variant of the block cipher AES.
Perturbing and Protecting a Traceable Block Cipher
At the Asiacrypt 2003 conference Billet and Gilbert introduce a block cipher, which, to quote them, has the following paradoxical traceability properties: it is computationally easy to derive many equivalent distinct descriptions of the same instance of the block cipher; but it is computationally difficult, given one or even up to $k$ of them, to recover the so-called meta-key from which they were derived, or to find any additional equivalent description, or more generally to forge any new untraceable description of the same instance of the block cipher. Their construction relies on the Isomorphism of Polynomials (IP) problem. We here show how to strengthen this construction against algebraic attacks by concealing the underlying IP problems. Our modification is such that our description of the block cipher now does not give the expected results all the time and parallel executions are used to obtain the correct value.
A Fuzzy Sketch with Trapdoor
In 1999, Juels and Wattenberg introduce an effective construction of Fuzzy Sketch, i.e. a way of handling errors into string verification. This allows them to consider data varying into time, such as, for instance, answers to a list of subjective questions. To this end, they utilize an Error Correcting Code. We here show how to embed a trapdoor into Fuzzy Sketches, reducing to authorized people the ability to correct errors and thus to verify the fuzzy equality to the Fuzzy Sketch.
HB++: a Lightweight Authentication Protocol Secure against Some Attacks
At Crypto'05, Juels and Weis introduce HB+, an enhancement of the Hopper and Blum (HB) authentication protocol. This protocol HB+ is proven secure against active attacks, though preserving HB's advantages: mainly, requiring so few resources to run that it can be implemented on an RFID tag. However, in a wider adversarial model, Gilbert, Robshaw and Sibert exhibit a very effective attack against HB+. We here show how a modification of the HB+ protocol thwarts Gilbert et al's attack. The resulting protocol, HB++, remains a good candidate for RFID tags authentication.
Electromagnetic Side Channels of an FPGA Implementation of AES
We show how to attack an FPGA implementation of AES where all bytes are processed in parallel using differential electromagnetic analysis. We first focus on exploiting local side channels to isolate the behaviour of our targeted byte. Then, generalizing the Square attack, we describe a new way of retrieving information, mixing algebraic properties and physical observations.
Grey Box Implementation of Block Ciphers Preserving the Confidentiality of their Design
In 1997,Patarin and Goubin introduce new asymmetric cryptosystems based on the difficulty of recovering two systems of multivariate polynomials from their composition. We make a different use of this difficult algorithmic problem to obtain a way of representing block ciphers concealing their design but still leaving them executable. We show how to implement our solution with Field Programmable Gate Array. Finally, we give a compact representation of our solution using Binary Decision Diagrams.
- Maël Berthier (1)
- Yves Bocktaels (1)
- Julien Bringer (9)
- Vincent Carlier (2)
- Taoufik Chouta (1)
- Jean-Luc Danger (1)
- Quoc Dung Do (1)
- Emmanuelle Dottax (5)
- Mélanie Favre (1)
- Tarik Graba (1)
- Thomas Icart (2)
- Roch Lescuyer (1)
- Houssem Maghrebi (1)
- Emmanuel Michon (1)
- Alain Patey (1)
- Herv? Pelletier (1)
- Duong Hieu Phan (1)
- David Pointcheval (1)
- Emmanuel Prouff (1)