Progress in Cryptology - INDOCRYPT 2008

The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is

slidable

, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams. There are 2

256

and more then 2

39

such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of such related pairs efficiently as well as detect such pairs in large portions of key-stream very efficiently. We show that Salsa20 does not have 256-bit security if one considers general birthday and related key distinguishing and key-recovery attacks.

In cryptology we commonly face the problem of finding an unknown key

K

from the output of an easily computable keyed function

F

(

C

,

K

) where the attacker has the power to choose the public variable

C

. In this work we focus on self-synchronizing stream ciphers. First we show how to model these primitives in the above-mentioned general problem by relating appropriate functions

F

to the underlying ciphers. Then we apply the recently proposed framework presented at AfricaCrypt’08 by Fischer

et. al.

for dealing with this kind of problems to the proposed T-function based self-synchronizing stream cipher by Klimov and Shamir at FSE’05 and show how to deduce some non-trivial information about the key. We also open a new window for answering a crucial question raised by Fischer

et. al.

regarding the problem of finding weak IV bits which is essential for their attack.

In this paper, the RC4 Key Scheduling Algorithm (KSA) is theoretically studied to reveal non-uniformity in the expected number of times each value of the permutation is touched by the indices

i

,

j

. Based on our analysis and the results available in the literature regarding the existing weaknesses of RC4, few additional layers over the RC4 KSA and RC4 Pseudo-Random Generation Algorithm (PRGA) are proposed. Analysis of the modified cipher (we call it RC4

 + 

) shows that this new strategy avoids existing weaknesses of RC4.

A new bias is detected in the key scheduling algorithm of RC4 and a novel framework that advantageously combines this new bias with the existing ones is proposed. Using the new bias, a different algorithm is proposed to retrieve the RC4 key given the state table. The new method not only improves the success probability but also provides a more efficient way of calculation in comparison with the previous methods for any key size. The efficiency of the algorithm is demonstrated experimentally. If the key length is 40 bits, the secret key is retrieved with a 99% success rate in 0.007 seconds. The success probability for retrieving the 128 bit RC4 key is also increased significantly. 128-bit key can be retrieved with 3% success rate in 185 seconds and 7.45% success rate in 1572 seconds on a 2.67GHz Intel CPU.

We investigate the security of the hash function design called

RadioGatún

in a recently proposed framework of sponge functions. We show that previously introduced symmetric trails can hardly be used to construct collisions and to find a second preimage efficiently. As a generalization of truncated differentials, trails with linear and non-linear restrictions on differences are proposed. We use these trails to find semi-free-start collisions and second preimages with the meet-in-the middle approach and the complexity in the gap between claimed security level and the birthday bound. We also provide some observations on lower bounds on the complexity of our methods with respect to the length of the trail used. This is the best attack on

RadioGatún

.

Joux’s multicollision attack is one of the most striking results on hash functions and also one of the simplest: it computes a

k

-collision on iterated hashes in time

$\lceil \log_2 k\rceil\cdot 2^{n/2}$

, whereas

k

!

1/

k

·2

n

(

k

 − 1)/

k

was thought to be optimal. Kelsey and Schneier improved this to 3·2

n

/2

if storage 2

n

/2

is available and if the compression functions admits easily found fixed-points. This paper presents a simple technique that reduces this cost to 2

n

/2

and negligible memory, when the IV can be chosen by the attacker. Additional benefits are shorter messages than the Kelsey/Schneier attack and cost-optimality.

We present a new type of 2-block collisions for MD5. The colliding messages differ in words

m

2

,

m

9

,

m

12

in both blocks. The differential paths for the collisions were generated by our implementation of Stevens algorithm [11]. The actual colliding messages were found by a version of Klima’s algorithm involving tunnels [3].

In this work, we provide new and improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP ’08. The success probability of our 22-step attack is 1 for both SHA-256 and SHA-512. The computational efforts for the 23-step and 24-step SHA-256 attacks are respectively 2

11.5

and 2

28.5

calls to the corresponding step reduced SHA-256. The corresponding values for the 23 and 24-step SHA-512 attack are respectively 2

16.5

and 2

32.5

calls. Using a look-up table having 2

32

(resp. 2

64

) entries the computational effort for finding 24-step SHA-256 (resp. SHA-512) collisions can be reduced to 2

15.5

(resp. 2

22.5

) calls. We exhibit colliding message pairs for 22, 23 and 24-step SHA-256 and SHA-512. This is the

first

time that a colliding message pair for 24-step SHA-512 is provided. The previous work on 23 and 24-step SHA-2 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikolić and Biryukov (NB) at FSE ’08. The reported computational efforts are 2

18

and 2

28.5

for 23 and 24-step SHA-256 respectively and 2

43.9

and 2

53

for 23 and 24-step SHA-512. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-2 family. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.

An identity based cryptosystem is a public key cryptosystem where the public key can be represented as an arbitrary string. Hierarchical identity based cryptography is a generalization of identity based encryption that mirrors an organizational hierarchy. It allows a root private key generator to distribute the workload by delegating private key generation and identity authentication to lower-level private key generators. Most of hierarchical identity based encryption schemes are provably secure in the random oracles or weak models without random oracles such as selective-ID model.

Currently, there is no hierarchical identity based encryption scheme that is fully CCA2 secure in the standard model, with short public parameters and a tight reduction. In this paper, we first propose a hierarchical identity based encryption scheme that is fully secure in the standard model. And it achieves IND-ID-CCA2 security based on the decision q-TBDHE problem. The ciphertext size is independent of the level of the hierarchy. Moreover, our scheme has short public parameters, high efficiency and a tight reduction simultaneously.

The fuzzy identity-based encryption schemes are attribute-based encryption schemes such that each party with the private key for an attribute set

$\mathcal{S}$

is allowed to decrypt ciphertexts encrypted by an attribute set

$\mathcal{S}'$

, if and only if the two sets

$\mathcal{S}$

and

$\mathcal{S}'$

are close to each other as measured by the set-overlap-distance metric. That is, there is a threshold

t

and, if

t

out of

n

attributes of

$\mathcal{S}$

are also included in

$\mathcal{S}'$

, the receivers can decrypt the ciphertexts. In previous schemes, this threshold

t

is fixed when private keys are generated and the length of ciphertexts are linear to

n

. In this paper, we propose a novel fuzzy identity-based encryption scheme where the threshold

t

is flexible by nature and the length of ciphertexts are linear to

n

 − 

t

. The latter property makes the scheme short if it allows receivers to decrypt ciphertexts when error rate

n

 − 

t

, i.e., distance between the two attribute sets, is low.

Recently, the concept of proxy re-encryption has been shown very useful in a number of applications, especially in enforcing access control policies. In existing proxy re-encryption schemes, the delegatee can decrypt all ciphertexts for the delegator after re-encryption by the proxy. Consequently, in order to implement fine-grained access control policies, the delegator needs to either use multiple key pairs or trust the proxy to behave honestly. In this paper, we extend this concept and propose type-based proxy re-encryption, which enables the delegator to selectively delegate his decryption right to the delegatee while only needs one key pair. As a result, type-based proxy re-encryption enables the delegator to implement fine-grained policies with one key pair without any additional trust on the proxy. We provide a security model for our concept and provide formal definitions for semantic security and ciphertext privacy which is a valuable attribute in privacy-sensitive contexts. We propose two type-based proxy re-encryption schemes: one is CPA secure with ciphertext privacy while the other is CCA secure without ciphertext privacy.

Undeniable signatures were proposed to limit the verification property of ordinary digital signatures. In fact, the verification of such signatures cannot be attained without the help of the signer, via the confirmation/denial protocols. Later, the concept was refined to give the possibility of converting the issued undeniable signatures into ordinary ones by publishing a

universal

receipt that turns them publicly verifiable.

In this paper, we present the first generic construction for universally convertible undeniable signatures from certain weakly secure cryptosystems and any secure digital signature scheme. Next, we give two specific approaches for building universally convertible undeniable signatures from a large class of pairing-based signatures. These methods find a nice and practical instantiation with known encryption and signature schemes. For instance, we achieve the most efficient undeniable signatures with regard to the signature length and cost, the underlying assumption and the security model. We believe these constructions could be an interesting starting point to develop more efficient schemes or give better security analyses of the existing ones.

Entity recognition does not ask whether the message is from some entity

X

, just whether a message is from the same entity as a previous message. This turns turns out to be very useful for low-end devices. The current paper proposes a new protocol – the “Jane Doe Protocol” –, and provides a formal proof of its concrete security. The protocol neither employs asymmetric cryptography, nor a trusted third party, nor any key pre-distribution. It is suitable for light-weight cryptographic devices such as sensor network motes and RFID tags.

In ACNS’06, Cliff et al. proposed the password-based server aided key exchange (PSAKE) as one of password-based authenticated key exchanges in the three-party setting (3-party PAKE) in which two clients with different passwords exchange a session key by the help of their corresponding server. Though they also studied a strong security definition of 3-party PAKE, their security model is not strong enough because there are desirable security properties which cannot be captured. In this paper, we define a new formal security model of 3-party PAKE which is stronger than the previous model. Our model captures all known desirable security requirements of 3-party PAKE, like resistance to key-compromise impersonation, to leakage of ephemeral private keys of servers and to undetectable on-line dictionary attack. Also, we propose a new scheme as an improvement of PSAKE with the optimal number of rounds for a client, which is secure in the sense of our model.

In this paper, we propose a round efficient

unconditionally secure multiparty computation

(UMPC) protocol in

information theoretic

model with

n

 > 2

t

players, in the absence of any physical broadcast channel. Our protocol communicates

${\cal O}(n^4)$

field elements per multiplication and requires

${\cal O}(n \log(n) + {\cal D})$

rounds, even if up to

t

players are under the control of an active adversary having

unbounded computing power

, where

${\cal D}$

denotes the multiplicative depth of the circuit representing the function to be computed securely. In the absence of a physical broadcast channel and with

n

 > 2

t

players, the best known UMPC protocol with minimum number of rounds, requires

${\cal O}(n^2{\cal D})$

rounds and communicates

${\cal O}(n^6)$

field elements per multiplication. On the other hand, the best known UMPC protocol with minimum communication complexity requires communication overhead of

${\cal O}(n^2)$

field elements per multiplication, but has a round complexity of

${\cal O}(n^3 +{\cal D})$

rounds. Hence our UMPC protocol is the most round efficient protocol so far and ranks second according to communication complexity.

In Indocrypt 2005 Viet et al. first proposed an anonymous password-based key exchange protocol: APAKE and its extension:

k

-out-of-

n

APAKE. Then Shin et al. presented an improved protocol TAP. In this paper, we first show that the TAP protocol is vulnerable to two attacks. One is an impersonating attack and the other is an off-line dictionary attack, which is also applied to

k

-out-of-

n

APAKE. Furthermore, we propose a novel anonymous password-based key exchange protocol, and prove its security in the random oracle model under the square computational Diffie-Hellman assumption and decision inverted-additive Diffie-Hellman assumption. We also extend our protocol to the distributed setting, which is secure against the proposed attacks.

Since the very beginnings of cryptography many centuries ago, key management has been one of the main challenges in cryptographic research. In case of a group of players wanting to share a common key, many schemes exist in the literature, managing groups where all players are equal or proposing solutions where the group is structured as a hierarchy. This paper presents the first key management scheme suitable for a hierarchy where no central authority is needed and permitting to manage a graph representing the hierarchical group with possibly several roots. This is achieved by using a HMAC and a non-hierarchical group key agreement scheme in an intricate manner and introducing the notion of virtual node.

Scan chain based attacks are a kind of side channel attack, which targets one of the most important feature of today’s hardware - the test circuitry. Design for Testability (DFT) is a design technique that adds certain testability features to a hardware design. On the other hand, this very feature opens up a side channel for cryptanalysis, rendering crypto-devices vulnerable to scan-based attack. Our work studies scan attack as a general threat to stream ciphers and arrives at a general relation between the design of stream ciphers and their vulnerability to scan attack. Finally, we propose a scheme which we show to thwart the attacks and is more secure than other contemporary strategies.

One of the eSTREAM final portfolio ciphers is the hardware-oriented stream cipher Trivium. It is based on 3 nonlinear feedback shift registers with a linear output function. Although Trivium has attached a lot of interest, it remains unbroken by passive attacks.

At FSE 2008 a differential fault analysis of Trivium was presented. It is based on the fact that one-bit fault induction reveals many polynomial equations among which a few are linear and a few quadratic in the inner state bits. The attack needs roughly 43 induced one-bit random faults and uses only linear and quadratic equations.

In this paper we present an improvement of this attack. It requires only 3.2 one-bit fault injections in average to recover the Trivium inner state (and consequently its key) while in the best case it succeeds after 2 fault injections. We termed this attack floating fault analysis since it exploits the floating model of the cipher. The use of this model leads to the transformation of many obtained high-degree equations into linear equations.

The presented work shows how a change of the cipher representation may result in much better attack.

This paper presents algebraic collision attacks, a new powerful cryptanalytic method based on side-channel leakage which allows for low measurement counts needed for a successful key recovery in case of AES. As opposed to many other side-channel attacks, these techniques are essentially based on the internal structure of the attacked cryptographic algorithm, namely, on the algebraic properties of AES. Moreover, we derived the probability distributions of Euclidean distance for collisions and non-collisions. On this basis, a statistical framework for finding the instances of side-channel traces leaking most key information in collision attacks is proposed.

Additionally to these theoretical findings, the paper also contains a practical evaluation of these side-channel collision attacks for a real-world microcontroller platform similar to many smart card ICs. To our best knowledge, this is the first real-world study of collision attacks based on generalized internal collisions. We also combined our methods with ternary voting [1] which is a recent multiple-differential collision detection technique using profiling, where neither plaintexts, ciphertexts nor keys have to be known in the profiling stage.

In this paper we present two new attacks on round reduced versions of the AES. We present the first application of the related-key boomerang attack on 7 and 9 rounds of AES-192. The 7-round attack requires only 2

18

chosen plaintexts and ciphertexts and needs 2

67.5

encryptions. We extend our attack to nine rounds of AES-192. This leaves to a data complexity of 2

67

chosen plaintexts and ciphertexts using about 2

143.33

encryptions to break 9 rounds of AES-192.

In this paper we apply impossible differential attacks to reduced round AES. Using various techniques, including the early abort approach and key schedule considerations, we significantly improve previously known attacks due to Bahrak-Aref and Phan. The improvement of these attacks leads to better impossible differential attacks on 7-round AES-128 and AES-192, as well as to better impossible differential attacks on 8-round AES-256.

In this paper, we provide a theoretical infrastructure of the reflection attack. In addition, we mount the reflection attack on some ciphers such as GOST, DEAL and a variant of DES. The attack method exploits certain similarities among round functions which have not been utilized in the previous self-similarity attacks. As an illustration, we introduce a chosen plaintext attack on full-round GOST under the assumption that its S-boxes are bijective. The attack works on approximately 2

224

keys and its complexity is 2

192

steps with 2

32

chosen plaintexts. Also, we introduce a known plaintext attack on 30-round GOST, which works for any key. The key is recovered with 2

224

steps by using only 2

32

known plaintexts. As another example, we deduce that the reflection attack works on DEAL for certain keys. For instance, a 192-bit DEAL-key can be identified as a weak key by using approximately 2

66

known plaintexts. Then, the key can be recovered with 2

136

steps. The number of weak keys of 192-bit DEAL is roughly 2

80

.

Serpent is an SP Network block cipher submitted to the AES competition and chosen as one of its five finalists. The security of Serpent is widely acknowledged, especially as the best known attack so far is a differential-linear attack on only 11 rounds out of the 32 rounds of the cipher.

In this paper we introduce a more accurate analysis of the differential-linear attack on 11-round Serpent. The analysis involves both theoretical aspects as well as experimental results which suggest that previous attacks had overestimated complexities. Following our findings we are able to suggest an improved 11-round attack with a lower data complexity. Using the new results, we are able to devise the first known attack on 12-round Serpent.

This paper presents new speed records for AES software, taking advantage of (1) architecture-dependent reduction of instructions used to compute AES and (2) microarchitecture-dependent reduction of cycles used for those instructions. A wide variety of common CPU architectures—amd64, ppc32, sparcv9, and x86—are discussed in detail, along with several specific microarchitectures.

Consider RSA with

N

 = 

pq

,

q

 < 

p

 < 2

q

, public encryption exponent

e

and private decryption exponent

d

. We concentrate on the cases when

e

( = 

N

α

) satisfies

eX

 − 

ZY

 = 1, given |

N

 − 

Z

| = 

N

τ

. Using the idea of Boneh and Durfee (Eurocrypt 1999, IEEE-IT 2000) we show that the LLL algorithm can be efficiently applied to get

Z

when |

Y

| = 

N

γ

and

$\gamma < 4\alpha \tau \left(\frac{1}{4\tau} + \frac{1}{12\alpha} - \sqrt{(\frac{1}{4\tau} +\frac{1}{12\alpha})^2 + \frac{1}{2\alpha \tau} (\frac{1}{12} + \frac{\tau}{24\alpha} - \frac{\alpha}{8\tau})}\right)$

. This idea substantially extends the class of weak keys presented by Nitaj (Africacrypt 2008) when

Z

 = 

ψ

(

p

,

q

,

u

,

v

) = (

p

 − 

u

)(

q

 − 

v

). Further, we consider

Z

 = 

ψ

(

p

,

q

,

u

,

v

) = 

N

 − 

pu

 − 

v

to provide a new class of weak keys in RSA. This idea does not require any kind of factorization as used in Nitaj’s work. A very conservative estimate for the number of such weak exponents is

N

0.75 − 

ε

, where

ε

> 0 is arbitrarily small for suitably large

N

.

Online ciphers are those ciphers whose ciphertexts can be computed in real time by using a length-preserving encryption algorithm. HCBC1 and HCBC2 are two known examples of Hash Cipher Block Chaining online ciphers. The first construction is secure against chosen plaintext adversary (or called CPA-secure) whereas the latter is secure against chosen ciphertext adversary (or called CCA-secure). In this paper, we have provided simple security analysis of these online ciphers. We have also proposed two new more efficient chosen ciphertext secure online ciphers modified-HCBC (MHCBC) and modified-CBC (MCBC). If one uses a finite field multiplication based universal hash function, the former needs one less key and one less field multiplication compared to HCBC2. The MCBC does not need any universal hash function and it needs only one blockcipher key unlike the other three online ciphers where two independent keys (hash function and blockcipher) are required.

The tiny encryption algorithm (TEA) was developed by [4] Wheeler and Needham as a simple computer program for encryption. This paper is the first design-space exploration for hardware implementations of the extended tiny encryption algorithm. It presents efficient implementations of XTEA on FPGAs and ASICs for ultra-low power applications such as RFID tags and wireless sensor nodes as well as fully pipelined designs for high speed applications. A novel ultra-low power implementation is introduced which consumes less area and energy than a comparable AES implementation. Furthermore, XTEA is compared with stream ciphers from the eSTREAM portfolio and lightweight ciphers. The high speed implementations of XTEA operate at 20.6 Gbps (FPGA) or 36.6 Gbps (ASIC).

This paper proposes an efficient high speed implementation of an elliptic curve crypto processor (ECCP) for an FPGA platform. The main optimization goal for the ECCP is efficient implementation of the important underlying finite field primitives namely multiplication and inverse. The techniques proposed maximize the utilization of FPGA resources. Additionally improved scheduling of elliptic curve point arithmetic results in lower number of register files thus reducing the area required and the critical delay of the circuit. Through several comparisons with existing work we demonstrate that the combination of the above techniques helps realize one of the fastest and compact elliptic curve processors.

The Brezing-Weng method is a general framework to generate families of pairing-friendly elliptic curves. Here, we introduce an improvement which can be used to generate more curves with larger discriminants. Apart from the number of curves this yields, it provides an easy way to avoid endomorphism rings with small class number.

The recent introduction of Edwards curves has significantly reduced the cost of addition on elliptic curves. This paper presents new explicit formulae for pairing implementation in Edwards coordinates. We prove our method gives performances similar to those of Miller’s algorithm in Jacobian coordinates and is thus of cryptographic interest when one chooses Edwards curve implementations of protocols in elliptic curve cryptography. The method is faster than the recent proposal of Das and Sarkar for computing pairings on supersingular curves using Edwards coordinates.

In this paper, we investigate how to achieve verifiable secret sharing (VSS) schemes by using the Chinese Remainder Theorem (CRT). We first show that two schemes proposed earlier are not secure by an attack where the dealer is able to distribute inconsistent shares to the users. Then we propose a new VSS scheme based on the CRT and prove its security. Using the proposed VSS scheme, we develop a joint random secret sharing (JRSS) protocol, which, to the best of our knowledge, is the first JRSS protocol based on the CRT.

An attribute based encryption scheme (ABE) is a cryptographic primitive in which every user is identified by a set of attributes, and some function of these attributes is used to determine the ability to decrypt each ciphertext. Chase proposed the first multi authority ABE scheme in TCC 2007 as an answer to an open problem presented by Sahai and Waters in EUROCRYPT 2005. However, her scheme needs a fully trusted central authority which can decrypt every ciphertext in the system. This central authority would endanger the whole system if it’s corrupted.

This paper presents a threshold multi authority fuzzy identity based encryption(MA-FIBE) scheme without a central authority for the first time. An encrypter can encrypt a message such that a user could only decrypt if he has at least

d

k

of the given attributes about the message for at least

t

 + 1,

t

 ≤ 

n

/2 honest authorities of all the

n

attribute authorities in the proposed scheme. The security proof is based on the secrecy of the underlying joint random secret sharing protocol and joint zero secret sharing protocol and the standard decisional bilinear Diffie-Hellman assumption. The proposed MA-FIBE could be extended to the threshold multi authority attribute based encryption (MA-ABE) scheme and be further extended to a proactive MA-ABE scheme.