## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

There is currently a problem with the jobs channel, and new jobs listings are not appearing here. Please see the jobs page.

#### 19 August 2019

###### M Sazadur Rahman, Adib Nahiyan, Sarah Amir, Fahim Rahman, Farimah Farahmandi, Domenic Forte, Mark Tehranipoor

ePrint Report
Logic locking has emerged as a promising solution against IP piracy and modification by untrusted entities in the integrated circuit design process. However, its security is challenged by boolean satisfiability (SAT) based attacks. Criteria that are critical to SAT attack success on obfuscated circuits includes scan architecture access to the attacker and/or that the circuit under attack is combinational. To address this issue, we propose a dynamically-obfuscated scan chain (DOSC) technique in resisting SAT attack in an obfuscated sequential design by restricting scan access only to authorized users.

###### Navid Ghaedi Bardeh

ePrint Report
In this paper, we study the results of the recently proposed exchange attack in an adaptive setting. As expected, it leads to present a better 6-round key-independent distinguisher in terms of data and computational complexities. More specifically, our 6-round adaptive distinguisher requires $2^{83}$ chosen plaintexts and $2^{83}$ adaptively chosen ciphertexts and has a computational cost of $2^{83}$ encryption.

###### Max Hoffmann, Michael Klooß, Andy Rupp

ePrint Report
Zero-knowledge arguments have become practical, and widely used,
especially in the world of Blockchain, for example in Zcash.

This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimize proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al.\ (EUROCRYPT '16) and Bünz et al. (S\&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree $n^2$ polynomial $f(X)$ can now be ``evaluated'' with at most $2n$ quadratic constraints.

Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting.

Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.

This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimize proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al.\ (EUROCRYPT '16) and Bünz et al. (S\&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree $n^2$ polynomial $f(X)$ can now be ``evaluated'' with at most $2n$ quadratic constraints.

Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting.

Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.

###### Ling Ren

ePrint Report
This paper gives a simple analysis of Nakamoto consensus.

#### 18 August 2019

###### Handan Kılınç Alper

ePrint Report
Ouroboros Praos is a proof of stake based blockchain protocol. One of its security
assumptions is parties are synchronized i.e., all of them knows when the protocol passes
a new state. However, it is not easy to have such a protocol in real life, especially in a
decentralized network. Therefore, we construct a new version of Ouroboros Praos by composing a new protocol called Relative Time protocol. We call the new version Ouroboros
Clepsydra. At the end of the relative time protocol, a party learns the approximate state
of the protocol based on the median of arrival times of messages sent by the other parties
and adjusts its local clock based on it. The relative time protocol does not add any new
computation to the other parties. They even do not realize that they are part of the relative time protocol. In order to prove Ouroboros Clepsydrain the Universally Composable
(UC) model, we define a general UC model to capture the notion of relative time. We
remove the synchronization assumption in Ouroboros Clepsydra and show that Ouroboros
Clepsydra is a secure proof of stake blockchain protocol in the UC model.

###### Eman Salem Alashwali, Pawel Szalachowski, Andrew Martin

ePrint Report
Experience shows that most researchers and developers tend to treat plain-domains (those that are not prefixed with “www” sub-domains, e.g. “example.com”) as synonyms for their equivalent www-domains (those that are prefixed with “www” sub-domains, e.g. “www.example.com”). In this paper, we analyse datasets of nearly two million plain-domains against their equivalent www-domains to answer the following question: Do plain-domains and their equivalent www-domains differ in TLS security configurations and certificates? If so, to what extent? Our results provide evidence of an interesting phenomenon: plain-domains and their equivalent www-domains differ in TLS security configurations and certificates in a non-trivial number of cases. Furthermore, www-domains tend to have stronger security configurations than their equivalent plain-domains. Interestingly, this phenomenon is more prevalent in the most-visited domains than in randomly-chosen domains. Further analysis of the top domains dataset shows that 53.35% of the plain-domains that show one or more weakness indicators (e.g. expired certificate) that are not shown in their equivalent www-domains perform HTTPS redirection from HTTPS plain-domains to their equivalent HTTPS www-domains. Additionally, 24.71% of these redirections contains plain-text HTTP intermediate URLs. In these cases, users see the final www-domains with strong TLS configurations and certificates, but in fact, the HTTPS request has passed through plain-domains that have less secure TLS configurations and certificates. Clearly, such a set-up introduces a weak link in the security of the overall interaction.

###### Nasrollah Pakniat

ePrint Report
Certificateless cryptography can be considered as an intermediate solution to overcome the issues in traditional public key infrastructure (PKI) and identity-based public key cryptography (ID-PKC). There exist a vast number of certificateless signature (CLS) schemes in the literature; however, most of them are not efficient enough to be utilized in limited resources environments such as Internet of things (IoT) or Healthcare Wireless Sensor Networks (HWSN). Recently, two lightweight CLS schemes have been proposed by Karati et al. and Kumar et al. to be employed in IoT and HWSNs, respectively. While both schemes are claimed to be existentially unforgeable, in this paper, we show that both these signatures can easily be forged. More specifically, it is shown that 1) in Karati et al.'s scheme, a type 1 adversary, considered in certificateless cryptography, can generate a valid partial private key corresponding to any user of its choice and as a consequence, it can forge any users' signature on any message of its choice, and 2) in Kumar et al.'s scheme, both types of adversaries which are considered in certificateless cryptography are able to forge any signer's signature on an arbitrary message.

###### Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Trav

ePrint Report
Homomorphic Encryption is a breakthrough technology which can enable private cloud storage and computation solutions, and many applications have been described in the literature in the last few years. But before Homomorphic Encryption can be adopted in medical, health, and financial sectors to protect data and patient and consumer privacy, it will have to be standardized, most likely by multiple standardization bodies and government agencies. An important part of standardization is broad agreement on security levels for varying parameter sets. Although extensive research and benchmarking has been done in the research community to establish the foundations for this effort, it is hard to find all the information in one place, along with concrete parameter recommendations for applications and deployment.
This document is the first Homomorphic Encryption Standard (HES) approved by the Homomorphicencryption.org community in 2018. It captures the collective knowledge on the state of security of these schemes, specifies the schemes, and recommends a wide selection of parameters to be used for homomorphic encryption at various security levels. We describe known attacks and their estimated running times in order to make these security parameter recommendations.

###### Gaëtan Leurent, Ferdinand Sibleyras

ePrint Report
The iterated Even-Mansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2-round Even-Mansour construction with a single key. This is the most minimal construction that offers security beyond the birthday bound: there is a security proof up to $2^{2n/3}$ evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly $2^n/n$ operations.
We show that attacking this scheme with block size $n$ is related to the 3-XOR problem with element size $w = 2n$, an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least $2^{w/3}$ queries, and the best known algorithms require around $2^{w/2} / w$ operations: this roughly matches the known bounds for the 2-round Even-Mansour scheme. Using this link we describe new attacks against the 2-round Even-Mansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than $2^n$ .
From a practical standpoint, previous works with a data and/or memory complexity close to $2^n$ are unlikely to be more efficient than a simple brute-force search over the key. Our best algorithm requires just $\lambda n$ known plaintext/ciphertext pairs, for some constant $0 < \lambda < 1$, $2^n/\lambda n$ time, and $2^{\lambda n}$ memory. For instance, with $n = 64$ and $\lambda = 1/2$, the memory requirement is practical, and we gain a factor 32 over brute-force search. We also describe an algorithm with asymptotic complexity $O(2^n (\ln^2{n/n^2})$, improving the previous asymptotic complexity of $O(2^n/n)$, using a variant of the 3-SUM algorithm of Baran, Demaine, and Patrascu.

###### Sayandeep Saha, Debapriya Basu Roy, Arnab Bag, Sikhar Patranabis, Debdeep Mukhopadhyay

ePrint Report
Fault attacks (FA) are one of the potent practical threats
to modern cryptographic implementations. Over the years the FA tech-
niques have evolved, gradually moving towards the exploitation of device-
centric properties of the faults. In this paper, we exploit the fact that
activation and propagation of a fault through a given combinational cir-
cuit (i.e. observability of a fault) is data dependent. Next, we show that
this property of combinational circuits leads to powerful fault attacks
even for implementations having dedicated and provably secure protec-
tions against both power and fault-assisted vulnerabilities. The attacks
found in this work are applicable even if the fault injection is made at
the middle rounds of a block cipher, which are out of reach for most
of the other existing fault analysis strategies. Quite evidently, they also
work for a known plaintext scenario. Moreover, the middle round attacks
are entirely blind in the sense that no access to the ciphertexts (cor-
rect/faulty) or plaintexts are required. The adversary is only assumed
to have the power of repeating an unknown plaintext several times. Ex-
perimental validation over software implementations of PRESENT and
AES proves the efficacy of the proposed attacks.

###### Markku-Juhani O. Saarinen

ePrint Report
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.

###### Kai Chen; Zhongrui Lin; Jian Wan; Chungen Xu.

ePrint Report
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.

###### Mohsin Khan, Kaisa Nyberg

ePrint Report
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.

###### Daniele Antonioli, Nils Ole Tippenhauer, Kasper Rasmussen

ePrint Report
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.

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.

###### Muhammad ElSheikh, Amr M. Youssef

ePrint Report
$\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.

###### Andre Esser, Alexander May

ePrint Report
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}$.

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}$.

###### Yang Wang, Mingqiang Wang

ePrint Report
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$.

###### Samuel Dobson, Steven D. Galbraith

ePrint Report
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.

###### Fatemeh Ganji, Shahin Tajik, Domenic Forte, Jean-Pierre Seifert

ePrint Report
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.

###### Lorenz Panny

ePrint Report
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.