Integrity (I) codes: Message Integrity Protection and Authentication over Insecure Channels

Inspired by unidirectional error detecting codes that are used in situations where only one kind of bit errors are possible (e.g., it is possible to change a bit “0” into a bit “1”, but not the contrary), we propose integrity codes (I-codes) for a radio communication channel, which enable integrity protection of messages exchanged between entities that do not hold any mutual authentication material (i.e. public keys or shared secret keys). The construction of I-codes enables a sender to encode any message such that if its integrity is violated in transmission over a radio channel, the receiver is able to detect it. In order to achieve this, we rely on the physical properties of the radio channel. We analyze in detail the use of I-codes on a radio communication channel and we present their implementation on a Mica2 wireless sensor platform as a “proof of concept”. We finally introduce a novel concept called “authentication through presence” that can be used for several applications, including for key establishment and for broadcast authentication over an insecure radio channel. We perform a detailed analysis of the security of our coding scheme and we show that it is secure with respect to a realistic attacker model.

Key Agreement in Peer-to-Peer Wireless Networks

Mario Cagalj, Srdan Capkun, Jean-Pierre Hubaux

We present a set of simple techniques for key establishment over a radio link in peer-to-peer networks. Our approach is based on the Diffie-Hellman key agreement protocol, which is known to be vulnerable to the ``man-in-the-middle" attack if the two users involved in the protocol share no authenticated information about each other (e.g., public keys, certificates, passwords, shared keys, etc.) prior to the protocol execution. In this paper, we show how the users can establish a shared key even if they share no authenticated information in advance; for this purpose, we leverage on the natural ability of users to authenticate each other by visual and verbal contact. Each of our techniques is based on a specific mechanism: (i) visual comparison of short strings, (ii) distance bounding, and (iii) integrity codes; in each case, the users do not need to enter any password or other data, nor do they need physical or infra-red connectivity between their devices. We base our analysis on a well-established methodology, leading us to a rigorous modularization and robustness proof of our proposal.

2006

Secure Communications over Insecure Channels Using an Authenticated Channel

Sylvain Pasini

A secure communication over an insecure channel without any prior exchanged key can be established with the help of an authentication step to exchange a public key and then using public-key cryptography such as RSA. In this work, we concentrate on message authentication protocols which require an extra authenticated channel. We also recall biometrics-based systems which are hard to implement and distance bounding-based authentication systems which are limited to closer communications. We sketch three generic attacks against any message authentication protocol, conclude on their maximal security, and study the security of some protocols. Finally, we propose a new protocol which achieves the same security level as that of SSH and GPG, but using much less authenticated bits.

2005

Secure communication using authenticated channels

Sylvain Pasini

Our main motivation is to design more user-friendly security protocols. Indeed, if the use of the protocol is tedious, most users will not behave correctly and, consequently, security issues occur. An example is the actual behavior of a user in front of an SSH certificate validation: while this task is of utmost importance, about 99% of SSH users accept the received certificate without checking it. Designing more user-friendly protocols may be difficult since the security should not decrease at the same time. Interestingly, insecure channels coexist with channels ensuring authentication. In practice, these latters may be used for a string comparison or a string copy, e.g., by voice over IP spelling. The shorter the authenticated string is, the less human interaction the protocol requires, and the more user-friendly the protocol is. This leads to the notion of SAS-based cryptography, where SAS stands for Short Authenticated String. In the first part of this thesis, we analyze and propose optimal SAS-based message authentication protocols. By using these protocols, we show how to construct optimal SAS-based authenticated key agreements. Such a protocol enables any group of users to agree on a shared secret key. SAS-based cryptography requires no pre-shared key, no trusted third party, and no public-key infrastructure. However, it requires the user to exchange a short SAS, e.g., five decimal digits. By using the just agreed secret key, the group can now achieve a secure communication based on symmetric cryptography. SAS-based authentication protocols are often used to authenticate the protocol messages of a key agreement. Hence, each new secure communication requires the interaction of the users to agree on the SAS. A solution to reduce the user interaction is to use digital signature schemes. Indeed, in a setup phase, the users can use a SAS-based authentication protocol to exchange long-term verification keys. Then, using digital signatures, users are able to run several key agreements and the authentication of protocol messages is done by digital signatures. In the case where no authenticated channel is available, but a public-key infrastructure is in place, the SAS-based setup phase is avoided since verification keys are already authenticated by the infrastructure. In the second part of this thesis, we also study two problems related to digital signatures: (1) the insecurity of digital signature schemes which use weak hash functions and (2) the privacy issues from signed documents. Digital signatures are often proven to be secure in the random oracle model. The role of random oracles is to model ideal hash functions. However, real hash functions deviate more and more from this idealization. Indeed, weaknesses on hash functions have already been discovered and we are expecting new ones. A question is how to fix the existing signature constructions based on these weak hash functions. In this thesis, we first try to find a better way to model weak hash function. Then, we propose a (randomized) pre-processing to the input message which transforms any weak signature implementation into a strong signature scheme. There remains one drawback due to the randomization. Indeed, the random coins must be sent and thus the signature enlarges. We also propose a method to avoid the increase in signature length by reusing signing coins. Digital signatures may also lead to privacy issues. Indeed, given a message and its signature, anyone can publish the pair which will confirm the authenticity of the message. In certain applications, like in electronic passports (e-passports), publishing the authenticated data leads to serious privacy issues. In this thesis, we define the required security properties in order to protect the data privacy, especially in the case of e-passport verification. The main idea consists for the e-passport to keep the signature secret. The e-passport should only prove that it knows a valid signature instead of revealing it. We propose a new primitive, called Offline Non-Transferable Authentication Protocol (ONTAP), as well as efficient implementations that are compatible with the e-passport standard signature schemes.

EPFL2009

Secure communication using authenticated channels

Sylvain Pasini

EPFL2009