Kickstarting roughtime again
131 views
Skip to first unread message
Christer Weinigel
Jan 10, 2024, 9:42:54 AM1/10/24
to proto-roughtime
Hi everyone,
it's been fairly quiet here for a while. I'd like to try to get the Roughtime development started again. I've composed this much too long mail with my thoughts and questions about roughtime. I'm posting it here and will also post it to some other mailing lists that I think might be interested.
I am reaching out to groups for whom Roughtime could be relevant in order to get a deeper understanding of the various requirements and possible use-cases. Please take a look at the questionnaire at the end of the mail and let me know any answers you may have. The more details we can get from the technical community at this stage, the more likely it is we can develop the protocol in the right direction, I have included a lot of details on Roughtime for those who might not be familiar with the work done so far and the background here.
Background
Time is important for many applications and to be able to set the internal clock of a device in a secure way is also important. There already exist some protocols for secure time transfer such as authenticated NTP and NTS. Authenticated NTP using shared secrets does not scale to a large number of clients and is thus rather unsuitable for IoT. NTS has a bootstrapping problem (more about that later) and in my opinion, might be a bit too heavyweight for resource constrained devices such as IoT devices.
Roughtime started out as a secure protocol for time transfer which solves the bootstrapping problem. The Roughtime protocol has evolved over time and is now a fairly generic protocol for secure time transfer. I believe that Roughtime, or at least something like it, could be very useful, especially for resource constrained devices.
Roughtime has been around for a few years as an IETF draft, but unfortunately, the development has stalled a bit. I've been talking to people at IETF and RIPE meetings and my impression is that it's not only me that is interested in Roughtime. Netnod recently received some funding from the RIPE Community Fund to kickstart the development of Roughtime. I'd like to start by collecting feedback from all of you.
This mail is fairly long. I'll start out by trying to explain what I think are the key principles and ideas behind Roughtime and how it relates to other secure time transfer protocols such as authenticated NTP and NTS. At the end I have a list of questions that I'd like to get feedback on.
My goal is to figure out what Roughtime actually should do to be useful and to ensure that it provides what you need, but does not contain unnecessary features that you don't need. Then we can update the Roughtime draft based on that feedback and, finally, submit it to the RFC editors.
What is Roughtime?
Roughtime principles
Roughtime is a time transfer protocol which signs responses from the server using a private key. A client can then use the server's public key to verify the response. Currently, the public key algorithm used is Ed25519, but the protocol does allow for other algorithms in the future.
One of the basic principles behind how Roughtime solves the bootstrap problem is that it hard codes these public keys for Roughtime servers. It is expected that this list can be updated, either by downloading a new list when the system has finished bootstrapping, or by keeping the list as a part of the firmware. That means a new list is installed when the firmware is updated.
Another aspect of Roughtime is that a client is expected to keep a fairly large list of Roughtime servers. When a device boots it queries random servers from this list until a number of servers all agree on what time it is. If a few servers on the list have stopped working or send t bad time (regardless of whether it's due to malfunction or attack), this should not be a big issue if one requires enough good servers to agree on time.
This last point is not a requirement though, Roughtime could be used with just a few, or even just a single server that one trusts completely. Basically, the idea here would be similar to the way one uses authenticated NTP, but using public keys instead of shared secrets. This could be a company that wants to run its own Roughtime servers and only use those. Another example is if Roughtime is used to distribute time within a system, for example with multiple devices connected to a local network that has to keep consistent time with one local server.
Roughtime has protection against replay attacks. A Roughtime client is expected to pass a "nonce", a 32 byte random and unique block of data, in each request. The Roughtime server will sign this nonce together with the timestamp in its response. If the nonce in the response matches what the client sent out the client knows that it is actually a response to its request and not to an earlier one.
A client is allowed to pass any data as the nonce though. For example the nonce could be a 32 byte cryptographic hash of a document. The Roughtime server can thus be used as a lightweight time stamping authority (TSA) giving a cryptographic proof that the client was in possession of a specific document at a specific point in time. This proof can be verified using the public key for the server. This functionality is basically free since the nonce is a required part of the Roughtime protocol anyway.
Another feature of Roughtime is the use of a Merkle tree to reduce CPU usage on the server. Ed25519, and most public key signature algorithms, are fairly heavy weight operations. Using the Merkle tree a server can hash multiple requests in a tree and then sign only the top of the tree. This allows a server to sign responses to multiple requests with one Ed25519 operation. This adds a bit of complexity to both the server and client but reduces the CPU usage on the server immensely.
One thing to note is that the Roughtime principles could be applied to other protocols. Roughtime is not limited to UDP over IPv4 or IPv6. It should work with just about any datagram oriented transport. Nothing in the protocol is set in stone yet. For example, different draft versions of Roughtime have used different encodings for the time stamps. Some have used UTC encoded as Posix time_t (which can't represent leap seconds); other draft versions have used MJD + the number of seconds since midnight (which can represent leap seconds). Roughtime originally was only meant to have a resolution of 10 seconds, good enough to check the validity of a TLS certificate. Now it has microsecond resolution. Additionally, the current Roughtime draft has support for multiple timescales.
Relation to authenticated NTP
Authenticated NTP has been around for a long time. A client and server have a shared secret with a 16 bit key ID. The client adds its key ID to the request and the server appends a signature of the NTP payload made using the shared secret to its response. Since it is a shared secret, if multiple clients share the same secret, any of the clients can impersonate the server.
Each client could have a unique shared secret, but since the key ID is only 16 bits this won't scale to a large number of clients. Even if the key ID was increased to say 64 bits, keeping track of a unique shared secret for each client would require insane amounts of storage on the server. Authenticated NTP does not solve key distribution either. This means that, in practice, authenticated NTP is only really useful for a small number of clients.
An additional issue with authenticated NTP is that it does not have good replay protection. It is possible to reuse the origin timestamp as a nonce field, but 64 bits is a bit on the short side.
Relation to NTS
NTS solves the scalability problem with authenticated NTP. NTS extends NTP with a "key establishment" protocol, NTS-KE, which is run before plain old NTP takes over. NTS-KE uses TLS 1.3 (RFC8446) and "Keying Material Exporters" (RFC5705) to basically get a NTP server and client to agree on a shared secret. After that NTS works similarly to how authenticated NTP works. Instead of just appending the raw signature to the response, a NTS capable NTP server adds an extension field with the signature made using the shared secret.
NTS has some additional tricks up its sleeve to allow the NTP server to be stateless. The shared secret is actually shipped back and forth using a "cookie" placed in another extension field. NTS also adds an extension field with a "unique identifier", just another name for a "nonce". Note that even though NTS signs the "unique identifier" / "nonce", there is no way for anyone else but the client to verify that signature. The shared secrets are only shared between the NTP server and client and have no relation to the TLS certificates that an external party can look at.'
Conceptually, NTS is just the key-establishment-over-TLS step followed by authenticated NTP using the shared secrets established by that first step. It also provides replay protection.
The first Roughtime drafts predate NTS being accepted as RFC8915. Roughtime is a completely new protocol which does not try to be compatible with NTP. Since NTS solves the "scalable and secure" part of time transfer, it partly makes Roughtime obsolete.
There still remains a bootstrap problem with NTS: to be able to use TLS properly one needs rough time which is accurate enough to be able to validate the TLS certificate used by the NTS server. But to get secure and accurate enough time one needs a time protocol such as NTS. But where should I start if I have no idea what time it is? Roughtime solves this problem. It turns the bootstrapping problem into a key distribution problem: how do we get the list of Roughtime server public keys onto a client.
Additionally, NTS may be a bit too heavyweight for resource constrained systems such as IoT devices. NTS requires TLS 1.3 and some TLS extensions that are not present in many embedded TLS implementations, Some resource constrained devices may not even be able to run TLS at all. Roughtime only depends on Ed25519 (Curve25519 + SHA512 + Merkle Tree) and requires less resources.
Additional issues with NTP
Plain old NTP, and thus authenticated NTP and NTS, has some issues with how leap seconds are handled. Part of this is a problem with how Posix systems handle leap seconds. Some NTP server operators have decided to work around this using "leap smearing", i.e. the leap second is smeared out over a whole day which gives a smooth transition of the leap second without a sharp jump of one second. This is basically anathema to anyone who cares about sub second accuracy for a time protocol, but does solve a real problem for those operators. A new protocol such as Roughtime could handle leap seconds "the right way" from the beginning.
Resources
Roughtime Draft
https://datatracker.ietf.org/doc/html/draft-ietf-ntp-roughtime
Working client implementation of draft version 4, 5 and 7
https://vadarklockan.readthedocs.io
Roughtime servers
Netnod: sth1.roughtime.netnod.se, sth2.roughtime.netnod.se (v7)
Marcus Dansarie: roughtime.se (v7)
Mailing list: "proto-roughtime"
Blog posts with background about Roughtime
https://blog.cloudflare.com/roughtime/
My questions to you
Application Requirements
Can you describe what you would like to use roughtime for?
What accuracy do you need for your application?
10 seconds or more, for example to be able to validate TLS certificates
1 second accuracy (good enough for a wall clock)
100 milliseconds
10 milliseconds
1 millisecond
Even better than that? Sub millisecond accuracy?
Do you care about leap seconds?
Do you use leap smearing today?
What time scales do you need?
UTC
posix time_t / NTP time - which can't represent leap seconds
MJD + seconds since midnight - which can represent leap seconds
TAI - international atomic time (currently at a 37 second offset from UTC)
UT1 - basically solar time
How do you see yourself using Roughtime? Roughtime can be used in multiple ways.
Do you want to use public roughtime servers?
Do you want to use a local roughtime server?
Do you expect to just use one server that you trust fully?
Do you expect to use the Roughtime ecosystem where you ask multiple servers and need a consensus where a number of servers all agree on what time it is?
Would you use the "nonce" in roughtime to sign documents with a timestamp?
I.e. use roughtime as a lightweight TSA
System Requirements
What transports are you interested in?
Right now roughtime is defined for UDP over IPv4 or IPv6, but the same principles and packet format could be used for just about any datagram transport.
Do you have any limits on packet size?
Is this an absolute limit or can larger packets be fragmented?
Roughtime uses about 1kByte packet size
What CPU and clock speeds are you using?
If you don't want to name the specific CPU, what architecture and clock speeds (e.g. ARM Cortex M0 48MHz)
How much flash memory does your device have?
How much is available for a time protocol?
On an ESP32 Roughtime itself needs about 8kBytes of code memory, plus an additional 12kBytes for Curve25519 + SHA512. Plus about 50 bytes for each server (hostname + 32 bytes of public key).
How much RAM memory does our device have?
How much is available for a time protocol?
Roughtime needs about 2 kBytes for packet buffers and temporary storage.
Can your device already support TLS?
Does it support TLS 1.3 (RFC8446)?
Does it support Keying Material Exporters for TLS (RFC 5705)?
Does your application already use TLS?
Or CBOR/COSE?
If not, would it be acceptable to add a dependency on TLS?
MbedTLS has a code size of about 70kBytes on ARM
(https://github.com/Mbed-TLS/mbedtls/issues/7895)
Does your application already support Ed25519?
If not, would it be acceptable to add a dependency on Ed25519?
About 12kBytes of code memory on a ESP32 for Curve25519 + SHA512
Security considerations
How long does Roughtime have to work and be secure?
What is your time horizon for how long a device can sit on a shelf?
Without updating the list of roughtime servers?
Without firmware updates?
Do you think that hardcoding the public keys of roughtime servers is acceptable?
If not, can you suggest a better way to handle key distribution for a bootstrapping protocol?
Do you think Ed25519 is an appropriate public key cryptography algorithm?
If not, can you suggest a better one?
Note that Ed25519 would probably not survive quantum computers with enough bits. Does roughtime need to use post-quantum public key cryptography?
See FIPS 204, Module-Lattice-Based Digital Signature Standard,
and FIPS 205, Stateless Hash-Based Digital Signature Standard
Do we need the Merkle tree?
Any other comments?
Regards,
Christer
it's been fairly quiet here for a while. I'd like to try to get the Roughtime development started again. I've composed this much too long mail with my thoughts and questions about roughtime. I'm posting it here and will also post it to some other mailing lists that I think might be interested.
I am reaching out to groups for whom Roughtime could be relevant in order to get a deeper understanding of the various requirements and possible use-cases. Please take a look at the questionnaire at the end of the mail and let me know any answers you may have. The more details we can get from the technical community at this stage, the more likely it is we can develop the protocol in the right direction, I have included a lot of details on Roughtime for those who might not be familiar with the work done so far and the background here.
Background
Time is important for many applications and to be able to set the internal clock of a device in a secure way is also important. There already exist some protocols for secure time transfer such as authenticated NTP and NTS. Authenticated NTP using shared secrets does not scale to a large number of clients and is thus rather unsuitable for IoT. NTS has a bootstrapping problem (more about that later) and in my opinion, might be a bit too heavyweight for resource constrained devices such as IoT devices.
Roughtime started out as a secure protocol for time transfer which solves the bootstrapping problem. The Roughtime protocol has evolved over time and is now a fairly generic protocol for secure time transfer. I believe that Roughtime, or at least something like it, could be very useful, especially for resource constrained devices.
Roughtime has been around for a few years as an IETF draft, but unfortunately, the development has stalled a bit. I've been talking to people at IETF and RIPE meetings and my impression is that it's not only me that is interested in Roughtime. Netnod recently received some funding from the RIPE Community Fund to kickstart the development of Roughtime. I'd like to start by collecting feedback from all of you.
This mail is fairly long. I'll start out by trying to explain what I think are the key principles and ideas behind Roughtime and how it relates to other secure time transfer protocols such as authenticated NTP and NTS. At the end I have a list of questions that I'd like to get feedback on.
My goal is to figure out what Roughtime actually should do to be useful and to ensure that it provides what you need, but does not contain unnecessary features that you don't need. Then we can update the Roughtime draft based on that feedback and, finally, submit it to the RFC editors.
What is Roughtime?
Roughtime principles
Roughtime is a time transfer protocol which signs responses from the server using a private key. A client can then use the server's public key to verify the response. Currently, the public key algorithm used is Ed25519, but the protocol does allow for other algorithms in the future.
One of the basic principles behind how Roughtime solves the bootstrap problem is that it hard codes these public keys for Roughtime servers. It is expected that this list can be updated, either by downloading a new list when the system has finished bootstrapping, or by keeping the list as a part of the firmware. That means a new list is installed when the firmware is updated.
Another aspect of Roughtime is that a client is expected to keep a fairly large list of Roughtime servers. When a device boots it queries random servers from this list until a number of servers all agree on what time it is. If a few servers on the list have stopped working or send t bad time (regardless of whether it's due to malfunction or attack), this should not be a big issue if one requires enough good servers to agree on time.
This last point is not a requirement though, Roughtime could be used with just a few, or even just a single server that one trusts completely. Basically, the idea here would be similar to the way one uses authenticated NTP, but using public keys instead of shared secrets. This could be a company that wants to run its own Roughtime servers and only use those. Another example is if Roughtime is used to distribute time within a system, for example with multiple devices connected to a local network that has to keep consistent time with one local server.
Roughtime has protection against replay attacks. A Roughtime client is expected to pass a "nonce", a 32 byte random and unique block of data, in each request. The Roughtime server will sign this nonce together with the timestamp in its response. If the nonce in the response matches what the client sent out the client knows that it is actually a response to its request and not to an earlier one.
A client is allowed to pass any data as the nonce though. For example the nonce could be a 32 byte cryptographic hash of a document. The Roughtime server can thus be used as a lightweight time stamping authority (TSA) giving a cryptographic proof that the client was in possession of a specific document at a specific point in time. This proof can be verified using the public key for the server. This functionality is basically free since the nonce is a required part of the Roughtime protocol anyway.
Another feature of Roughtime is the use of a Merkle tree to reduce CPU usage on the server. Ed25519, and most public key signature algorithms, are fairly heavy weight operations. Using the Merkle tree a server can hash multiple requests in a tree and then sign only the top of the tree. This allows a server to sign responses to multiple requests with one Ed25519 operation. This adds a bit of complexity to both the server and client but reduces the CPU usage on the server immensely.
One thing to note is that the Roughtime principles could be applied to other protocols. Roughtime is not limited to UDP over IPv4 or IPv6. It should work with just about any datagram oriented transport. Nothing in the protocol is set in stone yet. For example, different draft versions of Roughtime have used different encodings for the time stamps. Some have used UTC encoded as Posix time_t (which can't represent leap seconds); other draft versions have used MJD + the number of seconds since midnight (which can represent leap seconds). Roughtime originally was only meant to have a resolution of 10 seconds, good enough to check the validity of a TLS certificate. Now it has microsecond resolution. Additionally, the current Roughtime draft has support for multiple timescales.
Relation to authenticated NTP
Authenticated NTP has been around for a long time. A client and server have a shared secret with a 16 bit key ID. The client adds its key ID to the request and the server appends a signature of the NTP payload made using the shared secret to its response. Since it is a shared secret, if multiple clients share the same secret, any of the clients can impersonate the server.
Each client could have a unique shared secret, but since the key ID is only 16 bits this won't scale to a large number of clients. Even if the key ID was increased to say 64 bits, keeping track of a unique shared secret for each client would require insane amounts of storage on the server. Authenticated NTP does not solve key distribution either. This means that, in practice, authenticated NTP is only really useful for a small number of clients.
An additional issue with authenticated NTP is that it does not have good replay protection. It is possible to reuse the origin timestamp as a nonce field, but 64 bits is a bit on the short side.
Relation to NTS
NTS solves the scalability problem with authenticated NTP. NTS extends NTP with a "key establishment" protocol, NTS-KE, which is run before plain old NTP takes over. NTS-KE uses TLS 1.3 (RFC8446) and "Keying Material Exporters" (RFC5705) to basically get a NTP server and client to agree on a shared secret. After that NTS works similarly to how authenticated NTP works. Instead of just appending the raw signature to the response, a NTS capable NTP server adds an extension field with the signature made using the shared secret.
NTS has some additional tricks up its sleeve to allow the NTP server to be stateless. The shared secret is actually shipped back and forth using a "cookie" placed in another extension field. NTS also adds an extension field with a "unique identifier", just another name for a "nonce". Note that even though NTS signs the "unique identifier" / "nonce", there is no way for anyone else but the client to verify that signature. The shared secrets are only shared between the NTP server and client and have no relation to the TLS certificates that an external party can look at.'
Conceptually, NTS is just the key-establishment-over-TLS step followed by authenticated NTP using the shared secrets established by that first step. It also provides replay protection.
The first Roughtime drafts predate NTS being accepted as RFC8915. Roughtime is a completely new protocol which does not try to be compatible with NTP. Since NTS solves the "scalable and secure" part of time transfer, it partly makes Roughtime obsolete.
There still remains a bootstrap problem with NTS: to be able to use TLS properly one needs rough time which is accurate enough to be able to validate the TLS certificate used by the NTS server. But to get secure and accurate enough time one needs a time protocol such as NTS. But where should I start if I have no idea what time it is? Roughtime solves this problem. It turns the bootstrapping problem into a key distribution problem: how do we get the list of Roughtime server public keys onto a client.
Additionally, NTS may be a bit too heavyweight for resource constrained systems such as IoT devices. NTS requires TLS 1.3 and some TLS extensions that are not present in many embedded TLS implementations, Some resource constrained devices may not even be able to run TLS at all. Roughtime only depends on Ed25519 (Curve25519 + SHA512 + Merkle Tree) and requires less resources.
Additional issues with NTP
Plain old NTP, and thus authenticated NTP and NTS, has some issues with how leap seconds are handled. Part of this is a problem with how Posix systems handle leap seconds. Some NTP server operators have decided to work around this using "leap smearing", i.e. the leap second is smeared out over a whole day which gives a smooth transition of the leap second without a sharp jump of one second. This is basically anathema to anyone who cares about sub second accuracy for a time protocol, but does solve a real problem for those operators. A new protocol such as Roughtime could handle leap seconds "the right way" from the beginning.
Resources
Roughtime Draft
https://datatracker.ietf.org/doc/html/draft-ietf-ntp-roughtime
Working client implementation of draft version 4, 5 and 7
https://vadarklockan.readthedocs.io
Roughtime servers
Netnod: sth1.roughtime.netnod.se, sth2.roughtime.netnod.se (v7)
Marcus Dansarie: roughtime.se (v7)
Mailing list: "proto-roughtime"
Blog posts with background about Roughtime
https://blog.cloudflare.com/roughtime/
My questions to you
Application Requirements
Can you describe what you would like to use roughtime for?
What accuracy do you need for your application?
10 seconds or more, for example to be able to validate TLS certificates
1 second accuracy (good enough for a wall clock)
100 milliseconds
10 milliseconds
1 millisecond
Even better than that? Sub millisecond accuracy?
Do you care about leap seconds?
Do you use leap smearing today?
What time scales do you need?
UTC
posix time_t / NTP time - which can't represent leap seconds
MJD + seconds since midnight - which can represent leap seconds
TAI - international atomic time (currently at a 37 second offset from UTC)
UT1 - basically solar time
How do you see yourself using Roughtime? Roughtime can be used in multiple ways.
Do you want to use public roughtime servers?
Do you want to use a local roughtime server?
Do you expect to just use one server that you trust fully?
Do you expect to use the Roughtime ecosystem where you ask multiple servers and need a consensus where a number of servers all agree on what time it is?
Would you use the "nonce" in roughtime to sign documents with a timestamp?
I.e. use roughtime as a lightweight TSA
System Requirements
What transports are you interested in?
Right now roughtime is defined for UDP over IPv4 or IPv6, but the same principles and packet format could be used for just about any datagram transport.
Do you have any limits on packet size?
Is this an absolute limit or can larger packets be fragmented?
Roughtime uses about 1kByte packet size
What CPU and clock speeds are you using?
If you don't want to name the specific CPU, what architecture and clock speeds (e.g. ARM Cortex M0 48MHz)
How much flash memory does your device have?
How much is available for a time protocol?
On an ESP32 Roughtime itself needs about 8kBytes of code memory, plus an additional 12kBytes for Curve25519 + SHA512. Plus about 50 bytes for each server (hostname + 32 bytes of public key).
How much RAM memory does our device have?
How much is available for a time protocol?
Roughtime needs about 2 kBytes for packet buffers and temporary storage.
Can your device already support TLS?
Does it support TLS 1.3 (RFC8446)?
Does it support Keying Material Exporters for TLS (RFC 5705)?
Does your application already use TLS?
Or CBOR/COSE?
If not, would it be acceptable to add a dependency on TLS?
MbedTLS has a code size of about 70kBytes on ARM
(https://github.com/Mbed-TLS/mbedtls/issues/7895)
Does your application already support Ed25519?
If not, would it be acceptable to add a dependency on Ed25519?
About 12kBytes of code memory on a ESP32 for Curve25519 + SHA512
Security considerations
How long does Roughtime have to work and be secure?
What is your time horizon for how long a device can sit on a shelf?
Without updating the list of roughtime servers?
Without firmware updates?
Do you think that hardcoding the public keys of roughtime servers is acceptable?
If not, can you suggest a better way to handle key distribution for a bootstrapping protocol?
Do you think Ed25519 is an appropriate public key cryptography algorithm?
If not, can you suggest a better one?
Note that Ed25519 would probably not survive quantum computers with enough bits. Does roughtime need to use post-quantum public key cryptography?
See FIPS 204, Module-Lattice-Based Digital Signature Standard,
and FIPS 205, Stateless Hash-Based Digital Signature Standard
Do we need the Merkle tree?
Any other comments?
The questions above are rather coloured by my personal background with embedded Linux devices. Please let me know if I have missed anything you consider significant. I would appreciate it if you could respond as soon as convenient. My goal is to have the requirements for Roughtime in place before the IETF 119 meeting in March 2024.
I think the best place to discuss Roughtime is here on the proto-roughtime mailing list, but think there is a better forum I'm very much open to suggstions.
Regards,
Christer
Reply all
Reply to author
Forward
0 new messages