[ 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 "email@example.com" but CAST5, Blowfish, and TripleDES specified for "firstname.lastname@example.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