Cyrus POP3 Issue

[Marco Colombo]

Henrique de Moraes Holschuh wrote:
[...]
> That scenario assumes a lot of stuff like complete SHA break, complete PRNG
> break, capabilities to observe almost all output of the PRNG ordered on
> time, etc.

SHA1 break is enough. Guessing the state of the PRNG just requires
observing a very short sequence of its output. Once you guess the state
you don't need to observe the output. You can compute it. See below.

> So, why bother going the pure theory road, if it is useless to access just
> how safe (or unsafe) a real-world decision is?  We have to at the very
> least, mix both approaches.
> 
> 
>>Henrique de Moraes Holschuh wrote:
>>
>>>Which, in a Cyrus server, won't be helpful since there is a lot of disk
>>>activity and the PRNG state changes quite often, provided you don't keep it
>>>drained (and thus without activity because nobody can talk to the server!).
>>>
>>>Using random instead of urandom goes a long way into helping to keep the
>>>pool drained (the kernels usually protect a small amount of entropy 
>>>won't let urandom drain it completely).
>>
>>Well, the problem is simple. Let's say your server generated 100 session
>>keys in the last minute. If the system collected at least 100*key size
>>random bits, you could have used /dev/random. If it not, and you used
>>/dev/urandom, the attacker has fewer bits to guess. Let E be this number. 
>>Assuming that he knows the pool state _now_ (that is, he collects enough 
>>keys and is able to break SHA1 and reverse the PRNG algorithm to obtain 
>>its state), in order to get the pool state _one minute_ ago, he has to
>>guess E bits only, which it is easier than guessing all 100 keys. Every
>>_single_ bit you got out of /dev/urandom for your session keys when
>>/dev/random would have blocked _halves_ the attacker's effort.
> 
> 
> That is not taking into account that there are small amounts of entropy
> entering the pool (which WILL mess with blind backwards-in-time predicitions,
> since you cannot adjust for those.  If it is non-blind, i.e. you have some
> blocks, you may be able to avoid this).  That will not make the attack
> impossible, but it will increase the search space a bit (I have no idea how
> much).
> 
> AND that also assumes no catastrophic reseeds, which completely reset the
> PRNG, and kills any possibility of blind predictions to the past.

If those amounts of entropy are "small", you don't have work on the keys.
You work on PRNG output. Let's consider the Linux case. The attacker grabs
the code in random.c, and makes it userspace. The PRNG is no kernel magic,
it's just an algorithm. Let's see what happens:
1) the attacker gains some knowledge about the PRNG output... by
initiating some connections, and looking at the session keys, maybe.
Let's assume he can do that.
2) the attacker breaks SHA1, and gains useful knowledge about the real
PRNG output. Let's assume he can do that.
3) the attacker computes the internal state of the PRNG from the output
sequence. This is easy for most PRNG (even if the formula isn't
invertible, he can compute a table of possible outputs).
4) the attacker initializes its userspace PRNG with the state. Note that
even if the knowledge about the state is partial, he can try different
states until he gets the right output.

Once he guessed the state, he is able to reproduce all the output. He gets
some output now and then and is able to know exaclty what he missed.
Note that he's not searching key space at all. He _knows_ the keys.

If some entropy is added, all he needs to do is to search the space
of _these_ bits. In 2^(n+1)-1 attempts, he is able to guess n bits.
Not easy, but doable if n is small (we assumed added entropy is "small").
He adds all possible bits to his PRNG, and checks the output for a match.
Or he can start back at step 1), whichever is cheaper.

Note that the only big assumption in this scenario is that he can break
SHA1. Observing small amount of output is possible. Given a small sequence
of the (cleartext) PRNG output, the number of possible internal states 
that produce the sequance is very small, and the real one can easily
guessed.

You seem to have too much faith in catastrophic reseeds, btw. If he's
using the same sourcecode of the kernel, _his_ program is going to
perform a reseed at the same time, in the same way. No matter how
complicated the mechanism is (multiple pools, anti-draining techniques),
you need N random bits in input in order to generate N random bits in
output. There's no way an algorithm can increase entropy.

> Indeed.  The problem is that the errors are not always to the safe side.
> The fact that all Linux kernels in the 2.4.x series will *over*estimate
> entropy fed *from userspace* by a factor of 4 doesn't exactly fill me with
> confidence that the other entropy accounting done by those kernels is ok.

Errors should be on the safe side. If not, it's a bug. And anyway, you're
referring to _root_ writing to /dev/random. You can, and actually should,
use the right IOCTL in order to increase the entropy bits count. It makes
no sense to write() 256 bytes of random data and accounting 1024 bits on
the counter. That is the _theoretical maximum_ amount of entropy, and is
_never_ correct in practice, no matter what. Increase the counter only by
256 _bits_ (that's 1/8 of the provided data) and you'll be on the safe
side. I do assume root is always knowing what he's doing. The same IOCTL
can be used by root to increase the counter w/o adding any entropy at all.
The kernel has little protection from root misbehaving.

[...]
>>The kernel is quite conservative in estimating randomness, that's why
>>the pool empties so easily, expecially on headless servers.
> 
> 
> THAT is what I am NOT completely at ease with.  I sure hope it is being
> quite conserative.

Well let's say it is per specs. If the implementation is buggy, it can be
fixed.

>>And no, you're not depending on the security of the PRNG+hash when you're
>>using /dev/random, assuming they're not buggy.
> 
> 
> Even if the entropy pool has zero bits of randomness but the kernel thinks
> it still has some?  That was what I was talking about...

Again, that should never happen. AFAIK, it happens only when root increases
the entropy bit counter from userspace.

>>>Given that fact, IMHO you are much better using urandom anyway, because the
>>>system will still work enough close to an empty entropy pool to regen that
>>>pool a bit.
>>
>>I'm not following you. Unless you're implying that the only source of
>>randomness is the result of the activity the _needs_ the random bits.
> 
> 
> Not really.  But most of the activity in a headless Cyrus server needs
> TCP/IP to happen, and last time I checked, my boxes stopped talking to the
> network well when I drained them completely (2.4.25 or so at that time, I
> think. I should test that with 2.6.10).  Local processes doing a lot of IO
> without the need of the network would avoid this issue, obviously.  As would
> someone typing at a keyboard or moving a mouse around, etc.

I think TCP needs entropy when establishing a new connection. I don't
think anything needs entropy on _packet_ generation. Existing connections
should be fine.

>>Well, first I think disk activity is much bigger for already connected
>>clients. I know some clients out there make a new connections to the
> 
> 
> ONLY if the network layer does not starve due to a lack of entropy.  If it
> doesn't anymore, then you are perfectly correct.

See above.

>>Second, giving up security only to squeeze some more entropy bits from
>>your disks isn't a winning strategy, IMHO.
> 
> Well, that's what I am trying to argue.  That in the SASL case (relatively
> short-lived session keys, tipically on headless servers), you are not
> sacrificing too much security by using urandom, and that the loss of
> security in that case outweights starving the entire machine of entropy.

My point being: if you're fine with the above attack scenario, i.e. you
trust SHA1 (which again I think it's sensible today, even with recent
doubts about SHA1), why getting entropy from the kernel at all? Just use
your own hashed PRNG in userspace. If you're using /dev/urandom only
because it's there already, well, you're describing a _library_ not a
kernel service.

> Which STILL means disabling APOP if you don't need it is a major good idea.
> In fact, IMHO the APOP default should be disabled, since it is not widely
> used (people who would deploy APOP usually know better and deploy IMAP
> instead, in my experience).

Agreed.

>>>If, and only if, you have no new entropy going in.  If you have a few bits
>>>of entropy going in, they have a reduced search space (which IS already a
>>>very bad thing)... unless the kernel does a catastrophic reseed of the 
>>>PRNG.
>>>Which on newer Linux kernels for example, it does as often as it possibly
>>>can.
>>
>>I know that every single bit of entropy going in changes the state, but
>>the attacker needs only to try the possible values. The reduced search
>>space _is_ the problem.
> 
> 
> Yes.  The fact that those bits come in a variable rate helps a bit, but they
> are easy to find in the stream if you have a perfect break.  Catastrophic
> reseeds force you to break the thing again, though, since previous state is
> useless in that case.

But is the new state based on unknown data? How many times can you reseed,
before you run out of entropy bits? I think current code _does not_ reseed 
the secondary pool, when the primary pool is low on entropy.

>>foresee. That is, entropy bits. In order to truly randomly reseed the PRNG,
>>you need N truly random bits, where N is the size of the seed.
> 
> 
> Exactly.

But when entropy is low, you don't have those bits... if you reseed,
it has to be in a predictable way. If you do have N bits, your "consuming"
them by reseeding. Sooner or later you'll run out of this reserve as well.

[...]
>>>                                 Well, I am not afraid of the SHA search
>>>space, in Linux, BSDs and Solaris, that have somewhat good PRNGs.  The 
>>
>>state
>>
>>>of the entropy pool changes unpredictably quite often enough.
>>
>>What do you mean for "good" PRNG? Not invertible? That's not what you'd
> 
> 
> One whose output is not easy to predict [while NOT drained], unlike, say,
> that crap some unnamed OSes used a few years ago.

:-) the problem is not to predict the output. Once we know the state, the
output is _computable_. The problem is knowing the state by observing the
output. Given numbers N1, N2, and N3, say, how many possible states may
produce that sequence? I state the number is low. If it were big, the
sequence (N1, N2, N3) would be _very_ likely to happen, and that's not a
"good" PRNG for sure.

[...]
>>>At least so far.  Someone was talking about removing "that useless 
>>>feature", so keep an eye for it to make sure they don't.
>>
>>Well something must be done about the "feature". If all you need is a PRNG
>>whose seed it randomly changed now and then (ala /dev/urandom, when the
>>pool is almost empty), you'd better implement your own in user space, and
>>_always_ use that.
> 
> 
> I'd rather have it fixed where it will do the most good, which is in the
> kernel.  I don't want to see what happens in the Windows world happening in
> the Unix world...
> 
> 
>>Let me explain better. Let's say your cyrus server needs 100k/bits random 
>>bits per second. The kernel gets 25kbit/s (_you_ should underestimate
>>them as well, btw, adding less to the counter). So, every 100000 bits
> 
> 
> That source has H > 0.998, and I am already underestimating it to H=0.99,
> which is good enough for my needs. I could be really paranoid and use 0.75
> or even 0.5, but it is a slow source, so that would hurt.

Interesting enough. :-) How do you know the real H? How do you measure it?
Are you sure you're underestimating it?

> But are you talking about a fully-compromised /dev/urandom above, or about a
> non-compromised /dev/urandom?  For a fully-compromised urandom, I agree with
> you.

All it takes is to break SHA1. Ok, recent Linux kernel has a complicated
multi-level PRNG. But it's just a kind of (not-so-tested) crypto. I'm not
sure it counts as additionaly security.

[...]
>>Secondly, assuming you're fine with it, the question is: why don't you
>>_always_ drain 25kbit/s only, if that is enough for you?
> 
> I draw less than that most of the time, and for *my* case telling SASL to
> use /dev/random is fine.  Heck, I have always about 100k bits of entropy
> bufferized and waiting for a load spike, and I could easily make that 100M
> bits if I needed to and wanted to waste that much real memory (pages with
> random data are obviously locked and cannot be swapped).

Why? You can have an userspace daemon buffer it. Writes on /dev/random
block as well, if I recall right. The daemon will awake everytime the
entropy count is low.

[...]
>>Why don't you use your private PRNG, extract 100kbit/s from it, and get
>>only 25kbit/s from the kernel, _always_? By using /dev/urandom, you're
>>asking for more than, by definition, you need.
> 
> 
> Good point.  But I would actually argue that we should enhance /dev/urandom
> to be configurable to be able to do exactly that.

Why bloat the kernel with something that can easily be userspace? The only
kernel functionality it needs is already provided by /dev/random.

>>So yes, I am one who thinks that /dev/urandom is a useless feature
>>(almost). Run a user space daemon instead, which applications can register
>>to, and ask for the quality they need, and no more.
> 
> I'd say that /dev/urandom *would* be an useless feature if we could trust
> people to know what they are doing when writing their PRNGs. We cannot, so
> we better improve urandom to have better resource reservation semanthics.
> 
> It *could* be teached to set a maximum output of real entropy per calling
> process, if one is willing to write the code.  That would fix the issue you
> talk about.  And IMHO it would be a safer (in the real world) way to go for
> it.
> 
> But yes, it does not have to be done in kernel space.  In which case we are
> probably better off removing urandom or making it a named pipe managed by
> that user space daemon.  *And* teaching SASL to use the daemon instead of
> mucking with /dev/random (and there we go arguing it all again ;-) ).

No, here we agree. :-) It's _your_ system, _you_ are setting policies.
The deamon would provide SASL with _exacly_ the level of security you
want/are fine with.

I think we're slightly drifting off-topic. I'd end this thread here if you
don't mind. For most cases, a DoS is worse, in practice, than a remote
chance of total break at SASL/SSL level.

An interesting reading is:
http://www.ussg.iu.edu/hypermail/linux/kernel/0208.2/0347.html
and the whole thread (both previous and following mails). Yes, the idea
of userspace /dev/urandom is not new. :-)
Years ago I've played with /dev/random stuff. The result was this
project: http://freshmeat.net/projects/random_tools/
AFAIK, no one uses it, and it's unmaintained at all. Modern PCs seem to
collect enough entropy for my needs.

.TM.
-- 
       ____/  ____/   /
      /      /       /			Marco Colombo
     ___/  ___  /   /		      Technical Manager
    /          /   /			 ESI s.r.l.
  _____/ _____/  _/		       Colombo at ESI.it

---
Cyrus Home Page: http://asg.web.cmu.edu/cyrus
Cyrus Wiki/FAQ: http://cyruswiki.andrew.cmu.edu
List Archives/Info: http://asg.web.cmu.edu/cyrus/mailing-list.html