Subject: [Ntp] Last minute annoying discovery about NTS

From: Watson Ladd <[email-masked]>
Date: Wed, 20 Mar 2019 12:33:50 -0700

Dear all,

I really apologize for sending this message so late in the process,
but there is a problem with NTS in draft-17.

The cookie encrypts S2C and C2S under a key known to the server, but
then the response encrypts the cookie under S2C. This creates a
situation where we are encrypting plaintext that depends on the key,
which complicates the security analysis. (And by complicates I mean
there are contrived ciphers meeting the ordinary security notion that
would be completely insecure in such a protocol: one has to not use
generic analysis: it's a pain to deal with. see
https://eprint.iacr.org/2010/144.pdf)

One solution would be for the cookie to contain the new keys which the
server picks at random (and of course the client strips them out
before sending the rest of the cookie to the server). Again, I
apologize for only just noticing this detail.

Sincerely,
Watson Ladd

---

From: Daniel Franke <[email-masked]>
Date: Wed, 20 Mar 2019 16:18:27 -0400

Are you certain the standard security definitions don't suffice? If
the S2C key were directly being encrypted under itself, then a
circular-secure cipher would be needed. Ditto if you were to encrypt
the S2C key under the master key and also encrypted the master key
under the S2C key. We're producing the cookie by encrypting the S2C
key under the master key, and then for transmission we're encrypting
the resulting ciphertext under the S2C key. But at no point does the
master key ever get encrypted under the S2C key; the master key never
leaves the server even as ciphertext. So I don't think we actually
have a loop here.

On Wed, Mar 20, 2019 at 3:34 PM Watson Ladd
<watson=[email-masked]> wrote:
> _______________________________________________
> ntp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ntp

---

From: Watson Ladd <[email-masked]>
Date: Wed, 20 Mar 2019 13:29:05 -0700

> leaves the server even as ciphertext. So I don't think we actually

Any sort of encryption of a function of the key is a call the experts
situation. So the question for the experts: if E_K(M) is an AEAD
scheme, and K1, K2 keys
is E_{K1}(E_{K2}(K1)) a sane thing to do, or is it a problem from a
proof perspective? What if I am allowed to change the inner or outer
schemes to any AEAD scheme?

---

From: Aanchal Malhotra <[email-masked]>
Date: Wed, 20 Mar 2019 13:30:52 -0700

This reference for KDM security might be useful.
https://eprint.iacr.org/2010/513.pdf

---

From: Watson Ladd <[email-masked]>
Date: Wed, 20 Mar 2019 17:46:03 -0700

I've managed to convince myself Daniel is right and there is no problem.

On Wed, Mar 20, 2019, 1:31 PM Aanchal Malhotra <[email-masked]> wrote:

> https://eprint..iacr.org/2010/513.pdf
> <https://eprint.iacr.org/2010/513.pdf>
>
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 21 Mar 2019 09:38:07 +0100

> I've managed to convince myself Daniel is right and there is no problem.

That's great to hear :).

I have been meaning to ask something that may possibly be related.

The draft recommends servers to rotate their master keys. Shouldn't it
also recommend the clients to refresh their keys, i.e. rerun the
NTS-KE occasionally (e.g. once per week)? If attackers could get an
(old) server key, they would also get all S2C/C2S keys from cookies
encrypted by that key that were captured in the network, and use them
for MITM attacks on clients that are still using those S2C/C2S keys.

Either the keys need to be refreshed, and that should happen on both
sides, or they don't, right? I may be missing an important detail
here.

-- 
Miroslav Lichvar

---

From: Daniel Franke <[email-masked]>
Date: Thu, 21 Mar 2019 10:07:02 -0400

I think I might nonetheless spend my flight to Prague formalizing a
security proof, mostly as an exercise to improve my proficiency
working in the standard model. My intuition here is mostly that, even
if the adversary is given K1, it still can't distinguish E_{K2}(K1)
from E{K2}(R) for random R; there therefore shouldn't be anything
"special" about using E_{K2}(K1) as an input to E_{K1}(.). A colleague
has sketched out a plausible hybrid argument which sort of matches
this intuition. I'm going to take that argument and see if I can run
with it.

On Wed, Mar 20, 2019 at 8:46 PM Watson Ladd <[email-masked]> wrote:
>> On Wed, Mar 20, 2019 at 1:29 PM Watson Ladd <watson=[email-masked]> wrote:
>>>

---

From: Dan Brown <[email-masked]>
Date: Thu, 21 Mar 2019 16:58:25 +0000

What's the added value of key-dependency in E_K1(E_K2(K1)) over, say,
Hash(K1+K2), or E_K1(1)+E_K2(2), or some other kind of key confirmation,
etc.?  

Also, should there be messages, as in E_K1(M1+E_K2(K1+M2)) to limit the
scope of replay attack to a particular message? 

For weak enough E, the value E_K1(E_K2(K1)) seems weak.  For example, if
e.g. E_K(M) = K xor M, then E_K1(E_K2(K1))=K2, which is probably bad if K2
is necessary for any other purpose, etc.  If there is no E_K2 oracle for the
adversary, then very weak E meets Shannon's theorem about one-time pads, so
E_K2(K1) and E_K2(R) are indistinguishable. So, any security proof (of what
goal?) would need more than this indistinguishability, either some extra
property E (not held by E_K(M) = K xor M).

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Daniel Franke
> Subject: Re: [Cfrg] [Ntp] Last minute annoying discovery about NTS
> 
security
> proof, mostly as an exercise to improve my proficiency working in the
standard
> model. My intuition here is mostly that, even if the adversary is given
K1, it still
> can't distinguish E_{K2}(K1) from E{K2}(R) for random R; there therefore
> shouldn't be anything "special" about using E_{K2}(K1) as an input to
E_{K1}(.).
> A colleague has sketched out a plausible hybrid argument which sort of
> matches this intuition. I'm going to take that argument and see if I can
run with
> it.