## CryptoDB

### Chris Brzuska

#### Publications

**Year**

**Venue**

**Title**

2023

TCHES

On Provable White-Box Security in the Strong Incompressibility Model
Abstract

Incompressibility is a popular security notion for white-box cryptography and captures that a large encryption program cannot be compressed without losing functionality. Fouque, Karpman, Kirchner and Minaud (FKKM) defined strong incompressibility, where a compressed program should not even help to distinguish encryptions of two messages of equal length. Equivalently, the notion can be phrased as indistinguishability under chosen-plaintext attacks and key-leakage (LK-IND-CPA), where the leakage rate is high.In this paper, we show that LK-IND-CPA security with superlogarithmic-length leakage, and thus strong incompressibility, cannot be proven under standard (i.e. single-stage) assumptions, if the encryption scheme is key-fixing, i.e. a polynomial number of message-ciphertext pairs uniquely determine the key with high probability. Our impossibility result refutes a claim by FKKM that their big-key generation mechanism achieves strong incompressibility when combined with any PRG or any conventional encryption scheme, since the claim is not true for encryption schemes which are key-fixing (or for PRGs which are injective). In particular, we prove that the cipher block chaining (CBC) block cipher mode is key-fixing when modelling the cipher as a truly random permutation for each key. Subsequent to and inspired by our work, FKKM prove that their original big-key generation mechanism can be combined with a random oracle into an LK-IND-CPA-secure encryption scheme, circumventing the impossibility result by the use of an idealised model.Along the way, our work also helps clarifying the relations between incompressible white-box cryptography, big-key symmetric encryption, and general leakage resilient cryptography, and their limitations.

2023

ASIACRYPT

Adaptive Distributional Security for Garbling Schemes with O(|x|) Online Complexity
Abstract

Garbling schemes allow to garble a circuit C and an input x such that C(x) can be computed while hiding both C and x. In the context of adaptive security, an adversary specifies the input to the circuit after seeing the garbled circuit, so that one can pre-process the garbling of C and later only garble the input x in the online phase. Since the online phase may be time-critical, it is an interesting question how much information needs to be transmitted in this phase and ideally, this should be close to |x|. Unfortunately, Applebaum, Ishai, Kushilevitz, and Waters (AIKW, CRYPTO 2013) show that for some circuits, specifically PRGs, achieving online complexity close to |x| is impossible with simulation-based security, and Hubácek and Wichs (HW, ITCS 2015) show that online complexity of maliciously secure 2-party computation needs to grow with the incompressibility entropy of the function. We thus seek to understand under which circumstances optimal online complexity is feasible despite these strong lower bounds.
Our starting point is the observation that lower bounds (only) concern cryptographic circuits and that, when an embedded secret is not known to the adversary (distinguisher), then the lower bound techniques do not seem to apply. Our main contribution is distributional simulation-based security (DSIM), a framework for capturing weaker, yet meaningful simulation-based (adaptive) security which does not seem to suffer from impossibility results akin to AIKW. We show that DSIM can be used to prove security of a distributed symmetric encryption protocol built around garbling. We also establish a bootstrapping result from DSIM-security for NC0 circuits to DSIM-security for arbitrary polynomial-size circuits while preserving their online complexity.

2022

EUROCRYPT

On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness
📺
Abstract

Constructing one-way functions from average-case hardness is a long-standing open problem.
A positive result would exclude Pessiland (Impagliazzo '95) and establish a highly desirable win-win situation: either (symmetric) cryptography exists unconditionally, or all NP problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win-win results of the following type: either there are *fine-grained* one-way functions (FGOWF), or nontrivial speedups can be obtained for all NP problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results:
Construction. We show that if there is an NP language having a very strong form of average-case hardness, which we call *block finding hardness*, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF, and obtain two negative results:
Separation I. We provide a strong oracle separation for the implication (exponentially average-case hard languages exist => FGOWF exist).
Separation II. We provide a second strong negative result for an even weaker candidate win-win result. Namely, we rule out a black-box proof for the implication (exponentially average-case hard language *whose hardness amplifies optimally through parallel repetitions* exist => FGOWF exist). This separation forms the core technical contribution of our work.

2022

ASIACRYPT

Key-schedule Security for the TLS 1.3 Standard
📺
Abstract

Transport Layer Security (TLS) is the cryptographic backbone of secure communication on the Internet.
In its latest version 1.3, the standardization process has taken formal analysis into account both due to the importance of the protocol and the experience with conceptual attacks against previous versions. To manage the complexity of TLS (the specification exceeds 100 pages), prior
reduction-based analyses have focused on some protocol features and omitted others, e.g., included session resumption
and omitted agile algorithms or vice versa.
This article is a major step towards analysing the TLS 1.3 key establishment protocol as specified at the end of its rigorous
standardization process. Namely, we provide a full proof of the TLS key schedule, a core protocol component which produces
output keys and internal keys of the key exchange protocol. In particular, our model supports all key derivations featured in the standard, including its negotiated modes and algorithms that combine an optional Diffie-Hellman exchange for forward secrecy with optional pre-shared keys supplied by the application or recursively established in prior sessions.
Technically, we rely on state-separating proofs (Asiacrypt '18) and introduce techniques to model
large and complex derivation graphs. Our key schedule analysis techniques have been used subsequently %by Brzuska, Cornelissen and Kohbrok
to analyse the key schedule of Draft 11 of the MLS protocol (S&P'22) and to propose improvements.

2021

TCC

On Derandomizing Yao’s Weak-to-Strong OWF Construction
📺
Abstract

The celebrated result of Yao (Yao, FOCS'82) shows that concatenating n · p(n) copies of a weak one-way function f which can be inverted with probability 1 - 1/p(n) suffices to construct a strong one-way function g, showing that weak and strong one-way functions are black-box equivalent. This direct product theorem for hardness amplification of one-way functions has been very influential. However, the construction of Yao has severe efficiency limitations; in particular, it is not security-preserving (the input to g needs to be much larger than the input to f). Understanding whether this is inherent is an intriguing and long-standing open question.
In this work, we explore necessary features of constructions which achieve short input length by proving the following: for any direct product construction of strong OWF g from a weak OWF f, which can be inverted with probability 1-1/p(n), the input size of g must grow as Omega(p(n)). By direct product construction, we refer to any construction with the following structure: the construction g executes some arbitrary pre-processing function (independent of f) on its input, obtaining a vector (y_1 ,··· ,y_l ), and outputs f(y_1),··· ,f(y_l). Note that Yao's construction is obtained by setting the pre-processing to be the identity. Our result generalizes to functions g with post-processing, as long as the post-processing function is not too lossy. Thus, in essence, any weak-to-strong hardness amplification must either (1) be very far from security-preserving, (2) use adaptivity, or (3) must be very far from a direct-product structure (in the sense of having a very lossy post-processing of the outputs of f).
On a technical level, we use ideas from lower bounds for secret-sharing to prove the impossibility of derandomizing Yao in a black-box way. Our results are in line with Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (FOCS 1990) who derandomize Yao's construction for regular weak one-way functions by evaluating the OWF along a random walk on an expander graph---the construction is adaptive, since it alternates steps on the expander graph with evaluations of the weak one-way function.

2020

TCHES

On the Security Goals of White-Box Cryptography
📺
Abstract

We discuss existing and new security notions for white-box cryptography and comment on their suitability for Digital Rights Management and Mobile Payment Applications, the two prevalent use-cases of white-box cryptography. In particular, we put forward indistinguishability for white-box cryptography with hardware-binding (IND-WHW) as a new security notion that we deem central. We also discuss the security property of application-binding and explain the issues faced when defining it as a formal security notion. Based on our proposed notion for hardware-binding, we describe a possible white-box competition setup which assesses white-box implementations w.r.t. hardware-binding. Our proposed competition setup allows us to capture hardware-binding in a practically meaningful way.While some symmetric encryption schemes have been proven to admit plain white-box implementations, we show that not all secure symmetric encryption schemes are white-boxeable in the plain white-box attack scenario, i.e., without hardware-binding. Thus, even strong assumptions such as indistinguishability obfuscation cannot be used to provide secure white-box implementations for arbitrary ciphers. Perhaps surprisingly, our impossibility result does not carry over to the hardware-bound scenario. In particular, Alpirez Bock, Brzuska, Fischlin, Janson and Michiels (ePrint 2019/1014) proved a rather general feasibility result in the hardware-bound model. Equally important, the apparent theoretical distinction between the plain white-box model and the hardware-bound white-box model also translates into practically reduced attack capabilities as we explain in this paper.

2020

ASIACRYPT

Security Reductions for White-Box Key-Storage in Mobile Payments
📺
Abstract

The goal of white-box cryptography is to provide security even when the cryptographic implementation is executed in adversarially controlled environments. White-box implementations nowadays appear in commercial products such as mobile payment applications, e.g., those certified by Mastercard. Interestingly, there, white-box cryptography is championed as a tool for secure storage of payment tokens, and importantly, the white-boxed storage functionality is bound to a hardware functionality to prevent code-lifting attacks.
In this paper, we show that the approach of using hardware-binding and obfuscation for secure storage is conceptually sound. Following security specifications by Mastercard and also EMVCo, we first define security for a white-box key derivation functions (WKDF) that is bound to a hardware functionality. WKDFs with hardware-binding model a secure storage functionality, as the WKDFs in turn can be used to derive encryption keys for secure storage. We then provide a proof-of-concept construction of WKDFs based on pseudorandom functions (PRF) and obfuscation. To show that our use of cryptographic primitives is sound, we perform a cryptographic analysis and reduce the security of our WKDF to the cryptographic assumptions of indistinguishability obfuscation and PRF-security. The hardware-functionality that our WKDF is bound to is a PRF-like functionality. Obfuscation helps us to hide the secret key used for the verification, essentially emulating a signature functionality as is provided by the Android key store.
We rigorously define the required security properties of a hardware-bound white-box payment application (WPAY) for generating and encrypting valid payment requests. We construct a WPAY, which uses a WKDF as a secure building block. We thereby show that a WKDF can be securely combined with any secure symmetric encryption scheme, including those based on standard ciphers such as AES.

2019

JOFC

White-Box Cryptography: Don’t Forget About Grey-Box Attacks
Abstract

Despite the fact that all current scientific white-box approaches of standardized cryptographic primitives have been publicly broken, these attacks require knowledge of the internal data representation used by the implementation. In practice, the level of implementation knowledge required is only attainable through significant reverse-engineering efforts. In this paper, we describe new approaches to assess the security of white-box implementations which require neither knowledge about the look-up tables used nor expensive reverse-engineering efforts. We introduce the differential computation analysis (DCA) attack which is the software counterpart of the differential power analysis attack as applied by the cryptographic hardware community. Similarly, the differential fault analysis (DFA) attack is the software counterpart of fault injection attacks on cryptographic hardware. For DCA, we developed plugins to widely available dynamic binary instrumentation (DBI) frameworks to produce software execution traces which contain information about the memory addresses being accessed. For the DFA attack, we developed modified emulators and plugins for DBI frameworks that allow injecting faults at selected moments within the execution of the encryption or decryption process as well as a framework to automate static fault injection. To illustrate the effectiveness, we show how DCA and DFA can extract the secret key from numerous publicly available non-commercial white-box implementations of standardized cryptographic algorithms. These approaches allow one to extract the secret key material from white-box implementations significantly faster and without specific knowledge of the white-box design in an automated or semi-automated manner.

2018

ASIACRYPT

State Separation for Code-Based Game-Playing Proofs
Abstract

The security analysis of real-world protocols involves reduction steps that are conceptually simple but still have to account for many protocol complications found in standards and implementations. Taking inspiration from universal composability, abstract cryptography, process algebras, and type-based verification frameworks, we propose a method to simplify large reductions, avoid mistakes in carrying them out, and obtain concise security statements.Our method decomposes monolithic games into collections of stateful packages representing collections of oracles that call one another using well-defined interfaces. Every component scheme yields a pair of a real and an ideal package. In security proofs, we then successively replace each real package with its ideal counterpart, treating the other packages as the reduction. We build this reduction by applying a number of algebraic operations on packages justified by their state separation. Our method handles reductions that emulate the game perfectly, and leaves more complex arguments to existing game-based proof techniques such as the code-based analysis suggested by Bellare and Rogaway. It also facilitates computer-aided proofs, inasmuch as the perfect reductions steps can be automatically discharged by proof assistants.We illustrate our method on two generic composition proofs: a proof of self-composition using a hybrid argument; and the composition of keying and keyed components. For concreteness, we apply them to the KEM-DEM proof of hybrid-encryption by Cramer and Shoup and to the composition of forward-secure game-based key exchange protocols with symmetric-key protocols.

2016

EUROCRYPT

2014

CRYPTO

2014

ASIACRYPT

#### Program Committees

- Eurocrypt 2023
- Crypto 2023
- TCC 2023
- PKC 2022
- CHES 2022
- CHES 2021
- TCC 2021
- PKC 2020
- TCC 2020
- PKC 2019
- TCC 2019
- Crypto 2018
- PKC 2018
- Eurocrypt 2018
- Asiacrypt 2018
- Eurocrypt 2017
- Asiacrypt 2017
- TCC 2016
- Eurocrypt 2016

#### Coauthors

- Alessandro Amadori (1)
- Paul Baecher (2)
- Estuardo Alpirez Bock (5)
- Andrej Bogdanov (1)
- Joppe W. Bos (1)
- Zvika Brakerski (1)
- Geoffroy Couteau (2)
- Antoine Delignat-Lavaud (2)
- Christoph Egger (1)
- Pooya Farshim (2)
- Marc Fischlin (5)
- Nils Fleischhacker (1)
- Cédric Fournet (2)
- Tobias Freudenreich (1)
- Eloi Sanfelix Gonzalez (1)
- Charles Hubain (1)
- Håkon Jacobsen (2)
- Christian Janson (1)
- Pihla Karanko (2)
- Stefan Katzenbeisser (1)
- Konrad Kohbrok (2)
- Markulf Kohlweiss (2)
- Russell W. F. Lai (1)
- Anja Lehmann (2)
- Wil Michiels (3)
- Arno Mittelbach (5)
- Cristofaro Mune (1)
- Sabine Oechsner (1)
- Kirthivaasan Puniamurthy (1)
- Marcus Page (1)
- Felix Rohrbach (1)
- Jakob Schelbert (1)
- Heike Schröder (1)
- Dominique Schröder (2)
- Douglas Stebila (1)
- Philippe Teuwen (1)
- Alexander Treff (1)
- Florian Volk (1)