Subject: [openpgp] The combinatorial complexity of OpenPGPv4

From: David Leon Gil <[email-masked]>
Date: Fri, 13 Mar 2015 17:04:06 -0700

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

---

From: Falcon Darkstar Momot <[email-masked]>
Date: Fri, 13 Mar 2015 18:19:58 -0700

I feel like perhaps this type of exhaustive testing is neither necessary
nor expected, and that a few end-to-end tests designed to exercise edge
cases could be combined with more exhaustive unit tests to achieve
reasonable results.  Protocol modularity is not evil.

--Falcon Darkstar Momot
--Shadytel

On 13/03/2015 17:04, David Leon Gil wrote:
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp

---

From: David Gil <[email-masked]>
Date: Sat, 14 Mar 2015 03:57:17 +0000 (UTC)

On Friday, March 13, 2015 6:20 PM, Falcon Darkstar Momot <[email-masked]> wrote:

> reasonable results. 

The difficulty, as always, is proving that an actual implementation is modular. In the case of OpenPGP, it really isn't: A lot of data has to get carried between each stage to ensure conformance with the high-level semantics.

In contrast, suppose that I wanted to exhaustively test the different ways of doing authenticated encryption with TweetNaCl. That's exactly 1 test, which I can then test for 2^32 different parameter values or so quite easily.

That type of exhaustive testing is routinely (though not routinely enough) done, and it is expected for critical software.

> Protocol modularity is not evil.

Modularity is neutral. "Agility", as folks like to call it, is evil.

The name-sake article of Google and Yahoo's End-to-End project has some good arguments for avoiding redundancy in systems design: 

http://web.mit.edu/saltzer/www/publications/endtoend/endtoend.pdf

(I'd note that I think the article argues for its position a bit too strongly. It's clear that transport-layer and message-level encryption are both necessary, for example, because they have fundamentally different semantics.)

---

From: Derek Atkins <[email-masked]>
Date: Mon, 16 Mar 2015 09:46:23 -0400

> correctly. How many test cases do I need?

Generally?  One per packet-trail (which is, effectively, only a
handful).  If all you're doing is changing out the crypto and not the
packet structure then unit tests work perfectly for that.  You only need
to do integration tests for the packet formats!  That's the amazing
thing about how OpenPGP was designed.

> How many different ways can I compose this message?

TWO!  See above.

You can unit-test the crypto.  Changing from AES to Blowfish doesn't
change any of your processing code, the only change is the crypto within
the decryptor module.  But you've already validating that the crypto
works, and you've validated that the decryption module works,
so... you're done.

-derek
-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       [email-masked]                        PGP key available

---

From: Derek Atkins <[email-masked]>
Date: Mon, 16 Mar 2015 09:49:31 -0400

David Gil <[email-masked]> writes:

> The difficulty, as always, is proving that an actual implementation is
> modular. In the case of OpenPGP, it really isn't: A lot of data has to
> get carried between each stage to ensure conformance with the
> high-level semantics.

Having implemented it myself, I disagree completely.  It is absolutely
possible to create a modular implementation.  See my Usenix Security
Talk on the PGP Message Processing Pipeline from.... 1996??

[snip]
> Modularity is neutral. "Agility", as folks like to call it, is evil.

Well, it's a damn good thing we've had agility otherwise we'd have been
stuck with 3DES, SHA1 (or MD5!!), and probably either RSA or maybe
DSA/Elgamal.

-derek

---

From: David Leon Gil <[email-masked]>
Date: Mon, 16 Mar 2015 14:58:08 -0700

On Monday, March 16, 2015, Derek Atkins <[email-masked]> wrote:

> David Gil <[email-masked] <javascript:;>> writes:
>
> > On Friday, March 13, 2015 6:20 PM, Falcon Darkstar Momot
> > <[email-masked] <javascript:;>> wrote:
> >

Well, first: You're Derek Atkins. Not everyone is as good of a coder.

Second: It is hard to *prove* modularity, because of how complicated the
semantics are. (I have been trying, off-and-on, using Frama-C, for a while.)

> stuck with 3DES, SHA1 (or MD5!!), and probably either RSA or maybe

No: The reason there hasn't been any urgency to fix things like the CFB
mode problems, or the MDC, is that the current standard is too flexible.

I hate to use TLS as an exemplar of anything, but they have done a much
better job in this regard recently.

Where it is easy to provide flexibility, it is rarely useful. Where it is
useful, it is rarely feasible to provide. (E.g., a parameter to choose SIV,
encrypt-then-MAC, or robust AE.)

---

From: Derek Atkins <[email-masked]>
Date: Tue, 17 Mar 2015 11:27:29 -0400

[snip]
> Well, first: You're Derek Atkins. Not everyone is as good of a coder.

*blush*

> semantics are. (I have been trying, off-and-on, using Frama-C, for a while.)

Yes, the structure is complicated (my parser state machine had something
like 150-200 states).  But the processing itself is completely modular.
You just need concepts like split and join along the pipeline to handle
it.  Proof by existance?

> No: The reason there hasn't been any urgency to fix things like the CFB mode
> problems, or the MDC, is that the current standard is too flexible.

I don't agree with this statement.  It wasn't flexibility that stopped
changing CFB, it was that CTR mode was relatively new when the group was
working on 4880 (I'm not sure it even existed when we did 2440).  And
compatibility was always (generally) paramount.  I.e., if it ain't
completely broke let's not fix it..  and where it is broke, let's fix it
in the most compatible way.

Were I do start from scratch today then yes, I'd just use GCM.  We could
certainly add a GCM mode and a preference to specify support for it.
But for interop I don't think we could drop CFB support completely from
implementations.

I'll also point out that CFB vs "something else" (i.e., "mode agility")
is completely orthogonal to algorithm agility.  OpenPGP does NOT have
decent mode agility; we would need to add a new packet type for that.

> I hate to use TLS as an exemplar of anything, but they have done a much better
> job in this regard recently.
>

It's easy to add it if you think about it ahead of time (and put in the
parameterization).  It's harder to add it after-the-fact.  This is true
in both TLS and OpenPGP.

-derek

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Mon, 23 Mar 2015 19:48:28 +0100

> But for interop I don't think we could drop CFB support completely from
Could you elaborate on that?

I probably lack some decent+recent cryptanalysis of CFB as used with
OpenPGP, but at least we had quite a number of crypto systems where it
caused all kinds of issues recently.

So *if* there's a new OpenPGP v.X (and not just "amendments" as with
Ed25519), shouldn't it be actually a goal to get current state of the
art things?

Cheers,
Chris.