08 May, 2009

QND-zero: A zero-knowledge password proof scheme

This is my zero-knowledge password proof, QND-zero. QND is short for quick 'n' dirty: it works, and not much else.

Pick a random 32-bit seed. Set h (32-bit) to the seed. For each character in the password, from the first character to the last character, set c (clamped at 32-bit) to the character. Three times, you should square c, then add the seed to it plus one, then xor c with the seed. After that, add c to h, then rotate h left one spot, then xor h with the seed. After all that, h should contain your hash.

For languages which don't support rotate, but support left + right shift, try this for rotate left:

a = (a>>31) ^ (a<<1);>char is clamped to 32-bit and so is seed, and so is hash
pick a random seed
set hash to seed
for each char in the password (from the first to the last) {
do three times {
multiply the char by itself
add the seed plus one to the char
xor the char with the seed
}
add the char to the hash
rotate the hash left by one
xor the hash with the seed
}


Nice and simple, quick and dirty, zero-knowledge password proof scheme. Enjoy.

A quick test to see if you've done it right:
Seed = 0xDEADBEEF
"ab" -> 0x0D62D890
"ba" -> 0x91E6462F

This post and the algorithm are put into the public domain. I, Ben Russell, would like you to respect that.

EDIT: Whoops, my reference implementation was wrong. I've fixed the values.

EDIT 2: Apparently the pseudocode missed something vital. Fixed.

No comments:

Post a Comment