wr0ng 2017

Welcome

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)