[ 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

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

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

   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

   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

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

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.

HTML conversion and comments on this are RFC are Copyright (c) 1998 Werner Koch, Remscheider Str. 22, 40215 Düsseldorf, Germany. Verbatim copying and distribution is permitted in any medium, provided this notice is preserved. See here for copyright information on the RFC itself.

Updated: 1999-09-30 wkoch