Cryptography and Network Security Principles and Practice, 8th Edition - Pearson

APPENDIX E

Mathematical Basis of The Birthday Attack

E.1 Related Problem

E.2 The Birthday Paradox

E.3 Useful Inequality

E.4 The General Case of Duplications

E.5 Overlap Between Two Sets

 

In this appendix, we derive the mathematical justification for the birthday attack. We begin with a related problem and then look at the problem from which the name “birthday attack” is derived.

E.1 RELATED PROBLEM

A general problem relating to hash functions is the following. Given a hash function H, with n possible outputs and a specific value H(x), if H is applied to k random inputs, what must be the value of k so that the probability that at least one input y satisfies H(y) = H(x) is 0.5?

For a single value of y, the probability that H(y) = H(x) is just ...