Subject: Re: [tcpinc] TCP-ENO draft 02 review - collision-resistant

From: "Black, David" <[email-masked]>
Date: Tue, 5 Jul 2016 18:29:33 +0000

David>  WRT the collision discussion, a definition of what “collision-resistant” means in cryptographic terms would help here (this could be informal/summarized with  a reference to another doc), especially if accompanied by  an example to help implementers (e.g., concatenate all inputs, feed to HMAC with a good cryptographic hash/PRF,  along with some suitable recommendation on what to use for the K[ey] input to HMAC).

Thanks, --David

> [5.1] q( The session ID MUST depend in a collision-resistant way on fresh
> data contributed by both sides of the connection. ). Is this clear enough
> to rule out specs that, for instance, take random data from each side and
> XOR it? I think it does if "collision-resistance" is interpreted as
> applying to the set of raw inputs to the session ID computation; it doesn't
> if a spec author interprets it as applying to the string used as the input
> to the collision-resistant compression function they employ to produce the
> final session ID, where that string is some function of the raw inputs.

XOR is not collision-resistant.  I'm not sure I understand your second
interpretation well enough to craft language to rule it out.  Do you
have any suggested language?

I'm not sure, because the potential misunderstanding is really subtle. Let's say a spec says:
session ID = PRF('foo', (client_random XOR server_random) || other inputs)
This is collision-resistant in the sense that the underlying PRF is collision-resistant, so (wlog) an adversarial client can't for example choose two different client_randoms for a given server_random and get the same session ID; but it *can* choose a client_random for any given server_random such that the XOR of the two is the same, which may result in the session ID being the same for multiple connections. This isn't a collision in the PRF: it's a collision in the tuple of inputs to the PRF. (I'm not sure I'm explaining this clearly; let me know.)

I think your language does literally prohibit this case (the overall session ID function in my example isn't collision-resistant on its tuple of inputs), but it's really subtle and spec designers might screw it up. Maybe I'd be happy with q( The session ID MUST depend in a collision-resistant way on fresh data contributed by each side of the connection. ). Or maybe I'd separate out collision-resistance entirely:
<<EOF
 o  The session ID MUST be collision-resistant on its tuple of inputs.

 o  The session ID MUST depend on fresh data contributed by each side of the connection.

 o  The session ID MUST depend on any public keys, public Diffie-Hellman parameters, or other public asymmetric cryptographic parameters that are employed by the encryption spec and have corresponding private data that is known by only one side of the connection.
 o The session ID MUST depend on the negotiation transcript specified in Section 4.7.
EOF
Now I've created a new problem, which is: does this combination of constraints imply that the session ID cannot depend only on the first bit of (for example) the negotiation transcript? I'm not sure; maybe it would be better to explicitly state that "The negotiation transcript specified in section 4.7 MUST be included in the tuple of inputs to the session ID computation."
If I am being too pedantic, feel free to ignore. I am probably going way beyond what is reasonably required in terms of precision.

---

From: Kyle Rose <[email-masked]>
Date: Tue, 5 Jul 2016 14:35:59 -0400

I think David M's proposed resolution here has the precision I'm looking
for:

  o  The session ID MUST depend in a collision-resistant way on all of
      the following (meaning it is computationally infeasible to produce
      collisions of the session ID derivation function unless all of the
      following quantities are identical):

...after which he lists the various inputs to the session ID. In
particular, the part in parentheses eliminates the classes of Murphy I was
concerned about.

Kyle

On Tue, Jul 5, 2016 at 2:29 PM, Black, David <[email-masked]> wrote:

>
>
> David>  WRT the collision discussion, a definition of what
> “collision-resistant” means in cryptographic terms would help here (this
> could be informal/summarized with  a reference to another doc), especially
> if accompanied by  an example to help implementers (e.g., concatenate all
> inputs, feed to HMAC with a good cryptographic hash/PRF,  along with some
> suitable recommendation on what to use for the K[ey] input to HMAC).
>
>
>
> Thanks, --David
>
>
>
> This is collision-resistant in the sense that the underlying PRF is
> collision-resistant, so (wlog) an adversarial client can't for example
> choose two different client_randoms for a given server_random and get the
> same session ID; but it *can* choose a client_random for any given
> server_random such that the XOR of the two is the same, which may result in
> the session ID being the same for multiple connections. This isn't a
> collision in the PRF: it's a collision in the tuple of inputs to the PRF.
> (I'm not sure I'm explaining this clearly; let me know.)
>
> I think your language does literally prohibit this case (the overall
> session ID function in my example isn't collision-resistant on its tuple of
> inputs), but it's really subtle and spec designers might screw it up. Maybe
> I'd be happy with q( The session ID MUST depend in a collision-resistant
> way on fresh data contributed by each side of the connection. ). Or maybe
> I'd separate out collision-resistance entirely:
>
> <<EOF
>
>  o  The session ID MUST depend on any public keys, public Diffie-Hellman
> parameters, or other public asymmetric cryptographic parameters that are
> employed by the encryption spec and have corresponding private data that is
> known by only one side of the connection.
>
> Now I've created a new problem, which is: does this combination of
> constraints imply that the session ID cannot depend only on the first bit
> of (for example) the negotiation transcript? I'm not sure; maybe it would
> be better to explicitly state that "The negotiation transcript specified in
> section 4.7 MUST be included in the tuple of inputs to the session ID
> computation."
>
> If I am being too pedantic, feel free to ignore. I am probably going way
> beyond what is reasonably required in terms of precision.
>
>
>

---

From: "Black, David" <[email-masked]>
Date: Tue, 5 Jul 2016 19:11:22 +0000

Aha, yes, that explanation suffices to explain what collision resistance means to non-experts ...

Thanks, --David

From: Kyle Rose [mailto:[email-masked]]
Sent: Tuesday, July 05, 2016 2:36 PM
To: Black, David
Cc: David Mazieres expires 2016-09-29 PDT; tcpinc
Subject: Re: [tcpinc] TCP-ENO draft 02 review - collision-resistant

I think David M's proposed resolution here has the precision I'm looking for:

...after which he lists the various inputs to the session ID. In particular, the part in parentheses eliminates the classes of Murphy I was concerned about.
Kyle

On Tue, Jul 5, 2016 at 2:29 PM, Black, David <[email-masked]<mailto:[email-masked]>> wrote:

Thanks, --David