International Association
for Cryptologic Research

SNEIK is a family of lightweight cryptographic algorithms derived from a single 512-bit permutation. The SNEIKEN authenticated encryption and SNEIKHA hash algorithms are candidates in the ongoing NIST Lightweight Cryptography standardization effort. The SNEIGEN ``entropy distribution function'' was designed to speed up certain functions in post-quantum and lattice-based public key algorithms. We implement and evaluate SNEIK algorithms on popular 8-bit AVR and 32-bit ARMv7-M (Cortex M3/M4) microcontrollers, and also describe an implementation for the open-source RISC-V (RV32I) Instruction Set Architecture (ISA). Our results demonstrate that SNEIK algorithms usually outperform AES and SHA-2/3 on these lightweight targets while having a naturally constant-time design and significantly smaller implementation footprint. The RISC-V architecture is becoming increasingly popular for custom embedded designs that integrate a CPU core with application-specific hardware components. We show that inclusion of two simple custom instructions into the RV32I ISA yields a radical (more than five-fold) speedup of the SNEIK permutation and derived algorithms on that target, allowing us to reach 12.4 cycles/byte SNEIKEN-128 authenticated encryption performance on PQShield's ``Crimson Puppy'' RV32I-based SoC. Our performance measurements are for realistic message sizes and have been made using real hardware. We also offer implementation size metrics in terms of RAM, firmware size, and additional FPGA logic for the custom instruction set extensions.

In cloud security, traditional searchable encryption (SE) requires high computation and communication overhead for dynamic search and update. The clever combination of machine learning (ML) and SE may be a new way to solve this problem. This paper proposes interpretable encrypted searchable neural networks (IESNN) to explore probabilistic query, balanced index tree construction and automatic weight update in an encrypted cloud environment. In IESNN, probabilistic learning is used to obtain search ranking for searchable index, and probabilistic query is performed based on ciphertext index, which reduces the computational complexity of query significantly. Compared to traditional SE, it is proposed that adversarial learning and automatic weight update in response to user's timely query of the latest data set without expensive communication overhead. The proposed IESNN performs better than the previous works, bringing the query complexity closer to $O(\log N)$ and introducing low overhead on computation and communication.

The goal of this paper is to investigate the behavior of the ideal cipher under linear cryptanalysis. The motivation of this work is twofold. First, before a practical cipher can be distinguished from an ideal one, the cryptanalyst must have an accurate understanding of the statistical behavior of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditionally, the models have been based on the average behavior and simplified using other artificial assumptions such as independence of linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson's chi-squared test and finite population correction and shown to work well in small practical examples.

The specification of Bluetooth and Bluetooth Low Energy includes dedicated encryption key negotiation protocols used by two parties to agree on the entropy of encryption keys. In this work, we show that an attacker can manipulate the entropy negotiation of Bluetooth and Bluetooth Low Energy to drastically reduce the encryption key space. We call our attack the Key Negotiation Of Bluetooth (KNOB) attack.

In the case of Bluetooth, we demonstrate that the entropy can be reduced from 16 to 1 Byte. Such low entropy enables the attacker to easily brute force the negotiated encryption keys, decrypt the eavesdropped ciphertext, and inject valid encrypted messages in real-time. For Bluetooth Low Energy, we show that the entropy can still be downgraded from 16 to 7 Bytes, which reduces the attacker's effort to brute force the keys.

We implement and evaluate the KNOB attack on 17 Bluetooth chips (e.g., Intel Broadcom, Apple, and Qualcomm) and 15 Bluetooth Low Energy devices (e.g., Lenovo, Garmin, Samsung, Xiaomi, and Fitbit). Our results demonstrate that all tested devices are vulnerable to the KNOB attack. We discuss legacy and non-legacy compliant countermeasures to neutralize or mitigate the KNOB attack.

$\texttt{CRAFT}$ is a lightweight tweakable block cipher introduced in FSE 2019. One of the main design criteria of $\texttt{CRAFT}$ is the efficient protection of its implementations against differential fault analysis. While the authors of $\texttt{CRAFT}$ provide several cryptanalysis results in several attack models, they do not claim any security of $\texttt{CRAFT}$ against related-key differential attacks. In this paper, we utilize the simple key schedule of $\texttt{CRAFT}$ to propose a systematic method for constructing several repeatable 2-round related-key differential characteristics with probability $2^{-2}$. We then employ one of these characteristics to mount a key recovery attack on full-round $\texttt{CRAFT}$ using $2^{30}$ queries to the encryption oracle and $2^{69}$ encryptions. Additionally, we manage to use 8 related-key differential distinguishers, with 8 related-key differences, in order to mount a key recovery attack on the full-round cipher with $2^{35.17}$ queries to the encryption oracle, $2^{32}$ encryptions and about $2^6$ 64-bit blocks of memory. Furthermore, we present another attack that recovers the whole master key with $2^{36.09}$ queries to the encryption oracle and only $11$ encryptions with $2^7$ blocks of memory using 16 related-key differential distinguishers.

We propose two polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group $G$. The first one is a direct adaptation of the Becker-Coron-Joux (BCJ) algorithm for subset sum to the discrete logarithm setting. The second one significantly improves on this adaptation for all possible weights using a more involved application of the representation technique together with some new Markov chain analysis. In contrast to other low weight discrete logarithm algorithms, our second algorithm's time complexity interpolates to Pollard's $|G|^{\frac 1 2}$ bound for general discrete logarithm instances.

We also introduce a new subset sum algorithm with polynomial memory that improves on BCJ's $2^{0.72n}$ time bound for random subset sum instances $a_1, \ldots, a_n, t \in Z_{2^n}$. Technically, we introduce a novel nested collision finding for subset sum -- inspired by the NestedRho algorithm from Crypto '16 -- that recursively produces collisions. We first show how to instantiate our algorithm with run time $2^{0.649n}$. Using further tricks, we are then able to improve its complexity down to $2^{0.645n}$.

Till now, the only reduction from the module learning with errors problem (MLWE) to the ring learning with errors problem (RLWE) is given by Albrecht $et\ al.$ in ASIACRYPT $2017$. Reductions from search MLWE to search RLWE were satisfactory over power-of-$2$ cyclotomic fields with relative small increase of errors. However, a direct reduction from decision MLWE to decision RLWE leads to a super-polynomial increase of errors and does not work even in the most special cases-\ -power-of-$2$ cyclotomic fields. Whether we could reduce decision MLWE to decision RLWE and whether similar reductions could also work for general fields are still open. In this paper, we give a reduction from decision MLWE with module rank $d$ and computation modulus $q$ in worst-case to decision RLWE with modulus $q^d$ in average-case over any cyclotomic field. Our reduction increases the LWE error rate by a small polynomial factor. As a conclusion, we obtain an efficient reduction from decision MLWE with modulus $q\approx\tilde{O}(n^{5.75})$ and error rate $\alpha\approx\tilde{O}(n^{-4.25})$ in worst-case to decision RLWE with error rate $\Gamma\approx\tilde{O}(n^{-\frac{1}{2}})$ in average-case, hence, we get a reduction from worst-case module approximate shortest independent vectors problem (SIVP$_\gamma$) with approximation parameter $\gamma\approx\tilde{O}(n^{5})$ to corresponding average-case decision RLWE problems. Meanwhile, our result shows that the search variant reductions of Albrecht $et\ al.$ could work in arbitrary cyclotomic field as well. We also give an efficient self-reduction of RLWE problems and a converse reduction from decision MLWE to module SIVP$_{\gamma}$ over any cyclotomic field as improvements of relative results showed by Rosca $et\ al.$ in EUROCRYPT $2018$ and Langlois $et\ al.$ $[\rm{DCC}\ 15]$. Our methods can also be applied to more general algebraic fields $K$, as long as we can find a good enough basis of the dual $R^{\vee}$ of the ring of integers of $K$.

Fujioka, Takashima, Terada and Yoneyama, in their 2018 work on an authenticated key exchange protocol using supersingular isogenies, use new assumptions in their security proof of the scheme. In particular, they define the degree-sensitive and degree-insensitive SI-GDH assumptions and problems. These assumptions include a decision oracle that is used in the security proofs. We give evidence that those assumptions are not well defined. Hence, the security proofs in their paper do not seem to be correct.

Electronic chips in consumer, industrial, and military applications are targeted by untrusted entities in the design and fabrication process, aiming at reverse-engineering and Intellectual Property (IP) piracy. Hardware obfuscation techniques, namely logic locking and IC camouflaging, have been developed to mislead an adversary hoping to reverse engineer the netlist and extract the functionality. However, virtually all existing hardware obfuscation schemes developed over the last decade have been shown to be vulnerable to oracle-guided attacks, e.g., SAT and machine learning attacks. Moreover, most of these schemes rely on an ideal tamper- and read-proof memory to store the key used to unlock the circuit after manufacturing. In this work, we propose two novel cryptographically-secure hardware obfuscation schemes using garbled circuits, which are compatible with current circuit synthesis and fabrication tools. Our first construction does not require any secure hardware with tamper- and read-proof memory. In this case, the security of the obfuscation is guaranteed by Proof-of-Stack blockchain protocols and witness encryption schemes. However, for our second construction, we assume the existence of secure memory in the hardware to achieve higher performance and less overhead. Both constructions are inspired by program obfuscation and one-time program techniques enabling us to selectively encrypt and garble some IP cores during integration as well as manufacturing to prevent IP piracy. Furthermore, with the help of our constructions, we can realize one-time and pay-per-use hardware, where a user can use the electronic circuit for a limited amount of time.

The Charles-Goren-Lauter hash function on isogeny graphs of supersingular elliptic curves was shown to be insecure under collision attacks when the endomorphism ring of the starting curve is known. Since there is no known way to generate a supersingular elliptic curve with verifiably unknown endomorphisms, the hash function can currently only be used after a trusted-setup phase. This note presents a simple modification to the construction of the hash function which, under a few heuristics, prevents said collision attack and permits the use of arbitrary starting curves, albeit with a performance impact of a factor of two.

Timing side-channels are arguably one of the main sources of vulnerabilities in cryptographic implementations. One effective mitigation against timing side-channels is to write programs that do not perform secret-dependent branches and memory accesses. This mitigation, known as ''cryptographic constant-time'', is adopted by several popular cryptographic libraries.

This paper focuses on compilation of cryptographic constant-time programs, and more specifically on the following question: is the code generated by a realistic compiler for a constant-time source program itself provably constant-time? Surprisingly, we answer the question positively for a mildly modified version of the CompCert compiler, a formally verified and moderately optimizing compiler for C. Concretely, we modify the CompCert compiler to eliminate sources of potential leakage. Then, we instrument the operational semantics of CompCert intermediate languages so as to be able to capture cryptographic constant-time. Finally, we prove that the modified CompCert compiler preserves constant-time. Our mechanization maximizes reuse of the CompCert correctness proof, through the use of new proof techniques for proving preservation of constant-time. These techniques achieve complementary trade-offs between generality and tractability of proof effort, and are of independent interest.

Privacy protection has been extensively studied in the current blockchain research field. As representations, Monero and Zerocash have realized completely anonymous and amount-hiding transactions. However, nonregulation can lead to abuse of privacy, which brings about serious risks of breaking laws and committing crimes. Therefore, it is crucial to study the privacy-preserving blockchain systems with regulatory functions. In this paper, we discuss the regulatory model (regulator behavior, user behavior) on the privacy-preserving blockchains from application scenarios and finally select unconditional regulation, static regulation, and self-participation of users as the core principles, which is currently the closest approach to the "decentralization" of regulatable privacy-preserving blockchains. On the basis of the established regulatory model, we first propose a traceable and linkable ring signature scheme (TLRS) by use of classic ring signatures, one-time signatures and zero-knowledge proofs, which realizes the unforgeability, anonymity, linkability, nonslanderability and traceability of users' identities. Moreover, we first propose traceable Borromean range proof (TBoRP) and traceable Bulletproofs range proof (TBuRP) by use of Fiat-Shamir transform and DH assumptions, which realize the completeness, soundness, zero-knowledge and traceability of the transaction amounts. We also apply the newly designed schemes and other zero-knowledge proof protocols to achieve richer regulatory functions.

EMV, also known as Chip and PIN, is the world-wide standard for card-based electronic payment. Its security wavers: over the past years, researchers have demonstrated various practical attacks, ranging from using stolen cards by disabling PIN verification to cloning cards by pre-computing transaction data. Most of these attacks rely on violating certain unjustified and not explicitly stated core assumptions upon which EMV is built, namely that the input device (e.g. the ATM) is trusted and all communication channels are non-interceptable. In addition, EMV lacks a comprehensive formal description of its security. In this work we give a formal model for the security of electronic payment protocols in the Universal Composability (UC) framework. A particular challenge for electronic payment is that one participant of a transaction is a human who cannot perform cryptographic operations. Our goal is twofold. First, we want to enable a transition from the iterative engineering of such protocols to using cryptographic security models to argue about a protocol’s security. Second, we establish a more realistic adversarial model for payment protocols in the presence of insecure devices and channels. We prove a set of necessary requirements for secure electronic payment with regards to our model. We then discuss the security of current payment protocols based on these results and find that most are insecure or require unrealistically strong assumptions. Finally, we give a simple payment protocol inspired by chipTAN and photoTAN and prove its security. Our model captures the security properties of electronic payment protocols with human interaction. We show how to use this to reason about necessary requirements for secure electronic payment and how to develop a protocol based on the resulting guidelines. We hope that this will facilitate the development of new protocols with well-understood security properties.

In side-channel analysis attacks, on-die localized EM monitoring enable high bandwidth measurements of only a relevant part of the Integrated Circuit (IC). This can lead to improved attacks compared to cases where only power consumption is measured. Combined with profiled attacks which utilize a training phase to create precise models of the information leakage, the attacks can become even more powerful. In contrast, localized EM measurements can cause difficulties in applying the learned models as the probe should be identically positioned for both the training and the attack even when the setup was used otherwise in between. Even small differences in the probe position can lead to significant differences in the recorded signals. In this paper we present an automated system to precisely and efficiently reposition the probe when performing repeated measurements. Based on the training IC, we train a machine learning system to return the position of the probe for a given measurement. By taking a small number of measurements on the IC under attack, we can then obtain the coordinates of the measurements and map it to correct the coordinate system. As the target for our practical analyses, we use an STM32L0 ARMM0+ microcontroller with integrated hardware AES.

Secure Multi-Party Computation (MPC) enables a group of $n$ distrusting parties to jointly compute a function using private inputs. MPC guarantees correctness of computation and confidentiality of inputs if no more than a threshold $t$ of the parties are corrupted. Proactive MPC (PMPC) addresses the stronger threat model of a mobile adversary that controls a changing set of parties (but only up to $t$ at any instant), and may eventually corrupt all $n$ parties over a long time.

This paper takes a first stab at developing high-assurance implementations of (P)MPC. We present high-assurance implementations of (P)MPC protocols. We formalize in EasyCrypt, a tool-assisted framework for building high-confidence cryptographic proofs, several abstract and reusable variations of secret sharing and of (P)MPC protocols building on top of them. Using those, we prove a series of abstract theorems for the proactive setting. We implement and perform computer-checked security proofs of concrete instantiations of all required (abstract) protocols in EasyCrypt.

We also develop a new tool-chain to extract high-assurance executable implementations of protocols implemented and verified in EasyCrypt that uses Why3 as an intermediate tool. Using this new tool, we were able to extract code from our (P)MPC formalizations and to conduct a practical evaluation of it by comparing the performance obtained using our approach to the performance of manually implemented versions using Python-based Charm framework for prototyping cryptographic schemes. We argue that the small overhead of our high-assurance executables is a reasonable price to pay for the increased confidence about their correctness and security.

Public key algorithms based on QC-MPDC and QC-LDPC codes for key encapsulation/encryption submitted to NIST post-quantum competition (BIKE, QC-MDPC KEM, LEDA) are vulnerable against reaction attacks based on decoding failures. To protect algorithms, authors propose to limit the key usage, in the extreme (BIKE) to only use ephemeral public keys. In some authenticated protocols, we need to combine each key with a signature, which can lead to increased traffic overhead, especially given large signature sizes of some of the proposed post-quantum signature schemes. We propose to combine ephemeral public keys with a simple Merkle-tree to obtain a server authenticated key encapsulation/transport suitable for TLS-like handshake protocols.

The stream cipher FOUNTAIN was introduced in April 2019 as one of the candidates in the NIST lightweight crypto standardization process. In this paper we introduce a slide attack that leads to the construction of 32 relations on key bits, with time complexity around $17\times 2^{80}$. The success of the attack is around 98%. We also present some properties of the internal state transitions that allow the identification of (key-iv-ad) input data that produce identical ciphertexts, with probability of $2^{-32}$.

Side-channel analysis and fault injection attacks are two typical threats to cryptographic implementations, especially in modern embedded devices. Thus there is an insistent demand for dual side-channel and fault injection protections. As it is known, masking is a kind of provable countermeasure against side-channel attacks. Recently, inner product masking (IPM) was proposed as a promising higher-order masking scheme against side-channel analysis, but not for fault injection attacks. In this paper, we devise a new masking scheme named IPM-FD. It is built on IPM, which enables fault detection. This novel masking scheme has three properties: the security orders in the word-level probing model, bit-level probing model, and the number of detected faults. IPM-FD is proven secure both in the word-level and in the bit-level probing models, and allows for end-to-end fault detection against fault injection attacks.

Furthermore, we illustrate its security order by interpreting IPM-FD as a coding problem then linking it to one defining parameters of linear code, and show its implementation cost by applying IPM-FD to AES-128.

Logic encryption, a method to lock a circuit from unauthorized use unless the correct key is provided, is the most important technique in hardware IP protection. However, with the discovery of the SAT attack, all traditional logic encryption algorithms are broken. New algorithms after the SAT attack are all vulnerable to structural analysis unless a provable obfuscation is applied to the locked circuit. But there is no provable logic obfuscation available, in spite of some vague resorting to logic resynthesis. In this paper, we formulate and discuss a trilemma in logic encryption among locking robustness, structural security, and encryption efficiency, showing that pre-SAT approaches achieve only structural security and encryption efficiency, and post-SAT approaches achieve only locking robustness and encryption efficiency. There is also a dilemma between query complexity and error number in locking. We first develop a theory and solution to the dilemma in locking between query complexity and error number. Then, we provide a provable obfuscation solution to the dilemma between structural security and locking robustness. We finally present and discuss some results towards the resolution of the trilemma in logic encryption.

As an extension of identity-based encryption (IBE), revocable hierarchical IBE (RHIBE) supports both key revocation and key delegation simultaneously, which are two important functionalities for cryptographic use in practice. Recently in PKC 2019, Katsumata et al. constructed the first lattice-based RHIBE scheme with decryption key exposure resistance (DKER). Such constructions are all based on bilinear or multilinear maps before their work. In this paper, we simplify the construction of RHIBE scheme with DKER provided by Katsumata et al. With our new treatment of the identity spaces and the time period space, there is only one short trapdoor base in the master secret key and in the secret key of each identity. In addition, we claim that some items in the keys can also be removed due to the DKER setting. Our first RHIBE scheme in the standard model is presented as a result of the above simplification. Furthermore, based on the technique for lattice basis delegation in fixed dimension, we construct our second RHIBE scheme in the random oracle model. It has much shorter items in keys and ciphertexts than before, and also achieves the adaptive-identity security under the learning with errors (LWE) assumption.