Подгон криптогарфических хешей

[caxap]

Есть такой хеш -- CRC32. Длина его 32 бита. Известно, что можно получить любое значение данного хеша, если добавить/изменить в сообщении не более 32 битов (предположим для определённости, что биты дописываются в конец сообщения). Причем независимо от исходного значения хеша.

Есть ещё криптограф. хеш -- MD5. Длина его 128 бит. Можно ли с ним проделать такое и если можно, то какое минимальное (максимальное) количество бит нужно изменить в сообщении для получения заданного значения хеша?

[venco]

Почти наверняка можно, изменив/добавив порядка 128 бит. Но никто не знает, как это быстро посчитать.
Если же можно менять оба сообщения, то довольно легко считаются суффиксы порядка 512 бит, такие, что с этими суффиксами сообщения дадут какой-нибудь одинаковый MD5 хеш.

[caxap]

venco в сообщении #315613 писал(а):

порядка 128 бит

А точнее можно? Можно ли утверждать, что не более 128?

[venco]

caxap в сообщении #315912 писал(а):

venco в сообщении #315613 писал(а):

порядка 128 бит

А точнее можно? Можно ли утверждать, что не более 128?

Нельзя.

[caxap]

venco в сообщении #315916 писал(а):

Нельзя.

А чем принципиально отличается CRC32, что в нём с уверенностью можно сказать, что изменять потребуется не более 32 бит. Я думаю, дело в том, что в CRC32 при каждом изменении бита хеш будет менятся, причем не будет "повторений", т. е. изменили мы 100 раз бит, и все 100 раз будут получаться отличные хеши, такоим образом поскольку общее число хешей конечно ($2^{32}$), то в худшем случае при изменении всех 32 бит у нас появится нужная сумма. А в md5 наверное будут "повторения", так?