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

[Brendan Moran <[e-mail]>]

There are two variants of AES-GCM in firmware encryption that we could use.

1) out-of-order receipt, on-the-fly decryption. This is what Scott's
proposal enables. It comes with a catch: an attacker can modify the
ciphertext and it won't be detected until the last block of ciphertext
is received; meanwhile the attacker-controlled plaintext is present on
the recipient. This may have a risk if the attacker has a way to
recover any of the plaintext from the recipient.

2) ciphertext stored in NVM, decrypt during image swap. I think this
may be the simplest case. A single tag for the whole image is probably
acceptable, which would mean the tag can be verified post-download.
The tag could also be verified prior to swap. The only time that
decryption might occur without the tag being verified is if a swap
resume needs to be executed after a mid-swap failure. It's possible
that there is a workaround for this scenario, but it involves the
bootloader re-encrypting the already-swapped blocks of firmware image
in order to verify the GCM tag; I don't think it's safe to assume this
will always be the case. It does limit the attacks against an AES-GCM
implementation of SUIT to those that have physical access to the
target and can induce faults (e.g. reboots) at just the right moment
to interrupt the swap process. Even then, the system still has a hash
of the plaintext available to verify the image once decrypted.

Best Regards,
Brendan

On Mon, Nov 14, 2022 at 9:38 PM David Brown <[e-mail]> wrote:
>
> I'm not sure this is quite right. As I understand what Scott/Brendan is suggesting in #2 is that we use AES-GCM, and we verify the tag when the initial message is received. Then, when we piece-by-piece decrypt it, the tag is not verified, because we are not verifying the entire image.
>
> I like this approach, because we don't have to say that it is AES-CTR. But, I'm a little concerned that our implementation is effectively implementing this after the tag has been verified. I think we limit damage from ciphertext modification because after the entire image is decrypted, we validate a signature over the plaintext.
>
> This gives us the best of both, and would be acceptable to mcuboot.
>
> David
>
> On Tue, Nov 8, 2022 at 4:20 AM Russ Housley <[e-mail]> wrote:
>>
>> I am not sure that #2 meets the requirement.  At least one bootloader implementer has said that it is hard enough to finds space for the signature value, but adding authentication tags on top of that is too hard.
>>
>> Russ
>>
>> On Nov 8, 2022, at 5:24 AM, Brendan Moran <[e-mail]> wrote:
>>
>> Am I correct in understanding that we have three options as far as the SUIT use case goes?
>>
>> We register an algorithm identifier for AES-CTR, mark it as deprecated.
>> We take a variant of AES-GCM to cfrg; one where plaintext data explicitly IS returned before the tag is verified. If cfrg review determines it is appropriate, we register an algorithm identifier, and mark it as deprecated.
>> We use a block-wise AEAD that is already in COSE and accept that there is a payload inflation due to the additional tags.
>>
>> Best Regards,
>> Brendan
>>
>> On Mon, Nov 7, 2022 at 6:29 PM Russ Housley <[e-mail]> wrote:
>>>
>>> Scott:
>>>
>>> The AES-CCM specification says:
>>>
>>>    If the T value is not correct, the receiver MUST NOT reveal any
>>>    information except for the fact that T is incorrect.  The receiver
>>>    MUST NOT reveal the decrypted message, the value T, or any other
>>>    information.
>>>
>>> My reading of the NIST AES-GCM specification has a similar requirement:
>>>
>>>    If T = T′, then return P; else return FAIL.
>>>
>>> So, your technique works from a math perspective, but it does not honor this requirement.
>>>
>>> Russ
>>>
>>>
>>> On Nov 7, 2022, at 8:46 AM, Scott Fluhrer (sfluhrer) <sfluhrer=[e-mail]> wrote:
>>>
>>> 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]> 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]> 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]
>>> https://www.ietf.org/mailman/listinfo/cose
>>>
>>> _______________________________________________
>>> COSE mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/cose
>>>
>>>
>> _______________________________________________
>> COSE mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/cose
>>
>>
>> _______________________________________________
>> COSE mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/cose