How good is security via hashing

[Robin Becker]

A python web process is producing files that are given randomized names of the form

hhhhhh-YYYYMMDDhhmmss-rrrrrrrr.pdf

where rrr.. is a 128bit random number (encoded as base62). The intent of the
random part is to prevent recipients of one file from being able to guess the
names of others.

The process was originally a cgi script which meant each random number was
produced thusly


pid is process id, dur is 4 bytes from /dev/urandom.

random.seed(long(time.time()*someprimeint)|(pid<<64)|(dur<<32))
rrr = random.getrandbits(128)


is this algorithm safe? Is it safe if the process is switched to fastcgi and the
initialization is only carried out once and then say 50 rrr values are generated.

 

[Jean-Paul Calderone]

A python web process is producing files that are given randomized names of the form

hhhhhh-YYYYMMDDhhmmss-rrrrrrrr.pdf

where rrr.. is a 128bit random number (encoded as base62). The intent of the
random part is to prevent recipients of one file from being able to guessthe
names of others.

The process was originally a cgi script which meant each random number was
produced thusly

pid is process id, dur is 4 bytes from /dev/urandom.

random.seed(long(time.time()*someprimeint)|(pid<<64)|(dur<<32))
rrr = random.getrandbits(128)

is this algorithm safe? Is it safe if the process is switched to fastcgi and the
initialization is only carried out once and then say 50 rrr values are generated.

How much randomness do you actually have in this scheme? The PID is
probably difficult
for an attacker to know, but it's allocated roughly monotonically with
a known
wrap-around value. The time is probably roughly known, so it also
contributes less
than its full bits to the randomness. Only dur is really
unpredictable. So you have
something somewhat above 4 bytes of randomness in your seed - perhaps
8 or 10. That's
much less than even the fairly small 16 bytes of "randomness" you
expose in the
filename.

The random module is entirely deterministic, so once the seed is known
the value you
produce is known too.

Is 10 bytes enough to thwart your attackers? Hard to say, what does
an attack look like?

If you want the full 16 bytes of unpredictability, why don't you just
read 16 bytes from
/dev/urandom and forget about all the other stuff?

Jean-Paul

 

[Robin Becker]

On 07/06/2011 12:40, Jean-Paul Calderone wrote:
astcgi and the

How much randomness do you actually have in this scheme? The PID is
probably difficult
for an attacker to know, but it's allocated roughly monotonically with
a known
wrap-around value. The time is probably roughly known, so it also
contributes less
than its full bits to the randomness. Only dur is really
unpredictable. So you have
something somewhat above 4 bytes of randomness in your seed - perhaps
8 or 10. That's
much less than even the fairly small 16 bytes of "randomness" you
expose in the
filename.

I'm sure you're right about the limited amount of entropy in the initial state,
but how much state can be in the prng?

The random module is entirely deterministic, so once the seed is known
the value you
produce is known too.

Is 10 bytes enough to thwart your attackers? Hard to say, what does
an attack look like?

An attacker could try to gain information from seeing others' results by
guessing the filename.

an attack would consist of generating a sample file via a web query which might
take 1 or 2 seconds; the sequence number could then be seen and if the state
established future filenames could be guessed if fastcgi is in operation.

In a cgi type scheme that requires searching over the pid space, the time space
and some random bits from the OS.

I'm not sure such an attack is realistic given the size of the space even in the
initial seed.

If you want the full 16 bytes of unpredictability, why don't you just
read 16 bytes from
/dev/urandom and forget about all the other stuff?

Jean-Paul

I have a vague memory that the original author felt that entropy might run out
or something like that so reading from /dev/urandom always was not a good idea.

FreeBSD re-uses the entropy, but the end target is Solaris so I'm not really
sure about the details of /dev/urandom.

 

[Paul Rubin]

I have a vague memory that the original author felt that entropy might
run out or something like that so reading from /dev/urandom always was
not a good idea.

If there is enough entropy to begin with, then /dev/urandom should be
cryptographically strong. The main danger is just after the system
boots and there has not yet been much entropy gathered from physical
events.

FreeBSD re-uses the entropy, but the end target is Solaris so I'm not
really sure about the details of /dev/urandom.

No idea about Solaris. Another area of danger these days is virtual
hosts, since their I/O may be completely simulated. They are not
certified for payment card processing, mostly for that reason.

 

[Nobody]

I have a vague memory that the original author felt that entropy might
run out or something like that so reading from /dev/urandom always was
not a good idea.

The problem with /dev/urandom is that it shares the same entropy pool as
/dev/random, so you're "stealing" entropy which may be needed for tasks
which really need it (e.g. generating SSL/TLS keys).

Personally, I'd take whatever "cheap" entropy I can get and hash it.
If you're going to read from /dev/urandom, limit it to a few bytes per
minute, not per request.

 

[Paul Rubin]

The problem with /dev/urandom is that it shares the same entropy pool as
/dev/random, so you're "stealing" entropy which may be needed for tasks
which really need it (e.g. generating SSL/TLS keys).

The most thorough analysis of Linux's /dev/*random that I know of is
here:

http://www.pinkas.net/PAPERS/gpr06.pdf

It says random and urandom use separate pools, though both fed from the
same primary pool. The point is that reading from one should not
interfere with the other.

There have been interminable threads on sci.crypt about /dev/random vs
/dev/urandom and the sane conclusion seems to be that if there's enough
entropy in the system, /dev/urandom is not really worse than
/dev/random. Any type of userspace randomness collection is probably
worse than either. If you're doing typical low-to-medium security stuff
on traditional PC hardware (i.e. not virtualized, not something like
OpenWRT which has few real entropy sources), /dev/urandom is fine. If
you don't believe in its cryptographic PRNG, you shouldn't believe in
OpenSSL either.

If you're doing high security stuff (server-side financial apps, etc.)
then /dev/urandom and /dev/random are both considered not good enough,
and your PC is probably leaking keys, so you should be using dedicated
crypto hardware.

Personally, I'd take whatever "cheap" entropy I can get and hash it.
If you're going to read from /dev/urandom, limit it to a few bytes per
minute, not per request.

That's really not going to help you.

 

[Nobody]

That's really not going to help you.

In what way?

If I need security, I'll use /dev/random or /dev/urandom. If I don't, I'll
save the real entropy for something which needs it.

Issues with observability of entropy sources (mainly the use of network
traffic as an entropy source) are overblown. The staff of a co-location
facility have physical access, and anyone further out doesn't see enough
of the traffic for it to do them any good.

Predicting an entropy-hashing RNG based upon a fraction of the entropy
and a fraction of the output is a theoretical attack which is only
relevant to entities who have far easier options available to them.

 

[Paul Rubin]

In what way?
If I need security, I'll use /dev/random or /dev/urandom. If I don't, I'll
save the real entropy for something which needs it.

I just mean that if /dev/urandom has enough internal state then within
practical bounds, its output is effectively random no matter how much
you read from it. Did you look at the paper I linked? "Saving" the
"real entropy" isn't feasible since the maximum capacity of the two
"real" entropy pools is 4096 bits each. They will both fill pretty
quickly on an active system. Reading /dev/urandom will empty the
primary pool but /dev/random is fed by the secondary pool, which
receives entropy from both the primary pool and physical sources. If
you read too fast from /dev/urandom, the worst that happens (if I
understand correctly) is that the rate you can read from /dev/random is
cut in half and it will block more often. If that's a serious issue for
your application, you should probably rethink your approach and get an
HSM.