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