Clock drift
Encyclopedia
Clock drift refers to several related phenomena where a clock
does not run at the exact right speed compared to another clock. That is, after some time the clock "drifts apart" from the other clock. This phenomenon is also used for instance in computer
s to build random number generators. On the negative side, clock drift can be exploited by timing attack
s.
usually drift compared to the actual time. This is why it is necessary to reset them occasionally. Clocks often drift differently depending on their quality, the exact power they get from the battery, the surrounding temperature and other environmental variables. Thus the same clock can have different clock drift rates at different occasions.
Mechanical watches drift much more than quartz ones, but they are designed to drift ahead rather than behind, so that the watch gains time, making it easier to set the time to the second with the hack (stop mechanism) function.
More advanced clocks and old mechanical clocks often have some kind of speed trimmer where one can adjust the speed of the clock and thus reduce the clock drift. For instance, in pendulum clock
s the clock drift can be manipulated by slightly changing the length of the pendulum
. The formula of Fast drift is dc/dt>1.
s are very precise and have nearly no clock drift. The rotation of the Earth itself actually has much more clock drift (less accuracy) than modern atomic clocks. Thus to keep the Coordinated Universal Time
(UTC) in line with the Earth's rotation, a leap second
is added to some years.
predicted, relativistic effects can also cause clock drift due to time dilation
. This is because there is no fixed universal time, time being relative to the observer. Special relativity
describes how two clocks held by people in different inertial frames
(i.e. moving with respect to each other but not accelerating or decelerating) will each appear to tick more slowly to the other person.
In addition to this, general relativity
gives us gravitational time dilation
. Briefly, a clock in a higher gravitational field (e.g. closer to a planet) will appear to tick more slowly. People holding these clocks would agree on which clock appeared to be going faster.
Note that it is time itself rather than the function of the clock which is affected. Both effects have been experimentally observed.
Time dilation is of practical importance. For instance, the clocks in GPS satellites
experience this effect due to the reduced gravity they experience (making their clocks appear to run more quickly than those on Earth) and must therefore incorporate relativistically corrected calculations when reporting locations to users. If general relativity were not accounted for, a navigational fix based on the GPS satellites would be false after only 2 minutes, and errors in global positions would continue to accumulate at a rate of about 10 kilometers each day.
s often need high quality random number
s, especially for cryptography
. There are several similar ways clock drift can be used to build random number generators (RNGs).
One way to build a hardware random number generator is to use two independent clock crystals
, one that for instance ticks 100 times per second and one that ticks 1 million times per second. On average the faster crystal will then tick 10,000 times for each time the slower one ticks. But since clock crystals are not precise, the exact number of ticks will vary. That variation can be used to create random bits. For instance, if the number of fast ticks is even, a 0 is chosen, and if the number of ticks is odd, a 1 is chosen. Thus such a 100/1000000 RNG circuit can produce 100 somewhat random bits per second.
Typically such a system is biased—it might for instance produce more zeros than ones—and so hundreds of somewhat random bits are "whitened"
to produce a few unbiased bits.
There is also a similar way to build a kind of "software random number generator". This involves comparing the timer tick of the operating system (the tick that usually is 100–1000 times per second) and the speed of the CPU
. If the OS timer and the CPU run on two independent clock crystals the situation is ideal and more or less the same as the previous example. But even if they both use the same clock crystal the process
/program that does the clock drift measurement is "disturbed" by many more or less unpredictable events in the CPU such as interrupt
s and other processes and programs that runs at the same time. Thus the measurement will still produce fairly good random numbers. Some argue they are then not true random numbers but they seem to be good enough for most needs.
Note that most hardware random number generators such as the ones described above are fairly slow. Therefore most programs only use them to create a good seed that they then feed to a pseudorandom number generator
or a cryptographically secure pseudorandom number generator
to produce many random numbers fast.
was published that exploited clock skew based on CPU heating. The attacker causes heavy CPU load on a pseudonymous
server, causing CPU heating. CPU heating is correlated with clock skew, which can be detected by observing timestamps (under the server's real identity).
Clock
A clock is an instrument used to indicate, keep, and co-ordinate time. The word clock is derived ultimately from the Celtic words clagan and clocca meaning "bell". A silent instrument missing such a mechanism has traditionally been known as a timepiece...
does not run at the exact right speed compared to another clock. That is, after some time the clock "drifts apart" from the other clock. This phenomenon is also used for instance in computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s to build random number generators. On the negative side, clock drift can be exploited by timing attack
Timing attack
In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms...
s.
Clock drift in normal clocks
Normal clocks such as clocks at home and wristwatchesWatch
A watch is a small timepiece, typically worn either on the wrist or attached on a chain and carried in a pocket, with wristwatches being the most common type of watch used today. They evolved in the 17th century from spring powered clocks, which appeared in the 15th century. The first watches were...
usually drift compared to the actual time. This is why it is necessary to reset them occasionally. Clocks often drift differently depending on their quality, the exact power they get from the battery, the surrounding temperature and other environmental variables. Thus the same clock can have different clock drift rates at different occasions.
Mechanical watches drift much more than quartz ones, but they are designed to drift ahead rather than behind, so that the watch gains time, making it easier to set the time to the second with the hack (stop mechanism) function.
More advanced clocks and old mechanical clocks often have some kind of speed trimmer where one can adjust the speed of the clock and thus reduce the clock drift. For instance, in pendulum clock
Pendulum clock
A pendulum clock is a clock that uses a pendulum, a swinging weight, as its timekeeping element. The advantage of a pendulum for timekeeping is that it is a resonant device; it swings back and forth in a precise time interval dependent on its length, and resists swinging at other rates...
s the clock drift can be manipulated by slightly changing the length of the pendulum
Pendulum
A pendulum is a weight suspended from a pivot so that it can swing freely. When a pendulum is displaced from its resting equilibrium position, it is subject to a restoring force due to gravity that will accelerate it back toward the equilibrium position...
. The formula of Fast drift is dc/dt>1.
Atomic clocks
Atomic clockAtomic clock
An atomic clock is a clock that uses an electronic transition frequency in the microwave, optical, or ultraviolet region of the electromagnetic spectrum of atoms as a frequency standard for its timekeeping element...
s are very precise and have nearly no clock drift. The rotation of the Earth itself actually has much more clock drift (less accuracy) than modern atomic clocks. Thus to keep the Coordinated Universal Time
Coordinated Universal Time
Coordinated Universal Time is the primary time standard by which the world regulates clocks and time. It is one of several closely related successors to Greenwich Mean Time. Computer servers, online services and other entities that rely on having a universally accepted time use UTC for that purpose...
(UTC) in line with the Earth's rotation, a leap second
Leap second
A leap second is a positive or negative one-second adjustment to the Coordinated Universal Time time scale that keeps it close to mean solar time. UTC, which is used as the basis for official time-of-day radio broadcasts for civil time, is maintained using extremely precise atomic clocks...
is added to some years.
Relativity
As EinsteinAlbert Einstein
Albert Einstein was a German-born theoretical physicist who developed the theory of general relativity, effecting a revolution in physics. For this achievement, Einstein is often regarded as the father of modern physics and one of the most prolific intellects in human history...
predicted, relativistic effects can also cause clock drift due to time dilation
Time dilation
In the theory of relativity, time dilation is an observed difference of elapsed time between two events as measured by observers either moving relative to each other or differently situated from gravitational masses. An accurate clock at rest with respect to one observer may be measured to tick at...
. This is because there is no fixed universal time, time being relative to the observer. Special relativity
Special relativity
Special relativity is the physical theory of measurement in an inertial frame of reference proposed in 1905 by Albert Einstein in the paper "On the Electrodynamics of Moving Bodies".It generalizes Galileo's...
describes how two clocks held by people in different inertial frames
Inertial frame of reference
In physics, an inertial frame of reference is a frame of reference that describes time homogeneously and space homogeneously, isotropically, and in a time-independent manner.All inertial frames are in a state of constant, rectilinear motion with respect to one another; they are not...
(i.e. moving with respect to each other but not accelerating or decelerating) will each appear to tick more slowly to the other person.
In addition to this, general relativity
General relativity
General relativity or the general theory of relativity is the geometric theory of gravitation published by Albert Einstein in 1916. It is the current description of gravitation in modern physics...
gives us gravitational time dilation
Gravitational time dilation
Gravitational time dilation is the effect of time passing at different rates in regions of different gravitational potential; the lower the gravitational potential, the more slowly time passes...
. Briefly, a clock in a higher gravitational field (e.g. closer to a planet) will appear to tick more slowly. People holding these clocks would agree on which clock appeared to be going faster.
Note that it is time itself rather than the function of the clock which is affected. Both effects have been experimentally observed.
Time dilation is of practical importance. For instance, the clocks in GPS satellites
Global Positioning System
The Global Positioning System is a space-based global navigation satellite system that provides location and time information in all weather, anywhere on or near the Earth, where there is an unobstructed line of sight to four or more GPS satellites...
experience this effect due to the reduced gravity they experience (making their clocks appear to run more quickly than those on Earth) and must therefore incorporate relativistically corrected calculations when reporting locations to users. If general relativity were not accounted for, a navigational fix based on the GPS satellites would be false after only 2 minutes, and errors in global positions would continue to accumulate at a rate of about 10 kilometers each day.
Random number generators
Computer programComputer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
s often need high quality random number
Random number
Random number may refer to:* A number generated for or part of a set exhibiting statistical randomness.* A random sequence obtained from a stochastic process.* An algorithmically random sequence in algorithmic information theory....
s, especially for cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. There are several similar ways clock drift can be used to build random number generators (RNGs).
One way to build a hardware random number generator is to use two independent clock crystals
Crystal oscillator
A crystal oscillator is an electronic oscillator circuit that uses the mechanical resonance of a vibrating crystal of piezoelectric material to create an electrical signal with a very precise frequency...
, one that for instance ticks 100 times per second and one that ticks 1 million times per second. On average the faster crystal will then tick 10,000 times for each time the slower one ticks. But since clock crystals are not precise, the exact number of ticks will vary. That variation can be used to create random bits. For instance, if the number of fast ticks is even, a 0 is chosen, and if the number of ticks is odd, a 1 is chosen. Thus such a 100/1000000 RNG circuit can produce 100 somewhat random bits per second.
Typically such a system is biased—it might for instance produce more zeros than ones—and so hundreds of somewhat random bits are "whitened"
Decorrelation
Decorrelation is a general term for any process that is used to reduce autocorrelation within a signal, or cross-correlation within a set of signals, while preserving other aspects of the signal. A frequently used method of decorrelation is the use of a matched linear filter to reduce the...
to produce a few unbiased bits.
There is also a similar way to build a kind of "software random number generator". This involves comparing the timer tick of the operating system (the tick that usually is 100–1000 times per second) and the speed of the CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
. If the OS timer and the CPU run on two independent clock crystals the situation is ideal and more or less the same as the previous example. But even if they both use the same clock crystal the process
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
/program that does the clock drift measurement is "disturbed" by many more or less unpredictable events in the CPU such as interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s and other processes and programs that runs at the same time. Thus the measurement will still produce fairly good random numbers. Some argue they are then not true random numbers but they seem to be good enough for most needs.
Note that most hardware random number generators such as the ones described above are fairly slow. Therefore most programs only use them to create a good seed that they then feed to a pseudorandom number generator
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
or a cryptographically secure pseudorandom number generator
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
to produce many random numbers fast.
Timing attack
In 2006, a side channel attackSide channel attack
In cryptography, a side channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than brute force or theoretical weaknesses in the algorithms...
was published that exploited clock skew based on CPU heating. The attacker causes heavy CPU load on a pseudonymous
Pseudonymity
Pseudonymity is a word derived from pseudonym, meaning 'false name', and anonymity, meaning unknown or undeclared source, describing a state of disguised identity. The pseudonym identifies a holder, that is, one or more human beings who possess but do not disclose their true names...
server, causing CPU heating. CPU heating is correlated with clock skew, which can be detected by observing timestamps (under the server's real identity).