Editing Birthday attack (section)

==Understanding the problem==
[[File:birthday_attack_vs_paradox.svg|thumb|Comparison of the birthday problem (1) and birthday attack (2):{{parabr}}
In (1), collisions are found within one set, in this case, 3 out of 276 pairings of the 24 lunar astronauts.{{parabr}}
In (2), collisions are found between two sets, in this case, 1 out of 256 pairings of only the first bytes of SHA-256 hashes of 16 variants each of benign and malicious contracts.]]

{{Main article|Birthday problem}}
As an example, consider the scenario in which a teacher with a class of 30 students (n = 30) asks for everybody's birthday (for simplicity, ignore [[leap year]]s) to determine whether any two students have the same birthday (corresponding to a hash collision as described  further). Intuitively, this chance may seem small. Counter-intuitively, the probability that at least one student has the same birthday as ''any'' other student on any day is around 70% (for n = 30), from the formula <math>1-\frac{365!}{(365-n)!\cdot 365^n}</math>.<ref>{{cite web|title=Birthday Problem|url=https://brilliant.org/wiki/birthday-paradox/|website=Brilliant.org|publisher=[[Brilliant_(website)]]|access-date=28 July 2023}}</ref>

If the teacher had picked a ''specific'' day (say, 16 September), then the chance that at least one student was born on that specific day is <math>1 - (364/365)^{30}</math>, about 7.9%.

In a birthday attack, the attacker prepares many different variants of benign and malicious contracts, each having a [[digital signature]]. A pair of benign and malicious contracts with the same signature is sought. In this fictional example, suppose that the digital signature of a string is the first byte of its [[SHA-256]] hash. The pair found is indicated in green &ndash; note that finding a pair of benign contracts (blue) or a pair of malicious contracts (red) is useless. After the victim accepts the benign contract, the attacker substitutes it with the malicious one and claims the victim signed it, as proven by the digital signature.

=== Relation to the balls into bins problem ===
The birthday attack can be modelled as a variation of the [[balls into bins problem]], where balls (hash function inputs) are randomly placed into bins (hash function outputs). A hash collision occurs when at least two balls are placed into the same bin.