Re: one way permutation?

From: Volker Hetzer (volker.hetzer_at_ieee.org)
Date: 07/16/03 

Date: Wed, 16 Jul 2003 15:53:41 +0200

jsavard@ecn.ab.ca wrote:
> 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
>
> salt
> 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
different kinds.
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!
Volker 

--
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"

Relevant Pages

  • Re: Validating if password is encoded or encrypted
    ... encryption algorithm or hash function. ... specify the character set used on the system where the passwords were ... Usually the passwords will be base64 encoded before being stored in the db ... Prove to peers and potential employers without a doubt that you can actually do a proper penetration test. ...
    (Pen-Test)
  • Re: Obama administration funds motorcycle-only checkpoints
    ... Public-Key Infrastructure ... eMail encryption might be used by terrorists and organized crime. ... We have sub-constitutional law to protect privacy ...
    (rec.motorcycles)
  • Re: EFS and DRA. Admin unable to decrypt
    ... >So the certificate is used to identify the user & the ... EFS encryption key, the system will generate one for him. ... file using *his* private key, because his public key was incorporated ... into the public-key encryption of the FEK. ...
    (microsoft.public.windowsxp.security_admin)
  • Obfuscating sensitive data? (was: response to tax software not encrypting tax info)
    ... Encryption without a key is useless. ... If you can retrieve the file, brute force is always possible, so nothing ... attacker laugh, assuming he is just a bit smarter than a piece of wood. ... Never just obfuscate the passwords by using a generic key. ...
    (Bugtraq)
  • Re: In child porn case, a digital dilemma
    ... passwords. ... By now PGP has ... poop" having only been invented in 1991 and updated since. ... The fastest way to break encryption is to ...
    (alt.true-crime)