Подберите пароль по его md5-хэшу перебором над известным алфавитом
Реализуйте RecoverPassword(h), возвращающую пароль, чей md5-хэш равен h. Пароль использует только символы известного alphabet; длины растут от 1 и далее. Перебирайте кандидатов от коротких к длинным и сравнивайте хэш каждого с h.
var alphabet = []rune{'a', 'b', 'c', 'd', '1', '2', '3'}
func hashPassword(in string) []byte { h := md5.Sum([]byte(in)); return h[:] }
func RecoverPassword(h []byte) string {
// ваш код здесь
return ""
}Допишите реализацию.
Перебирайте строки-кандидаты по порядку — трактуйте счётчик шага как число в системе с основанием len(alphabet), декодируя каждый шаг в соответствующую строку над алфавитом. Для каждого кандидата считайте hashPassword(guess) и сравнивайте с h через bytes.Equal; возвращайте на первом совпадении. Поиск — O(a^n) для пароля длины n над алфавитом из a символов — экспоненциальный, поэтому работает только для коротких паролей.
- ✗Думать, что
md5обратим или отменяется повторным хэшированием - ✗Сравнивать хэши через
==на слайсах вместоbytes.Equal - ✗Недооценивать рост O(a^n) для длинных паролей
- →Как заранее вычисленная rainbow-таблица изменит временную стоимость этой атаки?
- →Как соль и медленный хэш вроде bcrypt делают этот перебор непрактичным?
Решение
md5 необратим, поэтому единственный путь — перебор. Счётчик step кодирует кандидата как число в системе счисления с основанием len(alphabet).
func RecoverPassword(h []byte) string {
for step := 0; ; step++ {
guess := genPassword(step)
if bytes.Equal(hashPassword(guess), h) {
return guess
}
}
}
func genPassword(step int) (res string) {
for {
res = string(alphabet[step%len(alphabet)]) + res
step = step/len(alphabet) - 1
if step < 0 {
break
}
}
return
}genPassword — биекция: каждый step даёт ровно одну строку над алфавитом, перебирая сначала все длины 1, затем все длины 2 и так далее. Сравнение хэшей — через bytes.Equal (срезы нельзя сравнивать ==).
⚠️ Сложность O(a^n): для длинного пароля перебор нереален. Защита у разработчика — соль и медленный хэш (bcrypt/scrypt/argon2), а не md5.
