Birthday Attack on Cryptography Applications

Abstract

In many network communications it is crucial to be able to authenticate both the contents and the origin of a message.
This paper will study in detail the problem known in probability theory as the Birthday Paradox (or the Birthday problem), as well as
its implications and different related aspects we consider relevant. The Birthday attack makes use of what’s known as the
Birthday paradox to try to attack cryptographic hash functions. Among other desirable properties of hash functions, an interesting
one is that it should be collision-resistant, that is it should be difficult to find two messages with the same hash value. To find a
collision the birthday attack is used, which shows that attacker may not need to examine too many messages before he finds a
collision. The purpose of this paper is thus to give the reader a general overview of the general aspects and applications of the
Birthday Paradox.