Is there any chance of failure in Cryptography

Question

With my limited knowledge of cryptography and its correct terms, functions (md5, base64, sha, aes or whatever) turn an input into encrypted output. For example, if the following input turns into following output:

input | output
______________
A     |  XX
B     |  YY
AB    |  ZZ

my question is: do such cryptography functions involve proven mechanism to avoid the failure of "repeated-output"? I mean, is there any chance, if inputing AB provides ZZ output, can there be any other input (like %) that might have the same output ZZ ?

What is the mechanism to ensure there doesn't exist two different input that provide the same output?

Answer 1

What you are talking about is called collision resistance.

Base 64 is an encoding technique. It doesn't use a key and therefore it is not a cipher. Encoding techniques commonly have a 1:1 relation with the output of course, so no collisions there.

Pseudo-random permutations such as block ciphers have a 100% collision resistance as a permutation always has a 1:1 relationship between the input and the output. So AES and (3)DES will never repeat output for different input. Beware that this changes if a block cipher mode of operation is used to turn it into a real semantically secure (probabilistic) cipher; in that case you'd would expect collisions that depend on the output size, see the final part of this answer.

MD5 is a message digest or cryptographically secure hash function. Hash functions are supposed to have a certain collision resistance. Collisions are of course certain as there are more messages than output values (see the pigeon hole principle). However, it should be computationally infeasible to find them. MD5 is considered broken and fails on this principle, which is why it is not actually considered "cryptographically secure" anymore.

As for the "whatever": cryptography consists of many algorithms, and the outcome depends on the algorithm. If the output is supposed to be indistinguishable from random and there are $n$ different outputs then you'd expect a $1 \over n$ chance of that a value is equal to a preset earlier output value. However, due to the birthday bound you'd expect to compare only $\sqrt n$ values against each other before you find a collision with a 50% chance of success.

In the case of MD5 with an output size of 128 bits, so $n = 2^{128}$- you'd expect a collision in about $\sqrt {2^{128}} = 2^{64}$ compares. That means a collisions resistance of 64 bits in other words. However, because it is broken attackers can create collisions much more easily. Generally cryptographers aim to have a security margin of 128 bits, which means that MD5 is considered insecure with regards to collision resistance even if it was not broken.