Subject: [ntpwg] Autokey-Protocol Analysis

From: Stephen Röttger <[email-masked]>
Date: Tue, 02 Aug 2011 22:11:55 +0200

Hello everyone,

Since the discussion about the Autokey-Protocol in June ended abruptly,
we want to inform you, that we finished our analysis of the protocol and
found several weaknesses, that render it completely useless.
Our analysis is in German, but if you are interested in it, we can
summarize the weaknesses for you.

In addition, we came up with some changes to the protocol, that mitigate
the vulnerabilities and would like to present you a revised
Autokey-protocol.
The changes are:

-Use the Clients Public Key used for cookie-encryption as input to the
cookie calculation. For example, calculate the Cookie as
  C = H(PubKey, ServerSeed).

-Change the length of Cookie and Server Seed from 32 to 128 bit.

-Replace the Identity Schemes with a common X.509 PKI, where the Clients
are in possession of certificates of Trusted Authorities

-Let the Signature included in extension fields cover the whole NTP-packet

-(optional) use HMAC for MAC-calculation and switch the used
Hash-Algorithms to SHA-256

Regards,
Dieter Sibold and Stephen Röttger
_______________________________________________
ntpwg mailing list
[email-masked]
http://lists.ntp.org/listinfo/ntpwg

---

From: Greg Dowd <[email-masked]>
Date: Tue, 2 Aug 2011 20:23:57 +0000

Hi Stephen,
	I am very interested in your analysis.  Do you have any plans to publish the results in English?  If not, are the results available in German?  I have a number of German colleagues and I may be able to ask them to translate the document for us.

Greg Dowd
gdowd at symmetricom dot com (antispam format)
Symmetricom, Inc.
www.symmetricom.com
"Everything should be made as simple as possible, but no simpler" Albert Einstein
-----Original Message-----
From: ntpwg-bounces+gdowd=[email-masked] [mailto:ntpwg-bounces+gdowd=[email-masked]] On Behalf Of Stephen Röttger
Sent: Tuesday, August 02, 2011 1:12 PM
To: NTP Working Group
Subject: [ntpwg] Autokey-Protocol Analysis

Hello everyone,

Regards,

---

From: todd glassey <[email-masked]>
Date: Tue, 02 Aug 2011 13:53:37 -0700

On 8/2/2011 1:11 PM, Stephen Röttger wrote:
> found several weaknesses, that render it completely useless
Yep...
> -Change the length of Cookie and Server Seed from 32 to 128 bit.
Good
> are in possession of certificates of Trusted Authorities
YES, but we also may want to integrate some OTPW type token controls as 
well.
> -Let the Signature included in extension fields cover the whole NTP-packet
YES
> Hash-Algorithms to SHA-256
As long as you are allowing optional algs - then we should support ANY 
algs as well as HSM modules too.

-- 
Todd S. Glassey
This is from my personal email account and any materials from this account come with personal disclaimers.

Further I OPT OUT of any and all commercial emailings.

---

From: Harlan Stenn <[email-masked]>
Date: Tue, 02 Aug 2011 14:04:30 -0700

Hi Stephen and Dieter,

I'm interested in the paper and analysis.

I'd be happy to see at least a link to this paper on the support.ntp.org
site, and in another month I'd like to see it somewhere else (that I'll
talk about in 2-3 weeks' time).

H

---

From: Danny Mayer <[email-masked]>
Date: Wed, 03 Aug 2011 00:00:50 -0400

> Since the discussion about the Autokey-Protocol in June ended abruptly,

Sorry about that. It wasn't meant to leave this dragging. July tends to
be the start of a lot of people's holidays but you weren't forgotten. In
fact the subject was mentioned last week at the IETF Conference.

> summarize the weaknesses for you.

It's really important to understand what these are. So if you can send
us a pointer to the paper even if in German and also tell us here what
you perceive the weaknesses are we can make a start on resolving the issues.

>   C = H(PubKey, ServerSeed).

Why do you think that it is necessary to go to all this trouble and
Where would the server get the client's public key?

> -Change the length of Cookie and Server Seed from 32 to 128 bit.
Fine but what does it really buy us?

> are in possession of certificates of Trusted Authorities

Does the PKI depend on reliable timm?

> -Let the Signature included in extension fields cover the whole NTP-packet

You need a way to signal this.

> Hash-Algorithms to SHA-256

This has already been raised as an issue. We believe it's just a minor
issue in the reference implementation and the protocol already supports
this. We don't believe that it is necessary to change the protocool for
this.

Danny

---

From: Stephen Röttger <[email-masked]>
Date: Wed, 03 Aug 2011 14:52:01 +0200

Greg,
Yes, there are plans to publish the results in english.
The german version is not public yet, but presumably will be in a few weeks.
However I can summarize the discovered vulnerabilities (mainly for
client-server-mode):

-The bitlenghts of the cookie and the server seed are only 32 Bit long.
This leads to an attacker being able to Brute Force them.
For example he can request a cookie from a server and try all 2^32
possibilites as server seed and calculate corresponding cookies. If he
finds one that matches the cookie he received from the server, he has
found the secret server seed and can consequently calculate cookies for
every client.
The same applies for brute-forcing the cookie. The attacker can
intercept a packet with a MAC and try to generate the MAC himself using
every possible of the 2^32 cookie-values, till he found the one that
matches.
For comparison, 2^32 MD5 calculations take roughly 25minutes on my
2,5ghz laptop using only one thread. (though cookie brute-forcing will
take 2 MD5 calculations for each try)

-The Identity Schemes (except the private certificate scheme) provide no
security.
The TC scheme accepts a certificate as that of a Trusted Authority if it
includes a extension 'CA=True'. Nothing prevents an attacker from
generating such a certificate himself.
We discovered a flaw in all three challenge-response identity schemes
(IFF, MV, GQ), that allowed us to send a response that would always be
accepted by the client. In addition, the challenge-response schemes
don't offer protection against a man-in-the-middle. Such an attacker
might just forward the clients challenge to the real server, get the
correct answer and again forward this to the client.

-The server identifies clients using their IP-Address (which is easily
forgable). An attacker can send a cookie request to the server using the
clients IP and the server will send the clients cookie to this IP
encrypted with the Public Key attached to the request. Since the
attacker chose this Public Key, he can intercept the response and
decrypt the cookie.
The cookie can then be used to calculate MACs and masquerade as the server.
(We wrote proof-of-concept code for this last attack and were able to
change a clients time as a man-in-the-middle)

Stephen

---

From: Stephen Röttger <[email-masked]>
Date: Wed, 03 Aug 2011 15:01:34 +0200

Todd,

> On 8/2/2011 1:11 PM, Stephen Röttger wrote:
[...]
> YES, but we also may want to integrate some OTPW type token controls as
Can you explain this further? Do you refer to the way how the
autokey-lists are generated (roughly after lamports otp-scheme)?
This seems to add protection only against forging of messages but no
additional protection against modification attacks.
> algs as well as HSM modules too.
We analyzed the use of MD5 and the simple MAC-Algorithm used
(H(key||packet)) and could not find any vulnerabilities in this, though
MD5 is known to provide no collision-resistance.
The security demands to the hash function include only, that it provides
preimage-resistance (which MD5 still does).
Changing the used algorithms would simply be to provide the possibility
of fips 140-2 compliance. I am not sure if this is needed though.

Stephen

---

From: Stephen Röttger <[email-masked]>
Date: Wed, 03 Aug 2011 15:08:30 +0200

Harlan,

as I wrote to Greg, the german paper is not yet public and we plan to
release it in a few weeks.
But I hope the summary in my mail to Greg will give an idea of the
vulnerabilities.

Stephen

---

From: Stephen Röttger <[email-masked]>
Date: Wed, 03 Aug 2011 15:26:10 +0200

[...]
> Why do you think that it is necessary to go to all this trouble and
Please see my third point in my mail to greg.
Since the server holds no state about clients, he has no way of checking
that consecutive requests from an IP-address belong to the same client.
Therefor, an attacker can spoof his IP to that of a client and can
request the corresponding cookie from the server.
If the public key is included in this calculation, he will either not
get the same cookie as the client does or he will not be able to decrypt it.
> Where would the server get the client's public key?
The Client would have to attach it's public key to every request.
As a side note:
Since the length of the public key would cause the MAC calculation to
use at least one additional Round of the used hash-function, it could be
switched to the hash of the public key:
	C = H(H(PubKey), ServerSeed)
In this case there would be no additional overhead to the MAC-calculation.
> Fine but what does it really buy us?
Again, please see point 1 in my mail to greg.
A 32-bit cookie and server seed can be easily brute-forced by an attacker.
> Does the PKI depend on reliable timm?
That is an interesting question.
The public key infrastructure used by SSL/TLS relies on certificate
revocation lists and expiration dates.
Expiration Dates can obviously not be verified before having doing the
time synchronisation, but that seems to be a chicken-or-egg problem.
> this. We don't believe that it is necessary to change the protocool for
Yes, we also think that this is not critical.

---

From: todd glassey <[email-masked]>
Date: Wed, 03 Aug 2011 08:02:53 -0700

On 8/2/2011 9:00 PM, Danny Mayer wrote:
> Why do you think that it is necessary to go to all this trouble
As to why, it brings NTP into compliance as another tool using the x509 
identity control models.  This means that parties running NTP as a part 
of a larger practice can use the same identity sets for everything 
making this model more easily audited.
> and

As to how , there are any number of ways this can be resolved including 
a new Key Lookup Request Type fo' verifying 'right to connect' type acl 
controls.
> Fine but what does it really buy us?
A better and larger key seed (or nonce) .
> Does the PKI depend on reliable timm?
It would depend on how long the cert is valid for so yes it can

> You need a way to signal this.
Agreed but its doable.

---

From: todd glassey <[email-masked]>
Date: Wed, 03 Aug 2011 12:45:22 -0700

> autokey-lists are generated (roughly after lamports otp-scheme)?
yes but we did a key exchange system called BLUNT TUNNELING back at 
Coastek for the collapsed TCP/IP stack (it ran in the User Space instead 
of OS/System Space) and that would work rather well here I think.
> additional protection against modification attacks.
Yes I agree - but this was an original design consideration which we are 
paying for now.
> MD5 is known to provide no collision-resistance.
Agreed, but the v3 of the NSA SUITE-B tools would be what I was looking 
at.  Possibly also some of Suite-A v1... To do this we need an open 
interface for the crypt subsystem.  Also building the sense of COI's 
(Communities of Interest) into the package would help.

As another option RFC 2522 key management could be interesting as well.

> preimage-resistance (which MD5 still does).
yes...
> of fips 140-2 compliance. I am not sure if this is needed though.
it is... trust me on that. So is a full end-to-end CODE BLUEPRINTING 
which is the last step in a Release Engineering effort (at least in the 
ones who worked for me). The BP was a formal trace run and security 
analysis which documented each thread and its actions within the code 
when called.

---

From: "David L. Mills" <[email-masked]>
Date: Thu, 04 Aug 2011 16:13:26 +0000

Stephen,

Thanks for your contributions in a security analysis of the Autokey 
protocol, although it might have wider appeal in English. As it is, my 
German is decidedly rusty, but I could translate if necessary. 
Meanwhile, I have further refined my own analysis in the white paper  
Security Analysis of the NTP Protocol 
http://www.eecis.udel.edu/~mills/security.html, which includes probably 
the same vulnerabilities as you report.
My analysis and most probably yours, identify two serious middleman 
hazards, what I call the cookie snatcher and propaganda attacks. The 
former is a tough one to fix and may yield to your insights, but I am 
confused by your suggested fix. Any true fix has to consider both the 
server private value and some sort of client private value, perhaps the 
host encryption key.

For others that might be reading this message and for historical 
context, the original Autokey design was circa 1996 as documented in an 
internal report. Subsequently in the early 2000s the design was reviewed 
by the STIME task force, which resulted in a revised specification in 
late 2005. That document was submitted as an informational RFC and 
eventually published five years later as RFC 5906. That RFC is intend as 
target practice and a possible starting point for new algorithms. One 
might observe this protocol is fifteen years old and the specification 
was last reviewed in 2005. In any case, the existing code is 
specifically designed in a modular fashion and can be removed and 
replaced in whole or in part with evolved algorithms.

Note that our current discussion is on client/server mode that might be 
used by a national time server network. However, the algorithms and 
protocol also have to work in both basic and interleaved modes, and in 
symmetric and broadcast modes. The algorithms and protocol also have to 
support multiple security groups, as defined in the specification.  I 
suspect your analysis does not consider these modes, but mine does. 
There continues to be issues in the initial volley in broadcast mode, 
where the present code does not precisely calibrate the roundtrip delay. 
Corrections for this are included, along with a careful analysis, in the 
white paper Analysis and Simulation of the NTP On-Wire Protocols 
http://www.eecis.udel.edu/~mills/onwire.html.

There is a serious disconnect about the design intent of the protocol. 
It was designed to operate with no assistive infrastructure at all. The 
DNS is not necessary and there are no provision for certificate 
verification other than the trusted host, for example a national time 
server,. While not the original motivation for this model, it is 
appropriate for the Mars spacecraft model suggested in Chapter 17 of my 
book. Since the light time between Mars and Earth can be as much as 40 
minutes, access to Earth infrastructure is highly awkward.  Even so, the 
certificate format conforms to X.500v3 and the certificate trail is 
verified as in conformant PKI practice.

Your suggestion about signing the entire NTP packet has bee considered 
before. However, a constraint you might have observed is that, except 
for the glaring case of the cookie request, signatures are always 
computed offline. Signing something in a flux of 3000 requests per 
second is not an option..

Meanwhile, your suggestion on server cookie length and hash algorithm 
are highly useful. Cookie length is easy to change, although it raises 
backward compatibility issues. As you might have noticed in recent 
documentation, selection of any hash algorithm supported by the OpenSSL 
library is now possible.

I suspect there is not much more to say, so I recommend these issues be 
raised and discussed by the working group at an upcoming IETF meeting. I 
can't volunteer to do much, as my eyesight is dwindling to nothing and 
messing with code is impractical.

Dave