Mailing List Archive

On Tue, 1 Feb 2000, Dave Dykstra wrote:

> Ok, maybe I'm missing something. If you have a good initial seed
> to your PRNG and you save it in a protected file the way ssh 1.2.27
> does, is there any problem with not using the EGD (or /dev/random
> because it's not available)? We could take some of the code from
> the EGD (ported to C) or from some other open source package to
> get the initial seed, when we don't mind spending a little extra
> time, and from then on do things more quickly without the aid of an
> external program or driver. Right?

A seed alone is not enough. You need to occassionally add new entropy
to the pool, otherwise your RNG is just a PRNG. OpenSSH already has a
PRNG, which it seeds from /dev/urandom or from EGD - it trusts these
to be high quality sources of random data.

It would be great if someone could resurrect some of the entropy
gathering hooks from ssh-1.2.16 and combine them with the pool
functions of a Yarrow modified to use OpenSSL's crypto routines.

-d

--
| "Bombay is 250ms from New York in the new world order" - Alan Cox
| Damien Miller - http://www.mindrot.org/
| Email: djm@mindrot.org (home) -or- djm@ibs.com.au (work)

On Tue, Feb 01, 2000 at 03:00:20PM -0800, Gary E. Miller wrote:
> The whole point of /dev/random is to add entropy to PNRG. The problem
> with a PNRG is that once you figure out the internal state of the PNRG
> you can recover past states and predict future states. Once you can
> predict states, even if the prediction is slightly off, then you have
> seriously reduced the strength of the encryption.
>
> This is the basis of the cracks for S/Key and some other crypto.

OK, but could one figure out the internal state of the PNRG without having
access to the seed file? I'm not worried about compromise of the seed file.
I would think that if somebody could figure out what numbers were being
generated by the PNRG they could predict what it might do in the future, but
as far as I know there's no way for someone to do that without having already
broken into the legitimate client or server.

I don't get why SSH 1.2.27 can do without /dev/random and EGD and yet
there's been no CERT advisories saying that that part of SSH is insecure.


> The solution to this problem is to add entropy to your PNRG to make
> it more truly random. That is why openssh wants to use /dev/random
> or EGD at regular intervals. EGD is to much of a pig and /dev/random
> requires kernel patching. So I agree with you that porting something
> like EGD to C is the way to go.

It's not enough to just port EGD to C, it needs to be integrated with
openssh and very preferably not be a separate process. There's nothing
inherently wrong with that, is there (ignoring for the moment the amount
of work it would take)?

- Dave Dykstra

On Wed, 2 Feb 2000, Dave Dykstra wrote:

> On Tue, Feb 01, 2000 at 03:00:20PM -0800, Gary E. Miller wrote:
[..]
> > The solution to this problem is to add entropy to your PNRG to make
> > it more truly random. That is why openssh wants to use /dev/random
> > or EGD at regular intervals. EGD is to much of a pig and /dev/random
> > requires kernel patching. So I agree with you that porting something
> > like EGD to C is the way to go.
>
> It's not enough to just port EGD to C, it needs to be integrated with
> openssh and very preferably not be a separate process. There's nothing
> inherently wrong with that, is there (ignoring for the moment the amount
> of work it would take)?
>
I think the main consern is if you have 5 clients all with their own
EGD built into OpenSSH. They could all be pulling the same entropy
and all coming up with pretty close to the same random numbers. Enough
that it could be used against the box in question.

<shrug> Or maybe I'm off.. That is what I see at this point. Since
the logic is all the same. And your feeding roughly the same data
into the function. Your going to get common results. Where as a
/dev/random or a single EGD process controls what each client gets
out of the entropy pool therefor the data should (if it's a good
sampling of entropy) be different.

Dave Dykstra wrote:
>
8<
> OK, but could one figure out the internal state of the PNRG without having
> access to the seed file? I'm not worried about compromise of the seed file.
> I would think that if somebody could figure out what numbers were being
> generated by the PNRG they could predict what it might do in the future, but
> as far as I know there's no way for someone to do that without having already
> broken into the legitimate client or server.
>
> I don't get why SSH 1.2.27 can do without /dev/random and EGD and yet
> there's been no CERT advisories saying that that part of SSH is insecure.
>
That's not the way I would look at things. The absence of a compromise
doesn't mean none exist. (I'm sure that's not what you meant either.) I
don't accept that what ssh-1 is prepared to live with is necessarily the
right way for us to go.

Your point is taken. I don't think most people who use SSH use it to
protect against people already logged in. Though I still think the
setuid() argument stands, there are other problems with running
standalone. A daemon sitting in the background has (potentially at
least) a much larger entropy pool to work with, and that should give a
more random result.

8<
> It's not enough to just port EGD to C, it needs to be integrated with
> openssh and very preferably not be a separate process. There's nothing
> inherently wrong with that, is there (ignoring for the moment the amount
> of work it would take)?

I don't agree that it *has* to be directly linked in. That would make it
easier to deploy, which is a win, and if that's the prime goal then
fine. I suspect that, all things being equal, everyone would like to use
/dev/random (a special case of a standalone entropy gathering program)
over builtin functions with designed-in limitations. Since we have to
implement something (or just stick with EGD; probably not acceptable for
long) we should at least consider all the options.

Disregarding the amount of work, I think it would be better to have it
separate. What goes into OpenSSH is Damien's call, though, and since
it's a lot of work for someone either way it might be good to see what
that decision turns out to be in this case.

Ta,
-Andre

Yo Niels!

I think we basically agree, except you missed one point. SCO has no
/dev/random, so open-ssh has no way of reseeding except with EGD. The
problem is to find a portable way to reseed the PNRG on all UNIX hosts,
even those with no /dev/random and without the problems of EGD.

RGDS
GARY

On Wed, 2 Feb 2000, Niels Provos wrote:

> Date: Wed, 02 Feb 2000 09:16:38 -0500
> From: Niels Provos <provos@citi.umich.edu>
> To: gary miller <gem@rellim.com>
> Cc: Dave Dykstra <dwd@bell-labs.com>, openssh-unix-dev@mindrot.org
> Subject: Re: EGD requirement a show stopper for me
>
> In message <Pine.LNX.4.21.0002011450370.22282-100000@ns1.aplatform.com>, "Gary
> E. Miller" writes:
> >FreeS/WAN struggled with this issue for a while and then decided
> >to just go with /dev/random. open-ssh does not have that option.
> OpenSSH uses the alleged RC4 stream cipher to stretch the randomness
> provided by /dev/random into a longer interval. This is a sane
> approach and as far as I can see is practially as secure as the
> mathematical requirements for pseudo-random generators. Furthermore,
> RC4's internal state is reseeded fairly often from /dev/random.
> Looking at purely statistical tests, using RC4 is far better than the
> raw output from /dev/random - at least the last time that I checked on
> it.
>
> Niels.
>

---------------------------------------------------------------------------
Gary E. Miller Rellim 20340 Empire Ave, Suite E-3, Bend, OR 97701
gem@rellim.com Tel:+1(541)382-8588 Fax: +1(541)382-8676

Yo Dave!

On Wed, 2 Feb 2000, Dave Dykstra wrote:

> > The whole point of /dev/random is to add entropy to PNRG. The problem
> > with a PNRG is that once you figure out the internal state of the PNRG
> > you can recover past states and predict future states. Once you can
> > predict states, even if the prediction is slightly off, then you have
> > seriously reduced the strength of the encryption.
> >
> > This is the basis of the cracks for S/Key and some other crypto.
>
> OK, but could one figure out the internal state of the PNRG without having
> access to the seed file? I'm not worried about compromise of the seed file.
> I would think that if somebody could figure out what numbers were being
> generated by the PNRG they could predict what it might do in the future, but
> as far as I know there's no way for someone to do that without having already
> broken into the legitimate client or server.
I am not a crptographer, I just listen to them, and they are all
fanatics about having real randomness. A lot of these guys hook
geiger counters, FM radio, zener diodes, sound cards, etc. because
they think they see patterns in /dev/random. I am not that fanatic,
but have seen attacks based on guessing the PRNG.

> I don't get why SSH 1.2.27 can do without /dev/random and EGD and yet
> there's been no CERT advisories saying that that part of SSH is insecure.
If you check the file randoms.c in the ssh 1.2.27 source you
will see how they do it. They pull in entropy from not only /dev/random
if it is available, but from a lot of other sources. Sources like:
ps laxww
ps -al
ls -alni /tmp/.
w
netstat -s
netstat -an
netstat -in

As you can see, ssh is pretty paranoid about having a good random
seed.

RGDS
GARY
---------------------------------------------------------------------------
Gary E. Miller Rellim 20340 Empire Ave, Suite E-3, Bend, OR 97701
gem@rellim.com Tel:+1(541)382-8588 Fax: +1(541)382-8676

On Wed, Feb 02, 2000 at 12:12:08PM -0800, Gary E. Miller wrote:
> > I don't get why SSH 1.2.27 can do without /dev/random and EGD and yet
> > there's been no CERT advisories saying that that part of SSH is insecure.
> If you check the file randoms.c in the ssh 1.2.27 source you
> will see how they do it. They pull in entropy from not only /dev/random
> if it is available, but from a lot of other sources. Sources like:
> ps laxww
> ps -al
> ls -alni /tmp/.
> w
> netstat -s
> netstat -an
> netstat -in
>
> As you can see, ssh is pretty paranoid about having a good random
> seed.

Note that random_acquire_environmental_noise() is only called if there is
no seed file. After that they frequently mix the seed file with
random_acquire_light_environmental_noise(). OpenSSH could do something
like that and avoid a separate process.

- Dave Dykstra

On Wed, Feb 02, 2000 at 07:23:49PM +1100, Damien Miller wrote:

> It would be great if someone could resurrect some of the entropy
> gathering hooks from ssh-1.2.16 and combine them with the pool
> functions of a Yarrow modified to use OpenSSL's crypto routines.
>

I'm doing the yarrow port right now, it's just a slog through the
Windows typedefs right now.

-Andre

--
Andre Lucas <andre.lucas@dial.pipex.com>
http://dspace.dial.pipex.com/andre.lucas/

On Wed, Feb 02, 2000 at 07:23:49PM +1100, Damien Miller wrote:

8<
> It would be great if someone could resurrect some of the entropy
> gathering hooks from ssh-1.2.16 and combine them with the pool
> functions of a Yarrow modified to use OpenSSL's crypto routines.
>

I've got Yarrow0.8.71 ported over from Win32, and I'm just moving the
hooks. Before I do that, can you confirm that we can use stuff from ssh
version 1.2.16? The openssh ssh manpage talks about 1.2.12. I can't find
a copy 1.2.12 to compare.

I only bring it up because the distributions on the all the offical ssh
mirrors start at 1.2.13, which makes me think 1.2.12 has some special
significance.

From what I've seen, it shouldn't be too much work to port the crypto to
openssl. Yarrow-0.8.71 only seems to use SHA-1 (no three key triple-DES
as in the paper.)

Ta,
-Andre

--
Andre Lucas <andre.lucas@dial.pipex.com>
http://dspace.dial.pipex.com/andre.lucas/

On Thu, 3 Feb 2000, Andre Lucas wrote:

> On Wed, Feb 02, 2000 at 07:23:49PM +1100, Damien Miller wrote:
>
> 8<
> > It would be great if someone could resurrect some of the entropy
> > gathering hooks from ssh-1.2.16 and combine them with the pool
> > functions of a Yarrow modified to use OpenSSL's crypto routines.
> >
>
> I've got Yarrow0.8.71 ported over from Win32, and I'm just moving the
> hooks. Before I do that, can you confirm that we can use stuff from ssh
> version 1.2.16? The openssh ssh manpage talks about 1.2.12. I can't find
> a copy 1.2.12 to compare.

Wow - well done! I think that it was ssh-1.2.16 that was used as the
basis for OpenSSH, but I am not 100%

In any case you can retrieve what the OpenBSD team started with:

cvs -z9 -d ":pserver:anoncvs@anoncvs1.usa.openbsd.org:/cvs" co -r 1.1 -d ssh-import src/usr.bin/ssh

This includes the random hooks.

> >From what I've seen, it shouldn't be too much work to port the crypto to
> openssl. Yarrow-0.8.71 only seems to use SHA-1 (no three key triple-DES
> as in the paper.)

Excellent. Yell if you want a hand.

Thanks again,
Damien

--
| "Bombay is 250ms from New York in the new world order" - Alan Cox
| Damien Miller - http://www.mindrot.org/
| Email: djm@mindrot.org (home) -or- djm@ibs.com.au (work)

On Fri, Feb 04, 2000 at 11:44:07AM +1100, Damien Miller wrote:
> > I've got Yarrow0.8.71 ported over from Win32, and I'm just moving the
> > hooks. Before I do that, can you confirm that we can use stuff from ssh
> > version 1.2.16? The openssh ssh manpage talks about 1.2.12. I can't find
> > a copy 1.2.12 to compare.
>
> Wow - well done! I think that it was ssh-1.2.16 that was used as the
> basis for OpenSSH, but I am not 100%

ftp://ftp.cert.dfn.de/pub/tools/net/ssh/snapshots/ssh-1.2.12.tar.gz
is the base for OpenSSH. the commit message has a typo, the webpage is correct.

Yo Damien!

I found out that the Apache product used the truerandom lib
as an alternative for /dev/random. Here is a message I got
from SCO support about:
ftp://ftp.research.att.com/dist/mab/librand.shar

It looks pretty easy to port. I could do it it you are interested.


RGDS
GARY
---------------------------------------------------------------------------
Gary E. Miller Rellim 20340 Empire Ave, Suite E-3, Bend, OR 97701
gem@rellim.com Tel:+1(541)382-8588 Fax: +1(541)382-8676

<information on the TrueRandom library>

This library is used by Apache to generate random numbers in the absence
of /dev/random. It isn't a standard library, but is something that seems
to have floated around on the net in more-or-less source form for some
time. It isn't large - only a couple of hundred lines or so of source,
and works by exploiting timing differences in system interrupts, rather
than on specific and deterministic algorithms.

I picked up my copy of it from

ftp://ftp.research.att.com/dist/mab/

in librand.shar. It's now immortalized in the Apache build, so if you
have any problems getting it from here, I can send you a copy.

Regarding its use, well, I've appended the Apache routine that does
the either-or thing with /dev/random and librand.a.

--------------83C16BD8BCDAEE8FB656BDEA
Content-Type: text/plain; charset=us-ascii;
name="rand"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="rand"

static void initialize_secret(server_rec *s)
{
#ifdef DEV_RANDOM
FILE *rnd;
size_t got, tot;
#else
extern int randbyte(void); /* from the truerand library */
unsigned int idx;
#endif

ap_log_error(APLOG_MARK, APLOG_NOERRNO|APLOG_NOTICE, s,
"Digest: generating secret for digest authentication ...");

#ifdef DEV_RANDOM
#define XSTR(x) #x
#define STR(x) XSTR(x)
if ((rnd = fopen(STR(DEV_RANDOM), "rb")) == NULL) {
ap_log_error(APLOG_MARK, APLOG_CRIT, s,
"Digest: Couldn't open " STR(DEV_RANDOM));
exit(EXIT_FAILURE);
}
if (setvbuf(rnd, NULL, _IONBF, 0) != 0) {
ap_log_error(APLOG_MARK, APLOG_NOERRNO|APLOG_CRIT, s,
"Digest: Error trying to disable buffering for " STR(DEV_RANDOM));
exit(EXIT_FAILURE);
}
for (tot=0; tot<sizeof(secret); tot += got) {
if ((got = fread(secret+tot, 1, sizeof(secret)-tot, rnd)) < 1) {
ap_log_error(APLOG_MARK, APLOG_CRIT, s,
"Digest: Error reading " STR(DEV_RANDOM));
exit(EXIT_FAILURE);
}
}
fclose(rnd);
#undef STR
#undef XSTR
#else /* use truerand */
/* this will increase the startup time of the server, unfortunately...
* (generating 20 bytes takes about 8 seconds)
*/
for (idx=0; idx<sizeof(secret); idx++)
secret[idx] = (unsigned char) randbyte();
#endif /* DEV_RANDOM */

ap_log_error(APLOG_MARK, APLOG_NOERRNO|APLOG_NOTICE, s, "Digest: done");
}

--------------83C16BD8BCDAEE8FB656BDEA--