Re: [Hash] BOF Goals

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

Does it need a working group?

I thought the I-D you and Bruce did was smashing. I thought it 
describes the current state of affairs quite well, especially that the 
main thing we know is the depth of what we don't know.

Now, if what we'd do in this working group is to come up something that 
was like that only better, fair enough. Then I have misunderstood what 
this WG would accomplish, and apologize.

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

But that should be a separate thing that happens when there's something 
to say. Guidance is simple right now and will give us a five-page RFC. 
There are lots and lots of edge conditions that can't be simply 
addressed in a single document.

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

At CRYPTO '04, I spoke to people and actually saw a proposed DSS 
update. Obviously, they haven't been happy with it. This is 
frustrating, but like it or not, they're the people who produce DSS, 
and when they come out with something, that's what to do.

If they don't come out with something before people really start 
switching, that would be sad, but that puts the urgency on them.

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

(I hope I'm not repeating myself.) Last summer, at PGP, we coded up DSA 
with truncated SHA-256. When the new results came out in February, we 
put it into alphas of PGP 9. I told some NIST people, who gave me the 
most dreadful look, and we took it out. (Actually, we didn't fully take 
it out in Beta 1, and so there were a few DSA-SHA256 signatures that 
leaked out into the world.)

The reason we didn't was that we decided that truncating wasn't the 
right thing, and sticking to SHA-1 is all right for the time being.

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

I worried about my last missive being far too long, and drastically 
truncated it before I sent it. I'll try to avoid that error again 
(which is part of why I risked repeating myself above, because even if 
I am, it's emphasis).

I'm the one responsible for the pithy comment about SHA-1 that it's 
time to walk, not run to the exit. I know that there are complications. 
Believe me.

I'm the author of both OpenPGP (which possibly has the widest use of 
DSA), and syslog-sign (which depends on DSA because it's really, really 
important to short signatures in a syslog packet).

In the OpenPGP case, it's cold comfort indeed to be told "make another 
key, then." I haven't. Heck, I got chewed out last weekend for our 
deprecating MD5. People get emotional about this.

In the syslog-sign case, we're in a bad spot. It's really, really 
important to have short signatures. Moving to SHA-256 is not 
convenient, and 40-byte sigs are important. This is a place were 
truncation or something else would be good. However -- I still say to 
stay the course on SHA-1. It's good enough for now. I repeat, for now.

Yes, this is not simple, and that's my point! If you want a simple 
answer, I gave one. That the simple answer is simplistic only 
underscores my questions about the WG's purpose and existence.

>> 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:
>
[elided]
>

Thank you! This is precisely my point. This is part of why we decided 
to not use truncated SHA-256. FIPS 180 tells us *how* to do it. It does 
not tell us *when* to, *why* to, or other things. But that's not what I 
said. I said that if one of the goals of the WG is *how* to truncate 
the wide SHAs, FIPS 180 tells us.

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

Then this should be in the IRTF, not the IETF.

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

Thanks.

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

I read it. As a protocol author, I find it amazingly unsatisfying.

If my worry, that this WG would take that draft, turn it into an RFC, 
and then start recommending, coercing, whatevering people to use it is 
an unfounded worry, then again, I apologize. I've been seeing things 
under the bed.

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

My point, as well.

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

Again, I don't see that as what a working group does.

>> * 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? :-)

My objection is to the WG charter, not its contents. If, however, I 
cannot affect the decision of *whether* to have a charter and we are 
indeed having one, then yes, I want it in the 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.
>

But that is at odds with one of the WG goals -- to explore salted 
hashing. I think it's far too early to do that.

My perception is that we're getting the verdict first -- 
randomized/salted hashing -- and collecting evidence later. If my 
perception is out of whack, please let me know.

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

Mea culpa. I forwarded my previous CFRG note here.

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

Assuming we have something to say that has a shelf life longer than 
bottled water, yes. I am not convinced we have that.

	Jon

________________________________________________________________
This message could have been secured by PGP Universal. To secure
future messages from this sender, please click this link:

https://keys.pgp.com/b/b.e?r=hash%40ietf.org&n=I6LW%2FTFegliptjmtozrp%2Bg%3D%3D

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