Subject: Line spacing in normative references

From: [email-masked] ("Hal Finney")
Date: Tue, 20 Sep 2005 10:39:39 -0700 (PDT)

A minor point, I notice that the spacing is inconsistent in the normative
references. Some are separated by blank lines and some are not.  It would
look nicer to be consistent here. I don't know if some macro is misfiring
or if we could clean it up and make it look better.

Hal

---

From: Jon Callas <[email-masked]>
Date: Fri, 30 Sep 2005 17:49:06 -0700

> or if we could clean it up and make it look better.

Cleaned up.

     Jon

Cc: [email-masked]
From: Jon Callas <[email-masked]>
Subject: Re: Line spacing in normative references
Date: Fri, 30 Sep 2005 17:49:06 -0700
To: Hal Finney <[email-masked]>
Sender: [email-masked]

> or if we could clean it up and make it look better.

Cleaned up.

     Jon

From: [email-masked] (Peter Gutmann)
To: [email-masked], [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
Date: Sat, 24 Sep 2005 19:31:30 +1200
Sender: [email-masked]

[email-masked] (Daniel A. Nagy) writes:
>On Thu, Sep 22, 2005 at 05:43:57PM +1200, Peter Gutmann wrote:
>> X9.42 was only added to S/MIME for political reasons.  AFAIK only one
>> implementation ever supported it, and that was the USG-funded reference
>> implementation that was required to support it.  In addition, MS supported a
>> read-only implementation just so they couldn't be accused of not supporting
>> it.
>
>>What political reasons? 

For a brief period during the S/MIME development, RSA was still owned by
RSADSI while DH wasn't.  From "The Crypto Gardening Guide and Planting Tips",
http://www.cs.auckland.ac.nz/~pgut001/pubs/crypto_guide.txt:

  An Internet standard RFC required that implementors support X9.42 DH key
  agreement, and provided RSA as an option (in IETF terms, "MUST X9.42, MAY
  RSA"). However, no existing software supported X9.42, no CAs would issue
  certificates for it, even if they did no-one wanted to renew all of their
  certificates ($$$) for an algorithm that provided no advantages over RSA,
  and no hardware (either crypto accelerators or smart cards) supported it
  (there was some token support after a few years, although even now there are
  problems being found with the X9.42 test vectors which indicate that no-one
  has really looked at them). As a result, even though the standard mandated
  use of X9.42, everyone treated it as if it said "MUST RSA, SHOULD NOT
  X9.42", pretending to do X9.42 while running business as usual with RSA.

>And why is there a reserved ID in OpenPGP?

OpenPGP has reserved IDs for all sorts of weird and wonderful stuff.  I guess
X9.42 is no exception.

Peter.

Date: Fri, 23 Sep 2005 07:46:43 -0400
From: David Shaw <[email-masked]>
To: Ben Laurie <[email-masked]>
Cc: [email-masked]
Subject: Re: Problems with v4 key packet format
Mail-Followup-To: Ben Laurie <[email-masked]>, [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Fri, Sep 23, 2005 at 11:35:42AM +0100, Ben Laurie wrote:
> 
> David Shaw wrote:
> >On Wed, Sep 21, 2005 at 02:26:13PM -0700, "Hal Finney" wrote:
> >
> >
> >>>If you're importing a foreign key or generating one on the fly, you don't
> >>>put subpackets into the key that cannot be determined next time you use 
> >>>the
> >>>same source to get the key. A flag in a subpacket indicating where the 
> >>>key
> >>>comes from might be useful, though.
> >>
> >>This is a good point, I'll have to think about it.  I'm still not
> >>sure that covering this material with key fingerprints and keyids is
> >>the right thing to do.  What would the security threats be from being
> >>able to bring a key back to life with the same fingerprint and keyid,
> >>but without any signatures on it being valid?
> >
> >
> >My original idea with subpackets was that they would be part of the
> >fingerprint, and changing a subpacket was akin to making a whole new
> >key as the fingerprint and key ID (though not the key material) would
> >change.  I see some advantages of what you are discussing.  It would
> >(somewhat) allow someone to violate a hard expiration date on their
> >key: make the key, get signatures, and then when the key expires, just
> >remake the key.  Essentially you can buy an extension on your "hard"
> >expiration time at the cost of losing all of your signatures.
> >
> >The thing is, I can't really decide if that is a threat or a
> >feature...
> 
> You can already do this by signing the new version of the key with the 
> old version of the key - same keypair, so messages to either will work, 
> and signatures made by either key will still check - but different IDs 
> and signatures on the keys.

Absolutely, but from the trust perspective (at least using the web of
trust), this second key is one further "hop" away from the one that
was signed.  It becomes the same situation as if someone generated a
brand new key without doing any trickery by keeping the same key
material and just signed it with the old one; the fact that the key
material is the same is interesting, but not really useful in practice
since the (changed) key ID is used to locate it in a keyring when
verifying a signature or handling a PKESK.

David

Date: Fri, 23 Sep 2005 12:16:35 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: "Daniel A. Nagy" <[email-masked]>
Cc: David Shaw <[email-masked]>, [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
Sender: [email-masked]

Daniel A. Nagy wrote:

> I think that SHA1 for key identification and fingerprinting is still a
> comfortable overkill.

It would seem that most efforts in this direction
are divisible into two classes - those with human
interaction and those without.

For the latter, it would seem reasonable to always
use full strength - the full bits available for
all computations.  Overkill is not a problem for
computers.

For human interaction issues, it is clearly tricky
in some cases that are hard to predict to use a
full length identifier.  So the notion could be that
each usage of a hash presented to humans simply
defines its own minimum portion of bits, but also
can and will accept a longer or even full length
hash without complaint.

(In effect that is what is done but the minimums
seem to be more hard coded and larger portions
have no acceptibility.)

 From this pov, we should

   * use the best hash available (e.g. SHA512, excessively)
   * convert to the display form as late as possible in the code
   * make sure that the "short form" convention is understood
     by all inputs
   * and recognisable/parsable in its text form.

     (Something like a dotted notation:  DEAD.BEEF would
     give us the 32 bits, DEAD.BEEF.C001.D00D would be
     64 bits.  These are relatively easy to parse, easier
     than the whitespace separated form.)

iang

PS: I'm not recommending SHA512 here, just conceptualising
the software engineering principles involved.

Date: Fri, 23 Sep 2005 11:35:42 +0100
From: Ben Laurie <[email-masked]>
To: David Shaw <[email-masked]>
CC: [email-masked]
Subject: Re: Problems with v4 key packet format
Sender: [email-masked]

David Shaw wrote:
> On Wed, Sep 21, 2005 at 02:26:13PM -0700, "Hal Finney" wrote:
> 
> 
>>>If you're importing a foreign key or generating one on the fly, you don't
>>>put subpackets into the key that cannot be determined next time you use the
>>>same source to get the key. A flag in a subpacket indicating where the key
>>>comes from might be useful, though.
>>
>>This is a good point, I'll have to think about it.  I'm still not
>>sure that covering this material with key fingerprints and keyids is
>>the right thing to do.  What would the security threats be from being
>>able to bring a key back to life with the same fingerprint and keyid,
>>but without any signatures on it being valid?
> 
> 
> My original idea with subpackets was that they would be part of the
> fingerprint, and changing a subpacket was akin to making a whole new
> key as the fingerprint and key ID (though not the key material) would
> change.  I see some advantages of what you are discussing.  It would
> (somewhat) allow someone to violate a hard expiration date on their
> key: make the key, get signatures, and then when the key expires, just
> remake the key.  Essentially you can buy an extension on your "hard"
> expiration time at the cost of losing all of your signatures.
> 
> The thing is, I can't really decide if that is a threat or a
> feature...

You can already do this by signing the new version of the key with the 
old version of the key - same keypair, so messages to either will work, 
and signatures made by either key will still check - but different IDs 
and signatures on the keys.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

Date: Thu, 22 Sep 2005 21:57:13 +0200
To: David Shaw <[email-masked]>, [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Thu, Sep 22, 2005 at 03:36:36PM -0400, David Shaw wrote:

> Well yes, but someone can generate a key with an arbitrary ID today.
> Even forgetting the DEADBEEF games that are possible with v3 RSA keys,
> there is a program out there that generates v4 DSA keys over and over
> until the requested (short) key ID comes up.

As I understand, that's precisely thre reason why long IDs are used as key
pointers. It would take 4 million times longer to generate one of those.
Still possible for a determined, well-funded adversary, but expensive. In
case of v3 keys, it was trivial. In case of the proposed hash function
choice, it will be still expensive, but substantially cheaper (even if
nothing is broken) than with current v4 keys, and in a "brittle" way: a
breaktrough in one case breaks the whole thing.

I think that SHA1 for key identification and fingerprinting is still a
comfortable overkill.

-- 
Daniel

Date: Thu, 22 Sep 2005 15:36:36 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Thu, Sep 22, 2005 at 09:18:36PM +0200, Daniel A. Nagy wrote:
> 
> On Thu, Sep 22, 2005 at 09:00:00PM +0200, Konrad Rosenbaum wrote:
> 
> > Let's say MDX is broken by some genius.
> 
> Remember, that the key ID is the last 8 (or four) byes of the fingerprint.
> If MDX is broken, one can generatet a key with an arbitrary ID.

Well yes, but someone can generate a key with an arbitrary ID today.
Even forgetting the DEADBEEF games that are possible with v3 RSA keys,
there is a program out there that generates v4 DSA keys over and over
until the requested (short) key ID comes up.

David

Date: Thu, 22 Sep 2005 21:18:36 +0200
To: [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Thu, Sep 22, 2005 at 09:00:00PM +0200, Konrad Rosenbaum wrote:

> Let's say MDX is broken by some genius.

Remember, that the key ID is the last 8 (or four) byes of the fingerprint.
If MDX is broken, one can generatet a key with an arbitrary ID.

-- 
Daniel

Date: Thu, 22 Sep 2005 15:06:48 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Problems with v4 key packet format
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Thu, Sep 22, 2005 at 08:47:05PM +0200, Konrad Rosenbaum wrote:
> On Wednesday 21 September 2005 23:26, Hal Finney wrote:
> > This is a good point, I'll have to think about it.  I'm still not
> > sure that covering this material with key fingerprints and keyids is
> > the right thing to do.  What would the security threats be from being
> > able to bring a key back to life with the same fingerprint and keyid,
> > but without any signatures on it being valid?
> 
> It becomes a threat once you get hold of the private key (through some 
> accident, a data leak, whatever) because then you can also issue new 
> self-signatures.
> 
> I see two possibilities to limit the damage: 
> 
> a) changing the expiration also changes the fingerprint, so the key does no 
> longer match whatever users have in their keyring and would basically be a 
> new key. 
> 
> b) changing the expiration breaks ALL signatures (not only self-sig) on the 
> key. (Actually b must be implemented as well, when a is implemented.)

If I understand what Hal was proposing, then b is already true.
Self-sigs aren't treated any differently than any other certification
signature.

> On the other hand: expiration dates are a very weak measure against key 
> abuse (they only limit the damage), un-revocable revocation sigs seem much 
> more effective to me.

True, but an unrevocable revocation signature can be stripped off the
key, so it becomes a key distribution problem.  Expiration dates are
naturally carried along with the key.

David

From: Konrad Rosenbaum <[email-masked]>
To: [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
Date: Thu, 22 Sep 2005 21:00:00 +0200
Sender: [email-masked]

--nextPart1493410.qBePzIRu3u
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On Wednesday 21 September 2005 23:00, Daniel A. Nagy wrote:
> As before, I would like to express my concerns about allowing a choice of
> hash algorithms. Here's some detail:
>
> A complete break (feasible reversal) of ANY ONE of the supported hash
> algorithms would allow generating keys with arbitrary long key IDs,
> possibly colliding with an attacked key. This was a major problem with v3
> and v4 was a giant step in the right direction. This would be a small
> step backwards.

I don't see how this attack would work.

Let's say MDX is broken by some genius.

=46irst the trivial case:=20
Alices Key A uses MDX as its fingerprint algorithm. The fingerprint looks=20
like: 99:AB 12 34 56 78 90 CD EF...
Mallory can now generate an arbitrary key M, that has the same algorithm an=
d=20
fingerprint.

Now the less trivial:
Bobs key B uses MDY (which was not broken). Fingerprint: A0:12 34 56 78...
Mallory could attempt to create a key M2 which has the same hash value usin=
g=20
MDY as Bobs key using MDX, but the fingerprint would still be different:=20
99:12 34 56 78...

I don't see any way for Mallory to compromise Bobs key without changing the=
=20
first byte of the fingerprint. So allowing different algorithms AND=20
including their ID in the fingerprint would in my opinion be a good measure=
=20
to limit the damage (only Alices key becomes ambiguous, not Bobs) in case=20
of a broken algorithm.

	Konrad

--nextPart1493410.qBePzIRu3u
Content-Type: application/pgp-signature

--nextPart1493410.qBePzIRu3u--

From: Konrad Rosenbaum <[email-masked]>
To: [email-masked]
Subject: Re: Problems with v4 key packet format
Date: Thu, 22 Sep 2005 20:47:05 +0200
Sender: [email-masked]

--nextPart1822501.mXWWIfq2zu
Content-Type: text/plain;
  charset="iso-8859-15"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On Wednesday 21 September 2005 23:26, Hal Finney wrote:
> This is a good point, I'll have to think about it.  I'm still not
> sure that covering this material with key fingerprints and keyids is
> the right thing to do.  What would the security threats be from being
> able to bring a key back to life with the same fingerprint and keyid,
> but without any signatures on it being valid?

It becomes a threat once you get hold of the private key (through some=20
accident, a data leak, whatever) because then you can also issue new=20
self-signatures.

I see two possibilities to limit the damage:=20

a) changing the expiration also changes the fingerprint, so the key does no=
=20
longer match whatever users have in their keyring and would basically be a=
=20
new key.=20

b) changing the expiration breaks ALL signatures (not only self-sig) on the=
=20
key. (Actually b must be implemented as well, when a is implemented.)

On the other hand: expiration dates are a very weak measure against key=20
abuse (they only limit the damage), un-revocable revocation sigs seem much=
=20
more effective to me.

	Konrad

--nextPart1822501.mXWWIfq2zu
Content-Type: application/pgp-signature

--nextPart1822501.mXWWIfq2zu--

Date: Thu, 22 Sep 2005 20:20:29 +0200
To: [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Thu, Sep 22, 2005 at 09:51:08AM -0700, "Hal Finney" wrote:

> These kinds of stories are often used to motivate cryptographic
> constructions, but the real world generally doesn't work that way.
> An infiltrator does not need cryptographic proof of his information
> about who is in the conspiracy!  After all, he doesn't have any such
> proof in the physical world, yet infiltrators, informants and spies have
> long been used as valuable sources of information.

I don't fully agree. Obviously, I wrote the story about the conspiracy and
the infiltrator with tongue firmly embedded in cheek. That's a long-standing
tradition in the crypto community and I certainly enjoy it. But
nevertheless, in many cases the presented scenario is precisely what
happens, just there's a lot less pathos surrounding it:

The overwhelming majority of "goverment agents" "infiltrating"
"conspiracies" are not politically motivated counter-intetlligence
operations but tax audits. A tax auditor pretends to be a customer and buys
someting. He sure as hell needs a rock-solid third-party proof to crack down
on you if you fail to report that income.

Now, what is taxed and what is not (by law!) depends on what is easy to tax
and what is hard to tax. If something is easy to tax, laws are passed and it
gets taxed. If something is hard to tax, if it's necessary for the functioning
of the society, it is not taxed, if it's not necessary, then it's outlawed.

Right now, e-commerce falls into the hard-to-tax-but-necessary category, but
the arms race is on. I'd certainly like it to stay the way it is.

While commerce is the single biggest user of crypto, there are other uses,
which we cannot even imagine. I don't have any reason to doubt that the
activist who wrote me about the missing feature in PGP could really use it.

Since ePointSystem is first and foremost a financial cryptography
consultancy, the first application on my mind was deniable invoicing. It's a
fair choice: either you use undeniable invoices, pay your taxes and resolve
your disputes in court relying on government enforcement, or you use
deniable invoices, don't pay taxes, and rely solely on reputational
self-regulation. I am pretty sure that most e-commerce will get taxed like
everything else, as soon as governments sort out their jurisdictional
problems. Having working deniable invoices would be a powerful argument in
the ensuing debate over taxation policies.

> I admit to a fondness for fancy crypto and it would be fun to see some
> form of deniable authentication in OpenPGP, but realistically it is not
> going to meet our customers' needs.

How do you know? In my experience, predicting what people will use your
product for is one of the most difficult tasks an engineer or a scientist
faces. People are amazingly inventive.

>  If we do want to pursue it, there
> are a number of technologies, like the DH shared keys you describe,
> the signed ESK packets Vedaal mentioned, or ring signatures and other
> variants of Chaum's designated-confirmer signatures.

All of which have slightly different characteristics and are therefore
optimal solutions for slightly different problems. In all cases, however,
interoperability is a major boon, and thus it's ITEF's business to provide
for it, isn't it?

DH shared keys and signed ESK packets are both very easy to incorporate into
the OpenPGP framework, and if we do it early on, we can hope that different
implementations will interoperate right away.

-- 
Daniel

To: [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
Date: Thu, 22 Sep 2005 09:51:08 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Daniel Nagy writes:
> Imagine, that a conspiracy expects to be infiltrated. They send encrypted
> messages back and forth but they have a dilemma: to sign or not to sign? If
> they do sign, the infiltrator will have damning evidence on his hands and
> the bad guys will be able to crack down on the conspirators. If they don't
> sign, the infiltrator will be able to forge messages and thus seriously
> interfere with the activities of the group (e.g. call off action in the name
> of the ringleader, etc.).

These kinds of stories are often used to motivate cryptographic
constructions, but the real world generally doesn't work that way.
An infiltrator does not need cryptographic proof of his information
about who is in the conspiracy!  After all, he doesn't have any such
proof in the physical world, yet infiltrators, informants and spies have
long been used as valuable sources of information.

I admit to a fondness for fancy crypto and it would be fun to see some
form of deniable authentication in OpenPGP, but realistically it is not
going to meet our customers' needs.  If we do want to pursue it, there
are a number of technologies, like the DH shared keys you describe,
the signed ESK packets Vedaal mentioned, or ring signatures and other
variants of Chaum's designated-confirmer signatures.

Hal Finney

Date: Thu, 22 Sep 2005 08:50:34 -0700
To: <[email-masked]>
Cc: 
Subject: Re: Plausible deniability (a feature to think about)
From: <[email-masked]>
Sender: [email-masked]

On Thu, 22 Sep 2005 07:52:08 -0700 "Daniel A. Nagy" 
<[email-masked]> wrote:

>Simply? How exactly do you suggest to share a common key so that 
>the parties
>can be reassured that it's their shared secret?

>> many variations of this are possible;
>> 
>> new signing subkeys, set to expire within hours of the message 
>> time,
>
>Again, how do you share them?

the sender generates the new keypair, and sends it signed and 
encrypted, to the receiver

it is neither more nor less trustworthy than the primary keys of 
the sender and receiver,
which could also conceivably be given to other parties,

>> split key systems with shares set to one, and split to only the 
>> receiver and sender keys, etc.
>
>I haven't seen split key implementations either in OpenPGP 
>compliant tools,
>though I know they are mentioned in RFC2440.

pgp has had them implemented since 6.x

a new type of pgp signature to deal with this issue was proposed by 

Ian Brown and Adam Back,
http://www.cs.ucl.ac.uk/staff/I.Brown/nts.htm

where the session key is signed, not the plaintext

(don't know if people want to explore this now, or wait until after 
the rfc 2440 is finalized, and save it for a further update,

i would welcome this useful type of signature, 
as i imagine many users would )

vedaal
>-- 
>Daniel

Concerned about your privacy? Follow this link to get
secure FREE email: http://www.hushmail.com/?l=2

Free, ultra-private instant messaging with Hush Messenger
http://www.hushmail.com/services-messenger?l=434

Promote security and make money with the Hushmail Affiliate Program: 
http://www.hushmail.com/about-affiliate?l=427

Date: Thu, 22 Sep 2005 16:52:08 +0200
To: [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Thu, Sep 22, 2005 at 07:21:39AM -0700, [email-masked] wrote:

> this can easily be accomplished now, 
> within the existing standard, and existing implementations:
> 
> any two correspondents,
> can simply make a third keypair, with a third name,
> and each have the public and private signing and encrypting keys,

Simply? How exactly do you suggest to share a common key so that the parties
can be reassured that it's their shared secret?
 
> anything signed with the third key, authenticates only to the 
> correspondents
> where the receiver knows that the sender signed it,
> but cannot be proved to any third party, 
> other than the fact that any possessor of the signing key, signed 
> it.

Actually, once you share some secret, you don't need to use asymmetric
crypto anymore. A message with MDC encrypted with a shared symmetric key has
all the necessary reassurances. Sharing the secret is the tricky part.

> many variations of this are possible;
> 
> new signing subkeys, set to expire within hours of the message 
> time,

Again, how do you share them?

> split key systems with shares set to one, and split to only the 
> receiver and sender keys, etc.

I haven't seen split key implementations either in OpenPGP compliant tools,
though I know they are mentioned in RFC2440.

-- 
Daniel

Date: Thu, 22 Sep 2005 16:45:19 +0200
To: [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Thu, Sep 22, 2005 at 06:28:33AM -0500, Brian G. Peterson wrote:

> We were most concerned with chain of evidence and verifiability, not plausible 
> deniability.

Different people have different concerns, I suppose.

> In the real world, most human rights organizations already have 
> extensive methods of verifying information that is provided to them, and 
> informers have elaborate methods of communicating that information, that only 
> rarely involves electronic communication, encrypted or otherwise, becasue of 
> the danger of interception.

The "real world" keeps changing. If you can make something cheaper, more
reliable, simpler, etc., why stop short of doing so?

Also, I am not convinced that what you're stating is universally true.
AFAIK, PGP has been quite popular with activists since its very first public
releases.

> In a country (like China) where much/most 
> private use of encryption is disallowed anyway, sending *any* encrypted 
> message is a risk that most human rights workers and informers will not take.

The world is not black and white. "Countries like that"  are not the only
places where basic human rights are under assault, and not even necessarily
by the government. There's a large number of considerably
less-than-democratic  governments that for one reason or another must
maintain  a democratic facade. And again, the government is not necessarily
the threat you're caring about.

> I don't think that OpenPGP needs a new shared-secret method of communication, 
> or that the spec needs another wrinkle for implementors to chew on.

It would be obviously optional, and as outlined in the first email of the
thread, not much of a trouble to design or implement.

Bests,

-- 
Daniel

Date: Thu, 22 Sep 2005 07:21:39 -0700
To: <[email-masked]>
Cc: 
Subject: Re: Plausible deniability (a feature to think about)
From: <[email-masked]>
Sender: [email-masked]

On Wed, 21 Sep 2005 21:29:55 -0700 "Daniel A. Nagy" 
<[email-masked]> wrote:

> Now, 
>the
>receiving party can be sure that it was composed by the sender, 
>but has no
>means of proving it to a third party. The sender can plausibly 
>deny
>authorship, claiming that the receiver has forged it using his 
>private key
>and the sender's public key.

>Has anybody ever bothered implementing (or even designing an 
>implementation
>of) this in an OpenPGP-friendly manner? 

this can easily be accomplished now, 
within the existing standard, and existing implementations:

any two correspondents,
can simply make a third keypair, with a third name,
and each have the public and private signing and encrypting keys,

anything signed with the third key, authenticates only to the 
correspondents
where the receiver knows that the sender signed it,
but cannot be proved to any third party, 
other than the fact that any possessor of the signing key, signed 
it.

many variations of this are possible;

new signing subkeys, set to expire within hours of the message 
time,

split key systems with shares set to one, and split to only the 
receiver and sender keys, etc.

vedaal

Concerned about your privacy? Follow this link to get
secure FREE email: http://www.hushmail.com/?l=2

Free, ultra-private instant messaging with Hush Messenger
http://www.hushmail.com/services-messenger?l=434

Promote security and make money with the Hushmail Affiliate Program: 
http://www.hushmail.com/about-affiliate?l=427

Date: Thu, 22 Sep 2005 15:56:34 +0200
To: [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Thu, Sep 22, 2005 at 05:43:57PM +1200, Peter Gutmann wrote:
> [email-masked] (Daniel A. Nagy) writes:
> 
> >Now, there exists a cryptographic solution for this problem, moreover,
> >RFC2440 even hints that it might be implemented in OpenPGP, though I have
> >never seen it used: X9.42 Diffie-Hellman key agreement (see also RFC2630,
> >RFC2631 and RFC2633).
> 
> X9.42 was only added to S/MIME for political reasons.  AFAIK only one
> implementation ever supported it, and that was the USG-funded reference
> implementation that was required to support it.  In addition, MS supported a
> read-only implementation just so they couldn't be accused of not supporting
> it.

What political reasons? And why is there a reserved ID in OpenPGP?

> (I remember having a conversation with a rather baffled security application
>  developer who wanted to see X9.42 in an S/MIME toolkit and just couldn't
>  understand that although the spec had it as a MUST requirement, all the
>  implementors knew that you should ignore it).

X9.42 may be flawed (is it?), but DH key agreement is one of the strongest
primitives in asymmetric cryptography.

-- 
Daniel

Date: Sat, 27 Aug 2005 17:24:00 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: "Daniel A. Nagy" <[email-masked]>
Cc: [email-masked]
Subject: Re: Signature types
Sender: [email-masked]

Daniel A. Nagy wrote:
> It's actually RFC1991 that got me wondering:
> 
>      <40> - time stamping ("I saw this document") (*)
>   ...                                          Type <40> is intended to
>   be a signature of a signature, as a notary seal on a signed document.
> 
> Now, this is contradictory. If a signature does not have any cryptograpic
> binding (except the indirect one through the other signature) to the
> document, it cannot be used to assert the integrity thereof.
> 
> Someone with the public key of the notary cannot verify this claim. Also, it
> makes a lot of sense to certify documents that have not been signed.

[snip]

>>        This signature is a signature over some other OpenPGP
>>	signature packet(s). It is analogous to a notary seal on the
>>	signed data.
> 
> 
> Except that if it's a signature on the signature, then it cannot be
> analogous to a notary seal on the signed data (see above).

One of the difficulties that may be occuring here
is that the word 'notary' has different meanings
in civil and common law contexts.  In the former,
a notary is likely to be interested in the content
of the signed data;  whereas in the latter, the
notary is normally only interested in the quality
of the signature, and not the data.

We had a long threat on this about a year ago, and
I believe some changes were made disambiguate ..

I think the context that the Draft uses the word
notary is more towards the common law case of just
the signature and not the data that is signed.

iang

From: "Brian G. Peterson" <[email-masked]>
To: [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
Date: Thu, 22 Sep 2005 06:28:33 -0500
Sender: [email-masked]

On Wednesday 21 September 2005 11:29 pm, Daniel A. Nagy wrote:
> I just got a message from a human rights activist, who pointed out a
> shortcoming of PGP for -- for the lack of a better word -- paranoid
> conspirators.
>
> Imagine, that a conspiracy expects to be infiltrated. They send encrypted
> messages back and forth but they have a dilemma: to sign or not to sign? If
> they do sign, the infiltrator will have damning evidence on his hands and
> the bad guys will be able to crack down on the conspirators. If they don't
> sign, the infiltrator will be able to forge messages and thus seriously
> interfere with the activities of the group (e.g. call off action in the
> name of the ringleader, etc.).
<...>
>The sender can plausibly deny authorship, claiming that the receiver has
>forged it using his private key and the sender's public key.

Interesting thought experiement.

I led the development team of the solution used by the CryptoRights Foundation
http://www.cryptorights.org/
our solution consisted of management tools, user interfaces, translations, and 
other niceties around a gnupg based engine.

We were most concerned with chain of evidence and verifiability, not plausible 
deniability.  In the real world, most human rights organizations already have 
extensive methods of verifying information that is provided to them, and 
informers have elaborate methods of communicating that information, that only 
rarely involves electronic communication, encrypted or otherwise, becasue of 
the danger of interception.  In a country (like China) where much/most 
private use of encryption is disallowed anyway, sending *any* encrypted 
message is a risk that most human rights workers and informers will not take.

I don't think that OpenPGP needs a new shared-secret method of communication, 
or that the spec needs another wrinkle for implementors to chew on.

Regards,

  - Brian

From: [email-masked] (Peter Gutmann)
To: [email-masked], [email-masked]
Subject: Re: Plausible deniability (a feature to think about)
Date: Thu, 22 Sep 2005 17:43:57 +1200
Sender: [email-masked]

[email-masked] (Daniel A. Nagy) writes:

>Now, there exists a cryptographic solution for this problem, moreover,
>RFC2440 even hints that it might be implemented in OpenPGP, though I have
>never seen it used: X9.42 Diffie-Hellman key agreement (see also RFC2630,
>RFC2631 and RFC2633).

X9.42 was only added to S/MIME for political reasons.  AFAIK only one
implementation ever supported it, and that was the USG-funded reference
implementation that was required to support it.  In addition, MS supported a
read-only implementation just so they couldn't be accused of not supporting
it.

(I remember having a conversation with a rather baffled security application
 developer who wanted to see X9.42 in an S/MIME toolkit and just couldn't
 understand that although the spec had it as a MUST requirement, all the
 implementors knew that you should ignore it).

>Has anybody ever bothered implementing (or even designing an implementation
>of) this in an OpenPGP-friendly manner?

See above.

Peter.

Date: Thu, 22 Sep 2005 06:29:55 +0200
To: [email-masked]
Subject: Plausible deniability (a feature to think about)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

I just got a message from a human rights activist, who pointed out a
shortcoming of PGP for -- for the lack of a better word -- paranoid
conspirators.

Imagine, that a conspiracy expects to be infiltrated. They send encrypted
messages back and forth but they have a dilemma: to sign or not to sign? If
they do sign, the infiltrator will have damning evidence on his hands and
the bad guys will be able to crack down on the conspirators. If they don't
sign, the infiltrator will be able to forge messages and thus seriously
interfere with the activities of the group (e.g. call off action in the name
of the ringleader, etc.).

Now, there exists a cryptographic solution for this problem, moreover,
RFC2440 even hints that it might be implemented in OpenPGP, though I have never
seen it used: X9.42 Diffie-Hellman key agreement (see also RFC2630, RFC2631
and RFC2633).

In addition to signature and encryption keys, one can have a DH subkey
which may be used to create a (salted) two-party shared secret session key
and send an MDC-protected encnrypted message using that key. Now, the
receiving party can be sure that it was composed by the sender, but has no
means of proving it to a third party. The sender can plausibly deny
authorship, claiming that the receiver has forged it using his private key
and the sender's public key.

Has anybody ever bothered implementing (or even designing an implementation
of) this in an OpenPGP-friendly manner? Seems like it's just a matter of a
third ESK type (tentatively called DH-ESK) and a clear definiton of DH keys
(for which we have reserved identifier 21), which, I guess, should be
identical to ElGamal keys, though it is instrumental that the entie
conspiracy used the same modulus and generator element.

DH-ESK should be very similar to SK-ESK with a salted (but not iterated)
S2K, except for the additional 8-octet IDs of the sender's and the
recipient's public DH keys. The usual traffic-analysis thwarting techniques
of leaving one or both of them blank obviously apply. Allowing for an
ephemeral sender PK to be included is pointless, as that would bring us back
to ElGamal encryption (well, almost), for which there is already a PK-ESK.

If the MDC verification works out on the receiving end, the implementation
should show the message as being "sealed" by the sender on the date from the
literal packet, in addition to decrypting it, much like it handles
signed+encrypted messages.

It's so easy and straightforward that I'd dare to propose it for 2440bis.

-- 
Daniel

Date: Wed, 21 Sep 2005 20:47:58 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Problems with v4 key packet format
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Thu, Sep 22, 2005 at 01:03:20AM +0200, Daniel A. Nagy wrote:
> 
> On Wed, Sep 21, 2005 at 05:55:03PM -0400, David Shaw wrote:
> 
> > The thing is, I can't really decide if that is a threat or a
> > feature...
> 
> In such cases isn't the best policy to let the users and/or implementers decide
> for themselves? How about having hashed and unhashed subpackets just like in
> v4 signatures, where all are subject to signatures but only the hashed ones
> are included in the fingerprint?

I think this might cause some serious user confusion.  With both types
of subpackets, plus the existing v4 signature subpackets, we would
have three different ways to specify expiration, each with a slightly
different meaning:

key-subpacket-in-fingerprint:

    hard expiration date.  All other expiration dates can only be
    extended to this point.  Changing it changes the fingerprint and
    key ID.

key-subpacket-in-signature:

    soft expiration date.  Changing it invalidates all signatures, but
    does not change the fingerprint/key ID.

regular-old-selfsig:

    very soft expiration date.  Can be changed at any time with no
    impact on anything but the expiration date.

Then we have various combinations of the above...

David

Date: Wed, 21 Sep 2005 16:24:22 -0700
To: <[email-masked]>
Cc: 
Subject: Re: Problems with v4 key packet format
From: <[email-masked]>
Sender: [email-masked]

On Wed, 21 Sep 2005 14:55:03 -0700 David Shaw 
<[email-masked]> wrote:
>  It 
>would
>(somewhat) allow someone to violate a hard expiration date on 
>their
>key: make the key, get signatures, and then when the key expires, 
>just
>remake the key.  Essentially you can buy an extension on your 
>"hard"
>expiration time at the cost of losing all of your signatures.
>
>The thing is, I can't really decide if that is a threat or a
>feature...

to the unsuspecting users who thought that an 'expired' key
is *really* expired,
it would be confusing to have someone claim,

"i 'revived' it,
it was dead, but it's better now,
just re-sign it and trust it again ..."

so,
while not really a threat, and not really a feature,
it potentially could add to the confusion of the key trust issue,
rather than simplify it...

vedaal

Concerned about your privacy? Follow this link to get
secure FREE email: http://www.hushmail.com/?l=2

Free, ultra-private instant messaging with Hush Messenger
http://www.hushmail.com/services-messenger?l=434

Promote security and make money with the Hushmail Affiliate Program: 
http://www.hushmail.com/about-affiliate?l=427

Date: Thu, 22 Sep 2005 01:03:20 +0200
To: [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 21, 2005 at 05:55:03PM -0400, David Shaw wrote:

> The thing is, I can't really decide if that is a threat or a
> feature...

In such cases isn't the best policy to let the users and/or implementers decide
for themselves? How about having hashed and unhashed subpackets just like in
v4 signatures, where all are subject to signatures but only the hashed ones
are included in the fingerprint?

-- 
Daniel

Date: Thu, 22 Sep 2005 01:00:43 +0200
To: Hal Finney <[email-masked]>, [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 21, 2005 at 02:26:13PM -0700, "Hal Finney" wrote:

> > Careful! If this information is not part of the fingerprint/keyID it can
> > still be changed by updating the self-signature, no matter whether it's in
> > thte signature packet or in the key packet.
> 
> Not exactly, the self-signature would not (by convention) override the
> information in the key subpackets.  So just issuing a new self-signature
> would not help.

That's not what I meant. If the self-signanture is the only integrity
protection measure, then someone in possession of the private part of the
key can alter the expiration date in the key packet just as he can alter it
in the signature subpacket. If it's hashed with the key ID, changing it
would also change the key ID, ergo resulting in a different key.
 
> What could happen is that someone who got hold of the private material
> could create a new key packet with the same keyid/fingerprint but with
> a different expiration date.  But(!) the new key would not inherit the
> signatures on the old key.

That's correct.

>  That is what I was thinking of as important.
> It would not be valid, it would not be part of the Web of Trust.
> The idea is that key signatures would cover all of the subpackets,
> even though fingerprints do not.

And what about keys that are not part of WoT? In the present standard, I can
trust a key not only because someone I trust has signed it, but also because
I know the fingerprint. Should we break that?

> This is a good point, I'll have to think about it.  I'm still not
> sure that covering this material with key fingerprints and keyids is
> the right thing to do.

Me neither, but the more I think about it, the more I am leaning towards
giving the choice to the user by having hashed and unhashed subpackets, both
of which are signed, but only the hashed ones being included in the
fingerprint. But I'll have to think more about it myself.

> What would the security threats be from being
> able to bring a key back to life with the same fingerprint and keyid,
> but without any signatures on it being valid?

Well, it depends on the applicatiton and the user's trust model. What I like
most about OpenPGP is the flexibility of the trust model. Ignoring the WoT
is certainly an option I would like to have.

-- 
Daniel

Date: Wed, 21 Sep 2005 17:55:03 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Problems with v4 key packet format
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Wed, Sep 21, 2005 at 02:26:13PM -0700, "Hal Finney" wrote:

> > If you're importing a foreign key or generating one on the fly, you don't
> > put subpackets into the key that cannot be determined next time you use the
> > same source to get the key. A flag in a subpacket indicating where the key
> > comes from might be useful, though.
> 
> This is a good point, I'll have to think about it.  I'm still not
> sure that covering this material with key fingerprints and keyids is
> the right thing to do.  What would the security threats be from being
> able to bring a key back to life with the same fingerprint and keyid,
> but without any signatures on it being valid?

My original idea with subpackets was that they would be part of the
fingerprint, and changing a subpacket was akin to making a whole new
key as the fingerprint and key ID (though not the key material) would
change.  I see some advantages of what you are discussing.  It would
(somewhat) allow someone to violate a hard expiration date on their
key: make the key, get signatures, and then when the key expires, just
remake the key.  Essentially you can buy an extension on your "hard"
expiration time at the cost of losing all of your signatures.

The thing is, I can't really decide if that is a threat or a
feature...

David

To: [email-masked]
Subject: Re: Problems with v4 key packet format
Date: Wed, 21 Sep 2005 14:26:13 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Daniel Nagy writes:
> On Wed, Sep 21, 2005 at 09:52:33AM -0700, "Hal Finney" wrote:
> > I would like to see immutable material put there.  One thing that bothers
> > me in the current V4 is that the key's expiration date can be changed by
> > updating the self-signature.  Suppose your key has expired and you don't
> > use it any more.  As a result perhaps you don't protect it that well.
> > If someone gets hold of the private part, they can issue a new self-sig
> > with a new expiration date and bring this dead key back to life.  It would
> > be better if a dead key would stay dead.  Expiration date and creation
> > date would be better placed in the key packet, IMO (as they were with
> > V3 keys).
>
> Careful! If this information is not part of the fingerprint/keyID it can
> still be changed by updating the self-signature, no matter whether it's in
> thte signature packet or in the key packet.

Not exactly, the self-signature would not (by convention) override the
information in the key subpackets.  So just issuing a new self-signature
would not help.

What could happen is that someone who got hold of the private material
could create a new key packet with the same keyid/fingerprint but with
a different expiration date.  But(!) the new key would not inherit the
signatures on the old key.  That is what I was thinking of as important.
It would not be valid, it would not be part of the Web of Trust.
The idea is that key signatures would cover all of the subpackets,
even though fingerprints do not.

> David's idea with sub-packets should be implemented in such a way that
> hashed sub-packets are part of the fingerprint. Maybe, we don't even need
> unhashed sub-packets.
>
> If you're importing a foreign key or generating one on the fly, you don't
> put subpackets into the key that cannot be determined next time you use the
> same source to get the key. A flag in a subpacket indicating where the key
> comes from might be useful, though.

This is a good point, I'll have to think about it.  I'm still not
sure that covering this material with key fingerprints and keyids is
the right thing to do.  What would the security threats be from being
able to bring a key back to life with the same fingerprint and keyid,
but without any signatures on it being valid?

Hal Finney

Date: Wed, 21 Sep 2005 23:13:16 +0200
To: [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

Sorry, something being "pareto complete for a particular purpose" is an
abuse of Ian's definition. SHA1 is not pareto-complete, but still
pareto-secure if collision-resistance is not an issue.

There is a number of good papers on truncating hash functions for message
authentication and there's a general consensus that at least 80 bits or
half of the bits (whichever is more) of a full-stregth hash function are
sufficient for medium-term security.

For long term, I would upgrade that to 128 bits, and taking into account
known and unforseen weeknesses of hash functions, using 160 bits should
satisfy even the most paranoid.

-- 
Daniel

Date: Wed, 21 Sep 2005 23:00:15 +0200
To: [email-masked]
Subject: Re: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

As before, I would like to express my concerns about allowing a choice of
hash algorithms. Here's some detail:

A complete break (feasible reversal) of ANY ONE of the supported hash
algorithms would allow generating keys with arbitrary long key IDs, possibly
colliding with an attacked key. This was a major problem with v3 and v4 was
a giant step in the right direction. This would be a small step backwards.

For MDC purposes, it's even worse.

Since collisions are of no concern in the case of the key fingerprint and
MDC, I would just stick to SHA1 for the time being.

Precisely because of this, assuming a full-strength hash function, half of
the hash suffices. This is just a remark to the length requirement. 128 bit
fingerprints are secure for the forseable future, but using the 160 bit SHA1
(with all its problems), is a reasonable overdesign taking into account what
we don't know.

Collision resistance is important for signatures and even more so for
certifications, but it is of no concern whatsoever for fingerprints and MDC.

Where RFC2440 has SHA1 hardwired into the spec, it is completely safe and
even somewhat of an overkill. Using Ian's terminology, it's still pareto-secure
and even pareto-complete. No alternative would provide more security.

Signatures and certifications are a completely different issue altogether.

-- 
Daniel

Date: Wed, 21 Sep 2005 16:22:08 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Some thoughts on a v5 key and why it shouldn't be a mess (fwd)
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

This is my original mail about V5 and keys with subpackets.  Since V5
is being discussed now, it seems reasonable to repost.

David

----- Forwarded message from David Shaw <[email-masked]> -----

Date: Mon, 21 Feb 2005 12:11:31 -0500
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Some thoughts on a v5 key and why it shouldn't be a mess
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc

I had around 10 hours in a car this weekend, which gave me a good bit
of time to think some more about the v5 key idea.

I don't see this as a "drop everything and do v5" suggestion.  It's
more of a "design v5 in 2005, because we need it a few years from
now".  Attacks only get better, and if we want to be able to shrug off
a future SHA-1 break like we were able to shrug off the MD5 break, we
need to start the process.  While this is prompted by the SHA-1
problems, note that NIST was already replacing SHA-1 with the SHA-2
family by 2010 for size reasons.  Even if the recent SHA-1 problems
hadn't happened, I'd still think it was time to start designing a v5
key.

I don't think there needs to be a lot of fear over a version number
bump.  To be sure, the change from v3 to v4 was disruptive.  In one
step, the packet format, the default symmetric cipher, and the
public-key algorithm was changed.  Even the concept of a key was
altered by adding subkeys.  I'm not criticizing - the changes were
necessary for many reasons, but unfortunately they also split the user
base into "before" and "after", with interoperability problems between
the two groups.  In some (occasionally frustrating) corners, the
change hasn't even happened yet.

I don't see the change from v4 to v5 being nearly as disruptive as the
v3 to v4 change.  The straw proposal I'm putting forth here is an
incremental change over v4, large enough to be worth doing, small
enough that if the change is done carefully, it should be painless.
v4 and the proposed v5 can also quite happily co-exist without anyone
noticing or caring.  Note that I'm not talking about making a v5
signature at this point.

Here is a proposed packet format for a v5 key, interspersed with
comments.  Obviously, not every detail is given, but the general ideas
should be clear:

     - A one-octet version number (5).

     - A one-octet hash algorithm number.

This is an attempt to balance Jon's comments about 160 bits being all
that a human user can handle for a fingerprint, and the desire to not
be locked to SHA-1 in case of future trouble.  Essentially you set
this value to the fingerprint hash you want to use for this key.  The
value itself is hashed into the fingerprint (and signatures on the
key), so it cannot be changed once the key is generated.  Is is
possible for different v5 key fingerprints to be of different lengths.
A v5 fingerprint is written "algo - colon - data", like 2:12 34 56 78
9A BC DE F0 ...(etc).  The v5 keyid concept is the same as v4: the
keyid is the lower 32 or 64 bits of the fingerprint, however long it
may be.

There are some problems with this idea, not least that any
implementation that doesn't understand the hash algorithm won't be
able to use the key.  It may well be better to lock this value to
SHA-256 and be done with it.

     - A two-octet scalar octet count for the following subpacket
       data.  Note that this is the length in octets of all of the
       hashed subpackets; a pointer incremented by this number will
       skip over the subpackets.

     - Subpacket data.

Yes, v5 keys have subpackets.  It's a bit of future-proofing since it
is a lot easier to add a subpacket than it is to go to a v6 key
format.  Note that there are no "unhashed" subpackets here.  All
subpackets are hashed into the fingerprint, and therefore are fixed at
key generation time.  The subpacket numbers do not need to be the same
as signature subpackets, but the encoding format is the same, and the
critical bit has the same meaning here as it does for signatures.

Only one subpacket comes to mind at the moment, and that is:

      Expiration time
      (4 octet time field)

      The validity period limit of the key.  This is the number of
      seconds after the key creation time that the key must expire by.
      If this is not present or has a value of zero, the key has no
      hard expiration.

This gives a "hard" expiration time which cannot be extended, unlike
the current "soft" expiration in v4.  There were a number of
disagreements over the v4 soft expirations, and while it's an
interesting discussion, at the end of the day there are good reasons
to support both.  In practice, this key subpacket sets a hard limit on
the lifetime of a key, and any soft expirations can only affect the
lifetime of the key up to that hard point.  No hard expiration acts
just like v4.  Users can mix the two to give whatever semantics they
want.

     - A four-octet number denoting the time that the key was created.

This might be better as a subpacket, but then implementers would have
to deal with the case if it was missing.

     - A one-octet number denoting the public key algorithm of this
     key.

     - A series of multiprecision integers comprising the key
     material.

Same as v4.  There is no need to change MPIs around.  There are only
so many ways to store large numbers in a row.

The v5 secret keys, like the v4 secret keys, are the same as the
public key with the secret material appended.

An additional change, which is not part of the key packet format is
that v5 keys have AES as both their "last resort" and "must implement"
ciphers.  When encrypting to v4 and v5 keys together, the default
cipher is 3DES.  One way to look at this is that cipher preferences on
a v5 key have "AES, 3DES" implicitly at the end if not explicitly used
earlier.  When combined with the implicit "3DES" already at the end of
a v4 preference list, the right thing will happen automatically.  Note
that while AES is the "must" cipher for v5, implementations that
support v4 keys must also implement 3DES.

To make the transition from v4 to v5 as invisible as possible, I'd
suggest having read support for this in implementations for as long as
possible (say, 1 year) before allowing users to create these keys.
This gives time for upgrading (and there will be a certain amount of
upgrading for other reasons during that time as well, which the v5
keys can be included with), and for various other processes that
interact with OpenPGP like keyservers to be updated.

I also suggest that this not be a part of 2440bis.  The v5 discussions
will undoubtedly take a while, and delaying 2440bis for an unknown
(but probably long) period of time seems a shame.

Anyway, this is a starting point.  Please thow darts and make
suggestions.

David

----- End forwarded message -----

Date: Wed, 21 Sep 2005 16:19:21 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Problems with v4 key packet format
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Wed, Sep 21, 2005 at 09:56:38PM +0200, Daniel A. Nagy wrote:
> 
> On Wed, Sep 21, 2005 at 09:52:33AM -0700, "Hal Finney" wrote:
> 
> > > 3. Key fingerprint depends on data unrelated to the actual key (namely:
> > > creation date).
> > 
> > Yes, this has hurt our PGP implementation when dealing with foreign keys
> > such as X.509 certificates.  If we want to import a raw modulus+exponent
> > pair as a PGP key, and we want to know if we already have one on the
> > keyring, we can't easily compute a fingerprint and look for a match,
> > because creation date affects fingerprints.  I agree that fingerprints
> > should just be over the formatted key material.
> > 
> > > 4. More generally, creation time does not belong to the key packet.
> > >
> > > Because it is just an attribute of the key as any other, thus belonging to
> > > certificatiton signature sub-packets, rather than the key packet.
> > 
> > I like David's idea better to have some sub-packets in the V5 key.
> 
> Me too.
> 
> > I would like to see immutable material put there.  One thing that bothers
> > me in the current V4 is that the key's expiration date can be changed by
> > updating the self-signature.  Suppose your key has expired and you don't
> > use it any more.  As a result perhaps you don't protect it that well.
> > If someone gets hold of the private part, they can issue a new self-sig
> > with a new expiration date and bring this dead key back to life.  It would
> > be better if a dead key would stay dead.  Expiration date and creation
> > date would be better placed in the key packet, IMO (as they were with
> > V3 keys).
> 
> Careful! If this information is not part of the fingerprint/keyID it can
> still be changed by updating the self-signature, no matter whether it's in
> thte signature packet or in the key packet.
> 
> David's idea with sub-packets should be implemented in such a way that
> hashed sub-packets are part of the fingerprint. Maybe, we don't even need
> unhashed sub-packets.

There have been a number of mentions of the key-with-subpackets idea
recently, so I'll repost the mail where I first proposed the idea.  It
has many more details than I mentioned in this thread.

In short though, the subpackets are hashed into the fingerprint and
any certification signatures (including self signatures).  In my
proposal there are no unhashed subpackets.  In the case of expiration,
we would have two different ways to specify expiration.  The
expiration time hashed into the key is a hard expiration time that
cannot be extended.  The expiration time in the self-signature is a
soft expiration time that can be extended or changed whenever desired
- but only up to the hard limit given in the key itself.

David

Date: Wed, 21 Sep 2005 21:56:38 +0200
To: [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 21, 2005 at 09:52:33AM -0700, "Hal Finney" wrote:

> > 3. Key fingerprint depends on data unrelated to the actual key (namely:
> > creation date).
> 
> Yes, this has hurt our PGP implementation when dealing with foreign keys
> such as X.509 certificates.  If we want to import a raw modulus+exponent
> pair as a PGP key, and we want to know if we already have one on the
> keyring, we can't easily compute a fingerprint and look for a match,
> because creation date affects fingerprints.  I agree that fingerprints
> should just be over the formatted key material.
> 
> > 4. More generally, creation time does not belong to the key packet.
> >
> > Because it is just an attribute of the key as any other, thus belonging to
> > certificatiton signature sub-packets, rather than the key packet.
> 
> I like David's idea better to have some sub-packets in the V5 key.

Me too.

> I would like to see immutable material put there.  One thing that bothers
> me in the current V4 is that the key's expiration date can be changed by
> updating the self-signature.  Suppose your key has expired and you don't
> use it any more.  As a result perhaps you don't protect it that well.
> If someone gets hold of the private part, they can issue a new self-sig
> with a new expiration date and bring this dead key back to life.  It would
> be better if a dead key would stay dead.  Expiration date and creation
> date would be better placed in the key packet, IMO (as they were with
> V3 keys).

Careful! If this information is not part of the fingerprint/keyID it can
still be changed by updating the self-signature, no matter whether it's in
thte signature packet or in the key packet.

David's idea with sub-packets should be implemented in such a way that
hashed sub-packets are part of the fingerprint. Maybe, we don't even need
unhashed sub-packets.

If you're importing a foreign key or generating one on the fly, you don't
put subpackets into the key that cannot be determined next time you use the
same source to get the key. A flag in a subpacket indicating where the key
comes from might be useful, though.

-- 
Daniel

Date: Wed, 21 Sep 2005 21:49:13 +0200
To: [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 21, 2005 at 07:18:58PM +0200, Werner Koch wrote:

> The suggestion was that we put a hard-expiration into a v5 key packet
> but keep the existing soft-expiration in the self-signature.

I think, David's subpacket solution accomodates for this without being
overly restrictive. If you want to make sure your key stays dead after
expiration, you put a hashed expiration date subpacket into your key.

-- 
Daniel

To: [email-masked] ("Hal Finney")
Cc: [email-masked]
Subject: Re: Problems with v4 key packet format
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Wed, 21 Sep 2005 19:18:58 +0200
Sender: [email-masked]

On Wed, 21 Sep 2005 09:52:33 -0700 (PDT), "Hal Finney" said:

> be better if a dead key would stay dead.  Expiration date and creation
> date would be better placed in the key packet, IMO (as they were with
> V3 keys).

We discussed this issue a long time ago and came to the conclusion
that both kinds of exiration dates make a lot of sense.  Prolonging
the expiration time is something what quite some users are doing now
on a regular basis.  If nothing else it helps against a lost
passphrase.

The suggestion was that we put a hard-expiration into a v5 key packet
but keep the existing soft-expiration in the self-signature.

Salam-Shalom,

   Werner

To: [email-masked]
Subject: Re: Problems with v4 key packet format
Date: Wed, 21 Sep 2005 09:52:33 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Let me give my responses to Daniel's points about V4 key packets.

First I want to mention that Ian seemed to take a much larger view and
wanted to redesign the whole of the OpenPGP format.  V4 to V5 key packets
is only one small part of the spec.  No one is proposing to redo OpenPGP
from scratch here.

> 1. No cryptographic binding between the encrypted private key material and
> the public key material.
>
> This results in a serious security issue, by allowing an attacker to replace
> the public material thus compromising the private material with the first
> use in the signature. There are various stop-gap measures to deal with this
> attack, but the only sure protetction would be some MDC binding together the
> private and the public key material.

This is a very good point, and it is a little different from the previous
attacks.  If we had thought of it, we would have tried to fix it when
we added the checksum over the private key material.

The previous attack involved modifying some private key material and
causing the signature algorithm to fail.  In RSA keys, if you hack
just one of p or q and get it to do the signature using the Chinese
Remainder Theorem (CRT), the resulting value can leak the other of p or
q and therefore leak your private key.  To defend against this we added
a SHA-1 hash over the private material as a checksum.

Daniel proposes an extension to the attack where the private key
material is left alone and the public material (in the private key
packet) is modified.  I don't think this would do anything on RSA
keys, as the CRT based signature algorithm does not use the public
modulus or exponent.  However it would be effective against DSA keys.
The attacker could change p and q to be much smaller values, such that
discrete logs were feasible, then request a DSA signature using these
values, solve the discrete log and reveal x (the private value) mod q.
Do this a few times with different q's would reveal x.

Had we thought about this, we could easily have had the SHA-1 hash
cover the public as well as the private key material, but we didn't,
unfortunately.  Putting some size-based sanity checks in the DSA signature
code might be a good idea though.

I don't know if there are other variations on the attack that could also
be addressed for now with sanity checks.

> 2. No explicit count of MPIs constituting the key material (both public and
> private).
>
> This information can only be inferred from the algorithm specifier, meaning
> that any implementation that wants to perform key management must have some
> rudimentary knowledge about all public key algorithms. This, in turn,
> hampers forward-compatibility.

I am inclined to agree with David that there is not much point to being
able to parse a packet's details when we can't do anything useful with it.

> 3. Key fingerprint depends on data unrelated to the actual key (namely:
> creation date).
>
> This prevents solutions when signature keys are generated on the fly (e.g.
> directly from a passphrase), as the key creation (or, in this case, key
> registration) date is not available at the time of signing, thus making it
> impossible to put am unambiguous reference to the public key into the
> signature.

Yes, this has hurt our PGP implementation when dealing with foreign keys
such as X.509 certificates.  If we want to import a raw modulus+exponent
pair as a PGP key, and we want to know if we already have one on the
keyring, we can't easily compute a fingerprint and look for a match,
because creation date affects fingerprints.  I agree that fingerprints
should just be over the formatted key material.

> 4. More generally, creation time does not belong to the key packet.
>
> Because it is just an attribute of the key as any other, thus belonging to
> certificatiton signature sub-packets, rather than the key packet.

I like David's idea better to have some sub-packets in the V5 key.
I would like to see immutable material put there.  One thing that bothers
me in the current V4 is that the key's expiration date can be changed by
updating the self-signature.  Suppose your key has expired and you don't
use it any more.  As a result perhaps you don't protect it that well.
If someone gets hold of the private part, they can issue a new self-sig
with a new expiration date and bring this dead key back to life.  It would
be better if a dead key would stay dead.  Expiration date and creation
date would be better placed in the key packet, IMO (as they were with
V3 keys).

Hal Finney

Date: Wed, 21 Sep 2005 18:41:56 +0200
To: [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 21, 2005 at 08:56:19AM -0400, David Shaw wrote:

> You could also do what GnuPG does - if it doesn't know the algorithm
> it just reads the entire list of MPIs (or anything else in the packet)
> into an opaque buffer.  I suppose it could figure out the MPIs, but
> there seems to be little point since either way, the key is not usable
> without support for the algorithm.  I suppose if the implementation
> stored keys in a backend that needed to know the individual key
> parameters that would be different.

That's what I actually do. But I don't like it. From an OO perspective, it
makes certain abstractions less efficient.
 
> Some people want to include things in the key fingerprint and some
> don't.  There are good reasons for both, so I favor v5 keys with
> optional subpackets like v4 signatures.  Within reason, it's a "make
> everyone happy" solution.

Excellent idea! Maybe, we can use a common set of subpackets, where some
make sense only in signatures while others only in keys. There are too many
overlaps for warranting a separate design.

-- 
Daniels

Date: Wed, 21 Sep 2005 18:36:48 +0200
To: [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

Oh, one item that I forgot to include in my list:

Encrypted private key packets are superfluous, IMO. Internally, it can be up
to the implementation how it secures private keys (as it varies from
situation to situation what the requirements and environmental assumptions
are), while for interoperability, it's perfectly secure to export
unencrypted private key packets (and the auxiliary stuff) within an
MDC-protected encrypted data packet, with some ESK in front of it.

This way, designers and implementers would only need to worry only about the
security of one MDC-protected encrypted data packet format, instead of two,
slightly different ones.

The only capability that would be lost is exporting and importing private
keys without knowing the corresponding passphrases, but I can't imagine
legitimate uses for that anyway, while such an action may well be part of
some more sophisticated active attack.

-- 
Daniel

Date: Wed, 21 Sep 2005 09:36:37 -0700
From: Bill Frantz <[email-masked]>
Subject: Re: Bigger DSA keys
To: [email-masked]
Sender: [email-masked]

On 9/18/05, [email-masked] (Ben Laurie) wrote:

>
>Ian G wrote:
>> Numbers?
>
>I was going to provide them, but accurate numbers for DSA is difficult, 
>because it requires modifying the core code in OpenSSL (or some other 
>DSA generator), and I couldn't be bothered.
>
>One can get a feel for it with:
>
>time openssl gendh <number of bits>

I'm not sure, based on these numbers, that this benchmark procedure is reproducible enough to give valid data with only one sample per prime size.  However, here is what I got.

On a Mac G4/450MHz running OS 10.3.9:

[G4:~] billfran% time openssl gendh 512
  ...
9.850u 0.170s 0:18.39 54.4%     0+0k 3+7io 0pf+0w

[G4:~] billfran% time openssl gendh 1024
  ...
11.920u 0.070s 0:13.19 90.9%    0+0k 0+3io 0pf+0w

[G4:~] billfran% time openssl gendh 2048
  ...
5909.970u 24.060s 1:45:08.60 94.0%      0+0k 0+4io 0pf+0w

[G4:~] billfran% time openssl gendh 3072
  ...
21017.450u 166.540s 6:42:28.96 87.7%    0+0k 0+3io 0pf+0w

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | gets() remains as a monument | Periwinkle 
(408)356-8506      | to C's continuing support of | 16345 Englewood Ave
www.pwpconsult.com | buffer overruns.             | Los Gatos, CA 95032

Date: Wed, 21 Sep 2005 18:21:31 +0200
To: [email-masked]
Subject: Re: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 21, 2005 at 01:28:27PM +0100, Ben Laurie wrote:

> I don't understand this attack.

It's the well-known Klima-Rosa attack. It has been discussed earlier on
this list.

> >2. No explicit count of MPIs constituting the key material (both public and
> >private).
> >
> >This information can only be inferred from the algorithm specifier, meaning
> >that any implementation that wants to perform key management must have some
> >rudimentary knowledge about all public key algorithms. This, in turn,
> >hampers forward-compatibility.
> 
> This appears to me to be incorrect - an implementation that didn't know 
> the algorithm could still deduce the number of MPIs by parsing the 
> packet until it is exhausted.

Except for private key packets.

> This would mean introducing a requirement 
> that all public key parameters were MPIs, of course.

That, too.

> >3. Key fingerprint depends on data unrelated to the actual key (namely:
> >creation date).
> >
> >This prevents solutions when signature keys are generated on the fly (e.g.
> >directly from a passphrase), as the key creation (or, in this case, key
> >registration) date is not available at the time of signing, thus making it
> >impossible to put am unambiguous reference to the public key into the
> >signature.
> 
> Not impossible, but I'll agree, crufty. One could use a fixed creation date.

That's a horrible cruft breaking all sorts of things (validity period, etc.).

I like Dave's suggestion about adding optional subpackets, similar to those
in signatures.

-- 
Daniel

Date: Wed, 21 Sep 2005 08:56:19 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Problems with v4 key packet format
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Wed, Sep 21, 2005 at 01:28:27PM +0100, Ben Laurie wrote:

> >2. No explicit count of MPIs constituting the key material (both public and
> >private).
> >
> >This information can only be inferred from the algorithm specifier, meaning
> >that any implementation that wants to perform key management must have some
> >rudimentary knowledge about all public key algorithms. This, in turn,
> >hampers forward-compatibility.
> 
> This appears to me to be incorrect - an implementation that didn't know 
> the algorithm could still deduce the number of MPIs by parsing the 
> packet until it is exhausted. This would mean introducing a requirement 
> that all public key parameters were MPIs, of course.

You could also do what GnuPG does - if it doesn't know the algorithm
it just reads the entire list of MPIs (or anything else in the packet)
into an opaque buffer.  I suppose it could figure out the MPIs, but
there seems to be little point since either way, the key is not usable
without support for the algorithm.  I suppose if the implementation
stored keys in a backend that needed to know the individual key
parameters that would be different.

> >3. Key fingerprint depends on data unrelated to the actual key (namely:
> >creation date).
> >
> >This prevents solutions when signature keys are generated on the fly (e.g.
> >directly from a passphrase), as the key creation (or, in this case, key
> >registration) date is not available at the time of signing, thus making it
> >impossible to put am unambiguous reference to the public key into the
> >signature.
> 
> Not impossible, but I'll agree, crufty. One could use a fixed creation date.

Some people want to include things in the key fingerprint and some
don't.  There are good reasons for both, so I favor v5 keys with
optional subpackets like v4 signatures.  Within reason, it's a "make
everyone happy" solution.

David

Date: Wed, 21 Sep 2005 13:48:24 +0100
From: Ben Laurie <[email-masked]>
To: "Daniel A. Nagy" <[email-masked]>
CC: OpenPGP <[email-masked]>
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Daniel A. Nagy wrote:
> On Tue, Sep 20, 2005 at 04:34:38AM -0400, Adam Back wrote:
> 
> 
>>Could one not use the Lim Lee safe prime generation method for DSA?
>>
>>It has significant speed advantages.
>>
>>Adam
> 
> 
> DSS explicitly specifies how to generate primes for DSA keys. It can be
> easily generalized for larger keys and other hash functions, and its
> reasonable to assume that the new DSS will do that.
> 
> My estimates were based on that specification.

You only have to follow DSS if you want FIPS-140 and the like, of course.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

Date: Wed, 21 Sep 2005 13:28:27 +0100
From: Ben Laurie <[email-masked]>
To: "Daniel A. Nagy" <[email-masked]>
CC: [email-masked]
Subject: Re: Problems with v4 key packet format
Sender: [email-masked]

Daniel A. Nagy wrote:
> In order to design a successor to v4 key packet format, it is important to
> first identify its shortcomings. Here's a list of my problems with it:
> 
> 1. No cryptographic binding between the encrypted private key material and
> the public key material.
> 
> This results in a serious security issue, by allowing an attacker to replace
> the public material thus compromising the private material with the first
> use in the signature. There are various stop-gap measures to deal with this
> attack, but the only sure protetction would be some MDC binding together the
> private and the public key material.

I don't understand this attack.

> 2. No explicit count of MPIs constituting the key material (both public and
> private).
> 
> This information can only be inferred from the algorithm specifier, meaning
> that any implementation that wants to perform key management must have some
> rudimentary knowledge about all public key algorithms. This, in turn,
> hampers forward-compatibility.

This appears to me to be incorrect - an implementation that didn't know 
the algorithm could still deduce the number of MPIs by parsing the 
packet until it is exhausted. This would mean introducing a requirement 
that all public key parameters were MPIs, of course.

> 3. Key fingerprint depends on data unrelated to the actual key (namely:
> creation date).
> 
> This prevents solutions when signature keys are generated on the fly (e.g.
> directly from a passphrase), as the key creation (or, in this case, key
> registration) date is not available at the time of signing, thus making it
> impossible to put am unambiguous reference to the public key into the
> signature.

Not impossible, but I'll agree, crufty. One could use a fixed creation date.

> 4. More generally, creation time does not belong to the key packet.
> 
> Because it is just an attribute of the key as any other, thus belonging to
> certificatiton signature sub-packets, rather than the key packet.

So?

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

Date: Wed, 21 Sep 2005 13:24:20 +0100
From: Ben Laurie <[email-masked]>
To: Hal Finney <[email-masked]>
CC: [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Hal Finney wrote:
> In contrast, finding "strong" primes p such that (p-1)/2 is also prime
> does tend to be slow.  I think there is a trick to do it using a double
> sieve but it is still much slower than finding regular primes.

There is - Geoff Thorpe and I planned to implement it for OpenSSL, but 
never got around to it.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

Date: Wed, 21 Sep 2005 12:00:52 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: OpenPGP <[email-masked]>
Cc: Jon Callas <[email-masked]>
Subject: Re: Interop grill-off
Sender: [email-masked]

Jon Callas wrote:
> 
> I think it would be good for us to have some sort of interoperability  
> test and event. Putting on my PGP Corporation hat, I'm happy to  sponsor 
> it. However, it doesn't *have* to be a physical event.

Physics is fun, but net chemistry also works.  I've
had some degree of success in testing cross-platform
code using a "webservice" approach.  Basically, build
a server that offers a number of actions over HTTP **.

The basic action is an echo service that forms part of
a read/write cycle to prove serialisation.  It works
roughly this way:

1.  Create a garbage packet.
2.  Serialise it into its network form.
3.  Send it off to the other implementation
     over some sort of server protocol.
4.  The echo server sits there and waits for packets:
     a. read a packet in,
     b. parse it, objectise it,
     c. write it out again in network form,
     d. return it as the response to the request.
5.  The original sender reads back the response,
     recovers it and then compares it internally
     with the original packet it sent.

This means that there needs to be two routines
added to every packet:  create a garbage packet,
and compare two packets for equality.

Once that basic architecture is defined, many
variants are possible....

> Does  anyone else 
> think it would be a good idea? Does anyone want to help  put it on, come 
> up with test cases, that sort of thing?

It's definately a good idea.  The main thing
above would be to define a list of the minimal
packets that should be echoed:

    public key packet with basic feature set
         and only the MUST algorithms
    encrypted message,
    signed message, cleartext and binary
    encrypted + signed binary

Start with the absolute minimum.  (Obviously
encrypted and signed messages will involve
some state ....)

iang

PS:  To add in another buzzword, I'd do it in
REST format, which basically means do it as a
simulated web server, and have the client and
server deal with HTTP POST requests with some
form of application binary data.  This avoids
most of the complications of defining ones own
transport protocol, avoids having to talk to
the firewall people, and for most languages
means you don't have to run a server at all,
just slot it in as a CGI into Apache.

Date: Wed, 21 Sep 2005 11:58:32 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: [email-masked]
Cc: "Daniel A. Nagy" <[email-masked]>
Subject: [v5] Re: Problems with v4 key packet format
Sender: [email-masked]

Daniel A. Nagy wrote:
> In order to design a successor to v4 key packet format, it is important to
> first identify its shortcomings. Here's a list of my problems with it:

Perhaps a pass at listing the problems in v4 ** would
be a fair first phase.  Here's a couple of issues
(although I admit to not bit-peeping as much as I
should, most of these are user/mgr level grumbles):

5.  Too many integers and formats and what have you.
There should be a base level of formats which should
cover all requirements, and these should be flexible
enough to do that job, while simple and short enough
to be easily implementable and understandable.

6.  PGP's feedback mode.  There's no point to this.
It's a thing that PRZ added in because he thought it
was cool;  he was wrong on that point && and it would
make matters easier if the standard CBC modes that
are described in all the textbooks were used.

7.  Cipher suites, not algorithms.  Although I like
OpenPGP's tradition of opening up to experiments in
algorithms and so forth, I think it is a pain for
interoperability and implementation.  It might be
fine to demand the "right" to implement odd-length RSA
with Ripem-666 hashes and the latest chinese cipher
feedback modes over GOST encryption, but this is
just plain stupidity at the software engineering
level.

As much as possible, I'd suggest that a cipher suites
approach be used:  Cipher suite #1 should fix the
PK, the encryption algorithm, the hash, the feedback
modes, and all that.  When something breaks, deprecate
the whole sodding lot, and move on to #2.

Life was really good in the days up to pgp2.6.  Then
it all went to pot.  We may never go back to those
simple times, but we can attempt to simulate it by
using cipher suites $$.

(some of these points are contradictory at some
level :-)

iang

PS **: if we are going to start discussing futures like
v5, it might be easier to stick something in the subject
so people know quickly that it does not effect the
current doc.

PS &&: This is not a criticism of him;  nobody ever
builds a perfect cryptosystem, and it falls to later
disciples to carefully clean out the mistakes.

PS $$: Allowing experimental cipher suites would be
fine.  Another trap to avoid is the SSL cipher suite
rabbit explosion ... but that should be easy to do
if we allow people to experiment with their own and
only promote the really useful, strong ones.  I.e.,
rejection of marginal improvements as a routine.

Date: Wed, 21 Sep 2005 11:44:26 +0200
To: [email-masked]
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 09:10:53PM -0400, David Shaw wrote:

> I'm all for getting these problems fixed, but we stand a better chance
> of doing by working the actual problem.  By all means, add some
> clarifying text to the text for the issuer key ID subpacket, but
> understand that won't change the keyserver situation.  It's just two
> different problems.

Oh, there seems to be a misunderstanding between us, for which I should
probably apologize. I never for a moment suggested that SKS's bad behavior
was the result of the wording in RFC2440, though reading back, it might have
indeed come across like I did.

I simply listed interoperability problems that I have encountered that in my
opinion resulted from not anticipating less obvious, yet perfectly
RFC-compliant behavior. In this particular case, I have noted a minor
possible ambiguity in the standard text, which, I repeat, should be obvious
for anyone giving it a little thought. As an implementer myself, I have
resorted to the same workarounds: canonizing public key packets before
uploading to keyserver and using short key IDs.

Also, I totally agree with you that clarification in the standard is not the
way to fix this problem, but listing it as a known interoperability issue in
the mailing list archive or even on some webpage dedicated to
interoperability between OpenPGP applications (is that what Jon aims to do?)
might help in two ways: culprits may eventually fix their bugs, and
meanwhile others might avoid running into them.

For example, if such a list existed when I coded the relevant parts of
ePointPGP, it would have saved me a lot of time. I think, Jon's idea of an
interop grill-off is an excellent opportunity for assembling such a list of
known interoperability issues, before venturing into testing unknown,
suspected ones.

That said, SKS is by far the most standards-compliant HKP-compatible
keyserver that I have seen. Others do horrible things to keys and search
results. Since keyservers are (correctly) considered outside of security
perimeters and should be treated as untrustworthy in any case, they tend to
be the least carefully written and maintained applications in the OpenPGP
world. That's just a fact of life, I guess, that we need to cope with.

And again, apologies in case I have unintentionally offended someone.

-- 
Daniel

Date: Tue, 20 Sep 2005 21:10:53 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Interop grill-off
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Wed, Sep 21, 2005 at 01:53:39AM +0200, Daniel A. Nagy wrote:

> > Doing otherwise would be an absurd thing to do - the signing
> > equivalent of putting the main key ID into a PKESK packet when
> > encrypting to a subkey.  If you can point to a single implementation
> > that does this wrong, I'll immediately concede the point.
> 
> Of course, I can't. This is why I am saying that SKS has an important
> interoperability problem. It EXPECTS the wrong behavior, while nobody
> actually does it.

While it is true that SKS doesn't do long keyid searches for subkeys,
and I agree this is suboptimal behavior, understand that this is not
connected to what clients put in the issuer key ID subpacket.  There
has never been a client that put anything other than the signing key
ID in the subpacket, and the SKS behavior is not based on some
misreading of that point in the draft.

Even if SKS started supporting long subkey ID searches tomorrow, it
would not resolve this problem, as GnuPG doesn't provide long key IDs
when speaking to any HKP-ish keyserver because there are still old PKS
servers out that that just won't die.  I believe PGP does the same
thing.  If you want long key ID searches, you need to use LDAP.

Note that even those PKS servers that don't blow up completely on long
key ID searches don't really do them either: they just pretend to, and
ignore the upper 32 bits - try searching for 0x99242560 and
0x1111111199242560.  PKS doesn't do subkey searches at all.

I'm all for getting these problems fixed, but we stand a better chance
of doing by working the actual problem.  By all means, add some
clarifying text to the text for the issuer key ID subpacket, but
understand that won't change the keyserver situation.  It's just two
different problems.

David

Date: Wed, 21 Sep 2005 01:53:39 +0200
To: [email-masked]
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 01:12:47PM -0400, David Shaw wrote:

> > No, it isn't. This becomes a major interoperability issue, when you use
> > signature subkeys. It's not quite clear from RFC2440 wether the 8-byte
> > signatory field sould point to the main key or the subkey, but in several
> > implementations it points to the subkey, which actually made the signature
> > (and this is the right behavior, IMHO).
> 
> I don't know of *any* implementations that set the issuer subpacket to
> anything other than the key that made the signature, as specified in
> the RFC. 

You mean the actual subkey, right? Where is it specified in the RFC?
The formulation "the key that made the signature" is a bit ambiguous, IMHO,
but, of course, the sensible thing to do is obvious.

> Doing otherwise would be an absurd thing to do - the signing
> equivalent of putting the main key ID into a PKESK packet when
> encrypting to a subkey.  If you can point to a single implementation
> that does this wrong, I'll immediately concede the point.

Of course, I can't. This is why I am saying that SKS has an important
interoperability problem. It EXPECTS the wrong behavior, while nobody
actually does it.

-- 
Daniel

Date: Wed, 21 Sep 2005 01:47:28 +0200
To: [email-masked]
Subject: Re: Bigger DSA keys
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 11:02:19AM -0700, "Hal Finney" wrote:

> I'm not sure how other systems that implement DSS handle the issue of
> validating public parameter certificates.  It could be that OpenPGP is
> the main user of DSA/DSS and nobody else worries about it.  I know I've
> seen X.509 certificate specs for DSS keys and they don't have the extra
> information necessary (although strangely, X.509 Diffie-Hellman keys do
> have it!).  I guess they just assume that checks for legal DSS public
> parameters are outside the scope of their spec.

I know about one other major implementation of DSS, which is java.security
by Sun Microsystems. Their key generation method  uses pre-calculated
moduli for the common key sizes, but one can turn that feature off and
have the key generated from scratch (which takes a lot longer, of course).

The certificates of the pre-calculated moduli are in a comment of the source
code, which you may obtain from Sun upon request (they are very forthcoming
about that, becasue they understand that openness is the basis of trust in
crypto matters).

-- 
Daniel

Date: Tue, 20 Sep 2005 14:08:23 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Information and meta-information
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Thu, Sep 08, 2005 at 01:31:25AM +0200, Daniel A. Nagy wrote:
> 
> On Wed, Sep 07, 2005 at 03:56:58PM -0700, Wim Lewis wrote:
> 
> > The existing 'b', 't', etc. tags could then be defined as shorthands  
> > for particular MIME headers (content-type and charset).
> 
> I disagree, because these tags convey a slightly different (lower-level)
> meaning than the mime headers. Also, the above suggestion would be a
> security hazard, since the literal packet's tag is not hashed and can be
> therefore altered in a signed message, without breaking the signature.
> PGP/MIME headers, on the other hand, are included in the hashed material, so
> they are part of the signed message.
> 
> > >I would suggest the following modification of RFC2440bis-14:
> > 
> > Do you mean removing the 't' and 'u' tags? Or supplementing them with  
> > 'm'?
> 
> Supplementing with 'm', of course. Removing 't' and 'b' tags (what's 'u'?)
> would break almost everything.

't' = unspecified charset
'u' = utf-8 charset

David

Date: Tue, 20 Sep 2005 14:06:51 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Interop grill-off
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Tue, Sep 20, 2005 at 10:33:37AM -0700, "Hal Finney" wrote:

> Perhaps we should clarify the language in the RFC to eliminate any
> such ambiguity.  5.2.3.5, the Issuer subpacket, just says:
> 
>     The OpenPGP key ID of the key issuing the signature.
> 
> We could add "If the signature is issued by a subkey then the key ID of
> this subkey is used here instead of the key ID of the primary key."
> 
> We do have similar language in 5.2 for PKESKs:
> 
>       - An eight-octet number that gives the key ID of the public key
>         that the session key is encrypted to. If the session key is
>         encrypted to a subkey then the key ID of this subkey is used
>         here instead of the key ID of the primary key.

I think that is reasonable, but it would need to be mentioned in
several places (in bis-14): 5.2.2 (V3 signatures), 5.2.3.5 (issuer
subpacket), and 5.4 (Onepass signature packet).  Perhaps something
could be said in 3.3 (Key IDs) that covers them all?

David

To: [email-masked]
Subject: Re: Bigger DSA keys
Date: Tue, 20 Sep 2005 11:02:19 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

There are a few differences between the OpenPGP requirements for DSA
keys and those in the DSS spec.

Usually, OpenPGP implementations do not use pre-calculated moduli
for DSA keys.  Likewise, OpenPGP does not require that DSA keys be
generated by the method described in the DSS standard.  This is the
reason why we generally call them DSA keys and not DSS keys in the spec.
Nevertheless we do follow the FIPS-186 recommendations for modulus sizes,
as their advice is good.

There are a few issues here.  Pre-calculated moduli do have some
advantages.  Generating the modulus is the slow part of DSA keygen.
With a pre-calculated modulus, all that is necessary to generate a key
is to pick a random value x and do one exponentiation to generate y = g^x
mod p.  This can also save space in key distribution; if there is a widely
shared modulus then only the y value has to be distributed for each key.

There are a few disadvantages though.  There are theoretical attacks where
the body that generates the pre-calculated modulus can use "trapdoor"
primes which allow faster calculation of discrete log.  Anyone who
generated a key using that shared modulus would be at risk of having
his private key broken by the body which created that modulus.

In order to protect users against this possibility, DSS specifies that
the public parameters (p, q, g) be generated using a randomization
technique which essentially eliminates the possibility of a trapdoor.
But it also requires that a sort of "certificate" of the parameter
generation be created and distributed, and that end users verify that
certificate to make sure that the public parameters have no trapdoors.

This is pretty complicated, and furthermore the general paranoia among
much of OpenPGP's audience is likely to make them mistrust even shared
parameters that are accompanied by such certificates.  As a result OpenPGP
has not pursued this approach.  There are no OpenPGP data structures to
share DSS public parameter certificates and nothing in the spec about
creating DSS keys in the standard way, or sharing and verifying such
certificates.

So OpenPGP generally envisions DSA keys being generated with fresh public
parameters for each key.  Not only is this more secure and simpler,
but it allows for the fast generation method I described in my mail
yesterday, which uses sieving.  Generating DSS moduli per FIPS-186 is
relatively slow, and extending that method to larger prime sizes may
become prohibitively slow.  (Of course, if the FIPS-186 method is used
with shared moduli, then keygen becomes very faster as I noted above,
just a single exponentiation to calculate y.)

I'm not sure how other systems that implement DSS handle the issue of
validating public parameter certificates.  It could be that OpenPGP is
the main user of DSA/DSS and nobody else worries about it.  I know I've
seen X.509 certificate specs for DSS keys and they don't have the extra
information necessary (although strangely, X.509 Diffie-Hellman keys do
have it!).  I guess they just assume that checks for legal DSS public
parameters are outside the scope of their spec.

Hal Finney

To: [email-masked]
Subject: Line spacing in normative references
Date: Tue, 20 Sep 2005 10:39:39 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Hal

To: [email-masked]
Subject: Re: Interop grill-off
Date: Tue, 20 Sep 2005 10:33:37 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

David Shaw writes:
> I don't know of *any* implementations that set the issuer subpacket to
> anything other than the key that made the signature, as specified in
> the RFC.  Doing otherwise would be an absurd thing to do - the signing
> equivalent of putting the main key ID into a PKESK packet when
> encrypting to a subkey.  If you can point to a single implementation
> that does this wrong, I'll immediately concede the point.

Perhaps we should clarify the language in the RFC to eliminate any
such ambiguity.  5.2.3.5, the Issuer subpacket, just says:

    The OpenPGP key ID of the key issuing the signature.

We could add "If the signature is issued by a subkey then the key ID of
this subkey is used here instead of the key ID of the primary key."

We do have similar language in 5.2 for PKESKs:

      - An eight-octet number that gives the key ID of the public key
        that the session key is encrypted to. If the session key is
        encrypted to a subkey then the key ID of this subkey is used
        here instead of the key ID of the primary key.

This would make sure there is no ambiguity about which key ID to use.

Hal Finney

Date: Tue, 20 Sep 2005 18:30:53 +0100
From: Ben Laurie <[email-masked]>
To: "Daniel A. Nagy" <[email-masked]>
CC: [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Daniel A. Nagy wrote:
> It's important to keep in mind that DSS-style signatures are twice the hash
> size. This is one of their nicest features; they do not grow with the
> modulus. A signature of a 3072/256 key will be 512 bits (plus overhead).
> 
> As for generating long modulae, it's not that big a problem, altough it has
> to be noted that generating a modulus for DSA takes more than just
> generating a prime that big; DSA moduli p are such that p-1 is divisible by
> some large (hash-sized) q. The generation of such moduli takes substantially
> longer than generating primes. For 3072/256 on a 500MHz intel, it would take
> approx. three minutes, provided that the random stream is available without
> waiting.
> 
> On the other hand, the overwhelming majority of DSS implementations use
> pre-calculated moduli, as there are no security hazards associated with
> using a common modulus for DSS. When keys need to be generated frequently,
> a pre-calculated modulus is the way to go. If one just needs to generate a
> personal signature key for the next five years, one can wait three minutes,
> in case they want to show off a self-generated modulus.

Good point.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

Date: Tue, 20 Sep 2005 13:12:47 -0400
From: David Shaw <[email-masked]>
To: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
Mail-Followup-To: OpenPGP <[email-masked]>
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Tue, Sep 20, 2005 at 06:04:57PM +0200, Daniel A. Nagy wrote:
> 
> On Tue, Sep 20, 2005 at 11:17:05AM -0400, David Shaw wrote:
> 
> > > 3. Some keyservers do not return matching keys, if searched by the long
> > > (16 byte) key ID of a subkey. SKS is guilty of this.
> > 
> > Isn't this a just SKS feature request?  Nothing in the draft says
> > anything about how keyservers work, or even that a UI must allow
> > particular ways to search.
> 
> No, it isn't. This becomes a major interoperability issue, when you use
> signature subkeys. It's not quite clear from RFC2440 wether the 8-byte
> signatory field sould point to the main key or the subkey, but in several
> implementations it points to the subkey, which actually made the signature
> (and this is the right behavior, IMHO).

I don't know of *any* implementations that set the issuer subpacket to
anything other than the key that made the signature, as specified in
the RFC.  Doing otherwise would be an absurd thing to do - the signing
equivalent of putting the main key ID into a PKESK packet when
encrypting to a subkey.  If you can point to a single implementation
that does this wrong, I'll immediately concede the point.

David

To: [email-masked] (Daniel A. Nagy)
Cc: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Tue, 20 Sep 2005 18:14:32 +0200
Sender: [email-masked]

On Tue, 20 Sep 2005 17:50:02 +0200, Daniel A Nagy said:

>> > more than one ESK? Does it try all of them with all the private keys, or
>> 
>> --try-all-secrets applies only to PKESK to assume wildcard key IDs.

> Right, but what if there are more of these (multiple recipients)?

Yes, it tries all of them with all available secret keys.

Salam-Shalom,

   Werner

Date: Tue, 20 Sep 2005 18:04:57 +0200
To: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 11:17:05AM -0400, David Shaw wrote:

> > 3. Some keyservers do not return matching keys, if searched by the long
> > (16 byte) key ID of a subkey. SKS is guilty of this.
> 
> Isn't this a just SKS feature request?  Nothing in the draft says
> anything about how keyservers work, or even that a UI must allow
> particular ways to search.

No, it isn't. This becomes a major interoperability issue, when you use
signature subkeys. It's not quite clear from RFC2440 wether the 8-byte
signatory field sould point to the main key or the subkey, but in several
implementations it points to the subkey, which actually made the signature
(and this is the right behavior, IMHO).

In this case, databases of keys, be it local keyrings or remote keyservers
MUST be indexed by subkey IDs as well, otherwise such signatures cannot be
verified. For example, this SKS deficienci breaks interoperability (namely
yautotmatic key retrieval) with GnuPG (and very possibly PGP), if signature
subkeys are used.

Signature subkeys have many uses, and although they are less popular than
encryption subkeys (because of the default settings of pgp and gpg) their
use is an important security measure allowing for changing the regularly
used signing key without losing all certificatitons on the main key. They
are also useful if the same user wishes to make signatures from different
computers without risking too much.

-- 
Daniel

Date: Tue, 20 Sep 2005 17:50:02 +0200
To: Werner Koch <[email-masked]>, OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 11:39:11AM +0200, Werner Koch wrote:
> On Tue, 20 Sep 2005 10:47:57 +0200, Daniel A Nagy said:
> 
> > By the way, what does gpg do given the --try-all-secrets option, if there's
> > more than one ESK? Does it try all of them with all the private keys, or
> 
> --try-all-secrets applies only to PKESK to assume wildcard key IDs.

Right, but what if there are more of these (multiple recipients)?

-- 
Daniel

Date: Tue, 20 Sep 2005 11:17:05 -0400
From: David Shaw <[email-masked]>
To: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
Mail-Followup-To: OpenPGP <[email-masked]>
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Tue, Sep 20, 2005 at 08:53:46AM +0200, Daniel A. Nagy wrote:

> 2. Some keyservers omit canonization before hashing the key packet. If the
> key packet is shorter than 256 bytes (typically the case for 1024-bit RSA
> keys) and uses the shortest possible packet header with a one-byte length,
> the fingerprint and the key IDs are mis-calculated. PKS is guilty of this.

This is a good one.  I've seen this mistake made more than once, and
not just in PKS.  Incidentally, that bug in PKS was fixed quite a
while ago.  PKS had many problems, including miscalculating v4 RSA
fingerprints, mangling keys with more than one subkey, discarding
attribute ID packets, etc.  Most of the worst have been fixed, but the
point may be moot as so far as I know, PKS is not being developed any
longer.

> 3. Some keyservers do not return matching keys, if searched by the long
> (16 byte) key ID of a subkey. SKS is guilty of this.

Isn't this a just SKS feature request?  Nothing in the draft says
anything about how keyservers work, or even that a UI must allow
particular ways to search.

David

Date: Tue, 20 Sep 2005 15:30:04 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: Werner Koch <[email-masked]>
Cc: Ben Laurie <[email-masked]>, Hal Finney <[email-masked]>, [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Werner Koch wrote:
> DSA 100 times    sign  verify
> -----------------------------
> DSA 1024/160    910ms   430ms
> DSA 2048/224   1560ms  1890ms
> DSA 3072/256   3610ms  4380ms
> 
> (The numbers for sign are not very reliable because it employs the
> RNG and I could not adjust for it)
> 
> 3072 takes more more than double the time of 2048 which is not too
> bad.  Compared to 1024 this is a real slowdown and would make key
> signature verification a very time consuming operation.  On slow
> machines (embedded devices, older hardware) this would be very
> annoying.

Ah, ok, so this last point about slow / small hardware
platforms makes sense.  So we might be tempted to suggest
that implementations SHOULD verify any of the three lengths,
and let them choose which length to deliver for signing
beyond the MUST of 1024/160.

(Which is after all a minor side discussion in Hal's
thread of whether to wait or not.)

iang

To: [email-masked] (Daniel A. Nagy)
Cc: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Tue, 20 Sep 2005 11:39:11 +0200
Sender: [email-masked]

On Tue, 20 Sep 2005 10:47:57 +0200, Daniel A Nagy said:

> By the way, what does gpg do given the --try-all-secrets option, if there's
> more than one ESK? Does it try all of them with all the private keys, or

--try-all-secrets applies only to PKESK to assume wildcard key IDs.

Shalom-Salam,

   Werner

To: [email-masked] (Daniel A. Nagy)
Cc: OpenPGP <[email-masked]>
Subject: Re: Bigger DSA keys
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Tue, 20 Sep 2005 11:34:16 +0200
Sender: [email-masked]

On Tue, 20 Sep 2005 10:54:32 +0200, Daniel A Nagy said:

> DSS explicitly specifies how to generate primes for DSA keys. It can be
> easily generalized for larger keys and other hash functions, and its
> reasonable to assume that the new DSS will do that.

FWIW, the Lim & Lee algorithm is newer than DSS.  It was published in
Crypto 97 whereas FIPS 186 was published in 1994.

Salam-Shalom,

   Werner

To: [email-masked] (Daniel A. Nagy)
Cc: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Tue, 20 Sep 2005 11:07:09 +0200
Sender: [email-masked]

On Tue, 20 Sep 2005 10:39:56 +0200, Daniel A Nagy said:

> I would suggest a completely different approach: try extracting a key from
> each ESK (be it password-derived, password-encrypted or
> asymmetcially encrypted), and use the one which inspires most confidence:

Makes sense.  We have not seen many pubkey/symkey encrypted messages
in the wild thus the way we handle them is straightforward.  Need to
look at it closer.

Thanks,

  Werner

Date: Tue, 20 Sep 2005 10:54:32 +0200
To: OpenPGP <[email-masked]>
Subject: Re: Bigger DSA keys
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 04:34:38AM -0400, Adam Back wrote:

> Could one not use the Lim Lee safe prime generation method for DSA?
> 
> It has significant speed advantages.
> 
> Adam

DSS explicitly specifies how to generate primes for DSA keys. It can be
easily generalized for larger keys and other hash functions, and its
reasonable to assume that the new DSS will do that.

My estimates were based on that specification.

-- 
Daniel

Date: Tue, 20 Sep 2005 10:47:57 +0200
To: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 10:06:36AM +0200, Werner Koch wrote:

> Due to gpg's streaming based design ...

By the way, what does gpg do given the --try-all-secrets option, if there's
more than one ESK? Does it try all of them with all the private keys, or
just the first one?

-- 
Daniel

Date: Tue, 20 Sep 2005 10:39:56 +0200
To: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Tue, Sep 20, 2005 at 10:06:36AM +0200, Werner Koch wrote:
> On Tue, 20 Sep 2005 08:53:46 +0200, Daniel A Nagy said:
> 
> > 4. Some implementations give up before trying all possible ways of
> > decrypting a message. For example, GnuPG gives up if it encounters a
> > passphrase-derived symmetric key specifier and the entered passphrase is
> > wrong, even if it is followed by an asymmetrically encrypted symmetric key
> > for which it does have access to the corresponding private decryption key.
> 
> There are actually two problems: 
> 
> There is no way to cancel the input of a passphrase when using the
> CLI, so that gpg can continue with other keys.  When using the
> gpg-agent, this is possible but a bug inhibited this - I just fixed
> that one.

I never thought of this as a problem, but maybe you're right.
 
> The other problem is that we can't reliable decide whether the
> passphrase is correct.  The only way to do this is by looking at the
> algorithm byte to check whether this gives a valid algorithm.  This is
> far form being reliable. Due to gpg's streaming based design with only
> a very limited look-ahead we can't do a test decryption and roll back
> if it does not work out.

I would suggest a completely different approach: try extracting a key from
each ESK (be it password-derived, password-encrypted or
asymmetcially encrypted), and use the one which inspires most confidence:

An asymmetrically decrypted key has an approx. 1 in 17 million chance of
being incorrect, symmetrically encrypted keys have a roughly 1 in 20 chance
of being incorrect, while there's absolutely no indication wheter a
passphrase-derived secret key is correct or not.

Thus, deriving a decryption key from a passphrase and then merrily
proceeding to the decryption of the encrypted content is incorrect. A
correct implementation should try to extract a key from each ESK, and in
case of success (asymmetric decryption with leading 0 and correct checksum,
symmetric encryption with valid algorithm id or any passphrase-derived key)
replacing the tentative decryption key, if the new key inspires more
confidence than the previous tentative key. Eventually, the last tentative
key should be used for decryption.
 
> A way to check early that the decryption worked would be needed to
> solve the problem - I am not sure whether this is really needed given
> the security implications of such a check.

Yes, that's somewhat hazardous, indeed (although only in non-interactive
applications). But it's not necessary, as explained above.

-- 
Daniel

Date: Tue, 20 Sep 2005 04:34:38 -0400
From: Adam Back <[email-masked]>
To: Hal Finney <[email-masked]>
Cc: [email-masked], Adam Back <[email-masked]>
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Could one not use the Lim Lee safe prime generation method for DSA?

It has significant speed advantages.

Adam

On Mon, Sep 19, 2005 at 06:44:29PM -0700, "Hal Finney" wrote:
> As far as the issue of generating large DSA keys, a good algorithm to
> use is the following.  First generate an appropriately sized subgroup
> prime q (160, 224, or 256 bits respectively).  Then search for a prime
> modulus p of the required size (1024, 2048 or 3072 bits) such that p is
> one more than a multiple of q.

To: [email-masked] (Daniel A. Nagy)
Cc: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Tue, 20 Sep 2005 10:06:36 +0200
Sender: [email-masked]

On Tue, 20 Sep 2005 08:53:46 +0200, Daniel A Nagy said:

> 4. Some implementations give up before trying all possible ways of
> decrypting a message. For example, GnuPG gives up if it encounters a
> passphrase-derived symmetric key specifier and the entered passphrase is
> wrong, even if it is followed by an asymmetrically encrypted symmetric key
> for which it does have access to the corresponding private decryption key.

There are actually two problems: 

There is no way to cancel the input of a passphrase when using the
CLI, so that gpg can continue with other keys.  When using the
gpg-agent, this is possible but a bug inhibited this - I just fixed
that one.

The other problem is that we can't reliable decide whether the
passphrase is correct.  The only way to do this is by looking at the
algorithm byte to check whether this gives a valid algorithm.  This is
far form being reliable. Due to gpg's streaming based design with only
a very limited look-ahead we can't do a test decryption and roll back
if it does not work out.

A way to check early that the decryption worked would be needed to
solve the problem - I am not sure whether this is really needed given
the security implications of such a check.

Salam-Shalom,

   Werner

Date: Tue, 20 Sep 2005 08:53:46 +0200
To: OpenPGP <[email-masked]>
Subject: Re: Interop grill-off
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Mon, Sep 19, 2005 at 02:05:19PM -0700, Jon Callas wrote:

> I think it would be good for us to have some sort of interoperability  
> test and event. Putting on my PGP Corporation hat, I'm happy to  
> sponsor it. However, it doesn't *have* to be a physical event. Does  
> anyone else think it would be a good idea? Does anyone want to help  
> put it on, come up with test cases, that sort of thing?

How about simply posting test cases with descriptions here, and testing on
various OpenPGP implementations, also posting the results to the mailing
list. Then you (or someone else) could post a summary here and/or to some
webpage.

I'm also wondering what are you more after: unusual data conforming to
RFC2400 (or RFC2440bis) or slight (but logical) deviations, extensions?

I guess, many of us have already identified interoperability problems. Would
it make sense to collect them first, before going into testing questionable
cases?

Here's my list of problematic cases that I have encountered:
(offenders: HushMail, PKS, SKS, GnuPG)

1. HushMail's idea of signed and encrypted messages is encrypting a
clearsigned message as canonical text, including the message boundary and
the armored signature. Other applications usually don't verify the
signature, though, of course, it's easy to do "by hand" (by running a second
pass). In the other direction, it's worse: HushMail decrypts the properly
signed and encrypted message, but keeps silent about the one-pass signature
within the encrypted payload; the message is identified as encrypted but not
signed.

2. Some keyservers omit canonization before hashing the key packet. If the
key packet is shorter than 256 bytes (typically the case for 1024-bit RSA
keys) and uses the shortest possible packet header with a one-byte length,
the fingerprint and the key IDs are mis-calculated. PKS is guilty of this.

3. Some keyservers do not return matching keys, if searched by the long
(16 byte) key ID of a subkey. SKS is guilty of this.

4. Some implementations give up before trying all possible ways of
decrypting a message. For example, GnuPG gives up if it encounters a
passphrase-derived symmetric key specifier and the entered passphrase is
wrong, even if it is followed by an asymmetrically encrypted symmetric key
for which it does have access to the corresponding private decryption key.

-- 
Daniel

Date: Tue, 20 Sep 2005 07:32:31 +0200
To: [email-masked]
Subject: Problems with v4 key packet format
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

In order to design a successor to v4 key packet format, it is important to
first identify its shortcomings. Here's a list of my problems with it:

1. No cryptographic binding between the encrypted private key material and
the public key material.

This results in a serious security issue, by allowing an attacker to replace
the public material thus compromising the private material with the first
use in the signature. There are various stop-gap measures to deal with this
attack, but the only sure protetction would be some MDC binding together the
private and the public key material.

2. No explicit count of MPIs constituting the key material (both public and
private).

This information can only be inferred from the algorithm specifier, meaning
that any implementation that wants to perform key management must have some
rudimentary knowledge about all public key algorithms. This, in turn,
hampers forward-compatibility.

3. Key fingerprint depends on data unrelated to the actual key (namely:
creation date).

This prevents solutions when signature keys are generated on the fly (e.g.
directly from a passphrase), as the key creation (or, in this case, key
registration) date is not available at the time of signing, thus making it
impossible to put am unambiguous reference to the public key into the
signature.

4. More generally, creation time does not belong to the key packet.

Because it is just an attribute of the key as any other, thus belonging to
certificatiton signature sub-packets, rather than the key packet.

-- 
Daniel

To: [email-masked]
Subject: Re: Bigger DSA keys
Date: Mon, 19 Sep 2005 18:44:29 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

As far as the issue of generating large DSA keys, a good algorithm to
use is the following.  First generate an appropriately sized subgroup
prime q (160, 224, or 256 bits respectively).  Then search for a prime
modulus p of the required size (1024, 2048 or 3072 bits) such that p is
one more than a multiple of q.

The trick is to make that second search fast.  Typically a fast prime
search is done in two phases: first sieving out multiples of small primes
to identify prime candidates, then a slower probabilistic primality test
to find a good prime.  The key for DSA keys is that sieving can still
be used even when looking for primes which are of the form qk+1.

Usually when sieving is done, the method already takes into consideration
that the prime must be odd.  So it already adjusts for the fact that the
number is of the form 2k+1.  The same basic approach works for primes
of the form qk+1 as well.  Since q is relatively prime to all of the
primes being sieved by, for a prime "j" we will eliminate every jth item.
The only question is where is the starting point for eliminating such
items in the sieve.  This comes down to computing q mod j.  Doing this
one extra step for each prime j being sieved by, allows the basic sieve
concept to still be used.

This method allows DSA primes to be found about as quickly as ordinary
primes of the same size.  The extra time to find the q prime is small,
and the sieve can run about as fast.  So generating such large primes
is not particularly costly or difficult.

In contrast, finding "strong" primes p such that (p-1)/2 is also prime
does tend to be slow.  I think there is a trick to do it using a double
sieve but it is still much slower than finding regular primes.  DSA
primes do not suffer from this deficiency.

Hal

To: OpenPGP <[email-masked]>
From: Jon Callas <[email-masked]>
Subject: Interop grill-off
Date: Mon, 19 Sep 2005 14:05:19 -0700
Sender: [email-masked]

I think it would be good for us to have some sort of interoperability  
test and event. Putting on my PGP Corporation hat, I'm happy to  
sponsor it. However, it doesn't *have* to be a physical event. Does  
anyone else think it would be a good idea? Does anyone want to help  
put it on, come up with test cases, that sort of thing?

     Jon

Cc: [email-masked]
From: Jon Callas <[email-masked]>
Subject: Re: Bigger DSA keys
Date: Mon, 19 Sep 2005 10:59:54 -0700
To: Hal Finney <[email-masked]>
Sender: [email-masked]

On 16 Sep 2005, at 3:41 PM, Hal Finney wrote:

>
> I have it on good authority that NIST will be announcing larger size
> DSS keys soon.  According to my source, the date will be by the end
> of October.
>

We've been waiting for this for years.

I think it's important enough to warrant a change in last call for.

     Jon

From: [email-masked]
Date: Mon, 19 Sep 2005 19:34:20 +0200
To: [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

On Mon, Sep 19, 2005 at 04:45:31PM +0200, Werner Koch wrote:
> 
> On Mon, 19 Sep 2005 09:01:37 -0400, David Shaw said:
> 
> > So at least from the graceful failure perspective in GnuPG, it doesn't
> > really matter much which way we go.  I prefer the first option (using
> > the current algorithm number) since it seems cleanest in both code and
> 
> However this does also means that another hash algorithm needs to be a
> MUST algorithm - unless we limit the MUST support for DSA to 1024 bits
> keys.
> 
> The need for another algorithm makes a big difference for emdedded
> applications.  Ofen the threat model does not require
> high budget spook proof algorithms.

I fully agree with that. I would limit the MUST support to plain old SHA1
and 1024bit DSA for the time being.

-- 
Daniel

From: [email-masked]
Date: Mon, 19 Sep 2005 19:34:20 +0200
To: Werner Koch <[email-masked]>
Subject: Re: Bigger DSA keys
Sender: [email-masked]

On Mon, Sep 19, 2005 at 04:45:31PM +0200, Werner Koch wrote:
> 
> On Mon, 19 Sep 2005 09:01:37 -0400, David Shaw said:
> 
> > So at least from the graceful failure perspective in GnuPG, it doesn't
> > really matter much which way we go.  I prefer the first option (using
> > the current algorithm number) since it seems cleanest in both code and
> 
> However this does also means that another hash algorithm needs to be a
> MUST algorithm - unless we limit the MUST support for DSA to 1024 bits
> keys.
> 
> The need for another algorithm makes a big difference for emdedded
> applications.  Ofen the threat model does not require
> high budget spook proof algorithms.

I fully agree with that. I would limit the MUST support to plain old SHA1
and 1024bit DSA for the time being.

-- 
Daniel

Date: Mon, 19 Sep 2005 11:08:07 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Bigger DSA keys
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Mon, Sep 19, 2005 at 04:45:31PM +0200, Werner Koch wrote:
> 
> On Mon, 19 Sep 2005 09:01:37 -0400, David Shaw said:
> 
> > So at least from the graceful failure perspective in GnuPG, it doesn't
> > really matter much which way we go.  I prefer the first option (using
> > the current algorithm number) since it seems cleanest in both code and
> 
> However this does also means that another hash algorithm needs to be a
> MUST algorithm - unless we limit the MUST support for DSA to 1024 bits
> keys.

Yes.  I'm not against limiting the MUST support to 1024/160 DSA.

David

To: [email-masked]
Subject: Re: Bigger DSA keys
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Mon, 19 Sep 2005 16:45:31 +0200
Sender: [email-masked]

On Mon, 19 Sep 2005 09:01:37 -0400, David Shaw said:

> So at least from the graceful failure perspective in GnuPG, it doesn't
> really matter much which way we go.  I prefer the first option (using
> the current algorithm number) since it seems cleanest in both code and

However this does also means that another hash algorithm needs to be a
MUST algorithm - unless we limit the MUST support for DSA to 1024 bits
keys.

The need for another algorithm makes a big difference for emdedded
applications.  Ofen the threat model does not require
high budget spook proof algorithms.

Shalom-Salam,

   Werner

Date: Mon, 19 Sep 2005 09:01:37 -0400
From: David Shaw <[email-masked]>
To: [email-masked]
Subject: Re: Bigger DSA keys
Mail-Followup-To: [email-masked]
OpenPGP: id=99242560; url=http://www.jabberwocky.com/david/keys.asc
Sender: [email-masked]

On Fri, Sep 16, 2005 at 03:41:13PM -0700, "Hal Finney" wrote:

> One issue is how best to incorporate these new key sizes.  As I see it,
> there are three alternatives.
> 
> 1. Just use the new sizes with the existing DSA keys.  Instead of only
> 512-1024 bits, let DSA keys also be 2048 and 3072 bits, and enforce the
> proper hash algorithms in software.
> 
> 2. Use a new algorithm ID for the new DSA keys, which would be only
> for 2048 and 3072 bits.  The old algorithm ID would continue to be
> used for old DSA keys.
> 
> 3. Use a new key packet version number for the new DSA keys, V5.
> Perhaps V5 keys could use a SHA-256 based fingerprint.  This would
> represent a clean break from the old way.
> 
> The first alternative would involve the least change to the spec, just
> changes to the information about how to sign and verify with DSA keys.
> The second alternative would require adding much the same material
> but with the handling of the new algorithm ID called out separately.
> It would probably duplicate some of the information on old-style DSA keys.
> 
> The third alternative is the most ambitious and is not feasible for
> RFC2440bis IMO.  We could still go to a V5 key packet at some point in
> the future anyway, and perhaps do other improvements at that time.

I am a big fan of V5 keys (see
http://www.imc.org/ietf-openpgp/mail-archive/msg09274.html), and I
love the clean break, but I feel that if the new DSA was tied to V5
then discussions and design for a good V5 key format would delay
availability of the new DSA in the field for an excessively long
amount of time.  People have been asking for a better DSA for a long
time now, so it seems a shame to delay it further.  I'm all for
planning V5 of course, just not tied to the new DSA.

> Between the first two, I would propose to decide largely on the basis of
> backwards compatibility.  Obviously signatures made with new-style DSA
> keys will not be verifiable in old code.  The question is how gracefully
> existing implementations will fail when presented with such keys and
> signatures, in either the first or second form.  Testing on current
> implementations could provide guidance as to which way of making the
> change will cause the least trouble.

Presuming that the size of q will change from 160 to 224 or 256 in the
new key, importing a DSA key to GnuPG with the current algorithm
number and a q that is not 160 bits or importing a new-style DSA key
with a new algorithm number fails more or less gracefully in either
case.

So at least from the graceful failure perspective in GnuPG, it doesn't
really matter much which way we go.  I prefer the first option (using
the current algorithm number) since it seems cleanest in both code and
standard.

David

To: Ian G <[email-masked]>
Cc: Ben Laurie <[email-masked]>, Hal Finney <[email-masked]>, [email-masked]
Subject: Re: Bigger DSA keys
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Mon, 19 Sep 2005 10:32:25 +0200
Sender: [email-masked]

On Sun, 18 Sep 2005 14:52:45 +0100, Ian G said:

>> How about because generating 2048 bit primes already takes long
>> enough, and 3072 takes ages?

> Numbers?

A quick test shows about 4 seconds for 2048 bit and 21 seconds for
3072.  However this includes the time required to gather enough
randomness; further tests took much longer very likely due to a lack
of entropy in the machine.  Most applications don't need to generate
keys very ofthen, thus this should not be a problem.

OTOH, verification is used very often.  Here are number from
Libgcrypt:

DSA 100 times    sign  verify
-----------------------------
DSA 1024/160    910ms   430ms
DSA 2048/224   1560ms  1890ms
DSA 3072/256   3610ms  4380ms

(The numbers for sign are not very reliable because it employs the
RNG and I could not adjust for it)

3072 takes more more than double the time of 2048 which is not too
bad.  Compared to 1024 this is a real slowdown and would make key
signature verification a very time consuming operation.  On slow
machines (embedded devices, older hardware) this would be very
annoying.

Shalom-Salam,

   Werner

Date: Sun, 18 Sep 2005 14:47:38 +0200
To: [email-masked]
Subject: Re: Bigger DSA keys
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Fri, Sep 16, 2005 at 03:41:13PM -0700, "Hal Finney" wrote:

> The new DSS keys will, according to what I have heard, be for two sizes:
> 2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
> (SHA-224 is not presently an OpenPGP algorithm; it is basically a
> truncated version of SHA-256 with a different internal initial value).
> This will allow for larger keys and use a different hash than SHA-1.

For this reason, I'd agree with Ian and just ignore the 2048/224 key
specification. Too much trouble for no gain.

> 1. Just use the new sizes with the existing DSA keys.  Instead of only
> 512-1024 bits, let DSA keys also be 2048 and 3072 bits, and enforce the
> proper hash algorithms in software.

I like this solution. If old implementations do not do very silly things
when encountering such signatures (e.g. claiming them to be bad signatures
as opposed to unverifiable), it is the cleanest way to go about it.

> 2. Use a new algorithm ID for the new DSA keys, which would be only
> for 2048 and 3072 bits.  The old algorithm ID would continue to be
> used for old DSA keys.

This approach would eat up the algorithm identifier space and provide very
little advantage. It is reasonable to expect new DSS key specifications
every decade, if NIST continues its current practices.

> 3. Use a new key packet version number for the new DSA keys, V5.
> Perhaps V5 keys could use a SHA-256 based fingerprint.  This would
> represent a clean break from the old way.

Let's wait with that. There are several problems with the v4 key formats and
using SHA-256 for fingerprinting is not necessarily a good idea, given that
its design is quickly becoming obsolete. 

> Between the first two, I would propose to decide largely on the basis of
> backwards compatibility.  Obviously signatures made with new-style DSA
> keys will not be verifiable in old code.  The question is how gracefully
> existing implementations will fail when presented with such keys and
> signatures, in either the first or second form.  Testing on current
> implementations could provide guidance as to which way of making the
> change will cause the least trouble.

That's a very reasonable suggestion.

-- 
Daniel

Date: Sun, 18 Sep 2005 14:34:39 +0200
To: [email-masked]
Subject: Re: Bigger DSA keys
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

It's important to keep in mind that DSS-style signatures are twice the hash
size. This is one of their nicest features; they do not grow with the
modulus. A signature of a 3072/256 key will be 512 bits (plus overhead).

As for generating long modulae, it's not that big a problem, altough it has
to be noted that generating a modulus for DSA takes more than just
generating a prime that big; DSA moduli p are such that p-1 is divisible by
some large (hash-sized) q. The generation of such moduli takes substantially
longer than generating primes. For 3072/256 on a 500MHz intel, it would take
approx. three minutes, provided that the random stream is available without
waiting.

On the other hand, the overwhelming majority of DSS implementations use
pre-calculated moduli, as there are no security hazards associated with
using a common modulus for DSS. When keys need to be generated frequently,
a pre-calculated modulus is the way to go. If one just needs to generate a
personal signature key for the next five years, one can wait three minutes,
in case they want to show off a self-generated modulus.

-- 
Daniel

Date: Sun, 18 Sep 2005 13:10:30 +0100
From: Ben Laurie <[email-masked]>
To: Ian G <[email-masked]>
CC: Hal Finney <[email-masked]>, [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Ian G wrote:
> Ben Laurie wrote:
> 
>> Ian G wrote:
>>
>>> Hal Finney wrote:
>>>
>>>> The new DSS keys will, according to what I have heard, be for two 
>>>> sizes:
>>>> 2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
>>>> (SHA-224 is not presently an OpenPGP algorithm; it is basically a
>>>> truncated version of SHA-256 with a different internal initial value).
>>>> This will allow for larger keys and use a different hash than SHA-1.
>>>
>>>
>>>
>>> (assuming we do it,) I would suggest we ditch the 2048/224
>>> and just implement the 3072/256.
>>>
>>> (We could add the other one as a MAY ... but I can't see
>>> the point of it.  Sure NIST may split hairs on it, but
>>> let's save ourselves the doco and the discussion and
>>> just do the better one.)
>>
>>
>>
>> How about because generating 2048 bit primes already takes long 
>> enough, and 3072 takes ages?
> 
> 
> Numbers?

I was going to provide them, but accurate numbers for DSA is difficult, 
because it requires modifying the core code in OpenSSL (or some other 
DSA generator), and I couldn't be bothered.

One can get a feel for it with:

time openssl gendh <number of bits>

which takes a long time. Long enough that I didn't wait for it to finish 
before hitting send.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

Date: Sun, 18 Sep 2005 14:52:45 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: Ben Laurie <[email-masked]>
Cc: Hal Finney <[email-masked]>, [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Ben Laurie wrote:
> Ian G wrote:
> 
>> Hal Finney wrote:
>>
>>> The new DSS keys will, according to what I have heard, be for two sizes:
>>> 2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
>>> (SHA-224 is not presently an OpenPGP algorithm; it is basically a
>>> truncated version of SHA-256 with a different internal initial value).
>>> This will allow for larger keys and use a different hash than SHA-1.
>>
>>
>> (assuming we do it,) I would suggest we ditch the 2048/224
>> and just implement the 3072/256.
>>
>> (We could add the other one as a MAY ... but I can't see
>> the point of it.  Sure NIST may split hairs on it, but
>> let's save ourselves the doco and the discussion and
>> just do the better one.)
> 
> 
> How about because generating 2048 bit primes already takes long enough, 
> and 3072 takes ages?

Numbers?

iang

Date: Sun, 18 Sep 2005 12:27:15 +0100
From: Ben Laurie <[email-masked]>
To: Ian G <[email-masked]>
CC: Hal Finney <[email-masked]>, [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Ian G wrote:
> Hal Finney wrote:
>> The new DSS keys will, according to what I have heard, be for two sizes:
>> 2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
>> (SHA-224 is not presently an OpenPGP algorithm; it is basically a
>> truncated version of SHA-256 with a different internal initial value).
>> This will allow for larger keys and use a different hash than SHA-1.
> 
> (assuming we do it,) I would suggest we ditch the 2048/224
> and just implement the 3072/256.
> 
> (We could add the other one as a MAY ... but I can't see
> the point of it.  Sure NIST may split hairs on it, but
> let's save ourselves the doco and the discussion and
> just do the better one.)

How about because generating 2048 bit primes already takes long enough, 
and 3072 takes ages?

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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

To: [email-masked]
Subject: Re: Bigger DSA keys
Date: Sat, 17 Sep 2005 17:13:03 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Ian Grigg writes:
> (assuming we do it,) I would suggest we ditch the 2048/224
> and just implement the 3072/256.
>
> (We could add the other one as a MAY ... but I can't see
> the point of it.  Sure NIST may split hairs on it, but
> let's save ourselves the doco and the discussion and
> just do the better one.)
> ...
> I don't think it is that easy.  SHAs are under a cloud,
> and until we get some more definitive info on the new
> hardware factoring, even the numbers suggested above
> won't satisfy all the extremists.  Consider that the
> extreme community considers 4096 to be a minimum, and
> all the news is supporting them at the moment;  also,
> NIST's hash work has been controversial (SHA0, SHA2
> being just an "extension" ...), I'd like to see what
> the crypto community comes up with in hash research as
> that feeds into DSS.

I'm not sure why there is not a plan for larger key sizes.  A possible
clue is in this NIST document, "Recommendation for Key Management",
http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf .
Table 2 on page 63 shows the following correspondences between hash size
and modulus size: 160/1024; 224/2048; 256/3072; 384/7680; and 512/15360.

This fits what we know, with SHA-1 and a 1024 bit modulus as the
traditional DSS; SHA-224 and a 2048 bit modulus, and SHA-256 and a 3072
bit modulus in this new DSS that I have been told about.  It implies that
the natural next size would be SHA-384 and a 7680 bit modulus.  But that
modulus is too big for most people's convenience.

You might say, just use SHA-384 and a 4096 bit modulus, but that is not
such a nice fit.  The hash is a lot stronger than the modulus and so it
is not well balanced.  Perhaps such esthetic considerations motivated
NIST's decision.

Hal Finney

Date: Sun, 18 Sep 2005 00:46:17 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: Hal Finney <[email-masked]>
Cc: [email-masked]
Subject: Re: Bigger DSA keys
Sender: [email-masked]

Hal Finney wrote:

> The new DSS keys will, according to what I have heard, be for two sizes:
> 2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
> (SHA-224 is not presently an OpenPGP algorithm; it is basically a
> truncated version of SHA-256 with a different internal initial value).
> This will allow for larger keys and use a different hash than SHA-1.

(assuming we do it,) I would suggest we ditch the 2048/224
and just implement the 3072/256.

(We could add the other one as a MAY ... but I can't see
the point of it.  Sure NIST may split hairs on it, but
let's save ourselves the doco and the discussion and
just do the better one.)

> If this report is correct, it would be good to see these new key sizes
> in RFC2440bis.  Otherwise the DSS support in the spec will be essentially
> "dead on arrival".  Rather than publishing a spec with a major class
> of keys that has no future utility, I think it makes sense to wait six
> weeks and see if we can incorporate the new information, making the
> spec much more robust and long-lasting.

I don't think it is that easy.  SHAs are under a cloud,
and until we get some more definitive info on the new
hardware factoring, even the numbers suggested above
won't satisfy all the extremists.  Consider that the
extreme community considers 4096 to be a minimum, and
all the news is supporting them at the moment;  also,
NIST's hash work has been controversial (SHA0, SHA2
being just an "extension" ...), I'd like to see what
the crypto community comes up with in hash research as
that feeds into DSS.

Which rambling means to say that even after the October
date, I suspect it will be all too easy to say "let's
wait a bit more..."

> For those who say we have waited too long already, I will just note that
> the weeks and months drift by without much reason for delay but without
> much progress either.  Now that there is a good reason to hold off a
> bit more, I would hate to see us suddenly rush to close the door.
> 
> One issue is how best to incorporate these new key sizes.  As I see it,
> there are three alternatives.
> 
> 1. Just use the new sizes with the existing DSA keys.  Instead of only
> 512-1024 bits, let DSA keys also be 2048 and 3072 bits, and enforce the
> proper hash algorithms in software.
> 
> 2. Use a new algorithm ID for the new DSA keys, which would be only
> for 2048 and 3072 bits.  The old algorithm ID would continue to be
> used for old DSA keys.

I think I'd lean towards this one.  This would allow
us to deprecate DSA-old just as soon as we can.

> 3. Use a new key packet version number for the new DSA keys, V5.
> Perhaps V5 keys could use a SHA-256 based fingerprint.  This would
> represent a clean break from the old way.

I'd go against this (for the same reason you
outline below).

> The first alternative would involve the least change to the spec, just
> changes to the information about how to sign and verify with DSA keys.
> The second alternative would require adding much the same material
> but with the handling of the new algorithm ID called out separately.
> It would probably duplicate some of the information on old-style DSA keys.

Ah, good point.  But unless by some miracle all the
implementations can handle #1 without blowing up,
then I can't see how we'd countenance an incompatible
change?

> The third alternative is the most ambitious and is not feasible for
> RFC2440bis IMO.  We could still go to a V5 key packet at some point in
> the future anyway, and perhaps do other improvements at that time.

Right.

> Between the first two, I would propose to decide largely on the basis of
> backwards compatibility.  Obviously signatures made with new-style DSA
> keys will not be verifiable in old code.  The question is how gracefully
> existing implementations will fail when presented with such keys and
> signatures, in either the first or second form.  Testing on current
> implementations could provide guidance as to which way of making the
> change will cause the least trouble.

Certainly interesting times for DSS fans.  I use it
in a lot of my stuff and have pretty much made up my
mind to move to RSA when and as I can.  Mostly this
is because NIST have moved too little, too late on
this one, and the numbers above are already looking
like we'll be into a change again in about 2-3 years
when the new Hash research settles into a new generation
of algorithms.

iang

To: [email-masked]
Subject: Bigger DSA keys
Date: Fri, 16 Sep 2005 15:41:13 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

I have it on good authority that NIST will be announcing larger size
DSS keys soon.  According to my source, the date will be by the end
of October.

Currently, DSS keys have two problems.  First, they can be no bigger
than 1024 bits.  Recent results show that keys of this size can no
longer be considered safe from large scale attackers.  See for example
http://lists.virus.org/cryptography-0509/msg00080.html (although this
is for RSA keys, DSS keys of a similar size are not thought to be too
much more difficult).  Second, DSS keys are locked into using SHA-1,
for which attacks have been published.

The new DSS keys will, according to what I have heard, be for two sizes:
2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
(SHA-224 is not presently an OpenPGP algorithm; it is basically a
truncated version of SHA-256 with a different internal initial value).
This will allow for larger keys and use a different hash than SHA-1.

If this report is correct, it would be good to see these new key sizes
in RFC2440bis.  Otherwise the DSS support in the spec will be essentially
"dead on arrival".  Rather than publishing a spec with a major class
of keys that has no future utility, I think it makes sense to wait six
weeks and see if we can incorporate the new information, making the
spec much more robust and long-lasting.

For those who say we have waited too long already, I will just note that
the weeks and months drift by without much reason for delay but without
much progress either.  Now that there is a good reason to hold off a
bit more, I would hate to see us suddenly rush to close the door.

One issue is how best to incorporate these new key sizes.  As I see it,
there are three alternatives.

1. Just use the new sizes with the existing DSA keys.  Instead of only
512-1024 bits, let DSA keys also be 2048 and 3072 bits, and enforce the
proper hash algorithms in software.

2. Use a new algorithm ID for the new DSA keys, which would be only
for 2048 and 3072 bits.  The old algorithm ID would continue to be
used for old DSA keys.

3. Use a new key packet version number for the new DSA keys, V5.
Perhaps V5 keys could use a SHA-256 based fingerprint.  This would
represent a clean break from the old way.

The first alternative would involve the least change to the spec, just
changes to the information about how to sign and verify with DSA keys.
The second alternative would require adding much the same material
but with the handling of the new algorithm ID called out separately.
It would probably duplicate some of the information on old-style DSA keys.

The third alternative is the most ambitious and is not feasible for
RFC2440bis IMO.  We could still go to a V5 key packet at some point in
the future anyway, and perhaps do other improvements at that time.

Between the first two, I would propose to decide largely on the basis of
backwards compatibility.  Obviously signatures made with new-style DSA
keys will not be verifiable in old code.  The question is how gracefully
existing implementations will fail when presented with such keys and
signatures, in either the first or second form.  Testing on current
implementations could provide guidance as to which way of making the
change will cause the least trouble.

Hal Finney

To: [email-masked]
Subject: Re: Any SHA-1 dependencies?
Date: Thu, 15 Sep 2005 19:33:25 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Daniel Nagy writes:
> Basically, what you are proposing is a sort of universal hash function,
> where the hash algorithm identifier is followed by the hash computed using
> that particular algorithm.
>
> This is potentially very dangerous, as it does not follow several
> assumptions about a good hash function. Namely the hash value is not
> unique and parts of the hash function are not uniformly strong.

I agree that is one way to look at it.  In a hypothetical future key
fingerprint system, there would be multiple kinds: a SHA-1 fingerprint,
a SHA256 fingerprint, a RIPEMD160 fingerprint, and so on.  So it is
non-unique.  The idea is that if SHA-1 or some other hash became broken,
the other kinds of fingerprints could be used, without revising the spec.
Of course an attacker could replace a fingerprint with one based on an
old, weak hash, but it would ultimately be up to the verifier to decide
which hashes he would trust.

In the event of a break, switching over to a new hash would be a
potentially costly operation but it would not require issuing a new spec.
I'm not sure what dangers you see over a system which would require
changing both implementations and specifications.

> On the other hand, there is a fair chance that SHA1 (and even MD5, though
> its 128 bit length is a problem by itself) might be fixed. The known
> collision attacks are based on collisions in the compression function
> and it seems that in both cases the set of "problematic" blocks is actually
> very sparse and easily detectable. This allows for several security
> improvements: first, (and it has already been done, AFAIK) one can
> immediately detect a data stream as one that is likely to be an
> attempted attack on the hash function, second, one might create a "fixed"
> compression function that does something different for problematic blocks,
> thus yielding a hash function that gives the same output as SHA1 for the
> vast majority of inputs, while being resistant against SHA1 collisions.
>
> The detection result is very likely to be presented at Eurocrypt2006, and
> there's a chance that the fix will be presented too.

I will look forward to seeing that.  I wonder if it might be discussed
at the NIST Halloween "hash bash", it sounds like it would be of great
interest there.

Without knowing the details it is hard to comment, but in general I
would worry that any detection system might be "brittle" and possibly
small changes to the attack method might bypass the detector while still
producing collisions (perhaps somewhat more expensively).  For example
the Wang attacks always use the same initial differential, but there
is no reason they could not work with slightly different differentials,
I think.  She chose the best one but I gather that there are others that
weren't too bad.  A detection system tuned too closely to known attacks
might miss these alternatives.

> The sparsity of problematic blocks also implies (although this is not
> strictly within the scope of the discussion) that key-id binding signatures
> might collide only on the key part (*), which is not dangerous. If the above
> mentioned sanity check is performed, it removes even the non-dangerous key
> collision as a possibility.

I also remember Eli Biham last year at Crypto demonstrating very textual
looking collisions on truncated SHA-1.  His collisions were composed
of ascii characters and even English words.  Granted, truncation makes
a world of difference in the ease of the attack but I wonder if we can
be sure that the full SHA-1 attacks can never be improved in this way.

> Also remember, that collisions are of concern only if the data is to be signed by
> someone different from its author. There are protocol-level safeguards
> against this possibility, though employing these would require a major
> overhaul of OpenPGP, which in the light of the above is not warranted (yet).
> Someday, however, we might very well be forced to introduce version 5
> signatures for certification and other notarial purposes. It is better to
> postpone that as long as possible, because important discoveries with
> immediate consequencnes on design and standardization decisions might lay ahead.

Yes, there have been strong debates in online forums for example about
changing signature procedures so that the signer prepends a block of
data of his choice to the message to be signed, in case the message is
prepared by someone else.  There seems to be no consensus on whether
this is on balance a good idea or not.

> So, I would recommend sticking to SHA1 for the time being, as there is no
> hash function with a better design at this point. Alternatives that belong
> to the same MD4 family of hash functions (e.g. the now-fashionable
> RIPEMD-160) have not been attacked only because SHA1 was a more rewarding
> target.

I didn't recommend stopping using SHA-1.  In fact my only actual
recommendation was to include SHA256 as another MUST hash, in case SHA-1
gets broken more badly (and in the hope that SHA256 will be OK).

> Now, moving to 256-bit hash functions in order to have a built-in "safety
> factor" keeping the hash-function safe even if it's partially broken, seems
> to be inconsistent with market-economies. In our case it is particularly
> relevant, because the standard we are designing is not enforced, leaving the
> choice to the user.

In general, though, it is risky to use non-MUST hashes in your
signatures, for interoperability reasons.  Of course we have only limited
leverage over this via the spec, and as you note the market may force
implementations to move to SHA256 regardless of whether it is MUST or not.

[Skipping on a bit]

> Back on topic, this is why I would advise against moving to 256-bit hashes
> based on the MD4 design. Yes, it would add some security against hypotetical
> ultra-motivated adversaries flush with resources, but you are interested in
> these not because they are actually threats but because you are catering to
> paranoid customers. Those would sneer at a partially broken SHA256 just as
> they sneer at a partially broken SHA1. So, you will have to switch again
> very soon, without gaining anything from the previous switch. It's not
> rational behavior, especially in standardization.

So, are you predicting that SHA256 will have at least theoretical breaks
of its own?  The people I have talked to seem quite non-committal about
this prospect.  No one can rule it out but most people say it should be
stronger than SHA-1 and more resistant to this kind of attack.

> Thus, my recommendation would be to postpone the discussion until more is
> known, to avoid swift moves and stick to SHA1 for the time being. Maybe a
> footnote would be warranted to explain why it's still safe to do things the
> way we do them.

Again, the only thing I recommended was to add SHA256 as a MUST.  The only
MUST-implement hash we have now is SHA-1.  What do you think of that change?

> Now, I have a separate set of grievances about the v4 private key packet format
> and the way v4 key fingerprints are being calculated, but that has very
> little to do with the recent developments around our once-favorite hash
> function. In a separate post, I will explain why I would like to introduce a
> new version of key packets (both public and private), and once we embark on
> designing new packet formats, we can address the use of hash functions in
> that context as well, but again, it's a separate topic.

I have another change to suggest as well, which will also go into a future
message.

Thanks for your comments, they are very interesting and helpful.

Hal Finney

Date: Fri, 16 Sep 2005 03:26:25 +0200
To: [email-masked]
Subject: Re: Any SHA-1 dependencies?
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

Hal,

Basically, what you are proposing is a sort of universal hash function,
where the hash algorithm identifier is followed by the hash computed using
that particular algorithm.

This is potentially very dangerous, as it does not follow several
assumptions about a good hash function. Namely the hash value is not
unique and parts of the hash function are not uniformly strong.

On the other hand, there is a fair chance that SHA1 (and even MD5, though
its 128 bit length is a problem by itself) might be fixed. The known
collision attacks are based on collisions in the compression function
and it seems that in both cases the set of "problematic" blocks is actually
very sparse and easily detectable. This allows for several security
improvements: first, (and it has already been done, AFAIK) one can
immediately detect a data stream as one that is likely to be an
attempted attack on the hash function, second, one might create a "fixed"
compression function that does something different for problematic blocks,
thus yielding a hash function that gives the same output as SHA1 for the
vast majority of inputs, while being resistant against SHA1 collisions.

The detection result is very likely to be presented at Eurocrypt2006, and
there's a chance that the fix will be presented too.

The sparsity of problematic blocks also implies (although this is not
strictly within the scope of the discussion) that key-id binding signatures
might collide only on the key part (*), which is not dangerous. If the above
mentioned sanity check is performed, it removes even the non-dangerous key
collision as a possibility.

Also remember, that collisions are of concern only if the data is to be signed by
someone different from its author. There are protocol-level safeguards
against this possibility, though employing these would require a major
overhaul of OpenPGP, which in the light of the above is not warranted (yet).
Someday, however, we might very well be forced to introduce version 5
signatures for certification and other notarial purposes. It is better to
postpone that as long as possible, because important discoveries with
immediate consequencnes on design and standardization decisions might lay ahead.

So, I would recommend sticking to SHA1 for the time being, as there is no
hash function with a better design at this point. Alternatives that belong
to the same MD4 family of hash functions (e.g. the now-fashionable
RIPEMD-160) have not been attacked only because SHA1 was a more rewarding
target.

Now, moving to 256-bit hash functions in order to have a built-in "safety
factor" keeping the hash-function safe even if it's partially broken, seems
to be inconsistent with market-economies. In our case it is particularly
relevant, because the standard we are designing is not enforced, leaving the
choice to the user.

The thing is that partially broken security products are a tough sell even if
the remaining part is still secure enough. It is pretty clear from your
post that you _are_ concerned about this. Let me digress a bit:

In the USSR, it was okay to slash development costs by building in safety
factors, so that even if the hash function or the block cipher turned out to
be weaker than the designers originally thought, they would be still secure
enough. Hence the 256-bit key length of the standard soviet block cipher
(GOST 28147-89) which also doubles as the compression function of their
standard hash function (standardized later as GOST 34.11-94). For government
use (**) and for use in a planned economy this was the most rational way of
designing the system: quick, cheap and a little dirty. In market economies,
this approach won't fly, because as soon as your product is discredited by
being partially broken, you will have to switch anyway, so cheap development
with safety factors won't save you money in the long run. Hence, it's not a
rational approach to cryptographic algorithm design and indeed, we don't see
it in successful products in the free market. It is important to emphasize
that it is not because your customers are somehow dumber in a market economy
but because in addition to your development costs, they also have to bear
the cost of choosing the right product for themselves (this cost does not
occur in planned economies -- in certain cases, it can be a significant
saving), and they are rational about minimizing it by not touching anything
that has been discredited in any way -- they simply cannot afford to behave
otherwise (in most cases).

Back on topic, this is why I would advise against moving to 256-bit hashes
based on the MD4 design. Yes, it would add some security against hypotetical
ultra-motivated adversaries flush with resources, but you are interested in
these not because they are actually threats but because you are catering to
paranoid customers. Those would sneer at a partially broken SHA256 just as
they sneer at a partially broken SHA1. So, you will have to switch again
very soon, without gaining anything from the previous switch. It's not
rational behavior, especially in standardization.

Thus, my recommendation would be to postpone the discussion until more is
known, to avoid swift moves and stick to SHA1 for the time being. Maybe a
footnote would be warranted to explain why it's still safe to do things the
way we do them.

Now, I have a separate set of grievances about the v4 private key packet format
and the way v4 key fingerprints are being calculated, but that has very
little to do with the recent developments around our once-favorite hash
function. In a separate post, I will explain why I would like to introduce a
new version of key packets (both public and private), and once we embark on
designing new packet formats, we can address the use of hash functions in
that context as well, but again, it's a separate topic.

(*) It is impossible to trick someone into binding a sane-looking unseen UID
to a given public key by presenting him with another sane-looking UID that
would collide with the unseen one for signature.

(**) There is evidence suggesting that the mentioned algorithms were in
government use long before having been released to the public as industry
standards. Probably since the early eighties or even earlier.

Bests,

-- 
Daniel

To: [email-masked]
Subject: Any SHA-1 dependencies?
Date: Thu, 15 Sep 2005 15:58:58 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

There are a few places in the OpenPGP spec where we hard-code the use of
the SHA-1 hash.  Given the recent attacks on this hash, we should look
and see if there will be any security weaknesses if it should turn out
that SHA-1 is broken and it becomes easier to generate collisions.

This is actually a pretty complicated issue and it becomes something of a
"can of worms" situation, ie. there are many complexities and subtleties
that arise in the analysis.  Here are some:

 - We don't know how badly SHA-1 might be broken.  Current attacks can
   theoretically generate limited sorts of collisions in (at last
   report) about 2^64 work.  Perhaps this work level will be lowered.
   Perhaps the limitations on collisions may be reduced.  Perhaps even
   more powerful attacks such as preimage attacks (to find data that
   matches the hash of a given value) will become possible.

 - Any hash algorithm might in principle be broken eventually.  A spec
   like OpenPGP can at best allow a choice of hash algorithms.  However
   even then it will be necessary for communicators to decide which
   hash algorithms they trust.  If someone loses confidence in a hash
   algorithm while others are still using it, interoperability is lost.

My approach to these problems is to assume that SHA-1 will be broken
to the extent that collisions can be found with moderate effort, even
collisions with particular structures.  However, preimages will not be
possible.  I think this is a conservative assumption given what is known
about the new attacks.  As far as the second issue, I will outline places
where we hard-code SHA-1, and we should think about what would be involved
in trying to allow for different hash algorithms to be used in place.

Here then are the places we hard-code SHA-1 and the security implications.

5.5.3 Secret Key Packet Formats

This has the option of using a 20-byte SHA-1 hash as a checksum of the
secret key material.  This should be safe.

5.13. Sym. Encrypted Integrity Protected Data Packet (Tag 18)

This uses the SHA-1 hash of the message as a checksum for integrity.
This should be safe.

9.4. Hash Algorithms

SHA-1 is the only MUST implement hash algorithm.  I would recommend
that we include at least SHA-256 as a MUST implement algorithm, for
future security.

11.2. Key IDs and Fingerprints

A V4 key fingerprint is the SHA-1 hash of the key material.  If SHA-1
is broken then it will be possible to create two keys which have the
same fingerprint.  Any places in the spec where fingerprints are used as
pointers to keys, it will be possible for the key creator to substitute
another key he created.  Likewise, the V4 key ID is a substring of the
fingerprint so the same considerations arise.  (However, with respect to
key IDs it is an old problem, since 64 bit key IDs can be made to collide
with only 2^32 work, a very tractable amount.)  Places where fingerprints
are used:

5.2.3.15. Revocation key

The revocation key (designated revoker) is specified via key fingerprint.
This should be safe since the key holder is trusted to perform this
service, so if he created a key collision he would only be able to
transfer this power among keys he controlled.

It is not an OpenPGP issue, but PGP uses signature subpacket 10 as an
additional decryption key indicator, and this is also done via a key
fingerprint.  Similar considerations apply as for the designated
revoker.

With regard to key IDs, these are used in the following places:

5.1. Public-Key Encrypted Session Key Packets (Tag 1)

The key ID indicates which key can decrypt the message.  Ability to
create keys with colliding key IDs should not cause security problems.

5.2.2. Version 3 Signature Packet Format

The key ID of the signing key is stored in the V3 signature packet.
Ability to create keys with colliding key IDs should not cause security
problems.

5.2.3.5. Issuer

This is the V4 key ID.  Same situation as for V3.  In fact we usually
put this signature packet in the unhashed region.

5.4. One-Pass Signature Packets (Tag 4)

Same situation as above.

Summary

None of the hard-coded uses of SHA-1 in the OpenPGP spec appear to
introduce security problems, even if creating SHA-1 collisions becomes
easy.  This analysis does not cover the case of finding pre-images.

The one change we might consider is to expand the set of MUST algorithms
beyond SHA-1 since the community is shifting away from that hash.

In the longer term it would be desirable to consider parameterizing the
few places where SHA-1 is hard-coded, to take a hash algorithm specifier.
This will allow us to avoid even the appearance of weakness which may
be of concern to potential users, as SHA-1 becomes deprecated in a wide
range of products and protocols in future years.

Hal Finney

Date: Wed, 14 Sep 2005 12:10:07 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: OpenPGP <[email-masked]>
Subject: Armouring - silly fix
Sender: [email-masked]

If we haven't entered last call.

In Section 6.6 it says "is indented by two spaces"
but looks like three to me :-)  I would suggest it
say "is indented by several spaces".

============8<============================8<================
6.6. Example of an ASCII Armored Message

    -----BEGIN PGP MESSAGE-----
    Version: OpenPrivacy 0.99

    yDgBO22WxBHv7O8X7O/jygAEzol56iUKiXmV+XmpCtmpqQUKiQrFqclFqUDBovzS
    vBSFjNSiVHsuAA==
    =njUN
    -----END PGP MESSAGE-----

Callas, et al.          Expires Jan 08, 2006                  [Page 53]
^LINTERNET-DRAFT          OpenPGP Message Format             Jul 08, 2005

     Note that this example is indented by two spaces.
============8<============================8<================

iang

Date: Thu, 8 Sep 2005 01:31:25 +0200
To: [email-masked]
Subject: Re: Information and meta-information
From: [email-masked] (Daniel A. Nagy)
Sender: [email-masked]

On Wed, Sep 07, 2005 at 03:56:58PM -0700, Wim Lewis wrote:

> The existing 'b', 't', etc. tags could then be defined as shorthands  
> for particular MIME headers (content-type and charset).

I disagree, because these tags convey a slightly different (lower-level)
meaning than the mime headers. Also, the above suggestion would be a
security hazard, since the literal packet's tag is not hashed and can be
therefore altered in a signed message, without breaking the signature.
PGP/MIME headers, on the other hand, are included in the hashed material, so
they are part of the signed message.

> >I would suggest the following modification of RFC2440bis-14:
> 
> Do you mean removing the 't' and 'u' tags? Or supplementing them with  
> 'm'?

Supplementing with 'm', of course. Removing 't' and 'b' tags (what's 'u'?)
would break almost everything.

-- 
Daniel

Cc: "Daniel A. Nagy" <[email-masked]>
From: Wim Lewis <[email-masked]>
Subject: Re: Information and meta-information
Date: Wed, 7 Sep 2005 15:56:58 -0700
To: [email-masked]
Sender: [email-masked]

On 31 Aug, 2005, at 8:26 AM, Daniel A. Nagy wrote:
> There is no distinction between PGP/MIME data and regular RFC2440  
> data,
> although all it would take is a flag in the Literal packet. This  
> way, if I
> saved the PGP MESSAGE from an application/pgp-encrypted MIME chunk  
> (which is
> doable even with MUAs ignorant of PGP/MIME), I could still decrypt  
> it into a
> usable file (e.g. a jpeg image).

I have had exactly the same thought (down to the choice of an 'm' in  
that field to indicate MIME data). This seems like a good idea in  
general. It would be useful outside of PGP/MIME as well: if metadata  
such as datatype or character encoding needs to be associated with  
the PGP-protected data, it seems reasonable to piggyback on MIME,  
just as (e.g.) HTTP does.

The existing 'b', 't', etc. tags could then be defined as shorthands  
for particular MIME headers (content-type and charset).

> I would suggest the following modification of RFC2440bis-14:

Do you mean removing the 't' and 'u' tags? Or supplementing them with  
'm'?

Date: Sat, 03 Sep 2005 16:10:12 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: Derek Atkins <[email-masked]>
Cc: [email-masked]
Subject: Re: IETF-63 Proceedings Submission
Sender: [email-masked]

Derek Atkins wrote:
> Of course this didn't make it into the minutes; this messages
> happened well after the IETF met in August.  The minutes are a
> status report of the IETF meeting;  It does not take into account
> messages that have been processed *since* the IETF.

Apologies - I was confused and didn't realise
this related to a meeting back then.

iang

From: Derek Atkins <[email-masked]>
To: Ian G <[email-masked]>
Cc: [email-masked]
Subject: Re: IETF-63 Proceedings Submission
Date: Sat, 03 Sep 2005 10:01:29 -0400
Sender: [email-masked]

Of course this didn't make it into the minutes; this messages
happened well after the IETF met in August.  The minutes are a
status report of the IETF meeting;  It does not take into account
messages that have been processed *since* the IETF.

-derek

And no, we're not in final call, yet.  I need to catch up and
make sure we've handled all the open issues.  I'll see if I
can get to that this week.

Ian G <[email-masked]> writes:

> Derek Atkins wrote:
>>         - If you want changes in wording - need to be compatable and suggest text.
>>         - Only open issue is David Shaw's BNF request for literal+literal.  No reason not to include David Shaw's request, but not in draft 14.  Should go into 15
>
> I guess the below didn't make it then.  Oh well.
>
>
>
> -------- Original Message --------
> Subject: Re: Signature types
> Date: Sat, 27 Aug 2005 10:25:07 +0100
> From: Ian G <[email-masked]>
> Organization: http://financialcryptography.com/
> To: [email-masked]
> References: <[email-masked]>
>
>
> Daniel A. Nagy wrote:
>> ... [some stuff]
>
> On that section, but not on Daniel's question, it occurs to
> me that the caveat found half way down ("Please note that
> the vagueness...") could be usefully expanded to cover all
> of 5.2.1.
>
> Something like:
>
> 5.2.1. Signature Types
>
>   There are a number of possible meanings for a signature.
>   By convention, OpenPGP suggests meanings by the following
>   signature type octets in any given signature.
>
>   Please note that the vagueness of these signature claims
>   is not a flaw, but a feature of the system.  Cryptographic
>   signing technology alone cannot make these claims true,
>   and a relying party would need to examine the intentions
>   of any signer, and the wider context of the system and
>   environment in order to assess any claims.  OpenPGP places
>   final authority and responsibility on the receiver of any
>   signature.
>
>   0x01:...
>
> Which then allows a simplification of the post-0x13 comment:
>
>   0x13:...
>
>     Please note that one authority's casual certification
>     might be more rigorous than some other authority's
>     positive certification. These classifications allow a
>     certification authority to issue fine-grained claims.
>
>     Most OpenPGP implementations make their "key signatures" as 0x10
>     certifications. Some implementations can issue 0x11-0x13
>     certifications, but few differentiate between the types.
>
>
> As an alternate, such general commentary could append to the
> end of the section - but in legal terms, if it is a warning
> as to limitations, it should be at the front.  Given the
> somewhat poisoned waters of digital signatures, I'd prefer
> to see the disclaims before any claims.
>
> iang
>
> PS: are we in final call already?
>
>
>
>

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

Date: Fri, 02 Sep 2005 18:53:43 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: Derek Atkins <[email-masked]>
Cc: [email-masked]
Subject: Re: IETF-63 Proceedings Submission
Sender: [email-masked]

Derek Atkins wrote:
>         - If you want changes in wording - need to be compatable and suggest text.
>         - Only open issue is David Shaw's BNF request for literal+literal.  No reason not to include David Shaw's request, but not in draft 14.  Should go into 15

I guess the below didn't make it then.  Oh well.

-------- Original Message --------
Subject: Re: Signature types
Date: Sat, 27 Aug 2005 10:25:07 +0100
From: Ian G <[email-masked]>
Organization: http://financialcryptography.com/
To: [email-masked]
References: <[email-masked]>

Daniel A. Nagy wrote:
 > ... [some stuff]

On that section, but not on Daniel's question, it occurs to
me that the caveat found half way down ("Please note that
the vagueness...") could be usefully expanded to cover all
of 5.2.1.

Something like:

5.2.1. Signature Types

   There are a number of possible meanings for a signature.
   By convention, OpenPGP suggests meanings by the following
   signature type octets in any given signature.

   Please note that the vagueness of these signature claims
   is not a flaw, but a feature of the system.  Cryptographic
   signing technology alone cannot make these claims true,
   and a relying party would need to examine the intentions
   of any signer, and the wider context of the system and
   environment in order to assess any claims.  OpenPGP places
   final authority and responsibility on the receiver of any
   signature.

   0x01:...

Which then allows a simplification of the post-0x13 comment:

   0x13:...

     Please note that one authority's casual certification
     might be more rigorous than some other authority's
     positive certification. These classifications allow a
     certification authority to issue fine-grained claims.

     Most OpenPGP implementations make their "key signatures" as 0x10
     certifications. Some implementations can issue 0x11-0x13
     certifications, but few differentiate between the types.

As an alternate, such general commentary could append to the
end of the section - but in legal terms, if it is a warning
as to limitations, it should be at the front.  Given the
somewhat poisoned waters of digital signatures, I'd prefer
to see the disclaims before any claims.

iang

PS: are we in final call already?

From: Derek Atkins <[email-masked]>
To: [email-masked]
Cc: [email-masked]
Subject: IETF-63 Proceedings Submission
Date: Fri, 02 Sep 2005 12:22:35 -0400
Sender: [email-masked]

--=-=-=

Minutes of OpenPGP Meeting at IETF-63

-derek

--=-=-=
Content-Disposition: attachment; filename=Minutes-63.txt
Content-Description: OpenPGP Minutes

AGENDA --

-- Introduction and Agenda Bashing

         No changes 

-- 2440 bis status

        - In "pentultimate last call" for some time (over a year) - now only doing tweaks to the document.
        - If you want changes in wording - need to be compatable and suggest text.
        - Only open issue is David Shaw's BNF request for literal+literal.  No reason not to include David Shaw's request, but not in draft 14.  Should go into 15
        - Run last call and finish this document
        - Use difference documents for new work - downside is that not everything will be in a small number of documents.  Good news is that will have a fixed definitive document

--  2440 next steps
        - Go to Last call. finish by end of August
        - Try for a bake off? try for Draft Standard. (early in '06)
        - update milestones - proposal given.
        - Draft standard would be tried for 6 months after IESG approval.
        
        - New Life
        -       New documents not hit 2440bis.
        -       

-- Proposed Milestones

   Aug 05  WGLC for 2440bis
   Sep 05  Submit 2440bis to IESG as Proposed Standard
   Nov 05  Finish Interop Test Plan
   Jan 06  Begin 2440bis Interop Testing
   Mar 06  Request DRAFT Status for 2440bis

        - No Objections

--- Message Header

        - draft-josefsson-openpgp-mailnews-header-01.txt

        - standardize some X- headers for PGP.
        - Lookup URL and key id of a sender
        - simplified original by dropping some unnecessary data.
                - key id - longer fingerprint - url to key

        - What is the problem to be solved?
                - Not completely clear
                - invent header that could be used programatically to lookup key and keyid of sender
                - Manual cut & paste?
                - request for additinoal current usage of old headers for inclusion in the doument.

        - Open Issuses:
                - Add token to state strong preference for reciving PGP and potentially the PGP format to be sent.
                        - IETF process restricted to MIME?
                        - place same info into a packet?

                - Keyserver field?
                        - unsure of what this would be really for.  Next expansion of the idea.

                - BNF problems on the draft need corrections.

         Open MIKE
                JON - Supports idea of draft - supports "supports token"  - PGP has a similar item already used.  used with different values for different reading devices.

                        - Wants support to plain inline text - kill mime and only use plain text as a personal preference.

                - response - Need additional proposals to solve some of the problems?

                        JON - display problems not format issues - Don't ban text only w/o mime wrappers.
                        8-bit character set problems with servers - 
                        
                        Vigourous dispute on issues with character sets.

                        Thomas Roessler - two formats - with and w/o tag - please elimiate the untagged version.
                        
                        ??? - Please add finger print header - used for validation.

                                - possible support already?

                        JON - KeyID is a trucated fingerprint - allow for longer id to get fuller fingerprint w/o much additional parsing.  

                                - -00 to -01 allowed for longer KeyID from a fixed length.

--- Open Discussion

        - Meeting closed.

--=-=-=

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       [email-masked]                        PGP key available

--=-=-=--

To: Karl Kashofer <[email-masked]>
Cc: [email-masked]
Subject: Re: Encrypt subject
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Fri, 02 Sep 2005 09:00:00 +0200
Sender: [email-masked]

On Thu, 01 Sep 2005 20:24:54 +0100, Karl Kashofer said:

> I see what you mean, but from a practical point of view, how much PGP
> encrypted spam have you gotten lately ?

I was not talking about spam but on how to prioritize/ignore regular
mail.

Salam-Shalom,

   Werner

Date: Thu, 01 Sep 2005 20:24:54 +0100
From: Karl Kashofer <[email-masked]>
CC: [email-masked]
Subject: Re: Encrypt subject
Sender: [email-masked]

Hi !

> What I mean is that a subject you need to decrypt first is not very
> usable for the purpose a subject line is commonly used, i.e. to
> quickly decide what messages belong together and whether to read them.
> 
> With a slow connection and POP3 and with IMAP in general many people
> just look at the subject to decide whether to retrieve the entire
> message.  Requiring to decrypt it first make no sense then.

I see what you mean, but from a practical point of view, how much PGP
encrypted spam have you gotten lately ?

I assume if its encrypted it might actually be worth reading ?

> So, my suggestion is to use a non-sense subject line to merely help
> visualizing a theread.

Sure, but if enigmail were able to permanently decrypt messages this
could still be accomplished once the message is decrypted. Problem seems
to be that mozilla/thunderbird does atm not allow them to permanently
modify the message, so it might take a while to implement that anyway.

Thanks for your help,
I will carry this to the enigmail mailing list,
Cheers,
Karl

To: Karl Kashofer <[email-masked]>
Cc: [email-masked]
Subject: Re: Encrypt subject
From: Werner Koch <[email-masked]>
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Thu, 01 Sep 2005 15:48:36 +0200
Sender: [email-masked]

On Thu, 01 Sep 2005 11:15:40 +0100, Karl Kashofer said:

> Well the way Werner describes it, he just advises not to use a Subject.

What I mean is that a subject you need to decrypt first is not very
usable for the purpose a subject line is commonly used, i.e. to
quickly decide what messages belong together and whether to read them.

With a slow connection and POP3 and with IMAP in general many people
just look at the subject to decide whether to retrieve the entire
message.  Requiring to decrypt it first make no sense then.

So, my suggestion is to use a non-sense subject line to merely help
visualizing a theread.

> Could you by any means describe this in more detail ?

Something like this:

    From: [email-masked]
    To: [email-masked]
    Subject: none 
    Content-Type: multipart/encrypted; 
                  protocol=application/pgp-encrypted;
                  boundary="xxxxxx"

    --xxxxxx
    Content-Type: application/pgp-encrypted
    
    Version: 1
    
    --xxxxxx
    Content-Type: application/octet-stream
    
  & Content-Type: message/rfc822; boundary="yyyyy"
  & 
  &
  & --yyyyyy
  & From: [email-masked]
  & To: [email-masked]
  & Subject: Don't tell anyone that PGP/MIME just works
  & Content-Type: text/plain
  &
  & Proposal on how to gain world domination of PGP/MIME
  & and to abolish any use of S/MIME.
  &
  & --yyyyyy--

    --xxxxxx--

Where the lines marked by "&" are actually encrypted.

Salam-Shalom,

   Werner

To: [email-masked], [email-masked]
Subject: Re: Encrypt subject
Date: Thu,  1 Sep 2005 10:13:22 -0700 (PDT)
From: [email-masked] ("Hal Finney")
Sender: [email-masked]

Karl Kashofer writes:
> So this would adhere to the standards, and allow to embed headers inside
> the PGP encryption block ?
>
> Could you by any means describe this in more detail ?
>
> I would try to bring it to the attention of enigmail developers, maybe
> they are interested in it.

Well, PGP/MIME is http://www.ietf.org/rfc/rfc3156.txt which is based on
the MIME security extensions, http://www.ietf.org/rfc/rfc1847.txt .
The message/rfc822 type for embedding mail with headers is described in
http://www.ietf.org/rfc/rfc2046.txt section 5.2.1.

The implementation concept would be that when you decrypt a PGP/MIME
message and find that the inner type is message/rfc822, you would promote
the relevant mail headers, particularly Subject, from the inner type to
the outer message.  This might also include source information ("From"),
for example if the message were delivered via an anonymous remailer
network.  Maybe some other headers could also be usefully encrypted.

Hal Finney

Date: Thu, 01 Sep 2005 11:15:40 +0100
From: Karl Kashofer <[email-masked]>
To: [email-masked]
Subject: Re: Encrypt subject
Sender: [email-masked]

Hi !

> The problem is that we do sort of have a solution to this already, which
> Werner described: use PGP/MIME.  MIME allows for embedding one email
> message inside another, and the MIME security extensions, including
> PGP/MIME, show how to encrypt such an embedded message.

Well the way Werner describes it, he just advises not to use a Subject.

>>Simply send your mail as an encrypted message/rfc2822 MIME message and
>>put an innocent subject into the header.

> The problem is that almost no mailers support this.  Few enough even
> support PGP/MIME, and then they would also have to be smart enough to
> figure out what to do with an embedded email message.  Replacing the
> enclosing message's headers with those from the embedded message is not
> an obvious thing to do.

So this would adhere to the standards, and allow to embed headers inside
the PGP encryption block ?

Could you by any means describe this in more detail ?

I would try to bring it to the attention of enigmail developers, maybe
they are interested in it.

They have Per-Recipient-Rules, so it would be possible to implement
that, and then specify it in these rules, so its only used for
recipients which are able to decrypt it. I do that with PGP/MIME to only
use it for thunderbird recipients, works fine.

I would really like to see this implemented, and I am sure it annoys a
few other people as well.

Cheers,
Karl