Subject: [lamps] New / updated drafts for composite keys, sigs, encryption, key transport

From: Mike Ounsworth <[email-masked]>
Date: Mon, 12 Jul 2021 21:52:45 +0000

Hi LAMPS!

Another long draft announcement email (sorry).

We have previously presented a draft for Composite Signatures (draft-ounsworth-pq-composite-sigs-04). Over the past 6 months we have incorporated a lot of community feedback and also taken a shot at defining composite encryption and composite key exchange mechanisms.

Short changelog and explanation of drafts:

draft-ounsworth-pq-composite-keys-00
  - New
  - Moved public and private key structures out of the signatures draft to make them standalone and key-usage-agnostic.
  - Defines separate public key OIDs for "Composite" and "Composite-OR" so that the public key algid identifies whether it wants to be used in the AND mode (highest security and rigidity) or OR mode (highest migration flexibility, subject to local policy).

draft-ounsworth-pq-explicit-composite-keys-00
  - New
  - Addressing public comments that the "SEQUENCE SIZE (2 .. MAX) OF __" composite structures are too generic and flexible. 
  - Explicit Composite aims to provide an ASN.1 "factory" module for producing and validating ASN.1 objects tied to a specific pair of component algIDs. 
  - Could be either competing or complementing the generic keys draft, depending on WG direction.

draft-ounsworth-pq-composite-sigs-05
  - Update of -04
  - Move public and private key structures to their own draft.
  - Notes about Generation and Verification with Composite-OR keys; one or more signatures may be omitted and a NULL placed in the corresponding signature value slot.

draft-ounsworth-pq-composite-encryption-00
  - New
  - Defines three "composite encryption" mechanisms:
    1. Composite Encryption where all component algs are encryption primitives (uses a one-time-pad mechanism).
    2. Composite Encryption where component algs may be a mixture of encryption and KEM primitives (uses a one-time-pad mechanism).
    3. Composite Key Exchange where components algs may be a mixture of encryption, KEM, and Key Exchange primitives (uses NIST SP 800-56Cr2 multi-input KDF).
  - Encryption and decryption processes support both Composite (all recipient keys MUST be used) and Composite-OR (any subset of recipient keys may be used).

Please accept that these are not completely "polished", but hopefully complete enough for discussion about working group adoption (ie are these the mechanisms we want to proceed with to accomplish our new charter items?). As always, we highly welcome feedback (either editorial or WG-directional), collaboration, interop testing.

---
Mike Ounsworth
Software Security Architect, Entrust

---

From: Russ Housley <[email-masked]>
Date: Tue, 13 Jul 2021 09:57:57 -0400

>  - Notes about Generation and Verification with Composite-OR keys; one or more signatures may be omitted and a NULL placed in the corresponding signature value slot.

Doe this create an opportunity for an attacher to replace a signature from the signer with a NULL?

Russ

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 13 Jul 2021 14:23:39 +0000

Correct. If you issue a public key with the Composite-OR OID (which we have included for Max's use-case) then signatures it produces will *not* be resistant against stripping attacks. Composite-OR trades off security for migration flexibility. 

Anyone who implements Composite-OR I would also strongly advise to implement an out-of-band algorithm policy mechanism.

In the current version of the draft, "3.2.  Composite-OR Signature Generation Process" does not say to do anything different with the SignatureAlgorithm Params when omitting a signature value. I wonder if that would make a difference, or if we are assuming that an attacker doing a stripping attack also has the ability to tamper with the remaining signatures? I can note that for the next version.

---
Mike Ounsworth

-----Original Message-----
From: Russ Housley <[email-masked]> 
Sent: July 13, 2021 8:58 AM
To: Mike Ounsworth <[email-masked]>
Cc: SPASM <[email-masked]>
Subject: [EXTERNAL] Re: [lamps] New / updated drafts for composite keys, sigs, encryption, key transport

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________

Russ

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 13 Jul 2021 14:50:19 +0000

>>  - Notes about Generation and Verification with Composite-OR keys;
    >>  one or more signatures may be omitted and a NULL placed in the
    >>  corresponding signature value slot.
    >
    > Does this create an opportunity for an attacker to replace
    > a signature from the signer with a NULL?

[Caveat: I can be totally wrong here due to lack of understanding - so an explanation would be welcome.]

Say, there are three signatures. I can crack/forge one, but not the other two. So, I doctor the document, forge one sig, and replace the other two with NULLs. 

What's to stop me?

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 13 Jul 2021 23:05:29 +0000

If the public key was generated as type Composite-OR then nothing is stopping you from doing that. But Composite-OR is not intending to provide this kind of security.

Let me back up and explain the design intent: there seem to be two camps of people eyeing this Composite draft:

1. People who want strong security of multi-signatures. AKA "composite for the sake of security".

2. People who want to issue multiple keys to each end entity and then choose at runtime whether to use one or the other or both. AKA "composite for the sake of migration flexibility".

These are conflicting requirements. In an online negotiated protocol, or an environment with strong control of crypto policy on all clients, you might be able to accomplish both at the same time, but in general you can't (for example document or code signing where you're throwing signatures to the wind and have no idea what client will verify them).

What we DO NOT WANT is someone signing, for example a legal document or an EXE, thinking they have provided strong type 1 dual-signatures, and then someone else's client verifies it using "sloppy" verification logic -- for example maybe the client does not support the PQ alg that was used, but passes the signature anyway because the RSA part was good. Therefore we have defined two separate public key OIDs (id-composite-key and id-composite-or-key respectively) and made it clear that you MAY NOT use a "sloppy" verification on a public key of type id-composite-key; if the signer wanted to allow sloppy verification, they would have used an id-composite-or-key instead.  Basically, this forces declaring at keygen / certification time whether this key is intended for dual-security or for migration.

Personal opinion: "OR style verifications" seem like a lot of rope to hang yourself with, I don't like it, but we know that people will do it anyway. So by specifying it, we can say which OIDs you are and are not allowed to do it with, and we have the opportunity to list security considerations.

---
Mike Ounsworth

-----Original Message-----
From: Blumenthal, Uri - 0553 - MITLL <[email-masked]> 
Sent: July 13, 2021 9:50 AM
To: Russ Housley <[email-masked]>; Mike Ounsworth <[email-masked]>
Cc: SPASM <[email-masked]>
Subject: [EXTERNAL] Re: [lamps] New / updated drafts for composite keys, sigs, encryption, key transport

What's to stop me?