Subject: [lamps] Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

From: Mike Ounsworth <[email-masked]>
Date: Fri, 25 Mar 2022 11:17:27 +0000

The comment I was going to make at the mic:

At the TLS WG this week, Douglas Stebila presented on a known issue in the hybrid KEM combiner they're proposing for TLS (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets to play with the lengths of the shared secrets at runtime. Obvious solution: KEM codepoints need to fix the SS length in the spec so that it's not variable at runtime.

We're putting together a draft which provides essentially the same combiner for hybrid CMS content encryption (yuck terminology hell. Florence D. please save us and write a terminology draft!).
For that combiner to avoid the attack, I think we need Sean's KEM OIDs draft to fix the shared secret length for each KEM that it specifies.

So for now I think I'm just asking @Sean to throw a Security Consideration into his draft so we don't forget that it's important.

---
Mike Ounsworth
Software Security Architect, Entrust

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

---

From: Sean Turner <[email-masked]>
Date: Fri, 25 Mar 2022 08:00:24 -0400

Mike,

I will make sure to note this as an issue the GH repo.

spt

> On Mar 25, 2022, at 07:17, Mike Ounsworth <Mike.Ounsworth=[email-masked]> wrote:
> 
> At the TLS WG this week, Douglas Stebila presented on a known issue in the hybrid KEM combiner they’re proposing for TLS (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets to play with the lengths of the shared secrets at runtime. Obvious solution: KEM codepoints need to fix the SS length in the spec so that it’s not variable at runtime.
>  
> We’re putting together a draft which provides essentially the same combiner for hybrid CMS content encryption (yuck terminology hell. Florence D. please save us and write a terminology draft!).
> For that combiner to avoid the attack, I think we need Sean’s KEM OIDs draft to fix the shared secret length for each KEM that it specifies.
>  
> So for now I think I’m just asking @Sean to throw a Security Consideration into his draft so we don’t forget that it’s important.
>  
> ---
> Mike Ounsworth
> Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system._______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm

---

From: Florence D <[email-masked]>
Date: Fri, 25 Mar 2022 13:09:17 +0000

> We’re putting together a draft which provides essentially the same combiner for hybrid CMS content encryption (yuck terminology hell. Florence D. please save us and write a terminology draft!).

Very happy to write something.  I suspect the word hybrid is already so overloaded that agreeing on anything will be much more difficult but I’m happy to get started.

> At the TLS WG this week, Douglas Stebila presented on a known issue in the hybrid KEM combiner they’re proposing for TLS (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets to…
On the shared secret length, assuming that we use the NIST algorithms as they’re defined, the length of the shared secret shouldn't be ambiguous as it will be part of the parameter set for the KEM.  If we’re proposing doing something different then this probably merits some security analysis of its own.   I’ll defer to more experienced protocol designers on whether it’s worth encoding the length in the codepoint if it’s implicit from the scheme, I’m not sure of the precedent.

Flo

From: Spasm <[email-masked]> On Behalf Of Mike Ounsworth
Sent: 25 March 2022 11:17
To: 'LAMPS' <[email-masked]>
Subject: [lamps] Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

---
Mike Ounsworth

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system. This information is exempt under the Freedom of Information Act 2000 (FOIA) and may be exempt under other UK information legislation. Refer any FOIA queries to [email-masked]. All material is UK Crown Copyright ©

---

From: Mike Ounsworth <[email-masked]>
Date: Fri, 25 Mar 2022 13:14:09 +0000

> assuming that we use the NIST algorithms as they’re defined, the length of the shared secret shouldn't be ambiguous as it will be part of the parameter set for the KEM.

Oh that’s good to know!
I saw that many (most? all?) of the remaining KEMs use SHAKE as their last internal step, so in theory they are variable-length, but if the NIST specs will fix the output length then that’s probably sufficient.

The experts in this case are @Nimrod Aviram<mailto:[email-masked]>, and @Douglas Stebila<mailto:[email-masked]>.

---
Mike Ounsworth

From: Florence D <Florence.D=[email-masked]>
Sent: March 25, 2022 8:09 AM
To: Mike Ounsworth <[email-masked]>; 'LAMPS' <[email-masked]>
Subject: [EXTERNAL] RE: [lamps] Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.
________________________________

Flo

From: Spasm <[email-masked]<mailto:[email-masked]>> On Behalf Of Mike Ounsworth
Sent: 25 March 2022 11:17
To: 'LAMPS' <[email-masked]<mailto:[email-masked]>>
Subject: [lamps] Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

---
Mike Ounsworth

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system. This information is exempt under the Freedom of Information Act 2000 (FOIA) and may be exempt under other UK information legislation. Refer any FOIA queries to [email-masked]<mailto:[email-masked]>. All material is UK Crown Copyright ©

---

From: Douglas Stebila <[email-masked]>
Date: Fri, 25 Mar 2022 09:23:45 -0400

> I saw that many (most? all?) of the remaining KEMs use SHAKE as their last internal step, so in theory they are variable-length, but if the NIST specs will fix the output length then that’s probabl…

All of the round 3 KEM finalists and alternate candidates have fixed length shared secrets, even if they happen to be using the extendable output function SHAKE internally while generating the shared secret.

But it's not just the PQ shared secret that would need to be fixed length.  If one is concatenating two shared secrets and then hashing -- H(ss_1 || ss_2) -- the concern arises when ss_1 is variable-length.  So if your scenario envisions concatenating a traditional (RSA/FFDH/ECC) shared secret and a PQ shared secret, one would want to be sure the first component of the concatenation is not variable length.  For TLS 1.3 key exchange, the number of standardized curves is quite small so one can reasonably have confidence the scenario won't arise.  For general certificates with arbitrary algorithms, I can see there being a long tail of peculiar algorithms, some of which might be variable-length, so this scenario might merit some extra care.

> At the TLS WG this week, Douglas Stebila presented on a known issue in the hybrid KEM combiner they’re proposing for TLS (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets to…

To be clear on the context here, there are additional requirements that have to be satisfied for there to be trouble, not the least of which is the ability to find collisions in the hash function used on concatenated secrets.

Douglas

>  
> The experts in this case are @Nimrod Aviram, and @Douglas Stebila.
>  
> ---
> Mike Ounsworth
>

---

From: Mike Ounsworth <[email-masked]>
Date: Fri, 25 Mar 2022 13:30:28 +0000

> So if your scenario envisions concatenating a traditional (RSA/FFDH/ECC) shared secret and a PQ shared secret, one would want to be sure the first component of the concatenation is not variable length.

Another good point!

Thinking out loud: does padding solve the problem?

H(ss_1 || ss_2 || .. || ss_n)

if ss_i are each padded / truncated to, say, the security level of the underlying hash function, does that work?

---
Mike Ounsworth

-----Original Message-----
From: Douglas Stebila <[email-masked]> 
Sent: March 25, 2022 8:24 AM
To: Mike Ounsworth <[email-masked]>
Cc: Florence D <Florence.D=[email-masked]>; LAMPS <[email-masked]>; Nimrod Aviram <[email-masked]>
Subject: [EXTERNAL] Re: [lamps] Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

______________________________________________________________________

Douglas

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 25 Mar 2022 15:49:44 +0200

On Fri, Mar 25, 2022 at 01:30:28PM +0000, Mike Ounsworth wrote:
> > So if your scenario envisions concatenating a traditional
> (RSA/FFDH/ECC) shared secret and a PQ shared secret, one would want
> to be sure the first component of the concatenation is not variable
> length.
> 
> Another good point!
> 
> if ss_i are each padded / truncated to, say, the security level of
> the underlying hash function, does that work?

One could solve the issue for variable length SS by adding a length
field and padding to the maximum possible SS length. I think truncating
is a bad idea, and could interact badly with some oddball KEMs.

However, using KEMs with variable-length SS seems like a bad idea
anyway. E.g., see the TLS RACCOON attack.

-Ilari

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 25 Mar 2022 14:39:17 +0000

In general, I agree with the points Ilari made. However…

I think it’s good to allow SS of variable length;
When you allow variable length, you must include the length field into the hash;
I don't think padding is necessary in this case;
We should be careful regarding “max possible SS length”: while I don’t expect to ever see SS of, e.g., 56MB - I doubt it would stay at 32 or 48 bytes forever. I definitely don’t want to see “max possible SS len = 32”.

What’s the purpose of padding, if you included the length?

Re. RACOON attack – besides being pretty darn difficult to launch, it’s rather limited in applicability, IMHO – to the point I don’t really care. Besides, offhand, it isn’t applicable to NIST KEMs.

Thanks

-- 

V/R,

Uri

On 3/25/22, 09:50, "Spasm on behalf of Ilari Liusvaara" <[email-masked] on behalf of [email-masked]> wrote:

    > > So if your scenario envisions concatenating a traditional

    > (RSA/FFDH/ECC) shared secret and a PQ shared secret, one would want

    > to be sure the first component of the concatenation is not variable

    > length.

    > 

    > Another good point!

    > 

    > Thinking out loud: does padding solve the problem?

    > 

    > H(ss_1 || ss_2 || .. || ss_n)

    > 

    > if ss_i are each padded / truncated to, say, the security level of

    > the underlying hash function, does that work?

 

    -Ilari

    _______________________________________________

    Spasm mailing list

    [email-masked]

---

From: Nimrod Aviram <[email-masked]>
Date: Fri, 25 Mar 2022 19:12:53 +0300

If it's envisioned that concatenate-and-hash is used with variable-length
shared secrets, padding the first secret such that it always occupies a
multiple of the hash function block size should stop attacks of this type
(APOP-style attacks).

I agree with Ilari (downthread) that truncating could have unexpected
consequences.

Also, variable-length KEMs indeed open the door to Raccoon-style attacks
that attempt to time the hash calculation in order to learn information
about the secret. I agree with Doulgas that this might merit some extra
care, esp. if using peculiar algorithms. At first glance, it seems that
requiring all KEMs to either be CCA-secure or to have fixed length should
prevent Raccoon-style attacks, but obviously this requires more careful
analysis.

best,
Nimrod

On Fri, 25 Mar 2022 at 16:30, Mike Ounsworth <[email-masked]>
wrote:

> > So if your scenario envisions concatenating a traditional (RSA/FFDH/ECC)
> shared secret and a PQ shared secret, one would want to be sure the first
> component of the concatenation is not variable length.
>
> Another good point!
>
> if ss_i are each padded / truncated to, say, the security level of the
> underlying hash function, does that work?
>
> ---
> Mike Ounsworth
>
> Cc: Florence D <Florence.D=[email-masked]>; LAMPS <
> [email-masked]>; Nimrod Aviram <[email-masked]>
> Subject: [EXTERNAL] Re: [lamps] Security Consideration for
> draft-turner-lamps-nist-pqc-kem-certificates
>
> > > assuming that we use the NIST algorithms as they’re defined, the
> length of the shared secret shouldn't be ambiguous as it will be part of
> the parameter set for the KEM.
> >
> > Oh that’s good to know!
> > I saw that many (most? all?) of the remaining KEMs use SHAKE as their
> last internal step, so in theory they are variable-length, but if the NIST
> specs will fix the output length then that’s probably sufficient.
>
> All of the round 3 KEM finalists and alternate candidates have fixed
> length shared secrets, even if they happen to be using the extendable
> output function SHAKE internally while generating the shared secret.
>
> But it's not just the PQ shared secret that would need to be fixed
> length.  If one is concatenating two shared secrets and then hashing --
> H(ss_1 || ss_2) -- the concern arises when ss_1 is variable-length.  So if
> your scenario envisions concatenating a traditional (RSA/FFDH/ECC) shared
> secret and a PQ shared secret, one would want to be sure the first
> component of the concatenation is not variable length.  For TLS 1.3 key
> exchange, the number of standardized curves is quite small so one can
> reasonably have confidence the scenario won't arise.  For general
> certificates with arbitrary algorithms, I can see there being a long tail
> of peculiar algorithms, some of which might be variable-length, so this
> scenario might merit some extra care.
>
> > At the TLS WG this week, Douglas Stebila presented on a known issue in
> the hybrid KEM combiner they’re proposing for TLS
> (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets
> to play with the lengths of the shared secrets at runtime. Obvious
> solution: KEM codepoints need to fix the SS length in the spec so that it’s
> not variable at runtime.
>
>
> To be clear on the context here, there are additional requirements that
> have to be satisfied for there to be trouble, not the least of which is the
> ability to find collisions in the hash function used on concatenated
> secrets.
>
> Douglas
>
> >
> > To: Mike Ounsworth <[email-masked]>; 'LAMPS' <[email-masked]
> >
> > Subject: [EXTERNAL] RE: [lamps] Security Consideration for
> draft-turner-lamps-nist-pqc-kem-certificates
> >
> > > We’re putting together a draft which provides essentially the same
> combiner for hybrid CMS content encryption (yuck terminology hell. Florence
> D. please save us and write a terminology draft!).
> >
> > Very happy to write something.  I suspect the word hybrid is already so
> overloaded that agreeing on anything will be much more difficult but I’m
> happy to get started.
> >
> > > At the TLS WG this week, Douglas Stebila presented on a known issue in
> the hybrid KEM combiner they’re proposing for TLS
> (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets
> to play with the lengths of the shared secrets at runtime. Obvious
> solution: KEM codepoints need to fix the SS length in the spec so that it’s
> not variable at runtime.
> > On the shared secret length, assuming that we use the NIST algorithms as
> they’re defined, the length of the shared secret shouldn't be ambiguous as
> it will be part of the parameter set for the KEM.  If we’re proposing doing
> something different then this probably merits some security analysis of its
> own.   I’ll defer to more experienced protocol designers on whether it’s
> worth encoding the length in the codepoint if it’s implicit from the
> scheme, I’m not sure of the precedent.
> >
> > Flo
> >
> > Subject: [lamps] Security Consideration for
> draft-turner-lamps-nist-pqc-kem-certificates
> >
> > At the TLS WG this week, Douglas Stebila presented on a known issue in
> the hybrid KEM combiner they’re proposing for TLS
> (draft-ietf-tls-hybrid-design): it gets into trouble if the attacker gets
> to play with the lengths of the shared secrets at runtime. Obvious
> solution: KEM codepoints need to fix the SS length in the spec so that it’s
> not variable at runtime.
> >
> > We’re putting together a draft which provides essentially the same
> combiner for hybrid CMS content encryption (yuck terminology hell. Florence
> D. please save us and write a terminology draft!).
> > For that combiner to avoid the attack, I think we need Sean’s KEM OIDs
> draft to fix the shared secret length for each KEM that it specifies.
> >
> > So for now I think I’m just asking @Sean to throw a Security
> Consideration into his draft so we don’t forget that it’s important.
> >
> > ---
> > Mike Ounsworth
> > Any email and files/attachments transmitted with it are confidential and
> are intended solely for the use of the individual or entity to whom they
> are addressed. If this message has been sent to you in error, you must not
> copy, distribute or disclose of the information it contains. Please notify
> Entrust immediately and delete the message from your system. This
> information is exempt under the Freedom of Information Act 2000 (FOIA) and
> may be exempt under other UK information legislation. Refer any FOIA
> queries to [email-masked]. All material is UK Crown Copyright ©
>
>

---

From: Mike Ounsworth <[email-masked]>
Date: Fri, 25 Mar 2022 16:33:14 +0000

Thanks Uri.

Can you provide the concrete construction you have in mind when you say “include the length field in the hash”? I will add a note to our composite kem combiner draft, but I do not want to mis-interpret your suggestion.

---
Mike Ounsworth

From: Spasm <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: March 25, 2022 9:39 AM
To: Ilari Liusvaara <[email-masked]>; LAMPS <[email-masked]>
Subject: Re: [lamps] [EXTERNAL] Re: Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

  *   I think it’s good to allow SS of variable length;
  *   When you allow variable length, you must include the length field into the hash;

  *   I don't think padding is necessary in this case;
  *   We should be careful regarding “max possible SS length”: while I don’t expect to ever see SS of, e.g., 56MB - I doubt it would stay at 32 or 48 bytes forever. I definitely don’t want to see “max possible SS len = 32”.

Thanks

--

V/R,

Uri

On 3/25/22, 09:50, "Spasm on behalf of Ilari Liusvaara" <[email-masked] on behalf of [email-masked]<mailto:[email-masked][email-masked]>> wrote:

    -Ilari

    Spasm mailing list

    [email-masked]<mailto:[email-masked]>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 25 Mar 2022 19:58:37 +0000

What I had in mind was something like (described loosely 😉)

SS_i ::= <len_in_bytes> || <ss_i>

Len_in_bytes ::= INTEGER (1..65536) – field taking 4 bytes

ss_i ::= symmetric shared secret obtained from the given KEM

SS_final = H(SS_1 || SS_2 || . . . || SS_n)

Sorry for sloppy handwaving, but I’m sure you understand what I mean.

TNX

--

V/R,

Uri

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

From: Mike Ounsworth <[email-masked]>
Date: Friday, March 25, 2022 at 12:34
To: Uri Blumenthal <[email-masked]>, Ilari Liusvaara <[email-masked]>, LAMPS <[email-masked]>
Subject: RE: [lamps] [EXTERNAL] Re: Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

Thanks Uri.

---
Mike Ounsworth

·         I think it’s good to allow SS of variable length;

·         When you allow variable length, you must include the length field into the hash;

·         I don't think padding is necessary in this case;

·         We should be careful regarding “max possible SS length”: while I don’t expect to ever see SS of, e.g., 56MB - I doubt it would stay at 32 or 48 bytes forever. I definitely don’t want to see “max possible SS len = 32”.

Thanks

-- 

V/R,

Uri

 

    -Ilari

    Spasm mailing list

    [email-masked]

---

From: Douglas Stebila <[email-masked]>
Date: Fri, 25 Mar 2022 19:14:02 -0400

Length prefixing a variable length shared secret will not avoid this type of attack.  It doesn't arise from ambiguity about how long something is (which is what length prefixing resolves), it arises from being able to control where certain parts of the string land with respect to a hash function block boundary.

Douglas

> On Mar 25, 2022, at 3:58 PM, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Sun, 27 Mar 2022 18:00:11 +0000

On Mar 25, 2022, at 19:14, Douglas Stebila <[email-masked]> wrote:
> 
> Length prefixing a variable length shared secret will not avoid this type of attack.

Would you mind clarifying - what attack/type-of-attack you mean?

>  It doesn't arise from ambiguity about how long something is (which is what length prefixing resolves), it arises from being able to control where certain parts of the string land with respect to a hash function block boundary.

Now you know where your 32-byte part of the string lands. Variable length would allow moving where your part of the string lands, somewhat. Still, so what? I don’t see a viable attack (assuming a decent hash function).

Thanks

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 28 Mar 2022 09:15:46 -0400

On Mar 27, 2022, at 14:00, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> 
> On Mar 25, 2022, at 19:14, Douglas Stebila <[email-masked] <mailto:[email-masked]>> wrote:
>> 

https://github.com/nimia/kdf_public#readme

> Now you know where your 32-byte part of the string lands. Variable length would allow moving where your part of the string lands, somewhat. Still, so what? I don’t see a viable attack (assuming a d…

That's the whole point of this scenario -- that one is not assuming a decent hash function.

Douglas

> 
> Thanks
> 
> 
>>> On Mar 25, 2022, at 3:58 PM, Blumenthal, Uri - 0553 - MITLL <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>> From: Mike Ounsworth <[email-masked] <mailto:[email-masked]>>
>>> To: Uri Blumenthal <[email-masked] <mailto:[email-masked]>>, Ilari Liusvaara <[email-masked] <mailto:[email-masked]>>, LAMPS <[email-masked] <mailto:[email-masked]>>
>>> From: Spasm <[email-masked] <mailto:[email-masked]>> On Behalf Of Blumenthal, Uri - 0553 - MITLL
>>> To: Ilari Liusvaara <[email-masked] <mailto:[email-masked]>>; LAMPS <[email-masked] <mailto:[email-masked]>>
>>> On 3/25/22, 09:50, "Spasm on behalf of Ilari Liusvaara" <[email-masked] <mailto:[email-masked]> on behalf of [email-masked] <mailto:[email-masked]>> wrote:
>>> 
>> [email-masked] <mailto:[email-masked]>
>> https://www.ietf.org/mailman/listinfo/spasm <https://www.ietf.org/mailman/listinfo/spasm>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 28 Mar 2022 13:19:53 +0000

Thanks!

Bending over backwards to support screwed-up hash functions does not seem worth it in this day and age. We do know now how to construct good hashes.

TNX

TNX
--
V/R,
Uri

Thanks Uri.

---
Mike Ounsworth

Thanks
-- 
V/R,
Uri

Another good point!

  -Ilari

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 28 Mar 2022 13:29:38 +0000

Along the same lines – how about “defending in depth” against block ciphers vulnerable to known-plaintext attacks and digital signatures that are easily forgeable, etc. etc.?

I understand the need to publish papers, but there got to be a limit in how far one pushes the assumptions.

--

V/R,

Uri

                                                                                                                                     -  C. A. R. Hoare

From: Spasm <[email-masked]> on behalf of Uri Blumenthal <[email-masked]>
Date: Monday, March 28, 2022 at 09:20
To: Douglas Stebila <[email-masked]>
Cc: LAMPS <[email-masked]>, Ilari Liusvaara <[email-masked]>, Mike Ounsworth <[email-masked]>
Subject: Re: [lamps] [EXTERNAL] Re: Security Consideration for draft-turner-lamps-nist-pqc-kem-certificates

Thanks!

TNX

TNX
--
V/R,
Uri

Thanks Uri.

---
Mike Ounsworth

Thanks
-- 
V/R,
Uri

Another good point!

  -Ilari