In the above diagram, if the binding signature of a subkey has been
revoked, the revoked binding signature may be removed, leaving only
one signature.
In a key that has a main key and subkeys, the primary key MUST be a
key capable of signing. The subkeys may be keys of any other type.
There may be other constructions of V4 keys, too. For example, there
may be a single-key RSA key in V4 format, a DSA primary key with an
RSA encryption key, or RSA primary key with an Elgamal subkey, etc.
It is also possible to have a signature-only subkey. This permits a
primary key that collects certifications (key signatures) but is used
only used for certifying subkeys that are used for encryption and
signatures.
11.2. Key IDs and Fingerprints
For a V3 key, the eight-octet key ID consists of the low 64 bits of
the public modulus of the RSA key.
The fingerprint of a V3 key is formed by hashing the body (but not
the two-octet length) of the MPIs that form the key material (public
modulus n, followed by exponent e) with MD5.
A V4 fingerprint is the 160-bit SHA-1 hash of the one-octet Packet
Tag, followed by the two-octet packet length, followed by the entire
Public Key packet starting with the version field. The key ID is the
low order 64 bits of the fingerprint. Here are the fields of the
hash material, with the example of a DSA key:
a.1) 0x99 (1 octet)
a.2) high order length octet of (b)-(f) (1 octet)
a.3) low order length octet of (b)-(f) (1 octet)
b) version number = 4 (1 octet);
c) time stamp of key creation (4 octets);
d) algorithm (1 octet): 17 = DSA (example);
e) Algorithm specific fields.
Algorithm Specific Fields for DSA keys (example):
e.1) MPI of DSA prime p;
e.2) MPI of DSA group order q (q is a prime divisor of p-1);
e.3) MPI of DSA group generator g;
e.4) MPI of DSA public key value y (= g**x where x is secret).
Note that it is possible for there to be collisions of key IDs -- two
different keys with the same key ID. Note that there is a much
smaller, but still non-zero probability that two different keys have
the same fingerprint.
Also note that if V3 and V4 format keys share the same RSA key
material, they will have different key ids as well as different
fingerprints.
12. Notes on Algorithms
12.1. Symmetric Algorithm Preferences
The symmetric algorithm preference is an ordered list of algorithms
that the keyholder accepts. Since it is found on a self-signature, it
is possible that a keyholder may have different preferences. For
example, Alice may have TripleDES only specified for "alice@work.com"
but CAST5, Blowfish, and TripleDES specified for "alice@home.org".
Note that it is also possible for preferences to be in a subkey's
binding signature.
Since TripleDES is the MUST-implement algorithm, if it is not
explicitly in the list, it is tacitly at the end. However, it is good
form to place it there explicitly. Note also that if an
implementation does not implement the preference, then it is
implicitly a TripleDES-only implementation.
An implementation MUST not use a symmetric algorithm that is not in
the recipient's preference list. When encrypting to more than one
recipient, the implementation finds a suitable algorithm by taking
the intersection of the preferences of the recipients. Note that the
MUST-implement algorithm, TripleDES, ensures that the intersection is
not null. The implementation may use any mechanism to pick an
algorithm in the intersection.
If an implementation can decrypt a message that a keyholder doesn't
have in their preferences, the implementation SHOULD decrypt the
message anyway, but MUST warn the keyholder than protocol has been
violated. (For example, suppose that Alice, above, has software that
implements all algorithms in this specification. Nonetheless, she
prefers subsets for work or home. If she is sent a message encrypted
with IDEA, which is not in her preferences, the software warns her
that someone sent her an IDEA-encrypted message, but it would ideally
decrypt it anyway.)
An implementation that is striving for backward compatibility MAY
consider a V3 key with a V3 self-signature to be an implicit
preference for IDEA, and no ability to do TripleDES. This is
technically non-compliant, but an implementation MAY violate the
above rule in this case only and use IDEA to encrypt the message,
provided that the message creator is warned. Ideally, though, the
implementation would follow the rule by actually generating two
messages, because it is possible that the OpenPGP user's
implementation does not have IDEA, and thus could not read the
message. Consequently, an implementation MAY, but SHOULD NOT use IDEA
in an algorithm conflict with a V3 key.
12.2. Other Algorithm Preferences
Other algorithm preferences work similarly to the symmetric algorithm
preference, in that they specify which algorithms the keyholder
accepts. There are two interesting cases that other comments need to
be made about, though, the compression preferences and the hash
preferences.
12.2.1. Compression Preferences
Compression has been an integral part of PGP since its first days.
OpenPGP and all previous versions of PGP have offered compression.
And in this specification, the default is for messages to be
compressed, although an implementation is not required to do so.
Consequently, the compression preference gives a way for a keyholder
to request that messages not be compressed, presumably because they
are using a minimal implementation that does not include compression.
Additionally, this gives a keyholder a way to state that it can
support alternate algorithms.
Like the algorithm preferences, an implementation MUST NOT use an
algorithm that is not in the preference vector. If the preferences
are not present, then they are assumed to be [ZIP(1),
UNCOMPRESSED(0)].
12.2.2. Hash Algorithm Preferences
Typically, the choice of a hash algorithm is something the signer
does, rather than the verifier, because a signer does not typically
know who is going to be verifying the signature. This preference,
though, allows a protocol based upon digital signatures ease in
negotiation.
Thus, if Alice is authenticating herself to Bob with a signature, it
makes sense for her to use a hash algorithm that Bob's software uses.
This preference allows Bob to state in his key which algorithms Alice
may use.
12.3. Plaintext
Algorithm 0, "plaintext", may only be used to denote secret keys that
are stored in the clear. Implementations must not use plaintext in
Symmetrically Encrypted Data Packets; they must use Literal Data
Packets to encode unencrypted or literal data.
12.4. RSA
There are algorithm types for RSA-signature-only, and RSA-encrypt-
only keys. These types are deprecated. The "key flags" subpacket in a
signature is a much better way to express the same idea, and
generalizes it to all algorithms. An implementation SHOULD NOT create
such a key, but MAY interpret it.
An implementation SHOULD NOT implement RSA keys of size less than 768
bits.
It is permissible for an implementation to support RSA merely for
backward compatibility; for example, such an implementation would
support V3 keys with IDEA symmetric cryptography. Note that this is
an exception to the other MUST-implement rules. An implementation
that supports RSA in V4 keys MUST implement the MUST-implement
features.
12.5. Elgamal
If an Elgamal key is to be used for both signing and encryption,
extra care must be taken in creating the key.
An ElGamal key consists of a generator g, a prime modulus p, a secret
exponent x, and a public value y = g^x mod p.
The generator and prime must be chosen so that solving the discrete
log problem is intractable. The group g should generate the
multiplicative group mod p-1 or a large subgroup of it, and the order
of g should have at least one large prime factor. A good choice is
to use a "strong" Sophie-Germain prime in choosing p, so that both p
and (p-1)/2 are primes. In fact, this choice is so good that
implementors SHOULD do it, as it avoids a small subgroup attack.
In addition, a result of Bleichenbacher [BLEICHENBACHER] shows that
if the generator g has only small prime factors, and if g divides the
order of the group it generates, then signatures can be forged. In
particular, choosing g=2 is a bad choice if the group order may be
even. On the other hand, a generator of 2 is a fine choice for an
encryption-only key, as this will make the encryption faster.
While verifying Elgamal signatures, note that it is important to test
that r and s are less than p. If this test is not done then
signatures can be trivially forged by using large r values of
approximately twice the length of p. This attack is also discussed
in the Bleichenbacher paper.
Details on safe use of Elgamal signatures may be found in [MENEZES],
which discusses all the weaknesses described above.
If an implementation allows Elgamal signatures, then it MUST use the
algorithm identifier 20 for an Elgamal public key that can sign.
An implementation SHOULD NOT implement Elgamal keys of size less than
768 bits. For long-term security, Elgamal keys should be 1024 bits or
longer.
12.6. DSA
An implementation SHOULD NOT implement DSA keys of size less than 768
bits. Note that present DSA is limited to a maximum of 1024 bit keys,
which are recommended for long-term use.
12.7. Reserved Algorithm Numbers
A number of algorithm IDs have been reserved for algorithms that
would be useful to use in an OpenPGP implementation, yet there are
issues that prevent an implementor from actually implementing the
algorithm. These are marked in the Public Algorithms section as
"(reserved for)".
The reserved public key algorithms, Elliptic Curve (18), ECDSA (19),
and X9.42 (21) do not have the necessary parameters, parameter order,
or semantics defined.
The reserved symmetric key algorithm, DES/SK (6), does not have
semantics defined.
The reserved hash algorithms, TIGER192 (6), and HAVAL-5-160 (7), do
not have OIDs. The reserved algorithm number 4, reserved for a
double-width variant of SHA1, is not presently defined.
We have reserver three algorithm IDs for the US NIST's Advanced
Encryption Standard. This algorithm will work with (at least) 128,
192, and 256-bit keys. We expect that this algorithm will be selected
from the candidate algorithms in the year 2000.
12.8. OpenPGP CFB mode
OpenPGP does symmetric encryption using a variant of Cipher Feedback
Mode (CFB mode). This section describes the procedure it uses in
detail. This mode is what is used for Symmetrically Encrypted Data
Packets; the mechanism used for encrypting secret key material is
similar, but described in those sections above.
OpenPGP CFB mode uses an initialization vector (IV) of all zeros, and
prefixes the plaintext with ten octets of random data, such that
octets 9 and 10 match octets 7 and 8. It does a CFB "resync" after
encrypting those ten octets.
Note that for an algorithm that has a larger block size than 64 bits,
the equivalent function will be done with that entire block. For
example, a 16-octet block algorithm would operate on 16 octets, and
then produce two octets of check, and then work on 16-octet blocks.
Step by step, here is the procedure:
1. The feedback register (FR) is set to the IV, which is all zeros.
2. FR is encrypted to produce FRE (FR Encrypted). This is the
encryption of an all-zero value.
3. FRE is xored with the first 8 octets of random data prefixed to
the plaintext to produce C1-C8, the first 8 octets of ciphertext.
4. FR is loaded with C1-C8.
5. FR is encrypted to produce FRE, the encryption of the first 8
octets of ciphertext.
6. The left two octets of FRE get xored with the next two octets of
data that were prefixed to the plaintext. This produces C9-C10,
the next two octets of ciphertext.
7. (The resync step) FR is loaded with C3-C10.
8. FR is encrypted to produce FRE.
9. FRE is xored with the first 8 octets of the given plaintext, now
that we have finished encrypting the 10 octets of prefixed data.
This produces C11-C18, the next 8 octets of ciphertext.
10. FR is loaded with C11-C18
11. FR is encrypted to produce FRE.
12. FRE is xored with the next 8 octets of plaintext, to produce the
next 8 octets of ciphertext. These are loaded into FR and the
process is repeated until the plaintext is used up.
13. Security Considerations
As with any technology involving cryptography, you should check the
current literature to determine if any algorithms used here have been
found to be vulnerable to attack.
This specification uses Public Key Cryptography technologies.
Possession of the private key portion of a public-private key pair is
assumed to be controlled by the proper party or parties.
Certain operations in this specification involve the use of random
numbers. An appropriate entropy source should be used to generate
these numbers. See RFC1750.
The MD5 hash algorithm has been found to have weaknesses (pseudo-
collisions in the compress function) that make some people deprecate
its use. They consider the SHA-1 algorithm better.
Many security protocol designers think that it is a bad idea to use a
single key for both privacy (encryption) and integrity (signatures).
In fact, this was one of the motivating forces behind the V4 key
format with separate signature and encryption keys. If you as an
implementor promote dual-use keys, you should at least be aware of
this controversy.
The DSA algorithm will work with any 160-bit hash, but it is
sensitive to the quality of the hash algorithm, if the hash algorithm
is broken, it can leak the secret key. The Digital Signature Standard
(DSS) specifies that DSA be used with SHA-1. RIPEMD-160 is
considered by many cryptographers to be as strong. An implementation
should take care which hash algorithms are used with DSA, as a weak
hash can not only allow a signature to be forged, but could leak the
secret key. These same considerations about the quality of the hash
algorithm apply to Elgamal signatures.
If you are building an authentication system, the recipient may
specify a preferred signing algorithm. However, the signer would be
foolish to use a weak algorithm simply because the recipient requests
it.
Some of the encryption algorithms mentioned in this document have
been analyzed less than others. For example, although CAST5 is
presently considered strong, it has been analyzed less than Triple-
DES. Other algorithms may have other controversies surrounding them.
Some technologies mentioned here may be subject to government control
in some countries.
14. Implementation Nits
This section is a collection of comments to help an implementer,
particularly with an eye to backward compatibility. Previous
implementations of PGP are not OpenPGP-compliant. Often the
differences are small, but small differences are frequently more
vexing than large differences. Thus, this list of potential problems
and gotchas for a developer who is trying to be backward-compatible.
* PGP 5.x does not accept V4 signatures for anything other than
key material.
* PGP 5.x does not recognize the "five-octet" lengths in new-format
headers or in signature subpacket lengths.
* PGP 5.0 rejects an encrypted session key if the keylength differs
from the S2K symmetric algorithm. This is a bug in its validation
function.
* PGP 5.0 does not handle multiple one-pass signature headers and
trailers. Signing one will compress the one-pass signed literal
and prefix a V3 signature instead of doing a nested one-pass
signature.
* When exporting a private key, PGP 2.x generates the header "BEGIN
PGP SECRET KEY BLOCK" instead of "BEGIN PGP PRIVATE KEY BLOCK".
All previous versions ignore the implied data type, and look
directly at the packet data type.
* In a clear-signed signature, PGP 5.0 will figure out the correct
hash algorithm if there is no "Hash:" header, but it will reject
a mismatch between the header and the actual algorithm used. The
"standard" (i.e. Zimmermann/Finney/et al.) version of PGP 2.x
rejects the "Hash:" header and assumes MD5. There are a number of
enhanced variants of PGP 2.6.x that have been modified for SHA-1
signatures.
* PGP 5.0 can read an RSA key in V4 format, but can only recognize
it with a V3 keyid, and can properly use only a V3 format RSA
key.
* Neither PGP 5.x nor PGP 6.0 recognize Elgamal Encrypt and Sign
keys. They only handle Elgamal Encrypt-only keys.
* There are many ways possible for two keys to have the same key
material, but different fingerprints (and thus key ids). Perhaps
the most interesting is an RSA key that has been "upgraded" to V4
format, but since a V4 fingerprint is constructed by hashing the
key creation time along with other things, two V4 keys created at
different times, yet with the same key material will have
different fingerprints.
* If an implementation is using zlib to interoperate with PGP 2.x,
then the "windowBits" parameter should be set to -13.
15. Authors and Working Group Chair
The working group can be contacted via the current chair:
John W. Noerenberg, II
Qualcomm, Inc
6455 Lusk Blvd
San Diego, CA 92131 USA
Phone: +1 619-658-3510
EMail: jwn2@qualcomm.com
The principal authors of this memo are:
Jon Callas
Network Associates, Inc.
3965 Freedom Circle
Santa Clara, CA 95054, USA
Phone: +1 408-346-5860
EMail: jon@pgp.com, jcallas@nai.com
Lutz Donnerhacke
IKS GmbH
Wildenbruchstr. 15
07745 Jena, Germany
Phone: +49-3641-675642
EMail: lutz@iks-jena.de
Hal Finney
Network Associates, Inc.
3965 Freedom Circle
Santa Clara, CA 95054, USA
EMail: hal@pgp.com
Rodney Thayer
EIS Corporation
Clearwater, FL 33767, USA
EMail: rodney@unitran.com
This memo also draws on much previous work from a number of other
authors who include: Derek Atkins, Charles Breed, Dave Del Torto,
Marc Dyksterhouse, Gail Haspert, Gene Hoffman, Paul Hoffman, Raph
Levien, Colin Plumb, Will Price, William Stallings, Mark Weaver, and
Philip R. Zimmermann.
16. References
[BLEICHENBACHER] Bleichenbacher, Daniel, "Generating ElGamal
signatures without knowing the secret key,"
Eurocrypt 96. Note that the version in the
proceedings has an error. A revised version is
available at the time of writing from
<ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc
/ElGamal.ps>
[BLOWFISH] Schneier, B. "Description of a New Variable-Length
Key, 64-Bit Block Cipher (Blowfish)" Fast Software
Encryption, Cambridge Security Workshop Proceedings
(December 1993), Springer-Verlag, 1994, pp191-204
<http://www.counterpane.com/bfsverlag.html>
[DONNERHACKE] Donnerhacke, L., et. al, "PGP263in - an improved
international version of PGP", ftp://ftp.iks-
jena.de/mitarb/lutz/crypt/software/pgp/
[ELGAMAL] T. ElGamal, "A Public-Key Cryptosystem and a
Signature Scheme Based on Discrete Logarithms," IEEE
Transactions on Information Theory, v. IT-31, n. 4,
1985, pp. 469-472.
[IDEA] Lai, X, "On the design and security of block
ciphers", ETH Series in Information Processing, J.L.
Massey (editor), Vol. 1, Hartung-Gorre Verlag
Knostanz, Technische Hochschule (Zurich), 1992
[ISO-10646] ISO/IEC 10646-1:1993. International Standard --
Information technology -- Universal Multiple-Octet
Coded Character Set (UCS) -- Part 1: Architecture
and Basic Multilingual Plane. UTF-8 is described in
Annex R, adopted but not yet published. UTF-16 is
described in Annex Q, adopted but not yet published.
[MENEZES] Alfred Menezes, Paul van Oorschot, and Scott
Vanstone, "Handbook of Applied Cryptography," CRC
Press, 1996.
[RFC822] Crocker, D., "Standard for the format of ARPA
Internet text messages", STD 11, RFC822, August
1982.
[RFC1423] Balenson, D., "Privacy Enhancement for Internet
Electronic Mail: Part III: Algorithms, Modes, and
Identifiers", RFC1423, October 1993.
[RFC1641] Goldsmith, D. and M. Davis, "Using Unicode with
MIME", RFC1641, July 1994.
[RFC1750] Eastlake, D., Crocker, S. and J. Schiller,
"Randomness Recommendations for Security", RFC1750,
December 1994.
[RFC1951] Deutsch, P., "DEFLATE Compressed Data Format
Specification version 1.3.", RFC1951, May 1996.
[RFC1983] Malkin, G., "Internet Users' Glossary", FYI 18, RFC
1983, August 1996.
[RFC1991] Atkins, D., Stallings, W. and P. Zimmermann, "PGP
Message Exchange Formats", RFC1991, August 1996.
[RFC2015] Elkins, M., "MIME Security with Pretty Good Privacy
(PGP)", RFC2015, October 1996.
[RFC2231] Borenstein, N. and N. Freed, "Multipurpose Internet
Mail Extensions (MIME) Part One: Format of Internet
Message Bodies.", RFC2231, November 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Level", BCP 14, RFC2119, March 1997.
[RFC2144] Adams, C., "The CAST-128 Encryption Algorithm", RFC
2144, May 1997.
[RFC2279] Yergeau., F., "UTF-8, a transformation format of
Unicode and ISO 10646", RFC2279, January 1998.
[RFC2313] Kaliski, B., "PKCS #1: RSA Encryption Standard
version 1.5", RFC2313, March 1998.
[SAFER] Massey, J.L. "SAFER K-64: One Year Later", B.
Preneel, editor, Fast Software Encryption, Second
International Workshop (LNCS 1008) pp212-241,
Springer-Verlag 1995
17. Full Copyright Statement
Copyright (C) The Internet Society (1998). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.