Suppose Alice wishes to send a message to Bob
privately over an untrusted channel. Cryptographers have worked hard on this
scenario, developing a whole range of tools, with different notions of security
and setup assumptions, between which one of the most common axioms is that
Alice has access to a trusted computer with a proper implementation of the
cryptographic protocol she wants to run. The harsh truth is that this is a
naïve assumption. The Snowden revelations show us that powerful adversaries can
and will corrupt users machines via extraordinary means, such as subverting cryptographic standards, intercepting and tampering with hardware on its
way to users or using Tailored Access Operation units.

Nevertheless, the relevance of these talks was
not just a matter of a “trending topic”, or distrust on the authoritarian and
unaccountable practices of intelligence agencies. More frequently than we would
like, presumably accidental vulnerabilities (such as Poodle, Heartbleed, etc.)
are found in popular cryptographic software, leaving the final user unprotected
even when using honest implementations. In the meantime, as Paul Kocher
remembered on his invited talk the day after, for most of our community it
passes without notice that, when we design our primitives and protocols, we
blindly rely on a mathematical model of reality that sometimes has little to do
with it.

In the same way as people from the CHES
community has become more aware –mainly also the hard way– that relying on the
wrong assumptions leads to a false confidence of the security of the deployed
systems and devices, I think those of us not that close to hardware should also
try to step back and look at how realistic are our assumptions. This includes,
as these talks addressed in different ways, starting to assume that some
standards might –and most of the systems will— be compromised at some point, and that we
understand what can still be done in those cases.

How would a Cryptography that worries not only
about prevention, but also about the whole security cycle look like? How can
the cryptography and information security communities come closer?

### Message Transmission with Reverse Firewalls— Secure Communication on Corrupted Machines

The reverse firewalls framework was recently
introduced by Mironov and Stephens-Davidowitz, with a paper that has already
been discussed in our group’s seminars and this same blog. A secure reverse
firewall is a third party that “sits between Alice and the outside world” and modifies
her sent and received messages so that even if her machine has been corrupted,
Alice’s security is still guaranteed.

Their elegant construction does not require the
users to place any additional trust on the firewall, and relies on having the
underlying cryptographic schemes to be rerandomizable.
With this threat model and rerandomization capabilities, they describe
impossibility results as well as concrete constructions.

For example, in the context of semantically
secure public-key encryption, in order to provide reverse firewalls for Bob,
the scheme must allow a third party to rerandomize a public key and map
ciphertexts under the rerandomized public key to ciphertexts under the original
public key. In the same context, Alice’s reverse firewall must be able to
rerandomize the ciphertext she sends to Bob, in such a way that
Dec(Rerand(Enc(m)))=m.

### Big-Key Symmetric Encryption: Resisting Key Exfiltration

The threat
addressed in Bellare’s talk is that of malware that aims to exfiltrate a user's
key, likely using her system’s network connection. On their work, they design a
schemes that aim to protect against this kind of

*Advanced Persistent Threats*by making secret keys so big that their undetected exfiltration by the adversary is difficult, yet making the user’s overhead almost exclusively in terms of storage instead of speed.
Their main
result is a

*subkey prediction lemma*, that gives a nice bound on an adversary’s ability to guess a modest length subkey, derived by randomly selecting bits of a big-key from which partial information has already been leaked. This approach, known as the Bounded Retrieval Model, has been –in the words of the authors—largely a theoretical area of research, whereas they show a fully concrete security analysis with good numerical bounds, constants considered.
Other
highlighted aspects of their paper were the concrete improvements over [ADW09]
and the key encapsulation technique carefully based in different security
assumptions (random oracle, standard model).

### Backdoors in Pseudorandom Number Generators: Possibility and Impossibility Results

The last talk of the session focused on the
concrete problem of backdoored Pseudorandom Number Generators (PRGs) and PRNGs
with input, which are fundamental building blocks in cryptographic protocols
that have already been successfully compromised, as we learnt when the
DUAL_EC_DRBG scandal came to light.

On their paper, the authors revisit
a previous abstraction of backdoored PRGs [DGA+15] which modeled the adversary (Big Brother) with weaker powers than it
could actually have. By giving concrete “Backdoored PRG” constructions, they
show how that model fails. Moreover, they also study robust PRNGs with input,
for which they show that Big Brother is still able to predict the values of the
PRNG state backwards, as well as giving bounds on the number of these previous
phases that it can compromise, depending on the state-size of the generator.[DGA+15] Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, and Thomas Ristenpart. A formal treatment of backdoored pseudorandom generators. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 101–126, Soﬁa, Bulgaria, April 26–30, 2015. Springer, Heidelberg, Germany.