Selected Areas in Cryptography

In this paper we present several weaknesses in the key scheduling algorithm of RC4, and describe their cryptanalytic significance. We identify a large number of weak keys, in which knowledge of a small number of key bits suffices to determine many state and output bits with non-negligible probability. We use these weak keys to construct new distinguishers for RC4, and to mount related key attacks with practical complexities. Finally, we show that RC4 is completely insecure in a common mode of operation which is used in the widely deployed Wired Equivalent Privacy protocol (WEP, which is part of the 802.11 standard), in which a fixed secret key is concatenated with known IV modifiers in order to encrypt different messages. Our new passive ciphertext-only attack on this mode can recover an arbitrarily long key in a negligible amount of time which grows only linearly with its size, both for 24 and 128 bit IV modifiers.

SSC2 is a stream cipher that operates by XORing the output of two “half-ciphers”. The first half-cipher is constructed from a linear feedback shift register (LFSR) with a non-linear filter. The second halfcipher is constructed from a lagged Fibonacci generator (LFG) and a multiplexor that chooses values from the Fibonacci register. The second half-cipher has a small cycle length π≈ 2⁵². The initial state of the LFSR is derived by performing a fast correlation attack on the sequence resulting when XORing the key-stream at an interval of π words (thus cancelling the effect of the LFG). This attack requires around 2²⁵ words of this sequence and a few hours of computation. The initial state of the LFG is then derived from around 15300 outputs using around one second of computation.

The encryption system E ₀ , which is the encryption system used in the Bluetooth specification, is examined. In the current paper, a method of deriving the cipher key from a set of known keystream bits is given. The running time for this method depends on the amount of known keystream available, varying from O(2⁸⁴) if 132 bits are available to O(2⁷³), given 2⁴³ bits of known keystream.

Cryptographic Boolean functions should have large distance to functions with simple algebraic description to avoid cryptanalytic attacks based on successive approximation of the round function such as the interpolation attack. Hyper-bent functions achieve the maximal minimum distance to all the coordinate functions of all bijective monomials. However, this class of functions exists only for functions with even number of inputs. In this paper we provide some constructions for Boolean functions with odd number of inputs that achieve large distance to all the coordinate functions of all bijective monomials.

In this paper we provide a new generalized construction method of highly nonlinear t-resilient functions, F : \( \mathbb{F}_2^n \mapsto \mathbb{F}_2^m \). The construction is based on the use of linear error correcting codes together with multiple output bent functions. Given a linear [u, m, t + 1] code we show that it is possible to construct n-variable, m-output, t-resilient functions with nonlinearity \( 2^{n - 1} - 2^{\left\lceil {\frac{{n + u - m - 1}} {2}} \right\rceil } \) for n ≥ u + 3m. The method provides currently best known nonlinearity results.

In stream ciphers, we should use a t-resilient Boolean function f(X) with large nonlinearity to resist fast correlation attacks and linear attacks. Further, in order to be secure against an extension of linear attacks, we wish to find a t-resilient function f(X) which has a large distance even from low degree Boolean functions. From this point of view, we define a new covering radius p(t, r, n) as the maximum distance between a t-resilient function f(X) and the r-th order Reed-Muller code RM(r, n). We next derive its lower and upper bounds. Finally, we present a table of numerical bounds for p(t, r, n).

In this paper we show some efficient and unconditionally secure oblivious transfer reductions. Our main tool is a class of functions that generalizes the Zig-zag functions, introduced by Brassard, Crepéau, and Sántha in [6]. We show necessary and sufficient conditions for the existence of such generalized functions, and some characterizations in terms of well known combinatorial structures. Moreover, we point out an interesting relation between these functions and ramp secret sharing schemes where each share is a single bit.

We show that there is a very straightforward closed algebraic formula for the Rijndael block cipher. This formula is highly structured and far simpler then algebraic formulations of any other block cipher we know. The security of Rijndael depends on a new and untested hardness assumption: it is computationally infeasible to solve equations of this type. The lack of research on this new assumption raises concerns over the wisdom of using Rijndael for security-critical applications.

In [15], Keliher et al. present a new method for upper bounding the maximum average linear hull probability (MALHP) for SPNs, a value which is required to make claims about provable security against linear cryptanalysis. Application of this method to Rijndael (AES) yields an upper bound of UB = 2^-75 when 7 or more rounds are approximated, corresponding to a lower bound on the data complexity of S ₃₂ ^UB = 2⁸⁰ (for a 96.7% success rate). In the current paper, we improve this upper bound for Rijndael by taking into consideration the distribution of linear probability values for the (unique) Rijndael 8×8 s-box. Our new upper bound on the MALHP when 9 rounds are approximated is 2^-92, corresponding to a lower bound on the data complexity of 2⁹⁷ (again for a 96.7% success rate). [This is after completing 43% of the computation; however, we believe that values have stabilized-see Section 7]

Cryptography and Coding Theory are closely knitted in many respects. Recently, the problem of Decoding Reed Solomon Codes (aka Polynomial Reconstruction) was suggested as an intractability assumption upon which the security of cryptographic protocols can be based. This has initiated a line of research that exploited the rich algebraic structure of the problem and related subproblems of which in the cryptographic setting. Here we give a short overview of recent works on the subject and the novel applications that were enabled due to this development.

Here we provide a comparison of several projective point transformations of an elliptic curve defined over GF(2 ⁿ ) and rank their performance.We provide strategies to achieve improved implementations of each. Our work shows that under certain conditions, these strategies can alter the ranking of these projective point arithmetic methods.

We propose a method for increasing the speed of scalar multiplication on binary anomalous (Koblitz) elliptic curves. By introducing a generator which produces random pairs (k, [k]P) of special shape, we exhibit a specific setting where the number of elliptic curve operations is reduced by 25% to 50% compared with the general case when k is chosen uniformly. This generator can be used when an ephemeral pair (k, [k]P) is needed by a cryptographic algorithm, and especially for Elliptic Curve Diffie-Hellman key exchange, ECDSA signature and El-Gamal encryption. The presented algorithm combines normal and polynomial basis operations to achieve optimal performance. We prove that a probabilistic signature scheme using our generator remains secure against chosen message attacks.

This paper compares different approaches for computing power products \( \prod _{1 \leqslant i \leqslant k} g_i^{e_i } \) in commutative groups. We look at the conventional simultaneous exponentiation approach and present an alternative strategy, interleaving exponentiation. Our comparison shows that in general groups, sometimes the conventional method and sometimes interleaving exponentiation is more efficient. In groups where inverting elements is easy (e.g. elliptic curves), interleaving exponentiation with signed exponent recoding usually wins over the conventional method.

In this paper we address two important topics in hyperelliptic cryptography. The first is how to construct in a verifiably random manner hyperelliptic curves for use in cryptography in generas two and three. The second topic is how to perform divisor compression in the hyperelliptic case. Hence, in both cases we generalise concepts used in the more familiar elliptic curve case to the hyperelliptic context.

SC2000 is a 128-bit block cipher with key length of 128, 192 or 256 bits, developed by Fujitsu Laboratories LTD. For 128-bit keys, SC2000 consists of 6.5 rounds, and for 192- and 256-bit keys it consists of 7.5 rounds. In this paper we demonstrate two different 3.5-round differential characteristics that hold with probabilities 2^-106 and 2^-107. These characteristics can be used to extract up to 32 bits of the first and last round keys in a 4.5-round variant of SC2000.

Linear cryptanalysis remains the most powerful attack against DES at this time. Given 2⁴³ known plaintext-ciphertext pairs, Matsui expected a complexity of less than 2⁴³ DES evaluations in 85 % of the cases for recovering the key. In this paper, we present a theoretical and experimental complexity analysis of this attack, which has been simulated 21 times using the idle time of several computers. The experimental results suggest a complexity upper-bounded by 2⁴¹ DES evaluations in 85 % of the case, while more than the half of the experiments needed less than 2³⁹ DES evaluations. In addition, we give a detailed theoretical analysis of the attack complexity.

This paper extends the analysis of Pollard’s rho algorithm for solving a single instance of the discrete logarithm problem in a finite cyclic group G to the case of solving more than one instance of the discrete logarithm problem in the same group G. We analyze Pollard’s rho algorithm when used to iteratively solve all the instances. We also analyze the situation when the goal is to solve any one of the multiple instances using any DLP algorithm.

For cryptographic applications, normal bases have received considerable attention, especially for hardware implementation. In this article, we consider fast software algorithms for normal basis multiplication over the extended binary field GF(2^m). We present a vector-level algorithm which essentially eliminates the bit-wise inner products needed in the conventional approach to the normal basis multiplication. We then present another algorithm which significantly reduces the dynamic instruction counts. Both algorithms utilize the full width of the data-path of the general purpose processor on which the software is to be executed. We also consider composite fields and present an algorithm which can provide further speed-up and an added flexibility toward hardwaresoftware co-design of processors for very large finite fields.

A new method for multiplication of large integers and designed for efficient software implementation is presented and compared with the well-known “schoolbook” method that is currently used for both software and hardware implementations of public-key cryptographic techniques. The comparison for the software-efficient method is made in terms of the required number of basic operations on small integers. It is shown that a significant performance gain is achieved by the new software-efficient method for integersfrom 192 to 1024 bitsin length, which is the range of interest for all current public-key implementations. For 1024-bit integer multiplication, the savings over the schoolbook method is conservatively estimated to be about 33%. A new method for multiplication of large integers, which is analogous to the new software efficient method but is designed for efficient hardware implementation, is also presented and compared to the schoolbook method in terms of the number of processor clock cycles required.

We propose a new method to compute x-coordinate of kP + lQ simultaneously on the elliptic curve with Montgomery form over IFp without precomputed points. To compute x-coordinate of kP +lQ is required in ECDSA signature verification. The proposed method is about 25% faster than the method using scalar multiplication and the recovery of Y-coordinate of kP and lQ on the elliptic curve with Montgomery form over \( \mathbb{F}_p \) and also slightly faster than the simultaneous scalar multiplication on the elliptic curve with Weierstrass form over \( \mathbb{F}_p \) using NAF and mixed coordinates. Furthermore, our methodis applicable to Montgomery method on elliptic curves over \( \mathbb{F}_{2^n } \).

We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2^k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.

This paper will propose an efficient algorithm that utilizes the signed-digit representation to compute the kth term of a characteristic sequence generated by a linear feedback shift register of order 3 over GF(q). We will also propose an efficient algorithm to compute the (h-dk)th term of the characteristic sequence based on the knowledge of the kth term where k is unknown. Incorporating these results, we construct the ElGamal-like digital signature algorithm for the public-key cryptography based on the 3rd-order characteristic sequences which was proposed by Gong and Harn in 1999.

A. K. Lenstra and E. R. Verheul in [2] proposed a very efficient way called XTR in which certain subgroup of the Galois field GF(p ⁶ ) can be represented by elements in GF(p2). At the end of their paper [2], they briefly mentioned on a method of generalizing their idea to the field GF(p ^6m ). In this paper, we give a systematic design of this generalization and discuss about optimal choices for p and m with respect to performances. If we choose m large enough, we can reduce the size of p as small as the word size of common processors. In such a case, this extended XTR is well suited for the processors with optimized arithmetic on integers of word size.

Lattices are regular arrangements of points in n-dimensional space, whose study appeared in the 19th century in both number theory and crystallography. Since the appearance of the celebrated Lenstra-Lenstra-Lovász lattice basis reduction algorithm twenty years ago, lattices have had surprising applications in cryptology. Until recently, the applications of lattices to cryptology were only negative, as lattices were used to break various cryptographic schemes. Paradoxically, several positive cryptographic applications of lattices have emerged in the past five years: there now exist public-key cryptosystems based on the hardness of lattice problems, and lattices play a crucial rôle in a few security proofs. In this talk, we will try to survey the main examples of the two faces of lattices in cryptology. The full material of this talk appeared in [2]. A preliminary version can be found in [1].

We present a new message authentication code. It is based on a two trail construction, which underlies the unkeyed hash function RIPEMD-160. It is in comparison with the MDx-MAC based on RIPEMD-160, much more efficient on short messages (that is on messages of 512 or 1024 bits) and percentage-wise a little bit more efficient on long messages. Moreover, it handles key-changes very efficiently. This positive fact remains if we compare our Two-Track-MAC with HMAC based on RIPEMD-160.

We present data structures for complement covering with intervals and their application for digital identity revocation. We give lower bounds showing the structures to be nearly optimal. Our method improves upon the schemes proposed by S. Micali [5],[6] and Aiello, Lodha, Ostrovsky [1] by reducing the communication between a Certificate Authority and public directories while keeping the number of tokens per user in the public key certificate small.

Let n be a large composite number. Without factoring n, the computation of a^{2 t} (mod n) given a, t with gcd(a, n) = 1 and t < n can be done in t squarings modulo n. For t ≪ n (e.g., n > 2¹⁰²⁴ and t < 2¹⁰⁰), no lower complexity than t squarings is known to fulfill this task. Rivest et al suggested to use such constructions as good candidates for realising timed-release crypto problems.

We argue the necessity for a zero-knowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in log₂ t standard crypto operations, the correctness of (a ^e )^{2 t} (mod n) with respect to a ^e where e is an RSA encryption exponent. With such a proof, a Timed-release Encryption of a message M can be given as a ^{2 t} M (mod n) with the assertion that the correct decryption of the RSA ciphertext M ^e (mod n) can be obtained by performing t squarings modulo n starting from a. Timed-release RSA signatures can be constructed analogously.