On Jan 11, 2022, at 19:07, Martin Thomson <m...@lowentropy.net> wrote:
>
> I was operating under the assumption that inputs to concatenation were fixed
> length. It seems that the attack mentioned did not. It seems like that is a
> far simpler way of achieving that goal.
>
> That is, it seems to be sufficient to state that assumption as a requirement.
Indeed we do state that in Section 6:
Therefore, this specification MUST only be used with algorithms which
have fixed-length shared secrets (after the variant has been fixed by
the algorithm identifier in the NamedGroup negotiation in Section 3.1).
> Constructing a length-prefixed encoding would work if we thought that
> supporting variable length secrets was a good idea.
As Scott writes in a subsequent email, length-prefixed encoding doesn't thwart
this type of attack. Length-prefixed encoding ensures there's no *ambiguity*
about which component is which, but that's not what the APOP-like attack
exploits. Instead it's helpful to the attacker to make parts of the input line
up with hash function boundaries, and length-prefixed encoding of
variable-length values don't stop that.
Padding to a fixed length would be the solution if we thought some algorithms
would have variable length secrets. For the purposes of the APOP-style attack,
I think it would even suffice to have a rule like "length-prefixed encoding +
pad up to the nearest multiple of 32 bytes in length" -- this would mean the
attacker's granularity in lining up something with respect to the hash function
boundary would be 32 bytes = 256 bits, which would make the search space of the
APOP-style attack infeasibly large.
Douglas
On Jan 11, 2022, at 19:07, Martin Thomson <m...@lowentropy.net> wrote:
>
> I was operating under the assumption that inputs to concatenation were fixed
> length. It seems that the attack mentioned did not. It seems like that is a
> far simpler way of achieving that goal.
>
> That is, it seems to be sufficient to state that assumption as a requirement.
>
> Constructing a length-prefixed encoding would work if we thought that
> supporting variable length secrets was a good idea. We could even do that on
> a per-secret basis, adding a length only when needed. However, I can't think
> of any way in which a variable length input would be advisable. So I'm going
> to recommend that we stick to fixed lengths. As Douglas notes, there aren't
> any primitives under consideration that want a variable-length secret once
> the parameters are decided.
>
> That TLS is vulnerable in the event of a collision will remain, even if we
> fix this, so while I'm not happy that our defense is that thin, the four
> conditions here on the second attack are each layers in that defense. Short
> timeouts mean that the massive computation involved in even SHA-1 collisions
> seems unlikely. Ephemeral key reuse is already advised against fairly
> strongly. We try to choose strong key agreement methods. And inputs are
> fixed length (or unambiguously encoded if deemed to be necessary).
>
> Cheers,
> Martin
>
> On Wed, Jan 12, 2022, at 08:01, Eric Rescorla wrote:
>> Hi Douglas,
>>
>> 8446 already says:
>>
>> Note that HKDF-Expand implements a pseudorandom function (PRF) with
>> both inputs and outputs of variable length. In some of the uses of
>> HKDF in this document (e.g., for generating exporters and the
>> resumption_master_secret), it is necessary that the application of
>> HKDF-Expand be collision resistant; namely, it should be infeasible
>> to find two different inputs to HKDF-Expand that output the same
>> value. This requires the underlying hash function to be collision
>> resistant and the output length from HKDF-Expand to be of size at
>> least 256 bits (or as much as needed for the hash function to prevent
>> finding collisions).
>>
>> With that said, defense in depth is good. Does it help to have just a
>> structured input, e.g.,
>>
>> opaque KeyInput<0..2^16-1>;
>>
>> struct {
>> KeyInput inputs<2..2^16-1>;
>> } KeyScheduleInput;
>>
>>
>>
>> -Ekr
>>
>>
>> On Tue, Jan 11, 2022 at 11:08 AM Douglas Stebila <dsteb...@gmail.com> wrote:
>>> Hello TLS working group,
>>>
>>> We've posted a revised version of "Hybrid key exchange in TLS 1.3" [1].
>>> Based on revision requests from the last draft, the main change is removing
>>> the unnecessary appendix of the past design considerations, and a few
>>> wording changes.
>>>
>>> Last September, Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenny
>>> Paterson, Eyal Ronen, and Eylon Yogev posted a note [2,3] with some
>>> concerns about whether the approach for constructing the hybrid shared
>>> secret in this document -- direct concatenation -- was risky in a scenario
>>> where the hash function used in TLS key derivation and transcript hashing
>>> is not collision resistant. Nimrod and his colleagues exchanged many
>>> emails with us over the past few months to help us understand their
>>> concerns. In the end we think the concerns are low and we have not made
>>> any changes in this draft, although if we receive different guidance from
>>> the working group, we'll do so.
>>>
>>> There were two types of concerns that Nimrod and his colleagues identified
>>> [2,3]:
>>>
>>> a) An attacker who can find collisions in the hash function can cause
>>> different sessions to arrive at the same session key. This concern is
>>> largely independent of this hybrid key exchange draft, as it focuses on
>>> collisions in the transcript hash, and affects existing TLS 1.3 even
>>> without this draft being adopted. If the TLS working group thinks this is
>>> a concern that should be addressed, it seems like it should be addressed at
>>> the overall level of TLS 1.3, rather than for this specific hybrid key
>>> exchange draft.
>>>
>>> b) An attacker who can find collisions in the hash function and has a
>>> certain level of control over the first of the two shared secrets in the
>>> hybrid shared secret concatenation may be able to carry out an iterative
>>> attack to recover bytes of the second shared secret. The iterative is
>>> similar to the APOP attacks [4,5] and also somewhat similar to the CRIME
>>> attack [6]. After discussing further with Nimrod and his colleagues, we
>>> identified that the following conditions need to be satisfied for this
>>> attack:
>>> i) Chosen-prefix collisions can be found in the hash function within
>>> the lifetime of the TLS handshake timeout of the victim.
>>> ii) The victim reuses ephemeral keying material several hundred
>>> times and for a time lasting at least as long as the time for part (i) of
>>> the attack.
>>> iii) The attacker can learn or control the value of the first shared
>>> secret in the hybrid shared secret concatenation.
>>> iv) The attacker is able to control the length of the first shared
>>> secret, so that -- for the iterative component of the attack -- the hash
>>> block boundary lands at different positions within the second shared secret.
>>>
>>> Although different standardized groups do not all have the same shared
>>> secret length, for all DH/ECDH groups for TLS 1.3 standardized in RFC 8446,
>>> once the group is fixed (during negotiation), the shared secret is fixed
>>> length, so condition (iv) is not satisfied for stock TLS 1.3. All NIST
>>> Round 3 finalist and alternate candidate KEMs currently have fixed-length
>>> shared secrets, so they would not satisfy condition (iv) either, if a
>>> post-quantum KEM was used as the first component in concatenation. It may
>>> be possible that other organizations have bespoke key exchange methods they
>>> would want to use in a hybrid format, which might be variable length, but
>>> we don't have any information about that. Even still, the three other
>>> conditions of the attack would need to be satisfied. We think that's a
>>> pretty high barrier and as such have decided not to incorporate
>>> countermeasures at this time, but if the working group prefers otherwise,
>>> we can do so. For example, Nimrod and his colleague
s
> ha
>>> ve proposed a KDF design that would be secure even in this scenario, but it
>>> has substantially more hash function applications that the current
>>> HKDF-based approach does.
>>>
>>> Douglas
>>>
>>>
>>> [1] https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/
>>> [2] https://mailarchive.ietf.org/arch/msg/tls/F4SVeL2xbGPaPB2GW_GkBbD_a5M/
>>> [3] https://github.com/nimia/kdf_public#readme
>>> [4] Practical key-recovery attack against APOP, an MD5-based
>>> challenge-response authentication. Leurent, Gaetan.
>>> [5] Practical Password Recovery on an MD5 Challenge and Response. Sasaki,
>>> Yu and Yamamoto, Go and Aoki, Kazumaro.
>>> [6] https://en.wikipedia.org/wiki/CRIME
>>> _______________________________________________
>>> TLS mailing list
>>> TLS@ietf.org
>>> https://www.ietf.org/mailman/listinfo/tls
>> _______________________________________________
>> TLS mailing list
>> TLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/tls
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls
