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 <[email protected]>
Sent: Monday, November 7, 2022 6:33 AM
To: Russ Housley <[email protected]>; Scott Fluhrer (sfluhrer)
<[email protected]>
Cc: Arciszewski, Scott <[email protected]>; [email protected]; [email protected]
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
<[email protected]<mailto:[email protected]>> 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
<[email protected]<mailto:[email protected]>> 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
[email protected]<mailto:[email protected]>
https://www.ietf.org/mailman/listinfo/cose
_______________________________________________
COSE mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/cose
