There are several cryptographic uses for a clock. Key management functions are often linked to deadlines. The current time can provide both a unique value and a complete ordering of events. We will discuss each of these uses in more detail.

16.1.1 Expiration

In many situations, we want to limit the validity period of a document. In the real world, we often see limited validity periods too. Checks, open airline tickets, vouchers, coupons, and even copyrights all have limited validity periods. The standard way to limit the validity period of a digital document is to include the expiration time in the document itself. But to check whether a document has expired, we need to know the current time. Hence, the need for a clock.

16.1.2 Unique Value

Another useful function of a clock—if its resolution is high enough—is to provide a unique value for a single machine. We've been using nonces in several places. The important property of a nonce is that any single value is never used twice, at least within some defined scope. Sometimes the scope is limited, such as the nonce we use in the secure channel, and the nonce can be generated using a counter. In other situations, the nonce has to be unique across reboots of the computer. There are two generic ways of generating nonce values. The first is to use the current time of the clock with some mechanism to ensure you never use the same time code twice. The second is to use a PRNG, which we discussed in some detail in Chapter 9. The disadvantage of using a random nonce is that it needs to be rather large. To achieve a security level of 128 bits, we would need to use a 256-bit random nonce. Not all primitives support such a large nonce. Furthermore, a PRNG can be very hard to implement on certain platforms. A reliable clock is an attractive alternative way to generate nonces.

16.1.3 Monotonicity

One of the useful properties of time is that it always keeps going forward. It never stops or reverses. There are cryptographic protocols that use this property. Including the time in a cryptographic protocol prevents an attacker from trying to pass off old messages as ones that belong to the current protocol. After all, the time encoded in those messages is not within the time-span of the current protocol.

Another really important application of the clock is auditing and logging. In any kind of transaction system, it is very important to keep a log of what happened. If there is ever a dispute, the audit logs provide the necessary data to trace the exact sequence of events. Including the time in each logging event is important; without a time stamp, it is very hard to know which events belong to the same transaction, and in which order the events occurred. As well-synchronized clocks do not deviate significantly from each other, the time stamps allow events from different logs on different machines to be correlated.

16.1.4 Real-Time Transactions

Our next example comes from Niels's work on electronic payment systems. To support real-time payments, the bank needs to run a real-time financial transaction system. To allow an audit to be performed, there should be a clear sequence of transactions. Given two transactions A and B, it is important to know which of the two was performed first, because the result of one of them could depend on whether the other one has been performed yet or not. The simplest way to record this sequence is to give a time stamp to each transaction. This only works if you have a reliable clock.

An unreliable clock might give the wrong time. There is little harm done if the clock accidentally moves backward: it is easy to check that the current time is greater than the time stamp of the last transaction performed. There is a problem, however, if the clock moves forward. Suppose half an hour's worth of transactions were done with the clock set in 2020. You can't just change the time stamps of those transactions; it is not acceptable to modify financial records by hand. You can't perform any new transactions with a time stamp before 2020 because that would upset the order of the transactions, which is determined by the time stamp. There are solutions to this problem, but a reliable clock is certainly preferable.

Most desktop computers contain a real-time clock chip and a small battery. This is really a small digital watch built into your machine. This is how your computer knows what time it is when you start it up in the morning. Why not simply use this clock time?

The real-time clock chip is adequate for normal use, but in a security system we have to impose higher standards. As part of the security system, the clock should give the correct time even if an enemy tries to manipulate the clock. A second reason is the consequences of a failed clock. For normal uses, a clock that shows the wrong time is irritating but not dangerous. If the clock is part of the security system, clock failures can result in much greater damage.

The real-time clocks in typical hardware are not as reliable and secure as we need. We have personally experienced several real-time clock chip failures in the last decade. Moreover, those failures were spontaneous, without a malicious attacker trying to corrupt the clock. Most failures are simple. On an old machine, the battery runs low and the clock stops or resets to 1980. Or one day you start the machine and the clock has been set to some date in 2028. Sometimes a clock just gradually drifts faster or slower than the real time.

Apart from accidental errors in real-time clocks, we have to consider active attacks. Someone might try to manipulate the clock in some way. Depending on the details of the computer, changing the clock time can be easy or hard. On some systems, you need special administrator access to change the clock; others have clocks that can be changed by anyone.

There are several types of attack that can be mounted against a system with a clock.

16.3.1 Setting the Clock Back

Suppose the attacker can set the clock to some arbitrary time in the past. This might allow all kinds of mischief. The machine mistakenly believes it lives in the past. Maybe an attacker once had access to some data because he was a temporary employee, but that access has now expired. With the wrong time on the clock, a computer might now allow this ex-employee access to the sensitive data. This problem has the potential of occurring every time some access is revoked from a user. Setting the clock back might restore his access, depending on how the rest of the system was designed.

Another interesting avenue of attack is automated tasks. Suppose an HR computer makes salary payments automatically at the end of the month, using direct deposit. Automated tasks like this are initiated by a program that checks the time and has a list of tasks to perform. Repeatedly setting the clock back can trigger the tasks repeatedly. If the task is set to start at midnight, the attacker sets the clock to 23:55 (11:55 pm), and waits for the task to be started. After the task finishes, the attacker sets the clock back again. He can repeat this until the bank balance of the company is exhausted.

Another problem occurs in financial systems. It is important to get the time of a transaction right because interest computations give different results depending on when a transaction was performed. If you carry a large balance on your credit card, it would be very advantageous to convince your bank's computer that the online payment you just made actually happened six months ago, and avoid paying six months of interest.

16.3.2 Stopping the Clock

Every designer lives with the instinctive understanding that time does not stand still. It is an unspoken assumption, too obvious to even document. The systems they design rely on time behaving normally. But if the clock is stopped, time appears to stand still. Things might not get done. And many systems behave in unpredictable ways.

The simple problems are things like getting the wrong time on audit logs and reports. The exact time of a transaction can have large financial consequences, and sending out formal paperwork with the wrong date and time on it can lead to serious complications.

Other problems might occur with real-time displays. Maybe the GUI programmer uses a simple system to display the current situation at the real-time broker. Every ten seconds, he refreshes the display with the latest data. But not all reports of financial transactions arrive with the same speed, due to various delays. Just reporting the latest data that was received is going to give an inconsistent view of the financial situation. Maybe one part of a transaction has already been reported, but the other half has not. The money could show up on the bank balance before the shares move from the stock holdings. Accountants do not like to get reports where the numbers do not add up.

So the programmer does something clever. Each report of a financial transaction is time-stamped and stored in a local database. To display a consistent report, he takes a particular point in time and reports the financial situation at that point in time. For example, if the slowest system has a five-second delay in reporting, he displays the financial situation of seven seconds ago. It increases the display delay a bit, but it guarantees a consistent report. That is, until the clock is stopped. Suddenly, the display reports the same situation over and over again: the situation of seven seconds ago relative to the (failed) clock. Oops!

16.3.3 Setting the Clock Forward

Setting the clock forward makes the computer think it lives in the future. This leads to simple denial-of-service attacks. With the clock set four years in the future, all credit card transactions are suddenly refused because all the cards have expired. You cannot book online airline tickets either, because there is no airline schedule out yet for those dates.

Substantial bidding at eBay auctions happens in the last seconds. If you can move eBay's clock forward just a little bit, you cut out many of the other bidders and can obtain the item at a cheaper price.

A friend of ours had a problem of this nature with his billing system. Due to a software error, the clock jumped ahead by about 30 years. The billing system started to bill all his customers for 30 years of unpaid bills. In this case, it didn't result in a direct financial loss, but it could have been different if he had been using automatic debits from bank accounts or credit cards. It certainly wasn't good customer relations.

There are also direct security risks involved with clocks set to a future time. There are many situations in which certain data is to be kept secret until a specific time, and made public after that time. In an automated system, setting the clock forward provides access to the data. If this is a profit warning for a publicly traded company, quite a bit of profit can be made from accessing this data prematurely.

We don't have a simple solution to the clock problem. We can suggest some ideas and techniques, but the details depend too much on the exact working environment and the risk analysis for us to be able to give universal answers. Our goal here is therefore multifold. We wish to increase understanding, encourage minimal reliance on a clock, identify key issues to consider, and provide an example for how to think about building a reliable clock.

Most computers have, or can implement, a counter of some sort that starts when the computer is booted. This might be a count of the number of CPU clock cycles, a refresh counter, or something similar. This counter can be used to keep track of the time since the last reboot. It is not a clock, as it provides no information about what the actual time is, but it can be used to measure elapsed time between events as long as both events happened since the last reboot.

The main use for this type of counter, at least in relation to our clock problem, is to check for accidental errors in the real-time clock. If the real-time clock doesn't run properly, it will show discrepancies with the clock counter. This is simple to test for, and provides some warning for certain error modes of the clock chip. Note that the correspondence between clock time and counter value has to be modified if the clock time is changed by an authorized user.

This brings us to a serious problem that you find on some hardware platforms. We're talking here about small embedded computers—something like a door lock or a remote smart card reader. These typically consist of a small CPU, a small amount of RAM, nonvolatile memory (e.g., flash) to store the program, some communication channels, and further task-specific hardware.

You will notice that a real-time clock is often not included. Adding a real-time clock requires an extra chip, an oscillator crystal, and most importantly, a battery. Apart from the extra cost, adding a battery complicates the device. You now have to worry about the battery running out. Batteries can be sensitive to temperature fluctuations, and the toxic chemicals in some batteries can even lead to problems with shipping the hardware. For all of these reasons, many small computers do not have a real-time clock.

Every time such a small computer is booted, it starts in exactly the same state. It reads the same program from the same nonvolatile memory, initializes the hardware, and starts operations. As this is a book about cryptography, we will assume that some kind of cryptographic protocol is used in the communication with other pieces of the system. But here is the problem: without a clock or hardware random number generator, the embedded system will always repeat the exact same behavior. Suppose the attacker waits until the gate computer needs to open the gate because a truck needs to pass through. She reboots the gate computer just before the gate needs to open (e.g., by interrupting the power supply momentarily). After some initialization procedures, the central system will command the gate computer to open the gate via the communication channel. The next day, the attacker reboots the gate computer again, and sends exactly the same messages as were sent the first time. As the gate computer starts in the same state and sees the same inputs, it behaves the same and opens the gate. This is bad. Note that it doesn't matter if the gate computer uses a time synchronization protocol. The protocol messages can be replayed from yesterday, and the gate computer has no way of detecting this. The same-state problem is not solved by any protocol.

A real-time clock chip solves this problem. The small embedded computer can encrypt the current time with a fixed secret key to generate highly random data. This data can in turn be used as a nonce in a cryptographic protocol. As the real-time clock never repeats its state, the embedded computer can avoid falling into the same-state trap.

A hardware random number generator has the same effect. It allows the embedded computer to behave differently each time it is rebooted.

But if you don't have a real-time clock or a random number generator, you have a big problem. Sometimes you can fudge a bit and try to extract randomness from the clock skew between the local clock oscillator and the network timing or another oscillator, but it is very hard to extract enough entropy from this within a short time. Taking 10 minutes to reboot an embedded computer is simply unacceptable.

We've seen the same-state problem come up again and again. The upshot is that the hardware has to change before you can do useful cryptography on such small computers. This is hard to sell to managers, especially since the hardware is often already in the field and they don't want to hear that something cannot be done. But there is no magic security sauce that you can pour over an existing insecure system to make it secure. If you don't design the security into the system from the very start, you almost never get good security.

There is one more possible solution, though it rarely works in practice. Sometimes you can keep a reboot counter in the nonvolatile memory. Each time the CPU reboots, it increments a counter in nonvolatile memory. This solution is fraught with problems. Some nonvolatile memories can only be updated a few thousand times, which makes the machine wear out if you keep updating the counter. Some nonvolatile technologies require an additional power voltage to be programmable, which is often not available in the field. In some designs, you can only set bits in nonvolatile memory, or wipe all of the nonvolatile memory. The latter option is not viable, as you'd lose the main program of the machine. Even if all these problems are overcome, it is very difficult to modify nonvolatile memory in such a way that the counter always reliably increases even if the power supply to the machine can be interrupted at arbitrary points in time. This nonvolatile counter option is only viable in a minority of the cases we've seen. When it is feasible, such a counter could be used as part of a PRNG. For example, the counter could be used with CTR mode and an AES key to generate a stream of pseudorandom bits.

While we're discussing clocks, we have a few short comments on which time base to choose. Stay away from local time. Local time is the time we use on our watches and other clocks. The problem is, local time changes with daylight saving time and time zone. These changes pose problems: some time values are repeated each year when clocks are set back an hour in the fall, which means that the time is no longer unique or monotonic. Some time values are impossible when clocks are set forward an hour in the spring. Furthermore, the exact date on which daylight saving time starts and stops is different in different countries. In some countries, the rules change every few years, and you don't want to have to update your software for that. And people who travel with laptops might change the time on their laptops to the local time, which just makes these problems worse.

The obvious choice is to use UTC time. This is an international time standard based on atomic clocks, and is widely used throughout the world. Any single computer can keep track of the offset of local time with regard to UTC and use this knowledge in interactions with the user.

There is one problem with UTC: the leap seconds. To keep UTC synchronized with the Earth's rotation, there is a leap second once every few years or so. So far, all leap seconds have been extra seconds; there is a particular minute that gets 61 seconds. It is also theoretically possible to have a missing second. It all depends on the rotation of the Earth. The problem for computers is that the leap seconds are unpredictable. Ignoring leap seconds leads to inaccuracies in measuring time intervals across a leap second. This is not really a cryptographic problem, but if you want to make a good clock, you might as well do it right. All computer software always assumes that each minute has 60 seconds. If you synchronize directly to a real UTC clock, the insertion of a leap second can lead to problems. Most likely this results in your internal clock repeating itself for one second. It is a minor problem, but again, it destroys the uniqueness and monotonicity of time values.

For most applications, the exact synchronization of the clock is less important than the monotonicity and uniqueness of the time stamps. As long as you make sure the clock never jumps backwards at a leap second, it doesn't matter how you solve this problem.

Unfortunately, we have no ideal solution for you. Creating a reliable clock is very tricky, especially in a cryptographic setting where you assume there are malicious attackers. The best solution depends on your local situation. Our recommendations, therefore, are to be aware there are potential security issues associated with the use of a clock, minimize reliance on the clock whenever possible, and be cautious. And again, the most important thing is generally the monotonicity and uniqueness of the time stamps.

Exercise 16.1 Some computers use NTP at boot, or at regular intervals. Turn off NTP for one week on your computer. Write a program that at regular intervals (at least once every two hours) records both the true time and the time reported by your computer. Let t0 be the initial true time at the start of your experiment. For each time measurement pair, plot the true time minus t0 on the horizontal axis of a graph and plot your computer's time minus true time on the vertical axis. How different is your computer's clock from true time after one week? Does your graph tell you anything else?

Exercise 16.2 Repeat exercise 16.1, but this time for a collection of five different computers.

Exercise 16.3 Find a new product or system that uses (or should use) a clock. This might be the same product or system you analyzed for Exercise 1.8. Conduct a security review of that product or system as described in Section 1.12, this time focusing on the security and privacy issues surrounding the clock.