International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Chris Brzuska

Publications

Year
Venue
Title
2023
TCHES
On Provable White-Box Security in the Strong Incompressibility Model
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
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 📺
Chris Brzuska Geoffroy Couteau
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 📺
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 📺
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 📺
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 📺
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
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
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.
2017
PKC
2016
EUROCRYPT
2016
CRYPTO
2015
TCC
2015
TCC
2014
CRYPTO
2014
ASIACRYPT
2014
ASIACRYPT
2013
ASIACRYPT
2013
ASIACRYPT
2011
CRYPTO
2010
PKC
2009
PKC

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