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]

This paper investigates a novel attack vector against

cryptography realized on FPGAs, which can pose a serious threat

to real-world implementations. We demonstrate how a simple

bitstream modification can seriously weaken crypto algorithms,

which we show by example of the AES and 3DES. The attack is

performed by modifying the FPGA bitstream that configures the

hardware elements during initialization. It has been known for a

long time that cloning of FPGA designs, even if the bitstream

is encrypted, is a relatively easy task. However, due to the

proprietary format of the bitstream, a meaningful modification

of an unknown FPGA bitstream is very challenging. While

so far it has not been evaluated how difficult it is to detect

and modify cryptographic elements. We outline two possible

practical attacks that can lead to serious security implications.

We target the non-linear S-boxes of crypto algorithms of a

synthesized FPGA design that can be either implemented as

Boolean equations in look-up tables, or as precomputed set

of values that are stored in the memory of the FPGA. We

demonstrate that it is possible to detect and apply meaningful

changes to cryptographic elements inside an unknown propriety

and undocumented bitstream. Furthermore, we also show how

an AES key can be revealed within seconds by modifying the

bitstream. Finally, we propose countermeasures that can raise

the bar for an adversary to successfully perform an attack.

09:17 [Pub][ePrint]

In a Password-Protected Secret Sharing (PPSS) scheme with parameters (t,n) (formalized by Bagherzandi et al), a user Alice stores secret information s among n servers so that she can later recover the information solely on the basis of her password. The security requirement is similar to a (t,n)-threshold secret sharing, i.e., Alice can recover her secret as long as she can communicate with t + 1 honest servers but an attacker gaining access to t servers cannot learn information about the secret. In particular, the system is secure against o-line attacks by an attacker controlling up to t servers. On the other hand, accounting for inevitable on-line attacks one allows the attacker an advantage proportional to the fraction of dictionary passwords tested in on-line interactions with the user and servers.

We present the first round-optimal PPSS scheme, requiring just one message from user to server, and from server to user, and that works in the password-only setting where users do not have access to an authenticated public key. The scheme uses an Oblivious PRF whose security we define using a UC-style ideal functionality and denote as V-OPRF due to its verifiability, and for which we show concrete, very practical realizations in the random oracle model, as well as standard-model instantiations. As an important application we use this scheme to build the first single-round password-only Threshold-PAKE protocol in the CRS and ROM models for arbitrary (t,n) parameters with no PKI requirements for any party (clients or servers) and no inter-server communication. Our T-PAKE protocols are built by combining suitable key exchange protocols on top of our V-OPRF-based PPSS schemes. We prove T-PAKE security via a generic composition theorem showing the security of any such composed protocol.

09:17 [Pub][ePrint]

We show that the plaintext of some of the proposed CCA2 conversions of McEliece cryptosystem with a public key in systematic form can be recovered faster than with a general linear decoding. This is due to the fact that an attacker only needs to recover a part of the cleartext to decrypt the relevant plaintext.

09:17 [Pub][ePrint]

As far as the Differential Cryptanalysis of reduced round Grain v1 is concerned, the best results were those published by Knellwolf et al. in Asiacrypt $2011$. In an extended version of the paper, it was shown that it was possible to retrieve {\\bf (i)} $5$ expressions in the Secret Key bits for a variant of Grain v1 that employs $97$ rounds (in place of $160$) in its Key Scheduling process using $2^{27}$ chosen IVs and {\\bf (ii)} $1$ expression in Secret Key bits for a variant that employs $104$ rounds in its Key Scheduling using $2^{35}$ chosen IVs. However, the second attack on $104$ rounds, had a success probability of around $50$\\%, which is to say that the attack worked for only around one half of the Secret Keys.

In this paper we propose a dynamic cube attack on $105$ round Grain v1, that has a success probability of $100$\\%, and thus we report an improvement of $8$ rounds over the previous best attack on Grain v1 that attacks the entire Keyspace. We take the help of the tool $\\Delta${\\sf Grain}$_{\\sf KSA}$, proposed by Banik at ACISP 2014, to track the differential trails induced in the internal state of Grain v1 by any difference in the IV bits, and we prove that a suitably introduced difference in the IV leads to a distinguisher for the output bit produced in the $105^{th}$ round. This, in turn, helps determine the values of $6$ expressions in the Secret Key bits.

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.