note on sequence counter atomicity for asynchronous/concurrent implementations

[panva]

The current draft (draft-ietf-hpke-hpke-02) provides clear language on:

• The requirement that ciphertexts be presented to Open() in the same order they were generated by Seal() calls
• The use of a sequence counter for nonce generation
• The automatic increment of the context's sequence number after each successful Seal() and Open()

However, the draft does not address the critical issue of operation atomicity when AEAD operations are made asynchronous, e.g. in a JavaScript runtime (Node.js, browsers, Deno, Cloudflare Workers), where cryptographic operations are either

• Inherently asynchronous (returning Promises through the Web Cryptography API)
• Dispatched to worker threads or separate execution contexts to avoid blocking the process event loop

Consider this naive javascript implementation based on the pseudo-code in the draft

async function ContextSSeal(aad, pt) {
  const ct = await Seal(this.key, this.ComputeNonce(this.seq), aad, pt)
  this.IncrementSeq()
  return ct
}

async function ContextROpen(aad, ct) {
  const pt = await Open(this.key, this.ComputeNonce(this.seq), aad, ct) // throws OpenError
  this.IncrementSeq()
  return pt
}

These implementations are non-atomic with respect to sequence counter incrementation because if parallel execution comes into play it may entirely be the case that two ContextSSeal() or ContextROpen() are called "at the same time" and so this.ComputeNonce(this.seq) is called multiple times before each invocation's Seal()/Open() gets resolved.

This implementation then results in reusing the same sequence number, therefore the same nonce 💥.

Improving on this then?

async function ContextSSeal(aad, pt) {
-  const ct = await Seal(this.key, this.ComputeNonce(this.seq), aad, pt)
+  const ct = Seal(this.key, this.ComputeNonce(this.seq), aad, pt)
  this.IncrementSeq()
-  return ct
+  return await ct
}

async function ContextROpen(aad, ct) {
-  const pt = await Open(this.key, this.ComputeNonce(this.seq), aad, ct) // throws OpenError
+  const pt = Open(this.key, this.ComputeNonce(this.seq), aad, ct) // Promise rejecting with OpenError
  this.IncrementSeq()
-  return pt
+  return await pt
}

This implementation no longer results in reusing the same sequence number, great 🎉 . But it still has two issues

• if either Seal() or Open() fail then the sequence number has already been incremented (and cannot be reverted since function context has no awareness of its paralllel use), this is generally a non-issue on the Sender side since Seal() is not expected to fail (but who knows...), but a Recipient may easily be tricked into processing a bad [ct, aad] that fails and then their entire context has to be discarded because its out of sync.
• (minor and js specific): if this.IncrementSeq() throws MessageLimitReachedError AND Seal() or Open() fail there will be a global unhandled rejection

So the only correct implementation in an inherently async environment is?

async function ContextSSeal(aad, pt) {
  const release = await this.mutex.lock()
  try {
    const ct = await Seal(this.key, this.ComputeNonce(this.seq), aad, pt)
    this.IncrementSeq()
    return ct
  } finally {
    release()
  }
}

async function ContextROpen(aad, ct) {
  const release = await this.mutex.lock()
  try {
    const pt = await Open(this.key, this.ComputeNonce(this.seq), aad, ct) // throws OpenError
    this.IncrementSeq()
    return pt
  } finally {
    release()
  }
}

(That, or the entire ContextSSeal(), ContextROpen() context instance calls need to be synchronized with a mutex)

This is obviously not an issue for implementations that only expose single-shot APIs.

What do you think, would it make sense to add more guidance to the draft so that these naive implementations don't (re¹)occur?

Footnotes

1. I've privately disclosed this issue to an HPKE implementation project recently ↩

[bifurcation]

Ah, async environments provide such a rich variety of failure modes (see, e.g., futurelock). FWIW, I don't think interleaving Seal and Open is a problem, because that doesn't create two encrypted objects with the same nonce, which is the condition that causes problems. (It would cause practical problems, just not crypto problems.) The real problem would be interleaved Seal calls.

I appreciate the instinct to try to guide folks toward safe patterns. Do you have thoughts on a way to write this up in a way that would be applicable to many environments, not tied too deeply to one environment?

Maybe something like:

In parallel or concurrent environments, the Seal and IncrementSeq operations MUST be done as an atomic unit, e.g. by holding a lock on ContextS for the duration of ContextS.Seal. If other calls to Seal might be interleaved between the Seal and the IncrementSeq, this will result in multiple encryptions with the same counter, and thus the same nonce, which is a Bad Thing.

[panva]

Ah, async environments provide such a rich variety of failure modes

Yeah they do...

FWIW, I don't think interleaving Seal and Open is a problem

Neither do I. The mutex instance is distinct to each Context instance.

It would cause practical problems, just not crypto problems.

I only mention Open() because if an attacker can force an Open() routine to de-sync with bad aad or ct then they could force a DoS on the Recipient. I wouldn't think to mention that in a CFRG/IRTF track document but it seems fitting to mention in an IETF track one.

The real problem would be interleaved Seal calls.

Very true.

I appreciate the instinct to try to guide folks toward safe patterns.

Whilst doing an implementation the need for atomicity was clear to me but thinking that it's such an easy mistake to make if one just follows the pseudo-code I checked other projects and ... there it was.

Do you have thoughts on a way to write this up in a way that would be applicable to many environments, not tied too deeply to one environment?

Your suggestion is a great starting-off point, I'll ponder on it some more and open a PR today.

[samuel-lee-msft]

This thread makes me wonder whether there are any plans to extend HPKE with API surface which would allow better concurrency / resilience to message loss (or corruption) and broader applicability?

Specifically it seems like it could be a good improvement to have:

ContextS.SealUnordered(aad, pt) -> <(ct, seq), Error>
internally atomically increments sequence number (probably should be only 64-bits rather than 96-bits) of the state and provides the sequence number used to the caller to encode in the application. If there is some internal failure in the Seal operation, some sequence numbers may not correspond to any valid ciphertext, and that's fine.

ContextR.OpenUnordered(aad, ct, seq) -> <pt, Error>
just attempts to decrypt ct with aad using the caller provided sequence number. Like the normal ContextR.Open the API should only release secret-dependent information on successful AEAD decryption (i.e. it should be constant time w.r.t. the AEAD Open operation and internal temporary values should be cleared).

This would enable HPKE to be used in lossy environments. Specifically with the current specification if I want to Seal a series of 1000 messages and only message 750 is corrupted or lost, there is no standard way for a Receiver to validly open valid messages 750...1000 (the receiver state can never update its counter to 751).
This pushes applications towards the oneshot API for resiliency in these use cases at the cost of way more overhead (computationally and size wise).

[panva]

@samuel-lee-msft related, OpenSSL allows re-sequencing on the recipient api

[samuel-lee-msft]

Still thinking on this thread.

Is there anything in the HPKE spec that precludes a future AEAD to be defined which does not require a unique nonce for security?

I'm not sure the atomicity of the counter update + seal operation should be a MUST at the HPKE-level for future AEADs, rather than a implementation detail MUST for the existing AEADs.

For example, we could define a new AEAD algorithm with AES-GCM-128 with a construction to generate per-message encryption keys which would sidestep the whole concurrency issue, assuming a good source of random:

AES-GCM-128-singleUseEncryptionKeys.Seal(key, _nonce, aad, pt):
    prekey = random(16)
    inner_nonce = 0x000000000000000000000000
    inner_key = AES-ECB(key, prekey)
    inner_ct = AES-GCM-128.Seal(inner_key, inner_nonce, aad, pt)
    return concat(prekey, inner_ct)

AES-GCM-128-singleUseEncryptionKeys.Open(key, _nonce, aad, ct):
    prekey = ct[:16]
    inner_ct = ct[16:]
    inner_nonce = 0x000000000000000000000000
    inner_key = AES-ECB(key, prekey)
    return AES-GCM-128.Open(inner_key, inner_nonce, aad, ct)   

Such an AEAD would not enforce any ordering of decryption as is, and there would be no need for a sequence counter or nonce generation at the HPKE level. Perhaps that means it's not a valid AEAD for the base profile of HPKE?

You could pass the HPKE "nonce" to the inner aad to maintain the ordering behavior between Sender and Receiver, without exposing the ability to encrypt 2 messages with the same (inner_key, inner_nonce) pair. Would that be a valid future AEAD?