International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

01:17 [Pub][ePrint] Short Schnorr signatures require a hash function with more than just random-prefix resistance, by Daniel R. L. Brown

  Neven, Smart and Warinschi (NSW) proved, in the generic group model, that full-length Schnorr signatures require only random-prefix resistant hash functions to resist passive existential forgery.

Short Schnorr signatures halve the length of the hash function, and

have been conjectured to provide a similar level of security. The

NSW result is too loose to provide a meaningful security for short

Schnorr signatures, but Neven, Smart and Warinschi conjecture that

this is mere artefact of the proof technique, and not an essential

deficiency of the short Schnorr signatures. In particular, this

amounts to a conjecture that short Schnorr signature are secure

under the same set of assumptions, namely random-prefix resistance

of the hash function.

This report provides a counterexample to the latter conjecture, in

other words, a separation result. It finds a hash function that

seems to suggest random-prefix resistance does not suffice for short

Schnorr signatures. In other words, the loose reduction implicit

in the NSW theorem is as tight as possible.

Obviously, this result does not preclude the possibility of another

proof for short Schnorr signatures, based on different hash function

security properties such as preimage resistance.

01:17 [Pub][ePrint] Stealing Keys from PCs by Radio: Cheap Electromagnetic Attacks on Windowed Exponentiation, by Daniel Genkin and Lev Pachmanov and Itamar Pipman and Eran Tromer

  We present new side-channel attacks on implementations of RSA and ElGamal encryption. The attacks can extract secret keys using a very low measurement bandwidth (a frequency band of less than 100 kHz, residing under 2 MHz) even when attacking multi-GHz CPUs. They targets implementation that use the popular sliding-window and fixed-window (m-ary) modular exponentiation.

We demonstrate the attacks\' feasibility by extracting keys from laptop computers running GnuPG, using a nonintrusive measurement of electromagnetic emanations for a few seconds from a range of 50 cm. The measurement is made using cheap and readily-available components, such as a Software Defined Radio USB dongle or a consumer-grade radio receiver. The measurement equipment is compact and can operate untethered and concealed, e.g., inside pita bread.

The attack uses a few non-adaptive chosen ciphertexts to trigger the occurrence of specially-structured values inside the sliding-window or fixed-window exponentiation routine. These special values cause observable fluctuations in the electromagnetic field surrounding the laptop, in a way that depends on the key-bit pattern within the sliding window. The secret key can be deduced from these fluctuations, through suitable signal processing and cryptanalysis.

01:17 [Pub][ePrint] Authenticated Network Time Synchronization, by Benjamin Dowling and Douglas Stebila and Greg Zaverucha

  The Network Time Protocol (NTP) is used by many network-connected devices to synchronize device time with remote servers. Many security features depend on the device knowing the current time, for example in deciding whether a certificate is still valid. Currently, most services implement NTP without authentication, and the authentication mechanisms available in the standard have not been formally analyzed, require a pre-shared key, or are known to have cryptographic weaknesses. In this paper we design an authenticated version of NTP, called ANTP, a generic construction which protects against desynchronization attacks. To make ANTP suitable for large-scale deployments, it is designed to minimize server-side public-key operations and requires no server-side state. Additionally, ANTP ensures that authenticity does not degrade accuracy. Authentication adds no latency to server responses, by using the fact that authentication information can arrive in a separate, subsequent message. We define a novel provable security framework involving adversary control of time, and use the framework to analyze ANTP. The framework may also be used to analyze other secure time synchronization protocols.

22:17 [Pub][ePrint] Analysis of Impossible, Integral and Zero-Correlation Attacks on Type-II Generalized Feistel Networks using the Matrix Method, by Céline Blondeau and Marine Minier

  While some recent publications have shown some strong relations between impossible differential and zero-correlation distinguishers as well as between zero-correlation and integral distinguishers, we analyze in this paper some relation between the underlying key-recovery attacks against Type-II Feistel networks. The

results of this paper are build on the relation presented at ACNS 2013.

In particular, using a matrix representation of the round function, we show that we can not only find impossible, integral and multidimensional zero-correlation distinguishers but also find the key-words involved in the underlined key-recovery attacks. Based on this representation, for matrix-method-derived strongly-related zero-correlation and impossible distinguishers, we show that the key-words involved in the zero-correlation

attack is a subset of the key-words involved in the impossible differential attack. Other relations between the key-words involved in zero-correlation, impossible and integral attacks are also extracted.

Also we show that in this context the data complexity of the multidimensional zero-correlation attack is larger than that of the other two attacks.

22:17 [Pub][ePrint] Multi-Client Verifiable Computation with Stronger Security Guarantees, by S. Dov Gordon and Jonathan Katz and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou

  Choi et al. (TCC 2013) introduced the notion of multi-client verifiable computation (MVC) in which a set of clients outsource to an untrusted server the computation of a function f over their collective inputs in a sequence of time periods. In that work, the authors defined and realized multi-client verifiable computation satisfying soundness against a malicious server and privacy against the semi-honest corruption of a single client. Very recently, Goldwasser et al. (Eurocrypt 2014) provided an alternative solution relying on multi-input functional encryption.

Here we conduct a systematic study of MVC, with the goal of satisfying stronger security requirements. We begin by introducing a simulation-based notion of security that provides a unified way of defining soundness and privacy, and automatically captures several attacks not addressed in previous work. We then explore the feasibility of achieving this notion of security. Assuming no collusion between the server and the clients, we demonstrate a protocol for multi-client verifiable computation that achieves strong security in several respects. When server-client collusion is possible, we show (somewhat surprisingly) that simulation-based security cannot be achieved in general, even assuming semi-honest behavior.

22:17 [Pub][ePrint] Harder, Better, Faster, Stronger - Elliptic Curve Discrete Logarithm Computations on FPGAs, by Erich Wenger and Paul Wolfger

  Computing discrete logarithms takes time. It takes time to develop new algorithms, choose the best algorithms, implement these algorithms correctly and efficiently, keep the system running for several months, and, finally, publish the results. In this paper, we present a highly performant architecture that can be used to compute discrete logarithms of Weierstrass curves defined over binary fields and Koblitz curves using FPGAs. We used the architecture to compute for the first time a discrete logarithm of the elliptic curve \\texttt{sect113r1}, a previously standardized binary curve, using 10 Kintex-7 FPGAs. To achieve this result, we investigated different iteration functions, used a negation map, dealt with the fruitless cycle problem, built an efficient FPGA design that processes 900 million iterations per second, and we tended for several months the optimized implementations running on the FPGAs.

22:17 [Pub][ePrint] Security of the AES with a Secret S-box, by Tyge Tiessen and Lars R. Knudsen and Stefan Kölbl and Martin M. Lauridsen

  How does the security of the AES change when the S-box is replaced

by a secret S-box, about which the adversary has no knowledge? Would it be safe to reduce the number of encryption rounds?

In this paper, we demonstrate attacks based on integral cryptanalysis

which allows to recover both the secret key and the secret S-box for respectively four, five,

and six rounds of the AES. Despite the significantly larger amount of secret information which an

adversary needs to recover, the attacks are very efficient with

time/data complexities of $2^{17}/2^{16}$, $2^{38}/2^{40}$ and $2^{90}/2^{64}$, respectively.

Another interesting aspect of our attack is that it works both as chosen plaintext and as chosen ciphertext attack. Surprisingly, the chosen ciphertext variant has a significantly lower time complexity in the attacks on four and five round, compared to the respective chosen plaintext attacks.

22:17 [Pub][ePrint] Observations on the SIMON block cipher family, by Stefan Kölbl and Gregor Leander and Tyge Tiessen

  In this paper we analyze the general class of functions underlying the SIMON block cipher. In particular, we derive efficiently computable and easy to implement expressions for the exact differential and linear behavior of SIMON-like round function. Using those expressions we investigate a large set of natural SIMON variants with respect to the most important cryptographic criteria. Interestingly, the NSA\'s choice for the parameters are not always optimal.

Using a computer aided approach based on SAT/SMT solvers we are able to find both the optimal differential and linear characteristics for variants of SIMON and can also give better estimates on the

probability of differentials. As a result of this analysis we propose different sets of rotation constants, which feature better properties on some criteria, and might be interesting for further analysis.

22:17 [Pub][ePrint] New Attacks on Feistel Structures with Improved Memory Complexities, by Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir

  Feistel structures are an extremely important and extensively researched type of cryptographic schemes. In this paper we describe improved attacks on Feistel structures with more than 4 rounds.

We achieve this by a new attack that combines the main benefits of

meet-in-the-middle attacks (which can reduce the time complexity by

comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n-bit inputs with seven independent round keys of n/2 bits each), a MITM attack can use (2^1.5n ,2^1.5n) time and memory, while dissection requires (2^2n, 2^n) time and memory. Our new attack requires only (2^1.5n, 2^n) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multicollisions and differential properties deep in the structure in order to further reduce the memory complexity.

Our new attacks are not just theoretical generic constructions - in fact, we can use them to improve the best known attacks on several concrete cryptosystems such as CAST-128 (where we reduce the memory complexity from 2^111 to 2^64) and DEAL-256 (where we reduce the memory complexity from 2^200 to 2^144), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures - for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of 2^16.

22:17 [Pub][ePrint] High Precision Fault Injections on the Instruction Cache of ARMv7-M Architectures, by Lionel Rivière and Zakaria Najm and Pablo Rauzy and Jean-Luc Danger and Julien Bringer and Laurent Sauvage

  Hardware and software of secured embedded systems are prone to physical attacks.

In particular, fault injection attacks revealed vulnerabilities on the data and the control flow

allowing an attacker to break cryptographic or secured algorithms implementations.

While many research studies concentrated on successful attacks on the data flow, only a few targets the instruction flow.

In this paper, we focus on electromagnetic fault injection (EMFI) on the control flow,

especially on the instruction cache.

We target the very widespread (smartphones, tablets, settop-boxes, health-industry monitors and sensors, etc.) ARMv7-M architecture.

We describe a practical EMFI platform and present a methodology providing high control level and high reproducibility over fault injections.

Indeed, we observe that a precise fault model occurs in up to 96\\% of the cases.

We then characterize and exhibit this practical fault model on the cache that is not yet considered in the literature.

We comprehensively describe its effects and show how it can be used to reproduce well known fault attacks.

Finally, we describe how it can benefits attackers to mount new powerful attacks or simplify existing ones.

22:17 [Pub][ePrint] On the Effectiveness of the Remanence Decay Side-Channel to Clone Memory-based PUFs, by Yossef Oren and Ahmad-Reza Sadeghi and Christian Wachsmann

  We present a side-channel attack based on remanence decay in volatile memory and show how it can be exploited effectively to launch a non-invasive cloning attack against SRAM PUFs --- an important class of PUFs typically proposed as lightweight security primitive with low overhead by using the existing memory of the underlying device. We validate our approach against two SRAM PUF implementations in 65~nm CMOS ASICs. We discuss countermeasures against our attack and propose the constructive use of remanence decay to improve the cloning-resistance of SRAM PUFs.

Moreover, as a further contribution of independent interest, we show how to use our evaluation results to significantly improve the performance of the recently proposed TARDIS scheme, which is based on remanence decay in SRAM and used as a time-keeping mechanism for low-power clock-less devices.