The motivation for the work of this thesis originates from an analysis of the use-cases presented by the CoBIs European project in [Cob07]. In one scenario, drums containing chemicals are stocked in a warehouse; however, safety regulations impose restrictions on the dispositions of these barrels. For instance, barrels containing reactive chemicals cannot be stored close to each other: a small leak of the chemicals could have potentially disastrous consequences.

The devised solution included equipping each barrel with a wireless device. Each device was exchanging information about the content of its associated barrel in cleartext: this allowed to perform some inference on the disposition of the barrels and take countermeasures in case of forbidden combinations. The risk assessment of such scenario showed many shortcomings: the matching of complementary chemicals was possible only due to the fact that the content of the barrels was broadcast in cleartext. The fact that transmissions were in cleartext however may have led to attacks linked to terrorism or to industrial espionage. Many cryptographic solutions can be thought of, or are existing, to address this simple matching problem: a study of possible solutions shows that they are very similar and yet they present subtle differences that in the end create completely different protocols, achieving greatly different results. The focus of this thesis is therefore an analysis of the family of these protocols, called Secret Handshake.

Secret Handshake

A Secret Handshake is a distinct form of greeting which conveys membership in club, group or fraternity [wik10]. Usually a Secret Handshake involves conducting the handshake in a special way so as to be recognizable as such by fellow members while seeming completely normal to non-members. The need for such a secretive initial exchange is motivated by the existence in society of gatherings of individuals, revolving around sensitive topics and therefore secret by nature. With the increasing role over the past half century of electronic communications in our society, it is natural to expect that the discipline of computer science should capture the essence of Secret Handshakes and model it into protocols that can be automatically executed by electronic devices. In particular, given the secret and sensitive nature of the scenarios motivating these protocols – namely secret groups and concealed fraternities – ought to become cryptographic protocols, accounting for the existence of misbehaving users and attackers.

Scenarios 

In this Section we justify Secret Handshakes by presenting a broad range of different scenarios where these protocols may be required. Consider a secret agent on a mission, needing to authenticate to a fellow agent or to a server belonging to the agency. Agents are bound to follow the agency’s policy never to disclose their Credentials, unless they are certain to be dealing with fellow agents or with agency’s servers. The same policy is applied by the servers too. The interesting consequence of the interactions of individuals following such policies is called a policy deadlock: none of the agents will accept to reveal his Credential first, so the communication comes to a standstill. Let us now turn our attention to a user, Alice, who lives in a country with a questionable human-rights record. She is a member of a pro democracy movement. Members periodically gather at secret meetings, where Alice often meets new alleged members, whom she has never met before. Consequently she is worried that she might be dealing with members of the secret police of that state, whose aim is to round up members of the pro-democracy movement and arrest them. Nonetheless, legitimate members need to interact with one another in order to carry on the activities of the movement. Consider now justice forces of a federation of states, needing to cooperate with one another in order to solve cross boundary criminal cases. Regulations of the federation define official processes that must imperatively be followed by operating officers: in particular, these processes mandate which institutions must cooperate upon each particular case. For instance, a member of an agency of one state must cooperate with a member of the corresponding agency of another state, to investigate on an alleged internal scandal. The two officers may need to meet secretly, and authenticate themselves on-the-fly. Both are definitely reluctant to disclose their affiliation and purpose to anybody but the intended recipient. Imagine now a newly formed project consortium whose members want to securely add one another as friends on a social network and use the social network infrastructure as a collaboration tool. The consortium members require means to secure the friendship invitation process: this helps to avoid false negatives, refusing a request from a legitimate consortium member, or false positives, accepting the invitation from a rogue user and consequently interacting with it. In addition, the project consortium may require additional security for fear of industrial espionage. These different scenarios share some common requirements: in each of these examples, users are interested in conducting an authentication protocol and willing to disclose their allegiance, provided that this happens only when they are dealing with the intended remote party, a secret agent in the first example, a member of the prodemocracy movement in the second, a justice official of the intended state in the third and a consortium member in the last. If these conditions do not apply, users require that no information is leaked on their actual membership, except that the matching is not successful.

Characteristics 

The design space of Secret Handshake protocols is governed by two main dimensions. The first and most prominent one is the dimension of security requirements; security requirements aim at giving assurance that Secret Handshake can be used in the presence of adversaries, whose aim is to subvert its operations and increase their return from its execution. Common security requirements include resistance to openly subverting the protocol: for instance, with reference to the first example of the previous Section, somebody who is not a member of the agency must not be able to authenticate as one. Additional security requirements address the amount of information that is leaked by each protocol instance upon unsuccessful executions, or that is leaked to passive adversaries whose aim is to read a number of protocol transcripts and derive information about the nature of users executing them: the information being derived may be the identity of the user, its membership or even the mere information that the same user or members of the same agency have executed the protocol twice. The second dimension relates to functional requirements of the protocol: for instance, these requirements encompass considerations on the existence of a central authority and its role in the protocol. Indeed the protocol can either be managed by a central authority, in charge of creating cryptographic tokens that allow users to conduct the authentication; as an alternative, the protocol can be self-managed by user, without the requirement for a central authority. If a central authority is required, it can exercise variable degrees of control over the capabilities of users, which represents as well another design choice. Another example of functional requirement addresses the actual type of cryptographic token(s) required for the execution of the protocol, as to whether a single type of token is sufficient, whether it can be reused and whether it can be self-generated or not. Further requirements mix functional and security aspects, such as – referring to the same example as before – the support for disqualification from the status of agency member, also known as revocation.

Contributions and Organization

This thesis makes several contributions:

• We perform a detailed analysis of the literature on Secret Handshakes; we build a taxonomy of the Secret Handshake protocol family, examining gradually more complex protocols and introducing new features; at the end of this analysis we present a snapshot of the state-of-the art and we highlight a number of missing features;

• We suggest six new protocols, each of which contributes to completing the spectrum of available techniques in the field. In particular we focus on:
– a new concept of Secret Handshake whereby the aforementioned central authority exercises a strong control over the capabilities of users;
– bringing revocation support to a number of schemes that either completely lacked this support or could only cover a limited range of scenarios;
– decentralized Secret Handshake schemes, with a scheme that requires no central authority and a second one where several independent authorities can federate but maintain their independence;

• We present a first use-case where the techniques discussed in this thesis can be leveraged by users of a social network to spontaneously create a secret group and subsequently secure their interactions on the social network; we design a framework that achieves this objective, and implement part of it in the ever growing Facebook platform [fac]; we also discuss some of the implementation challenges;

• We present a second use-case where companies that are members of a common supply chain can exchange batches of goods equipped with RFID tags; each partner can then perform a Secret Handshake-like authentication with another partner to authenticate on the grounds of having handled a common tag at some point during the life-cycle of the supply chain;

Each new protocol comes with a detailed security analysis, conducted using stateof the-art techniques. The analyses show mastery of the complex art of proving security protocols, since, as it shall be seen in the sequel of this document, in some occasion they require turning to advanced techniques or resorting on complex approaches.