Prev: CFP DATA MINING 2010: new date - until 29 March 2010
Next: A link to a news on SSL
From: bmearns on 24 Mar 2010 14:04
I'm performing a salted hash for generating multiple passphrases from
a single password. The salt is assumed to be known to an adversary,
and I'm interested in knowing what sort of dependency the hash output
has on the salt versus the password. For instance, if the salt and
password are of equal length, is it fair to say that the hash output
is equally dependent on both of them? Does it matter what the entropy
density of each is, or how those lengths compare to the length of the
digest? Does any kind of vague concept of dependency even make sense
in this context?

My motivation for the question is as follows: multiple users will
likely have the same salt (the salt is something relevant to the
specific service, like "gmail" for an email password, so everybody
using the technique for that service will likely have the same salt).
I don't want this to make it unnecessarily easy for an attacker to
break into the service because the digest was too dependent on the
known salt.

The opposite side of the same coin is that I don't want an attacker
who is able to collect the digests for a single password and multiple
salts to be able to easily recover the password because the digest was
too dependent on it.

For context, I have amateur experience in cryptography and a moderate
mathematical background.

Thanks for any help.
-Brian
From: Maaartin on 24 Mar 2010 15:12
On Mar 24, 7:04 pm, bmearns <mearn...(a)gmail.com> wrote:
> I'm performing a salted hash for generating multiple passphrases from
> a single password. The salt is assumed to be known to an adversary,
> and I'm interested in knowing what sort of dependency the hash output
> has on the salt versus the password. For instance, if the salt and
> password are of equal length, is it fair to say that the hash output
> is equally dependent on both of them? Does it matter what the entropy
> density of each is, or how those lengths compare to the length of the
> digest?

You need no entropy in the salt, what you need is having different
salt for each use, you can use a counter if appropriate. The reason
for the salt is to make dictionary attacks much harder and prevent the
use of rainbow tables.

> Does any kind of vague concept of dependency even make sense in this context?

I don't think so (but I'm no expert).

> My motivation for the question is as follows: multiple users will
> likely have the same salt (the salt is something relevant to the
> specific service, like "gmail" for an email password, so everybody
> using the technique for that service will likely have the same salt).

This is no good idea because of the reason given above.

> I don't want this to make it unnecessarily easy for an attacker to
> break into the service because the digest was too dependent on the
> known salt.

You've got it wrong. There's no such thing as "being too dependent",
you don't need to make it depend less on the salt in order to make it
depend more on the password.

> The opposite side of the same coin is that I don't want an attacker
> who is able to collect the digests for a single password and multiple
> salts to be able to easily recover the password because the digest was
> too dependent on it.

You can think about the hash function as being "perfectly dependent"
on every bit of the password and every bit of the salt. For sure,
there's no such problem as what you try to avoid.
From: bmearns on 24 Mar 2010 15:28
On Mar 24, 3:12 pm, Maaartin <grajc...(a)seznam.cz> wrote:
> On Mar 24, 7:04 pm, bmearns <mearn...(a)gmail.com> wrote:
>
> > I'm performing a salted hash for generating multiple passphrases from
> > a single password. The salt is assumed to be known to an adversary,
> > and I'm interested in knowing what sort of dependency the hash output
> > has on the salt versus the password. For instance, if the salt and
> > password are of equal length, is it fair to say that the hash output
> > is equally dependent on both of them? Does it matter what the entropy
> > density of each is, or how those lengths compare to the length of the
> > digest?
>
> You need no entropy in the salt, what you need is having different
> salt for each use, you can use a counter if appropriate. The reason
> for the salt is to make dictionary attacks much harder and prevent the
> use of rainbow tables.

Thanks for the response Maaartin. I understand the concept of
cryptographic salt, but that's not actually what I'm going for here. I
referred to it as salt because it's used in a similar way, but in this
application it's used for different purposes. I think a quick
illustration might make it a little clearer. I have a strong password
I've committed to memory. I want to use different passwords for every
service, but I don't want to remember a different strong password for
each service. So I simply append the service name to my strong
password, hash it, and use the digest as my password for that service.
The service name is employed in a manner similar to salt, but not
intended as a defense against dictionary attacks as salt would
normally be used.

[snip]
> You've got it wrong. There's no such thing as "being too dependent",
> you don't need to make it depend less on the salt in order to make it
> depend more on the password.

Can you explain this any more? The digest has a finite size so
strictly speaking there is some limit to how much input it can depend
on, right? It should be related to the amount of information it can
encode, I think.

[snip]

Thanks,
-Brian

From: J.D. on 24 Mar 2010 15:36
On Mar 24, 2:04 pm, bmearns <mearn...(a)gmail.com> wrote:
> I'm performing a salted hash for generating multiple passphrases from
> a single password. The salt is assumed to be known to an adversary,
> and I'm interested in knowing what sort of dependency the hash output
> has on the salt versus the password. For instance, if the salt and
> password are of equal length, is it fair to say that the hash output
> is equally dependent on both of them? Does it matter what the entropy
> density of each is, or how those lengths compare to the length of the
> digest? Does any kind of vague concept of dependency even make sense
> in this context?
>
> My motivation for the question is as follows: multiple users will
> likely have the same salt (the salt is something relevant to the
> specific service, like "gmail" for an email password, so everybody
> using the technique for that service will likely have the same salt).
> I don't want this to make it unnecessarily easy for an attacker to
> break into the service because the digest was too dependent on the
> known salt.
>
> The opposite side of the same coin is that I don't want an attacker
> who is able to collect the digests for a single password and multiple
> salts to be able to easily recover the password because the digest was
> too dependent on it.
>
> For context, I have amateur experience in cryptography and a moderate
> mathematical background.
>
> Thanks for any help.
> -Brian

If the password is large enough to prevent brute force guessing (which
it should be anyway), and if the hash function is sufficiently
resistant to preimage attacks, then knowledge of the salt(s) will not
enable the attacker to recover the password from the digest(s).
From: J.D. on 24 Mar 2010 15:53
On Mar 24, 3:28 pm, bmearns <mearn...(a)gmail.com> wrote:
> On Mar 24, 3:12 pm, Maaartin <grajc...(a)seznam.cz> wrote:
>
> > On Mar 24, 7:04 pm, bmearns <mearn...(a)gmail.com> wrote:
>
> > > I'm performing a salted hash for generating multiple passphrases from
> > > a single password. The salt is assumed to be known to an adversary,
> > > and I'm interested in knowing what sort of dependency the hash output
> > > has on the salt versus the password. For instance, if the salt and
> > > password are of equal length, is it fair to say that the hash output
> > > is equally dependent on both of them? Does it matter what the entropy
> > > density of each is, or how those lengths compare to the length of the
> > > digest?
>
> > You need no entropy in the salt, what you need is having different
> > salt for each use, you can use a counter if appropriate. The reason
> > for the salt is to make dictionary attacks much harder and prevent the
> > use of rainbow tables.
>
> Thanks for the response Maaartin. I understand the concept of
> cryptographic salt, but that's not actually what I'm going for here. I
> referred to it as salt because it's used in a similar way, but in this
> application it's used for different purposes. I think a quick
> illustration might make it a little clearer. I have a strong password
> I've committed to memory. I want to use different passwords for every
> service, but I don't want to remember a different strong password for
> each service. So I simply append the service name to my strong
> password, hash it, and use the digest as my password for that service.
> The service name is employed in a manner similar to salt, but not
> intended as a defense against dictionary attacks as salt would
> normally be used.
>
> [snip]
>
> > You've got it wrong. There's no such thing as "being too dependent",
> > you don't need to make it depend less on the salt in order to make it
> > depend more on the password.
>
> Can you explain this any more? The digest has a finite size so
> strictly speaking there is some limit to how much input it can depend
> on, right? It should be related to the amount of information it can
> encode, I think.
>
> [snip]
>
> Thanks,
> -Brian

Cryptographic hash functions are like good block ciphers in that they
incorporate the principles of confusion and diffusion. With a good
hash function, every single bit of the digest will be a very
complicated function of every single bit of the message, such that if
any bit of the message is complemented then every bit of the resulting
digest will have a (very close to) 50% chance of being complemented as
well.

In this sense, every bit of the digest 'depends' on every bit of the
message, and with a good hash function the only way to find the
password from the salt and the digest is by brute force guessing.
There are, for example, MAC generators that simply prepend a secret
key to the beginning of the message and then run a cryptographically
secure hash function on the result (e.g. Keccak) -- the digest is the
MAC, and even though the attacker knows the entire message (less the
secret key), and knows the hash function, the attacker still cannot
find the secret key except by brute force.

Hash functions do have limits on how large a message they can
compress, but generally those limits are so large as to be irrelevant.
 |  Next  |  Last
Pages: 1 2 3
Prev: CFP DATA MINING 2010: new date - until 29 March 2010
Next: A link to a news on SSL