Progress in Cryptology – INDOCRYPT 2007

In MyCrypt 2005, Augot, Finiasz, and Sendrier proposed FSB, a family of cryptographic hash functions. The security claim of the FSB hashes is based on a coding theory problem with hard average-case complexity. In the ECRYPT 2007 Hash Function Workshop, new versions with essentially the same compression function but radically different security parameters and an additional final transformation were presented. We show that hardness of average-case complexity of the underlying problem is irrelevant in collision search by presenting a linearization method that can be used to produce collisions in a matter of seconds on a desktop PC for the variant of FSB with claimed 2

128

security.

We show that a 2

112.9

collision attack exists against the FORK-256 Hash Function. The attack is surprisingly simple compared to existing published FORK-256 cryptanalysis work, yet is the best known result against the new, tweaked version of the hash. The attack is based on “splitting” the message schedule and compression function into two halves in a meet-in-the-middle attack. This in turn reduces the space of possible hash function results, which leads to significantly faster collision search. The attack strategy is also applicable to the original version of FORK-256 published in FSE 2006.

HMAC is a popular MAC (Message Authentication Code) that is based on a cryptographic hash function. HMAC is provided with a formal proof of security, in which it is proven to be a PRF (Pseudo-Random Function) under the condition that its underlying compression function is a PRF. Nonetheless, the security of HMAC is limited by a birthday attack, that is, HMAC using a compression function with

n

-bit output gets forged after about 2

n

/2

queries. In this paper we resolve this problem by introducing novel construction we call

L

-Lane HMAC. Our construction is provided with concrete-security reduction accomplishing a security guarantee well beyond the birthday limit.

L

-Lane HMAC requires more invocations to the compression function than the conventional HMAC, but the performance decline is smaller than those of previous constructs. In addition,

L

-Lane HMAC inherits the design principles of the original HMAC, such as single-key usage and off-the-shelf hash-function calls.

We study the security of elliptic curve Diffie-Hellman secret keys in the presence of oracles that provide partial information on the value of the key. Unlike the corresponding problem for finite fields, little is known about this problem, and in the case of elliptic curves the difficulty of representing large point multiplications in an algebraic manner leads to new obstacles that are not present in the case of finite fields. To circumvent this obstruction, we introduce a

small

multiplier version of the hidden number problem, and we use its properties to analyze the security of certain Diffie-Hellman bits. We suggest new character sum conjectures that guarantee the uniqueness of solutions to the hidden number problem, and provide some evidence in support of the conjectures by showing that they hold on average in certain cases. We also present a Gröbner basis algorithm for solving the hidden number problem and recovering the Diffie-Hellman secret key when the elliptic curve is defined over a constant degree extension field and the oracle is a coordinate function in the polynomial basis.

In this paper, we prove that for any polynomial function

f

of fixed degree without multiple roots, the probability that all the (

f

(

x

 + 1),

f

(

x

 + 2), ...,

f

(

x

 + 

κ

)) are quadratic non-residue is

$\approx \frac{1}{2^\kappa}$

. In particular for

f

(

x

) = 

x

3

 + 

ax

 + 

b

corresponding to the elliptic curve

y

2

 = 

x

3

 + 

ax

 + 

b

, it implies that the quadratic residues (

f

(

x

 + 1),

f

(

x

 + 2), ... in a finite field are sufficiently randomly distributed. Using this result we describe an efficient implementation of El-Gamal Cryptosystem. that requires efficient computation of a mapping between plain-texts and the points on the elliptic curve.

The stream cipher TPypy has been designed by Biham and Seberry in January 2007 as the strongest member of the Py-family ciphers, after weaknesses in the other members Py, Pypy, Py6 were discovered. One main contribution of the paper is the detection of related-key weaknesses in the Py-family of ciphers including the strongest member TPypy. Under related keys, we show a distinguishing attack on TPypy with data complexity 2

192.3

which is lower than the previous best known attack on the cipher by a factor of 2

88

. It is shown that the above attack also works on the other members TPy, Pypy and Py. A second contribution of the paper is design and analysis of two fast ciphers RCR-64 and RCR-32 which are derived from the TPy and the TPypy respectively. The performances of the RCR-64 and the RCR-32 are 2.7 cycles/byte and 4.45 cycles/byte on Pentium III (note that the speeds of the ciphers Py, Pypy and RC4 are 2.8, 4.58 and 7.3 cycles/byte). Based on our security analysis, we conjecture that no attacks lower than brute force are possible on the RCR ciphers.

In this paper, we study the security of AES-192 against related-key differential-linear cryptanalysis, which is the first attempt using this technique. Among our results, we present two variant attacks on 7-round AES-192 and one attack on 8 rounds using a 5-round related-key differential-linear distinguisher. One key point of the construction of the distinguisher is the special property of

MC

operation of AES. Compared with the best known results of related-key impossible differential attacks and related-key rectangle attacks on AES-192, the results presented in this paper are not better than them, but the work is a new attempt, and we hope further work may be done to derive better results in the future.

The Data Encryption Standard (DES) is a 64-bit block cipher. Despite its short key size of 56 bits, DES continues to be used to protect financial transactions valued at billions of Euros. In this paper, we investigate the strength of DES against attacks that use a limited number of plaintexts and ciphertexts. By mounting meet-in-the-middle attacks on reduced-round DES, we find that up to 6-round DES is susceptible to this kind of attacks. The results of this paper lead to a better understanding on the way DES can be used.

We study the interplay of network connectivity and the issues related to feasibility and optimality for

probabilistic perfectly reliable message transmission

(PPRMT) and

probabilistic perfectly secure message transmission

(PPSMT) in a

synchronous

network under the influence of a

mixed

adversary who possesses

unbounded

computing power and can corrupt different set of nodes in Byzantine, omission, failstop and passive fashion simultaneously. Our results show that that

randomness helps in the possibility of multiphase PPSMT and significantly improves the lower bound on communication complexity for both PPRMT and PPSMT protocols!!

Secret sharing is a basic fundamental cryptographic task. Motivated by the virtual automata abstraction and swarm computing, we investigate an extension of the

k

-secret sharing scheme, in which the secret components are changed on the fly, independently and without (internal) communication, as a reaction to a global external trigger. The changes are made while maintaining the requirement that

k

or more secret shares may reveal the secret and no

k

 − 1 or fewer reveal the secret.

The application considered is a swarm of mobile processes, each maintaining a share of the secret which may change according to common outside inputs e.g., inputs received by sensors attached to the process.

The proposed schemes support addition and removal of processes from the swarm as well as corruption of a small portion of the processes in the swarm.

This paper is on efficient implementation techniques of Elliptic Curve Cryptography. In particular, we improve timings for Jacobi-quartic (3M+4S) and Hessian (7M+1S or 3M+6S) doubling operations. We provide a faster mixed-addition (7M+3S+1d) on modified Jacobi-quartic coordinates. We introduce tripling formulae for Jacobi-quartic (4M+11S+2d), Jacobi-intersection (4M+10S+5d or 7M+7S+3d), Edwards (9M+4S) and Hessian (8M+6S+1d) forms. We show that Hessian tripling costs 6M+4C+1d for Hessian curves defined over a field of characteristic 3. We discuss an alternative way of choosing the base point in successive squaring based scalar multiplication algorithms. Using this technique, we improve the latest mixed-addition formulae for Jacobi-intersection (10M+2S+1d), Hessian (5M+6S) and Edwards (9M+1S+ 1d+4a) forms. We discuss the significance of these optimizations for elliptic curve cryptography.

Double base number systems (DBNS) provide an elegant way to represent numbers. These representations also have many interesting and useful properties, which have been exploited to find many applications in Cryptography and Signal Processing. In the current article we present a scheme to represent numbers in double (and multi-) base format by combinatorial objects like graphs and diagraphs. The combinatorial representation leads to proof of some interesting results about the double and multibase representation of integers. These proofs are based on simple combinatorial arguments. In this article we have provided a graph theoretic proof of the recurrence relation satisfied by the number of double base representations of a given integer. The result has been further generalized to more than 2 bases. Also, we have uncovered some interesting properties of the sequence representing the number of double base representation of a positive integer

n

. It is expected that the combinatorial representation can serve as a tool for a better understanding of the double (and multi-) base number systems.

This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options:

many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves;

double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case;

many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006).

The analysis takes account of speedups such as

S

–

M

tradeoffs and includes recent advances such as inverted Edwards coordinates.

The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader.

Transitive signature is an interesting primitive due to Micali and Rivest. During the past years, many constructions of transitive signatures have been proposed based on various assumptions. In this paper, we provide the first construction of transitive signature schemes by using braid groups. In the random oracle model, our proposals are proved to be transitively unforgeable against adaptively chosen message attack under the assumption of the intractability of one-more matching conjugate problem (OM-MCP) over braid groups. Moreover, the proposed schemes are invulnerable to currently known quantum attacks.

To construct a suitable and secure proxy re-signature scheme is not an easy job, up to now, there exist only three schemes, one is proposed by Blaze

et al.

[6] at EUROCRYPT 1998, and the others are proposed by Ateniese and Hohenberger [2] at ACM CCS 2005. However, none of these schemes is proved in the standard model (i.e., do not rely on the random oracle heuristic). In this paper, based on Waters’ approach [20], we first propose a multi-use bidirectional proxy re-signature scheme, denoted as

S

mb

, which is existentially unforgeable in the standard model. And then, we extend

S

mb

to be a multi-use bidirectional ID-based proxy re-signature scheme, denoted by

S

id

 − 

mb

, which is also existentially unforgeable in the standard model. Both of these two proposed schemes are computationally efficient, and their security bases on the Computational Diffie-Hellman (CDH) assumption.

Cryptographic embedded systems are vulnerable to Differential Power Analysis (DPA). In particular, the S-boxes of a block cipher are known to be the most sensitive parts with respect to this very kind of attack. While many sound countermeasures have been proposed to withstand this weakness, most of them are too costly to be adopted in real-life implementations of cryptographic algorithms. In this paper, we focus on a widely adopted lightweight variation on the well-known Duplication Method. While it is known that this design is vulnerable to higher-order DPA attacks, we show that it can also be efficiently broken by first-order DPA attacks. Finally, we point out ad hoc costless countermeasures that circumvent our attacks.

For elliptic curve based cryptosystems, the discrete logarithm problem must be hard to solve. But even when this is true from a mathematical point of view, side-channel attacks could be used to reveal information about the key if proper countermeasures are not used. In this paper, we study the difficulty of the discrete logarithm problem when partial information about the key is revealed by side channel attacks. We provide algorithms to solve the discrete logarithm problem for generic groups with partial knowledge of the key which are considerably better than using a square-root attack on the whole key or doing an exhaustive search using the extra information, under two different scenarios. In the first scenario, we assume that a sequence of contiguous bits of the key is revealed. In the second scenario, we assume that partial information on the “Square and Multiply Chain” is revealed.

SMS4 is a 128-bit block cipher which is used in the WAPI standard in China for protecting wireless transmission data. Due to the nature that the functions deployed in the round transformations of SMS4 operate on two different fields GF(2

8

) and GF(2), it is difficult to analyze this cipher algebraically. In this paper we describe a new block cipher called ESMS4, which uses only algebraic operations over GF(2

8

). The new cipher is an extension of SMS4 in the sense that SMS4 can be embedded into ESMS4 with restricted plaintext space and key spaces. Thus, the SMS4 cipher can be investigated through this embedding over GF(2

8

). Based on this new cipher, we represent the SMS4 cipher with an overdetermined, sparse multivariate quadratic equation system over GF(2

8

). Furthermore, we estimate the computational complexity of the XSL algorithm for solving the equation system and find that the complexity is 2

77

when solving the whole system of equations.

We study a tweakable blockcipher for arbitrarily long message (also called a tweakable enciphering scheme) that consists of a universal hash function and an expansion, a keyed function with short input and long output. Such schemes, called HCTR and HCH, have been recently proposed. They used (a variant of) the counter mode of a blockcipher for the expansion. We provide a security proof of a structure that underlies HCTR and HCH. We prove that the expansion can be instantiated with any function secure against Known-plaintext attacks (KPAs), which is called a weak pseudorandom function (WPRF). As an application of our proof, we provide efficient blockcipher-based schemes comparable to HCH and HCTR. For the double-block-length case, our result is an interesting extension of previous attempts to build a double-block-length cryptographic permutation using WPRF.

Saarinen recently proposed a chosen IV statistical attack, called the

d

-monomial test, and used it to find weaknesses in several proposed stream ciphers. In this paper we generalize this idea and propose a framework for chosen IV statistical attacks using a polynomial description. We propose a few new statistical attacks, apply them on some existing stream cipher proposals, and give some conclusions regarding the strength of their IV initialization. In particular, we experimentally detected statistical weaknesses in some state bits of Grain-128 with full IV initialization as well as in the keystream of Trivium using an initialization reduced to 736 rounds from 1152 rounds. We also propose some stronger alternative initialization schemes with respect to these statistical attacks.

Public-key encryption schemes with searchable keywords are useful to delegate searching capabilities on encrypted data to a third party, who does not hold the entire secret key, but only an appropriate token which allows searching operations but preserves data privacy. Such notion was previously proved to imply identity-based public-key encryption [5] and to be equivalent to anonymous (or key-private) identity-based encryption which are useful for fully-private communication.

So far all presented public-key encryption with keyword search (

PEKS

) schemes were based on bilinear forms and finding a

PEKS

that is not based on bilinear forms has been an open problem since the notion of

PEKS

was first introduced in [5]. We construct a public-key encryption scheme with keyword search based on a variant of the

quadratic residuosity problem

. We obtain our scheme using a non-trivial transformation of Cocks’ identity-based encryption scheme [9]. Thus we show that the primitive of

PEKS

can be based on additional intractability assumptions which is a conventional desiderata about all cryptographic primitives.

We present a proxy cryptosystem based on a certificate-based encryption scheme. The proposed scheme inherits the merits of certificate-based encryption systems: no-key-escrow and implicit certification. In addition, the proposed scheme allows the proxy’s decryption power to be revoked even during the valid period of the proxy key without changing the original decryptor’s public information. Few proxy schemes have this property, and ours is more efficient than the existing ones. We show that our proposal is IND-CBPd-Rev-CCA secure under the bilinear Diffie-Hellman assumption in the random oracle model.

In this paper, we present a computationally efficient password authenticated key exchange protocol based on quadratic residues. The protocol, called

QR

-

CEKE

, is derived from the protocol

QR

-

EKE

, a previously published password authenticated key exchange protocol based on quadratic residues. The computational time for the client, however, is significant reduced in the protocol

QR

-

CEKE

. In comparison with

QR

-

EKE

, the protocol

QR

-

CEKE

is more suitable to an imbalanced computing environment where a low-end client device communicates with a powerful server over a broadband network. Based on number-theoretic techniques, we show that the computationally efficient password authenticated key exchange protocol is secure against

residue attacks

, a special type of off-line dictionary attack against password-authenticated key exchange protocols based on factorization. We also provide a formal security analysis of

QR

-

CEKE

under the factoring assumption and the random oracle model.

Non-trivial lower bounds on the linear complexity are derived for a sequence obtained by performing

k

or fewer operations on a single period of a periodic sequence over

$\mathbb{F}_q$

. An operation is a substitution, an insertion, or a deletion of a symbol. The bounds derived are similar to those previously established for either

k

substitutions,

k

insertions, or

k

deletions within a single period. The bounds are useful when

T

/2

k

 < 

L

 < 

T

/

k

, where

L

is the linear complexity of the original sequence and

T

is its period.

There has been a wide ranging discussion on the contents copyright protection in digital contents distribution systems. Fiat and Tassa proposed the framework of

dynamic traitor tracing

. Their framework requires dynamic computation transactions according to the real-time responses of the pirate, and it presumes real-time observation of contents redistribution and therefore cannot be simply utilized in an application where such an assumption is not valid. In this paper, we propose a new scheme that not only provides the advantages of dynamic traitor tracing schemes but also overcomes their problems.

Feedback with Carry Shift Registers (FCSRs) are a promising alternative to LFSRs in the design of stream ciphers. The previous constructions based on FCSRs were dedicated to hardware applications [3]. In this paper, we will describe X-FCSR a family of software oriented stream ciphers using FCSRs. The core of the system is composed of two 256-bits FCSRs. We propose two versions: X-FCSR-128 and X-FCSR-256 which output respectively 128 and 256 bits at each iteration. We study the resistance of our design against several cryptanalyses. These stream ciphers achieve a high throughput and are suitable for software applications (6.3 cycles/byte).

In a recent paper [10], Mishra and Dimitrov have proposed a window-based Elliptic Curve (EC) scalar multiplication using double-base number representation. Their methods were rather heuristic. In this paper, given the window lengths

w

2

and

w

3

for the bases 2 and 3, we first show how to fix the number of windows,

ρ

, and then obtain a Double Base Number System (DBNS) representation of the scalar

n

suitable for window-based EC scalar multiplication. Using the DBNS representation, we obtain our first algorithm that uses a small table of precomputed EC points. We then modify this algorithm to obtain a faster algorithm by reducing the number of EC additions at the cost of storing a larger number of precomputed points in a table. Explicit constructions of the tables are also given.

For an iterated hash, it is expected that, the hash transform inherits all the cryptographic properties of its compression function. This means that the cryptanalytic validation task can be confined to the compression function. Bellare and Ristenpart [3] introduced a notion Multi-Property preserving (MPP) to characterize the goal. In their paper, the MPP was collision resistance preserving (CR-pr), pseudo random function preserving (PRF-pr) and pseudo random oracle preserving (PRO-pr). The probability distribution of hash transform influences the randomness and adversary’s advantage on collision finding, we expect that the hash transform is almost uniformly distributed and this property is inherited from its compression function and call it Almost-Uniform Distribution preserving (AUD-pr). However, AUD-pr is not always true for MD-strengthening Merkle-Damgård [7,12] transform. It is proved that the distribution of Merkle-Damgård transform is not only influenced by output distribution of compression function, but also influenced by the iteration times. Then, we recommend a new construction and give proofs of satisfying MPP that is CR-pr, PRO-pr, PRF-pr and AUD-pr.

Gate level masking is one of the most popular countermeasures against Differential Power Attack (DPA). The present paper proposes a masking technique for AND gates, which are then used to build a balanced and masked multiplier in

GF

(2

n

). The circuits are shown to be computationally secure and have no glitches which are dependent on unmasked data. Finally, the masked multiplier in

GF

(2

4

) is used to implement a masked AES S-Box in

GF

(2

4

)

2

. Power measurements are taken to support the claim of random power consumption.

Linear Feedback Shift Registers (LFSRs) are used as building blocks for many stream ciphers, wherein, an

n

-degree primitive connection polynomial is used as a feedback function to realize an

n

-bit LFSR. This paper shows that such LFSRs are susceptible to power analysis based Side Channel Attacks (SCA). The major contribution of this paper is the observation that the state of an

n

-bit LFSR can be determined by making

O

(

n

) power measurements. Interestingly,

neither the primitive polynomial nor the value of n

be known to the adversary launching the proposed attack

. The paper also proposes a simple countermeasure for the SCA that uses

n

additional flipflops.

Okeya has established that HMAC/NMAC implementations based on only Matyas-Meyer-Oseas (

MMO

) PGV scheme and his two refined PGV schemes are secure against side channel DPA attacks when the block cipher in these constructions is secure against these attacks. The significant result of Okeya’s analysis is that the implementations of HMAC/NMAC with the Davies-Meyer (

DM

) compression function based hash functions such as SHA-1 are vulnerable to DPA attacks. In this paper, first we show a partial key recovery attack on NMAC/HMAC based on Okeya’s two refined PGV schemes by taking practical constraints into consideration. Next, we propose new hybrid NMAC/HMAC schemes for security against side channel attacks assuming that their underlying block cipher is ideal. We show a hybrid NMAC/HMAC proposal which can be instantiated with

DM

and a slight variant to it allowing NMAC/HMAC to use hash functions such as SHA-1. We then show that M-NMAC, MDx-MAC and a variant of the envelope MAC scheme based on

DM

with an ideal block cipher are secure against DPA attacks.

The filter generator is an important building block in many stream ciphers. We present here an attack that recovers the initial state of the hidden LFSR by detecting the positions where the inputs of the filtering function are equal to zero. This attack requires the precomputation of low weight multiples of the LFSR generating polynomial. By a careful analysis, we show that the attack complexity is among the best known and work for almost all cryptographic filtering functions.

We present optimized FPGA implementations of three tweakable enciphering schemes, namely, HCH, HCTR and EME using AES-128 as the underlying block cipher. We report performance timings and hardware resources occupied by these three modes when using a fully pipelined AES core and a sequential AES design. Our experimental results suggest that in terms of area HCTR, HCH and HCHfp (a variant of HCH) require more area than EME. However, HCTR performs the best in terms of speed followed by HCHfp, EME and HCH.