Cryptology and Network Security

Location information extracted from mobile devices has been largely exploited to reveal our routines, significant places, and interests, just to name a few. Given the sensitivity of the information it reveals, location access is protected by mobile operating systems and users have control over which applications can access it. We argue that applications can still infer the coarse-grain location information by using alternative sensors that are available in off-the-shelf mobile devices that do not require any permissions from the users.

Over the years, developers have become increasingly reliant on web technologies to build their applications, raising concerns about side-channel attacks, especially on cryptographic libraries. Despite the efforts of researchers to ensure constant-time security by proposing tools and methods to find vulnerabilities, challenges remain due to inadequate tools and integration issues in development processes.

We tackle the main limitations of state-of-the-art detection tools. While Microwalk is the first and, to the best of our knowledge, only tool to find side-channel vulnerabilities in JavaScript libraries, the instrumentation framework it relies on does not support modern JavaScript features. Moreover, and common to most state-of-the-art detection tools not aimed at JavaScript, writing tests is a tedious process due to the complexity of libraries, the lack of information about test coverage, and the rudimentary interpretability of the report. Furthermore, recent studies show that developers do not use these tools due to compatibility issues, poor usability, and a lack of integration into workflows.

We extend Microwalk in several directions. First, we design a generic AST-level tracing technique that is tailored to source-based dynamic side-channel leakage analysis, providing support for the latest language features. Second, we bring semi-automation to Microwalk analysis templates, considerably reducing the manual effort necessary to integrate side-channel analyses into development workflows. Third, we are the first to combine leakage reporting with coverage visualization. We evaluate the new toolchain on a set of cryptographic libraries and show that it can quickly and comprehensively uncover more vulnerabilities while writing tests with half as many lines of code as the previous Microwalk version. By open sourcing our new tracer and analysis template, we hope to increase the adoption of automated side-channel leakage analyses in cryptographic library development.

Updatable encryption (UE) allows a third-party server to update outsourced encrypted data without exposing keys and plaintexts. The server can update ciphertexts to ones under a new key using an update token provided by the client. UE can realize efficient key rotation and is effective against key compromise. The standard security notions of UE capture the property that even if keys or update tokens are compromised, the confidentiality of messages is maintained by the key update and ciphertext update. In general, the randomnesses used in the encryption and ciphertext update algorithms must be kept secret in the same way as the keys. On the other hand, while key compromise is considered in existing security notions, randomness compromise is not. In this paper, we define a new security notion for UE, \(\textsf{IND}\text {-}\textsf{UE}\text {-}\textsf{R}\) security, that is resilient to the compromise of randomnesses used to generate or update ciphertexts. Furthermore, we prove that the UE construction \(\textsf{RISE}\) (EUROCRYPT’18) satisfies our proposed security notion.

Federated learning (FL) is one of the promising collaborative machine learning methods finding many usage application scenarios in different domains such as healthcare [19] and/or telecommunication (5G, 5G beyond and 6G [25]). It also enhances privacy by allowing users to contribute to the global model training without sharing their training data. However, the local model updates exposed by users can still leak sensitive information. To prevent such leakage, secure aggregation protocols are utilized to hide the individual local model updates from the aggregator. Enhancing privacy in this way creates an open door for security attacks because the server is no longer able to analyze received updates for detection of poisoning type of attacks. Although there are considerable number of studies that address the privacy and security aspects individually, solutions against the combination of these attacks have started to appear recently in a few studies. When we add some additional requirements such as aggregation unforgeability and robustness against user drop-outs, the number of solutions becomes very limited. Most of the proposals addressing all these aspects at the same time require two or more non-colluding aggregators, which may not be a realistic assumption in most of the use cases. To address this gap, we introduce new secure aggregation protocols involving one aggregator only. Each proposed protocol addresses a subset of the requirements where as the final one, FULLSA3, is secure against malicious clients and robust against user drop-outs. As a side contribution, we design a new batch oblivious range verification protocol.

Classic Machine Learning as a Service (MLaaS) solutions suffer from privacy-related risks since the user inputs are sent in the clear to the server hosting the ML model. To alleviate this problem, a thriving line of research has emerged, called Privacy-Preserving Machine Learning (PPML) or secure MLaaS, that uses cryptographic techniques such as Fully Homomorphic Encryption (FHE) to preserve the privacy of both the client’s input and the server’s output. FHE-based secure MLaaS solutions bear a resemblance to classic MLaaS solutions. This similarity arises from the fact that the client interacts with the server hosting the ML model only twice. The first interaction occurs when the client sends its encrypted input, while the second interaction takes place when the client receives the still-encrypted inference result. The entire inference runs on the server, albeit on encrypted data. However, this similarity also begs the question of whether these FHE-based secure MLaaS solutions are vulnerable to model-stealing attacks from the classic MLaaS setting. In this paper, we, for the first time in literature, investigate the transferability of the well-known model-stealing attacks from the classic to the secure MLaaS domain. We demonstrate two attacks from the classic MLaaS setting, namely Jacobian-based Dataset Augmentation (JBDA) and KnockoffNets, on FHE-based image classification tasks to highlight the practicality of the attacks. We then argue that while the existing attacks are portable to the PPML setting, the same does not hold for the existing defenses. To support our argument, we present a detailed study of popular defenses against model-stealing attacks. We highlight the gap between their implementation in the classic MLaaS and the incompatibility of their underlying operations with that of the FHE operations. Finally, we demonstrate a countermeasure against these attacks that lowers the accuracy of the stolen model while minimally affecting the accuracy of the victim model on benign queries, without compromising the privacy of the client’s data.

Registration-based encryption (RBE) is a solution for the key-escrow problem in identity-based encryption. Initial RBE schemes are too theoretical and inefficient, but recent advances make RBE schemes efficient enough to be incorporated into real-world systems. On the other hand, from a security point of view, existing schemes are insufficient for such systems because they only consider CPA security. Recently, Glaeser et al. (ACM CCS’23) presented a solution to this problem. They suggested the usage of the original Fujisaki-Okamoto (FO) transformation (CRYPTO’99) to realize CCA-secure RBE. However, they did not provide its formal analysis because they considered it can be applied in a straightforward manner. In this work, we reveal that the FO transformation for RBE is non-trivial, and provide an appropriate one suitable to RBE. The essence of achieving CCA security through FO transformation is that the receiver verifies that the received ciphertext is correctly generated by re-encryption. In RBE, we find that the sender and receiver must share the public parameter used for encryption since the decryption algorithm does not take it by default. Therefore, we make the sender explicitly send the current public parameter as part of the ciphertext. Furthermore, we show that a sufficiently large min-entropy of ciphertexts (so-called well-spreadness) is necessary to apply the FO transformation to RBE, in contrast to PKE or IBE. This property guarantees that no information is leaked from the decryption oracle even if the public parameter in the ciphertext is replaced. Based on these observations, we propose a new FO transformation tailored to RBE, which allows existing CPA-secure RBE schemes to be transformed into CCA-secure ones correctly.

Private information retrieval (PIR) allows a client to obtain records from a database without revealing the retrieved index to the server. In the single-server model, it has been known that (plain) PIR is vulnerable to selective failure attacks, where a (malicious) server intends to learn information of an index by getting a client’s decoded result. Recently, as one solution for this problem, Ben-David et al. (TCC 2022) proposed verifiable PIR (vPIR) that allows a client to verify that the queried database satisfies certain properties. However, the existing vPIR scheme is not practically efficient, especially when we consider the multi-query setting, where a client makes multiple queries for a server to retrieve some records either in parallel or in sequence.

In this paper, we introduce a new formalization of multi-query vPIR and provide an efficient scheme based on authenticated PIR (APIR) and succinct non-interatctive arguments of knowledge (SNARKs). More precisely, thanks to the nice property of APIR, the communication cost of our multi-query vPIR scheme is \(\mathcal {O}(n \cdot |a| + |\pi | )\), where n is the number of queries, |a| is the APIR communication size, and \(|\pi |\) is the SNARK proof size. That is, the communication includes only one SNARK proof. In addition to this result, to show the effectiveness of our multi-query vPIR scheme in a real-world scenario, we present a practical application of vPIR on the online certificate status protocol (OCSP) and provide a comprehensive theoretical evaluation on our scheme in this scenario. Especially in the setting of our application, we observe that integrating SNARK proofs (for verifiability) does not significantly increase the communication cost.

We revisit OCAKE (ACNS 23), a generic recipe that constructs password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEMs), to allow instantiations with post-quantums KEM like KYBER.

The ACNS23 paper left as an open problem to argue security against quantum attackers, with its security proof being in the universal composability (UC) framework. This is common for PAKE, however, at the time of this submission’s writing, it was not known how to prove (computational) UC security against quantum adversaries. Doing this becomes even more involved if the proof uses idealizations like random oracles or ideal ciphers.

To pave the way towards post-quantum security proofs, we therefore resort to a (still classical) game-based security proof in the BPR model (EUROCRYPT 2000). We consider this a crucial stepping stone towards a fully satisfying post-quantum security proof. We also hope that a game-based proof is easier to (potentially formally) verify.

We prove security of (a minor variation of) OCAKE, assuming the underlying KEM satisfies notions of ciphertext indistinguishability, anonymity, and (computational) public-key uniformity. Using multi-user variants of these properties, we achieve tight security bounds.

We provide a full detailed proof – something often omitted in publications on game-based security of PAKE. As a side-contribution, we demonstrate in detail how to handle password guesses, which is something we were unable to find in the existing literature at the time of writing.

Finally, we discuss which current PQC KEMs can be plugged into the proposed protocol and provide a concrete instantiation, accompanied by a proof-of-concept implementation and respective run-time benchmarks.

In this paper, we propose a new method based on Mixed-Integer Linear Programming (MILP) to search for differential-linear (DL) distinguishers targeting word-oriented block ciphers. To be specific, we present a new structure of DL distinguishers based on the works of Biham et al. and Bar-On et al., and divide the process of finding an R-round DL distinguisher into two stages. In the first stage, we aim to prepare some special (\(R-1\))-round truncated differentials with high probabilities using MILP, which is adapted to our new DL structure. To achieve this goal, we simplify the types of previous truncated differential (TD) patterns and optimize the propagation rules of TDs. In the second stage, we concatenate the prepared TDs with the introduced concept of the differential-linear connectivity layer (DLCL), whose bias can be calculated by differential-linear connectivity tables (DLCTs) of S-boxes, to efficiently determine the optimal output linear mask for deriving an R-round DL distinguisher.

We apply the proposed method to Midori64, CRAFT, and Skinny64. As a result, the longest DL distinguishers obtained in this paper for Midori64, CRAFT, and Skinny64 are 6, 11, and 10 rounds with the estimated biases of \(2^{-14.43}\), \(2^{-16.04}\), and \(2^{-22.73}\), respectively. To the best of our knowledge, this is the first study to explore the DL distinguishers of Midori64 and CRAFT against DL cryptanalysis. In addition, we also conduct experiments to verify the validity of these distinguishers. Consequently, our estimated biases are very close to the experimental ones, which indicates that these DL distinguishers are indeed valid and also provides a strong support for the effectiveness of our method. By the way, our results cannot threaten the security of the three ciphers, but provide a better understanding on the strength against DL cryptanalysis, especially for Midori64 and CRAFT.

The SPRING block cipher is an award-winning algorithm of the recent Cryptographic Algorithm Design Competition in China, and it has three versions: SPRING128-128 with a 128-bit block size and a 128-bit key size, SPRING128-256 with a 128-bit block size and a 256-bit key size, and SPRING256 with a 256-bit block size and a 256-bit key size. The best previously published cryptanalytic results on SPRING are (ordinary) differential attacks on 5-round SPRING128-128 and 10-round SPRING256 and differential and meet-in-the-middle attacks on 6-round SPRING128-256. In this paper, we observe that the two main elementary operations SubRow and Transpose of the SPRING round function enable some multiple-round one-byte truncated differential paths (i.e., input and output differences as well as any intermediate difference have only one active byte) with probability approximately \(2^{-24}\) for every round, then we construct a few 4-round truncated differentials with probability \(2^{-68}\) of SPRING128, 5-round truncated differentials with probability \(2^{-90}\) of SPRING128 and 11-round truncated differentials with probability \(2^{-223}\) of SPRING256, and finally we make truncated differential attacks on 6-round SPRING128-128/256, 7-round SPRING128-256 and 11/12/13-round SPRING256. Our attacks are better than any previously published cryptanalytic results on the corresponding versions of SPRING in terms of the numbers of attacked rounds.

Areion is a family of wide-block permutations proposed at CHES 2023. For the security against differential attacks of Areion, the designers showed only upper bounds of the differential characteristic probability, which are derived from the lower bounds of the number of active S-boxes by a byte-wise search. In this paper, we obtain tighter bounds on differential characteristic probability of Areion by a bit-wise SAT-based search tool. We discover a new inherent property in the S-box layers for Areion permutation, which is overlooked by designers’ evaluation. This enables us to significantly update the bounds of differential probability. Furthermore, leveraging this new property with our SAT-based tool, we develop collision attacks on Areion-DM (Davies-Meyer) and Areion-MD (Merkle-Damgård) hashing modes. As a result, we demonstrate 4/6-round collision attacks on Areion256/512-DM, and 7-round semi-free-start collision on Areion-MD.