You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Jonathan Nieder <jr...@gmail.com> on 2011/11/03 06:44:42 UTC
[RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Hi,
In December, 2004, Alex Jacques reported[1]:
> If there is little entropy available then svnserve can hang for up to
> several minutes waiting on /dev/random. This is similiar to the problem
> listed here:
>
> http://svnbook.red-bean.com/en/1.1/apb.html#svn-ap-b-sect-1.2.14
As a result, since November, 2005, svnserve on Debian has been patched
to avoid calling apr_generate_random_bytes() and just use the current
time as a nonce. That's ugly. So I'd like your advice.
The random number is used by the CRAM-MD5 auth mechanism in svnserve
(and could be used by other programs calling svn_ra_svn_cram_server
from libsvn_ra_svn-1, though I doubt anyone does that). One
possibility would be to have an internal random number source
initialized from a strong random source at startup, to avoid drawing
on the entropy pool so much. Another possibility would be to enhance
apr's random number source API to allow requesting random bytes
without so much entropy (erandom/frandom) or without blocking on lack
of entropy (urandom).
What do you think? Is forcing !APR_HAS_RANDOM and just using
apr_time_now() as Debian currently does safe, or does it expose users
to a security risk? Would some other simple fix (e.g., calling
"lrand48") make sense and be generally useful?
[1] http://bugs.debian.org/285708
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Greg Hudson <gh...@MIT.EDU>.
On 11/03/2011 05:10 PM, Jonathan Nieder wrote:
> Why would that be? When someone dumps in 20 bits of data from a
> strong, in-hardware, random number source, even if the PRNG is utterly
> stupid, it can have an unguessable 20 bits of internal state. After
> reading enough random numbers, I will have enough information to guess
> the seed and learn what comes next.
If you want to attack a PRNG, you need very little of the output
state--only enough to distinguish between the possible values of the
generator seed. What you do need is for the generator seed to be
partially guessable; otherwise, you will be trying to brute-force a
128-bit or 256-bit seed, which is impractical.
If I somehow know the initial generator state, and you reseed your
generator with only 20 unguessable bits, I will be able to determine
those bits using 20 bits of output and 2^20 effort (which is easy), and
then I will know all of the generator state again. However, if you
reseed with enough unguessable bits that I can't brute-force them, it
doesn't matter how much output I see; I will never again be able to
determine the internal state.
For the Fortuna generator, for instance, if I discover a way to
determine the generator state solely by observing the output, then I
will also have discovered a plaintext recovery attack against AES-256.
For more, see chapter 9 of _Cryptography Engineering_.
> A good PRNG helps mitigate that somewhat
More than "somewhat". Any PRNG which doesn't have the above properties
in its generator is insecure for any cryptographic purpose, and would be
considered a security bug in the operating system.
In another message, Peter Samuelson wrote:
> apr_time_now() has microsecond resolution.
It has microsecond precision but not necessarily microsecond accuracy.
For instance,
http://fixunix.com/kernel/378888-gettimeofday-resolution-linux.html
suggests that two requests arriving within a 10ms window could get the
same nonce.
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Jonathan Nieder <jr...@gmail.com>.
Greg Hudson wrote:
> As for the second threat, at least on Linux, /dev/random output still
> comes from the PRNG. It just keeps an internal counter and blocks when
> the PRNG has "run out of" its guess at estimated input entropy. (This
> is exceedingly silly, because a PRNG doesn't "use up" input entropy as
> it generates results; either it has unguessable internal state or it
> doesn't.)
Why would that be? When someone dumps in 20 bits of data from a
strong, in-hardware, random number source, even if the PRNG is utterly
stupid, it can have an unguessable 20 bits of internal state. After
reading enough random numbers, I will have enough information to guess
the seed and learn what comes next.
A good PRNG helps mitigate that somewhat, of course (especially if
unfriendly people doesn't have access to the entire random number
stream and information about when it was seeded).
More practically speaking, the benefit of /dev/random's entropy
accounting on Linux is to annoy people enough to get them to find a
good source of random data. When I am generating a PGP key, I am
grateful for the notification. Less so when picking a nonce for svn
access. Another downside of using either /dev/random or /dev/urandom
is that it involves revealing information about the random number
state, which could hurt the security of other applications if there is
not enough entropy.
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Greg Hudson <gh...@MIT.EDU>.
On 11/03/2011 01:44 AM, Jonathan Nieder wrote:
> What do you think? Is forcing !APR_HAS_RANDOM and just using
> apr_time_now() as Debian currently does safe, or does it expose users
> to a security risk?
I suspect it makes the server vulnerable to a replay attack.
The right answer is to use /dev/urandom. Using /dev/random has highly
questionable advantages over using /dev/urandom, and it's unfortunate
that APR only provides an interface to one and not the other.
A longer analysis: if a system has collected even a small amount of
entropy (128 bits) relative to what an attacker can guess since boot, it
can generate an infinite amount of pseudo-random data without risk of
vulnerability, if it uses a suitable PRNG function. The actual dangers
are that (1) the system has not accumulated enough entropy, and maybe we
should wait until it has, or (2) the system has a bad PRNG function.
Using /dev/random does not protect against either threat very effectively.
As for the first threat, it's very difficult to mitigate because a
system cannot generally estimate its entropy very well. It throws
possible entropy events into a pool and mixes them together, but it
doesn't have a very good measure of how guessable those events were.
PRNG algorithms like Fortuna seek to guarantee that the PRNG will
eventually reach an unguessable state (by ensuring that more and more
possible entropy is used each time the internal state is updated, until
eventually an update happens that the attacker can't brute-force), but
they can't tell you when they've reached that point.
As for the second threat, at least on Linux, /dev/random output still
comes from the PRNG. It just keeps an internal counter and blocks when
the PRNG has "run out of" its guess at estimated input entropy. (This
is exceedingly silly, because a PRNG doesn't "use up" input entropy as
it generates results; either it has unguessable internal state or it
doesn't.) An application can only protect against a poor system PRNG by
implementing its own generator, and it's far simpler to declare it the
system's responsibility to fix its PRNG if there's a security issue
associated with it.
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
On Thursday, November 03, 2011 11:42 AM, "Stefan Sperling" <st...@elego.de> wrote:
> On Thu, Nov 03, 2011 at 12:01:58PM +0200, Daniel Shahaf wrote:
> > Something tells me that when a cryptographic protocol calls for random
> > numbers then a quasiconstant or known value wouldn't do instead.
>
> Put more bluntly, if protocol designers bothered with putting a random
> number into their protocol, implementors must assume that designers had
> a good reason for the number to be *random*. Using the current time instead
> of a random number is breaking the protocol implementation.
>
> I mean, seriously, it's not like Debian didn't have a track record
> of breaking security with custom patches. Remember the ssh keys debacle?
> I am amazed to learn such a patch exists in Debian's Subversion packages.
> I think this patch should be pulled from Debian's Subversion packages
> immediately.
>
Yes, in general if you don't know why a random number was used you'd
better not make it any less random. But please don't rush to
conclusions without studying the concrete protocol.
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Stefan Sperling <st...@elego.de>.
On Thu, Nov 03, 2011 at 12:01:58PM +0200, Daniel Shahaf wrote:
> > As a result, since November, 2005, svnserve on Debian has been patched
> > to avoid calling apr_generate_random_bytes() and just use the current
> > time as a nonce. That's ugly. So I'd like your advice.
> >
> > The random number is used by the CRAM-MD5 auth mechanism in svnserve
> > (and could be used by other programs calling svn_ra_svn_cram_server
> > from libsvn_ra_svn-1, though I doubt anyone does that). One
> > possibility would be to have an internal random number source
> > initialized from a strong random source at startup, to avoid drawing
> > on the entropy pool so much. Another possibility would be to enhance
> > apr's random number source API to allow requesting random bytes
> > without so much entropy (erandom/frandom) or without blocking on lack
> > of entropy (urandom).
> >
>
> Fixing this by extending APR's API sounds good. Would the change be
> backportable to APR 1.4.x too?
Whatever is done, please do not introduce problems on operating
systems where the built-in strong random number generator works
just fine without blocking applications all the time.
> > What do you think? Is forcing !APR_HAS_RANDOM and just using
> > apr_time_now() as Debian currently does safe, or does it expose users
> > to a security risk?
>
> Something tells me that when a cryptographic protocol calls for random
> numbers then a quasiconstant or known value wouldn't do instead.
Put more bluntly, if protocol designers bothered with putting a random
number into their protocol, implementors must assume that designers had
a good reason for the number to be *random*. Using the current time instead
of a random number is breaking the protocol implementation.
I mean, seriously, it's not like Debian didn't have a track record
of breaking security with custom patches. Remember the ssh keys debacle?
I am amazed to learn such a patch exists in Debian's Subversion packages.
I think this patch should be pulled from Debian's Subversion packages
immediately.
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Peter Samuelson <pe...@p12n.org>.
[Daniel Shahaf]
> Something tells me that when a cryptographic protocol calls for
> random numbers then a quasiconstant or known value wouldn't do
> instead. It might still provide some security guarantees but I
> wouldn't assume it would provide all guarantees of the
> correctly-executed protocol.
It doesn't call for random numbers. It calls for a nonce. The nonce
is not secret - it is passed in plaintext to the client - it just has
to be different every time, to prevent replay. Given the nature of
cryptographic hashes, it doesn't even have to be _very_ different to be
useless to an attacker. To attack the challenge in CRAM, you have to
attack _two_ checksums, outer and then inner. Even one bit of entropy
scrambles the inner checksum, and _that_ scrambles the outer.
apr_time_now() has microsecond resolution. There's no way a single
svnserve process will handle two connections in the same microsecond.
(I note that even at gigabit speeds, two adjacent network packets will
be about a microsecond apart.)
That leaves multiple processes calling apr_time_now in the same
microsecond. So I think I'll add a getpid() in there somewhere.
(The Debian patch, I mean. Probably not useful here.)
> > Would some other simple fix (e.g., calling
> > "lrand48") make sense and be generally useful?
Well, rand() and friends have to be seeded _somehow_, usually from time
of day, so that doesn't seem much better than apr_time_now().
> No objection here, but doesn't APR already use lrand48() if it's available?
If that's true, we shouldn't even be having this conversation at all.
The problem is that /dev/random was being exhausted.
--
Peter Samuelson | org-tld!p12n!peter | http://p12n.org/
Re: [PATCH] Re: [RFC] ra_svn::make_nonce: how to cope with entropy
shortages?
Posted by Jonathan Nieder <jr...@gmail.com>.
Peter Samuelson wrote:
> The problem is that svnserve is often used in 'inetd' mode, one
> connection per process. I've recommended that for years, as being
> easier and less hassle than managing a separate daemon. Given inetd
> mode, your approach will exhaust /dev/random just as fast as the status
> quo.
True. Well, to avoid exhausting /dev/random, one needs some fallback
source for the nonce. There are two cases:
- in 'inetd' mode, I guess the pid could work.
- in non-inetd mode, an in-process PRNG would work well.
Using the timestamp as nonce feels a little silly, given that the
challenge is going to look like
<no...@hostname>
Though it's better than just using nonce=0, say (since some
hard-to-predict amount of time passes between when the nonce and
timestamp are generated for the challenge). Times like these make me
wish that more systems had erandom or some other interface for
lower-quality random numbers.
The random(4) manpage says:
If you are unsure about whether you should use /dev/random or
/dev/urandom, then probably you want to use the latter. As a
general rule, /dev/urandom should be used for everything
except long-lived GPG/SSL/SSH keys.
APR was fixed accordingly in version 1.3.3 (see r652830,
"configure.in: Prefer /dev/urandom over /dev/random"). Running
$ strings /usr/lib/libapr-1.so.0.4.5 | grep dev
/dev/zero
/dev/urandom
/dev/null
I see that Debian has the fix.
If refining the Debian-specific code here, please consider patching
the upstream code for the !APR_HAS_RANDOM case, too. That way, your
changes can get a wider audience and more review, it is more likely
that the code will be updated when assumptions of the surrounding code
change, and people on those rare platforms that lack a secure random
number source would benefit as well.
Sorry to have been taking so long to figure this one out.
Re: [PATCH] Re: [RFC] ra_svn::make_nonce: how to cope with entropy
shortages?
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
On Thursday, November 03, 2011 4:26 PM, "Peter Samuelson" <pe...@p12n.org> wrote:
>
> [Jonathan Nieder]
> > state = apr_random_standard_new(pool);
> >
> > for (;;) {
> > while (apr_random_secure_ready(state) == APR_ENOTENOUGHENTROPY) {
> > apr_generate_random_bytes(buf, sizeof(buf));
> > apr_random_add_entropy(state, buf, sizeof(buf));
> > }
> >
> > apr_random_secure_bytes(state, ret, n);
> > yield;
> > }
>
> The problem is that svnserve is often used in 'inetd' mode, one
> connection per process. I've recommended that for years, as being
> easier and less hassle than managing a separate daemon. Given inetd
> mode, your approach will exhaust /dev/random just as fast as the status
> quo.
>
> (Also, and this is minor, those functions didn't exist in apr 0.9, for
> those poor souls still needing to build Subversion on platforms with
> Apache 2.0. I don't _think_ we've ever dropped support for our
> original apr platform, have we?)
Yes, but I'm not sure that means we can't use the above code when we
detect a new APR at build time. I mean, APR_VERSION_AT_LEAST() exists
for a reason.
> --
> Peter Samuelson | org-tld!p12n!peter | http://p12n.org/
>
Re: [PATCH] Re: [RFC] ra_svn::make_nonce: how to cope with entropy
shortages?
Posted by Peter Samuelson <pe...@p12n.org>.
[Jonathan Nieder]
> state = apr_random_standard_new(pool);
>
> for (;;) {
> while (apr_random_secure_ready(state) == APR_ENOTENOUGHENTROPY) {
> apr_generate_random_bytes(buf, sizeof(buf));
> apr_random_add_entropy(state, buf, sizeof(buf));
> }
>
> apr_random_secure_bytes(state, ret, n);
> yield;
> }
The problem is that svnserve is often used in 'inetd' mode, one
connection per process. I've recommended that for years, as being
easier and less hassle than managing a separate daemon. Given inetd
mode, your approach will exhaust /dev/random just as fast as the status
quo.
(Also, and this is minor, those functions didn't exist in apr 0.9, for
those poor souls still needing to build Subversion on platforms with
Apache 2.0. I don't _think_ we've ever dropped support for our
original apr platform, have we?)
--
Peter Samuelson | org-tld!p12n!peter | http://p12n.org/
[PATCH] Re: [RFC] ra_svn::make_nonce: how to cope with entropy
shortages?
Posted by Jonathan Nieder <jr...@gmail.com>.
Daniel Shahaf wrote:
> On Thursday, November 03, 2011 12:44 AM, "Jonathan Nieder" <jr...@gmail.com> wrote:
>> Another possibility would be to enhance
>> apr's random number source API to allow requesting random bytes
>> without so much entropy (erandom/frandom) or without blocking on lack
>> of entropy (urandom).
>
> Fixing this by extending APR's API sounds good. Would the change be
> backportable to APR 1.4.x too?
I think a proper fix is possible without changing APR's API.
The calling sequence is something like this:
state = apr_random_standard_new(pool);
for (;;) {
while (apr_random_secure_ready(state) == APR_ENOTENOUGHENTROPY) {
apr_generate_random_bytes(buf, sizeof(buf));
apr_random_add_entropy(state, buf, sizeof(buf));
}
apr_random_secure_bytes(state, ret, n);
yield;
}
Justification: that is how /dev/random seems to be meant to be used
(as source for a random seed, with userspace taking over after that).
Actually, using apr_random_insecure_bytes without seeding the
generator would be about as good, as far as I can tell. What is
important is that a given <nonce, timestamp> pair is not likely to be
repeated.
Complications:
- This involves application-local state. Making the PRNG state
per-thread would be fussy. And on the other hand if it's global,
synchronizing between threads could hurt performance.
- Could be controversial on platforms "where the built-in strong
random number generator works just fine without blocking
applications all the time" (but aren't good random numbers a scarce
resource almost everywhere?).
[...]
> Something tells me that when a cryptographic protocol calls for random
> numbers then a quasiconstant or known value wouldn't do instead.
Right. It's not as bad as it sounds because abusing this requires
(1) intercepting and replaying challenge responses in real time
(2) getting your <nonce, timestamp, hostname> tuple to match the one
from the challenge you intercepted. On affected installations,
both the nonce and timestamp are timestamps with 1-microsecond
resolution.
but it certainly looks like a problem to me.
So how about this to start, to avoid providing people on platforms
with !APR_HAS_RANDOM with a false sense of security?
[[[
* subversion/libsvn_ra_svn/cram.c (make_nonce): Refuse to build if
APR_HAS_RANDOM is unset, instead of falling back to using a
timestamp as nonce.
]]]
Index: subversion/libsvn_ra_svn/cram.c
===================================================================
--- subversion/libsvn_ra_svn/cram.c (revision 1197294)
+++ subversion/libsvn_ra_svn/cram.c (working copy)
@@ -117,18 +117,10 @@
return svn_ra_svn_flush(conn, pool);
}
-/* If we can, make the nonce with random bytes. If we can't... well,
- * it just has to be different each time. The current time isn't
- * absolutely guaranteed to be different for each connection, but it
- * should prevent replay attacks in practice. */
+/* Make the nonce with random bytes. */
static apr_status_t make_nonce(apr_uint64_t *nonce)
{
-#if APR_HAS_RANDOM
return apr_generate_random_bytes((unsigned char *) nonce, sizeof(*nonce));
-#else
- *nonce = apr_time_now();
- return APR_SUCCESS;
-#endif
}
svn_error_t *svn_ra_svn_cram_server(svn_ra_svn_conn_t *conn, apr_pool_t *pool,
Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?
Posted by Daniel Shahaf <d....@daniel.shahaf.name>.
On Thursday, November 03, 2011 12:44 AM, "Jonathan Nieder" <jr...@gmail.com> wrote:
> Hi,
>
> In December, 2004, Alex Jacques reported[1]:
>
> > If there is little entropy available then svnserve can hang for up to
> > several minutes waiting on /dev/random. This is similiar to the problem
> > listed here:
> >
> > http://svnbook.red-bean.com/en/1.1/apb.html#svn-ap-b-sect-1.2.14
>
> As a result, since November, 2005, svnserve on Debian has been patched
> to avoid calling apr_generate_random_bytes() and just use the current
> time as a nonce. That's ugly. So I'd like your advice.
>
> The random number is used by the CRAM-MD5 auth mechanism in svnserve
> (and could be used by other programs calling svn_ra_svn_cram_server
> from libsvn_ra_svn-1, though I doubt anyone does that). One
> possibility would be to have an internal random number source
> initialized from a strong random source at startup, to avoid drawing
> on the entropy pool so much. Another possibility would be to enhance
> apr's random number source API to allow requesting random bytes
> without so much entropy (erandom/frandom) or without blocking on lack
> of entropy (urandom).
>
Fixing this by extending APR's API sounds good. Would the change be
backportable to APR 1.4.x too?
> What do you think? Is forcing !APR_HAS_RANDOM and just using
> apr_time_now() as Debian currently does safe, or does it expose users
> to a security risk?
Something tells me that when a cryptographic protocol calls for random
numbers then a quasiconstant or known value wouldn't do instead. It might
still provide some security guarantees but I wouldn't assume it would provide
all guarantees of the correctly-executed protocol.
> Would some other simple fix (e.g., calling
> "lrand48") make sense and be generally useful?
>
No objection here, but doesn't APR already use lrand48() if it's available?
> [1] http://bugs.debian.org/285708
>