Subject: new approach to MDCs: single shared private key

From: Adam Back <[email-masked]>
Date: Wed, 21 Apr 1999 14:07:54 +0100

Whilst looking at RFC2440 with a view to defining suitable algorithm
ids and minimal backwards compatible changes to try out the
verification packet approach, in response to Werner Koch's posts, an
insight struck me:

	all we have to do is publish and agree upon a minimal sized
	RSA public and private key and publish it.

This allows us to provide:

- the best backwards compatibility of all (allows even pgp23a to
*check* MDCs, which is even better than just "not choking" on them).

- the lowest implementation overhead of all (ie none!)

This approach:

- prevents Gary Howland's encrypted message modification attack
because the signature with known public and private key performs the
same function as a hash inside the encryption envelope.

- it doesn't provide non-repudiation because the private key is shared
(which is the whole point, we don't want non-repudiation in this
scenario, and some people have good reasons for not wanting it).

- any pgp2.3a and forward implementation can "implement" these MDCs
merely by adding this public and private key pair to their key ring.

- PRZ identified the problem that even with signed messages often the
public key is not present to verify them, so integrity is not assured.
With openPGP and pgp(5|6).x where multiple signatures can be applied,
the document could be signed by both the fixed published RSA key, and
the user's private RSA key.

- The same approach of a published public and private DSA key can be
used to do the same thing with DSA for implementations temporarily
avoiding RSA until the patent expires.

- The only extra overhead is the signature creation and verification.
The key size does not affect security, so using a small a key as
possible does not adversely affect security.  A 384 bit key, or
perhaps even 256 bit key would be perfectly adequate.  (The limit will
be imposed by the size of RSA block required to hold the minimum sized
padded document hash.)  The minimum key size that the already deployed
DSA and RSA signature verification code would consider a valid
signature

- The keyid on the keys can be set to the string "Integrity
Verification Key" to help ensure that implementations present
representative messages.

- These public and private keys can be distributed with new
implementations, and distrubted widely on the internet.

Comments?  I think it is a neat, and exciting trick which allows even
pgp2.3a to overcome the message modification problem with no
implementation work.

The only advantages of defining a different MDC packet (which is what
I was in the process of doing when this occured to me) is to avoid
this small computational and space overhead.

Defining an elegant, space and computationally efficiient
implementation at our leisure can be done once the standard RSA and
DSA private and public keys are agreed upon, as an optimally backwards
compatible approach can be used for old implementations.

Adam

---

From: [email-masked]
Date: Wed, 21 Apr 1999 12:46:01 -0700

At 2:07 PM +0100 1999-04-21, Adam Back wrote:
>[elided]
>the user's private RSA key.            [...]

Adam,

The parallel signature extension I've added to the forthcoming
OpenPGP/MIME draft will make this very easy for MIME-compliant
mailers. Thomas Roessler and I are hoping to have the draft ready for
the Oslo IETF in July, and we'll have it up on the list for dsicussion
fairly soon.

    dave

An excerpt:
................................. cut here .................................
8.  Parallel (Multiple) Signatures

    Digitally signed messages conforming to this document are denoted by
    the "multipart/signed" content type, defined in RFC 1847, with a
    "protocol" parameter which MUST have a value of "multipart/mixed".
    (MUST be quoted).

    The "micalg" parameter MUST contain a comma-separated list of hash-
    symbols.  These hash-symbols identify the message integrity check
    (MIC) algorithm(s) used to generate the subsequent signature(s).
    Hash-symbols MUST NOT occur more than once in this list.

    The multipart/signed body MUST consist of exactly two parts.  The
    first part contains the signed data in MIME canonical format,
    including a set of appropriate content headers describing the data.

    The second part MUST be of type "multipart/mixed".  Each sub-part
    represents an individual digital signature which has been formed
    according to RFC 1847 and the specification of the signature protocol
    used.

    Example message:

         From: Dave Del Torto <[email-masked]>
         To: Raph Levien <[email-masked]>
         Mime-Version: 1.0
         Content-Type: multipart/signed; protocol="multipart/mixed";
            boundary=0000_031; micalg="pgp-md5,pgp-sha1,rsa-md5"

         --0000_031
         Content-Type: text/plain

         Hi Raph,

         Here's some text with parallel (multiple) digital signatures
         in various formats.

            dave

         ______________________________________________________________________
         "All email luxuriantly hand-crafted using only the finest ASCII text."

         --0000_031
         Content-Type: multipart/mixed; boundary=0000_032

         --0000_032
         Content-Type: application/pgp-signature

         -----BEGIN PGP SIGNATURE-----
         Version: PGP 2.6.2
         Comment: Hash computed using MD5 micalg.

         iQCVAwUBM0Iu16HBOF9KrwDlAQGaiQP9EU1YXgMSoNxDAqSmo7UoCE52DuYCfxm7
         x8RfRr9+Xz3nPFytSYM2TIWGMeKi1fVr5PhfjdrKvOh9sCq97h6zndZVpGA9x62k
         mPVn/QY3fz1eOdyJbYvW4ba7WQll5OoA6cqmEb9tWwh4ra4yE8hZMnLS9a0uPpuB
         5dpiTTAE/gY=
         =hD3D
         -----END PGP SIGNATURE-----

         --0000_032
         Content-Type: application/pgp-signature

         -----BEGIN PGP SIGNATURE-----
         Version: PGP for Personal Privacy 5.0
         Comment: Hash computed using SHA-1 micalg (FIPS 180-1).

         iQCVAwUBM0It9qHBOF9KrwDlAQFBaQQAisIzQUgyknT2v729b7MImcUc3ROdRBh6
         nwMyAfdewQYCDxqdDWvnD1UWoUjwjA1JNA6qhTXBxs8yPtZdDZaguOG2zWawyat9
         Jib556AuSx10psREDC3vNsaJ99MV8SKFF92H53l9w/YhVOA0aMZeNfLE0jJVypkY
         /so4/7DHhqQ=
         =/wlj
         -----END PGP SIGNATURE-----

         --0000_032
         Content-Type: application/x-pkcs7-signature
         Content-Transfer-Encoding: base64
         Comment: Hash computed using S/MIME MD5 micalg.

         MIAGCSqGSIb3DQEHAqCAMIACAQExDjAMBggqhkiG9w0CBQUAMIAGCSqGSIb3DQEH
          [ciphertext elided]
         +kNIWIbxNiNje1wlzIhaGjrGrOnvYc8+tFn2LgAAAAAAAAAA

         --0000_032--

         --0000_031--

---

From: Werner Koch <[email-masked]>
Date: Thu, 22 Apr 1999 09:47:33 +0200

> 	RSA public and private key and publish it.

But not before Sep 20th, 2000.  Or we would have to make it optional.

-- 
Werner Koch at guug.de           www.gnupg.org           keyid 621CC013