Hash collision

If m is a hash"collision with any of the messages in m, the forgery is provable with probability 1. (Note that the value skjtemp actually used in... 

Most full-structure search systems use a hashing scheme to quickly locate potential matches and then perform a full lexical comparison of the name. A hashing function is used that takes the canonical name as input and returns a disk location to store and retrieve the name from. The number of hash collisions (where two different structures have the same hash value) is dependent on the hash function used and percentage utilization of the hash space. This database access method means that search speeds are relatively independent of database size, except where excessive hash collisions occur or numerous matches occur. 

Figure 2-65. This fingerprint was received by hashing, whereas only one part of all the substructures is specified in the illustration. The asterisk indicates the address of a collision in the bit string, generated by the algorithm.

The ciphered code is indicated with a defined length, i.e., a fixed hit/byte length. A hash code of 32 bits could have 2 (or 4 294 976 296) possible values, whereas one of 64 bits could have 2 values, However, due to tbe fixed length, several diverse data entries could assign the same hash code ( address collision ), The probability of collision rises if the number of input data is increased in relation to the range of values (bit length). In fact, the limits of hash coding are reached with about 10 000 compounds with 32 bits and over 100 million with 64 bits, to avoid collisions in databases [97. ... 

Because hashing is a one-way function and the output of the function has a low probability of collisions, hashing can be used with the cryptographic product or services family for authentication, nonrepudiation, and data integrity. An example of these is the Digital Notary.3 Hashing is also a key element in the DSA. 

Any such algorithms must inevitably cause more different input keys to produce identical address. This effect which is immanent to all hash algorithms is known as the address collision and programers must provide a way to calculate the consecutive addresses (an address increment) until an adequate address is reached. 

Figure 4.6 shows how hash algorithm works in the case of collisions. If hashing of a given key produces the address where the information about another key is stored a new address must be calculated and the content checked again. The procedure is repeated until an empty (for update of new items) record is reached or the record containing the information of the identical key is reached. In order to check the identities of keys the complete reference key must be stored in each record. 

Fig. 4.6 Hash algorithm produces another address whenever the collision of two different keys occurs on the same address.

Because of the nature of InChIKey (and every hash in general), collisions are possible. This fact comes directly from the limited number of possibilities a 25-char-acters-long string can contain. Even though collisions of InChIKeys are inevitable in the future, it is not possible to say when the first collision will occur. The official InChl documentation (documentation published with the InChl source code, version 1.02-Beta http //www.iupac.org/inchi/download/index.html) states that the probability of a collision in a set of 1 billion InChIKeys is 2.0 x 10 20%. However because the second part of the InChIKey is based on InChl layers that do not exist (are empty) for many structures (such as isotopic layer, stereochemistry layer, etc.), a more realistic estimate must be based on collisions in the first part of the InChIKey alone. In this case the same source states that the probability of a collision in a set of 1 billion structures increases to 2.7 x 10-9 %. However, even this means that unless we are extremely unlucky, InChIKey should remain unique for quite a long time. It... 

The hash origin of InChIKey also means that it is not convertible back to the original InChl or molecular structure, because for each InChIKey there is an unlimited number of possible matching input values. Although this might seem to be a drawback of the format, it is simply the price of the fixed length of the identifier. When a readable identifier with no possible collisions is needed, InChl (or canonical SMILES) should be used. 

Figure 1.8 Generation of hashed fingerprints. Each fragment leads to switching on of several bits. A bit with collisions is underlined and shown in bold.

One might say cryptologically strong instead, if one adheres to the convention from Footnote 3. However, this term is established, and the convention is not always respected anyway. Actually, they are simply called claw-free permutation pairs in [G0MR88]. The two name changes make the notation consistent with related collision-intractable or collision-free families of hash functions (see Section 8.5). The reasons are that the objects called claws do exist, it is only infeasible to find them, and that similar families without trap-doors are needed later. 

Moreover, [DaPP94] contains a construction from an arbitrary so-called collision-intractable family of hash functions, which is fairly efficient at least if one trusts a fast, but not cryptographically strong hash function, and may therefore be a reasonable alternative if number-theoretic assumptions should be disproved. 

One basic idea for these constructions is tree authentication. If one starts with the type sketched in Section 2.4, the same addition is needed as with message hashing The hash functions used must be collision-intractable, and their collisions count as proofs of forgery. 

This property, which will guarantee availability of service in the chosen model, is only defined here, but not always required, because that would exclude the general abstract construction with message hashing, unless the notion of hash functions were modified significantly. However, the constructions with concrete collision-intractable families of hash functions can be modified to have this property (see Section 10.1). 

The property that makes all the functions with bundling properties, and also some other functions such as hash functions, interesting for cryptology is that it is infeasible to find collisions, i.e., two values with the same image see Figure 8.4 (and Figure 6.9). For precision, this notion and two related ones are given formal definitions. 

This implies that collision-intractable hash functions as used in practice (e.g., [SHS92]) are formally undefinable. 

As with most other classes of function families, there is not only one definition of collision-intractable families of hash functions. 

Note that a weaker notion of families of hash functions exists, too, so-called families of universal one-way hash functions [NaYu89]. However, in the applications to fail-stop signature schemes, collision-intractability is needed. 

Definition 8.35. A collision-intractable family of hash functions has the... 

Now tuple exponentiation is turned into collision-intractable families of fixed-size hash functions. This was first done in [ChHP92] the construction was extended for the use in incremental signature schemes in [BeGG94]. In particular, one can use pair exponentiation, but larger tuples tiun out to be more efficient. 

Construction 8.52. (Part of the proof of Theorem 3.1 in [Damg90a].) Let a collision-intractable family of fixed-size hash functions be given with len(k) < - 1 for all fc > kig . The corresponding family of hash functions is defined by the following components, which are written with an asterisk to distinguish them from the components of the underlying family of fixed-size hash functions ... 

Theorem 8.53. (Adapted from [Damg90a, Theorem 3.1]). Construction 8.52 is a collision-intractable family of hash functions. ... 

Remark 8.54. This family of hash functions can be augmented by short collision proofs according to Remark 8.37 The reduction used in the proof of the theorem yields a (rather obvious) algorithm to construct a collision of the underlying family of fixed-size hash functions, from any collision of the new family (for all acceptable keys, although it is only needed for correctly generated keys in the proof of collision-intractability). ... 

The following table summarizes the most important parameters of the constructions of collision-intractable families of bundling homomorphisms, hiding homomor-phisms, and fixed-size hash functions based on the discrete-logarithm assumption. Note that the main use of fixed-size hash functions is in the constmction of real hash functions. 

Collision-intractable families of hash functions have to be used. 

A collision of the hash function cormts as a valid proof of forgery. 

A signer s entity must store each message m it has signed, so that it can indeed show a collision if a computationally unrestricted attacker finds another message m with the same hash value and uses the signature on m for m (Note that there was no need to store the message in the constructions in Chapter 9.)... 

The key for the family of hash functions, i.e., the description of the particular function used, must be chosen by the risk bearer s entity (because collision-intractability is only guaranteed against parties who did not generate this key). Hence in schemes with prekey, this key is a part of the prekey. 

---