International Association
for Cryptologic Research

We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damg\\aa rd (MD) hash functions with Preimage Aware (PrA) compression functions. It is known that the PrA assumption alone is insufficient for proving the security of unbounded hash tree schemes against back-dating attacks. We show that many known PrA constructions satisfy a stronger \\emph{Bounded Pre-Image Awareness (BPrA)} condition that assumes the existence of an extractor $\\EXT$ that is bounded in the sense that for any efficiently computable query string $\\alpha$, the number of outputs $y$ for which $\\EXT(y,\\alpha)$ succeeds does not exceed the number of queries in $\\alpha$. We show that blockcipher based MD-hash functions with rate-1 compression functions (such as Davies-Meyer and Miyaguchi-Preneel) of both type I and type II are BPrA.

We also show that the compression function of Shrimpton-Stam that uses non-compressing components is BPrA. The security proof for unbounded hash-tree schemes is very tight under the BPrA assumption. In order to have $2^s$-security against back-dating, the hash function must have $n=2s + 4$ output bits, assuming that the security of the hash function is close to the birthday barrier, i.e. that there are no structural weaknesses in the hash function itself. Note that the previous proofs that assume PrA gave the estimation $n=2s + 2 \\log_2 C + 2$, where $C$ is the maximum allowed size of the hash tree. For example, if $s=100$ ($2^{100}$-security) and $C=2^{50}$, the previous proofs require $n=302$ output bits, while the new proof requires $n=204$ output bits.

The Side Channel Cube Attack (SCCA) is a kind of Algebraic Side Channel Attack (ASCA) consisting of theoretical and practical aspects. This paper presents a general framework for the SCCA (called a Iterative SCCA (ISCCA)) on block ciphers in which these aspects are explained and the requirements are listed. On the theoretical side, we use extracting quadratic equations, recognizing iterated chosen plaintexts, and cube iteration to improve the SCCA on block ciphers. On the experimental side, we define a feasible scenario in which ISCCA can be applied on block ciphers. Then, we implement the ISCCA on AES and verify the results on an ARM micro controller. Finally, we compare the proposed SCCA (ISCCA) with the Simple Power Analysis, the previous SCCAs, and the previous attacks on AES. This comparison is based on the template building and data, time, and memory complexity. We show that the SCCA can recover 128 and 256 key bits of the AES-128/256 only with data complexity 2^{7.3}, time complexity 2^{15.74}, and memory complexity 2^{7.89} on AES-128, and data complexity 2^{7.75}, time complexity 2^{16.2}, and memory complexity 2^{8.21} on AES-256. We show only nine interesting points are needed for template matching phase. This is the most efficient SCCA on AES-128/256.

Side-channel analysis is a well-known and efficient hardware technique to recover embedded secrets in microprocessors. Over the past years, the state-of-the-art side-channel attacks has significantly increased, leading to a myriad of vulnerability paths that secure codes must withstand. Nowadays most of the attacks target the cryptographic algorithms, but very few exploit the cryptographic protocol. In this paper, we present a new attack that exploits the information exchange at the cryptographic protocol level in order to disclose the secret key. This attack is applicable to the MAC calculations standardized in ISO/IEC 9797-1 especially the MAC algorithm 3 with the DES function. This protocol is spread in secure products nowadays, this is the case typically for some EMV implementations. By using a side-channel technique combined with a reasonable brute force effort, we show that the secret key can be fully retrieved even though the DES implementation seems to be well-protected against side-channel attacks.

We propose a new general framework for the security of multivariate quadratic (\\mathcal{MQ}) schemes with respect to attacks that exploit the existence of linear subspaces. We adopt linearity measures that have been used traditionally to estimate the security of symmetric cryptographic primitives, namely the nonlinearity measure for vectorial functions introduced by Nyberg at Eurocrypt \'92, and the $(s, t)$--linearity measure introduced recently by Boura and Canteaut at FSE\'13. We redefine some properties of \\mathcal{MQ} cryptosystems in terms of these known symmetric cryptography notions, and show that our new framework is a compact generalization of several known attacks in \\mathcal{MQ} cryptography against single field schemes. We use the framework to explain various pitfalls regarding the successfulness of these attacks. Finally, we argue that linearity can be used as a solid measure for the susceptibility of \\mathcal{MQ} schemes to these attacks, and also as a necessary tool for prudent design practice in \\mathcal{MQ} cryptography.

Submission: 23 December 2014
Notification: 19 January 2015
From April 14 to April 14
Location: Singapore, Singapore
More Information: http://conference.cs.cityu.edu.hk/asiaccsscc/

Submission: 1 November 2014
From January 7 to January 9
Location: London, United Kingdom
More Information: http://www.realworldcrypto.com/rwc2015

Public-key distance bounding schemes are needed to defeat relay attacks in payment systems. So far, only two such schemes exist, but fail to fully protect against malicious provers. In this paper, we solve this problem. We provide a full formalism to define the proof of proximity of knowledge (PoPoK). Protocols should succeed if and only if a prover holding a secret is within the proximity of the verifier. Like proofs of knowledge, these protocols must satisfy completeness, soundness (protection for the honest verifier), and security (protection for the honest prover). We construct ProProx, the very first fully secure PoPoK.

We present security proofs for the BLT signature scheme in the model, where hash functions are built from ideal components (random oracles, ideal ciphers, etc.). We show that certain strengthening of the Pre-image Awareness (PrA) conditions like boundedness of the extractor, and certain natural properties (balancedness and the so-called output one-wayness) of the hash function are sufficient for existential unforgeability of the BLT signature scheme.

The Idemix library provides the implementation of the Camenisch-Lysyanskaya (CL) Attribute-based Credential System (ABC), its protocol extensions and the U-Prove ABC. In the case of the CL ABC, the library can delegate some cryptographic operations to a hardware token (e.g. a smart card). In the last few years several practitioners have proposed different implementations of ABCs in smart

cards. The IRMA card provides at the time of writing this manuscript, an optimal performance for practical applications. In this report, we address the case of integrating this implementation in the Idemix library. We opted for implementing the key binding use case together with the generation of exclusive scope pseudonyms and public key commitments on card. The integration requires two additional classes

(one that parses system parameters, credential specifications and issuer public keys and other one that interfaces the card and its functionalities with the CL building block) together with one modification in the code if the signature randomization is delegated to the card (only required in one of the proposed alternatives). The integration of the key binding use case requires 540 bytes extra in the smart card. We can perform all the involved cryptographic operations in only 206.75 ms, including the computation of exclusive scope pseudonyms (55.19 ms).

On top of the passively secure extension protocol of [IKNP03] we build

a new construction secure against active adversaries.

We can replace the invocation of the hash function that is used

to check the receiver is well-behaved with the XOR of bit strings.

This is possible by applying a cut-and-choose

technique on the length of the bit strings that the receiver sends

in the reversed OT. We also improve on the number

of seeds required for the extension, both asymptotically and practically.

Moreover, the protocol used to test receiver\'s behaviour enjoys

unconditional security.

Provably secure distance-bounding is a rising subject, yet an unsettled one; indeed, very few distance-bounding protocols, with formal security proofs, have been proposed. In fact, so far only two protocols, namely SKI (by Boureanu et al.) and FO (by Fischlin and Onete), offer all-encompassing security guaranties, i.e., resistance to distance-fraud, mafia-fraud, and terrorist-fraud. Matters like security, alongside with soundness, or added tolerance to noise do not always coexist in the (new) distance-bounding designs. Moreover, as we will show in this paper, efficiency and simultaneous protection against all frauds seem to be rather conflicting matters, leading to proposed solutions which were/are sub-optimal. In fact, in this recent quest for provable security, efficiency has been left in the shadow. Notably, the tradeoffs between the security and efficiency have not been studied. In this paper, we will address these limitations, setting the \"security vs. efficiency\" record straight.

Concretely, by combining ideas from SKI and FO, we propose symmetric protocols that are efficient, noise-tolerant and-at the same time- provably secure against all known frauds. Indeed, our new distance-bounding solutions outperform the two aforementioned provably secure distance-bounding protocols. For instance, with a noise level of 5%, we obtain the same level of security as those of the pre-existent protocols, but we reduce the number of rounds needed from 181 to 54.

We present collisions for a version of SHA-1 with modified constants, where the colliding payloads are valid binary files. Examples are given of colliding executables, archives, and images. Our malicious SHA-1 instances have round constants that differ from the original ones in only 40 bits (on average). Modified versions of cryptographic standards are typically used on closed systems (e.g., in pay-TV, media and gaming platforms) and aim to differentiate cryptographic components across customers or services. Our proof-of-concept thus demonstrates the exploitability of custom SHA-1 versions for malicious purposes, such as the injection of user surveillance features. To encourage further research on such malicious hash functions, we propose definitions of malicious hash functions and of associated security notions.

In this paper we introduce a new transformation method and a multiplication

algorithm for multiplying the elements of the field GF$(2^k)$

expressed in a normal basis. The number of XOR gates for the proposed

multiplication algorithm is

fewer than that of the optimal normal basis multiplication, not taking into

account the cost of forward and backward transformations. The algorithm is

more suitable for applications in which tens or hundreds of field multiplications

are performed before needing to transform the results back.

White-box cryptography is an obfuscation technique to protect the secret key in the software implementations even if an adversary has full access to the implementation of the encryption algorithm and full control over its execution platforms.

This concept was presented in 2002 by Chow et al., and since then there have been many proposals to give solutions for the white-box cryptography.

However, the progress does not seem to be substantial in spite of its practical importance.

In fact, it is repeated that as a proposal on white-box implementation is announced, an attack of this implementation with lower complexity followed soon.

It is mainly because most cryptanalytic methods were just targeted to some specific implementations and there is no general attack tool for the white-box cryptography.

In this paper, we present a general analytic toolbox for white-box implementations which extracts the secret information obfuscated in the implementation.

For a general SLT cipher on $n$ bits with S-boxes on $m$ bits, one can remove the nonlinear encodings with complexity $O(\\frac{n}{m_Q}2^{3m_Q})$ using our attack tool, if $m_Q$-bit nonlinear encodings are used to obfuscate input/output values in the implementation.

Also, one can recover the affine encoding $A$ in time $O(\\frac{n}{m}\\cdot{m_A}^32^{3m})$ using our extended affine equivalence algorithm~(EAEA), if the inverse of the encoded round function $F$ on $n$ bits is given, where $m_A$ is the smallest integer $p$ such that $A$ or its similar matrix obtained by permuting rows and columns is a block diagonal matrix with a $p\\times p$ matrix as a block.

To avoid our attack, we need to consider a special encoding of large $m_A$, up to $n$. This results in storage blowing up in general. We suggest one approach with special affine encodings of $m_A=n$ that saves storage.

In that case, the EAEA has the complexity~$O\\left(\\min\\left\\{\\tfrac{n}{m}\\cdot {n}^{m+3}\\cdot2^{2m}, {n}\\cdot\\log{n}\\cdot {\\sqrt{2}}^{n}\\right\\}\\right)$, {which can be large up to $2^{74}$ and $2^{109}$ for $n=128$ and $256$, respectively, when $m=8$.

This gives an approach to design secure white-box implementation with practical storage.

We expect that our analytic toolbox initiates the research on white-box implementation design.}

We present new ideas for decreasing the size of secure memory needed for hardware implementations of

hash-sequence based signatures proposed recently by Buldas, Laanoja and Truu (in the following referred to as BLT).

In their scheme, a message $m$ is signed by time-stamping a concatenation $m\\| z_t$ of the message and the one-time

pseudo-random password $z_t$ intended to sign messages at a particular time $t$.

The signature is valid only if the time-stamp points to the same time $t$. Hence, the one time passwords cannot be abused after their use.

To efficiently and securely implement such a scheme at the client side, dedicated hardware is needed and thereby, the solutions that save the (secure) memory and computational time are important. For such schemes, the memory consumption directly depends on the efficiency of the \\emph{hash sequence reversal algorithms}.

The best known reversal algorithm for the BLT scheme uses $O(\\log^2 \\ell)$ memory.

This means that for a signing key that is valid for one year (i.e. $\\ell\\approx 2^{25}$ with one-second time resolution), the device needs to store about $25^2=625$ hash

values which for SHA-256 hashing algorithm means about $20$ K bytes of secure memory.

Another problem with hash sequence reversal algorithms is that they mostly assume that the signature device is always

connected to the computer or has an independent power supply. This is a serious limitation for smart-card implementations of the scheme.

We show first that a mini Public Key Infrastructure in the signature device can be used to lower the memory consumption about twice.

There is a master key (i.e. a hash sequence) that is used to certify short term (about five minutes) signing keys

so that a signature consists of a short term certificate which is a hash chain in the master hash tree (used to authenticate the master hash sequence), and a hash chain that is used to authenticate a particular hash value $z_t$ in the sequence.

We also discuss how to implement hash sequence signatures in devices that have no power supply and are not regularly connected to

computers, such as smart-cards which are often used as personal digital signature devices. General-purpose cryptographic smart-cards also have many

restrictions that limit the use of hash sequence signatures. For example, their hashing speed is relatively low: up to 500 hashing steps per second;

their secure memory is of limited size, etc. This all combined with irregular usage patterns makes the use of hash sequence signatures questionable.

We show why the hash sequence signature (in its original form) cannot be used as the CA signature in the mini PKI solution.

Finally, we propose a new type of hash sequence signature that is more suitable for smart-card implementations.

We consider the following problem: Assuming that Alice and Bob have an integer interval $[a, e]$ and an integer $b$ respectively, for a commitment $c$ to $b$, Alice and Bob jointly check whether $b$ is within $[a, e]$ without revealing their inputs, where either party may behave maliciously. A special case of the problem is the secure integer comparison in the malicious model. This problem mainly arises from location-based access control systems where one party needs to assure to the other party that its location is within some definite area.

Our main result is a constant-round protocol that exhibit the square of $\\log e$ communication and the square of $\\log e$ exponentiations with simulation-based security. At the heart of the construction is perfect $k$-ary index and corresponding zero-knowledge proof techniques.

We consider a more general case of the problem where the interval is substituted by a union of intervals.

Submission: 16 January 2015
Notification: 17 March 2015
From June 2 to June 5
Location: New York, USA
More Information: http://acns2015.cs.columbia.edu/

From August 14 to August 18
Location: Santa Barbara, USA
More Information: http://www.iacr.org/conferences/

From August 16 to August 20
Location: Santa Barbara, USA
More Information: http://www.iacr.org/conferences/

It is a long-standing open problem to prove the existence of (deterministic) hard-core predicates for the Diffie-Hellman problem over finite fields, without resorting to the generic approaches for any one-way functions (e.g., the Goldreich-Levin hard-core predicates). Fazio et al. (FGPS, Crypto \'13) make important progress on this problem by defining a weaker Computational Diffie-Hellman (CDH) problem over $\\mathbb{F}_{p^2}$, i.e., Partial-CDH problem, and proving the unpredictability of every single bit of one of the coordinates of the secret Diffie-Hellman value. However, the existence of specific hard-core predicates for the regular CDH problems defined over finite fields remains unproven. This paper closes this gap and resolves all the open problems left in FGPS:

1. We prove that the Partial-CDH problem over finite fields $\\mathbb{F}_{p^2}$ is as hard as the regular CDH problem over the same fields.

2. We show a much stronger and more generalized result over finite fields $\\mathbb{F}_{p^2}$---not only the regular CDH problem over $\\mathbb{F}_{p^2}$ admits hard-core predicates but every individual bit of the CDH value is unpredictable.

3. We extend the Partial-CDH problem to define the $d$-th CDH problem over finite fields $\\mathbb{F}_{p^t}$ for any polynomial $t>1$ and for any $0\\leq d \\leq t-1$. We show that computing any single coordinate of the CDH value over $\\mathbb{F}_{p^t}$ is equivalent to computing the entire CDH value.

4. We prove that over finite fields $\\mathbb{F}_{p^t}$ for any polynomial~$t>1$, each $d$-th CDH problem except $d \\neq 0$ admits a large class of hard-core predicates, including every individual bit of the $d$-th coordinate. Hence almost all individual bits of the CDH value of the regular CDH problem over finite fields $\\mathbb{F}_{p^t}$ for $t>1$ are hard-core.