Subject: Re: NIST publishes new DSA draft

From: [email-masked] ("Hal Finney")
Date: Tue, 14 Mar 2006 11:44:47 -0800 (PST)

David Shaw writes:
> In the OpenPGP context, probably the most interesting bit is that the
> 160-bit hash limit has been removed.  The sizes supported are:
>
> * 1024-bit key, 160-bit hash (the current DSA)
> * 2048-bit key, 224-bit hash (presumably aimed at SHA-224)
> * 2048-bit key, 256-bit hash (presumably aimed at SHA-256)
> * 3072-bit key, 256-bit hash (presumably aimed at SHA-256)
>
> It also adds the concept of using a larger hash than will fit by
> taking the leftmost bits.

The main question is whether we want to change the current draft to make
these changes.  That would probably require backing it out of "last
call" status.  Personally I think this makes sense.  There is no one
waiting urgently for this draft to be finalized AFAIK.  The alternative
will be to immediately amend the RFC with another RFC.  But for the sake
of future implementors I think it would be better to wait a few months
more and put it all into one draft.

In two places in RFC2440-bis, we mention that DSA signatures must use
a 160 bit hash.  The main one is in section 5.2.2, Version 3 Signature
Packet Format.  This is not a good location as it is not information
that is specific to V3 signature packets.  It applies to V4 signatures
as well.  This information should probably be in 5.5.2 on public key
packet formats, or at least should be repeated in 5.2.3 for V4 sigs.

It is also mentioned in section 13, Security Considerations, where we
state explicitly that RIPEMD-160 can be used, but that "DSS" as compared
to "DSA" requires SHA-1.

One of the implications of the changes in the new draft is that 1024 bit
DSA keys can use SHA-256 (truncated to 160 bits).  We should probably
allow that as an alternative to SHA-1, although it raises backwards
compatibility issues.

For 2048 bit keys they allow either 224 or 256 bit hashes.  This also
means allowing a subgroup "q" size of either 224 or 256 bits, I think.
The hash then must either match "q" or be larger, in which case it is
left-truncated.

We do not have an algorithm ID for SHA-224.  SHA-224 is the same
algorithm as SHA-256 but uses different initial values internally,
and then truncates the result to 224 bits.  I don't see any advantage
in this case to using SHA-224 over using SHA-256 truncated to 224 bits.
However we might want to add an ID for it in case an implementor wanted
to follow the new DSS spec very closely.

The simplest change we could make would be to allow that DSA keys can
use modulus "p" and subgroup "q" values of the specified sizes, based
on the table above.  Hashes should be equal in size or larger than the
"q" size.  Hashes larger than the "q" size should be left-truncated.
Then we could note that for DSS compliance the hashes must be taken from
the SHA family, either SHA-1 or one of the larger SHA's.

We might want to think about making SHA-256 be another MUST algorithm.
The only MUST hash now is SHA-1.  Making SHA-256 be a MUST would make
these new key sizes be more useful, and also give us an easier fallback
if SHA-1 should be broken.

I also think we should change the names of SHA256 etc to use dashes
as in SHA-256; those are the official names.

Hal Finney

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Mar 2006 14:20:09 +0000

> as in SHA-256; those are the official names.

I'm in favour of making these changes now rather than waiting for the
next version.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: "Anton Stiglic" <[email-masked]>
Date: Wed, 15 Mar 2006 21:40:01 -0500

I haven't participated in this list so far but I have been lurking here for
some time.

I agree with the phasing out of SHA1, as soon as possible!
Indeed there have been some vulnerabilities demonstrated, collisions on
arbitrary inputs (as this has already been discussed before, this is not as
strong attack as 2nd pre-image attack which would directly affect digital
signatures based on SHA1 for example, but still an indication of weakness in
the hash algorithm).  Also governments have plans of phasing SHA1 out soon. 
CSE in Canada plans to take it out of commission by 2008 for the protection
of certain types of information, see for example
http://www.cse-cst.gc.ca/services/crypto-services/crypto-algorithms-e.html

--Anton

-- 
Internal Virus Database is out-of-date.
Checked by AVG Free Edition.
Version: 7.1.375 / Virus Database: 268.1.2/274 - Release Date: 03/03/2006

---

From: David Shaw <[email-masked]>
Date: Thu, 16 Mar 2006 14:28:23 -0500

> more and put it all into one draft.

I agree with this.  It is unfortunate, but will ultimately result in a
better RFC.

> to follow the new DSS spec very closely.

Given that the main alternative is truncated SHA-256, which implies
SHA-256 support in the first place, and the code difference between
SHA-256 and 224 is simple to say the least (as you say, same
algorithm), I think we should add the ID (#7 ?) for SHA-224.  It's a
checkbox item that we can trivially support.

> if SHA-1 should be broken.

Unless DSA2 is also a MUST, I wonder what the practical advantage to
that would be (beyond making the social point that we really, really
want people to move away from SHA-1).  Since an OpenPGP program would
not necessarily know whether the recipient could handle SHA-256
(SHA-256 dates from around 2004, implementation-wise), it would have
to use SHA-1 in many or most cases anyway.  Obviously a DSA2 signature
wouldn't be expected to work, but an RSA signature would have this
problem, and DSA1 (using a truncated SHA-256) would have the problem
as well for both truncation and SHA-256 reasons.

A few months back you asked the question whether new DSAs would best
be supported by extending the definition of the current DSA, or by
assigning a new algorithm ID for DSA2.  At the time, most people
(myself included) felt that extending the current DSA would be the
right answer.  Now that we have actual information about DSA2, perhaps
it would be worth revisiting that question.  A new algorithm ID for
DSA2 resolves a number of problems in one fell swoop as there is no
expectation of interoperability.  SHA-256 is always usable
(effectively the default) for DSA2, and there is no problem with
knowing when it is possible to use truncation (always).

> as in SHA-256; those are the official names.

To be clear here: are you referring to changing the descriptive text
in the draft or changing the hash name strings as used in clearsigned
message "Hash:" headers?  The first is easy and I agree should be
done, the second has compatibility implications.

David

---

From: Ian G <[email-masked]>
Date: Fri, 17 Mar 2006 16:01:25 +0100

David Shaw wrote:
> want people to move away from SHA-1).

I think this is pretty much all of the point.  Any
new DSA signing method or other usage will likely
be non-obligatory, but pushing the implementations
into that direction seems useful.

> knowing when it is possible to use truncation (always).

Sounds good to me.

iang

---

From: Werner Koch <[email-masked]>
Date: Fri, 17 Mar 2006 16:54:21 +0100

> Sounds good to me.

I support this too.  The majority of keys are DSA keys q=160 bit.
Having a new algorithm indentifier will help more than harm.

Salam-Shalom,

   Werner

---

From: David Shaw <[email-masked]>
Date: Fri, 17 Mar 2006 12:49:37 -0500

> Having a new algorithm indentifier will help more than harm.

Even though I originally brought it up, I've given this a good bit of
additional thought while mailing with Hal on the list yesterday, and I
think it really does come down to something as simple as a question of
error messages.  I'm not for a new algorithm ID.

It breaks down like this:

1) a q==160 signature without truncation (hash size matches q exactly)
2) a q==160 signature with truncation (hash left-truncated to match q)
3) a q!=160 signature without truncation (hash size matches q exactly)
4) a q!=160 signature with truncation (hash left-truncated to match q)

I'm not mentioning the larger key size in DSA2 as I believe that
deployed code will handle larger DSA key sizes correctly.

Obviously #1 isn't a problem, as it is what DSA is today.  I think PGP
can actually do #2, but for the sake of argument, let's say that
nobody can do #2, #3, or #4 on current code.

If we don't assign a new algo ID for DSA2, #3 and #4 will fail because
of the wrong q size, and #2 will fail because of the truncation.  If
we do assign the new ID, as before #2, #3, and #4 will fail - but so
will #1!  Even though the signatures are compatible, the new algo ID
will cause the signature to fail on the older implementation.  This
argues against a new algo ID.  Even if we don't create DSA2 q=160 keys
(internally changing them to DSA1 keys), this just returns the
question to neutral, and the extra code complexity and questions (will
it break any keyservers? It will certainly break pksd) of assigning
the new algo ID argue against it.

David

---

From: Jon Callas <[email-masked]>
Date: Sun, 19 Mar 2006 11:51:17 -0800

I think we ought to keep it with the same algorithm number.

I'm happy to put in SHA-224 (meaning it's trivial work), but I don't  
like it, myself. The reason is that SHA-224 is really a truncated  
SHA-256. Thus, it has no advantages over SHA-256 except being smaller  
by 32-bits with 112 bits of security. The reason it exists at all is  
for crypto-balance with 2-key 3DES (which is not TDEA), which we  
don't allow at all. I don't think we should have it as it goes  
against our principles of wanting a minimum of 128-bits of security  
in OpenPGP. (Yes, yes, I know that SHA-1 doesn't meet this either,  
but until SHA-256, we didn't have many options. That doesn't mean the  
principle is wrong; we *have* options.)

	Jon

---

From: Ian G <[email-masked]>
Date: Mon, 20 Mar 2006 20:38:47 +0100

Jon Callas wrote:
> for crypto-balance with 2-key 3DES (which is not TDEA), which we  don't 
> allow at all. I don't think we should have it as it goes  against our 
> principles of wanting a minimum of 128-bits of security  in OpenPGP. 
> (Yes, yes, I know that SHA-1 doesn't meet this either,  but until 
> SHA-256, we didn't have many options. That doesn't mean the  principle 
> is wrong; we *have* options.)

In general I'd agree that the less algorithms/lengths
the better.  I'd certainly be keen to drop SHA-224 if
there is no good reason for it.

iang

---

From: David Shaw <[email-masked]>
Date: Mon, 20 Mar 2006 15:28:41 -0500

> principle is wrong; we *have* options.)

I understand the argument about wanting 128 bits of security, but
since the new DSA allows a 224 bit q, there just isn't room for 128
bits of security.  Whether we truncate SHA-256 and call it "truncated
SHA-256" or truncate SHA-256 and call it "SHA-224", we have to
truncate.

We support DSA now, with a note saying that if someone wants DSS, they
need to use SHA-1.  I suspect we'll end up in a similar place with
DSA2 allowing whatever key size and q size that people want to use and
a note that if they want DSS they need to use one of the four
NIST-blessed key size / q size pairs.

I lean towards adding SHA-224 as one of those four pairs has a 224-bit
q, and NIST suggests SHA-224 for this size.  It's only a lean towards
adding it as NIST also suggests truncated 256, 384, or 512 as valid
options, so 224 is not the only game in town.  (384 seems a little
silly as it would be a truncation of a truncation, but it's an
option.)  It's really a feeling that we currently support 4 out of the
5 FIPS-approved hash functions (SHA-1, 256, 384, 512), and since
supporting the 5th (224) is so trivial, we may as well be complete.

I'll defer to someone who feels more strongly about this than I do.

David

---

From: Tony Hansen <[email-masked]>
Date: Mon, 20 Mar 2006 16:08:28 -0500

Just a quibble. Truncating sha-256 down to 224 bits does not give the
same output as sha-224, as sha-256 and sha-224 use different
initialization vectors. So "truncated sha-256" and "sha-224" really
would be totally different hash values.

No comment on the rest of what you say.

	Tony Hansen
	[email-masked]

---

From: David Shaw <[email-masked]>
Date: Mon, 20 Mar 2006 16:35:23 -0500

No, it is not the same output, but it is the same amount of security.
Which hash and which IV doesn't matter here - just that the end result
is 224 bits long.

David

---

From: Ben Laurie <[email-masked]>
Date: Sun, 26 Mar 2006 12:12:25 +0100

Jon Callas wrote:
> SHA-256. Thus, it has no advantages over SHA-256 except being smaller by
> 32-bits with 112 bits of security. The reason it exists at all is for
> crypto-balance with 2-key 3DES (which is not TDEA), which we don't allow
> at all.

<pedantic>

3-key DES also has a strength of 112 bits.

</pedantic>

> I don't think we should have it as it goes against our
> SHA-256, we didn't have many options. That doesn't mean the principle is
> wrong; we *have* options.)
> 
>     Jon
> 
>

---

From: Jon Callas <[email-masked]>
Date: Mon, 27 Mar 2006 12:00:20 -0800

> 3-key DES also has a strength of 112 bits.

There are certainly good arguments for that, but if 3-key 3DES is no  
stronger than 2-key, then there shouldn't be any harm in dropping the  
third key. Right? If you don't like this idea (that 2-key and 3-key  
are equivalent), which I don't, then 3-key must be some stronger. It  
just isn't easy to know how much more.

I wrote a long thing on this a couple years ago at:

<http://searchsecurity.techtarget.com/tip/ 
1,289483,sid14_gci968714,00.html?track=NL-102&ad=486202>

	Jon

---

From: Jon Callas <[email-masked]>
Date: Mon, 27 Mar 2006 13:28:13 -0800

On 27 Mar 2006, at 12:36 PM, Ben Laurie wrote:

>
> I'm not going to argue with this, but it clearly ain't much more. You
> would be out on a limb to argue that it provided usefully more than  
> 112
> bits - though I won't hesitate to agree that 2DES < 3DES.
>

Ben, I think we're far closer to agreeing than disagreeing.

During The Crypto Wars, we crypto-proponents made a point of saying  
that the minimum crypto we'd live with was 128-bit. The reasons for  
this had as much to do with the simple mathematical fact that 128 was  
the next convenient power of two as anything else. So therefore, viva  
IDEA, viva CAST, viva Blowfish. A lot of it was also just sheer  
politics.

But what about three-key 3DES? Collectively, we agreed to include it  
as a "128-bit" cipher (the quotes are there to mean quasi-, or so- 
called). The reasons for this were also mostly politics. It would  
have been unwise to say, "ooo, ick, 3DES" and in fact in this group,  
arguably the most political standards group of them all, we not only  
*accepted* 3DES as 128-bit cipher, but made it the MUST. That was  
also mostly a political decision. It saved us a long, acrimonious  
argument about Blowfish and CAST with side trips along 3DES itself,  
DES/X, SAFER and others. Bravi us. (Personally, I say "3DES" to mean  
three-key-3DES. I consider the two-key version to be some unmentioned  
step-down, kinda the way that Blowfish will work with 32-bit keys.  
It's true, but we don't even grace it with a mention.) Reality is a  
collective hunch, especially in the IETF. The hunch is that 3DES is  
as good as IDEA, CAST, Blowfish, etc.

Now, a decade later, we all mostly use AES. In fact, we mostly use  
AES-256, and that for marketing reasons. AES-128 runs faster than  
single-DES, and AES-256 is only 20% slower than -128, so there is  
pressure to step up to 256-bit keys. People do it because all the  
other kids are doing it, not for security.

You are right that we've *agreed* that 3DES is a "128"-bit algorithm  
and there's no math to back it up. As fantasies (or collective  
hunches) go, it's not a bad one. The strength of 3DES all revolves  
around how much it's not a group. It appears to be enough of a non- 
group that this isn't a mad thought. Better, though, to just use AES.  
Or Twofish. Or petition the group to put Serpent in.

Nonetheless, getting back to the hash functions, the *only* reason to  
use SHA-224 is that you have an application where a 28-byte hash will  
work and a 32-byte one will not. If one person thinks that's  
important for engineering reasons, I'm happy to have it in. If zero  
people think it has engineering value, then less is more. We don't  
need another hash function with no obvious value because in the  
future there will be more hash functions. Save room on the bus for  
the ones that aren't born yet.

	Jon

---

From: Ben Laurie <[email-masked]>
Date: Mon, 27 Mar 2006 21:36:43 +0100

Jon Callas wrote:
> third key. Right? If you don't like this idea (that 2-key and 3-key are
> equivalent), which I don't, then 3-key must be some stronger. It just
> isn't easy to know how much more.

I'm not going to argue with this, but it clearly ain't much more. You
would be out on a limb to argue that it provided usefully more than 112
bits - though I won't hesitate to agree that 2DES < 3DES.

Cheers,

Ben.