Subject: RSA conf paper on PGP web of trust

From: "Hal Finney" <[email-masked]>
Date: Fri, 5 Mar 2004 10:51:24 -0800

I just noticed that a paper was published at the RSA conference with
concepts that might be relevant to the PGP web of trust.

http://discovery.csc.ncsu.edu/~pning/pubs/robust-keyrings.pdf

Improving Robustness of PGP Keyrings by Conflict Detection, by Q Jiang
et al of North Carolina State University.

One concept they discuss is the use of redundancy in the WoT.  This idea
goes back to PGP 2; you can mark introducers as partially trusted,
and then if you have two chains of trust leading to the same key, both
partial, this can add up to full validity.  We extended this internally
in later versions of PGP to support full probabilistic calculation based
on a paper by Ueli Maurer.

However a problem with this is that if a user has two keys, both marked
as partially trusted, and both sign a third key, that key can end up
as fully valid, even though only one user signed it.  Internally at
PGP.com we discussed this years ago and thought about providing a way
to indicate that one or more keys were controlled by the same user,
but the UI would be so complex that we gave up on it.  (Ironically,
the sample keyring we distributed at one point had two keys on it by the
same person, with both keys signing other keys on the keyring, so we were
setting up a situation which practically begged for this flaw to show up.)

The new paper does not use a probabilistic model, but rather assumes
that users are either malicious or reliable.  It attempts to distinguish
the two by detecting conflicts, where the same identity is bound to
two different keys.  It takes such a conflict as evidence of malicious
behavior and uses graph theory to try to figure out which keys are the
malicious ones.  These can then be eliminated from the WoT and then the
resulting signatures are taken to be correct.

There is a large literature on trust issues in WoT-like structures.
I'll see if I can find an up-to-date bibliography on the subject, or
perhaps someone here knows of one.

Hal Finney

---

From: Mike Markowitz <[email-masked]>
Date: Mon, 08 Mar 2004 16:48:31 -0600

Folks:

Since Hal just pointed to an RSA Conference paper, I thought I'd bring
attention

to an OpenPGP-related paper to be presented by Phong Nguyen at EuroCrypt
in May.

The abstract sounds like old news, but perhaps list subscribers will be
interested

anyway:

http://www.di.ens.fr/~pnguyen/pub.html#Ng04

Abstract: More and more software use cryptography. But how can
one know if what is implemented is good cryptography? For proprietary
software, one cannot say much unless one proceeds to reverse-engineering,
and history tends to show that bad cryptography is much more frequent
than good cryptography there. Open source software thus sounds like a
good solution, but the fact that a source code can be read does not imply
that it is actually read, especially by cryptography experts. In this
paper, we illustrate this point by examining the case of a basic Internet
application of cryptography: secure email. We analyze parts of the source
code of the latest version of GNU Privacy Guard (GnuPG or GPG), a free
open source alternative to the famous PGP software, compliant with the
OpenPGP standard, and included in most GNU/Linux distributions such as
Debian, MandrakeSoft, Red Hat and SuSE. We observe several cryptographic
flaws in GPG v1.2.3. The most serious flaw has been present in GPG for
almost four years: we show that as soon as one (GPG-generated) ElGamal
signature of an arbitrary message is released, one can recover the
signer's private key in less than a second on a PC. As a consequence,
ElGamal signatures and the so-called ElGamal sign+encrypt keys have
recently been removed from GPG. Fortunately, ElGamal was not GPG's
default option for signing keys.

-mjm

==========

Michael J. Markowitz, Ph.D.
Email: [email-masked]

Vice President
R&D
Voice: 708-445-1704 (Oak Park)

Information Security
Corporation
847-405-0500 (Deerfield)

1011 Lake Street, Suite 212
Fax:   708-445-9705

Oak Park, IL
60301
WWW:
http://www.infoseccorp.com

---

From: Bill Frantz <[email-masked]>
Date: Mon, 8 Mar 2004 20:26:37 -0800

At 10:51 AM -0800 3/5/04, Hal Finney wrote:
>...

Wouldn't this be a common situation if someone replaces a key for hygiene
reasons, but does not revoke the previous key (on the basis that the old
key hasn't been proven bad, and some people may not have the new one)?

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | "There's nothing so clear as a | Periwinkle
(408)356-8506      | vague idea you haven't written | 16345 Englewood Ave
www.pwpconsult.com | down yet." -- Dean Tribble     | Los Gatos, CA 95032

---

From: Ben Laurie <[email-masked]>
Date: Tue, 09 Mar 2004 12:23:26 +0000

> key hasn't been proven bad, and some people may not have the new one)?

Or, like me, where I have an RSA key and a DSA key...

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

---

From: Ian Grigg <[email-masked]>
Date: Tue, 09 Mar 2004 16:42:15 -0500

Mike Markowitz wrote:
> Folks:
> 
> Since Hal just pointed to an RSA Conference paper, I thought I'd bring attention
> to an OpenPGP-related paper to be presented by Phong Nguyen at EuroCrypt in May.

A goodly post, although the paper worries
me somewhat on two points, the second of
which may be germane to OpenPGP, further
below.

> The abstract sounds like old news, but perhaps list subscribers will be interested
> anyway:
> 
>     Abstract: More and more software use cryptography. But how can one know if
>     what is implemented is good cryptography? For proprietary software, one
>     cannot say much unless one proceeds to reverse-engineering, and history
>     tends to show that bad cryptography is much more frequent than good
>     cryptography there. Open source software thus sounds like a good solution,
>     but the fact that a source code can be read does not imply that it is
>     actually read, especially by cryptography experts. In this paper, we
>     illustrate this point by

Having read the paper here:

     ftp://ftp.di.ens.fr/pub/users/pnguyen/Eurocrypt04.ps

(at least the non heavy-crypto parts), I
think the above half-abstract is unsupported,
and probably disproven by the existence of
the paper itself.

As the paper presents no information on
anything about "good/bad cryptography"
and/or "open source" and/or "proprietary
software" and/or "reverse engineering",
it seems an out of place comment?

(As is the first paragraph of the paper
proper.)

In essence, the existence of GPG as an
open source crypto system has permitted
the author to examine the software and
find some potentially useful flaws.  That
would seem to be evidence to the contrary
of the point claimed above?

 >     examining the case of a basic Internet application
>     of cryptography: secure email. We analyze parts of the source code of the
>     latest version of GNU Privacy Guard (GnuPG or GPG), a free open source
>     alternative to the famous PGP software, compliant with the OpenPGP standard,
>     and included in most GNU/Linux distributions such as Debian, MandrakeSoft,
>     Red Hat and SuSE. We observe several cryptographic flaws in GPG v1.2.3. The
>     most serious flaw has been present in GPG for almost four years: we show
>     that as soon as one (GPG-generated) ElGamal signature of an arbitrary
>     message is released, one can recover the signer's private key in less than a
>     second on a PC. As a consequence, ElGamal signatures and the so-called
>     ElGamal sign+encrypt keys have recently been removed from GPG. Fortunately,
>     ElGamal was not GPG's default option for signing keys.

This part and the paper proper looks useful!
I recall the ElGamal signing keys are already
deprecated.

The paper also makes some comments concerning
OpenPGP weaknesses (sans exploits) of PKCS#1 v1.5
RSA encryption and signatures (section 4.2, 4.3).

    4.2 Encryption

    As already mentioned in Section 2, GPG implements
    RSA encryption as defined by PKCS#1 v1.5.  This is
    not state-of-the-art cryptography: like with
    ElGamel, Bleichenbacker's chosen-ciphertext [4]
    can decrypt any ciphertext.  But, as mentioned
    in 3.3, the relevance of such attacks to the email
    world is debatable, in part because of the high
    number of oracle calls.  We hope that future
    versions of the OpenPGP standard, will recommend
    better RSA encryption standards (see for instance
    PKCS#1 v2.1 [20] or NESSIE [8]).

Any comments?

Presumably it is way too late in the piece to
change these methods.  My question here would be
more along the lines of whether a warning comment
should be placed in the draft document?

(Apologies for not proposing the text for that!)

iang

PS: definately worth posting though.

[4] D. Bleichenbacker.  Generating ElGamal signatures
without knowing the secret key. In _Proc. of Eurocrypt
'96_, volume 1070 of LNCS, pages 10-18.  IACR, Springer-
Verlag, 1996.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Tue, 09 Mar 2004 17:40:43 -0500

>should be placed in the draft document?

Adding a warning in the Security Considerations section would, I think, 
be necessary here.  It's a known weakness that could have serious 
consequences if, for example, the OpenPGP message format was used for 
some sort of programmatic interface, rather than for email.

		--Steve Bellovin, http://www.research.att.com/~smb

---

From: "Carl Ellison" <[email-masked]>
Date: Tue, 9 Mar 2004 23:25:36 -0800

In UPnP Security, we started out with a better encoding mechanism, that
provably avoids the attack on PKCS#1v1.5. However, we were forced by our
developers to go back to PKCS.  The crypto libraries some of these folks
were using did PKCS#1 and nothing else.

So, we added instructions to the developers and convinced ourselves that
this made PKCS#1 safe.

http://www.upnp.org/standardizeddcps/security.asp

See p.49 of DeviceSecurity for those instructions.

 - Carl

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Steven 
> M. Bellovin
> Sent: Tuesday, March 09, 2004 2:41 PM
> To: Ian Grigg
> Cc: Mike Markowitz; Hal Finney; [email-masked]
> Subject: Re: paper of interest to be presented at EuroCrypt 
> 
>

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 10 Mar 2004 20:43:41 +1300

Ian Grigg <[email-masked]> writes:

>>As already mentioned in Section 2, GPG implements RSA encryption as defined
>>by PKCS#1 v1.5.  This is not state-of-the-art cryptography: like with
>>ElGamel, Bleichenbacker's chosen-ciphertext [4] can decrypt any ciphertext.
>
>Any comments?

This came up on the S/MIME group some time ago, I did a back-of-the-envelope
calculation and came up with some figure like 6 months continuous hammering of
a mail server *specifically configured to act as an oracle* to decrypt a
message (that's not the exact figure, it may have been 8 months or something
similar, I'd have to go back and dig up the notes).  My conclusion was that in
terms of things to worry about it was at about the same level as being hit by
a freak meteor.

(And before someone leaps in with "I can dream up an artificial scenario where
 ...", I'm quite sure you can, but it's really a "don't do that, then" issue
 and not any real-world threat).

There was a brief attempt to force S/MIME to go to OAEP, but the response was
something akin to a general yawn from implementors (see "The Crypto Gardening
Guide and Planting Tips" at
http://www.cs.auckland.ac.nz/~pgut001/pubs/crypto_guide.txt for more on this).

>My question here would be more along the lines of whether a warning comment

"Do not custom-configure your MTA to act as an oracle for an attacker and then
let it run unattended for six months" ought to do it.

Peter.

---

From: Jon Callas <[email-masked]>
Date: Wed, 10 Mar 2004 15:11:36 -0800

> let it run unattended for six months" ought to do it.

I'm happy to put this in as a security consideration. Should I also put 
in one about not looking into a laser with your remaining eye?

	Jon