In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on mathematical problems, and whose security thus follows from rigorous mathematical proofs, complexity theory and formal reduction. These functions are called Provably Secure Cryptographic Hash Functions. To construct these is very difficult, and few examples have been introduced. Their practical use is limited. In the second category are functions which are not based on mathematical problems, but on an ad-hoc constructions, in which the bits of the message are mixed to produce the hash. These are then believed to be hard to break, but no formal proof is given. Almost all hash functions in widespread use reside in this category. Some of these functions are already broken, and are no longer in use. See Hash function security summary. Types of security of hash functions Generally, the basic security of cryptographic hash functions can be seen from different angles: pre-image resistance, second pre-image resistance, collision resistance, and pseudo-randomness. Pre-image resistance: given a hash it should be hard to find any message such that . This concept is related to that of the one-way function. Functions that lack this property are vulnerable to pre-image attacks. Second pre-image resistance: given an input , it should be hard to find another input, (not equal to ) such that . This property is sometimes referred to as weak collision resistance. Functions that lack this property are vulnerable to second pre-image attacks. Collision resistance: it should be hard to find two different messages and such that . Such a pair is called a (cryptographic) hash collision. This property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as what is required for pre-image resistance, otherwise collisions may be found by a birthday attack. Pseudo-randomness: it should be hard to distinguish the pseudo-random number generator based on the hash function from a random number generator, e.g., it passes usual randomness tests. The meaning of "hard" The basic question is the meaning of "hard". There are two approaches to answer this question. First is the intuitive/practical approach: "hard means that it is almost certainly beyond the reach of any adversary who must be prevented from breaking the system for as long as the security of the system is deemed important." The second approach is theoretical and