Фишка в том, что ограничена длина хэша. Предположим, мы используем keccak - ну или абсолютно любой другой алгоритм с длиной хэша n бит. В этом случае максимально возможное количество значений хэша будет 2n. Возьмем 2n+1 сообщений и вычислим хэши для каждого из них. Очевидно, что поскольку количество сообщений больше, чем количество возможных значений хэша, то хотя бы у двух сообщений хэши окажутся одинаковыми - вот вам и коллизия.
Ммм, ясно. Но ведь мало найти коллизию, надо ещё определить какого она рода и насколько опасна?
А если сообщения с одинаковым хэшем вообще никак аналитически не стыкуются, то это будет значить, что коллизия безопасна, так? По идее, именно такое тогда должно быть доказательство соответствия "чёрному ящику". Который может зажевать любое число бит, но выплюнет только n.