Advances in Cryptology — CRYPTO ’96

The use of cryptographic hash functions like MD5 or SHA-1 for message authentication has become a standard approach in many applications, particularly Internet security protocols. Though very easy to implement, these mechanisms are usually based on ad hoc techniques that lack a sound security analysis.

We present new, simple, and practical constructions of message authentication schemes based on a cryptographic hash function. Our schemes, NMAC and HMAC, are proven to be secure as long as the underlying hash function has some reasonable cryptographic strengths. Moreover we show, in a quantitative way, that the schemes retain almost all the security of the underlying hash function. The performance of our schemes is essentially that of the underlying hash function. Moreover they use the hash function (or its compression function) as a black box, so that widely available library code or hardware can be used to implement them in a simple way, and replaceability of the underlying hash function is easily supported.

In this paper, we study unconditionally secure codes that provide authentication without secrecy. Our point of view is the universal hashing approach pioneered by Wegman and Carter in 1981. We first compare several recent universal-hashing based constructions for authentication codes. Then we generalize the theory of universal hashing in order to accommodate the situation where we would like to authenticate a sequence of messages with the same key. Unlike previous methods for doing this, we do not require that each message in the sequence have a “counter” attached to it.

In this paper new families of strongly universal hash functions, or equivalently, authentication codes, are proposed. Their parameters are derived from bounds on exponential sums over finite fields and Galois rings. This is the first time hash families based upon such exponential sums have been considered. Their performance improves the previously best known constructions and they can be made general in their choice of parameters. Furthermore, the constructions are suitable both for hardware and software implementations. The latter is an aspect that is significant and has been considered in several recent papers.

In [1] T. Matsumoto and H. Imai have presented a very efficient “candidate” algorithm, called C*, for asymmetric cryptography. This algorithm was broken in [2]. Then in [3], I have suggested two algorithms, HFE and IP, to repair C*. However the secret key computations of HFE and IP are not as efficient as in the original algorithm C*. Is it possible to repair C* with the same kind of very easy secret key computations? This question is the subject of this paper. Unfortunately, we will see that for all the “easy” transformations of C* the answer is no. However one of the new ideas of this paper will enable us to suggest a candidate algorithm for assymetric signatures of length only 64 bits. An extended version of this paper can be obtained from the author.

We propose considering the problem of electronic cash in the context of a network in which anonymous, untraceable communication is assumed to be possible. We present a formal model for such a network, and define security criteria for an electronic cash system in such a setting. Finally, we show that there exists a remarkably simple electronic cash system which meets the security criteria of the proposed model.

Threshold cryptosystems allow n members of a group to share a private key such that any k of them can use the key without revealing its value. These systems can be divided into two categories, systems which use a trusted center to generate the shares and systems which create the shares in a distributed manner. This paper describes a number of security weaknesses which arise in systems which do not use a trusted center. We show that the n-out-of-n threshold undeniable signature scheme [8] has an actual security of only 2-out-of-n. The discrete log based threshold signature schemes [7, 11, 12] have a weakness in the key generation protocol. Finally, the generalized threshold cryptosystem [9] is not secure for some access structures.

We explain how to forge public parameters for the Digital Signature Standard with two known messages which always produce the same set of valid signatures (what we call a collision). This attack is thwarted by using the generation algorithm suggested in the specifications of the Standard, so it proves one always need to check proper generation. We also present a similar attack when using this generation algorithm within a complexity 2⁷⁴, which is better than the birthday attack which seeks for collisions on the underlying hash function.

The use of cryptographic devices as “black boxes”, namely trusting their internal designs, has been suggested and in fact Capstone technology is offered as a next generation hardware-protected escrow encryption technology. Software cryptographic servers and programs are being offered as well, for use as library functions, as cryptography gets more and more prevalent in computing environments. The question we address in this paper is how the usage of cryptography as a black box exposes users to various threats and attacks that are undetectable in a black-box environment. We present the SETUP (Secretly Embedded Trapdoor with Universal Protection) mechanism, which can be embedded in a cryptographic black-box device. It enables an attacker (the manufacturer) to get the user’s secret (from some stage of the output process of the device) in an unnoticeable fashion, yet protects against attacks by others and against reverse engineering (thus, maintaining the relative advantage of the actual attacker). We also show how the SETUP can, in fact, be employed for the design of “auto-escrowing key” systems. We present embeddings of SETUPs in RSA, El-Gamal, DSA, and private key systems (Kerberos). We implemented an RSA key-generation based SETUP that performs favorably when compared to PGP, a readily available RSA implementation. We also relate message-based SETUPs and subliminal channel attacks. Finally, we reflect on the potential implications of “trust management” in the context of the design and production of cryptosystems.

By carefully measuring the amount of time required to perform private key operations, attackers may be able to find fixed Diffie-Hellman exponents, factor RSA keys, and break other cryptosystems. Against a vulnerable system, the attack is computationally inexpensive and often requires only known ciphertext. Actual systems are potentially at risk, including cryptographic tokens, network-based cryptosystems, and other applications where attackers can make reasonably accurate timing measurements. Techniques for preventing the attack for RSA and Diffie-Hellman are presented. Some cryptosystems will need to be revised to protect against the attack, and new protocols and algorithms may need to incorporate measures to prevent timing attacks.

In this paper we show that for any one-way function f, being able to determine any single bit in ax + b mod p for a random Ω(|x|)-bit prime p and random a, b with probability only slightly better than 50% is equivalent to inverting f(x).

We show that computing the most significant bits of the secret key in a Diffie-Hellman key-exchange protocol from the public keys of the participants is as hard as computing the secret key itself. This is done by studying the following hidden number problem: Given an oracle \( \mathcal{O} \) _α(x) that on input x computes the k most significant bits of α · g ^x mod p, find α modulo p. Our solution can be used to show the hardness of MSB’s in other schemes such s ElGamal’s public key system, scheme. Our results lead us to suggest a new variant of Diffie-Hellman key exchange (and other systems), for which we prove the most significant bit is hard to compute.

Ong-Schnorr identification and signatures are variants of the Fiat-Shamir scheme with short and fast communication and signatures. This scheme uses secret keys that are 2^t-roots modulo N of the public keys, whereas Fiat-Shamir uses square roots modulo N. Security for particular cases has recently been proved by Micali [M94] and Shoup [Sh96].

We prove that identification and signatures are secure for arbitrary moduli N = pq unless N can easily be factored. The proven security of identification against active impersonation attacks depends on the maximal 2-power 2^m that divides either p − 1 or q − 1. We show that signatures are secure against adaptive chosen-message attacks. This proves the security of a very efficient signature scheme.

We present two efficient protocols which implement robust threshold RSA signature schemes, where the power to sign is shared by N players such that any subset of T or more signers can collaborate to produce a valid RSA signature on any given message, but no subset of fewer than T corrupted players can forge a signature. Our protocols are robust in the sense that the correct signature is computed even if up to T − 1 players behave in arbitrarily malicious way during the signature protocol. This in particular includes the cases of players that refuse to participate or that generate incorrect partial signatures. Our robust protocols achieve optimal resiliency as they can tolerate up to (N − 1)/2 faults, and their efficiency is comparable to the efficiency of the underlying threshold RSA signature scheme.

Robust threshold signature schemes have very important applications, since they provide increased security and availability for a signing server (e.g. a certification authority or an electronic cash provider). Solutions for the case of the RSA signature scheme are especially important because of its widespread use. In addition, these techniques apply to shared RSA decryption as well, thus leading to efficient key escrow schemes for RSA.

Our schemes are based on some interesting extensions that we devised for the information checking protocol of T. Rabin and Ben-Or [Rab94], [RB89], and the undeniable signature work initiated by Chaum and van Antwerpen [CA90]. These extensions have some attractive properties, and hence are of independent interest.

For most digital signature schemes used in practice, such as ISO9796/RSA or DSA, it has only been shown that certain plausible cryptographic assumptions, such as the difficulty of factoring integers, computing discrete logarithms or the collision-intractability of certain hash-functions are necessary for the security of the scheme, while their sufficiency is, strictly speaking, an open question.

A clear advantage of such schemes over many signature schemes with security proven relative to such common cryptographic assumptions, is their efficiency: as a result of their relatively weak requirements regarding computation, bandwidth and storage, these schemes have so far beaten proven secure schemes in practice.

We introduce oblivious decision proofs and agnostic decision proofs. In the former, the prover does not have to know whether the instance is in the language proven or not in order to be able to perform the decision proof; in the latter, the prover cannot even find out this information from interacting in the protocol. The proofs are minimum-knowledge, limiting the knowledge exposed to the verifier as well. We demonstrate an easily distributable oblivious computational minimum-knowledge decision proof protocol for proving validity/invalidity of undeniable signatures. This method, using obliviousness, solves an open problem [6] of practical value: the distributed verification of undeniable signatures. We also present an agnostic proof for the same language; an agnostic prover reduces the dissemination of trust in the system; in fact, a prover can be blindfolded and not get to learn the input. As part of the agnostic protocol, and perhaps of independent interest, we exhibit an efficient zero-knowledge proof of knowledge (possession) of both a base and an exponent of an element of a finite group (and similar algebraic structures). Finally, we show a perfect agnostic minimum-knowledge decision proof protocol for quadratic residuosity modulo Blum integers.

We present a very practical string-commitment scheme which is provably secure based solely on collision-free hashing. Our scheme enables a computationally bounded party to commit strings to an unbounded one, and is optimal (within a small constant factor) in terms of interaction, communication, and computation.

Our result also proves that constant round statistical zero-knowledge arguments and constant-round computational zero-knowledge proofs for NP exist based on the existence of collision-free hash functions.

In this paper we investigate the strength of the secret-key algorithm RC5 newly proposed by Ron Rivest. The target version of RC5 works on words of 32 bits, has 12 rounds and a user-selected key of 128 bits. At Crypto’95 Kaliski and Yin estimated the strength of RC5 by differential and linear cryptanalysis. They conjectured that their linear analysis is optimal and that the use of 12 rounds for RC5 is sufficient to make both differential and linear cryptanalysis impractical. In this paper we show that the differential analysis made by Kaliski and Yin is not optimal. We give differential attacks better by up to a factor of 512. Also we show that RC5 has many weak keys with respect to differential attacks. This weakness relies on the structure of the cipher and not on the key schedule.

Meet-in-the-middle attacks, where problems and the secrets being sought are decomposed into two pieces, have many applications in cryptanalysis. A well-known such attack on double-DES requires 2⁵⁶ time and memory; a naive key search would take 2¹¹² time. However, when the attacker is limited to a practical amount of memory, the time savings are much less dramatic. For n the cardinality of the space that each half of the secret is chosen from (n=2⁵⁶ for double-DES), and w the number of words of memory available for an attack, a technique based on parallel collision search is described which requires O \( (\sqrt {n/ w} ) \) times fewer operations and O(n/w) times fewer memory accesses than previous approaches to meet-in-the-middle attacks. For the example of double-DES, an attacker with 16 Gbytes of memory could recover a pair of DES keys in a known-plaintext attack with 570 times fewer encryptions and 3.7×10⁶ times fewer memory accesses compared to previous techniques using the same amount of memory.

We present new attacks on key schedules of block ciphers. These attacks are based on the principles of related-key differential cryptanalysis: attacks that allow both keys and plaintexts to be chosen with specific differences. We show how these attacks can be exploited in actual protocols and cryptanalyze the key schedules of a variety of algorithms, including three-key triple-DES.

The block cipher DESX is defined by DESX _k.k1.k2(x) = k2 ⊕ DES_k(k1 ⊕ x), where ⊕ denotes bitwise exclusive-or. This construction was first suggested by Ron Rivest as a computationally-cheap way to protect DES against exhaustive key-search attacks. This paper proves, in a formal model, that the DESX construction is sound. We show that, when F is an idealized block cipher, FX _k.k1.k2(x) = k2 ⊕ F _k(k1 ⊕ x) is substantially more resistant to key search than is F. In fact, our analysis says that FX has an effective key length of at least k + n − 1 − lg m bits, where k is the key length of F, n is the block length, and m bounds the number of <x, FX _K (x)> pairs the adversary can obtain.

This paper consists of three parts. First, various types of Diffie-Hellman oracles for a cyclic group G and subgroups of G are defined and their equivalence is proved. In particular, the security of using a subgroup of G instead of G in the Diffie-Hellman protocol is investigated. Second, we derive several new conditions for the polynomial-time equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms in G which extend former results by den Boer and Maurer. Finally, efficient constructions of Diffie-Hellman groups with provable equivalence are described.

We introduce the notion of a black box field and present several algorithms for manipulating such fields. Black box fields arise naturally in cryptography and our algorithms have several cryptographic implications. First, our results show that any algebraically homomorphic cryptosystem can be broken in sub-exponential time. The existence of such cryptosystems was posed as an open problem in [12]. Second we show that over elliptic (or hyperelliptic) curves the hardness of computing discrete-log implies the security of the Diffie-Hellman protocol. This provable security of the Diffie-Hellman protocol over elliptic curves demonstrates an additional advantage of elliptic curve cryptosystems over conventional ones. Finally, we prove that manipulating black box fields over the rationals is as hard as factoring integers.

With the advent of the Pentium processor parallelization finally became available to Intel based computer systems. One of the design principles of the MD4-family of hash functions (MD4, MD5, SHA-1, RIPEMD-160) is to be fast on the 32-bit Intel processors. This paper shows that carefully coded implementations of these hash functions are able to exploit the Pentium’s superscalar architecture to its maximum effect: the performance with respect to execution on a non-parallel architecture increases by about 60%. This is an important result in view of the recent claims on the limited data bandwidth of these hash functions. Moreover, it is conjectured that these implementations are very close to optimal. It will also be shown that the performance penalty incurred by non-cached data and endianness conversion is limited, and in the order of 10% of running time.

There are well-known techniques for message authentication using universal hash functions. This approach seems very promising, as it provides schemes that are both efficient and provably secure under reasonable assumptions. This paper contributes to this line of research in two ways. First, it analyzes the basic construction and some variants under more realistic and practical assumptions. Second, it shows how these schemes can be efficiently implemented, and it reports on the results of empirical performance tests that demonstrate that these schemes are competitive with other commonly employed schemes whose security is less well-established.

Quantum cryptography is an emerging technology in which two parties may simultaneously generate shared, secret cryptographic key material using the transmission of quantum states of light whose security is based on the inviolability of the laws of quantum mechanics. An adversary can neither successfully tap the key transmissions, nor evade detection, owing to Heisenberg’s uncertainty principle. In this paper we describe the theory of quantum cryptography, and the most recent results from our experimental system with which we are generating key material over 14-km of underground optical fiber. These results demonstrate that optical-fiber based quantum cryptography could allow secure, real-time key generation over “open” multi-km node-to-node optical fiber communications links between secure “islands.”

We prove the unconditional security of a quantum key distribution (QKD) protocol on a noisy channel against the most general attack allowed by quantum physics. We use the fact that in a previous paper we have reduced the proof of the unconditionally security of this QKD protocol to a proof that a corresponding Quantum String Oblivious Transfer (String-QOT) protocol would be unconditionally secure against Bob if implemented on top of an unconditionally secure bit commitment scheme. We prove a lemma that extends a security proof given by Yao for a (one bit) QOT protocol to this String-QOT protocol. This result and the reduction mentioned above implies the unconditional security of our QKD protocol despite our previous proof that unconditionally secure bit commitment schemes are impossible.

The linear complexity of an N-periodic sequence with components in a field of characteristic p, where N = np ^ν and gcd(n, p) = 1, is characterized in terms of the n ^th roots of unity and their multiplicities as zeroes of the polynomial whose cofficients are the first N digits of the sequence. Hasse derivatives are then introduced to quantify these multiplicities and to define a new generalized discrete Fourier transform that can be applied to sequences of arbitrary length N with components in a field of characteristic p, regardless of whether or not gcd(N, p) = 1. This generalized discrete Fourier transform is used to give a simple proof of the validity of the well-known Games-Chan algorithm for finding the linear complexity of an N-periodic binary sequence with N = 2^ν and to generalize this algorithm to apply to N-periodic sequences with components in a finite field of characteristic p when N = p ^ν. It is also shown how to use this new transform to study the linear complexity of Hadamard (i.e., component-wise) products of sequences.

Siegenthaler inequality shows the existence of a tradeoff between the correlation-immunity order and the nonlinearity order of a Boolean functions. We generalize this result to correlation-immune functions over any finite field. We then construct a family of correlation-immune functions achieving this bound; these functions are notably well-suited for combining linear feedback shift registers. We also apply this result to the cryptanalysis of any cryptographic primitive based on boxes connected by a network. Schnorr and Vaudenay have previously recommended that these boxes should be multipermutations; we here refine this condition since we show that each binary component of these multipermutations, seen as a Boolean function, should have low degree.

In 1993, Beimel and Chor presented an unconditionally secure interactive protocol which allows a subset of users in a network to establish a common key. This scheme made use of a key predistribution scheme due to Blom.

We also discuss lower bounds on the storage and communcation requirements of protocols of these types. Some of our schemes are optimal (or close to optimal) with respect to these bounds.

Naor and Shamir ([1]) defined the basic problem of visual cryptography by a visual variant of the k out of n secret sharing problem: how can an original picture be encoded by n transparencies so that less than k of them give no information about the original, but by stacking k of them the original can be seen? They described a solution to this problem by a structure called k out of n secret sharing scheme whose parameters directly correspond to quality and usability of the solution. In this paper a new principle of construction for such schemes is presented which is easy to apply and in most cases gives much better results than the former principles. New bounds on relevant parameters of k out of n schemes are developed, too. Furthermore, an extension of the basic problem is introduced and solved in which every combination of the transparencies can contain independent information.