[ SEE THE OTHER PROPOSALS ]

Keywords: Authentication, Cryptanalysis of Protocol, Logic-based Cryptography.

Requirements: The student candidate for this thesis should show up some dexterity in manipulating basic logic operations, and possess some skills in implementation with a mathematical-oriented language and/or in C.

Abstract: Authentication is a well known concept that is intensively studied for many years. It can rely on basic protocols based on the exchange of a password, on a challenge-response protocol, or on a dedicated zero-knowledge protocol as Fiat-Shamir, Schnorr, Guillou-Quisquater, and others.

While cryptographers mostly focused on heavy cryptography for two decades, the deployment of ubiquitous computer systems brought again the lightweight cryptography under the spotlights. Designing secure applications without any public-key cryptography is the new challenge of our era. Mobile applications are even more requiring: ensuring authentication is no longer enough, dealing with privacy is also a subject of matter. Current challenge-response protocols, as defined for example in the standard ISO-9796, do not fit well this new requirement: in a classical framework, it is implicit that the verifier knows the identity of the prover in order to check his response. Without this assumption, the verifier would have to test all the keys he stores to find the appropriate one. Roughly speaking, this problem can be summarized by the following question: In front of a door lock, given a ring of n indistinguishable keys, how can one find the right key that will open the door with a complexity better than O(n).

Several symmetric-key based protocols have been introduced during the last years in order to reduce this complexity while still preserving privacy. One approach consists simply in degrading the security or privacy of the protocol in order to reduce the complexity. Another approach - which we consider in this work - consists in designing authentication protocols that require a synchronization between the prover and the verifier. For example, the key shared between the verifier and the prover is refreshed each time the prover is queried and so required the two entities to remain synchronized. Such a synchronization is also the Achille heel of solutions based on stream ciphers.

In this work, we will focus on a family of lightweight authentication protocols designed by Peris-Lopez et al., which rely on basic logic operations. Most of their proposals, e.g., LMAP [PerisHER-2006-rfidsec] and EMAP [PerisHER-2006-otm-is] have been broken soon after their publication. They recently published a new variant called Gossamer [Gossamer-2008-wisa] that seems much more resistant. If such a protocol was really secure, it would become very attractive for low-capabilities devices. The goal of this work is so to analysis the security of Gossamer and - as I think so - to break it. Due to the exotic design of Gossamer - it has been designed using a genetic algorithm - several approaches can be considered to carry out the cryptanalysis, which could be based on a simple logic analysis, a statistical analysis, or an algebraic analysis, to name a few.

The candidate can have a foretaste of this exciting and challenging topic by having a look at the article [Gossamer-2008-wisa].