wr0ng 2017

Random Number Generation Done Right

April 2017, Paris, France

wr0ng 2017 is a one-day Ecrypt-CSA workshop organized by CryptoExperts and affiliated to EUROCRYPT 2017. It will take place in Paris, France, on 30 April 2017.

Workshop focus

All cryptographic constructions heavily rely on the availability of random bits, for operations such as key generation, randomization of encryption or signatures and or nonces in protocols. Unfortunately, multiple incidents have demonstrated that the quality of the (pseudo-)random number generators leaves much to be desired. Even worse, in September 2013 it was revealed that the US government agency has deliberately undermined the security of cryptographic solutions by inserting a backdoor in the Dual EC random number generator included in ANSI, NIST and ISO standards. This highlights that a secure system can be fatally weakened by the insertion of just one flawed component; if the NSA can predict all randomness used by a system, it knows all secrets used during that time period and might even be able to recover long-term keys.

In spite of their crucial importance, there are very few research papers on the topic and most industrial designs are proprietary. Moreover, existing designs and instances are notoriously difficult to evaluate.

The goal of this workshop is to review new models, constructions, implementations, and evaluation methodologies. It will also be explored whether the area is mature enough to identify requirements and plan an open competition. The workshop will cover both truly random number generators and pseudo-random number generators.

Organized by

This workshop is part of the EU Horizon 2020 ECRYPT-CSA project.

Registration is mandatory.




Registration will start at 8:50.


Session 1: Why does strong randomness matter? (1h30)

  • 09:00 – Random Number Generator Done Wrong

    Nadia Heninger

    Randomness is essential to cryptography: cryptographic security depends on private keys that are unpredictable to an attacker. But how good are the random number generators that are actually used in practice? In this talk, I will discuss several large-scale surveys of cryptographic deployments, including TLS, SSH, Bitcoin, and smart cards, and show that random number generation flaws are surprisingly widespread. We will see how many of the most commonly used public key encryption and signature schemes, including RSA, DSA, and ECDSA are brittle if used with faulty random number generators and can fail catastrophically to an external attacker. We trace many of the the random number generation flaws we encountered to specific implementations and vulnerable implementation patterns. I will also discuss followup work showing that, distressingly, many hosts with random number generation flaws remain unpatched years after public disclosure.
    This talk surveys several joint projects with a very large number of collaborators.

  • 09:45 – Malleability of the Blockchain's Entropy

    Cécile Pierrot

    Trustworthy generation of public random numbers is necessary for the security of many cryptographic applications. It was suggested to use the inherent unpredictability of blockchains as a source of public randomness. Entropy from the Bitcoin blockchain in particular has been used in lotteries and has been suggested for a number of other applications ranging from smart contracts to election auditing. In this talk, we analyse this idea and show how an adversary could manipulate these random numbers, even with limited computational power and financial budget.
    A short introduction to public random number generation will be provided, as well as a quick refresher on Bitcoin, so that you need almost no background to follow this talk.
    It is a joint work with Benjamin Wesolowski, EPFL.

Coffee Break (30 min)

Session 2: Backdoors in random number generation (1h30)

  • 11:00 – Backdoors in PRGs and PRNGs

    Kenneth Paterson

    Inspired by the Dual_EC_DBRG incident, Dodis et al. (Eurocrypt 2015) and Degabriele et al. (Crypto 2016) have recently given formal models, security definitions and constructions for backdoored PRGs and PRNGs with input. I'll introduce these results and explain what they tell us about the limits and opportunities for inserting backdoors into these primitives.

  • 11:45 – False Backdoors in Historical Symmetric Ciphers

    Nicolas Courtois

    In spite of the existence of several provably secure encryption systems and RNGs, practical systems frequently use block and stream cipher based PRNGs which are typically OK if ... and potentially insecure if... In this talk we will review some ways in which several known cipher and RNG systems were very substantially weakened for NO APPARENT reason and which properties are very hard to justify in a reasonable way. We call these false backdoors because they are not really hidden, they are rather apparent and become visible if we study the system seriously. Secondly, these properties could be accidental, hence "false" backdoors. Finally there is also a third major reason to call them "false backdoors": for many of them there is NOT yet a truly convincing or a truly devastating attack. We are a bit disappointed, and we are going to discuss some interesting open problems. Most ciphers we study are quite old e.g. T-310, or they are low-cost industrial ciphers such as KeeLoq or CRYPTO-1.

Lunch (1h30)

Session 3: True random number generation and entropy evaluation (1h30)

  • 14:00 – Design of Secure TRNGs for Cryptography - Past, Present, and Future

    Viktor Fischer

    The main objective of the talk is to show evolution and recent advances in random number generator (RNG) design. Starting with a short analysis of the old RNG designs and design constraints, we will discuss the contemporary RNG design based on the use of stochastic models and dedicated tests, and draw briefly future design strategies, which will guarantee higher security levels for random number generation in hardware.

  • 14:45 – Evaluating Entropy for True Random Number Generators

    Maciej Skorski

    True Random Number Generators are devices that extract randomness from physical processes, such as radioactive decay, atmospheric noise or noise in MEMS sensors. Since the output quality depends on the entropy provided by the source, evaluating entropy is of critical importance to the design of TRNGs.
    In this talk I will overview various techniques proposed so far, focusing on provable security. In particular, I will address the following issues

    • what are "right" and "wrong" entropy notions to be used,
    • how the estimation is impacted by the statistical model of the source (i.i.d blocks, general Markov chains),
    • on-line versus off-line entropy evaluation.
    I will also discuss how advances in other areas (including streaming algorithms, key derivation) can be combined to improve the evaluation performance upon existing approaches, and illustrate this for certain settings discussed in the applied literature.

Coffee Break (30 min)

Session 4: Constructions for deterministic and hybrid random number generation (1h30)

  • 16:00 – Security of Pseudo-Random Number Generators With Input

    Damien Vergnaud

    A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNG with input was proposed in 2005 by Barak and Halevi. This model involves an internal state that is refreshed with a (potentially biased) external random source, and a cryptographic function that outputs random numbers from the internal state. In this talk, we will discuss the Barak-Halevi model and its extension proposed in 2013 by Dodis, Pointcheval, Ruhault, Wichs and Vergnaud to include a new security property capturing how a PRNG should accumulate the entropy of the input data into the internal state. We will present analysis of the security of real-life PRNGs in this model and present efficient constructions that achieve provable security.

  • 16:45 – Provably-robust Sponge-based PRNGs

    Stefano Tessaro

    Many recent works have focused on establishing formal frameworks to prove the security of PRNG designs based on cryptographic primitives. Recent constructions of permutation-based PRNGs (following in particular the sponge paradigm by Bertoni et al, as used e.g. in SHA-3) appear to offer both simplicity and efficiency. However, evaluating their security in strong formal models (allowing to prove, e.g., forward security) turns out to be a challenging technical question.
    In this talk, I will give an overview of sponge-based PRNGs, and discuss what we know about their provable security. I will also present a few open questions in this domain.
    Based on joint work with Peter Gazi.

Concluding discussions (30 min)


Workshop Will Be Held At

UPMC Jussieu Campus

Paris, France.

(10 min from Eurocrypt's venue)