Re: [Hash] BOF Goals

This guidance is provided for unforeseen applications in order to 
provide interoperability. A standard method for truncating hash 
function outputs is provided strictly as a convenience for 
implementers and application developers. No claims are made about the 
suitability of truncating the hash output or about the security level 
obtained by truncating the hash output. The proper use of truncated 
hash outputs is an application-level issue.

Truncating the hash function output can impact the security of an 
application. For example, applications that use the truncated hash 
output risk attacks based on confusion between different parties 
about the specific amount of truncation used, and the specific hash 
function whose output was truncated.  Any application using truncated 
hash output is responsible for ensuring that the truncation amount 
and the hash function used are known to all parties, with no chance 
of ambiguity.

Truncated hash output shall not be used in place of the full hash 
output by standardized applications that reference this Standard, 
e.g. digital signatures (FIPS 186-2) or keyed hash functions used for 
message authentication (FIPS 198).

At 7:37 PM -0700 7/12/05, Jon Callas wrote:
>It's therefore a bit unusual for me to ask one of my own cliché 
>questions: What problem are we trying to solve? and have that be 
>both genuine and backed with my own puzzlement. I don't know what we 
>are doing, expect, plan, or even hope.

This is not a Working Group to produce a protocol. As the proposed 
charter says, "The proposed working group responds to the current 
state of research in this area.  However, additional research is 
likely to provide new insights as the working group progresses." In 
other words, our job is to help in an area that people didn't feel 
the need for help before, namely the use of hashes in protocols.

>As it has been stated, there are two problems we're looking at:
>
>(1) truncating existing wide hashes for use in systems like DSA.
>
>(2) to explore "randomized" hashes.

Those are only the first two. There is a third problem we may be 
looking at in the longer term: "The optional second phase will 
identify one or more standards-track one-way hash functions that 
fulfill the requirements stated in the BCP documents developed in the 
first phase.  Guidance will also be developed
to assist protocol developers in the selection among the 
standards-track one-way hash functions."

>FIPS-180, which describes all of the SHA-family hashes [1] answers 
>this question on page 73:
>
>     "Some applications may require a hash function with an output size
>     (i.e., message digest size) different than those provided by the
>     hash functions in this Standard. In such cases, a truncated hash
>     output may be used, whereby a hash function with a larger output
>     size is applied to the data to be hashed, and the resulting output
>     (i.e., message digest) is truncated by selecting an appropriate
>     number of the leftmost bits. For example, if an output of 96 bits is
>     desired, the SHA256 hash function could be used (e.g., because it is
>     available to the application), and the leftmost 96 bits of the
>     output are selected as the message digest, discarding the rightmost
>     160 bits of the SHA-256 output."

>NIST is supposed to release an addendum to DSA for wide hashes and 
>keys bigger than 1024 bits.

I see nothing on the NIST site that says that they will release this 
addendum, nor have I heard it from the NIST folks I have spoken with. 
That is not to say that they aren't working on it, just that we 
shouldn't assume that the addendum is a fact.

>The *correct* thing for us to do is wait for that.

Some folks at NIST have told us (quite informally) that us working on 
the truncation issue would be a good thing. Certainly, if it turns 
out that simple truncation can be shown to be as safe as any other 
shortening method, that would help DSA because it would make the 
algorithm much simpler. This is why I asked in the previous message 
for input on research in this area.

>If someone finds the wait unacceptable, then there's an obvious 
>workaround -- use RSA with SHA-256.

This is simplistic on a couple of levels.

- There are many properties where DSA and RSA differ, and a protocol 
developer may have chose DSA for one of those.

- The assumption of SHA-256 seems rash. In particular, we don't yet 
have information preimage attacks on SHA-1, we haven't specified 
which kinds of uses of hashes with digital signatures are affected by 
the reduction in collision strength, and we haven't looked at whether 
other formulations of hashes might appear to more immune to attacks 
related to the ones we know now.

- Changing protocols is very difficult for typical users. They may be 
using a protocol in which there is no identifier for "RSA with 
SHA-256". They may be using the algorithm for long-lived signatures, 
where switching means using multiple protocols with different 
properties. Having some users change while others don't can cause 
long-term problems for both groups: that's why the IETF tries to be 
clear which algorithms to use, and when.

>The answer of how to truncate the wide SHAs is answered for us in FIPS 180.

If you only read the paragraph you quoted, yes. The rest of that 
section from FIPS 180 says:

>This guidance is provided for unforeseen applications in order to 
>provide interoperability. A standard method for truncating hash 
>function outputs is provided strictly as a convenience for 
>implementers and application developers. No claims are made about 
>the suitability of truncating the hash output or about the security 
>level obtained by truncating the hash output. The proper use of 
>truncated hash outputs is an application-level issue.
>
>Truncating the hash function output can impact the security of an 
>application. For example, applications that use the truncated hash 
>output risk attacks based on confusion between different parties 
>about the specific amount of truncation used, and the specific hash 
>function whose output was truncated.  Any application using 
>truncated hash output is responsible for ensuring that the 
>truncation amount and the hash function used are known to all 
>parties, with no chance of ambiguity.
>
>Truncated hash output shall not be used in place of the full hash 
>output by standardized applications that reference this Standard, 
>e.g. digital signatures (FIPS 186-2) or keyed hash functions used 
>for message authentication (FIPS 198).

Not wearing my BOF chair hat: the little that is said in FIPS 180 is 
not sufficient to decide that we know enough about the issue to 
decide anything. The cryptographic community is certainly able to 
deal with this issue better than the first paragraph of the section 
in FIPS 180.

>The answer of what to do with DSA is "Don't." We can wait for NIST. 
>If we don't we're going to have to do what they say, anyway. Why 
>make more work?

Because the "more work" may be valuable research, even for NIST.

To be clear: I'm not saying we should have truncation in our WG 
charter, and Jon is the first so far to speak up to say we shouldn't. 
Hearing from others on the mailing list would be useful.

>The second issue, using salted hashes (I prefer this to 
>"randomized"), is more interesting technologically, but there are 
>still a number of extremely important issues open about them.

Exactly!

>The first open issue is their expected security when compared both 
>to the unsalted version and comparable other functions. For example, 
>we know that SHA-1 should have 80 bits of security and doesn't. Will 
>as salted SHA-1 have 80 bits of security? What makes us think so? 
>SHA-256 should have 128 bits of security, and many of us (I know I 
>am one) expect it to have flaws. However, do we expect it to have 
>less than 80 bits of security? I don't.

This paragraph again assumes a move to SHA-256. It might be better to 
deal with the tradeoffs, as is done in the one Internet Draft we 
have, 
<http://www.ietf.org/internet-drafts/draft-irtf-cfrg-rhash-00.txt>.

>In discussions in the CFRG list, Dan Bernstein has suggested that 
>salted MD5 has similar performance to unsalted SHA-256.

Seeing actual numbers on this would be a great boon to the discussion.

>It seems to me that if there are questions that a hashing working 
>group should be asking, they are not the ones we're asking, but 
>other ones that include:
>
>* What is the security of a salted hash function? Does salted MD5 
>have 64 bits of security? Does salted SHA-1 have 80 bits of 
>security? Does salted SHA-256 have 128 bits of security? Why do we 
>think this? I've seen no reasoning nor metrics.

Good questions, and ones we should answer.

>* What is the security of a truncated hash function? Examples: 
>Suppose SHA-256 has 110 bits of security (if it is as broken as 
>SHA-1, this is my predicted security value). If you truncate SHA-256 
>to 128 bits, does that mean that it has 55 bits of security? Or does 
>it mean that it has 64 bits of security? Or something in the middle? 
>Why do we think this? What do we expect its security to be if you 
>truncate it to 160 bits and why?

Good questions, and ones we should answer. So, now you want to keep 
the item in the WG charter? :-)

>* What is the performance of a salted hash function? Bernstein's 
>claim that salted MD5 has similar performance to SHA-256 has gone 
>unchallenged, and he himself has noted this silence.

These should not be difficult values to start generating.

>* Are there other constructions we can perform that give us security 
>over the naked hash function, but require less work than salting? 
>For example, suppose we took SHA-256 and folded its halves, XORing 
>them together. Does this give us more security than straight 
>truncation? If not, why not (since it seems intuitive that folding 
>would have at least an eensy bit more security)? What other 
>constructions could we make that improve over raw truncation without 
>the cost of salting?

Good questions, and ones we should answer.

>Without answers to these questions, I don't see how this working 
>group can give any meaningful results. Worse, I don't see how any 
>recommendation of this group can improve over the simple advice of 
>"use SHA-256." If this BOF results in a working group, I believe it 
>*must* address the questions I outlined above, as well as the issues 
>I and Bernstein have brought up in CFRG.

A specific list of issues on *this* list, not on CFRG, would help us 
finalize the charter.

>If salted hashes are slower than wider hashes and the wider hash has 
>enough security (enough being greater than 64 bits for an MD5 
>replacement and greater than 80 bits for a SHA-1 replacement), then 
>we should just use the wider hash and be done with it -- except when 
>that's not reasonable.

Having a description of when it is reasonable also seems to be 
valuable to be written down.

--Paul Hoffman, Director
--VPN Consortium

_______________________________________________
Hash mailing list
Hash@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/hash