C2S/S2C lifetime

Sun Feb 3 02:50:15 UTC 2019

[I have re-ordered the quoted text to fit my response ordering.]

On 2/2/19 7:13 PM, Gary E. Miller via devel wrote:
>> Hal's comments and the quote from Daniel are about whether it is
>> necessary to require rotation of C2S/S2C, not K.
> 
> Yes.

This discussion was originally about why it is not necessary to rotate
C2S/S2C. You have shifted it to a discussion about attacks on K.

>> Clients can keep their own lifetime to enforce
>> rotation of it (by re-running NTS-KE), but when Hal asked the working
>> group, Daniel said that is not necessary:
>
> Yes.  Using flawed assumptions.  Such as only one client using the
> same key.

That's not a flawed assumption in the context of attacks on C2S/S2C. A
client following the spec has a separate C2S/S2C for every association,
and it is specific to that client. In the context of attacks on C2S/S2C,
if the client willingly shares C2S/S2C in plaintext with someone else
(other than the server), the client has already compromised C2S/S2C by
its own actions. There is nothing in the protocol which does this.

Now, in the context of attacks against K, sure you can have multiple
coordinating clients sharing a C2S/S2C as part of the effort to break K.
I'll discuss that later.

> Since their IS a recommended limit, it should be respected.  And
> very conservatively.

The limit is on how many messages should be encrypted by a single key.

For C2S/S2C, the limit is applicable to a normally functioning client
(and server). A separate key is used in each direction, so we can
consider each direction separately (i.e. we do not need to halve the
limit or double the count for request/response pairs).

Even with the worst case assumptions of AES-GCM and minpoll 4, that
limit is 2,176 years. C2S/S2C are re-keyed at least on client restart. I
believe 2,176 years is "very conservative[]" relative to client ntpd
restarts. Do you disagree?

Therefore, I conclude that it is safe to use even AES-GCM in ntpciphers
to protect C2S/S2C. It should not be the default (AES-SIV should be),
and it should only be implemented if there is a desire to have an
alternate algorithm to AES-SIV already supported by the installed base,
just in case.

For K, the limit is applicable to the number of messages transmitted by
a server ntpd, or a set of cooperating ntpds sharing K.

If we assume the attacker can somehow capture all or substantially all
of the traffic transmitted by that ntpd, it doesn't really matter
whether this is attacker generated traffic or legitimate traffic. If
they can't capture it all, it would have to be attacker generated
traffic, but I'll stipulate (for argument's sake at least) that
attackers can generate lots of traffic that might go unnoticed (e.g. due
to the volume of legitimate traffic, e.g. at NIST scale).

The server chooses its algorithm for protecting K independent of the
clients. It is not required to support AES-GCM, so it can gain a
significant factor of protection (2^32 to 2^48) by using only AES-SIV as
recommended by Daniel. However, as above, maybe we want some crypto
diversity, just in case a future problem is found with AES-SIV. So maybe
we do allow AES-GCM too, and thus need to consider that case, so we're
at 2^32 messages.

If we assume the recommended rotation of daily, keeping one old K,
2^32/2/24/60/60 = 24,855 requests/sec per K with AES-GCM. In comparison,
1628906115 request/sec per K with AES-SIV.

NIST handled nearly that many (28,254 requests/sec average) in 2016 on a
single server:
https://nvlpubs.nist.gov/nistpubs/jres/121/jres.121.003.pdf

So I conclude that using AES-GCM to protect K is a real problem at NIST
scale, even if they don't share K across servers, with a daily rotation
schedule (assuming a world where everyone implemented NTS).

Rotating more frequently is one possible solution. However, they almost
certainly need to keep a client's cookie valid for at least 1024 seconds
(17 hours), as that is a common polling window. So K needs to be valid
at least that long (i.e. rotate K every 9 hours keeping one old K).
Trying to support a maxpoll of 17 (36.4 hours) is really pushing the
boundaries of an AES-GCM protected K at NIST load, even if K is per
server, unless they deploy more servers (to get more Ks) than they used
in 2016.

Another option, I suppose, might be to support multiple Ks in use at a
time, such that the clients are split across them. That would add some
complexity that seems unnecessary given the alternative of just using
AES-SIV.

So I think I conclude that we'd be pushing the boundaries of safety at
NIST scale if AES-GCM is used. There, it seems we should not use AES-GCM
for the cookies, to protect K, only using AES-SIV there.

>> The NTS protocol does
>> not rotate C2S/S2C.
> 
> Yes, that is bad.
The client is not attacking C2S/S2C, because they have C2S/S2C. I've
addressed the general limit on messages above. If you want to discuss
some other, specific attack on C2S/S2C, please describe it.

>>> The recommendation for AES-SIV is to encrypt no more than 2**48
>>> messages under the same key. At one message per second that's
>>> almost 9 million years. If you (unwisely) use AES-GCM instead,
>>> where the recommended limit is 2**32 messages, that's still 136
>>> years.  
>>
>> The client isn't going to be sending one message per second either.
>> minpoll has a lower limit of 16 seconds. So these numbers can be
>> scaled up by 16.
> 
> But what if a thousand AWS instances hit the NIST servers with the same
> cookie for days, weeks, months.  Each at one second intervals.  10e11
> comes quickly
Again, for clarity: if multiple clients are sharing the same C2S/S2C
("the same cookie"), they are not attacking C2S/S2C, as they have that.
They are attacking K.

The implementation decides how to handle K. The draft just makes a
suggestion. (In fact, the whole thing suggesting K at all is just a
suggestion for the cookie format, but it's likely the general approach
that will be used by most implementations.)

Assuming we're following the recommendation, then K will be rotated with
a lifetime of two days. So the attacker's window to breach K is not
weeks or months, it is two days. Once that window closes, they have to
start over against a new K.

If each K is randomly generated (let's address ratcheting separately),
do you agree that the window for attack is however long K is valid,
which by the recommendation is two days?

If so, then as discussed above, AES-SIV should be fine to protect K, but
AES-GCM seems dangerous at NIST scale.

> The key is NOT rotated and NOT replaced.  It is 'ratcheted'.

This is only a suggestion. It may be better to just generate random Ks
that the NTS-KE and NTP server share. And also accept as a design
constraint that NTP servers do not share K.

A large installation could then work like this:

1) Present a name time.example.com pointing to a single IPv4 as before.
2) As before, this IP hits a load balancer.
3) (Non-NTS) NTP traffic on UDP port 123 to this IP continues to go to
   the backend servers as always.
4) NTS-KE traffic on TCP port TBD to this IP is load balanced to the
   backend servers in the same way.
5) The backend servers each have ntpd listening on port 123 and a
   separate NTP port for NTS. (Or there are separate NTS and non-NTS
   servers. The non-NTS listen only on 123 and the NTS listen only
   on one port which is separate for each server.) For example, server A
   uses port 1000, server B uses port 1001, etc. The NTS-KE daemon on
   server A will direct clients to the load balanced public IP on port
   1000 and server B will direct clients to port 1001.
6) When clients hit the public IP on UDP port 1000, the load balancer
   directs it to server A. When they use port 1001, it goes to server B.

I have configured load balancers before, and the setup above is trivial.

In this way, each NTS-KE/NTP server is fully independent (which is a
nice property anyway) with no need to share K. Then, K can just be
randomly generated, which takes away any concern about the ratcheting
mechanism weakening security.

> So any master key K that I can eliminate today, I can use the same
> ratchet, and eliminate tommorrow.

I am not well-versed enough to know if this is correct or not. It
*sounds* reasonable to me, which would argue against using the
ratcheting mechanism.

-- 
Richard

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <https://lists.ntpsec.org/pipermail/devel/attachments/20190202/5124bd66/attachment-0001.bin>