[ Contents ]
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.
Updated: 1999-09-30 wkoch