Redactable Blockchain in the Permissionless Setting

Conference paper
Dominic Deuber, Bernardo Magri and Sri Aravinda Krishnan Thyagarajan
40th IEEE Symposium on Security and Privacy (IEEE S&P 2019)
Publication year: 2019

Bitcoin is an immutable permissionless blockchain system that has been extensively used as a public bulletin board by many different applications that heavily relies on its immutability. However, Bitcoin’s immutability is not without its fair share of demerits. Interpol exposed the existence of harmful and potentially illegal documents, images and links in the Bitcoin blockchain, and since then there have been several qualitative and quantitative analysis on the types of data currently residing in the Bitcoin blockchain.
Although there is a lot of attention on blockchains, surprisingly the previous solutions proposed for data redaction in the permissionless setting are far from feasible, and require additional trust assumptions. Hence, the problem of harmful data still poses a huge challenge for law enforcement agencies like Interpol (Tziakouris, IEEE S&P’18).

We propose the first efficient redactable blockchain for the permissionless setting that is easily integrable into Bitcoin, and that does not rely on heavy cryptographic tools or trust assumptions. Our protocol uses a consensus-based voting and is parameterised by a policy that dictates the requirements and constraints for the redactions; if a redaction gathers enough votes the operation is performed on the chain. As an extra feature, our protocol offers public verifiability and accountability for the redacted chain. Moreover, we provide formal security definitions and proofs showing that our protocol is secure against redactions that were not agreed by consensus. Additionally, we show the viability of our approach with a proof-of-concept implementation that shows only a tiny overhead in the chain validation of our protocol when compared to an immutable one.

Public Immunization against Complete Subversion without Random Oracles

Conference paper
Giuseppe Ateniese, Danilo Francati, Bernardo Magri amd Daniele Venturi
ACNS '19
Publication year: 2019

We seek constructions of general-purpose immunizers that take arbitrary cryptographic primitives, and transform them into ones that withstand a powerful “malicious but proud” adversary, who attempts to break security by possibly subverting the implementation of all algorithms (including the immunizer itself!), while trying not to be detected. This question is motivated by the recent evidence of cryptographic schemes being intentionally weakened, or designed together with hidden backdoors, e.g. with the scope of mass surveillance.

Our main result is a subversion-secure immunizer in the plain model (assuming collision-resistant hashing), that works for a fairly large class of deterministic primitives, i.e. cryptoschemes where a secret (but  tamperable) random source is used to generate the keys and the public parameters, whereas all other algorithms are deterministic. The immunizer relies on an additional independent source of public randomness, which is used to sample a public seed. While the public source is untamperable, the subversion of all other algorithms is allowed to depend on it.

Previous work in the area only obtained subversion-secure immunization for very restricted classes of primitives, often in weaker models of subversion and relying on random oracles, or by leveraging a higher number of independent random sources.

Secure Outsourcing of Cryptographic Circuits Manufacturing

Conference paper
Giuseppe Ateniese, Aggelos Kiayias, Bernardo Magri, Yiannis Tselekounis and Daniele Venturi
The 12th International Conference on Provable Security (ProvSec 2018)
Publication year: 2018

The fabrication process of integrated circuits (ICs) is complex and requires the use of off-shore foundries to lower the costs and to have access to leading-edge manufacturing facilities. Such an outsourcing trend leaves the possibility of inserting malicious circuitry (a.k.a. hardware Trojans) during the fabrication process, causing serious security issues. Hardware Trojans are very hard and expensive to detect and can disrupt the entire circuit or covertly leak sensitive information. In this paper, we propose a formal model for assessing the security of ICs whose fabrication has been outsourced to an untrusted off-shore manufacturer. We assume that the IC specification and design are trusted but the fabrication facility(ies) may be untrusted. Our objective is to stop Trojans from releasing sensitive information to the outside while still using its circuitry for day-to-day operations. We also provide two different methodologies for constructing compilers relying on verifiable computation (VC) schemes and secure multiparty computation (MPC) protocols with certain properties. Suitable VC schemes, with the properties we require, were recently constructed, e.g., by Parno et al. (Oakland ’13), and by Fiore, Gennaro, and Pastro (CCS ’14). Similarly, many MPC protocols readily comply (or can be easily adapted to comply) with our requirements. By allowing manufacturers to use off-shore fabrication facilities, we ensure a high degree of competition among suppliers, thus providing lower cost without hindering innovation or access to leading-edge microelectronics.

A Family of FDH Signature Schemes Based on the Quadratic Residuosity Assumption

Conference paper
Giuseppe Ateniese, Katharina Fech, Bernardo Magri
19th International Conference on Cryptology in India (IndoCrypt 2018)
Publication year: 2018

Signature schemes are arguably the most crucial cryptographic primitive, and devising tight security proofs for signature schemes is an important endeavour, as it immediately impacts the feasibility of deployment in real world applications. Hash-then-sign signature schemes in the Random Oracle Model, such as RSA-FDH, and Rabin-Williams variants are among the fastest schemes to date, but that unfortunately do not enjoy tight security proofs based on the one-wayness of their trapdoor function; instead, all known tight proofs rely on variants of the (non-standard) Φ-Hiding assumption.
As our main contribution, we introduce a family of hash-then-sign signature schemes, inspired by a lossy trapdoor function from Freeman et al. (JoC’ 13), that is tightly secure under the Quadratic Residuosity assumption. Our first scheme has the property of having unique signatures, while the second scheme is deterministic with an extremely fast signature verification, requiring at most 3 modular multiplications.

The Good, the Bad, and the (not so) Ugly: Many Facets of Cryptographic Backdoors

PhD Thesis
Bernardo Magri
Ph.D. Thesis, Sapienza University of Rome, Italy, 2017
Publication year: 2017

Modern cryptography is concerned with the feasibility or infeasibility of securely realizing a task. The answer to whether or not a task can be securely realized depends on the assumed power of the adversary. The obtained security holds in a strong mathematical sense, meaning that breaking a secure cryptographic protocol is either impossible or it would require to solve some computational problem which is believed to be hard to solve. The most basic computational assumption made in cryptography is the existence of one-way functions. One-way functions are functions that are easy to compute but are hard to invert on almost all inputs. By just assuming the existence of one-way functions it is already possible to realize many cryptographic tasks, but there are some tasks that can only be realized by assuming the existence of trapdoor functions (also called backdoored functions). Trapdoor functions are easy to compute in one direction but hard to invert; the difference is the existence of a special value that allows the function to be easily inverted by any party that has knowledge of this special value.

In this thesis we have contributions in three different facets of backdoors in cryptography, that we describe next.

  • Backdoors for legitimate usage: We define a new security goal for chameleon hash functions that we call enhanced collision resistance. This security definition informally says that a chameleon hash function must remain collision-resistant even after an adversary sees polynomially many collisions for the function. We also present a novel transformation from standard chameleon hash functions to enhanced ones; a full-fledged “redactable blockchain” application, that leverages the power of enhanced collision-resistant chameleon hashes, is built to show that this new security goal for chameleon hashes makes sense in practice.
  • Backdoors for malicious usage: Motivated by the revelations of Edward Snowden about intelligence agencies intentionally undermining the security of cryptographic schemes, we cover the case where backdoors are used to perform attacks against signature schemes. In this vein, we define what is an undetectable subversion attack against a signature scheme and we also present two devastating attacks against randomized signature schemes that allows the complete extraction of the users’ signing key.
  • Immunization techniques against malicious backdoors: Our contributions in this vein are twofold. We first show positive results for signature schemes against subversion attacks; we prove that unique signatures are secure against an undetectable class of subversion attacks and that re-randomizable signatures are secure against *all* classes of subversion attacks (by employing a cryptographic reverse firewall introduced in this thesis). In the other contribution on the immunization direction we define a secure model for the outsourcing of circuit fabrication, where the outsourcing facilities are untrusted and can potentially embed malicious hardware trojans in the circuit. We construct three compilers that upon input an arbitrary circuit it produces an outsourcing-secure version of the circuit.

Redactable Blockchain - or - Rewriting History in Bitcoin and Friends

Conference paper
Giuseppe Ateniese, Bernardo Magri, Daniele Venturi and Ewerton R. Andrade
IEEE Euro Security & Privacy conference, 2017
Publication year: 2017

We put forward a new framework that makes it possible to re-write and/or compress the content of any number of blocks in decentralized services exploiting the blockchain technology. As we argue, there are several reasons to prefer an editable blockchain, spanning from the necessity to remove improper content and the possibility to support applications requiring re-writable storage, to “the right to be forgotten”.

Our approach generically leverages so-called chameleon hash functions (Krawczyk and Rabin, NDSS ’00), which allow to efficiently determine hash collisions given a secret trapdoor information. We detail how to integrate a chameleon hash function in virtually any blockchain-based technology, for both cases where the power of redacting the blockchain content is in the hands of a single trusted entity and where such a capability is distributed among several distrustful parties (as is the case in Bitcoin).

We also report on a proof-of-concept implementation of a redactable blockchain, building on top of Nakamoto’s Bitcoin core. The implementation only requires minimal changes to the way current client software interprets information stored in the blockchain and to the current blockchain, block, or transaction structures. Moreover, our experiments show that the overhead imposed by a redactable blockchain is small compared to the case of an immutable one.

Subversion-Resilient Signature Schemes

Conference paper
Giuseppe Ateniese, Bernardo Magri and Daniele Venturi
CCS '15, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Pages 364-375
Publication year: 2015

We provide a formal treatment of security of digital signatures against subversion attacks (SAs). Our model of subversion generalizes previous work in several directions, and is inspired by the proliferation of software attacks (e.g., malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms. The main security requirement we put forward demands that a signature scheme should remain unforgeable even in the presence of an attacker applying SAs (within a certain class of allowed attacks) in a fully-adaptive and continuous fashion. Previous notions—e.g., security against algorithm-substitution attacks introduced by Bellare et al. (CRYPTO ’14) for symmetric encryption—were non-adaptive and non-continuous.

In this vein, we show both positive and negative results for constructing subversion-resilient signature schemes. — Negative results. As our main negative result, we show that a broad class of randomized schemes is unavoidably insecure against SAs, even if using just a single bit of randomness. This improves upon earlier work that was only able to attack schemes with larger randomness space. When designing our attack we consider undetectability to be an explicit adversarial goal, meaning that the end-users (even the ones knowing the signing key) should not be able to detect that the signature scheme was subverted. — Positive results. We complement the above negative results by showing that signature schemes with unique signatures are subversion-resilient against all attacks that meet a basic undetectability requirement. A similar result was shown by Bellare et al. for symmetric encryption, who proved the necessity to rely on stateful schemes; in contrast unique signatures are stateless, and in fact they are among the fastest and most established digital signatures available.

We finally show that it is possible to devise signature schemes secure against arbitrary tampering with the computation, by making use of an un-tamperable cryptographic reverse firewall (Mironov and Stephens-Davidowitz, EUROCRYPT ’15), i.e., an algorithm that “sanitizes” any signature given as input (using only public information). The firewall we design allows to successfully protect so-called re-randomizable signature schemes (which include unique signatures).

While our study is mainly theoretical, due to its strong practical motivation, we believe that our results have important implications in practice and might influence the way digital signature schemes are selected or adopted in standards and protocols.

Certified Bitcoins

Conference paper
Giuseppe Ateniese, Antonio Faonio, Bernardo Magri and Breno de Medeiros
ACNS '14, Applied Cryptography and Network Security, Volume 8479 of the series Lecture Notes in Computer Science, Pages 80-96
Publication year: 2014

Bitcoin is a peer-to-peer (p2p) electronic cash system that uses a distributed timestamp service to record transactions in a public ledger (called the Blockchain). A critical component of Bitcoin’s success is the decentralized nature of its architecture, which does not require or even support the establishment of trusted authorities. Yet the absence of certification creates obstacles to its wider acceptance in e-commerce and official uses. We propose a certification system for Bitcoin that offers: a) an opt-in guarantee to send and receive bitcoins only to/ from certified users; b) control of creation of bitcoins addresses (certified users) by trusted authorities. Our proposal may encourage the adoption of Bitcoin in different scenarios that require an officially recognized currency, such as tax payments—often an integral part of e-commerce transactions.