Не стоит использовать слишком длинные пароли, т.к. коллизии?

Хеш-функции обычно лучше, чем mod 10. Так что можешь использовать длинные пароли, их сложнее подобрать.

Например, F(x) = x mod 10. Т.е. использование числового пароля >10 нецелесообразно.

то вероятность коллизии будет >50% после ~ sqr(10) = 3 паролей. Если выход хеша 256 бит, то вероятность коллизии будет >50%, после 2^128 разных паролей вне зависимости от их длины.

Это понятно. Но все же это нужно учитывать, ибо можно перестараться.

Нет, не нужно.

Получается, 2^256 = 100%. Ну да, логично.

Но выход этой хэш-функции = 4 бита(1001(2) = 9(10)). Т.е. 2^2 разных пароля дает вероятность коллизии >50 процентов, т.е. 4 пароля, а не 3. Что я не так сделал?

Нет, вероятность коллизии это почти постоянная для хорошей хеш функции. А при меньшей длине пароля у тебя только повышается вероятность коллизий ещё на входных данных и упрощается перебор, так как не требуется вычислять значения для всего.

И лучше использовать какие-нибудь специальные алгоритмы для генерации паролей. Вроде Scrypt. Так как у них изначально цель на меньшем множестве входных данных получить большее множество вероятных значений, и именно за счет сложности перебора в виду затратности вычислений.

Почему не нужно?

Кэш-функиция, которую я привел выше, дает коллизии после 10. т.е. вывод-то одинакового кэша будет независимо от того, password == 1 or 11; 2 or 12...

Например, пароль 1 дает кэш 1, 11 - тоже 1. То есть нет различия между паролем 100002 и 12, т.к. кэш всегда будет 2.

Например, пароль 1 дает кэш 1, 11 - тоже 1. То есть нет различия между паролем 100002 и 12, т.к. кэш всегда будет 2.

А теперь переведи это на человеческие цифры. При длине хэша в 256 бит и длине входных данных в 256 бит имеем пароль примерно 32 символа, где символы — латиница в верхнем и нижнем регистрах, цифры и спецсимволы (если довериться тому, как считает битность keepassx). Вот в случае с mod в качестве хэш-функции можешь считать, что использование более длинных паролей нецелесообразно. Но использовать более короткие пароли ты не можешь, потому что уже не сможешь считать хэш 256 битным. Так как результат mod предсказуем.

Если честно, я не особо понял о чем ты. «Длина хэша 256 бит» - что это значит? Ведь максимальная в моей хэш-функции длина - 4 бита(т.к. число 9 в двоичной системе весит 4 бита). Или остальные 252 бита - нули? Но зачем они?

Ты же в реальности не планируешь использовать четыре бита?

Да дело не в этом. Я хочу понять, существует ли коллизия после перебора определенного количества символов(в моем случае 10)? А эта хэш-функция - лишь пример, чтобы было понятно.

Конечно существует. Но в случае хэш функций вовсе необязательно что это будет сразу для входных при превышении длины хэш-значения. Но тут зависит от конкретного алгоритма. Смысл хэш-функций именно в практической недостижимости коллизий. А есть они уже по определению.

Ясно, спасибо. Что-то начал понимать. Да, довольно сложно в этой теме(криптография) без знания теор.вер.

Есть еще неустойчивые к коллизиям алгоритмы?