International Association
for Cryptologic Research

Time is an important component of the Domain Name System (DNS) and the DNS Security Extensions (DNSSEC). DNS caches rely on an absolute notion of time (eg "August 8, 2018 at 11:59pm'') to determine how long DNS records can be cached (i.e their Time To Live (TTL)) and to determine the validity interval of DNSSEC signatures. This is especially interesting for two reasons. First, absolute time is set from external sources, and is thus vulnerable to a variety of network attacks that maliciously alter time. Meanwhile, relative time (e.g. "2 hours from the time the DNS query was sent'') can be set using sources internal to the operating system, and is thus not vulnerable to network attacks. Second, the DNS on-the-wire protocol only uses relative time; relative time is then translated into absolute time as a part of DNS caching, which introduces vulnerabilities.

We leverage these two observations to show how to pivot from network attacks on absolute time to attacks on DNS caching. Specifically, we present and discuss the implications of attacks that (1) expire the cache earlier than intended and (2) make the cached responses stick in the cache longer than intended. We use network measurements to identify a significant attack surface for these DNS cache attacks, focusing specifically on pivots from Network Time Protocol (NTP) attacks by both on-path and off-path attackers. We therefore recommend that DNS resolvers stop using absolute time for caching, and instead start using relative time. We have implemented our recommendations as part of the popular Unbound open source resolver, and our implementation will be part of Unbound's upcoming release.

We present in this paper an efficient implementation of the code-based cryptosystem ROLLO, a candidate to the NIST PQC project, on a device available on the market. This implementation benefits of the existing hardware by using crypto co-processor for ECC contained in a microcontroller to speed-up operations in $\mathbb{F}_{2^m}$. Optimizations are then made on operations in $\mathbb{F}_{2^m}^n$. Finally, the cryptosystem outperforms the public key exchange protocol ECDH for a security level of 192 bits showing then the possibility of the integration of this new cryptosystem in current chips. According to our implementation, the CPA-secure ROLLO-I-128 submission takes 173,6 ms for key generation, 12 ms for encapsulation and 79.4 ms for decapsulation on an embedded system including featured with a Cortex M3 core running at 50 MHz.

The number of electric vehicles (EVs) is steadily growing. This provides a promising opportunity for balancing the smart grid of the future, because vehicle-to-grid (V2G) systems can utilize the batteries of plugged-in EVs as much needed distributed energy storage: In times of high production and low demand the excess energy in the grid is stored in the EVs’ batteries, while peaks in demand are mitigated by EVs feeding electricity back to the grid. But the data needed for managing individual V2G charging sessions as well as for billing and rewards is of a highly personal and therefore sensitive nature. This causes V2G systems to pose a significant threat to the privacy of their users. Existing cryptographic protocols for this scenario either do not offer adequate privacy protection or fail to provide key features necessary to obtain a practical system. Based on the recent cryptographic toll collection framework P4TC, this work introduces a privacy-preserving but efficient V2G payment and reward system called P6V2G. Our system facilitates two-way transactions in a semi online and post-payment setting. It provides double-spending detection, an integrated reputation system, contingency traceability and blacklisting features, and is portable between EVs. The aforementioned properties are holistically captured within an established cryptographic security framework. In contrast to existing protocols, this formal model of a V2G payment and reward system allows us to assert all properties through a comprehensive formal proof.

In recent years, several cryptographic scholars have proposed quantum blind signature schemes. However, their methods require the signatories and the inspectors to share common keys in advance, which makes them not only complicated in concept, but also suffering deniable problem. Moreover, due to the fact that not everyone can verify the blind signature, it needs to have a designated verifier. In view of Laurent, et al.’s argument that other than the assumption of the pre-image being collision-free, the one-way hash function is an attractive cryptographic component in the post-quantum era when designing a cryptosystem. Inspired by this, we propose a publicly verifiable quantum blind signature scheme based on the hash function. After security analyses, we confirm that our quantum blind signature not only is secure, but also have the needed properties. It includes anonymity, unforgeability, non-repudiation, blindness, public verifiability, and traceability. Hence, we conclude that this approach is better than the state-of-the-art, and is therefore more suitable for applications in real life, such as, mobile payments, quantum voting, or quantum government.

Traditional Certificate-based public key infrastructure (PKI) suffers from the problem of certificate overhead like its storage, verification, revocation etc. To overcome these problems, the idea of certificate less identity-based public key cryptography (ID-PKC) was proposed by Shamir. This is suitable for closed trusted group only. Also, this concept has some inherent problems like key escrow problem, secure key channel problem, identity management overhead etc. Later on, there had been several works which tried to combine both the cryptographic techniques such that the resulting hybrid PKI framework is built upon the best features of both the cryptographic techniques. It had been shown that this approach solves many problems associated with an individual cryptosystem. In this paper, we have reviewed and compared such hybrid schemes which tried to combine both the certificate based PKC and ID-based PKC. Also, the summary of the comparison, based on various features, is presented in a table.

Event date: 15 December to 18 December 2019
Submission deadline: 20 August 2019
Notification: 20 September 2019

Event date: 25 February to 27 February 2020
Submission deadline: 4 October 2019
Notification: 20 December 2019

One challenge of the CHES 2018 side channel contest was to break a masked AES implementation. It was impressively won by Gohr et al. by applying ridge regression to obtain guesses for the hamming weights of the (unmasked) AES key schedule, and then using a SAT solver to brute force search the remaining key space. Template attacks are one of the most common approaches used to assess the leakage of a device in a security evaluation. Hence, this raises the question whether ridge regression is a more suitable choice for security evaluation, especially w.r.t. portability. We investigate the feasibility of template attacks to break the presented AES implementation, analyze the leakage of the device, and based on this mount a template attack on hamming weights of the key expansion. We then use classical key search algorithms to recover the AES key. By analyzing the leakage and applying dimension reduction techniques we are able to compress each trace from 650 000 points to only 30 points that are then used to create the templates. Our experimental results indicate that such classical templates achieve similar results compared to ridge regression, and in several cases even slightly outperforming it. According to the organizers, the CTF was aimed to evaluate the concepts of deep learning and classic profiling. Our final conclusion is that the challenge traces are not optimal to settle the question intended, as the leakage is very strong and local. Therefore it is very suitable to apply classical machine learning techniques such as template attacks or ridge regression, and the difficulty in recovering the key is more linked to the resulting key search problem than to the actual attack.

Elliptic bases, introduced by Couveignes and Lercier in 2009, give an elegant way of representing finite field extensions. A natural question which seems to have been considered independently by several groups is to use this representation as a starting point for small characteristic finite field discrete logarithm algorithms. This idea has been recently proposed by two groups working on it, in order to achieve provable quasi-polynomial time for discrete logarithms in small characteristic finite fields.

In this paper, we don’t try to achieve a provable algorithm but, instead, investigate the practicality of heuristic algorithms based on elliptic bases. Our key idea, is to use a different model of the elliptic curve used for the elliptic basis that allows for a relatively simple adaptation of the techniques used with former Frobenius representation algorithms. We haven’t performed any record computation with this new method but our experiments with the field GF(3^1345) indicate that switching to elliptic representations might be possible with performances comparable to the current best practical methods.

This works studies the use of the AES block-cipher for Picnic-style signatures, which work in the multiparty-computation-in-the-head model. It applies advancements to arithmetic circuits for the computation of the AES S-box over multiparty computation in the preprocessing model to obtain an improvement of signature sizes of 40\% on average compared to using binary circuits for AES-128, AES-192 and AES-256 in combination with previous techniques. This work also discusses other methods for the computation of the S-box and provides insights into the reaches and limits of the multiparty-computation-in-the-head paradigm.

Dwork and Naor (FOCS'00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives.

However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

The standard definition of security for digital signatures---existential unforgeability---does not ensure certain properties that protocol designers might expect. For example, in many modern signature schemes, one signature may verify against multiple distinct public keys. It is left to protocol designers to ensure that the absence of these properties does not lead to attacks.

Modern automated protocol analysis tools are able to provably exclude large classes of attacks on complex real-world protocols such as TLS 1.3 and 5G. However, their abstraction of signatures (implicitly) assumes much more than existential unforgeability, thereby missing several classes of practical attacks.

We give a hierarchy of new formal models for signature schemes that captures these subtleties, and thereby allows us to analyse (often unexpected) behaviours of real-world protocols that were previously out of reach of symbolic analysis. We implement our models in the Tamarin Prover, yielding the first way to perform these analyses automatically, and validate them on several case studies. In the process, we find new attacks on DRKey and SOAP's WS-Security, both protocols which were previously proven secure in traditional symbolic models.

The high latency and low throughput of blockchain protocols constitute one of the fundamental barriers for their wider adoption.Overlay protocols, notably the lightning network, have been touted asthe most viable direction for rectifying this in practice. In this work wepresent for the first time a full formalisation and security analysis ofthe lightning network in the (global) universal composition setting thattakes into account a global ledger functionality for which previous work[Badertscher et al., Crypto’17] has demonstrated its realisability by theBitcoin blockchain protocol. As a result, our treatment delineates exactlyhow the security guarantees of the protocol depend on the properties ofthe underlying ledger. Moreover, we provide a complete and modulardescription of the core of the lightning protocol that highlights preciselyits dependency to underlying basic cryptographic primitives such as digital signatures, pseudorandom functions, identity-based signatures anda less common two-party primitive, which we term a combined digitalsignature, that were originally hidden within the lightning protocol’s implementation.

Kerberos is one of the earliest network security protocols, providing authentication between clients and servers with the assistance of trusted servers. It remains widely used, notably as the default authentication protocol in Microsoft Active Directory (thus shipped with every major operating system), and is the ancestor of modern single sign-on protocols like OAuth and OpenID Connect.

There have been many analyses of Kerberos in the symbolic (Dolev--Yao) model, which is more amenable to computer-aided verification tools than the computational model, but also idealizes messages and cryptographic primitives more. Reduction-based proofs in the computational model can provide assurance against a richer class of adversaries, and proofs with concrete probability analyses help in picking security parameters, but Kerberos has had no such analyses to date.

We give a reduction-based security proof of Kerberos authentication and key establishment, focusing on the mandatory 3-party mode. We show that it is a secure authentication protocol under standard assumptions on its encryption scheme; our results can be lifted to apply to quantum adversaries as well.

As has been the case for other real-world authenticated key exchange (AKE) protocols, the standard AKE security notion of session key indistinguishability cannot be proven for Kerberos since the session key is used in the protocol itself, breaking indistinguishability. We provide two positive results despite this: we show that the standardized but optional sub-session mode of Kerberos does yield secure session keys, and that the hash of the main session key is also a secure session key under Krawczyk's generalization of the authenticated and confidential channel establishment (ACCE) model.

Event date: 15 December to 17 December 2019
Submission deadline: 10 September 2019

Event date: 9 December to 12 December 2019
Submission deadline: 14 July 2019
Notification: 15 September 2019

We present a new efficient protocol for computing private set union (PSU). Here two semi-honest parties, each holding a dataset of known size (or of a known upper bound), wish to compute the union of their sets without revealing anything else to either party. Our protocol is in the OT hybrid model. Beyond OT extension, it is fully based on symmetric-key primitives. We motivate the PSU primitive by its direct application to network security and other areas.

At the technical core of our PSU construction is the reverse private membership test RPMT protocol. In RPMT, the sender with input $x^*$ interacts with a receiver holding a set $X$. As a result, the receiver learns (only) the bit indicating whether $x^*$ is in $X$, while the sender learns nothing about the set $X$. (Previous similar protocols provide output to the opposite party, hence the term "reverse'' private membership.) We believe our RPMT abstraction and constructions may be a building block in other applications as well.

We demonstrate the practicality of our proposed protocol with an implementation. For input sets of size $2^{20}$ and using a single thread, our protocol requires 238 seconds to securely compute the set union, regardless of the bit length of the items. Our protocol is amenable to parallelization. Increasing the number of threads from 1 to 32, our protocol requires only 13.1 seconds, a factor of $18.25 \times$ improvement.

To the best of our knowledge, ours is the first protocol that reports on large-size experiments, makes code available, and avoids extensive use of computationally expensive public-key operations. (No PSU code is publicly available for prior work, and the only prior symmetric-key-based work reports on small experiments and focuses on the simpler 3-party, 1-corruption setting.)Our work improves reported PSU state of the art by factor up to $7,600\times$ for large instances.

The feasibility of bribing attacks on cryptocurrencies was first highlighted in 2016, with various new techniques and approaches having since been proposed. Recent reports of real world $ 51\% $ attacks on smaller cryptocurrencies underline the realistic threat bribing attacks present, in particular to permissionless cryptocurrencies. In this paper, bribing attacks and similar techniques, which we refer to as incentive attacks, are systematically analyzed and categorized.Thereby, we show that the problem space is not fully explored and present several new and improved incentive attacks. We identify no- and near-fork incentive attacks as a powerful, yet largely overlooked, category. In particular transaction ordering and exclusion attacks raise serious security concerns for stateful cryptocurrencies, such as smart contract platforms. Further, we propose the first trustless out-of-band bribing attack capable of facilitating double-spend collusion across different blockchains that reimburses collaborators in case of failure. Our attack is hereby rendered between $ 85 \% $ and $ 95 \% $ cheaper than comparable bribing techniques (e.g., the whale attack). We implement the basic building blocks of all our out-of-band attacks as Ethereum smart contracts to demonstrate their feasibility.

Consider the representative task of designing a distributed coin-tossing protocol for $n$ processors such that the probability of heads is $X_0\in[0,1]$, and an adversary can reset one processor to change the distribution of the final outcome. For $X_0=1/2$, in the non-cryptographic setting, no adversary can deviate the probability of the outcome of the well-known Blum's ``majority protocol'' by more than $\frac1{\sqrt{2\pi n}}$, i.e., it is $\frac1{\sqrt{2\pi n}}$ insecure. For computationally bounded adversaries and any $X_0\in[0,1]$, the protocol of Moran, Naor, and Segev (2009) is only $O\left(\frac1n\right)$ insecure.

In this paper, we study discrete-time martingales $(X_0,X_1,\dotsc,X_n)$ such that $X_i\in[0,1]$, for all $i\in\{0,\dotsc,n\}$, and $X_n\in \{0,1\}$. These martingales are commonplace in modeling stochastic processes like coin-tossing protocols in the non-cryptographic setting mentioned above. In particular, for any $X_0\in[0,1]$, we construct martingales that yield $\frac12\sqrt{\frac{X_0(1-X_0)}{n}}$ insecure coin-tossing protocols with $n$-bit communication; irrespective of the number of bits required to represent the output distribution. Note that for sufficiently small $X_0$, we achieve higher security than Moran et al.'s protocol even against computationally unbounded adversaries. For $X_0=1/2$, our protocol requires only 40 percent of the processors to achieve the same security as the majority protocol.

The technical heart of our paper is a new inductive technique that uses geometric transformations to precisely account for the large gaps in these martingales. For any $X_0\in[0,1]$, we show that there exists a stopping time $\tau$ such that $$E\left[{|{X_\tau-X_{\tau-1}}|}\right]\geq \frac2{\sqrt{2n-1}}\cdot X_0(1-X_0)$$ The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, \ie, a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that any stopping time $\tau$ has $$E\left[{|{X_\tau-X_{\tau-1}}|}\right]\leq \frac1{\sqrt{n}}\cdot \sqrt{X_0(1-X_0)}$$

Our lower-bound holds for all $X_0\in[0,1]$; while the previous bound of Cleve and Impagliazzo (1993) exists only for positive constant $X_0$. Conceptually, our approach only employs elementary techniques to analyze these martingales and entirely circumvents the complex probabilistic tools inherent to the approaches of Cleve and Impagliazzo (1993) and Beimel, Haitner, Makriyannis, and Omri (2018).

By appropriately restricting the set of possible stopping-times, we present representative applications to constructing distributed coin-tossing/dice-rolling protocols, discrete control processes, fail-stop attacking coin-tossing/dice-rolling protocols, and black-box separations.

In this paper we present a practical protocol for secure ridge regression. We develop the necessary secure linear algebra tools, using only basic arithmetic over prime fields. In particular, we will show how to solve linear systems of equations and compute matrix inverses efficiently, using appropriate secure random self-reductions of these problems. The distinguishing feature of our approach is that the use of secure fixed-point arithmetic is avoided entirely, while circumventing the need for rational reconstruction at any stage as well.

We demonstrate the potential of our protocol in a standard setting for information-theoretically secure multiparty computation, tolerating a dishonest minority of passively corrupt parties. Using the MPyC framework, which is based on threshold secret sharing over finite fields, we show how to handle large datasets efficiently, achieving practically the same root-mean-square errors as Scikit-learn. Moreover, we do not assume that any (part) of the datasets is held privately by any of the parties, which makes our protocol much more versatile than existing solutions.