Rolando Trujillo-Rasua

Rolando Trujillo-Rasua

Memory erasure protocols serve to clean up a device's memory before the installation of new software. Although this task can be accomplished by direct hardware manipulation, remote software-based memory erasure protocols have emerged as a more efficient and cost-effective alternative. Existing remote memory erasure protocols, however, still rely on non-standard adversarial models to operate correctly, thereby requiring additional hardware to restrict the adversary's capabilities. In this work, we provide a formal definition of secure memory erasure within a symbolic security model that utilizes the standard Dolev-Yao adversary. Our main result consists of a restriction on the Dolev-Yao adversary that we prove necessary and sufficient to solve the problem of finding a protocol that satisfies secure memory erasure. We also provide a description of the resulting protocol using standard cryptographic notation, which we use to analyze the security and communication complexity trade-off commonly present in this type of protocols.

Ahto Buldas, Olga Gadyatskaya, Aleksandr Lenin et al.

Attack trees are considered a useful tool for security modelling because they support qualitative as well as quantitative analysis. The quantitative approach is based on values associated to each node in the tree, expressing, for instance, the minimal cost or probability of an attack. Current quantitative methods for attack trees allow the analyst to, based on an initial assignment of values to the leaf nodes, derive the values of the higher nodes in the tree. In practice, however, it shows to be very difficult to obtain reliable values for all leaf nodes. The main reasons are that data is only available for some of the nodes, that data is available for intermediate nodes rather than for the leaf nodes, or even that the available data is inconsistent. We address these problems by developing a generalisation of the standard bottom-up calculation method in three ways. First, we allow initial attributions of non-leaf nodes. Second, we admit additional relations between attack steps beyond those provided by the underlying attack tree semantics. Third, we support the calculation of an approximative solution in case of inconsistencies. We illustrate our method, which is based on constraint programming, by a comprehensive case study.

Gildas Avoine, Sjouke Mauw, Rolando Trujillo-Rasua

Distance bounding protocols are security countermeasures designed to thwart relay attacks. Such attacks consist in relaying messages exchanged between two parties, making them believe they communicate directly with each other. Although distance bounding protocols have existed since the early nineties, this research topic resurrected with the deployment of contactless systems, against which relay attacks are particularly impactful. Given the impressive number of distance bounding protocols that are designed every year, it becomes urgent to provide researchers and engineers with a methodology to fairly compare the protocols in spite of their various properties. This paper introduces such a methodology based on concepts from the decision making field. The methodology allows for a multi-criteria comparison of distance bounding protocols, thereby identifying the most appropriate protocols once the context is provided. As a side effect, this paper clearly identifies the protocols that should no longer be considered, regardless of the considered scenario.

Ravi Jhawar, Barbara Kordy, Sjouke Mauw et al.

We provide the first formal foundation of SAND attack trees which are a popular extension of the well-known attack trees. The SAND attack tree formalism increases the expressivity of attack trees by introducing the sequential conjunctive operator SAND. This operator enables the modeling of ordered events. We give a semantics to SAND attack trees by interpreting them as sets of series-parallel graphs and propose a complete axiomatization of this semantics. We define normal forms for SAND attack trees and a term rewriting system which allows identification of semantically equivalent trees. Finally, we formalize how to quantitatively analyze SAND attack trees using attributes.

Rolando Trujillo-Rasua

Distance bounding (DB) emerged as a countermeasure to the so-called \emph{relay attack}, which affects several technologies such as RFID, NFC, Bluetooth, and Ad-hoc networks. A prominent family of DB protocols are those based on graphs, which were introduced in 2010 to resist both mafia and distance frauds. The security analysis in terms of distance fraud is performed by considering an adversary that, given a vertex labeled graph $G = (V, E)$ and a vertex $v \in V$, is able to find the most frequent $n$-long sequence in $G$ starting from $v$ (MFS problem). However, to the best of our knowledge, it is still an open question whether the distance fraud security can be computed considering the aforementioned adversarial model. Our first contribution is a proof that the MFS problem is NP-Hard even when the graph is constrained to meet the requirements of a graph-based DB protocol. Although this result does not invalidate the model, it does suggest that a \emph{too-strong} adversary is perhaps being considered (i.e., in practice, graph-based DB protocols might resist distance fraud better than the security model suggests.) Our second contribution is an algorithm addressing the distance fraud security of the tree-based approach due to Avoine and Tchamkerten. The novel algorithm improves the computational complexity $O(2^{2^n+n})$ of the naive approach to $O(2^{2n}n)$ where $n$ is the number of rounds.

Rolando Trujillo-Rasua, Benjamin Martin, Gildas Avoine

Contactless technologies such as RFID, NFC, and sensor networks are vulnerable to mafia and distance frauds. Both frauds aim at passing an authentication protocol by cheating on the actual distance between the prover and the verifier. To cope these security issues, distance-bounding protocols have been designed. However, none of the current proposals simultaneously resists to these two frauds without requiring additional memory and computation. The situation is even worse considering that just a few distance-bounding protocols are able to deal with the inherent background noise on the communication channels. This article introduces a noise-resilient distance-bounding protocol that resists to both mafia and distance frauds. The security of the protocol is analyzed with respect to these two frauds in both scenarios, namely noisy and noiseless channels. Analytical expressions for the adversary's success probabilities are provided, and are illustrated by experimental results. The analysis, performed in an already existing framework for fairness reasons, demonstrates the undeniable advantage of the introduced lightweight design over the previous proposals.

Rolando Trujillo-Rasua

Radio Frequency Identification (RFID) is a technology aimed at eficiently identifying and tracking goods and assets. Such identification may be performed without requiring line-of-sight alignment or physical contact between the RFID tag and the RFID reader, whilst tracking is naturally achieved due to the short interrogation field of RFID readers. That is why the reduction in price of the RFID tags has been accompanied with an increasing attention paid to this technology. However, since tags are resource-constrained devices sending identification data wirelessly, designing secure and private RFID identification protocols is a challenging task. This scenario is even more complex when scalability must be met by those protocols. Assuming the existence of a lightweight, secure, private and scalable RFID identification protocol, there exist other concerns surrounding the RFID technology. Some of them arise from the technology itself, such as distance checking, but others are related to the potential of RFID systems to gather huge amount of tracking data. Publishing and mining such moving objects data is essential to improve efficiency of supervisory control, assets management and localisation, transportation, etc. However, obvious privacy threats arise if an individual can be linked with some of those published trajectories. The present dissertation contributes to the design of algorithms and protocols aimed at dealing with the issues explained above. First, we propose a set of protocols and heuristics based on a distributed architecture that improve the efficiency of the identification process without compromising privacy or security. Moreover, we present a novel distance-bounding protocol based on graphs that is extremely low-resource consuming. Finally, we present two trajectory anonymisation methods aimed at preserving the individuals' privacy when their trajectories are released.