Brute-force a password from its md5 hash over a known alphabet
Implement RecoverPassword(h) returning the password whose md5 hash equals h. The password uses only characters from a known alphabet; lengths grow from 1 upward. Enumerate candidates shortest-first and compare each hash to 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 {
// your code here
return ""
}Write the implementation.
Enumerate candidate strings in order — treat the step counter as a number in base len(alphabet), decoding each step into the corresponding string over the alphabet. For each candidate compute hashPassword(guess) and compare it to h with bytes.Equal; return on the first match. The search is O(a^n) for an n-length password over an a-symbol alphabet — exponential, so it only works for short passwords.
- ✗Thinking
md5can be reversed or undone by hashing again - ✗Comparing hashes with
==on slices instead ofbytes.Equal - ✗Underestimating the O(a^n) blow-up for longer passwords
- →How would a precomputed rainbow table change the time cost of this attack?
- →How do a salt and a slow hash like bcrypt make this brute force impractical?
Solution
md5 is irreversible, so the only path is brute force. The step counter encodes a candidate as a number in base 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 is a bijection: each step yields exactly one string over the alphabet, enumerating all length-1 strings first, then all length-2, and so on. Hash comparison uses bytes.Equal (slices cannot be compared with ==).
⚠️ Complexity is O(a^n): brute force is infeasible for a long password. The developer's defense is a salt and a slow hash (bcrypt/scrypt/argon2), not md5.
