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).

2014-08-27
09:17 [Pub][ePrint]

We present work in progress to fully factor seventeen Mersenne numbers using a variant of the special number field sieve where sieving on the algebraic side is shared among the numbers. It is expected that it reduces the overall factoring effort by more than 50\\%. As far as we know this is the first practical application of Coppersmith\'s factorization factory\'\' idea. Most factorizations used a new double-product approach that led to additional savings in the matrix step.

09:17 [Pub][ePrint]

Very few differential fault attacks (DFA) were reported on {\\em Grain-128} so far.

In this paper we present a generic attack strategy that allows the adversary to challenge the cipher under different multi-bit fault models with faults at a targeted keystream generation round even if bit arrangement of the actual cipher device is unknown. Also unique identification of fault locations is not necessary.

To the best of our knowledge, this paper assumes the weakest adversarial power ever considered in the open literature for DFA on {\\em Grain-128} and develops the most realistic attack strategy so far on {\\em Grain-128}.

In particular, when a random area within $k \\in \\{1,2,3,4,5\\}$ neighbourhood bits can only be disturbed by a single fault injection at the first keystream generation round ($k$-neighbourhood bit fault), without knowing the locations or the exact number of bits the injected fault has altered, our attack strategy always breaks the cipher with $5$ faults.

In a weaker setup even if bit arrangement of the cipher device is unknown, bad-faults (at the first keystream generation round) are rejected with probabilities $0.999993$, $0.999979$, $0.999963$, $0.999946$ and $0.999921$ assuming that the adversary will use only 1, 2, 3, 4 and 5 neighbourhood bit faults respectively for {\\em key-IV} recovery.

09:17 [Pub][ePrint]

Password-based authentication has been widely deployed in practice due to its simplicity and efficiency. Storing passwords and deriving cryptographic keys from passwords in a secure manner are crucial for many security systems and services. However, choices of well-studied password hashing algorithms are extremely limited, as their security requirements and design principles are different from common cryptographic algorithms. In this paper, we propose two simple and practical password hashing algorithms, Pleco and Plectron. They are built upon well-understood cryptographic algorithms, and combine advantages of symmetric and asymmetric primitives. By employing the Rabin cryptosystem, we prove that the one-wayness of Pleco is at least as strong as the hard problem of integer factorization. In addition, both password hashing algorithms are designed to be sequential memory-hard, in order to thwart large-scale password cracking by parallel hardware, such as GPUs, FPGAs, and ASICs. Moreover, total computation and memory consumptions of Pleco and Plectron are tunable through their cost parameters.

09:17 [Pub][ePrint]

The FX-construction was proposed in 1996 by Kilian and Rogaway as a generalization of the DESX scheme. The construction increases the security of an $n$-bit core block cipher with a $\\kappa$-bit key by using two additional $n$-bit masking keys. Recently, several concrete instances of the FX-construction were proposed, including PRINCE (proposed at Asiacrypt 2012) and PRIDE (proposed at CRYPTO 2014). These ciphers have $n=\\kappa=64$, and are proven to guarantee about $127-d$ bits of security, assuming that their core ciphers are ideal, and the adversary can obtain at most $2^d$ data.

In this paper, we devise new cryptanalytic time-memory-data tradeoff attacks on FX-constructions, combining recent techniques by Fouque, Joux and Mavromati with time-memory-data tradeoffs for stream ciphers. While our attacks do not contradict the security proof of PRINCE and PRIDE, nor pose an immediate threat to their users, some specific choices of tradeoff parameters demonstrate that the security margin of the ciphers against practical attacks is smaller than expected. Finally, we propose very light changes to PRINCE and PRIDE. These changes ensure that the ciphers resist our attacks while maintaining their design goals, with the exception of the theoretical security proof (which is invalidated, as PRINCE and PRIDE are no longer FX-constructions). Consequently, we conclude that although the FX-construction provides a very simple way of increasing the security of a widely deployed cipher (such as DES at the time), using it for a new design is a less reasonable approach.

09:17 [Pub][ePrint]

Recently, Kalikinkar Mandal and Guang Gong presented a family of nonlinear pseudorandom number generators using Welch-Gong Transformations in their paper [6]. They also performed the cycle decomposition of the WG-NLFSR recurrence relations over different finite fields by computer simulations where the nonlinear recurrence relation is composed of a characteristic polynomial and a WG permutation. In this paper, we mainly prove that the state transition transformation of the WG-NLFSR is an even permutation. We also prove that the number of the cycles in the cycle decomposition of WG-NLFSR is even. And we apply our results to the filtering WG7-NLFSR to prove that the period of the sequences generated by WG7-NLFSR can not be maximum.

09:17 [Pub][ePrint]

In this paper, We find a way to construct FSRs. The constructed FSRs can be depicted in many ways.

They are just the FSRs whose characteristic polynomial can be written as $g=(x_0+x_1)*f$ for some $f$.

Their adjacency graphs do not contain self-loops. Further more, we can divide the vertexes in their adjacency graphs into two sets such that

the edges are all between the two sets. The number of this class of FSRs is also considered. Besides, some applications in

LFSRs and constructing full cycles are presented.

09:17 [Pub][ePrint]

In this paper, we

explore the primitivity of trinomials over small finite fields. We

extend the results of the primitivity of trinomials $x^{n}+ax+b$

over ${\\mathbb{F}}_{4}$ \\cite{Li} to the general form

$x^{n}+ax^{k}+b$. We prove that for given $n$ and $k$, one of all the trinomials

$x^{n}+ax^{k}+b$ with $b$ being the primitive element of

${\\mathbb{F}}_{4}$ and $a+b\\neq1$ is primitive over

${\\mathbb{F}}_{4}$ if and only if all the others are primitive over

${\\mathbb{F}}_{4}$. And we can deduce that if we find one primitive

trinomial over ${\\mathbb{F}}_{4}$, in fact there are at least four primitive

trinomials with the same degree. We give the necessary conditions if

there exist primitive trinomials over ${\\mathbb{F}}_{4}$. We study

the trinomials with degrees $n=4^{m}+1$ and $n=21\\cdot4^{m}+29$,

where $m$ is a positive integer. For these two cases, we prove that

the trinomials $x^{n}+ax+b$ with degrees $n=4^{m}+1$ and

$n=21\\cdot4^{m}+29$ are always reducible if $m>1$. If some results

are obviously true over ${\\mathbb{F}}_{3}$, we also give it.

09:17 [Pub][ePrint]

We consider the task of constructing interactive proofs for NP which can provide meaningful security for a prover even in the presence of continual memory leakage. We imagine a setting where an adversarial verifier participates in multiple sequential interactive proof executions for a fixed NP statement x. In every execution, the adversarial verifier is additionally allowed to leak a fraction of the (secret) memory of the prover. This is in contrast to the recently introduced notion of leakage-resilient zero-knowledge (Garg-Jain-Sahai\'11) where there is only a single execution. Under multiple executions, in fact the entire prover witness might end up getting leaked thus leading to a complete compromise of prover security.

Towards that end, we define the notion of non-transferable proofs for all languages in NP. In such proofs, instead of receiving w as input, the prover will receive an \"encoding\'\' of the witness w such that the encoding is sufficient to prove the validity of x; further, this encoding can be \"updated\'\' to a fresh new encoding for the next execution. We then require that if (x,w) are sampled from a \"hard\'\' distribution, then no PPT adversary A* can gain the ability to prove x (on its own) to an honest verifier, even if A* has participated in polynomially many interactive proof executions (with leakage) with an honest prover whose input is (x,w). Non-transferability is a strong security guarantee which suffices for many cryptographic applications (and in particular, implies witness hiding).

We show how to construct non-transferable proofs for all languages in NP which can tolerate leaking a constant fraction of prover\'s secret-state during each execution. Our construction is in the common reference string (CRS) model. To obtain our results, we build a witness-encoding scheme which satisfies the following continual-leakage-resilient (CLR) properties:

- The encodings can be randomized to yield a fresh new encoding,

- There does not exist any efficient adversary, who receiving only a constant fraction of leakage on polynomially many fresh encodings of the same witness w, can output a valid encoding provided that the witness w along with its corresponding input instance x were sampled from a hard distribution.

Our encoding schemes are essentially re-randomizable non-interactive zero-knowledge (NIZK) proofs for circuit satisfiability, with the aforementioned CLR properties. We believe that our CLR-encodings, as well as our techniques to build them, may be of independent interest.

2014-08-26
18:47 [Event][New]

Submission: 21 November 2014
From May 2 to May 5
Location: Lugano, Switzerland

2014-08-25
03:14 [Event][New]

From January 12 to January 16
Location: New Brunswik, USA