International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service 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).

2012-08-23
00:17 [Pub][ePrint] Computational Soundness without Protocol Restrictions, by Michael Backes and Ankit Malik and Dominique Unruh

  The abstraction of cryptographic operations by term algebras, called

Dolev-Yao models, is essential in almost all tool-supported methods

for verifying security protocols. Recently significant progress was

made in establishing computational soundness results: these results

prove that Dolev-Yao style models can be sound with respect to actual

cryptographic realizations and security definitions. However, these

results came at the cost of imposing various constraints on the set of

permitted security protocols: e.g., dishonestly generated keys must

not be used, key cycles need to be avoided, and many more. In a

nutshell, the cryptographic security definitions did not adequately

capture these cases, but were considered carved in stone; in contrast,

the symbolic abstractions were bent to reflect cryptographic features

and idiosyncrasies, thereby requiring adaptations of existing

verification tools.

In this paper, we pursue the opposite direction: we consider a

symbolic abstraction for public-key encryption and identify two

cryptographic definitions called PROG-KDM (programmable key-dependent

message) security and MKE (malicious-key extractable) security that we

jointly prove to be sufficient for obtaining computational soundness

without imposing assumptions on the protocols using this

abstraction. In particular, dishonestly generated keys obtained from

the adversary can be sent, received, and used. The definitions can be

met by existing cryptographic schemes in the random oracle model. This

yields the first computational soundness result for trace-properties

that holds for arbitrary protocols using this abstraction (in

particular permitting to send and receive dishonestly generated keys),

and that is accessible to all existing tools for reasoning about

Dolev-Yao models without further adaptations.



00:17 [Pub][ePrint] Short communication: An interpretation of the Linux entropy estimator, by Benjamin Pousse

  The Linux random number generator (LRNG) aims to produce random numbers with all the limitations due to a deterministic machine. Two recent analysis exist for this generator. These analysis provide strong cryptographic details about LRNG. However both fail to give a mathematical explanation of the entropy estimator embedded. In this paper we propose an interpretation using Newton polynomial interpolation.



00:17 [Pub][ePrint] Designated Verifier Threshold Proxy Signature Scheme without Random Oracles, by Mohammad Beheshti-Atashgah \\and Majid Bayat \\and Mahmoud Gardeshi \\and Mohammad Reza Aref

  In a $(t,n)$ designated verifier threshold proxy signature \\, scheme, an original signer can delegate his/her signing power to $n$ proxy signers such that any $t$ or more out of $n$ proxy signers can sign messages on behalf of the original signer but $t-1$ or less of the proxy signers cannot generate a valid proxy signature. Of course, the signature is issued for a designated receiver and therefore only the designated receiver can validate the proxy signature. In this paper, we propose a new designated verifier threshold proxy signature scheme and also show that the proposed scheme has provable security in the standard model. The security of proposed scheme is based on the $GBDH$ assumption and the proposed scheme satisfies all the security requirements of threshold proxy signature schemes.



00:17 [Pub][ePrint] Recursive Linear and Differential Cryptanalysis of Ultralightweight Authentication Protocols, by Zahra Ahmadian, Mahmoud Salmasizadeh, Mohammad Reza Aref

  Privacy is faced to serious challenges in the ubiquitous computing world. In order to handle this problem, some researches in recent years have focused on design and analysis of privacy friendly ultralightweight authentication protocols. In less than a decade, many ultralightweight authentication protocols are proposed. Though, successful crypanalyses are proposed for almost all of them, most of these attacks are based on ad-hoc methods that are not extensible to a large class of ultralightweight protocols. So this research area still suffers from the lack of structured cryptanalysis and evaluation ethods.

In this paper, we introduce new frameworks for full disclosure attacks on ultralightweight authentication protocols based on new concepts of recursive linear and recursive differential cryptanalysis. Both of them exploit triangular functions in ultralightweight protocols and recover all secret data stored in the tag in a recursive manner. The recursive linear attack is applied to Yeh et al. and SLMAP authentication protocols. This attack is passive, deterministic (i.e. the attacker can retrieve all the secrets with probability of one), and requires only a single authentication session. The recursive differential attack is more powerful and can be applied to the protocols which linear attack may not work on. We show the effectiveness of this attack on LMAP++and SASI authentication protocols. This differential attack is probabilistic, active in the sense that the attacker suffices only to block some specific messages, and requires a few authentication sessions.





2012-08-22
00:17 [Pub][ePrint] A j-lanes tree hashing mode and j-lanes SHA-256, by Shay Gueron

  j-lanes hashing is a tree mode that splits an input message to j slices, computes j independent digests of each slice, and outputs the hash value of their concatenation. We demonstrate the performance advantage of j-lanes hashing on SIMD architectures, by coding a 4-lanes-SHA-256 implementation and measuring its performance on the latest 3rd Generation Intel® Core(TM). For message ranging 2KB to 132KB in length, the 4-lanes SHA-256 is between 1.5 to 1.97 times faster than the fastest publicly available implementation (that we are aware of), and between 1.9 to 2.5 times faster than OpenSSL 1.0.1c. For long messages, there is no significant performance difference between different choices of j. We show that the 4-lanes SHA-256 is faster than the two SHA3 finalists (BLAKE and Keccak) that have a published tree mode implementation. We explain why j-lanes hashing will be even faster on the future AVX2 architecture with 256 bits registers. This suggests that standardizing a tree mode for hash functions (SHA-256 in particular) would deliver significant performance benefits for a multitude of algorithms and usages.



00:17 [Pub][ePrint] Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting, by Patrick Derbez and Pierre-Alain Fouque and Jérémy Jean

  In this paper, we revisit meet-in-the-middle attacks on AES in the

single-key model and improve on Dunkelman, Keller and Shamir attacks

of Asiacrypt 2010. We present the best attack on 7 rounds of AES-128

where data/time/memory complexities are below $2^{100}$. Moreover, we

are able to extend the number of rounds to reach attacks on 8 rounds

for both AES-192 and AES-256. This gives the best attacks on those two

versions with a data complexity of $2^{107}$ chosen-plaintexts, a

memory complexity of $2^{96}$ and a time complexity of $2^{172}$ for

AES-192 and $2^{196}$ for AES-256. Finally, we also describe the best

attack on 9 rounds of AES-256 with $2^{120}$ chosen-plaintexts and

time and memory complexities of $2^{203}$. All these attacks have been

found by carefully studying the number of reachable multisets in

Dunkelman et al. attacks.



00:17 [Pub][ePrint] Cryptanalysis on a novel unconditionally secure oblivious polynomial evaluation protocol, by Wang Qinglong, Xu Li

  Vanishree et.al proposed a novel unconditionally oblivious polynomial evaluation protocol and they claimed

that can fulfill both sender and receiver\'s security. Here, this protocol is cryptanalyzed. We find that it has a fatal fault

which cannot implement the receiver\'s security at all and show the detail analyzing process.



00:17 [Pub][ePrint] Mix-Compress-Mix Revisited: Dispensing with Non-invertible Random Injection Oracles, by Mohammad Reza Reyhanitabar and Willy Susilo

  We revisit the problem of building dual-model secure (DMS) hash functions that are simultaneously

provably collision resistant (CR) in the standard model and provably pseudorandom oracle (PRO) in an idealized

model. Designing a DMS hash function was first investigated by Ristenpart and Shrimpton (ASIACRYPT

2007); they put forth a generic approach, called Mix-Compress-Mix (MCM), and showed the feasibility of the

MCM approach with a secure (but inefficient) construction. An improved construction was later presented by

Lehmann and Tessaro (ASIACRYPT 2009). The proposed construction by Ristenpart and Shrimpton requires

a non-invertible (pseudo-) random injection oracle (PRIO) and the Lehmann-Tessaro construction requires a

non-invertible random permutation oracle (NIRP). Despite showing the feasibility of realizing PRIO and NIRP

objects in theory-using ideal ciphers and (trapdoor) one-way permutations- these constructions suffer from several

efficiency and implementation issues as pointed out by their designers and briefly reviewed in this paper.

In contrast to the previous constructions, we show that constructing a DMS hash function does not require any

PRIO or NIRP, and hence there is no need for additional (trapdoor) one-way permutations. In fact, Ristenpart and

Shrimpton posed the question of whether MCM is secure under easy-to-invert mixing steps as an open problem in

their paper.We resolve this question in the affirmative in the fixed-input-length (FIL) hash setting. More precisely,

we show that one can sandwich a provably CR function, which is sufficiently compressing, between two random

invertible permutations to build a provably DMS compression function. Any multi-property-preserving (MPP)

domain extender that preserves CR and PRO can then be used to convert such a DMS compression function

to a full-fledged DMS hash function. Interestingly, there are efficient off-the-shelf candidates for all the three

ingredients (provably CR compression functions, random invertible permutations, and MPP domain extenders)

from which one can choose to implement such a DMS hash function in practice. Further, we also explain the

implementation options as well as a concrete instantiation.



00:17 [Pub][ePrint] Short Signatures From Diffie-Hellman: Realizing Short Public Key, by Jae Hong Seo

  In EUROCRYPT 2005, Waters proposed a signature scheme based on the computational Diffie-Hellman (DH) assumption without random oracles. His scheme is the first and sole signature scheme in the category of (hash-and-sign) signature schemes secure under the DH assumption in the standard model and has also been applied to the design of numerous protocols in the various cryptographic areas. However, the Waters signature scheme suffered from a large public key of $\\Theta(\\lambda)$ group elements, where $\\lambda$ is the security parameter. Realizing standard model DH-based signature scheme, in which both the signature and the public key are short, has been an open problem.

We propose short signatures from the DH assumption, which has a sublinear size public key. More precisely, our proposal produces a public key of $\\Theta(\\sqrt{\\frac{\\lambda}{\\log \\lambda}})$ group elements. Our construction is inspired from two techniques for short signatures such as using programmable hashes and using tags. From two previous techniques, we first derive a signature scheme with a somewhat short public key of $\\Theta(\\frac{\\lambda}{\\log\\lambda})$, and then we developed a new technique for {\\em asymmetric trade} between the public key size and the signature size. In particular, by adding one field element in each signature, we can reduce the public key size to $O(\\sqrt{\\frac{\\lambda}{\\log \\lambda}})$ group elements, so that the resulting signature size is two group elements and two field elements.

We also propose a variant by applying a technique for compressing tag vectors so that the resulting signatures has a shorter signature size (two group elements and one field element) by augmenting signing/verification costs and adding constant factor in public key size (that is, public key size is still $\\Theta(\\sqrt\\frac{\\lambda}{\\log\\lambda})$ group elements). Note that we limit ourselves to dealing with only polynomial-time reductions in all security proofs.



00:17 [Pub][ePrint] Improved Security Bounds for Key-Alternating Ciphers via Hellinger Distance, by John Steinberger

  A $t$-round key alternating cipher can be viewed as an abstraction of AES. It defines a cipher $E$ from $t$ fixed public permutations $P_1, \\ldots, P_t : \\{0,1\\}^n \\ra \\{0,1\\}^n$ and a key $k = k_0\\Vert \\cdots \\Vert k_t \\in \\{0,1\\}^{n(t+1)}$ by setting $E_{k}(x) = k_t \\oplus P_t(k_{t-1} \\oplus P_{t-1}(\\cdots k_1 \\oplus P_1(k_0 \\oplus x) \\cdots))$. The indistinguishability of $E_k$ from a random truly random permutation by an adversary who also has oracle access to the (public) random permutations $P_1, \\ldots, P_t$ was investigated for $t = 2$ by Even and Mansour and, much later, by Bogdanov et al. The former proved indistinguishability up to $2^{n/2}$ queries for $t = 1$ while the latter proved indistinguishability up to $2^{2n/3}$ queries for $t \\geq 2$ (ignoring low-order terms). Our contribution is to improve the analysis of Bogdanov et al$.$ by showing security up to $2^{3n/4}$ queries for $t \\geq 3$. Given that security cannot exceed $2^{\\frac{t}{t+1}n}$ queries, this is in particular achieves a tight bound for the case $t = 3$, whereas, previously, tight bounds had only been achieved for $t = 1$ (by Even and Mansour) and for $t = 2$ (by Bogdanov et al$.$). Our main technique is an improved analysis of the elegant \\emph{sample distinguishability} game introduced by Bogdanov et al. More specifically, we succeed in eliminating adaptivity by considering the Hellinger advantage of an adversary, a notion that we introduce here. To our knowledge, our result constitutes the first time Hellinger distance (a standard measure of ``distance\'\' between random variables, and a cousin of statistical distance) is used in a cryptographic indistinguishability proof.



00:17 [Pub][ePrint] Approaches for the Parallelization of Software Implementation of Integer Multiplication, by Vladislav Kovtun and Andrew Okhrimenko

  In this paper there are considered several approaches for the increasing performance of software implementation of integer multiplication algorithm for the 32-bit & 64-bit platforms via parallelization. The main idea of algorithm parallelization consists in delayed carry mechanism using which authors have proposed earlier [11]. The delayed carry allows to get rid of connectivity in loop iterations for sums accumulation of products, which allows parallel execution of loops iterations in separate threads. Upon completion of sum accumulation threads, it is necessary to make corrections in final result via assimilation of carries. First approach consists in optimization of parallelization for the two execution threads and second approach is an evolution of the first approach and is oriented on three and more execution threads. Proposed approaches for parallelization allow increasing the total algorithm computational complexity, as for one execution thread, but decrease total execution time on multi-core CPU.