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.
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.
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.
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.
- Maël Berthier (1)
- Yves Bocktaels (1)
- Hervé Chabanne (9)
- Taoufik Chouta (1)
- Jean-Luc Danger (2)
- Quoc Dung Do (1)
- Emmanuelle Dottax (3)
- Mélanie Favre (1)
- Tarik Graba (1)
- Thomas Icart (2)
- Roch Lescuyer (1)
- Houssem Maghrebi (1)
- Zakaria Najm (1)
- Alain Patey (1)
- Pablo Rauzy (1)
- Lionel Rivière (1)
- Laurent Sauvage (1)
- Victor Servant (1)