Selected Areas in Cryptography

The voice privacy of IS-95 CDMA cellular systemis analyzed in this paper. By exploiting information redundancy on the downlink traffic channel, it is shown that an eavesdropper can recover the voice privacy mask after eavesdropping the transmission on the downlink traffic channel for about one second. Thus, IS-95 CDMA voice privacy is vulnerable under ciphertext-only attacks.

We show that an additive stream cipher with an n-bit key has an effective key size of n-min(l, lgM) against the key collision attack, and of 2n/3+ lg(n/3) + max(n - l, 0) against the time memory tradeoff attack, when the the attacker knows l linear equations over the plaintext and has M ciphertexts encrypted with M distinct unknown secret keys.

Lastly, we analyze the IP, TCP, and UDP protocols and some typical protocol constructs, and show that they contain significant linear redundancy. We conclude with observations on the use of stream ciphers for Internet security.

At Crypto’90, Koyama and Terada proposed a family of cryptographic functions for application to symmetric block ciphers. Youssef and Tavares showed that this family is affine and hence it is completely insecure. In response to this, Koyama and Terada modified their design, by including a data dependent operation between layers. The modified family of circuits was presented in the first international security workshop (ISW’97). In this paper, we show that the modified circuit can be easily broken by a differential-like attack. More explicitly, we show that after d rounds, and for any specific key K, the input space can be partitioned into M ≤ 2^d sets such that the ciphertext Y of each set is related to the plaintext X by an affine relation. The expected value of M ≪ 2^d. Our attack enables us to explicitly recover these linear relations. We were able to break an 8—round 64—bit version of this family in few minutes on a workstation using less than 2²⁰ chosen plaintext-ciphertext pairs.

The development process of the Advanced Encryption Standard (AES) was launched in 1997 by the US government through NIST. The Decorrelated Fast Cipher (DFC) was the CNRS proposal for the AES, among 14 other candidates in 1998. It was based on the recent decorrelation theory, to obtain certain security proofs covering linear and differential cryptanalysis. DFC received numerous comments. In particular, Coppersmith discovered a weakness in the key schedule. We address this weakness by a slight modification on DFC. This paper presents the specifications and rationales of DFC version 2, and discusses issues raised during the AES process.

This paper proposes a nested (hierarchical) SPN structure and the symmetric block cipher “Hierocrypt”. In the nested SPN structure, lower-level SPN structures are recursively embedded into S-box positions in SPN of the higher level. This structure recursively assures the lower bound of active S-box number, and high security level is efficiently realized. The 8-round Hierocrypt is implemented in C language on Pentium III, and shows the middle-class performance of final AES candidates.

We introduce a new family of symmetric block ciphers based on group bases. The main advantage of our approach is its full scalability. It enables us to construct, for instance, a trivial 8-bit Caesar cipher as well as a strong 256-bit cipher with 512-bit key, both from the same specification. We discuss the practical aspects of the design, especially the choice of carrier groups, generation of random group bases and an efficient factorization algorithm. We also describe how the cryptographic properties of the system are optimized, and analyze the influence of parameters on its security. Finally we present some experimental results regarding the speed and security of concrete ciphers from the family.

Koblitz, Solinas, and others investigated a family of elliptic curves which admit faster cryptosystem computations.In this paper, we generalize their ideas to hyperelliptic curves of genus 2.We consider the following two hyperelliptic curves C _α : v ² + uv = u ⁵ + αu ² + 1 defined over F₂ with α = 0, 1, and show how to speed up the arithmetic in the Jacobian J_Cα(F_2n) by making use of the Frobenius automorphism.With two precomputations, we are able to obtain a speed-up by a factor of 5.5 compared to the generic double-and-add-method in the Jacobian.If we allow 6 precomputations, we are even able to speed up by a factor of 7.

In this paper, the complexity of a squaring operation using polynomial basis (PB) in a class of finite fields F_2m is evaluated. The main results are as follows: 1. When the field is generated with an irreducible trinomial f(x) = x^m + x^k + 1, 1 ≤ k ≤ m/2 where both m and k are odd, a PB squaring operation requires m - 1/2 bit operations. 2. When the field is generated with an irreducible trinomial f(x0) = x^m + x^k + 1, 1 ≤ k ≤ m/2 where m + k is odd and k ≠ m/2 , a PB squaring operation requires m + k - 1/2 bit operations. 3. When the field is generated with an irreducible trinomial f(x) = x^m+x^m/2+1, a PB squaring operation requires m + 2/4 bit operations.

A metering scheme is a protocol in which an audit agency is able to measure the interaction between clients and servers on the web during a certain number of time frames. Naor and Pinkas [7] considered metering schemes in which any server is able to construct a proof to be sent to the audit agency if and only if it has been visited by at least a number, say h, of clients in a given time frame. In their schemes the parameter h is fixed and is the same for any server and any time frame. In this paper we introduce dynamic multi-threshold metering schemes, that are metering schemes in which there is a threshold associated to any server for any time frame. We mainly focus on the efficiency of dynamic multi-threshold metering schemes, by minimizing the information received and distributed by clients. This is important because the clients participating in the metering process do not receive any money from the audit agency.

We present a protocol for the exchange of individually authenticated data streams among N parties. Our authentication procedure is fast, because it only requires the computation of hash functions - we do not need digital signatures, that are substantially less efficient. The authentication information is also short: two hash values for every block of data. Since there are no shared secrets, this information does not grow with N, the number of parties.

The paper describes a novel application of a Privilege Management Infrastructure (PMI) to enforce copyright protection in electronic content distribution. The PMI is “global” in nature and thus permits customers to gain access to content on any appropriate device. The use of a PMI also allows delegation of access to content. A unique key encrypting scheme provides increased security over other methods of protecting electronic content.

We demonstrate the existence of an efficient block cipher with the property that whenever it is composed with any non-perfect cipher, the resulting product is strictly more secure, against an ideal adversary, than the original cipher. We call this property universal security amplification, and note that it holds trivially for a one-time pad (a stream cipher). However, as far as we are aware, this is the first efficient block cipher with this property. Several practical implications of this result are considered.

Decorrelation theory has recently been proposed in order to address the security of block ciphers and other cryptographic primitives over a finite domain. We show here how to extend it to infinite domains, which can be used in the Message Authentication Code (MAC) case. In 1994, Bellare, Kilian and Rogaway proved that CBC-MAC is secure when the input length is fixed. This has been extended by Petrank and Rackoff in 1997 with a variable length.

In this paper, we prove a result similar to Petrank and Rackoff’s one by using decorrelation theory. This leads to a slightly improved result and a more compact proof.

This result is meant to be a general proving technique for security, which can be compared to the approach which was announced by Maurer at CRYPTO’99.

Hash functions play an essential role in many areas of cryptographic applications such as digital signature, authentication, and key derivation. In this paper, we propose a new hash function with variable output length, namely HAS-V, to meet the needs of various security levels desired among different applications. A great deal of attention was paid to balance the characteristics of security and performance. The use of message expansion, 4-variable Boolean functions, variable and fixed amounts of shifts, and interrelated parallel lines provide a high level of security for HAS-V. Experiments show that HAS-V is about 19% faster than SHA-1, 31% faster than RIPEMD-160, and 26% faster than HAVAL on a Pentium PC.

Welch-Gong (WG) transformation sequences are binary sequences of period 2ⁿ. 1 with 2-level auto correlation. These sequences were discovered by Golomb, Gong and Gaal in 1998 and verified for 5 ≤ n ≤ 20. Later on, No, Chung and Yun found another way to construct the WG sequences and verified their result for 5 ≤ n ≤ 23. Dillon first proved this result for odd n in 1998, and finally, Dobbertin and Dillon proved it for even n in 1999. In this paper, we investigate a two-faced property of the WG transformation sequences for application in stream ciphers and pseudo-random number generators. One is to present randomness or unpredictability of the WG transformation sequences. The other is to exhibit the security property of the WG transformations regarded as Boolean functions. It is shown that the WG transformation sequences, in addition to the known 2-level auto correlation, have threelevel cross correlation with m-sequences, large linear ! span increasing exponentially with n and efficient implementation. Thus this is the first type of pseudo-random sequences with good correlation and statistic properties, large linear span and efficient implementation. When the WG transformation are regarded as Boolean functions, it is proved that they have high nonlinearity. A criterion for whether the WG transformations regarded as Boolean functions are r-resilient is derived. It is shown that the WG transformations regarded as Boolean functions have large linear span (this concept will be defined in this paper) and high degree.

A general stream cipher with memory in which each ciphertext symbol depends on both the current and previous plaintext symbols, as well as each plaintext symbol depends on both the current and previous ciphertext symbols, is pointed out. It is shown how to convert any keystream generator into a stream cipher with memory and their security is discussed. It is proposed how to construct secure self-synchronizing stream ciphers, keyed hash functions, hash functions, and block ciphers from any secure stream cipher with memory. Rather new and unusual designs can thus be obtained, such as the designs of block ciphers and (keyed) hash functions based on clock-controlled shift registers only.

A family of keystream generators, called the LILI keystream generators, is proposed for use in stream cipher applications and the security of these generators is investigated with respect to currently known attacks. The design is simple and scalable, based on two binary linear feedback shift registers combined in a simple way, using both irregular clocking and nonlinear functions. The design provides the basic security requirements such as a long period and high linear complexity, and is resistant to known cryptanalytic attacks.

It has recently been shown that when m > 1/2n - 1, the nonlinearity N _f of an mth-order correlation immune function f with n variables satisfies the condition of N _f ≤ 2^n-1 - 2^m, and that when m > 1/2n - 2 and f is a balanced function, the nonlinearity satisfies N _f ≤2^n-1 - 2^m+1. In this work we prove that the general inequality, namely N _f ≤ 2^n-1 - 2^m, can be improved to N _f ≤ 2^n-1 - 2^m+1 for m ≥ 0.6n - 0.4, regardless of the balance of the function. We also show that correlation immune functions achieving the maximum nonlinearity for these functions have close relationships with plateaued functions. The latter have a number of cryptographically desirable properties.

We present a new non-interactive public key distribution system based on the class group of a non-maximal imaginary quadratic order Cl(Δ_p). The main advantage of our system over earlier proposals based on (ℤ/nℤ). [19],[21] is that embedding id information into group elements in a cyclic subgroup of the class group is easy (straight-forward embedding into prime ideals suffices) and secure, since the entire class group is cyclic with very high probability. In order to compute discrete logarithms in the class group, the KGC needs to know the prime factorization of Δ_p = Δ1p². We present an algorithm for computing discrete logarithms in Cl(Δ_p) by reducing the problem to computing discrete logarithms in Cl(Δ₁) and either Fp or Fp². We prove that a similar reduction works for arbitrary non-maximal orders, and that it has polynomial complexity if the factorization of the conductor is known.

Cryptosystems based on the discrete logarithm problem in the infrastructure of a real quadratic number field [7],[19],[2] are very interesting from a theoretical point of view, because this problem is known to be at least as hard as, and when considering todays algorithms - as in [11] - much harder than, factoring integers. However it seems that the cryptosystems sketched in [2] have not been implemented yet and consequently it is hard to evaluate the practical relevance of these systems. Furthermore as [2] lacks any proofs regarding the involved approximation precisions, it was not clear whether the second communication round, as required in [7],[19], really could be avoided without substantial slowdown. In this work we will prove a bound for the necessary approximation precision of an exponentiation using quadratic numbers in power product representation and show that the precision given in [2] can be lowered considerably. As the highly space consuming power products can not be applied in environments with limited RAM, we will propose a simple (CRIAD¹-) arithmetic which entirely avoids these power products. Beside the obvious savings in terms of space this method is also about 30% faster. Furthermore one may apply more sophisticated exponentiation techniques, which finally result in a ten-fold speedup compared to [2]. CRIAD is an abbreviation for Close Reduced Ideal and Approximated relative Distance

In this paper, we first show that there are several equivalent keys for t + 1 chosen plaintexts if the degree of the reduced cipher is t-1. This is against the claim by Jakobsen and Knudsen. We also derive an upper bound on the number of equivalent last round keys for t + 1 chosen plaintexts. We further show an efficient method which finds all the equivalent keys by using Rabin’s root finding algorithm. We call our attack root finding interpolation attack

The block cipher GOST was proposed in former Soviet Union in 1989. In this paper we present the first result of differential cryptanalysis of GOST with reduced number of rounds. By introducing the idea of using a set of differential characteristics, which is a partitioning type, we can reduce the influence of the key value upon the probability as well as get high differential probability. Using 2⁵¹ chosen plaintexts the key of 13-round GOST can be obtained. Next this differential cryptanalysis is expanded with combining related-key attack. Using 2⁵⁶ chosen plaintexts the key of 21 rounds of GOST can be obtained.

This paper studies the upper bounds of the maximum differential and linear characteristic probabilities of Feistel ciphers with SPN round function. In the same way as for SPN ciphers, we consider the minimum number of differential and linear active s-boxes, which provides a measure of the upper bounds of these probabilities, in order to evaluate the security against differential and linear cryptanalyses. The purpose of this work is to clarify the (lower bound of) minimum numbers of active s-boxes in some consecutive rounds of Feistel ciphers, i.e., in three, four, six, eight, and twelve consecutive rounds, using differential and linear branch numbers Pd, Pl, respectively. Furthermore, we investigate the necessary condition for desirable P-functions, which means that the round functions are invulnerable to both differential and linear cryptanalyses. As an example, we show the round function of Camellia, which satisfies the condition.