function for clockticks since 1980?

[Peter J. Holzer]

Presuming that you will want to run the code for another couple of
years, that would require at least a 57 bit number, if one's
baseline is a 3 GHz clock.

I think the OP referred to the real-time clock, not the CPU clock. So
the clock frequency would be at most 1 kHz, not 3 GHz.

hp

 

[Spoon]

Linux and other POSIX-compatible systems have the gettimeofday function,
which returns the time in seconds and microseconds since the epoch. Be
warned that the actual resolution of the clock can be much coarser:
Linux/x86 actually uses a microsecond clock, but some other Unixes have
resolutions of something between 1/60 to 1/1024 of a second.

Linux/x86 (and possibly other platforms as well) are able to offer
sub-jiffie resolution by interpolating cycle counter values.

On Linux/x86 the /resolution/ is less than 1 ns when using the TSC
on a CPU faster than 1 GHz.

(Contrast resolution with precision and accuracy.)

 

[Peter J. Holzer]

Linux/x86 (and possibly other platforms as well) are able to offer
sub-jiffie resolution by interpolating cycle counter values.

As I wrote: "Linux/x86 actually uses a microsecond clock" (actually the
clock is 1.19 MHz (4.77 MHz/4)). But I didn't want to get too deep into
system specifics, this is comp.lang.c, after all, not
comp.os.linux.hardware.pc.8254 .

The point I wanted to make is that if you have a function like
gettimeofday, which is available on a wide variety of systems, you
cannot rely on the resolution or granularity being the same as
precision.

gettimeofday returns time in a struct containing to integral values, one
representing seconds, and the other microseconds. So the precision is
1 µs. The resolution (or granularity) may be much coarser, though. Image
an system, which doesn't have a high resolution timer (or doesn't use it
for computing system time), instead it has a timer chip which generates
interrupts at 256 Hz, and a counter is incremented at each interrupt
(this is called "jiffies" in Linux, but just "clock ticks" on most
systems). On such a system, if you call gettimeofday repeatedly, it may
return 11718 in the microseconds field several times, then 15625 several
times, then 19531, etc. All in all, just 256 different values.

Which leads me to a cautionary tale: When I was at the university, two
of the courses involved writing "real" programs. One team at our
institute wrote a program for managing students: Keeping personal data,
assigning exercises and exams, computing scores, etc., and among other
things, creating accounts on the unix machines. To get random passwords,
they did something like this:

struct timeval tv;
gettimeofday(&tv, NULL);
srand(tv.tv_usec);
for (i = 0; i < 8; i++) {
pwd = pwd_chars[rand() % sizeof pwd_chars];
}

After my long prelude, you see of course at once what happened.
That system used a 256 Hz timer (which was actually quite fine at that
time, most systems only used 60 Hz), so tv.tv_usec could only contain
256 different values, so there were only 256 different seeds and
therefore only 256 different passwords. We noticed the problem at the
start of the next semester. (1 million different passwords would still
have been easy to brute-force, but we probably would never have noticed
this by accident)

hp

 

[Keith Thompson]

gettimeofday returns time in a struct containing to integral values, one
representing seconds, and the other microseconds. So the precision is
1 µs. The resolution (or granularity) may be much coarser, though. Image
an system, which doesn't have a high resolution timer (or doesn't use it
for computing system time), instead it has a timer chip which generates
interrupts at 256 Hz, and a counter is incremented at each interrupt
(this is called "jiffies" in Linux, but just "clock ticks" on most
systems). On such a system, if you call gettimeofday repeatedly, it may
return 11718 in the microseconds field several times, then 15625 several
times, then 19531, etc. All in all, just 256 different values.

[...]

This isn't strictly topical, except that I'm going to argue that it
could theoretically apply to the behavior of the standard time()
function.

I've seen implementations of gettimeofday() whose actual precision is
fairly coarse (say, 0.01 second), but that still manage to yield a
unique value on each call. For example, successive results might be
something like:

{ 1185837859, 730000 }
{ 1185837859, 730001 }
{ 1185837859, 730002 }
{ 1185837859, 730003 }
{ 1185837859, 730004 }
{ 1185837859, 740000 }
{ 1185837859, 740001 }
...

In other words, if gettimeofday() is called again within the same
0.01-second interval, the implementation successively adds one
microsecond to the result to make it unique.

A time() implementation that returns, say, microseconds since some
epoch in 64 bits could do the same thing. But of course it's not
required to do so <OT>nor is gettimeofday()</OT>.

 

[David Thompson]

<[email protected]> wrote:

You don't need clock-ticks since 1980, not unless you are planning
to run retroactive transactions for 25 years ago. You only need
(at best) clock-ticks since some arbitrary reference point
starting about now.

Several people have suggested using /dev/random or /dev/urandom in Linux.
However, the nature of random number generators and pseudo-
random number generators is that you get repeated values (or at least
you do on the better ones) -- "uniformly distributed random numbers"
are, mathematically, "selection with replacement", and if you can
never generate the same numbers, you have "selection without
replacement" which is not "uniformly distributed". If you use a

However, it should be extremely unlikely to repeat a value for two
consecutive tries, or even within a window small relative to the
range. And for many _P_RNGs impossible, even though they are indeed
uniform over a large (enough) window. Yes, in principle a (T)RNG could
return a thousand consecutive zeros, but in practice one that does so
is broken, not absurdly lucky.

pseudo random-number generator, then you need to keep careful track
of the "seed" that is currently in use, because if you have a crash
(or power outage, or maintenance, or switch to a new machine) then you
need to pick up with exactly the same internal seed you left off at --
if you don't, then you risk accidently re-using random numbers and
thus session-IDs. Unless, that is, one of your components in creating
the session ID is an absolute timestamp at a resolution fine enough
as to be sure to have a different value when your system came back up.

Or just any value which is (reliably) different when you come back up.
I worked on a system that for database transaction-id's, which
similarly need to be globally and permanently unique (for suitable
definitions of global and permanent), included a "crash count" (in
reserved stable=disk storage) which was incremented on a startup that
did not find clean state stored. (If clean state WAS found, it
included the next value for a, in this case, sequential counter.)

But if you don't have that, if you do need to keep complete track
of the current PRNG seed, then you might as well just use a sequential
counter (and hash the constructed session ID together with some
private key.)

Assuming the hash does not interact badly with some (any) structure of
the input. The hashes used in (modern = computer) cryptography like
MD5 and SHA1 (to name the most common and best known) are designed to
produce pseudorandom output for any unique input sequence, of which a
counter is the simplest case. Other (homegrown) hashes do not come
with the same kind of "guarantee". (Research fairly recently, about a
year ago, has found _collision_ attacks on MD5, that is where the
adversary can control the input to the hash, or most of it, but so far
as is known, this does not weaken it for the type of usage here.
Modern ciphers like DES and AES are similarly designed to be
pseudorandom _permutations_ hence reversible of their input = output
space, and thus one now-NIST-approved mode of operation is essentially
to encrypt sequential counter values and use the results for a
conventional (XOR) stream cipher -- subject the limitations for all
such stream ciphers regarding known-plain alteration etc.)

- formerly david.thompson1 || achar(64) || worldnet.att.net