In any scheme for protecting the confidentiality of data, selecting a key and encrypting the data is the easy part. The difficult part is controlling access to decryption keys. This becomes particularly significant with object-based protection, that is protection of an object, such as a file or a message, regardless of where the object is currently being stored or transferred within a distributed environment. An example of object-based protection is traditional electronic mail encryption, where access control amounts to selecting a list of individuals permitted to decrypt a message and attaching copies of the symmetric encryption key, encrypted using their public keys, to the encrypted message content. We present a different means of controlling access to decryption keys which can support more flexible access control rules and can better reflect security policy. It is particularly suitable for use in such data distribution environments as public file servers, bulletin boards, commercial information dissemination services, and groupware applications. Because all participants need to trust central servers, the method is less suitable for loosely-connected groups than for medium to large commercial or government organizations.

Current techniques for collision search with feasible memory requirements involve pseudo-random walks through some space where one must wait for the result of the current step before the next step can begin. These techniques are serial in nature, and direct parallelization is inefficient. We present a simple new method of parallelizing collision searches that greatly extends the reach of practical attacks. The new method is illustrated with applications to hash functions and discrete logarithms in cyclic groups. In the case of hash functions, we begin with two messages; the first is a message that we want our target to digitally sign, and the second is a message that the target is willing to sign. Using collision search adapted for hashing collisions, one can find slightly altered versions of these messages such that the two new messages give the same hash result. As a particular example, a $10 million custom machine for applying parallel collision search to the MD5 hash function could complete an attack with an expected run time of 24 days. This machine would be specific to MD5, but could be used for any pair of messages. For discrete logarithms in cyclic groups, ideas from Pollard’s rho and lambda methods for index computation are combined to allow efficient parallel implementation using the new method. As a concrete example, we consider an elliptic curve cryptosystem over GF(2 155) with the order of the curve having largest prime factor of approximate size 10 36. A $10 million machine custom built for this finite field could compute a discrete logarithm with an expected run time of 36 days. 1.

A cryptanalytic attack on the use of short RSA secret exponents is described. The attack makes use of an algorithm based on continued fractions that finds the numerator and denominator of a fraction in polynomial time when a close enough estimate of the fraction is known. The public exponent e and the modulus pq can be used to create an estimate of a fraction that involves the secret exponent d. The algorithm based on continued fractions uses this estimate to discover sufficiently short secret exponents. For a typical case where e>pq, GCD(p-1, q-1) is small, and p and q have approximately the same number of bits, this attack will discover secret exponents with up to approximately one-quarter as may bits as the modulus. Ways to combat this attack, ways to improve it, and two open problems are described. This attack poses no threat to the normal case of RSA where the secret exponent is approximately the same size as the modulus. This is because the attack uses information provided by the public exponent and, in the normal case, the public exponent can be chosen almost independently of the modulus.>