Recently, it occurred to me that there wasn’t a good, focused resource that covers commitments in the context of asymmetric cryptography.

I had covered confused deputy attacks in my very short (don’t look at the scroll bar) blog post on database cryptography., and that’s definitely relevant.

I had also touched on the subject of commitment in regards to asymmetric cryptography in a lightning round blog post, but that was focused on Exclusive Ownership.

Contents

• What is Commitment?
• What’s An Asymmetric Commitment?
• Obstacles to Asymmetric Commitment
  • RSA Encryption
  • RSA Signatures
  • ECDSA Signatures
  • ECDH + Symmetric Encryption
• Asymmetric Commitment at the Protocol Level
  • Committing RSA Encryption
  • Committing RSA Signatures
  • Committing ECDSA Signatures
  • Committing ECDH + Symmetric Encryption
• What About Post-Quantum Cryptography?

What is Commitment?

In simple terms, a commitment scheme in cryptography allows you to mathematically ensure some value is unchanging on both ends of a communication; often without revealing said value to anyone observing the communication.

For example, if you use a symmetric-key AEAD construction, you can bind the ciphertext to its intended context by specifying that context as Additional Authenticated Data (AAD) in both the encrypt path and the decrypt path.

If an attacker tries to replay a ciphertext in the wrong context, the decryption will fail. This kind of commitment prevents confused deputy attacks in the context of encrypted databases.

This isn’t the whole story, but it should suffice to build intuition for how commitment is expected to work.

“Well, what is the whole story?”

It turns out, there’s a loophole with mainstream symmetric AEAD modes that makes them not actually committing: If you can choose multiple symmetric keys, you can calculate two (plaintext, AAD) pairs that result in the same (ciphertext, authentication tag) pair.

This is called the “invisible salamanders” problem, and it shows up in some fun places (including password-authenticated key exchanges and so-called secure messengers).

This means that a clever and motivated attacker can defeat the commitment of AES-GCM, ChaCha20-Poly1305, etc. in a multi-key setting.

To staple commitment onto an existing AEAD scheme, there are a couple techniques in the literature that work:

1. If you use HKDF in your protocol, squeeze out one additional output (with a distinct info parameter), which you will then publish with your ciphertext to explicitly commit to the input key material. Assert its equality (in constant-time) on the decrypt path. This prevents the attack directly.
2. Prefix the plaintext with a block of NUL bytes. On decrypt, assert that the same block is present.
3. Instead of using the AEAD mode’s normal authentication tag, calculate a cryptographic hash (e.g. SHA256) of the key, nonce, and authentication tag.

Or, you can simply choose a committing AEAD scheme, wherein you replace the fast MAC algorithms with a collision-resistant hash function. For example: AES-CTR+HMAC, XChaCha+BMAC, etc.

Either way, committing symmetric-key encryption is an understood and solvable problem.

What’s An Asymmetric Commitment?

Broadly speaking, they don’t even exist in the context of how most developers experience asymmetric cryptography:

• RSA encryption
• RSA signatures
• ECDSA signatures
• ECDH + symmetric encryption (e.g. ECIES)

You might be surprised by some of the items on the above list. (Surely signature algorithms are committing, right?)

I’m going to explore each in detail, describe why they don’t offer the property we want, and then describe protocol-level design decisions we can take to provide commitment.

“What About Schnorr, EdDSA, and Zero-Knowledge Proofs?”

They’re out of scope for this discussion because they’re either committing by design or they’re not in the hot path for most developers’ experiences with asymmetric cryptography.

Obstacles to Asymmetric Commitment

First, let’s look at some of the challenges to commitment in the most common asymmetric cryptography algorithms. Once we have a vague sense of the challenges faced, the solutions should seem straightforward.

RSA Encryption

There are many problems with RSA encryption, including the fact that many developers try encrypting arbitrary data with RSA directly. Or the ever-present Bleichenbacher attacks against PKCS#1 v1.5 padding.

However, there’s an even more basic trouble here: Unlike symmetric-key encryption, there is no AAD parameter. Context-binding is simply not possible.

Furthermore, anyone with access to a given public key can generate a valid ciphertext (for a chosen plaintext message) that any party with the correct private key can decrypt. Sender authenticity is not provided by RSA encryption.

Committing RSA Encryption »

RSA Signatures

RSA signatures do not provide exclusive ownership. This means that it’s possible for two distinct RSA keypairs to produce the same RSA signature.

Additionally, depending on the parameters you choose and how you implement signature verification, you may be susceptible to forgery attacks.

Committing RSA Signatures »

ECDSA Signatures

ECDSA signatures do not provide exclusive ownership (as with RSA signatures), and implementations often permit malleable signatures.

ECDSA signature malleability is subtle and probably warrants an explanation.

Elliptic curve signatures are formatted as two numbers (R, S), where R can be thought of as a one-time challenge (calculated as a public key from a random one-time secret, –note that may be deterministic) and S is the actual signature of your message (calculated using both and R, as well as your secret key and a hash of the message).

The security of ECDSA depends on a few things, including:

1. The security of the elliptic curve being used.
2. The difficulty of the Elliptic Curve Discrete Logarithm Problem.
3. Your secret key being random, and not leaking.
4. being unbiased and random.
5. Signatures being calculated in constant-time.

However, the security of protocols using ECDSA depends on a few more things.

If S is larger than the group order of the elliptic curve, it should be reduced modulo the order.

For EdDSA, there was a malleability concern if your library accepted values for S that were larger than the group order. This meant you could take an existing signature (R, S), add the order of the curve (n) to S (yielding (R, S + n)), and submit it as a new valid signature.

For ECDSA, the problem is a little more subtle: (R, S) and (R, n – S) were both valid signatures. The solution is to reject any signatures where S > n/2.

If you designed your system to depend on the uniqueness of signatures, this introduced a vulnerability into your system.

Committing ECDSA Signatures »

ECDH + Symmetric Encryption

The elliptic curve cryptography counterpart to how encryption is done with RSA involves an Elliptic Curve Diffie Hellman key-exchange followed by Symmetric-Key Encryption.

Most often, ECDH is done ephemerally with long-term signing keys (i.e. certificates) used to authenticate one or both parties. This is ephemeral-ephemeral ECDH and offers forward secrecy.

Some messaging apps built atop NaCl or libsodium used static-static ECDH. However, this lacks forward secrecy, so a forward-secure authenticated key exchange (such as X3DH) is generally preferred.

In between these extremes, you have the use case of encrypting against a static public key. The sender generates an ephemeral ECDH keypair, does the handshake, encrypts their data with the key, and publishes the ephemeral public key with their ciphertext. This is static-ephemeral ECDH.

As with RSA encryption above, static-ephemeral ECDH does not authenticate the sender. Anyone with access to a given public key can generate a valid ciphertext that the recipient possessing the corresponding secret key will decrypt.

There are a couple of ways you can screw up this general construction.

• Using the raw ECDH output as a symmetric key.
  • The output of an elliptic curve operation is a random group element, not a uniformly random bit string. This pedantic observation leads to Cheon’s attack.
• Using unauthenticated encryption with ECDH.
  • I’ve seen many implementations in the real world that use AES in CBC or CTR mode instead of an authenticated mode like GCM.

    Tip: Don’t introduce padding oracles or let attackers trivially flip plaintext bits. You won’t have a good time.

Unfortunately, even when those perils are avoided, most ECDH + symmetric encryption protocols tend to not expose a mechanism for AAD (as is tradition with RSA encryption), nor do they use a committing authentication tag; opting instead for GCM or Poly1305.

Committing ECDH + Symmetric Encryption »

Asymmetric Commitment at the Protocol Level

To recap: Most of the mainstream asymmetric cryptography algorithms we all know and use aren’t ideal for cryptographic commitment. What can we do about it?

Well, we don’t need to dump these algorithms and move onto new designs. Instead, we can implement a secure commitment scheme atop the existing primitives, at the protocol level.

Committing RSA Encryption

RSA Encryption doesn’t provide any mechanism for additional authenticated data (AAD). This means if you’re using RSA for encrypting one-time symmetric keys, you cannot commit to a given context.

This means you have to attempt to decrypt the actual message before you get an error. (Assuming you get an error.)

The most straightforward way to solve this problem is, instead of only encrypting the symmetric key, include a hash of the AAD with this plaintext data. This allows you to verify it on the decrypt path. However, this makes part of your plaintext predictable, which isn’t a good place to be in with RSA encryption.

Instead, use your wrapped key (or, if you’re using a KDF with the wrapped key as the input key material, one additional output of the KDF) as an HMAC key, and calculate the HMAC of the AAD instead of a simple hash.

Additionally, it may be beneficial to always prepend the HMAC plaintext with the RSA pubic key, for reasons I’ll explain in the next section.

Here’s some JS-like pesudocode to demonstrate the idea:

function rsaCommitEncrypt(pk, key, aad = '') {
    const aadKey = kdf(key, 'RSA_WRAP_AAD', null);
    const aadMac = hmacSha256(
      aadKey,
      canonicalize([
        pk,
        aad
      ])
    );
    return crypto.publicEncrypt(
      {
        key: pk,
        padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
        oaepHash: "sha256",
      },
      Buffer.concat([aadMac, key])
    );
}

function rsaCommitDecrypt(sk, pk, ciphertext, aad = '') {
    const plain = crypto.privateDecrypt(
      {
        key: sk,
        padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
        oaepHash: "sha256"
      },
      ciphertext
    );
    const aadMac = plain.slice(0, 32);
    const key = plain.slice(32);
    const aadKey = kdf(key, 'RSA_WRAP_AAD', null);
    const aadMac2 = hmacSha256(
      aadKey,
      canonicalize([
        pk,
        aad
      ])
    );
    if (!crypto.timingSafeEqual(aadMac, aadMac2)) {
      throw new Error('Invalid AAD');
    }
    return key;
}

Committing RSA Signatures

Section 3.3 of the Exclusive Ownership paper describes a way to provide Universal Exclusive Ownership without increasing the message size.

For RSA signatures, the technique is simple: Include the public key in the hash of the message being signed.

function rsaCommitSign(sk, pk, message) {
    return crypto.sign("sha256", Buffer.concat(pk, message), {
      key: sk,
      padding: crypto.constants.RSA_PKCS1_PSS_PADDING,
    });
}

function rsaCommitVerify(pk, sig, message) {
    return crypto.verify(
      "sha256",
      Buffer.concat(pk, message),
      {
        key: pk,
        padding: crypto.constants.RSA_PKCS1_PSS_PADDING,
      },
      sig
    );
}

RSA encryption uses the public key for a similar reason: The AAD is bound to both the decrypted key and the public key. You can then use a committing RSA signature to authenticate the sender.

Committing ECDSA Signatures

Section 3.3 of the Exclusive Ownership paper describes a way to provide Universal Exclusive Ownership without increasing the message size.

For ECDSA signatures, we need to do two things:

1. Include the public key in the hash of the message being signed.
2. Reject signatures where S is larger than half the group order.

Using NIST P-256, a pseudocode implementation may look like:

const halfOrderP256 = BigInt(
  "0x7fffffff800000007fffffffffffffffde737d56d38bcf4279dce5617e3192a8"
);

function ecdsaP256CommitSign(sk, pk, message) {
    while (true) {
      let sig = crypto.sign(
        "sha256",
        Buffer.concat(pk, message),
        {
          key: sk,
          dsaEncoding: 'ieee-p1363'
        }
      );
      const S = bufToBigInt(sig.slice(32))
      if (S < halfOrderP256) {
        return sig;
      }
    }
}

function ecdsaP256CommitVerify(pk, sig, message) {
    const S = bufToBigInt(sig.slice(32))
    if (S >= halfOrderP256) {
      throw new Error('Malleable signature');
    }
    return crypto.verify(
      "sha256",
      Buffer.concat(pk, message),
      {
        key: pk,
        dsaEncoding: 'ieee-p1363',
      },
      sig
    );
}

Adopting this logic for P-384, P-521, etc. is straightforward.

Committing ECDH + Symmetric Encryption

Unlike the situation with RSA encryption above, ECDH doesn’t have any spare room for AAD to be stapled onto.

Instead, we’re going to use static-ephemeral ECDH to encrypt a random key (as with RSA). The shared secret will be then hashed with both public keys. The output of this hash will be the input key material for our KDF.

Then, we can do one of two things:

1. Derive an encryption key and a key commitment from HKDF, use a fast AEAD cipher for key wrapping.
2. Derive an encryption key and an authentication key, use a stream cipher and HMAC for message authentication (encrypt then MAC).

In either case, you will use the AAD mechanism.

I’m going with option 2 in the pseudocode below:

commitSealKey(pk, key, aad = '') {
    comst {ephSK, ephPK} = crypto_box_keypair();
    const ikm = crypto_generichash(Buffer.concat([
        crypto_scalarmult(ephSK, pk),
        ephPK,
        pk
    ]));
    const nonce = crypto_generichash(
      Buffer.concat([ephPK, pk]),
      null,
      24
    );
    const encKey = hkdf(ikm, 'ECDH_COMMIT_KEY_ENC');
    const macKey = hkdf(ikm, 'ECDH_COMMIT_KEY_AUTH');
    const cipher = crypto_stream_xor(encKey, nonce, /* plaintext: */ key);
    const tag = crypto_generichash(
       canonicalize([   
         pk,
         aad,
         cipher
       ]),
       macKey
    );
    return Buffer.concat([
      ephPK,
      tag,
      cipher
    ]);
}

commitOpenKey(sk, pk, sealed, aad = '') {
    const ephPK = sealed.slice(0, 32);
    const tag = sealed.slice(32, 64);
    const cipher = sealed.slice(64);
    
    const ikm = crypto_generichash(Buffer.concat([
        crypto_scalarmult(sk, ephPK),
        ephPK,
        pk
    ]));
    const macKey = hkdf(ikm, 'ECDH_COMMIT_KEY_AUTH');
    const tag2 = crypto_generichash(
       canonicalize([   
         pk,
         aad,
         cipher
       ]),
       macKey
    );

    if (!crypto.timingSafeEqual(tag, tag2)) {
      throw new Error('Invalid tag');
    }
    const encKey = hkdf(ikm, 'ECDH_COMMIT_KEY_ENC');
    return key = crypto_stream_xor(encKey, nonce, cipher);
}

What About Post-Quantum Cryptography?

I imagine hash-based signatures are committing, but I don’t know specifically about all of the NIST post-quantum cryptography candidates as of this writing.

This is an area I intend to explore in a future blog post.

Closing Thoughts

Whether the additional protocol complexity is worthwhile depends on your threat model, and the assumptions that went into your threat model. Ultimately, for most applications, vanilla RSA/ECDSA/etc. will serve their purposes just fine.

That said, I hope someone finds this post useful.

Header art: Sophie and Swizzlestix; I tried to make it a visual pun on asymmetry.