International Association
for Cryptologic Research

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

some previous work had addressed bitstream reverse-engineering,

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Submission: 21 November 2014
Notification: 30 January 2015
From May 2 to May 5
Location: Lugano, Switzerland
More Information: http://icits2015.net/

From January 12 to January 16
Location: New Brunswik, USA
More Information: http://dimacs.rutgers.edu/Workshops/Post-Quantum/

From May 31 to June 5
Location: Sibenik, Croatia
More Information: http://summerschool-croatia15.cs.ru.nl/

From May 31 to June 5
Location: Sibenik, Croatia
More Information: http://summerschool-croatia15.cs.ru.nl/

From February 4 to February 7
Location: Goa, India
More Information: http://nullcon.net

Despite more than thirty years of research efforts, textual passwords are still enveloped in mysterious veils. In this work, we make a substantial step forward in understanding the distributions of passwords and measuring the strength of password datasets by using a statistical approach. We first show that Zipf\'s law perfectly exists in real-life passwords by conducting linear regressions on a corpus of 56 million passwords. As one specific application of this observation, we propose the number of unique passwords used in regression and the slope of the regression line together as a metric for assessing the strength of password datasets, and prove it in a mathematically rigorous manner. Furthermore, extensive experiments (including optimal attacks, simulated optimal attacks and state-of-the-art cracking sessions) are performed to demonstrate the practical effectiveness of our metric. To the best of knowledge, our new metric is the first one that is both easy to approximate and accurate to facilitate comparisons, providing a useful tool for the system administrators to gain a precise grasp of the strength of their password datasets and to adjust the password policies more reasonably.

We introduce a formal model for order queries on lists in zero knowledge in the traditional authenticated data structure model.

We call this model Privacy-Preserving Authenticated List (PPAL).

In this model, the queries are performed on the list stored in the (untrusted) cloud where data integrity and privacy have to

be maintained. To realize an efficient authenticated data structure, we first adapt consistent data query model.

To this end we introduce a formal model called Zero-Knowledge List (ZKL) scheme which generalizes consistent membership queries in zero-knowledge

to consistent membership and order queries on a totally ordered set in zero knowledge. We present a construction of ZKL based on zero-knowledge set

and homomorphic integer commitment scheme. Then we discuss why this construction is not as efficient as desired in cloud applications and

present an efficient construction of PPAL based on bilinear accumulators and bilinear maps which is provably secure and zero-knowledge.

The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server\'s actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed.

We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the \"committed-simulator\" technique of Deng et. al [FOCS 09].