Topics in Cryptology – CT-RSA 2004

In this paper, we present related-key slide attacks on 2-key and 3-key triple DES, and related-key differential and slide attacks on two variants of DESX. First, we show that 2-key and 3-key triple-DES are susceptible to related-key slide attacks. The only previously known such attacks are related-key differential attacks on 3-key triple-DES. Second, we present a related-key differential attack on DESX+, a variant of the DESX with its pre- and post-whitening XOR operations replaced with addition modulo 2⁶⁴. Our attack shows a counter-intuitive result, that DESX+ is weaker than DESX against a related-key attack. Third, we present the first known attacks on DES-EXE, another variant of DESX where the XOR operations and DES encryptions are interchanged. Further, our attacks show that DES-EXE is also weaker than DESX against a related-key attack. This work suggests that extreme care has to be taken when proposing variants of popular block ciphers, that it is not always newer variants that are more resistant to attacks.

Recently, Barkan and Biham proposed the concept of dual ciphers and pointed out that there are 240 dual ciphers of AES (Dual AES). An interesting application of dual ciphers is to design a cipher which run faster than the original cipher. In this paper, we first generalize the dual AES and propose a complete setup procedure to determine all dual ciphers. Then, a hardware implementation of AES based on the combination of dual cipher and composite field is proposed. We demonstrate that our AES design not only offers better performance and smaller area requirement than the design proposed by Wolkerstorfer et al which uses a composite field only. Our results confirm Barkan et al.’s conjecture that it is possible to design an AES cipher more efficiency than ever.

This paper analyses periodic properties of counter assisted stream ciphers. In particular, we analyze constructions where the counter system also has the purpose of providing additional complexity. We then apply the results to the recently proposed stream cipher Rabbit, and increase the lower bound on the internal state period length from 2¹⁵⁸ to 2²¹⁵. With reasonable assumptions we illustrate that the period length of Rabbit is at least the period of the counter system, i.e. at least 2²⁵⁶-1. The investigations are related to a “mod 3” characteristic of Rabbit. Attacks based on this characteristic are discussed and found infeasible.

In this paper, an improved fast correlation attack on stream ciphers is presented. The proposed technique is based on the construction of an unequal error protecting LDPC code from the LFSR output sequence. The unequal error protection allows to achieve lower bit-error probability for initial bits of the LFSR in compared to the rest of the output bits. We show that constructing the unequal error protecting code has also the advantage of reducing the number of output bits involved in decoding to less than the available keystream output bits. Our decoding approach is based on combination of exhaustive search over a subset of information bits and a soft-decision iterative message passing decoding algorithm. We compare the performance of the proposed algorithm with the recent fast correlation attacks. Our results show that we can reduce the number of bits obtained by exhaustive search in half and still get better performance comparing to recent fast correlation attacks based on iterative decoding algorithm. Using the expected number of parity-check equations of certain weights, we find the lower bound on the number of information bits that needs to be obtained by the exhaustive search without compromising the performance.

We present and analyze an adaptive chosen ciphertext secure (IND-CCA) identity-based encryption scheme (IBE) based on the well studied Decisional Diffie-Hellman (DDH) assumption. The scheme is provably secure in the standard model assuming the adversary can corrupt up to a maximum of k users adaptively. This is contrary to the Boneh-Franklin scheme which holds in the random-oracle model.

In this paper, we propose the security notion of certificate-based signature that uses the same parameters and certificate revocation strategy as the encryption scheme presented at Eurocrypt 2003 by Gentry. Certificate-based signature preserves advantages of certificate-based encryption, such as implicit certification and no private key escrow. We present concrete certificate-based signature schemes derived from pairings on elliptic curves and prove their security in the random oracle model assuming that the underlying group is GDH. Additionally, we propose a concrete delegation-by-certificate proxy signature scheme which is derived from a certificate-based signature scheme after simple modifications. Our proxy scheme is provably secure in the random oracle model under the security notion defined by Boldyreva, Palacio and Warinschi.

In this paper, we give a first example of identity based undeniable signature using pairings over elliptic curves. We extend to the identity based setting the security model for the notions of invisibility and anonymity given by Galbraith and Mao in 2003 and we prove that our scheme is existentially unforgeable under the Bilinear Diffie-Hellman assumption in the random oracle model. We also prove that it has the invisibility property under the Decisional Bilinear Diffie-Hellman assumption and we discuss about the efficiency of the scheme.

This note presents a method to compress a Rabin signature [Rab78] to about half of its length.

There has been a lot of recent work in the area of proving in zero-knowledge that an RSA modulus N is in the correct form. For example, protocols have been given that prove that N is the product of: two safe primes, two primes nearly equal in size, etc. Such proof systems are rather remarkable in what they achieve, but may be regarded as being heavyweight protocols due to the computational and messaging overhead they impose. In this paper an efficient zero-knowledge protocol is given that simultaneously proves that N is a Blum integer and that its factorization is recoverable. The proof system requires that the RSA primes p and q be such that p ≡ q ≡ 3 mod 4 and another sematically secure encryption. The solution is therefore amenable for use with systems based on PKCS #1. A proof is given that shows that our algorithm is secure under the integer factorization problem (and can be turned into a non-interactive roof in the random oracle model).

One of the main objectives of server-assisted computation is to reduce the cost of generating public key signatures for ordinary users with their constrained devices. On the other hand, based on nothing more than a one-way function, one-time signatures provide an attractive alternative to public key signatures. This paper revisits server assisted computation for digital signatures to show server assisted one-time signature (SAOTS) that combines the benefits of these two efficiency solutions. The proposed protocol turns out to be a more computational and round-efficient protocol than previous verifiable-server approaches. In addition, SAOTS offers other advantages like verification transparency, getting rid of public key operations for the ordinary user and proving the server’s cheating without storing the signatures.

While technically and conceptually simple, universal re-encryption leads to new types of functionality in mixnet architectures. Conventional mixnets are often called upon to enable players to communicate with one another through channels that are externally anonymous, i.e., that hide information permitting traffic-analysis. Universal re-encryption lets us construct a mixnet of this kind in which servers hold no public or private keying material, and may therefore dispense with the cumbersome requirements of key generation, key distribution, and private-key management. We describe two practical mixnet constructions, one involving asymmetric input ciphertexts, and another with hybrid-ciphertext inputs.

We analyze a new class of primitives called weak commitments. We completely characterize when bit commitments can be reduced to these primitives. Also, we employ a new concept in cryptographic reductions, the rate of a reduction. We propose protocols achieving a nontrivial rate. We provide examples of how to implement these primitives based on oblivious transfer and on quantum mechanics. Using the theory here developed, some open problems on computationally secure quantum bit commitments are solved. Our reductions are information theoretically secure.

Secure authentication frequently depends on the correct recognition of a user’s public key. When there is no certificate authority, this key is obtained from other users using a web of trust. If users can be malicious, trusting the key information they provide is risky. Previous work has suggested the use of redundancy to improve the trustworthiness of user-provided key information. In this paper, we address two issues not previously considered. First, we solve the problem of users who claim multiple, false identities, or who possess multiple keys. Secondly, we show that conflicting certificate information can be exploited to improve trustworthiness. Our methods are demonstrated on both real and synthetic PGP keyrings, and their performance is discussed.

In smartcard encryption and signature applications, randomized algorithms can be used to increase tamper resistance against attacks based on averaging data-dependent power or EMR variations. Oswald and Aigner describe such an algorithm for point multiplication in elliptic curve cryptography (ECC). Assuming an attacker can identify and distinguish additions and doublings during a single point multiplication, it is shown that the algorithm is insecure for repeated use of the same secret key without blinding of that key. Thus blinding should still be used or great care taken to minimise the differences between point additions and doublings.

Many hardware countermeasures against differential power analysis (DPA) attacks have been developed during the last years. Designers of cryptographic devices using such countermeasures to protect their devices have the challenging task to select and implement a suitable combination of countermeasures. Every device has different requirements, and so there is no universal solution to protect devices against DPA attacks.

In this article, a statistical approach is pursued to determine the effect of hardware countermeasures on the number of samples needed in DPA attacks. This approach results in a calculation method that enables designers to assess the resistance of their devices against DPA attacks throughout the design process. This way, different combinations of countermeasures can be easily compared and costly design iterations can be avoided.

Exponentiation is a central process in many public-key cryptosystems such as RSA and DH. This paper introduces the concept of self-randomized exponentiation as an efficient means for preventing DPA-type attacks. Self-randomized exponentiation features several interesting properties:

All these advantages make our method particularly well suited to secure implementations of the RSA cryptosystem in standard mode, on constrained devices like smart cards.

This paper presents a scalable hardware implementation of both commonly used public key cryptosystems, RSA and Elliptic Curve Cryptosystem (ECC) on the same platform. The introduced hardware accelerator features a design which can be varied from very small (less than 20 Kgates) targeting wireless applications, up to a very big design (more than 100 Kgates) used for network security. In latter option it can include a few dedicated large number arithmetic units each of which is a systolic array performing the Montgomery Modular Multiplication (MMM). The bound on the Montgomery parameter has been optimized to facilitate more secure ECC point operations. Furthermore, we present a new possibility for CRT scheme which is less vulnerable to side-channel attacks.

Sedlak’s [Sed] modular multiplication algorithm is one of the first real silicon implementations to speed up the RSA signature generation [RSA] on a smartcard, cf. [DQ]. Theoretically, Sedlak’s algorithm needs on average n/3 steps (i.e., additions/subtractions) to compute the modular product of n-bit numbers. In [FS2] we presented a theoretical algorithm how to speed up Sedlak’s algorithm by an arbitrary integral factor i ≥ 2, i.e., our new algorithm needs on average n/(3 · i) steps in order to compute the modular product of n-bit numbers. As an extension of [FS2] the present paper will show how this theoretical framework can be turned into a practical implementation.

A compact mesh architecture for supporting the relation collection step of the number field sieve is described. Differing from TWIRL, only isolated chips without inter-chip communication are used. According to a preliminary analysis for 768-bit numbers, with a 0.13 μm process one mesh-based device fits on a single chip of ≈(4.9 cm)²—the largest proposed chips in the TWIRL cluster for 768-bit occupy ≈(6.7 cm)².

A 300 mm silicon wafer filled with the mesh-based devices is ≈ 6.3 times slower than a wafer with TWIRL clusters, but due to the moderate chip size, lack of inter-chip communication, and the comparatively regular structure, from a practical point of view the mesh-based approach might be as attractive as TWIRL.

We describe a block-cipher mode of operation, EME, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where mε[1..n]. The mode is parallelizable, but as serial-efficient as the non-parallelizable mode CMC [6]. EME can be used to solve the disk-sector encryption problem. The algorithm entails two layers of ECB encryption and a “lightweight mixing” in between. We prove EME secure, in the reduction-based sense of modern cryptography. We motivate some of the design choices in EME by showing that a few simple modifications of this mode are insecure.

In [8] Vaudenay presented an attack on block cipher CBC-mode encryption when a particular padding method is used. In this paper, we employ a similar approach to analyse the padding methods of the ISO CBC-mode encryption standard. We show that, for several of the padding methods referred to by this standard, we can exploit an oracle returning padding correctness information to efficiently extract plaintext bits. In particular, for one padding scheme, we can extract all plaintext bits with a near-optimal number of oracle queries. For a second scheme, we can efficiently extract plaintext bits from the last (or last-but-one) ciphertext block, and obtain plaintext bits from other blocks faster than exhaustive search.

Hash functions are among the most widespread cryptographic primitives, and are currently used in multiple cryptographic schemes and security protocols, such as IPSec and SSL. In this paper, we investigate a new hardware architecture for a family of dedicated hash functions, including American standards SHA-1 and SHA-512. Our architecture is based on unrolling several message digest steps and executing them in one clock cycle. This modification permits implementing majority of dedicated hash functions with the throughput exceeding 1 Gbit/s using medium-size Xilinx Virtex FPGAs. In particular, our new architecture has enabled us to speed up the implementation of SHA-1 compared to the basic iterative architecture from 544 Mbit/s to 1 Gbit/s using Xilinx XCV1000. The implementation of SHA-512 has been sped up from 717 to 929 Mbit/s for Virtex FPGAs, and exceeded 1 Gbit/s for Virtex-E Xilinx FPGAs.

A hash chain is a sequence of hash values x _i  = hash(x _i − 1) for some initial secret value x ₀. It allows to reveal the final value x _n and to gradually disclose the pre-images x _n − 1, x _n − 2, ... whenever necessary. The correctness of a given value x _i can then be verified by re-computing the chain and comparing the result to x _n . Here we present a method to speed up the verification by outputting some extra information in addition to the chain’s end value x _n . This information allows to relate the verifier’s workload to a variably chosen security bound. That is, on input a putative chain value the verifier determines a security level (i.e., security against adversaries with at most T steps and success probability ε) and performs only a fraction p=p(T,ε) of the original work by using the additional information. We also show lower bounds for the length of this extra information.

A drawback of visual cryptography schemes (VCS) is much loss of contrast in the reconstructed image. This paper shows that no loss of contrast can be almost achieved if we are allowed to use a very simple non-cryptographic operation, reversing black and white. Many copy machines have this function these days. Therefore, our VCS is very attractive.

We demonstrate that some finite fields, including \(\mathbb{F}_{{2}^{210}}\), are weak for elliptic curve cryptography in the sense that any instance of the elliptic curve discrete logarithm problem for any elliptic curve over these fields can be solved in significantly less time than it takes Pollard’s rho method to solve the hardest instances. We discuss the implications of our observations to elliptic curve cryptography, and list some open problems.