International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

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

2015-02-28
01:17 [Pub][ePrint]

Two constructions/classes of bent functions are derived from the notion of spread. The first class, ${\\cal PS}$, gives a useful framework for designing bent functions which are constant (except maybe at 0) on the elements of a (partial) spread. Dillon has deduced the explicit class ${\\cal PS}_{ap}$ of bent functions obtained from the spread of all multiplicative cosets of ${\\Bbb F}_{2^m}^*$ (added with 0) in ${\\Bbb F}_{2^{2m}}^*$ (that we shall call the Dillon spread). The second class, $H$, later slightly modified into a class called ${\\cal H}$ so as to relate it to the so-called Niho bent functions, is up to addition of affine functions the set of bent functions whose restrictions to the spaces of the Dillon spread are linear. It has been observed that the functions in ${\\cal H}$ are related to o-polynomials, and this has led to several explicit classes of bent functions. In this paper we first apply the ${\\cal PS}$ construction to a larger class of spreads, well-known in the finite geometry domain and that we shall call Andr\\\'e\'s spreads, and we describe explicitly the ${\\cal PS}$ corresponding bent functions and their duals. We also characterize those bent functions whose restrictions to the spaces of an Andr\\\'e spread are linear. This leads to a notion extending that of o-polynomial. Finally, we obtain similar characterizations for the ${\\cal H}$-like functions derived from the spreads used by Wu to deduce ${\\cal PS}$ bent functions from the Demp\\-wolff-M\\\"uller pre-quasifield, the Knuth pre-semifield and the Kantor pre-semifield. In each case, this also leads to a new notion on polynomials.

01:17 [Pub][ePrint]

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]

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]

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.

2015-02-27
22:17 [Pub][ePrint]

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]

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]

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]

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]

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]

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]

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.