Information Security and Cryptology – ICISC 2022

See-In-The-Middle (SITM) is an analysis technique that utilizes side-channel information for differential cryptanalysis. The SITM attack exploits side-channel leakage in the middle round of blockcipher implementations. The blockcipher ARIA proposed at ICISC 2003 is a Korean national standard, and the blockcipher DEFAULT proposed at Asiacrypt 2021 offers proctection against differential fault analysis. In this study, we propose SITM attacks on the ARIA-128, 192, 256 and DEFAULT. Consequently, it is demonstrated that for these blockciphe r based on look-up-table implementations and no masking technique SITM attacks are possible with practical attack complexities.

When keys are small or parts thereof leak, key-recovery attacks on symmetric-key primitives still pose a plausible threat. Key stretching is one well-known means to throttle potential adversaries, where stretching a key by s bit means that a key-recovery attack has to perform \(\min \{2^{k-1}, 2^{k-\lambda +s-1}\}\) operations on average for \(\lambda \) bit information leakage. However, typical explicit key stretching requires also the defender to pay for the stretch operations.

The usual assumption is that a surrounding encryption scheme does not increase the key-recovery security of its internal primitives. This work challenges this assumption by considering the structure of popular encryption schemes. In particular, message lengths may be non-negligible in settings such as full-disk encryption or archiving, where the adversary can obtain only long messages. Surprisingly, the question of whether a surrounding encryption scheme has only a negligible impact on key recovery seems to have remained uninvestigated. Therefore, it is interesting to study if “implicit” key stretching may come for free as an inherent property of popular schemes.

We define an encryption scheme as “fully key-stretching-secure” if an adversary that sees plaintext-ciphertext pairs of at least m blocks each must perform at least m primitive calls for testing a key candidate. Using a similar definition of affine modes as Chakraborti et al. in JMC 2018, we systematically explore common encryption schemes with respect to their key-stretching security. In total, we consider five classes of (1) online, (2) SIV-like, (3) parallelizable two-pass (EME-like), (4) sequential two-pass (CMC-like), and (5) three-pass (HCTR-like) encryption schemes. By modeling them as affine modes, we can identify all considered encryption schemes key-stretching-insecure, i.e., one needs only O(1) primitive calls for testing a key candidate. However, for the insecure schemes from types (4) and (5), namely for EME-, CMC-, and HCTR-like schemes, we propose minor tweaks to ensure full key-stretching security.

With the urgency of the threat imposed by quantum computers, there is a strong interest in making the signature schemes quantum resistant. As the promising candidates to ensure post-quantum security, symmetric-key primitives, in particular the recent MPC/FHE/ZK-friendly hash functions or block ciphers, are providing another choice to build efficient and secure signature schemes that do not rely on any assumed hard problems. However, considering the intended use cases, many of these novel ciphers for advanced cryptographic protocols do not claim the related-key security.

In this paper, we initiate the study of the ignored related-key security of GMiMC proposed by Albrecht et al. at ESORICS 2019, some versions of which are optimized and designed to be used in post-quantum secure signatures. By investigating the potential threats of related-key attacks for GMiMC intended to be deployed as the underlying building block in post-quantum signature schemes, we then construct two kinds of iterative related-key differentials, from which not only do we explore its security margin against related-key attacks, but also collision attacks on its key space can be performed. For example, for GMiMC instance that beats the smallest signature size obtainable using LowMC, we can find its key collision using only about \(2^{10}\) key pairs. It worths noting that our current key collision attack is only applicable when the adversarial power is sufficiently strong (e.g., in the so-called multi-user setting), and it does not threaten the one-wayness of GMiMC. Furthermore, from the experiments of our related-key differentials, it can be observed that the differential clustering effect of GMiMC differs in both aspects: the choice of the finite field \(\mathbb {F}\) being \(\mathbb {F}_p\) or \(\mathbb {F}_2^n\), and the size of the finite field \(\mathbb {F}\).

The area of lightweight cryptography, i.e., ciphers with particularly low implementation costs, has drawn considerable attention over the last few years. PRINCE is a lightweight block cipher proposed by J. Borghoff et al. at ASIACRYPT 2012. In 2017, Ding et al. constructed a 4-round truncated impossible differential distinguisher. They treat S-boxes as ideal ones that any nonzero input difference could produce any nonzero output difference. Obviously, this is not true for the S-boxes in the real block ciphers. In this paper, after investigating the properties of both the S-box and the linear layer of PRINCE, we construct two types of 5-round impossible differential distinguishers. Then we exhibit two types of key-recovery attacks on 9 out of 12 rounds of PRINCEcore. The corresponding data complexities are \(2^{53.3}\) and \(2^{56.1}\) chosen plaintexts, respectively. Our results are the best impossible differential cryptanalysis on PRINCE as far as we know to date, and our attacks meet the security claims of the designers.

Pattern lock strength meters designed for securing Android devices are inconsistent in their metering, e.g., assigning higher scores to weaker patterns. In this paper, we raise this inconsistency problem by analyzing five existing pattern strength meters. We reveal that they commonly miss some important visual features and even assign erroneous weights to features. As a preliminary study toward a consistent pattern strength meter in the future, we design a rigorous user study to identify the visual features of a pattern that correspond to real-world users’ criteria to score the strength of the pattern. We conducted an online survey for 3,851 users to collect reliable labels for 625 patterns. The statistical result of the user study sheds light on a pattern strength meter that reflects the user’s visual perception with various visual features.

End-to-End Encryption (E2EE) aims to make all messages impossible to read by anyone except you and your intended recipient(s). Many well-known and widely used Instant-Messaging (IM) applications (such as Signal, WhatsApp, Apple’s iMessage, and Telegram) claim to provide an E2EE functionality. However, a recent technique called client-side scanning (CSS), which could be implemented by these IM applications, makes these E2EE claims grandiose and hollow promises. The CSS is a technology that scans all sending and receiving messages from one end to the other, including text, images, audio, and video files. Some in industry and government now advocate this CSS technology to combat the growth of malicious child pornography, terrorism, and other illicit communication. Even though combating the spread of illegal and morally objectionable content is a laudable effort, it may open further backdoors that impact the user’s privacy and security. Therefore, it is not end-to-end encryption when there are censorship mechanisms and backdoors in end-to-end encrypted applications. In this paper, we shed light on this hugely problematic issue by introducing an encrypted keyboard that works as a system keyboard and can be enabled on the user’s phone device as a default system keyboard. Therefore, it works on every application on the user’s phone device when the user is asked to enter some data. To avoid the CSS system, users can use this encrypted keyboard to encrypt and decrypt their messages locally on their phone devices when sending and receiving them via IM applications. We first design and implement our encrypted keyboard as a custom keyboard application, and then we evaluate the effectiveness and security of our encrypted keyboard. Our study results show that our encrypted keyboard can successfully encrypt and decrypt all sending and receiving messages through IM applications, and therefore, it can successfully defeat the CSS technology in end-to-end encrypted systems. We also show that our encrypted keyboard can be used to add another layer of E2EE functionality on top of the existing E2EE functionality implemented by many end-to-end encrypted applications.

Differential fuzz testing is a promising technique to detect numerous bugs in cryptographic libraries by providing the same input for different implementations of cryptographic algorithms. Cryptofuzz is an edge-cutting project that supports various libraries in this regard, employing coverage-guided libFuzzer as its back-end core. However, we observe that Cryptofuzz heavily relies on heuristic custom mutation strategies to expand code coverage while fuzzing, compensating for the limited performance of libFuzzer and the overhead of differential fuzzing. In this paper, we show such evidence and then present a novel tweak method to make differential fuzzing perform better with advanced fuzzers rather than the custom mutators overfitted with cryptographic features. Our basic insight is that hybrid fuzzing, which combines fuzzing and concolic execution, could help. We make the front end of Cryptofuzz standalone for differential testing of cryptographic libraries with hybrid fuzzers. We conduct experiments and use AFL and Intriguer for hybrid fuzzing. Our evaluation results show that the proposed method achieves better code coverage independently of the custom mutators and is more effective in bug-finding than Cryptofuzz. Our method generalizes its back end to use any advanced fuzzers for differential testing of cryptographic libraries.

Public key encryption with keyword search (PEKS), which was introduced by Boneh et al. at EUROCRYPT’ 04, is a breakthrough approach to searching encrypted data under a public key setting. In this cryptographic primitive, senders can generate searchable ciphertexts for specific keywords to be retrieved from a given document; receivers can generate corresponding trapdoors for search by using their private keys. Recently, Jiang et al. (ACISP’ 16) proposed an improved PEKS scheme called public key encryption with authorized keyword search (PEAKS); this scheme enables authorized users to generate trapdoors for specific sets of keywords even if these users do not have access to the private key. Unfortunately, authorized users cannot delegate this power to other unauthorized users because the authorization in PEAKS is insufficiently flexible; therefore, this scheme is not suitable for enterprise scenarios in general. In this work, we introduce a novel cryptographic primitive called public key encryption with hierarchical authorized keyword search (PEHAKS) to solve this problem. In contrast to PEAKS, the proposed primitive enables authorized users to further hierarchically delegate their power of generating trapdoors to unauthorized users. We formally define the system model of PEHAKS under a multikeyword setting, and the security requirements are designed to withstand attacks in a real scenario. Furthermore, we propose a provably secure scheme using the technique of dual pairing vector spaces and demonstrate that the scheme is secure under the hardness of the n-extended decisional Diffie–Hellman assumption. Therefore, the proposed scheme is secure and can be applied in scenarios that require hierarchical authorization. To the best of the authors’ knowledge, no PEKS variant schemes with this property have been previously designed.

There has been increasing interest in developing privacy-preserving algorithms for evaluating machine learning (ML) models. With the advancement of cloud computing, it is now possible for model owners to host their trained ML models on a cloud server and offer cloud computing solutions on different ML tasks to users (clients). Thus private evaluation of ML models is an attractive area of research as it allows solution providers to protect their propriety ML models and users to protect their sensitive data while using cloud computing solutions. In this work, we propose an algorithm to privately evaluate a decision tree. We examine current state-of-the-art private evaluation protocols and present a solution that is sublinear in tree size and linear in tree depth. The key feature of our proposal is that it is entirely based on secret sharing and thus there are no computational costs associated with heavy cryptographic primitives such as modular exponentiation. We propose a new method to privately index arrays that avoids the use of public/symmetric key cryptosystem, typically associated with private array indexing protocols. The results of our experiments show that our solution has a low communication cost compared to existing methods (lower by a factor of \(\approx \)10 in the online phase), and demonstrate a faster runtime at low network latency (such as LAN network). We conclude by suggesting improvement to our protocol and proposing potential areas of future research.

This work introduces, to the best of our knowledge, the first stake based reputation and trust layer to proof of stake (PoS) system. Namely, we show that the delegation framework, introduced by Karakostas et al. (SCN’20) to provide a delegation framework, can be extended and repurposed to construct a trust layer over a PoS consensus protocol in addition to its original application. Furthermore, we show a concrete reputation system satisfying the positive results of (1) Asharov et al. (Asiacrypt’13), allowing the secure execution of multiparty protocols such as GMW (STOC’ 87) and Damgard and Ishai (Crypto’05), and (2) Kleinrock et al. (Indocrypt’20), a Reputation-fair Lottery, thus, also, a Proof of Reputation system. More concretely, our devised layer is used to construct a concrete reputation system based on arbitrary stake distribution. In this layer groups of users can freely and dynamically “assign their respective trust” to members of a set of trustees, i.e. participants that offered themselves as receivers of such assignment. Furthermore, our work offers the advantage of providing a clear stake based criteria, verifiable in the ledger, and, therefore, naturally resistant to sybil attack, that the set of trustees indeed yields an honest majority. This setting provides a better situation than a simple assumption of honest majority, since it involves stake in a decentralized ledger, and the public verifiability of the reputation score via verification of the stake distribution.

The modern security protocols in most of our systems rely primarily on three basic functions of asymmetric cryptography: public key encryption, digital signature, and key exchange. Today, we only do key exchange (TLS 1.3) with the ECDH protocol. The confidentiality is persistent because the session keys are discarded at the end and to certify this key exchange, we sign it with RSA or ECDSA. However, these cryptosystems are at least theoretically attackable in a quantum computer model. Thus the NIST PQC standardization process has given significant momentum to research on code-based public-key cryptosystems specifically. Their security is based on the hardness of the syndrome decoding problem. In this article, we first propose a new formalism of the matrix-vector product in based-code cryptography. Second, we present a chosen-ciphertext attack on the first step of Niederreiter decryption by solving the matrix-vector product problem with side-channel information. Finally, we put this result to recover secret information in code-based cryptosystems including some candidates for the extension of the NIST PQC normalization process.

As Post-Quantum Cryptography (PQC) incurs higher costs in some metrics compared to conventional cryptosystems, performance evaluation to determine the trade-offs on circumstantial usage is essential. In this paper, we provide state-of-the-art performance evaluation results of PQC algorithms in the IPsec protocol. Specifically, we perform a deep dive into the performance of PQC-integrated IKEv2 in terms of the execution speed of each IKEv2 stage and packet size according to various PQC algorithms and their security levels. The evaluation is conducted with our implementation, constructed upon strongSwan, the most popular open-source IPsec implementation. As only the latest, but unstable version of strongSwan supports PQC, it is not straightforward to integrate the existing PQC implementations into strongSwan. We propose a well-established method to integrate PQC algorithmhe code base of strongSwan. Our evaluation targets a variety of PQC KEM algorithms, including NIST Round 3 finalists (i.e., Kyber, NTRU, and Saber) and algorithms developed in Korea and China. The performance evaluation shows the trade-offs between the security level and performance for individual PQC algorithms in the IPsec protocol.

An ultrafast cryptographically secure pseudorandom number generator, referred to as MaD4, is presented in this paper. MaD4 maintains a small byte-oriented state, whose transition follows a pseudorandom permutation, and a large integer-oriented state, whose transition follows a pseudorandom mapping. The byte-oriented state is initialized from a secret key and then further used to bootstrap and initialize the integer-oriented state. After initialization, both states evolve, with the byte-oriented state serving as a source of entropy and periodically reseeding the integer-oriented state. The combination of slow byte-oriented operations and fast integer-oriented operations renders a nice balance between quality and speed. MaD4 generates high quality pseudorandom numbers as attested by standard statistical testing tools and runs at a speed close to half clock cycle per byte on an Intel Core i7 processor. With a large state space of 10520 bits, MaD4 has an expected period length around 1.00e+1783. It is designed to resist various known cryptographic attacks and withstand state compromise extension attacks as well.

The elliptic curve family of schemes has the lowest computational latency, memory use, energy consumption, and bandwidth requirements, making it the most preferred public key method for adoption into network protocols. Being suitable for embedded devices and applicable for key exchange and authentication, ECC is assuming a prominent position in the field of IoT cryptography. The attractive properties of the relatively new curve Curve448 contribute to its inclusion in the TLS1.3 protocol and pique the interest of academics and engineers aiming at studying and optimizing the schemes. When addressing low-end IoT devices, however, the literature indicates little work on these curves. In this paper, we present an efficient design for both protocols based on Montgomery curve Curve448 and its birationally equivalent Edwards curve Ed448 used for key agreement and digital signature algorithm, specifically the X448 function and the Ed448 DSA, relying on efficient low-level arithmetic operations targeting the ARM-based Cortex-M4 platform. Our design performs point multiplication, the base of the Elliptic Curve Diffie-Hellman (ECDH), in 3,2KCCs, resulting in more than 48% improvement compared to the best previous work based on Curve448, and performs sign and verify, the main operations of the Edwards-curves Digital Signature Algorithm (EdDSA), in 6,038KCCs and 7,404KCCs, showing a speedup of around \(11\%\) compared to the counterparts. We present novel modular multiplication and squaring architectures reaching \(\sim \)25% and \(\sim \)35% faster runtime than the previous best-reported results, respectively, based on Curve448 key exchange counterparts, and \(\sim \)13% and \(\sim \)25% better latency results than the Ed448-based digital signature counterparts targeting Cortex-M4 platform.

Synchronized aggregate signature is a special type of signature that all signers have a synchronized time period and allows aggregating signatures which are generated in the same period. This signature has a wide range of applications for systems that have a natural reporting period such as log and sensor data, or blockchain protocol.

In CT-RSA 2016, Pointcheval and Sanders proposed the new randomizable signature scheme. Since this signature scheme is based on type-3 pairing, this signature achieves a short signature size and efficient signature verification.

In this paper, we design the Pointchcval-Sanders signature-based synchronized aggregate signature scheme and prove its security under the generalized Pointcheval-Sanders assumption in the random oracle model. Our scheme offers the most efficient aggregate signature verification among synchronized aggregate signature schemes based on bilinear groups.

In trapdoor sanitizable signatures (TSS) (ACNS’08), a signer can partially delegate its signing ability to someone. When signing a message, the signer chooses its sanitizable parts. Each signature is associated with a trapdoor, enabling any entity arbitrarily to modify the sanitizable parts while retaining validity of the signature. In previous TSS, the sanitizable parts are permanently sanitizable. We formalize sanitization-controllable TSS, where the sanitizable parts can be partially (and irreversibly) changed into fixed. We formally define its security notions, including unlinkablity (any sanitized signature and its trapdoor cannot be linked to their original ones), invisibility (each signature leaks no information about its sanitizable parts) and strong context-hiding (SCH) (any sanitized signature and its trapdoor distribute like fresh ones). We propose a generic transformation from a downgrade-controllable downgradable affine MAC (DAMAC), which is a generalization of DAMAC (CT-RSA’19). Our TSS scheme is the first TSS scheme satisfying unlinkability or invisibility. In redactable signatures (ICISC’01), we can partially black out a signed message. We formalize disclosure-controllable trapdoor redactable signatures (TRS). We propose a generic transformation from a sanitization-controllable TSS. Our TRS scheme is the first unlinkable and disclosure-controllable (T)RS scheme.

In this paper, we comprehensively study group testing aggregate signatures that have functionality of both keyless aggregation of multiple signatures and identifying an invalid message from the aggregate signature, in order to reduce a total amount of signature-size for lots of messages. Our contribution is (i) to formalize strong security notions including soundness for group testing aggregate signatures by taking into account related work such as fault-tolerant aggregate signatures and non-interactive aggregate MACs with detecting functionality (i.e., symmetric case); (ii) to construct group testing aggregate signatures from aggregate signatures in a generic and comprehensive way; and (iii) to present an aggregate signature scheme which we can apply to our generic construction of group testing aggregate signatures with the formalized security.

In attribute-based signatures (ABS) for inner products, the digital signature analogue of attribute-based encryption for inner products (Katz et al., EuroCrypt’08), a signing-key (resp. signature) is labeled with an n-dimensional vector \(\textbf{x}\in \mathbb {Z}_p^n\) (resp. \(\textbf{y}\in \mathbb {Z}_p^n\)) for a prime p, and the signing succeeds iff their inner product is zero, i.e., \(\langle \textbf{x}, \textbf{y} \rangle =0 \pmod p\). We generalize it to ABS for range of inner product (ARIP), requiring the inner product to be within an arbitrarily-chosen range [L, R]. As security notions, we define adaptive unforgeablity and perfect signer-privacy. The latter means that any signature reveals no more information about \(\textbf{x}\) than \(\langle \textbf{x}, \textbf{y} \rangle \in [L,R]\). We propose two efficient schemes, secure under some Diffie-Hellman type assumptions in the standard model, based on non-interactive proof and linearly homomorphic signatures. The 2nd (resp. 1st) scheme is independent of the parameter n in secret-key size (resp. signature size and verification cost). We show that ARIP has many applications, e.g., ABS for range evaluation of polynomials/weighted averages, fuzzy identity-based signatures, time-specific signatures, ABS for range of Hamming/Euclidean distance and ABS for hyperellipsoid predicates.

Aggregate signature allows users to compress multiple signatures into a short signature (called an aggregate signature), and can reduce a total amount of signature-size on a channel. In particular, identity-based aggregate signature can reduce not only total signature-size but also total verification key-size, because it is possible to check the validity of multiple messages and an aggregate signature by using signers’ IDs, instead of verification keys. Furthermore, we focus on lattice-based constructions as post-quantum cryptography, due to recent advancement of quantum computers. In this paper, we propose the first identity-based interactive aggregate signature scheme from lattices. The security of our scheme is based on a standard lattice assumption, and its aggregate signature-size is logarithmic in the number of signatures.

Debris-Alazard, Sendrier, and Tillich proposed SURF, which is a code-based signature scheme and enjoys efficient signature generation and verification (eprint in 2017). The security of this scheme is based on two problems: one is DOOM (Decoding One Out of Many), and the other is the plain (U,U+V)-code problem over \(\mathbb {F}_2\). There are many studies on the former one but few studies on the latter one. Later the security of SURF was broken because the hardness of the plain (U,U+V)-code problem does not hold with considering a notion of the hull.

Then Debris-Alazard et al. proposed Wave as a successor of SURF, which is known as one of the most promising quantum-resistant signature schemes (ASIACRYPT 2019). Wave is based on similar problems used in SURF. Wave uses DOOM and the normalized generalized (U,U+V)-code problem over \(\mathbb {F}_3\).

In this paper, we utilize a notion of the Gramian (the determinant of the Gram matrices) of public keys and analyze the plain (U,U+V)-code problem over \(\mathbb {F}_2\). For this purpose, we compute the asymptotic probability distribution of Gramians of random matrices. Furthermore, we also show a way to analyze the normalized generalized (U,U+V)-code problem over \(\mathbb {F}_2\). Finally, we apply our analysis to the normalized generalized (U,U+V)-code problem over \(\mathbb {F}_3\). By our analysis with Gramian, SURF is completely broken, however, Wave is not directly threatened.

Creating a good deep learning model is an art which requires expertise in deep learning and a large set of labeled data for training neural networks. Neither is readily available. In this paper, we introduce a method that enables us to recover messages of LWE/LWR-based PKE/KEMs using simple multilayer perceptron (MLP) models trained on a small dataset. The core idea is to extend the attack dataset so that at least one of its traces has the ground truth label to which the models are biased towards. We demonstrate the effectiveness of the presented method on the examples of CRYSTALS-Kyber and Saber algorithms implemented in ARM Cortex-M4 CPU on nRF52832 system-on-chip supporting Bluetooth 5.2. We use amplitude-modulated EM emanations which are typically weaker and noisier than power or near-field EM side channels, and thus more difficult to exploit.

Approximate lattice trapdoors are introduced to improve the efficiency of lattice-based hash-and-sign signature. There are two improvements of the approximate setting for such schemes. The first is to use a non-spherical Gaussian sampler, and the second is the higher-bit approximate setting.

In this paper we consider further improvements of the approximate setting, namely we combine the higher-bit approximate setting with the use of a non-spherical Gaussian sampler. We assess the effectiveness of this approach by doing an analysis with a proof-of-concept implementation. We observe that our construction brings several improvements, especially in the public key size and signature size. Moreover, an exhaustive search for parameter sets make us aware of new parameters choices which lead to better results in the higher-bit approximate setting than those of previous work.

The \(\mathcal {S}_{\text{ leeve }}\) construction proposed by Chaum et al. (ACNS’21) introduces an extra security layer for digital wallets by allowing users to generate a “back up key” securely nested inside the secret key of a signature scheme, i.e., ECDSA. The “back up key”, which is secret, can be used to issue a “proof of ownership”, i.e., only the real owner of this secret key can generate a single proof, which is based on the WOTS+ signature scheme. The authors of \(\mathcal {S}_{\text{ leeve }}\) proposed the formal technique for a single proof of ownership, and only informally outlined a construction to generalize it to multiple proofs. This work identifies that their proposed construction presents drawbacks, i.e., varying of signature size and signing/verifying computation complexity, limitation of linear construction, etc. Therefore we introduce WOTSwana, a generalization of \(\mathcal {S}_{\text{ leeve }}\), which is, more concretely, a more general scheme, i.e. an extra security layer that generates multiple proofs of ownership, and put forth a thorough formalization of two constructions: (1) one given by a linear concatenation of numerous WOTS+ private/public keys, and (2) a construction based on tree like structure, i.e., an underneath Merkle tree whose leaves are WOTS+ private/public key pairs. Furthermore, we present the security analysis for multiple proofs of ownership, showcasing that this work addresses the early mentioned drawbacks of the original construction. In particular, we extend the original security definition for \(\mathcal {S}_{\text{ leeve }}\). Finally, we illustrate an alternative application of our construction, by discussing the creation of an encrypted group chat messaging application.