Re: one way permutation?
From: Volker Hetzer (volker.hetzer_at_ieee.org)
Date: Wed, 16 Jul 2003 15:53:41 +0200
> Your conditions can be met by something short of public-key
> techniques in any case: take A ^ (username-password) mod P; since
> discrete logarithm is hard, this is one-way, but it is bijective
> given suitable A for P. It's still modular encryption, but it's only
> one step.
I think I'm going to check how much performance this actually costs me.
> But if you can lengthen the data, here is how you can securely check
> the ownership of rows.
> Your row in the password table can be
> H(H(username || password || salt))
> E( username||password, H(username || password || salt) )
Took me a while to figure this out but the way I see this,
encrypting username||password with H(username || password || salt)
as key encrypts each row with a different key. Which, in turn kills
its usefulness as a permutation because obviously, different (or even
identical) data encrypted with different keys may yield the same ciphertext.
What is the double hash for? Just as an additional means of comparing?
Wouldn't the likelyhood of a collision with this scheme be in the same
order as a row consisting of
data, salt1, h(uname||pwd||salt1), salt2, h(uname||pwd||salt2)?
> Incidentally, it isn't needed to have users all check the entire
> table to find their row. Use H( username || password ) to determine
> the first row to look for your own row, and the increment to look for
> the next row to try, and most users will find their row on the first
> or second try.
I don't understand that one. What do you mean by a "first" row in
a table? Normally a db table does not have such a thing.
> But salt alone doesn't protect against dictionary attacks on poor
> passwords. For that, you DO need public-key techniques, such as
> Encrypted Key Exchange. Look on my page about "Passwords and
> Protocols" for examples of what is needed.
Hm... One rsa keypair per row? Naa, we will not do that. Also, one
important aspect is to sell this to another department. The whole permutation
idea stems from the fact that it's hard to go there and say that it will be
mostly okay but in theory there could be mixups due to hash collisions.
OTOH, telling them to choose hard to guess passwords places responsibility
on them and that they will accept much easier.
Ok, here's what I've come up with now:
The idea is to have employees responsible for buying and selling items of
Each kind has a person officially resposible for this. This is public information.
Then that guy makes changes in the inventory, pricing and such. What we want
is one way traceability so that the guy can separate his transactions from others
which may or may not be allowed. What we do not want (for legal reasons among
others) is to go and simply check how lazy each guy is.
So we could use two tables:
T1: kind -> owner (who is responsible for it)
T2: change_transaction, salt, h(owner||passwd||salt),A^(owner||passwd||salt)mod p
Now, the receiver really cares only about change_transaction. Only when he thinks
something is wrong he phones the owner. the owner can do a fast list which checks
only the hashes. Only when he can't remember a transaction that shows up it is necessary
to do the computations for the third row.
Also, we might have to include a hmac of the change_transaction too to prevent
the excuse that the dba hacked the row.
Lots of Greetings!
-- While it is a known fact that programmers never make mistakes, it is still a good idea to humor the users by checking for errors at critical points in your program. -Robert D. Schneider, "Optimizing INFORMIX Applications"