Cryptographic protocols commonly use (random) nonces to guarantee security properties. Although it is known for a long time that nonces should benefit from clear security properties, modern standards regularly miss this fundamental requirement. The lack of clear recommendations leads to error-prone cryptographic implementations, especially vulnerabilities due to nonce reuse and nonce leakage. This paper introduces a method based on TAMARIN to identify with a systematic approach the nonce-related properties an implementation should guarantee to ensure the security of a cryptographic protocol. As a corollary, the method also determines the security impact of a nonce misuse. Our method also applies to other types of random values used in protocols, namely ephemeral keys, masks, and nonces used in randomized primitives. This approach is then extended to take into account the well-known weaknesses of some randomized primitives when nonces are reused. The paper finally applies the method to real-life cryptographic protocols, discovering so new vulnerabilities related to nonce misuses in Dragonfly, WPA3, and Bluetooth.

A cryptanalytic time-memory trade-off is a technique introduced by M. Hellman in 1980 to perform brute-force attacks. It consists of a time-consuming precomputation phase performed and stored once and for all, which is then used to reduce the computation time of brute-force attacks. A variant, known as rainbow tables, introduced by Oechslin in 2003 is used by most of today’s off-the-shelf password-guessing tools. Precomputation of such tables is highly inefficient however, because much of the values computed during this task are eventually discarded. This paper revisits rainbow tables precomputation, challenging what has so far been regarded as an immutable foundation. The key idea consists in recycling values discarded during the precomputation phase, and adapting the brute force phase to make use of these recycled values. For a given memory and probability of success, the stepped rainbow tables thus created significantly reduce the workload induced by both the precomputation phase and the attack phase. The speedup obtained by using such tables is provided, and backed up by practical experiments.

Abstract Rainbow tables are techniques commonly used in computer security to invert one-way functions, for instance to crack passwords, when the domain of definition is reasonably sized. This article explores the limit on the problem size that can be treated by rainbow tables when the precomputation and the attack phases are both CPU-driven. We conclude that the bottleneck is no longer the memory as it may have been and the precomputation phase seems to have been underestimated so far. We offer a comparison of what can be done on different environments depending on the needs and available computing power of the users.

International audience

With this article, we survey the research performed in the domain of browser fingerprinting, while providing an accessible entry point to newcomers in the field. We explain how this technique works and where it stems from. We analyze the related work in detail to understand the composition of modern fingerprints and see how this technique is currently used online. We systematize existing defense solutions into different categories and detail the current challenges yet to overcome.

Smart cards are involved in most of activities, and they gather and record plenty of personal data. A manual interpretation of these raw data is difficult without specifications. This task becomes really tedious applied to plenty of devices. The paper introduces the first method to automatically retrieve textual information from memory dumps of smart cards. Given the data structure and encoding are assumed to be unknown, the method is based on text statistics and characteristics of smart cards to discard false positives. The experiments performed on more than 350 memory dumps revealed that the method can automatically retrieve more than 99% of textual information available in a dump, while keeping the false positive rate as low as 5.5%.

Distance-bounding protocols have been introduced to thwart relay attacks against contactless authentication protocols. In this context, verifiers have to authenticate the credentials of untrusted provers. Unfortunately, these protocols are themselves subject to complex threats such as terrorist-fraud attacks, in which a malicious prover helps an accomplice to authenticate. Provably guaranteeing the resistance of distance-bounding protocols to these attacks is complex. The classical solutions assume that rational provers want to protect their long-term authentication credentials, even with respect to their accomplices. Thus, terrorist-fraud resistant protocols generally rely on artificial extraction mechanisms, ensuring that an accomplice can retrieve the credential of his partnering prover, if he is able to authenticate. We propose a novel approach to obtain provable terrorist-fraud resistant protocols that does not rely on an accomplice being able to extract any long-term key. Instead, we simply assume that he can replay the information received from the prover. Thus, rational provers should refuse to cooperate with third parties if they can impersonate them freely afterwards. We introduce a generic construction for provably secure distance-bounding protocols, and give three instances of this construction: (1) an efficient symmetric-key protocol, (2) a public-key protocol protecting the identities of provers against external eavesdroppers, and finally (3) a fully anonymous protocol protecting the identities of provers even against malicious verifiers that try to profile them.

Cryptanalytic time-memory trade-offs are techniques introduced by Hellman in 1980 to speed up exhaustive searches. Oechslin improved the original version with the introduction of rainbow tables in 2003. It is worth noting that this variant is nowadays used world-wide by security experts, notably to break passwords, and a key assumption is that rainbow tables are of equal width. We demonstrate in this paper that rainbow tables are underexploited due to this assumption never being challenged. We stress that the optimal width of each rainbow table should be individually -- although not independently -- calculated. So it goes for the memory allocated to each table. We also stress that visiting sequentially the rainbow tables is no longer optimal when considering tables with heterogeneous widths.

This article introduces prudent engineering practices and offers recommendations to follow, together with typical mistakes to avoid, when designing new ultralightweight authentication protocols. This work can help, as a sanity check, designers of RFID, NFC, and sensor networks based security solutions to improve the security, reliability, and longevity of ultralightweight authentication protocol designs. Additionally, it aims to help reviewers to quickly distinguish what is really new and worthy in a research area that has been flooded lately with proposals of dubious quality.

Cryptanalytic time-memory trade-offs (TMTO) are famous tools available in any security expert toolbox. They have been used to break ciphers such as A5/1, but their efficiency to crack passwords made them even more popular in the security community. While symmetric keys are generated randomly according to a uniform distribution, passwords chosen by users are in practice far from being random, as confirmed by recent leakage of databases. Unfortunately, the technique used to build TMTOs is not appropriate to deal with non-uniform distributions. In this paper, we introduce an efficient construction that consists in partitioning the search set into subsets of close densities, and a strategy to explore the TMTOs associated to the subsets based on an interleaved traversal. This approach results in a significant improvement compared to currently used TMTOs. We experimented our approach on a classical problem, namely cracking 7-character NTLM Hash passwords using an alphabet with 34 special characters. This resulted in speedups ranging from 16 to 76 (depending on the input distribution) over rainbow tables, which are considered as the most efficient variant of time-memory trade-offs. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

After several years of research on cryptographic models for privacy in RFID systems, it appears that no universally model exists yet. Experience shows that security experts usually prefer using their own ad-hoc model than the existing ones. In particular, the impossibility of the models to refine the privacy assessment of different protocols has been highlighted in several studies. The paper emphasizes the necessity to define a new model capable of comparing protocols meaningfully. It introduces an untraceability model that is operational where the previous models are not. The model aims to be easily usable to design proofs or describe attacks. This spirit led to a modular model where adversary actions (oracles), capabilities (selectors and restrictions), and goals (experiment) follow an intuitive and practical approach. This design enhances the ability to formalize new adversarial assumptions and future evolutions of the technology, and provide a finest privacy evaluation of protocols.

Contactless technologies such as radio-frequency identification, near field communication, and sensor networks are vulnerable to mafia and distance fraud. These types of fraud are aimed at successfully passing an authentication protocol by cheating on the actual distance between the prover and the verifier. Distance-bounding protocols have been designed to cope with these security issues, but none of them properly resist these two types of fraud 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 paper introduces a noise-resilient distance-bounding protocol that resists both mafia and distance fraud. The security of the protocol is analyzed against known attacks and illustrated by experimental results. The results demonstrate the significant advantage of the introduced lightweight design over previous proposals.

The Publisher's final version can be found by following the DOI link

A distance bounding protocol enables one entity to determine an upper bound on the physical distance to the other entity as well as to authenticate the other entity. It has been actively researched during the recent years as distance-based attacks like Mafia fraud attacks become a threat in wireless environment, especially in RFID systems. Almost all distance bounding protocols deal with unilateral authentication as they consider authentication of a passive RFID tag to a reader. Recently, a distance bounding protocol providing mutual authentication has been proposed by Yum et al. asserting that it provides a lower false acceptance rate under Mafia fraud attack. However, we show in two ways that their security margins have been overestimated. First, we show that their analysis is not correct. Second, we introduce a new attack that achieves a higher false acceptance rate. Furthermore, we introduce a method that can modify existing distance bounding protocols with unilateral authentication to ones providing mutual authentication.

Authentication protocols are usually designed to face an adversary who is able to tamper with the channel, possibly with the prover, but rarely with the verifier. When considering large-scale RFID applications, e.g., mass transportation or ticketing, the last threat is no longer a fiction. A typical case is the loss or theft of a handheld reader. If the protocol is expected to be privacy-friendly, and run by offline readers, there is no solution currently to restore the privacy once the readers are compromised except renewing all the tags, which is definitely impractical.

Terrorist fraud is a relay attack against distance bounding protocols where the prover conspires with an adversary to misrepresent the distance between himself and the verifier. In ideal situations, the adversary does not gain any knowledge about the prover's long-term secret. This makes designing a distance bounding protocol resistant to a such fraud tricky: the secrets of an honest prover must be protected, while those of a dishonest one should be disclosed as an incentive not to cheat. In this paper, we demonstrate that using a secret-sharing scheme, possibly based on threshold cryptography, is well suited for thwarting terrorist fraud. Although such an idea has been around since the work of Bussard and Bagga, this is the first time that secret-sharing and terrorist fraud have been systematically studied altogether. We prove that secret sharing can counter terrorist fraud, and we detail a method that can be applied directly to most existing distance bounding protocols. We illustrate our method on the protocol of Hancke and Kuhn, yielding two variants: the threshold distance bounding (tdb) protocol and the thrifty threshold distance bounding (ttdb) protocol. We define the adversarial strategies that attempt to gain some knowledge on the prover's long-term secret, evaluate the amount of information disclosed, and determine the adversary's success probability.

Many distance bounding protocols appropriate for the RFID technology have been proposed recently. Unfortunately, they are commonly designed without any formal approach, which leads to inaccurate analyzes and unfair comparisons. Motivated by this need, we introduce a unified framework that aims to i mprove analysis and design of distance bounding protocols. Our framework includes a thorough terminology about the frauds, adversary and prover, thus disambiguating many misleading terms. It also explores the adversary's capabilities and strategies, and addresses the impact of the prover's ability to tamper with his device. It thus introduces some new concepts in the distance bounding domain as the black-box and white-box models, and the relation between the frauds with respect to these models. The relevancy and impact of the framework is finally demonstrated on a study case: Munilla–Peinado distance bounding protocol.

RFID systems suffer from different location-based attacks such as distance fraud, mafia fraud, and terrorist fraud. Among them mafia fraud is the most serious one as it can be mounted without the awareness of neither the reader nor the tag. In such an attack, the adversary acts as a man-in-the-middle who relays the signal between the two entities, possibly without knowing the specifications of the protocol used on the channel. Recently, distance bounding protocols measuring the round-trip times of messages exchanged between the reader and the tag have been designed to prevent this attack. Almost all the existing proposals are based on binary challenges, with no final signature, and provide a mafia fraud success probability equal to (3/4)n, where n is the number of rounds in the protocol, or require too much memory. In this article, we introduce new distance bounding protocols, based on binary mixed challenges, that converge toward the expected and optimal (1/2)nbound and which only require little memory.

Cryptanalytic time-memory trade-offs have been studied for 25 years and have benefited from several improvements since the original work of Hellman. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. We fill this lack by analyzing the perfect form of classic tables, distinguished point-based tables, and rainbow tables. We especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Our analysis leads to the concept of a characteristic that enables to measure the intrinsic quality of a trade-off. We finally introduce a new technique based on checkpoints that still reduces the cryptanalysis time by ruling out false alarms probabilistically. Our analysis yields the exact gain of this approach and establishes its efficiency when applied on rainbow tables.

We propose a novel authentication scheme that ensures privacy of the provers. Our scheme is based on symmetric-key cryptography, and therefore, it is well-suited to resource constrained applications in large scale environments. A typical example for such an application is an RFID system, where the provers are low-cost RFID tags, and the number of the tags can potentially be very large. We analyze the proposed scheme and show that it is superior to the well-known key-tree based approach for private authentication both in terms of privacy and efficiency.