[openpgp] The combinatorial complexity of OpenPGPv4

[David Leon Gil <[e-mail]>]

Suppose that I want to test whether an implementation
handles all OpenPGPv4 signed-then-encrypted messages
correctly. How many test cases do I need?

Let's suppose, first, that I prove that handling of
PTag formats is independent of the rest of the code.

In that case, the packet composition is either:

    PKESK
    SEIPD
      COMPRESSED
      LITERAL
      SIGNATURE
    MDC

Or:

    PKESK
    SE
      COMPRESSED
      LITERAL
      SIGNATURE

How many different ways can I compose this message?

15 * 24 * 4 * 3 * 35
- 15: PKESK
  - RSA-ES
  - RSA-E
  - ELG-E
  - 12 ECDH combinations:
    - 3 curves
      - P-256
      - P-384
      - P-521
    - 4 KDF hash algorithms
      - SHA2-224
      - SHA2-256
      - SHA2-384
      - SHA2-512
- 24: SEIPD
  - 2 choices of packet type
    - SE
    - SEIPD
  - 12 encryption algorithms
    - Plaintext (prohibited)
    - IDEA
    - TripleDES
    - CAST5
    - Blowfish
    - AES128
    - AES192
    - AES256
    - Twofish
    - CAMELLIA128
    - CAMELLIA192
    - CAMELLIA256
- 4: Compressed
  - Uncompressed
  - ZLIB
  - DEFLATE
  - BZIP2
- 3: Literal
  - UTF-8
  - Binary
  - Local
- 35: Signature
 - 5 asymmetric algorithms:
   - RSA-ES
   - RSA-S
   - DSA
   - ECDSA
   - ED25519 (GnuPG)
 - 7 hash algorithms:
   - MD5
   - SHA-1
   - RIPEMD160
   - SHA2-224
   - SHA2-256
   - SHA2-384
   - SHA2-512

Or: 151,200 test cases. For the simplest message anyone
wants to send.

Not including any of the details of signature subpackets,
or unusual (but valid) variants of PKESKs etc. I previously
calculated that number, but it is so absurdly huge I won't
bother.

- David