International Association for Cryptologic Research

International Association
for Cryptologic Research


Xinyi Huang

Affiliation: Singapore Management University


Subvert KEM to Break DEM: Practical Algorithm-Substitution Attacks on Public-Key Encryption 📺
Rongmao Chen Xinyi Huang Moti Yung
Motivated by the widespread concern about mass surveillance of encrypted communications, Bellare \textit{et al.} introduced at CRYPTO 2014 the notion of Algorithm-Substitution Attack (ASA) where the legitimate encryption algorithm is replaced by a subverted one that aims to undetectably exfiltrate the secret key via ciphertexts. Practically implementable ASAs on various cryptographic primitives (Bellare \textit{et al.}, CRYPTO'14 \& CCS'15; Ateniese \textit{et al.}, CCS'15; Berndt and Li\'{s}kiewicz, CCS'17) have been constructed and analyzed, leaking the secret key successfully. Nevertheless, in spite of much current attention, the practical impact of ASAs (formulated originally for symmetric key cryptography) on public-key (PKE) encryption operations remains unclear, primarily since the encryption operation of PKE does not involve the secret key and previously known ASAs become relatively inefficient for leaking the plaintext due to the logarithmic upper bound of exfiltration rate (Berndt and Li\'{s}kiewicz, CCS'17). In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practical systems. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack. Our attack relies on a novel identification and formalization of specific non-black-box yet general enough properties that yield practical ASAs on KEMs. More broadly, this may shed some light on exploring the structural weakness of other composed cryptographic primitives, which may make them susceptible to more dangerous ASAs that surpass the logarithmic upper bound of exfiltration rate on universal ASAs.
Nominative Signature: Application, Security Model and Construction
Since the introduction of nominative signature in 1996, there have been only a few schemes proposed and all of them have already been found flawed. In addition, there is no formal security model defined. Even more problematic, there is no convincing application proposed. Due to these problems, the research of nominative signature has almost stalled and it is unknown if a secure nominative signature scheme can be built or there exists an application for it. In this paper, we give positive answers to these problems. First, we illustrate that nominative signature is a better tool for building user certification systems which are originally believed to be best implemented using a universal designated-verifier signature. Second, we propose a formal definition and a rigorous set of adversarial models for nominative signature. Third, we show that Chaum's undeniable signature can be transformed efficiently to a nominative signature and prove its security.
Online/Offline Signatures and Multisignatures for AODV and DSR Routing Security
Efficient authentication is one of important security requirements in mobile ad hoc network (MANET) routing systems. The techniques of digital signatures are generally considered as the best candidates to achieve strong authentication. However, using normal digital signature schemes is too costly to MANET due to the computation overheads. Considering the feasibility of incorporating digital signatures in MANET, we incorporate the notion of online/offline signatures, where the computational overhead is shifted to the offline phase. However, due to the diversity of different routing protocols, a universal scheme that suits all MANET routing systems does not exist in the literature. Notably, an authentication scheme for the AODV routing is believed to be not suitable to the DSR routing. In this paper, we first introduce an efficient ID-based online/offline scheme for authentication in AODV and then provide a formal transformation to convert the scheme to an ID-based online/offline multisignature scheme. Our scheme is unique, in the sense that a single ID-based online/offline signature scheme can be applied to both AODV and DSR routing protocols. We provide the generic construction as well as the concrete schemes to show an instantiation of the generic transformation. We also provide security proofs for our schemes based on the random oracle model. Finally, we provide an application of our schemes in the dynamic source routing protocol.
Breaking and Repairing Trapdoor-free Group Signature Schemes from Asiacrypt 2004
Xinyi Huang Willy Susilo Yi Mu
Group signature schemes allow a member of a group to sign messages anonymously on behalf of the group. In the case of later dispute, a designated group manager can revoke the anonymity and identify the originator of a signature. In Asiacrypt 2004, Nguyen and Safavi-Naini proposed a group signature scheme that has a constant-size public key and signature length, and more importantly, their group signature scheme does not require trapdoor. Their scheme is very efficient and the sizes of signatures are shorter compared to the existing schemes that were proposed earlier. In this paper, we point out that Nguyen and Safavi-Naini's scheme is insecure. In particular, we provide a cryptanalysis of the scheme that allows a non-member of the group to sign on behalf of the group. The resulting group signature can convince any third party that a member of the group has indeed generated such a signature, although none of the members has done it. Therefore, in the case of dispute, the group manager cannot identify who has signed the message. We also provide a new scheme that does not suffer against this problem.

Program Committees

Asiacrypt 2020