Available at http://www.itd.nrl.navy.mil/ITD/5540/ieee/cipher/old-conf-rep/conf-rep-sac99.html.
RC4, a stream cipher designed by Rivest for RSA Data Security Inc., has found several commercial applications, but little public analysis has been done to date. In this paper, alleged RC4 (hereafter called RC4) is described and existing analysis outlined. The properties of RC4, and in particular its cycle structure, are discussed. Several variants of a basic "tracking" attack are described, providing experimental results on their success for scaled-down versions of RC4. This analysis shows that, although the full-size RC4 remains secure against known attacks, keystreams are distinguishable from randomly generated bit streams, and the RC4 key can easily be recovered if a significant fraction of the full cycle of keystream bits is generated. The tracking attacks discussed provide a significant improvement over the exhaustive search of the full RC4 keyspace. More work is necessary to make these attacks practical in the case where a reduced keyspace is used.
Abstract and full version may be available after publication.
This paper describes a fast implementation of the elliptic curve version of DSA, as specified in standard documents ANSI X9.62 and IEEE P1363. We did the implementations for the fields GF(2n), using a standard basis, and GF(p). We discuss various design decisions that have to be made for the operations in the underlying field and the operations on elliptic curve points. In particular we conclude that it is a good idea to use projective coordinates for GF(p) but not for GF(2n). We also extend a number of exponentiation algorithms that result in considerable speed gains for DSA, to ECDSA, using a signed binary representation. Finally we present timing results for both types of fields on a PPro-200 based PC, for a C/C++ implementation with small assembly-language optimizations, and make comparisons to other signature algorithms, such as RSA and DSA. We conclude that for practical sizes of fields and moduli, GF(p) is roughly twice as fast as GF(2n). Furthermore, the speed of ECDSA over GF(p) is similar to the speed of DSA, but is approximately 7 times faster than RSA for signing, and 12 times slower than RSA for verification (with public exponent 216+1).
A full version will be available a year after publication.
In this paper we study the security of Substitution Permutation Encryption Networks (SPNS) with randomly selected bijective substitution boxes and a randomly selected invertible linear transformation layer. In particular, our results show that for such a 64-bit SPN using 8 x 8 s-boxes, the number of s-boxes involved in any 2 rounds of a linear approximation or a differential characteristic is equal to 8 with probability exceeding 0.8. For these SPNs the number of plaintext/ciphertext pairs that are required for the basic linear and differential cryptanalysis exceeds 2^64 within 6 rounds. We also provide two construction methods for involution linear transformations based on Maximum Distance Separable Codes.
Available in postscript format.
Much of the security of a block cipher based on the Feistel network depends on the properties of the substitution boxes (s-boxes) used in the round function. This paper presents one effort to construct large, cryptographically secure s-boxes, contrasting theoretical and practical limitations, and highlighting areas for future research.
Several (known) bent function construction methods are summarized, and properties of the resulting bent functions are discussed. A rapid method for calculating the nonlinearity of a boolean function, based on the Hadamard matrix, is described.
The constructions presented are based on the use of bent functions as s-box columns. This ensures that the maximum order strict avalanche criterion (SAC) is satisfied. The construction attempts to maximize nonlinearity, minimize the largest s-box XOR table entry and distance to maximum order bit independence criterion (BIC), and ensures that the column and row weight distributions are approximately binomial. The best characteristics achieved for a generated s-box are compared to those obtained for a randomly generated s-box. The constructed s-box is at least as good with respect to all of these properties, and is slightly better with respect to nonlinearity and distance to higher order BIC.
Available in postscript format.
In this letter we derive an estimate for the expected nonlinearity of a randomly selected injective substitution box. In particular, we show that the expected value of the nonlinearity of a randomly selected 8x32 s-box is about 72. Our theoretical argument is supported with experimental results.
Available in postscript format.