Re: one way permutation?

jsavard_at_ecn.ab.ca
Date: 07/15/03 

Date: Tue, 15 Jul 2003 13:15:35 GMT

Volker Hetzer (volker.hetzer@ieee.org) wrote:

: It could map them into strings of a greater length.
: Probably not smaller as then they wouldn't be unique any more.

Indeed not. This might allow something useful to you.

: > No long-term storage of a secret with which the inverse can be
: > computed is allowed.

: Exactly. If I understand you correctly this is the point that
: rules out symmetric encryption.

Yes, you do understand me correctly.

: The idea is to hide the ownership of a row in a database table.
: So, I don't go into the table with a name in the clear and check
: whether some other row matches but I go into the table
: with a name, get the salt from the row, do the computation
: and theck whether the row is mine. So, unlike password
: hashes I go through the whole table looking for any match.

This helps me see what can be done.

In this case, you can use symmetric encryption, in a way that I will
outline.

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.

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

This isn't absolutely guaranteed against collisions, but they're extremely
unlikely. The username and password are encrypted, based on the
singly-hashed username, password, and salt, which can't be determined from
the doubly-hashed version; the encryption function doesn't have
collisions, so a collision is only possible if you have a collision in the
hash function, and the two colliding values happen to encrypt their
corresponding usernames and passwords to the same result.

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. This,
however, can be risky if bad passwords are chosen. You could have a second
salt for each user, stored in a table indexed by H( username || password )
with collisions allowed, to help with that.

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.

http://home.ecn.ab.ca/~jsavard/crypto/mi060703.htm

and the following page discuss this.

John Savard

Relevant Pages

  • Re: Why does SRP (Secure Remote Password) use the username to encrypt the password?
    ... SHA is not an encryption algorithm, ... The reason this is done is because in many systems simply copying the private value from one username to another grants access to the second username, by including the username in the hash this process no longer works. ... hashing the plaintext password with a salt would be enough. ... Go with option A. B would eliminate some of the security, ...
    (sci.crypt)
  • Re: How to encrypt/decrypt a file
    ... Modified to use random IV value (and random salt). ... (and for CTR mode of operation counter IV gives much better IND-CPA security). ... get a cryptographically random salt (different for each encryption invocation) ... and the server is watching that this exact data is not stored on the server... ...
    (microsoft.public.dotnet.security)
  • Re: How to encrypt/decrypt a file
    ... However random IV (in addition to password's salt) is better and more secure solution anyway. ... (and for CTR mode of operation counter IV gives much better IND-CPA security). ... get a cryptographically random salt (different for each encryption invocation) ... even so your customer's requirement looks quite strange - the server is processing the data and the server is watching that this exact data is not stored on the server... ...
    (microsoft.public.dotnet.security)
  • Re: How to encrypt/decrypt a file
    ... Mitch's sample doesn't use have salt that I was talking about, but a password salt is not redundand... ... get a cryptographically random salt (different for each encryption invocation) ... The question is, from a security perspective, should the IV also be derived from a RNGCryptoServiceProvider ... even so your customer's requirement looks quite strange - the server is processing the data and the server is watching that this exact data is not stored on the server... ...
    (microsoft.public.dotnet.security)
  • Re: WSE 3.0 + UserNameToken without X.509 Cert/Kerberos + Signing + Encryption How?
    ... signed messages using UserName stuff. ... do response encryption, but I added that and it's working to great effect. ... I'm at a loss on how to add an "authorization assertion" to ... between client and server using a UserNameToken that passes the UserName ...
    (microsoft.public.dotnet.framework.webservices.enhancements)
Loading