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-05-11
17:13 [Event][New]

From September 30 to September 30
Location: Florence, Italy

17:13 [Event][New]

Submission: 29 May 2015
From January 1 to October 16

09:17 [Pub][ePrint]

Gu map-1 is a modified version of GGH map. It uses same ideal lattices for constructing the trapdoors, while the novelty is that no encodings of zero are given. In this short paper we show that Gu map-1 cannot be used for the instance of witness encryption (WE) based on the hardness of 3-exact cover problem. That is, if Gu map-1 is used for such instance, we can break it by solving a combined 3-exact cover problem. The reason is just that no encodings of zero are given.

2015-05-10
09:17 [Pub][ePrint]

Side-channel cube attacks are a class of leakage attacks on block ciphers in which the attacker is assumed to have access to some leaked information on the internal state of the cipher as well as the plaintext/ciphertext pairs. The known Dinur-Shamir model and its variants require error-free data for at least part of the measurements. In

this paper, we consider a new and more realistic model which can deal with the case when \\textit{all} the leaked bits are noisy. In this model, the key recovery problem is converted to the problem of decoding a binary linear code over a binary symmetric channel with the crossover probability which is determined by the measurement quality and the cube size. We use the maximum likelihood decoding method to recover the key. As a case study, we demonstrate efficient key recovery attacks on PRESENT. We show that the full $80$-bit key can be restored with $2^{10.2}$ measurements with an error probability of $19.4\\%$ for each measurement.

2015-05-09
18:17 [Pub][ePrint]

Side channel and fault attacks take advantage from the fact that the behavior of crypto implementations can be observed and provides hints that simplify revealing keys. In a real word a lot of devices, that are identical to the target device, can be attacked before attacking the real target to increase the success of the attack. Their package can be opened and their electromagnetic radiation and structure can be analyzed. Another example of how to improve significantly the success rate of attacks is the measurement of the difference of the side channel leakage of two identical devices, one of these devices being the target, using the Wheatstone bridge measurement setup. Here we propose to individualize the electrical circuit of cryptographic devices in order to prevent attacks that use identical devices: attacks, that analyze the structure of devices identical to the target device in a preparation phase; usual side channel attacks, that use always the same target device for collecting many traces, and attacks that use two identical devices at the same time for measuring the difference of side-channel leakages. The proposed individualization can prevent such attacks because the power consumption and the electromagnetic radiation of devices with individualized electrical circuit are individualized while providing the same functionality. We implemented three individualized ECC designs that provide exactly the same cryptographic function on a Spartan-6 FPGA. These designs differ from each other in a single block only, i.e. in the field multiplier. The visualization of the routed design and measurement results show clear differences in the topology, in the resources consumed as well as in the power and electromagnetic traces. We show that the influence of the individualized designs on the power traces is comparable with the influence of inputs. These facts show that individualizing of electrical circuits of cryptographic devices can be exploited as a protection mechanism. We envision that this type of protection mechanism is relevant if an attacker has a physical access to the cryptographic devices, e.g. for wireless sensor networks from which devices can easily be stolen for further analysis in the lab.

18:17 [Pub][ePrint]

The Bistable Ring (BR) Physical Unclonable Function (PUF) is a newly proposed hardware security primitive in the PUF family. In this work, we comprehensively evaluate its resilience against Machine Learning (ML) modeling attacks. Based on the success of ML attacks, we propose XOR strategies to enhance the security of BR PUFs. Our results show that the XOR BR PUF with more than four parallel BR PUFs is able to resist the ML modeling methods in this work. We also evaluate the other PUF metrics of reliability, uniqueness and uniformity, and find that the XOR function is also effective in improving the uniformity of BR PUFs.

18:17 [Pub][ePrint]

Ristenpart and Rogaway proposed XLS in 2007 which is a

generic method to encrypt messages with incomplete last blocks. Later

Andreeva et al., in 2013 proposed an authenticated encryption COPA

which uses XLS while processing incomplete message blocks. Following

the design of COPA, several other CAESAR candidates used the similar

approach. Surprisingly in 2014, Nandi showed a three-query distinguisher against XLS which violates the security claim of XLS and puts a question mark on all schemes using XLS. However, due to the interleaved nature of encryption and decryption queries of the distinguisher, it was not clear whether the security claims of COPA remains true or not. This paper revisits XLS and COPA both in the direction of cryptanalysis and provable security. Our contribution of the paper can be summarized into following two parts:

1. Cryptanalysis: We describe two attacks - (i) a new distinguisher

against XLS and extending this attack to obtain (ii) a forging algo-

rithm with query complexity about 2^n/3 against COPA where n is

the block size of the underlying blockcipher.

2. Security Proof: Due to the above attacks the main claims of XLS

(already known before) and COPA are wrong. So we revise the security analysis of both and show that (i) both XLS and COPA are

pseudorandom function or PRF up to 2^n/2 queries and (ii) COPA is

integrity-secure up to 2^n/3 queries (matching the query complexity

of our forging algorithm).

18:17 [Pub][ePrint]

In FSE 2007, Ristenpart and Rogaway had described a generic

method XLS to construct a length-preserving strong pseudorandom per-

mutation (SPRP) over bit-strings of size at least n. It requires a length-preserving permutation E over all bits of size multiple of n and a blockcipher E with block size n. The SPRP security of XLS was proved from the SPRP assumptions of both E and E. In this paper we disprove the claim by demonstrating a SPRP distinguisher of XLS which makes only

multi-permutation linear function, called mix2. In this paper, we also

show that if we replace mix2 by any invertible linear functions, the construction XLS still remains insecure. Thus the mode has inherit weakness.

18:17 [Pub][ePrint]

We propose a general technique that allows improving the complexity of

zero-knowledge protocols for a large class of problems where

previously the best known solution was a simple cut-and-choose style

protocol, i.e., where the size of a proof for problem instance $x$ and

error probability $2^{-n}$ was $O(|x| n)$ bits. By using our technique

to prove $n$ instances simultaneously, we can bring down the proof

size per instance to $O(|x| + n)$ bits for the same error probability

while using no computational assumptions. Examples where our technique

applies include proofs for quadratic residuosity, proofs of subgroup

membership and knowledge of discrete logarithms in groups of unknown

order, interval proofs of the latter, and proofs of plaintext

knowledge for various types of homomorphic encryption schemes. We

first propose our protocols as $\\Sigma$-protocols and extend them

later to zero-knowledge proofs of knowledge.

15:17 [Forum]

The authors of 2015/313 claim that their result implies a quantum polynomial time key-recovery attack against cryptographic constructions relying on the hardness of finding a short generator of a principal ideal in a cyclotomic field (ex: multilinear maps or Smart-Vercauteren scheme). This statement is not true, and it should be amended. It is based on two references to justify the existence of a quantum polynomial time algorithm to solve the Principal Ideal Problem (PIP). First, an online draft from Campbel, Grove and Shepherd [CGS14]. This work in progress has been publicly released as it was when the corresponding research program at CESG was interrupted. According to its authors, the polynomial run time of the attack is an overstatement that cannot be supported (This has been stated at the Heilbronn Quantum Algorithms Meeting 2015 and at the ICERM workshop on lattices and cybersecurity 2015). Moreover, it is unclear that the approach chosen in [CGS14] could ever lead to a polynomial run time for at least two fundamental reasons explained in this forum post : https://groups.google.com/forum/#!topic/cryptanalytic-algorithms/GdVfp5Kbdb8 Then, the authors of 2015/313 refer to ongoing research by Fang Song and myself. This work in progress (which adopts a totally different approach than that of [CGS14]) has never been shared with the authors and has never been publicly released. We have no timeline for its submission, and although it is promissing, it is clearly too soon to refer to it with the level of confidence chosen by the authors of this preprint ("known algorithm for the PIP"). We have already shared our concerns about this citation with the authors of 2015/313, but no change has been made so far. It is clearly "work in progress", and Fang Song and myself do not refer to it as an actual result. From: 2015-07-05 20:21:15 (UTC)

10:13 [PhD][New]

Name: Liam Keliher
Topic: Linear Cryptanalysis of Substitution-Permutation Networks
Category: secret-key cryptography

Description: The subject of this thesis is linear cryptanalysis of substitution-permutation networks (SPNs). We focus on the rigorous form of linear cryptanalysis, which requires the concept of linear hulls.\r\n\r\nFirst, we consider SPNs in which the s-boxes are selected independently and uniformly from the set of all bijective n x n s-boxes. We derive an expression for the expected linear probability values of such an SPN, and give evidence that this expression converges to the corresponding value for the true random cipher. This adds quantitative support to the claim that the SPN structure is a good approximation to the true random cipher. We conjecture that this convergence holds for a large class of SPNs.\r\n\r\nIn addition, we derive a lower bound on the probability that an SPN with randomly selected s-boxes is practically secure against linear cryptanalysis after a given number of rounds. For common block sizes, experimental evidence indicates that this probability rapidly approaches 1 with an increasing number of rounds.\r\n\r\nWe then consider SPNs with fixed s-boxes. We present two new algorithms for upper bounding the maximum average linear hull probability for SPNs. These algorithms, named KMT1 and KMT2, are the first completely general algorithms for this purpose -- they can be applied to any SPN, and they compute an upper bound that is a function of the number of encryption rounds being evaluated. In contrast, other approaches to this problem either require that the SPN linear transformation have a specific structure, or compute a single value independent of the number of rounds. By applying KMT1 and KMT2 to the AES, we establish the provable security of the AES against linear cryptanalysis.\r\n\r\nAs a straightforward application of our work with linear hulls, we analyze the Q cipher, an SPN submitted to the European Commission\'s NESSIE cryptographic competition. By using linear characteristics, not linear hulls, the designer of Q evaluates the cipher to [...]