User: Password:
|
|
Subscribe / Log in / New account

Random numbers for ASLR

Random numbers for ASLR

Posted May 14, 2009 4:27 UTC (Thu) by wahern (subscriber, #37304)
Parent article: Random numbers for ASLR

What's wrong w/ the ARC4-derived PRNG, arc4random(), that OpenBSD uses? Faster than SHA-1, it exemplifies an acceptable balance between security and performance. Not to mention there are more modern one-way hashes which are both stronger and faster to compute than SHA-1.

Linux suffers from one of the worst cases of NIH syndrome I've ever come across. It's only become worse over the years.


(Log in to post comments)

Random numbers for ASLR

Posted May 14, 2009 5:10 UTC (Thu) by bvdm (guest, #42755) [Link]

Yes, exactly. I find this compromise a bit shocking.

The best practice, which is fairly well-known from NIST and academic sources, is to use a strong (and expensive) RNG source to initialize a stream cipher. Preferably a trusted block cipher such as AES in a stream mode-of-operation should be used given the security history of stream ciphers, though RC4 may still be okay.

The stream output is by definition cryptographically still strong but computationally far less expensive random bytes. Definitely much cheaper than using a crypto hash function such as the note-quite-broken-yet SHA-1 or the obsolete MD4/5.

Why is a hack being implemented when a standard solution exist? Why is MD4 still in the kernel at all?

Random numbers for ASLR

Posted May 14, 2009 5:22 UTC (Thu) by ebiederm (subscriber, #35028) [Link]

Because the code was in the kernel and already debugged.

Because a fix was needed.

Because no one who was good with pseudo random number generators cared to join in the conversation.

Because just about anything is better than a constant value.

So are you willing to write a patch to correct the situation?

This is problem of communication

Posted May 14, 2009 14:00 UTC (Thu) by khim (subscriber, #9252) [Link]

So are you willing to write a patch to correct the situation?

A lot of guys can and will write a patch (including me), but few a ready to fight with kernel developers...

This is problem of communication

Posted May 14, 2009 18:10 UTC (Thu) by zooko (guest, #2589) [Link]

Yeah, I personally would hesitate to offer patches or analysis to lkml, simply because I don't want to be part of a conversation with that tone.

For what it is worth, it sounds like Matt Mackall stated a plausible threat -- that an attacker might be able to predict results from get_random_int(), thus being able to predict the address space randomization that is supposed to stop him. Linus's reply as quoted in this article, saying that Matt's concern is "TOTALLY INSANE" doesn't make sense to me.

I don't think that any cryptographer would ridicule Matt for this concern. To the contrary, I've always observed cryptographers (the vast majority of them) to be polite and precise. Engaging in ridicule leads one to make mistakes. ;-)

This is problem of communication

Posted May 15, 2009 0:10 UTC (Fri) by droundy (subscriber, #4559) [Link]

From what I could tell, his point was that they're only using 8 bits of randomness in the ASLR (presumably because of address-layout constraints and not wanting to waste address space?), which means that 256 tries will get you the answer anyhow. If there's a simple and easy attack, why should we work so hard to prevent a tricky sophisticated attack that achieves the same result?

But then again, maybe I misunderstood, in which case I'll be glad to be corrected...

Random numbers for ASLR

Posted May 15, 2009 15:43 UTC (Fri) by NRArnot (subscriber, #3033) [Link]

Patch?

How about changing the name? get_randomish_int()? get_somewhat_random_int()? fast_get_randomish_int()?

Any of these would make it clear what is (or isn't) being accomplished.

Random numbers for ASLR

Posted May 14, 2009 15:18 UTC (Thu) by copsewood (subscriber, #199) [Link]

The question Linus raised concerns how much slower can we accept a kernel everyone uses in order to defend against a secondary attack against address space layout randomisation defences (ASLR) against a primary class of attack (buffer or heap overflow) when insufficient bits of entropy are available within the ASLR defence to prevent brute force attacks against this defence in the first place. If 8 bits of genuine entropy are available, this makes a successful buffer overflow exploit work one in 2**8 i.e. 256 times attempted compared to without ASLR, and if 16 bits are available the exploit might work one in 2**16 times given a fully unpredictable ASLR within this set of permutations compared to a system without ASLR.

So the whole point of ASLR isn't to make a buffer or heap attack impossible, but to make it more difficult for an attacker to have code of their choosing executed by a vulnerable application, which is hopefully more likely to crash when an exploit is attempted than give a privilege escalation to the attacker. In a more fully secure system, the attacker wouldn't be able to carry out the primary buffer or heap overflow attack on a vulnerable application through an unvalidated input method, because these primary security bases would have been dealt with first; ASLR is a second line of defence and not the first.

So if the ASLR coding is too performance expensive it will have to be a compile time option and too few people will compile it in to make it of any use to them at all. Better to have enough speed that it doesn't have to be an option and to have enough unpredictability so those trying to defeat it are more likely to use brute force than PRNG state prediction.

Random numbers for ASLR

Posted May 14, 2009 20:55 UTC (Thu) by wahern (subscriber, #37304) [Link]

This argument is pure misdirection. There should be little doubt that cryptographically strong PRNGs exist which are just as performant as whatever ridiculous MD4 hack is being used now. Clearly there are cryptographers falling over themselves to try provide the code to Linus & Co.; he's just not hearing it.

Use a strong PRNG now, and worry (or not worry, as it may be) about ASLR entropy later. But who's going to care about the latter if the former would be the weak chain, regardless.

And let's not forget that there's an army of wholly untalented OEM engineers who will follow Linus & Co's lead, and will be (and surely are) using this inadequate PRNG for sundry cases in existing products, mimicking the same, poor calculus Linus uses in his stubborn defense.

Random numbers for ASLR

Posted May 14, 2009 21:47 UTC (Thu) by nix (subscriber, #2304) [Link]

There should be little doubt that cryptographically strong PRNGs exist which are just as performant as whatever ridiculous MD4 hack is being used now. Clearly there are cryptographers falling over themselves to try provide the code to Linus & Co.; he's just not hearing it.
If so, they're not doing it in that thread. Matt presented a PRNG that was twice as slow as the existing (crappy but cheap) MD4 one, to be used in time-critical contexts like process execution. That's not going to fly, given that that path has attention paid to every last cycle.

Random numbers for ASLR

Posted May 15, 2009 11:55 UTC (Fri) by man_ls (guest, #15091) [Link]

Linus wanted to speak about a small % instead of a big factor. Just from reading the article Ingo provided the answer: looking at the numbers in context we are talking about a 1% performance hit in fork(). If your system is completely CPU-bound and fork() takes half the CPU then your task will take 0.5% more to execute (seven extra minutes every day). I think it is quite acceptable for even a small increase in security.

Random numbers for ASLR

Posted May 15, 2009 12:33 UTC (Fri) by hppnq (guest, #14462) [Link]

If you genuinely worry about address space related exploits, you will know that ASLR is not really going to save the day regardless of the RNG used, although obviously some randomization is needed.

Random numbers for ASLR

Posted May 15, 2009 18:17 UTC (Fri) by nix (subscriber, #2304) [Link]

ASLR can make attacks very much harder, but only on 64-bit systems (and of
course only if more than 8 bits of randomness is used). On 32-bit there
isn't the room to make attacks significantly harder :(

Random numbers for ASLR

Posted May 14, 2009 13:01 UTC (Thu) by nix (subscriber, #2304) [Link]

How much slower is arc4random() than the current function, though? *That* is why Linus rejected SHA-1 in the first place...

(and this last-names kick gets seriously silly when you find yourself referring to Linus by his last name. Not even the Economist did that.)

Mr Torvalds

Posted May 15, 2009 12:01 UTC (Fri) by man_ls (guest, #15091) [Link]

and this last-names kick gets seriously silly when you find yourself referring to Linus by his last name.
If you are referring to Jake as the author of the article then I have to disagree. A consistent naming convention (first name or last name) adds to the clarity of the story. I find it mildly distracting when Jon refers to Linus by first name in an article, even if it is completely justified given the circumstances.
Not even the Economist did that.
How come?

Mr Torvalds

Posted May 15, 2009 12:21 UTC (Fri) by hppnq (guest, #14462) [Link]

You too?! Edge, you mean.

Mr Torvalds

Posted May 15, 2009 18:32 UTC (Fri) by man_ls (guest, #15091) [Link]

But I am not a reporter, my friend :D I try to follow the usual (altough perhaps outfashioned) rule: use first name for those people with whom I have had personal contact (maybe not too personal, even an exchange in a public forum qualifies); and family name elsewhere. So you see, when I say "Linus" I am actually being a bit pretentious. And of course I have had several pleasant exchanges with Jon and Jake.

Mr Torvalds

Posted May 15, 2009 14:47 UTC (Fri) by jake (editor, #205) [Link]

> Not even the Economist did that.

Yeah I was a bit puzzled by nix's comment, assuming, without any real knowledge, that the Economist did its normal 'Mr. Torvalds' on second reference. Which your link would seem to bear out.

There is, after all, more than one 'Linus' working on the kernel. So far, I haven't run into a problem with folks sharing the same last name in a particular article, but first names do collide from time to time.

jake

Mr Torvalds

Posted May 15, 2009 18:16 UTC (Fri) by nix (subscriber, #2304) [Link]

My memory is failing, it seems: that link was pretty persuasive.

(I'm surprised the kernel hasn't run into the Rasmussen/Smith problem yet:
in my experience family names are a *lot* more limited in supply than
personal names. This is especially notable in China.)


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds