Birthday Attack

---

A birthday attack is a type of cryptographic attack that exploits weaknesses in the mathematical algorithms used to encrypt passwords, in order to take advantage of the probability of different password inputs producing the same encrypted output.

• in cyptanalysis, is a variant of brute force technique used mainly against hash functions and signature algorithms
  • exploiting collisions in hash functions through brute force

Birthday Paradox

• named after the birthday paradox
  • shows that the computational time required to brute force a collision might be less than expected
  • asks how large must a group of people be so that the chance of two of them sharing a birthday is 50%
    • answer is people
  • the chances of someone sharing a particular birthday are small
  • but the chances of any two people in a group sharing any birth date in a calendar year increases as you add more people:
• to exploit the paradox
  • attacker creates multiple malicious and benign documents
    • both featuring minor changes
  • if the attacker can generate sufficient variations, then the chance of matching hash outputs can be better than 50%
    • Depending on the length of the hash and the limits to the non-suspicious changes
  • effectively means that
    • a hash function that outputs 128-bit hashes can be attacked by a mechanism that can generate  variations
    • Computing  variations takes much less time than computing  variations

Example

• Given a 128-bit signature algorithm
• when the attacker knows signature for a message ,
  • they can find, with 50% probability, another message , among messages, distinct from , such that and have the same signature
• attacker can then send a signed message, which will be evaluated by the recipient, while the message has never been signed by a legitimate sure