International Association
for Cryptologic Research

In this paper, we propose EM side-channel attacks with carefully constructed ciphertext on Kyber, a lattice-based key encapsulation mechanism, which is a candidate of NIST Post-Quantum Cryptography standardization project. We demonstrate that specially chosen ciphertexts allow an adversary to modulate the leakage of a target device and enable full key extraction with a small number of traces through simple power analysis. Compared to prior research, our techniques require a lower number of traces and avoid the need for template attacks. We practically evaluate our methods using both a clean reference implementation of Kyber and the ARM-optimized pqm4 library. For the reference implementation, we target the leakage of the output of the inverse NTT computation and recover the full key with only four traces. For the pqm4 implementation, we develop a message-recovery attack that leads to extraction of the full secret-key with between eight and 960 traces (or 184 traces for recovering 98% of the secret-key), depending on the compiler optimization level. We discuss the relevance of our findings to other lattice-based schemes and explore potential countermeasures.

We introduce a new cryptographic primitive, a lossy correlation-intractable hash function, and use it to soundly instantiate the Fiat-Shamir transform for the general interactive sumcheck protocol, assuming sub-exponential hardness of the Learning with Errors (LWE) problem. By combining this with the result of Choudhuri et al. (STOC 2019), we show that $\#\mathsf{SAT}$ reduces to end-of-metered line, which is a $\mathsf{PPAD}$-complete problem, assuming the sub-exponential hardness of LWE.

The Hamming Quasi-Cyclic (HQC) proposal is a promising candidate in the second round of the NIST Post-Quantum cryptography Standardization project. It features small public key sizes, precise estimation of its decryption failure rates and contrary to most of the code-based systems, its security does not rely on hiding the structure of an error-correcting code. In this paper, we propose the first power side-channel attack on the Key Encapsulation Mechanism (KEM) version of HQC. Our attack utilizes a power side-channel to build an oracle that outputs whether the BCH decoder in HQC's decryption algorithm corrects an error for a chosen ciphertext. Based on the decoding algorithm applied in HQC, it is shown how to design queries such that the output of the oracle allows to retrieve a large part of the secret key. The remaining part of the key can then be determined by an algorithm based on linear algebra. It is shown in experiments that less than 10000 measurements are sufficient to successfully mount the attack on the HQC reference implementation running on an ARM Cortex-M4 microcontroller.

The University of Luxembourg invites applications from M.Sc. holders in the general area of applied cryptography. Cryptolux.org is a team of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy, network security, cryptographic blockchains and is led by Prof. Alex Biryukov. We are affiliated to the Department of Computer Science (DCS) and to the interdisciplinary Security and Trust center (SnT).

Area (potential topics of the thesis)

• Cryptanalysis and design of cryptographic primitives
• Lightweight block ciphers, hash functions, authenticated encryption schemes
• Privacy Enhancing Technology (Tor-like networks, privacy for cryptocurrencies, blockchains)
• Blockchain Cryptography
• Design of proofs of work, resource-hard functions, commitment schemes
• Side-channel attacks and countermeasures
• White-box cryptography

The University offers a Ph.D. study program with an Initial contract of 36 months, with a further possible 1-year extension if required. The University offers competitive salaries and is an equal opportunity employer. You will work in an exciting international environment and will have a chance to participate in the development of a newly created research center.

Starting date 15-Oct-2020 or later upon agreement. Early submission is encouraged; applications will be processed upon receipt.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://recruitment.uni.lu/en/details.html?nPostingId=52476&nPostingTargetId=71379&id=QMUFK026203F3VBQB7V7VV4S8&LG=UK&ma

The University of Luxembourg, Computer Science department and Centre for Security, Reliability and Trust (SnT) invite applications from Ph.D. holders in the general area of Applied Cryptography. SnT is carrying out interdisciplinary research in secure, reliable and trustworthy ICT. CryptoLux/SnT team is currently doing research in cryptography, distributed ledgers and privacy.

Research area The successful candidate will join the CryptoLux research team led by Prof. Alex Biryukov. He or she will contribute to a research project entitled "Security, Scalability, and Privacy in Blockchain Applications and Smart Contracts (FINCRYPT)", which is funded by the Luxembourg National Research Fund (FNR). Candidates with proven research track record in one or more of the following areas are particularly encouraged to apply:

Applied Cryptography (SK or PK, PoWs, efficient ZK proofs, etc.)
Crypto-currencies, smart-contracts, financial cryptography, blockchains
Privacy enhancing technologies
Distributed consensus protocols

Your Profile

• A Ph.D. degree in Computer Science, Applied Mathematics or a related field
• Competitive research record in cryptography or information security (at least one paper in top 10 IT security/crypto conferences)
• Strong mathematical and algorithmic CS background, interest in economics/finance - a plus
• Good skills in programming and scripting languages
• Fluent written and verbal communication skills in English are mandatory

Starting date 1-Oct-2020 or later upon agreement. Due to Covid, EU citizens or residents will be given preference. Position is for 12 month with possible extension.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://recruitment.uni.lu/en/details.html?nPostingId=52476&nPostingTargetId=71379&id=QMUFK026203F3VBQB7V7VV4S8&LG=UK&ma

We are looking for an excellent, motivated, post-doctoral researcher to work in the area of information security and cryptography. The post-doctoral researcher will join Katerina Mitrokotsa's research group (Chair of Cyber Security), working in the area of information and communication security with a focus on authentication protocols, verifiable delegation of computation, and secure multi-party computation. The position is available for one plus one year after a successful review evaluation.

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: http://direktlink.prospective.ch/?view=7716a2ff-927c-4fb5-aa35-90e310e2f4f3

We are looking for an excellent, motivated, self-driven doctoral student to work in the area of information security and cryptography. The position is within the group of Prof. Katerina Mitrokotsa (Chair of Cyber Security) who is doing research in cryptographic protocols that guarantee reliable authentication, privacy-preservation and verifiable delegation of computation. The topic of this project is focusing on investigating security and privacy issues for resource-constrained devices (e.g., sensors) that rely on external untrusted servers in order to perform computations. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The overall aim of the PhD position will be to design and evaluate provably secure cryptographic protocols for privacy-preserving authentication and verifiable delegation of computation protocols. The research shall also consider the case where multiple clients outsource jointly computations to untrusted cloud servers.

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: http://direktlink.prospective.ch/?view=2d5b5bd0-e017-4917-90bb-14f3b6efe9c4

Event date: 17 May to 21 May 2021
Submission deadline: 1 December 2020
Notification: 17 February 2021

Registration has now opened for Crypto 2020. There are four affiliated events associated with the conference that occur on Friday-Sunday before the conference, and information on these has been updated.

A common primitive in election and auction protocols is plaintext equivalence test (PET) in which two ciphertexts are tested for equality of their plaintexts, and a verifiable proof of the test's outcome is provided. The most commonly-cited PETs require at least one honest party, but many applications claim universal verifiability, at odds with this requirement. If a test that relies on at least one honest participant is mistakenly used in a place where universally verifiable proof is needed, then a collusion by all participants can insert a forged proof of equality into the tallying transcript. We show this breaks universal verifiability for the JCJ/Civitas scheme among others, because the only PETs they reference are not universally verifiable. We then demonstrate how to fix the problem.

Minrank problem is investigated as a problem related to a rank attack in multivariate cryptography and decoding of a rank code in coding theory. Recently, the Kipnis-Shamir method for solving this problem has been made significant progress due to Verbel et al. As this method reduces the problem to the MQ problem that asks for a solution of a system of quadratic equations, its complexity depends on the solving degree of a quadratic system deduced from the method. A theoretical value introduced by Verbel et al. approximates the minimal solving degree of the quadratic systems in the method although their value is defined under a certain limit for a considering system. A quadratic system outside their limitation often has the larger solving degree, but its solving complexity is not necessary larger since it has a smaller number of variables and equations. Thus, in order to discuss the best complexity of the Kipnis-Shamir method, we need a theoretical value approximating the solving degree of each deduced quadratic system. A quadratic system deduced from the Kipnis-Shamir method has a multi-degree always, and its solving complexity is influenced by this property. In this paper, we introduce a theoretical value defined by such a multi-degree and show it approximates the solving degree of each quadratic system. Thus we are able to compare the systems in the method and to discuss the best complexity. As its application, in the Minrank problem from the rank attack using the Kipnis-Shamir method against Rainbow, we show a case that a quadratic system outside Verbel et al.'s limitation is the best. Consequently, by using our estimation, the complexities of the attack against Rainbow parameter sets Ia, IIIc and Vc are improved as $2^{160.6}, 2^{327.9}$ and $2^{437.0}$, respectively.

In cloud computing, multiple users can share the same physical machine that can potentially leak secret information, in particular when the memory de-duplication is enabled. Flush+Reload attack is a cache-based attack that makes use of resource sharing. T-table implementation of AES is commonly used in the crypto libraries like OpenSSL. Several Flush+Reload attacks on T-table implementation of AES have been proposed in the literature which requires a notable number of encryptions. In this paper, we present a technique to enhance the Flush+Reload attack on AES in the ciphertext-only scenario by significantly reducing the number of needed encryptions in both native and cross-VM setups. In this paper, we focus on finding the wrong key candidates and keep the right key by considering only the cache miss event. Our attack is faster than previous Flush+Reload attacks. In particular, our method can speed-up the Flush+Reload attack in cross-VM environment significantly. To verify the theoretical model, we implemented the proposed attack.

In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for $n$ parties, tolerating a computationally unbounded adversary, capable of corrupting up to $t < \frac{n}{3}$ parties. Our protocol needs a communication of ${\cal O}(n^4)$ field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of ${\cal O}(n^5)$ field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.

In this paper we cryptanalyze a recently proposed signature scheme consisting in a translation of the Lyubashevsky framework to the coding theory, whose security is based on the hardness of decoding low weight errors in the Hamming metric. We show that each produced signature leaks information about the secret key and that, after the observation of a bunch of signatures, the secret key can be fully recovered with simple linear algebra. We conservatively assess the complexity of our proposed attack and show that it grows polynomially in the scheme parameters; numerical simulations are used to confirm our analysis. Our results show that the weakness of the scheme is intrinsic by design, and that security cannot be restored by a mere change in the parameters.

The usage of deep learning in profiled side-channel analysis requires a careful selection of neural network hyperparameters. In recent publications, different network architectures have been presented as efficient profiled methods against protected AES implementations. Indeed, completely different convolutional neural network models have presented similar performance against public side-channel traces databases. In this work, we analyze how the choice of weight initializers influences deep neural networks' performance in the profiled side-channel analysis. Our results show that different weight initializers provide radically different behavior. We observe that even high-performing initializers can reach significantly different performance when conducting multiple training phases. Finally, we found that this hyperparameter is more dependent on the choice of dataset than other, commonly examined, hyperparameters. When evaluating the connections with other hyperparameters, the biggest connection is observed with activation functions.

In this paper, we propose a new heuristic algorithm to search efficient implementations (in terms of Xor count) of linear layers used in symmetric-key cryptography. It is observed that the implementation cost of an invertible matrix is related to its matrix decomposition if sequential-Xor (s-Xor) metric is considered, thus reducing the implementation cost is equivalent to constructing an optimized matrix decomposition. The basic idea of this work is to find various matrix de- compositions for a given matrix and optimize those decompositions to pick the best implementation. In order to optimize matrix decompositions, we present several ma- trix multiplication rules over F2, which are proved to be very powerful in reducing the implementation cost. We illustrate this heuristic by searching implementations of several matrices proposed recently and matrices already used in block ciphers and Hash functions, and the results show that our heuristic performs equally good or outperforms Paar’s and Boyar-Peralta’s heuristics in most cases.

Recently introduced federated learning is an attractive framework for the distributed training of deep learning models with thousands of participants. However, it can potentially be used with malicious intent. For example, adversaries can use their smartphones to jointly train a classifier for extracting secret keys from the smartphones' SIM cards without sharing their side-channel measurements with each other. With federated learning, each participant might be able to create a strong model in the absence of sufficient training data. Furthermore, they preserve their anonymity. In this paper, we investigate this new attack vector in the context of side-channel attacks. We compare the federated learning, which aggregates model updates submitted by N participants, with two other aggregating approaches: (1) training on combined side-channel data from N devices, and (2) using an ensemble of N individually trained models. Our first experiments on 8-bit Atmel ATxmega128D4 microcontroller implementation of AES show that federated learning is capable of outperforming the other approaches.

In this short report, we present a simple yet effective inter-session replay attack against the Diffie-Hellman style private set intersection protocol (cf. [Mea86]). The attack is indistinguishable from ordinary protocol execution, and yet allows the attacker to learn the cardinality of the intersection of honest party's input sets. This kind of attack demonstrates the inadequacy of semi-honest security guarantee when facing more serious adversarial threats, and highlights the necessity for security augmentation of protocols derived from [Mea86].

Code-based public-key cryptosystems are promising candidates for standardisation as quantum-resistant public-key cryptographic algorithms. Their security is based on the hardness of the syndrome decoding problem. Computing the syndrome in a finite field, usually $\mathbb{F}_2$ , guarantees the security of the constructions. We show in this article that the problem becomes considerably easier to solve if the syndrome is computed in $\mathbb{N}$ instead. By means of laser fault injection, we illustrate how to force the matrix-vector product in $\mathbb{N}$ by corrupting specific instructions, and validate it experimentally. To solve the syndrome decoding problem in $\mathbb{N}$, we propose a reduction to an integer linear programming problem. We leverage the computational efficiency of linear programming solvers to obtain real time message recovery attacks against all the code-based proposals to the NIST Post-Quantum Cryptography standardisation challenge. We perform our attacks on worst-case scenarios, i.e. random binary codes, and retrieve the initial message within minutes on a desktop computer. When considering parameters of the code-based submissions to the NIST PQC standardisation challenge, all of them can be attacked in less than three minutes.

Event date: 17 December to 21 December 2020
Submission deadline: 24 July 2020
Notification: 25 September 2020