Re: [COSE] COSE Support for AES-CTR and AES-CBC

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

Here’s how out-of-order GCM works:

The decryption part is easy; if you know where the ciphertext fragement falls within the overall message, then it is obvious how to select the AES input to decrypt it properly.

What’s less obvious is the integrity piece; that is, how to compute the GCM tag (so that you can compare the value you compute to the tag included with the ciphertext).  Yes, it can be done; to see how it is done, we need to explore how GCM tags are computed:

With GCM, we take the ciphertext (and the AAD), and convert them into a series of 16 byte values M_n, M_{n-1}, M_{n-2}, …, M_1; this mapping is quite simple (so 16 bytes of the ciphertext are placed into a single M_i value).  Once we do that, we compute:

   M_n H**n + M_{n-1} H**{n-1} + … + M_1 H**1

(and then, we add in a value that depends on the nonce, and that’s the tag – that part isn’t affected by out-of-the-order processing.

Now, the multiplication operations (both in evaluating H**n and multiplying M_n with H**n), and the addition operations are both in GF(2**128); these are not the traditional schoolbook operations, instead, the multiplication looks odd, and the addition operation can be implemented by bitwise xor’ing the two values together); however all the traditional ways of rearranging operations work (and any GCM implementation will already have the appropriate multiplication logic already).

So, when we need to implement out-of-order evaluation of the above polynomial, that is, if we get the parts of the ciphertext that corresponds to M_a, M_{a-1}, …, M_b, (where c = a-b), what we can do is evaluate the intermediate polynomial:

M_a H**c + M_{a-1} H**{c-1} + ... + M_b H**0.

Once we have that, we can compute H**b (which can be done with log(b) multiplications), and multiply the polynomial with that.  The result of that is:

M_a H**a + M_{a-1} H**{a-1} + … + M_b H**b.

We can add that to the running sum.

Once we have all the fragments, we have the sum; if you add them all together, that’s the formula GCM expects, and so we can compute the expected tag.

Just some notes:


  *   If the ciphertext fragment you have doesn’t happen to fall on nice 16 byte boundaries, you can zero fill in the first and last word and it still works.  For example, if you have a two byte fragment that falls across a 16 byte boundary ABCD, you would process this as the two words 0000000000000AB and CD00000000000000
  *   One thing that this depends on is that you get all the fragments, and you get each one exactly once; if you get one of the fragments twice and add both to the running sum, well, this doesn’t work.

From: Brendan Moran <[e-mail]>
Sent: Monday, November 7, 2022 6:33 AM
To: Russ Housley <[e-mail]>; Scott Fluhrer (sfluhrer) <[e-mail]>
Cc: Arciszewski, Scott <[e-mail]>; [e-mail]; [e-mail]
Subject: Re: [COSE] COSE Support for AES-CTR and AES-CBC

Sorry, I had the wrong email address for Scott.

I’m trying to understand some of the concerns that have been raised. I understand that AES-GCM is not exposed to the concerns that Sophie and has raised?

If we used AES-GCM with out of order reception and on-the-fly decryption, would that mitigate the risks?

Best Regards,
Brendan

On Mon, 7 Nov 2022 at 11:03, Brendan Moran <[e-mail]<mailto:[e-mail]>> wrote:
I talked with Scott Fluhrer today about this use case and he’s pointed out that GCM can be processed out of order.

Scott, would you be able to elaborate on this?

Best Regards,
Brendan

On Wed, 26 Oct 2022 at 22:51, Russ Housley <[e-mail]<mailto:[e-mail]>> wrote:
Scott:


Introducing AES-CTR and/or AES-CBC into COSE tokens that already support AES-GCM will open the GCM implementations to new security issues. Namely, potential padding oracle vulnerabilities.

I think that adding a reference to the existing paragraph in the Security Considerations will address this concern:

   With AES-CBC mode, implementers SHOULD perform integrity checks prior
   to decryption to avoid padding oracle vulnerabilities [Vaudenay].


At minimum, the Security Considerations section of draft-ietf-cose-aes-ctr-and-cbc-01 needs to call this risk out: Applications that encrypt or decrypt with AES-GCM *MUST NOT* support AES-GCM or AES-CTR with the same cryptographic materials, due to the existence of cross-protocol issues. One way to safeguard users from potential misuse is to use a separate "type" for keys used with unauthenticated encryption modes; similar to how COSE distinguishes MACs from Signatures.

I suggest an addition paragraph in the Security Considerations:

   To avoid cross-protocol concerns, implementations MUST NOT use the
   same keying material with AES-CTR and AES-GCM.  Likewise,
   implementations MUST NOT use the same keying material with AES-CTR
   and AES-CCM.

Additionally, I'd like to recommend sharing this draft with the CFRG mailing list to ensure it has the appropriate level of oversight from the IETF's cryptography experts.

AES-CTR and AES-CBC are not new cryptographic modes.  New techniques deserve CFRG review, but AES-CTR and AES-CBC have been included in RFCs for many years.

Russ

_______________________________________________
COSE mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/cose