Quotes of the week [LWN.net]

Quotes of the week

Posted Dec 14, 2007 20:49 UTC (Fri) by zooko (subscriber, #2589) [Link]

Hm.  You know, it really *is* reasonable to assume that the NSA is spending a mind-boggling
amount of computrons building a giant database of SHA-1 input/output pairs.  Their budget is
practically unlimited, and it should be obvious to them that the future might present rich
plums to be plucked by checking whether a given SHA-1 output is already in their giant table
(in which case they know the input that produced it).

Obviously the same goes for SHA-256, GOST, etc..  I'm pretty sure that NSA wouldn't hesitate
to throw a few tens of millions of dollars a year at a project like that.  And of course they
might find it to be more cost-effective to build custom hardware which does this particular
job quickly (and with low power expenditure) instead of implementing this job in software on
commodity hardware.

One consequence of this consideration is that if you are going to be using SHA-256 hashes, and
you don't want to risk that an organization like NSA has already gotten lucky and guessed an
input and stored the resulting (input,output), and the output happens to be the output of one
of your hashes, then one thing that you can do is prepend all of your inputs with an
application-specific fixed string of a few bytes (somewhere between 10 and 32 bytes, let's
say) to make inputs in your application distinct from inputs to other applications uses of
SHA-256, followed by a few bytes of all zeroes (somewhere between 10 and 32 bytes) to
distinguish pre-images for your application from "random" strings.

If you are interested in this notion I can give you some references to relevant papers by
cryptographers.

Quotes of the week

Posted Dec 16, 2007 22:03 UTC (Sun) by dlang (✭ supporter ✭, #313) [Link]

Quote:
Hm.  You know, it really *is* reasonable to assume that the NSA is spending a mind-boggling
amount of computrons building a giant database of SHA-1 input/output pairs.  Their budget is
practically unlimited, and it should be obvious to them that the future might present rich
plums to be plucked by checking whether a given SHA-1 output is already in their giant table
(in which case they know the input that produced it).

actually, this isn't reasonable.

remember that sha1 is a HASH, it takes many inputs and maps them to a single output (after
all, it can take a multi-gig file and produce a 160 byte output, there are obviously more
possible multi-gig files then there are 160 byte values, so there must be overlap).

Quotes of the week

Posted Dec 17, 2007 0:09 UTC (Mon) by njs (guest, #40338) [Link]

I don't understand the distinction you're making between the "application-specific fixed
string" and the "few bytes of all zeros".  Presumably the only thing that matters is that you
have a long-enough, fixed, unique chunk of magic at the beginning of your strings -- making it
pure randomness would work as well as anything else.  Is the distinction really just that to
get something like 32 bytes of fixed unique magic, one popular technique might be to pick some
natural string for your application (e.g., "app name in uppercase ASCII"), and then pad with
zero bytes to make sure its long enough?

application-specific salt

Posted Dec 17, 2007 3:58 UTC (Mon) by zooko (subscriber, #2589) [Link]

Hm. I think you may be right that my suggestion of the all-zeroes part doesn't add anything.
I was vaguely imagining that I wanted to make sure that the table wouldn't contain hash-inputs
that matched your application-specific salt prefix unless the table-builder had chosen to
include your salt prefix specifically. I.e., the table-builder wouldn't "accidentally"
include inputs which matched your prefix.

However, on reflection, my suggestion of some extra all-zeroes doesn't really guarantee that
any better than the salt does alone, provided that the salt is long enough. (32 bytes is
definitely long enough. Fewer might be long enough depending on the details of your
application.)

I really like your suggestion of appending zeroes (or space chars) until the total salt
including padding is 32 bytes. Oh, but on the other hand if everyone does that then the
table-builder can benefit from guessing "a few random bytes, padded with spaces to 32, then a
few more random bytes"...

Of course, if your application never takes a hash of something that doesn't itself contain at
least 32 bytes of unpredictability, then your application doesn't need this salt at all.

This proposal (which isn't original with me -- it is presaged by Schneier and Kelsey "Chosen
Protocol Attack", for example) is basically just to use salt, the same way that we have been
using salt in our stored encrypted passwords for many a year. The only difference is that
this is per-application salt instead of per-server salt.

Regards,

Zooko

application-specific salt

Posted Dec 17, 2007 6:23 UTC (Mon) by njs (guest, #40338) [Link]

Right, the horrible nasty protocol interaction cases that Schneier and Kelsey raise *really*
need this kind of protection (so, umm, every cryto protocol ever does, is basically the
conclusion).  It's an interesting idea that similar defenses can help against Rainbow tables
(and their ilk) -- is there some way that pre-image attacks are "really" protocol interaction
attacks?

But it's important to note that using context-specific salting as a defense against protocol
interaction is truly, cryptographically strong, whereas for pre-image attacks it is only
"economically sound", and only for lesser-used protocols -- it's not any *harder* to mount a
pre-image attack on "SSL-salted SHA-256" than it is on "plain SHA-256", it's just one can't
then take the results of one's investment in attacking SSL and also use it to attack
lesser-used protocols that would not otherwise justify the investment in developing Rainbow
tables.

Of course, one could declare that the "context salt" for SSL connections should include the
name of the server being connected to or something like that -- diversity is *way* easier to
get than shared entropy.

BTW, I believe that for common (Merkle-Damguard construction?) hashes, this comes out
mathematically equivalent to simply choosing a different IV for each use of the hash?

application-specific salt

Posted Dec 17, 2007 13:51 UTC (Mon) by zooko (subscriber, #2589) [Link]

You are exactly right -- application-specific salt is merely "economically sound" in that it
doesn't increase the cost to attack your application's use of a hash function, but it does
increase the cost to attack all applications' uses of that hash function.  This is precisely
the same as salting your encrypted password -- it doesn't make it any harder for the attacker
to brute force *your* password, but it does make it harder for him to use brute force to
recover *any* password.

  "Of course, one could declare that the "context salt" for SSL connections should include the
name of the server being connected to or something like that -- diversity is *way* easier to
get than shared entropy."

Well that is an excellent point.  I guess this goes back to "Chosen Protocol Attack" and
"Strategies Against Replay Attacks" by Tuomas Aura [1].  Oh, but your point is that this kind
of salt from shared-public-knowledge protects against tables (e.g. Rainbow Tables) in addition
to protecting against replay or chosen-protocol attack.  Nice!

  "BTW, I believe that for common (Merkle-Damguard construction?) hashes, this comes out
mathematically equivalent to simply choosing a different IV for each use of the hash?"

I believe you are right.  I prefer to express it in terms of a specific input to the hash
function so that people understand that I am using the hash function as defined by standards
and am not changing it.

[1] http://citeseer.ist.psu.edu/aura97strategies.html