LWN: Comments on "Randomizing structure layout"

Randomizing structure layout

bokr — Mon, 04 Sep 2017 22:43:49 +0000

Terminology nit: IMO "hardening" is not the right term
for what this is about, any more than making yourself
harder to hit by wearing camouflage in your own bunker.
It's not even a hard kevlar vest ;-)

Sad if necessary, but real security will come by other means, ISTM.

Obviously, people are trying, from BIOS/UEFI on through hypervisors
and up and sideways to ineluctable management engines. Which may all
be good and clever dogs, but better hope they can be trained to be
loyal to you ;-)

Randomizing snake-oil

Wol — Thu, 25 May 2017 20:47:34 +0000

> Provably secure is pretty much a non-starter as it requires a full and accurate theory of everything, and a proof the hardware you run on meets it's specification. Short of that you will have assumptions that may be wrong somewhere in your approach.

A correctness proof is mathematics.

Hardware is reality.

Congratulations on finding a proof that reality and mathematics coincide ... :-)

Cheers,
Wol

Randomizing snake-oil

smoogen — Thu, 18 May 2017 00:52:38 +0000

I was told by a Dec guy was that the original story was that with the right assumptions you could make anything provably secure and then showed how it could be done with the VMS system. You basically start by assuming all sorts of things like not having an active attacker, a set of actions that the system will only do, dropping down all the hardware to the bare minimum etc etc. All of these are things that various "provable" had used in one set or another.. so why not put them all together. You basically had a brick with VMS installed on it, but it was provable that it was secure within the parameters that could be used.

The problem was that the joke got out hand as someone took it seriously and started passing around about how VMS was superior to Unix because it was provably secure.

How true this story is versus all the others... I don't know.

Randomizing structure layout

nix — Wed, 17 May 2017 12:45:40 +0000

Quite. The point is that if you ask gdb or crash or something else with access to the DWARF for info on some structure member's contents, it'll still be able to tell you what they are, exactly as it always could.

Randomizing structure layout

nix — Wed, 17 May 2017 12:44:13 +0000

Well, if it were built in to GCC and not a plugin this would actually be considered unacceptable: specifying -g should not change the generated code in any way (including disabling, say, structure randomization). What should happen, instead (and what I think does in fact happen) is that the generated debugging info correctly represents the structures' randomized field offsets in the DWARF. (DWARF does not require structure members to be represented in ascending order: indeed, they can be entirely overlapping -- this is how unions are represented -- or even partially overlapping, reversed, or, as here, in random order.)

Contrary to reproducible builds

and — Tue, 16 May 2017 07:51:10 +0000

exactly! With this, exploits would not even work for different versions of the Fedora kernel, i.e., the attacker would have to guess the exact patchlevel of the kernel to make an exploit that depends on structure layout work. While this usually won't stop state-sponsored adversaries from doing targeted attacks, it would likely prevent the spreading of most worms even in scenarios where everyone runs distribution kernels, so I think adding this functionality to the kernel is totally worth its costs. (note that this is just my personal "couch philosophy" -- I'm in involved that effort at all.)

Contrary to reproducible builds

alison — Tue, 16 May 2017 04:30:05 +0000

>you can make the randomization seed depend on the hash of the tarball, so you'll get the same >seed for different builds of the same thing but a different one for a different kernel.

If I understand you correctly, the result would be that each release of a particular package would have a different layout of structs, but everyone who had the same source tarball would build the same package with the same structs. That would certainly make exploits less portable across machines: they would work with the Fedora version of a package perhaps, but not the RHEL or CENTOS ones.

Randomizing structure layout

autious — Mon, 15 May 2017 21:47:30 +0000

Which is kinda the goal I think?

Randomizing structure layout

and — Mon, 15 May 2017 15:59:48 +0000

> It might even work as long as the user doesn't need any third party binary only module.

even in this case it can be made to work fine: mechanisms like DKMS allow to automatically recompile kernel modules after package updates. for this to work, the seed must be stored somewhere in the system, but remember that it is basically already game over if the attacker can access a random file that requires root permissions.

Contrary to reproducible builds

and — Mon, 15 May 2017 15:49:20 +0000

RB should not be a problem: e.g., you can make the randomization seed depend on the hash of the tarball, so you'll get the same seed for different builds of the same thing but a different one for a different kernel.

Randomizing structure layout

tialaramex — Mon, 15 May 2017 12:52:54 +0000

You seem to have assumed that you'll be the one calling the functions. In some scenarios we may be relying upon somebody else to do the calling, and they may not be inclined to run whichever random function we've actually tampered with in the way we hoped.

The pointers are there because _if_ the corresponding function is used we need to follow the pointer, but their presence doesn't mean anybody is actually obliged to use the function. Furthermore, in some cases function pointers are invoked conditionally. The kernel doesn't do this for simple "If exists then..." tests, which are traditionally done just by checking if the pointer is non-NULL (which will work if you scribble over it) but it does do this in other places, and some people's C code may not follow that style even for "if exists then..." tests so they'd benefit from this feature too.

Randomizing structure layout

jreiser — Sun, 14 May 2017 23:49:03 +0000

debugging without debuginfo will remain precisely as painful as it always was. No, it will be harder. The mapping from source declaration to binary layout previously could be understood quickly; now it will require reverse engineering (inspecting machine instructions for offsets from pointers), and it may change from version to version.

Randomizing structure layout

johan — Sun, 14 May 2017 17:49:20 +0000

"The randstruct plugin is a new GCC add-on that lets the compiler randomize the layout of C structures."

Since it's a plugin I'm hoping that it has sane defaults so the randstruct plugin is disabled when specifying -g

Randomizing structure layout

mb — Sun, 14 May 2017 07:40:01 +0000

>structures consisting entirely of function pointers are automatically randomized.

How does this even help to improve security?
Even if I don't know the actual structure layout and thus don't know which pointer I'm going to overwrite, there's a good chance I could exploit it anyway. I would just have to try out each function call until I hit my overwritten one.
Someone will eventually call the pointer. Otherwise it would not be there in the structure. And if that happens my code will run.

Gentoo

linuxrocks123 — Sun, 14 May 2017 04:33:26 +0000

In addition to Facebook and Google, presumably anyone who runs Gentoo would benefit from this.

Debugging randomizing structure layout

nix — Sat, 13 May 2017 18:32:04 +0000

You can still do an eu-readelf --debug=info on the bit of the kernel containing the structure definition you're interested in and look at the debuginfo to see where the structure members are. (Yes, this is a drag.)

Randomizing snake-oil

NAR — Sat, 13 May 2017 18:04:05 +0000

"To my knowledge no one has yet demonstrated a system that can build operating systems that is sufficiently well defined as to allow proofs of correctness for anything interesting"

I remember 20 years ago someone mentioned to me that the VMS kernel (the OS running on VAX computers) was formally proven to be correct (to some degree). Of course, in that case DEC provided the hardware and the software too. Unfortunately I don't remember the details.

How much entropy is actually gained ?

zlynx — Sat, 13 May 2017 17:57:19 +0000

The biggest advantage to these things is that it tends to remove stealth from attacks. The system administrator should notice repeated kernel BUG outputs and/or system crashes caused by overwriting random struct fields.

With a perfect attack script, the administrator never notices anything wrong and the attack leaves no traces.

Once an attack is noticed, the machine can be turned into a honeypot with full network recording. On the next attack, you've then got the complete log of how it was done, and can find and patch the bug.

It's the difference between breaking into a building with a copied key or lockpicks, vs. breaking the glass and setting off the alarm.

How much entropy is actually gained ?

Nelson — Sat, 13 May 2017 14:21:45 +0000

How does the system maintain compatibility with anything? You clearly can't randomize the unions and structs that are used to read network packets. Nor could you do that to any structs that are used for device register access. You could randomize the structs that are part of the kernel API, but every application would have to be rebuilt with the knowledge of how they are randomized. You can really only safely do this to completely internal structures which doesn't seem as useful.

How much entropy is actually gained ?

aggelos — Sat, 13 May 2017 10:53:20 +0000

In the absence of any way to quantify the "security" "increase" by this kind of defense, how could one possibly decide whether they want to make this tradeoff or not? I mean, yah, if you can't afford any slowdown at all then sure, you probably want to set this option at least. In the absence of hard "fails to perform adequately"-situations though, this seems to be more of a CYA solution for the vendor, not the user. "Here's a choice that's impossible to make. Take a guess and it's not our fault for the users that get it wrong". There's really a continuum here (e.g. structures consisting only of function pointers are usually singletons, so you can "raise the bar" by blowing them up X% and fill them with booby-trap function pointers) and this applies to most other kinds of probabilistic defenses too.

Randomizing structure layout

tdz — Sat, 13 May 2017 08:23:47 +0000

Glad I'm not the poor soul who has to debug with this...

> When potential attackers do not know the layout of a structure, it becomes much harder for them to overwrite specific fields in those structures. Thus, the barrier to exploitation is raised significantly

There are 6 possible permutations for structures with 3 fields, 24 permutations for structures with 4 fields, and so one. With millions (billions?) of installed kernel binaries, this still leaves a good number of systems for each variant. And if the attacker knows distribution and version number, the structure layout is trivial to find out.

Contrary to reproducible builds

alison — Sat, 13 May 2017 05:53:33 +0000

"Reproducible builds" is another very popular topic in security. RB is more useful to distros due to the need to distribute the randomization string associated with struct randomization. I can't see why anyone with a public kernel build would go this route.

Debugging randomizing structure layout

vomlehn — Sat, 13 May 2017 00:58:05 +0000

I'm less than happy with this. I often dump out structure memory for, say 64 bytes or so, starting at some particular structure. Then I look at the source for the structure to see where various things are. This will make that impossible. I will instead have to specify each item individually, which means paying a lot more attention to the debugger and less to debugging.

Randomizing kernel structures layout - external modules compulation?

darwish — Sat, 13 May 2017 00:57:08 +0000

I do not understand how would this affect compiling external kernel modules?

If I compile a module with a statement "x->y", how would a compiler know the _right_ actual offset of y? Would the seed be saved somewhere statically in the system? (E.g. /lib/modules/kernel-version/random-seed)

And if the seed is stored somewhere globally readable, can't the exploit writer just use that? And if the seed is not globally readable, does that mean we will have to compile kernel modules using sudo / root access in the future?

How much entropy is actually gained ?

Lionel_Debroux — Fri, 12 May 2017 19:40:33 +0000

The version of RANDSTRUCT in grsecurity definitely aims at addressing at least your first concern, and possibly your second one as well. The Kconfig snippet corresponding to the GRKERNSEC_RANDSTRUCT_PERFORMANCE config option reads:
+config GRKERNSEC_RANDSTRUCT_PERFORMANCE
+ bool "Use cacheline-aware structure randomization"
+ depends on GRKERNSEC_RANDSTRUCT
+ default y if GRKERNSEC_CONFIG_PRIORITY_PERF
+ help
+ If you say Y here, the RANDSTRUCT randomization will make a best effort
+ at restricting randomization to cacheline-sized groups of elements. It
+ will further not randomize bitfields in structures. This reduces the
+ performance hit of RANDSTRUCT at the cost of weakened randomization.

Randomizing snake-oil

walters — Fri, 12 May 2017 18:40:04 +0000

https://sel4.systems/ is pretty interesting on this topic. That said, I thought Coccinelle was an intimidating but https://github.com/seL4/l4v/commit/df7693b687a5ad541d1bee... is totally unintelligible to me. (Why are there almost no comments?)

Randomizing structure layout

geert — Fri, 12 May 2017 15:57:13 +0000

It can be taken further:
- Generate random seed
- Feed seed to softcore generation for FPGA
- Feed seed to gcc toolchain build
- Build kernel and userland
Now I have a "secure" device using a "random" instruction set that nobody else knows about. Happy cracking ;-)

Randomizing snake-oil

ebiederm — Fri, 12 May 2017 14:07:14 +0000

Provably secure is pretty much a non-starter as it requires a full and accurate theory of everything, and a proof the hardware you run on meets it's specification. Short of that you will have assumptions that may be wrong somewhere in your approach.

That said it is possible to manage the assumptions and prove certain properties about code. Which could in principle could close many lines of attack. The kernel deliberately does not implement any turning machines not even with eBPF so the halting problem should not be an issue.

The practical problem and what most attacks today exploit is that to be able to reason soundly about logic or algorithms requires the abstractions you build those out of to be well defined. Currently C explicitly is not well defined with respect to memory management. When you add in devices that can perform DMA and are not restricted by an IOMMU (as a kernel must) there is an additional problem.

To my knowledge no one has yet demonstrated a system that can build operating systems that is sufficiently well defined as to allow proofs of correctness for anything interesting. Which unfortunately leaves proofs of correctness needing a proof of concept before anyone will believe in them.

Which is all to say people are adding kernel defenses some of the randomization because no one has been clever enough yet to think of something better.

Randomizing structure layout

NAR — Fri, 12 May 2017 13:14:20 +0000

Also a binary distro should be able to provide a package that builds a randomized kernel including all needed modules.

It might even work as long as the user doesn't need any third party binary only module. Might even work for enterprise distributors - when they need support, they already share a lot of possibly confidential information with support, so they might also share the random seed. If there is an actual bug in the kernel, they have to rebuild it anyway and use a different seed.

Randomizing structure layout

abradona — Fri, 12 May 2017 13:03:18 +0000

that's what I was thinking about too ;-)

Randomizing structure layout

MatejLach — Fri, 12 May 2017 12:49:47 +0000

I'd reckon it has something to do with there not being too many downsides of merging it in and it offering *some* additional obfuscation, even if not real *security* (in depth). So given that and Torvalds probably being encouraged by others + a nice headline about Linux security actually being *strengthened*, as opposed to breached again,, Torvalds probably went something like; "Alllriigt then...I'll merge, but I am under no illusions that this really solves anything...", but I am purely guessing there.

Randomizing structure layout

nix — Fri, 12 May 2017 12:41:07 +0000

It should be fine, I think -- the debuginfo GCC emits will contain appropriate offsets for all structure members post-randomization. (And debugging without debuginfo will remain precisely as painful as it always was.)

How much entropy is actually gained ?

deater — Fri, 12 May 2017 12:11:37 +0000

> While it's certainly a step in the right direction (better
> security with zero runtime cost

Has it been shown to have zero runtime cost?

What about structs that cross cachelines? Suddenly frequently accessed fields that are close together and have good cache behavior might be moved apart.

Or structs that used to be far apart might be moved together and cause false sharing which is a really hard performance issue to track down.

Randomizing structure layout

aggelos — Fri, 12 May 2017 09:02:44 +0000

Nevertheless, Torvalds is unimpressed by structure randomization, calling it security theater.

No argument here. Can anyone explain why this is going into the kernel then? Or why KASLR went into the kernel? As an uninformed observer, I have a bit of trouble understanding the acceptance criteria that Torvalds and the core kernel developers apply here.

How much entropy is actually gained ?

moltonel — Fri, 12 May 2017 09:00:45 +0000

While it's certainly a step in the right direction (better security with zero runtime cost, yeah !), I wonder if it'll be a big deterrent to exploit writers, who are used to working around randomization by trying many combinations. Is there some study that quantifies the gains ?

A 2-fields struct ought to give 1 bit of entropy, except if the exploit can still function when overwriting all fields instead of one. I suspect that randomization is also restricted to avoid padding bloat, so a 10-fields struct might not add 10 bits of entropy. Things get better when a exploit has to subvert multiple structs in a row, but I wonder of frequent that is ?

It's interesting to compare that to the efforts of the rust community which has also implemented field reordering (http://camlorn.net/posts/April%202017/rust-struct-field-r...). In their case the main goal is speed (reduce struct padding) rather than security (although adding a bit of randomization on top of that should be a comparatively small step), and it's opt-out rather than opt-in (when a struct is an interface to C code, basically).

Randomizing snake-oil

aggelos — Fri, 12 May 2017 08:56:21 +0000

Actually solving problems is not in the interest of most people in the security field. Randomized defenses which "raise the bar", only to be conclusively shown inadequate within a few months are very convenient that way. This is a pattern both in academia and the industry. By pursuing defenses which cannot be complete (if you allow arbitrary programmer expressivity, you're always confronted with the halting problem), you keep the arms race going. This is to the benefit of both defenders and attackers (keeps the funds flowing).

Not being totally cynical about this, as of course "raising the bar" now is a consideration for many production deployments. In my (perhaps poorly informed) opinion though, the allocation of funds is clearly not concerned with eventually having robust solutions, just with piling complexity on top of complexity (academia is pretty good at that) with no end in sight.

And yes, there's no way to have flawless programs. Logic errors aside, even in a memory safe language, the programmers can very well implement their own instruction set and have a memory safety violation in their binary code (which would only be data to the type system). This is not really in the same class of "fundamentally unworkable" as expecting a huge source base to be kept bug free (see the recent kernel quotes of the week). This line of thought is a total derailment IMHO.

Randomizing snake-oil

matthias — Fri, 12 May 2017 08:17:50 +0000

Focusing only on probabilistic defences is certainly not good. But I do not see this happening. It is just one defence among many.

Certainly it would be better to just have provably secure code. But as the kernel is several orders of magnitude too large for proving its correctness, there have to be other measures.

Also I do not see, where this makes the code harder to understand. This change takes the right way of hiding the added complexity in the compiler (to be precise in a plugin). The visible changes in code mostly come down to some hints, where randomization is allowed or not allowed.

For debug it is a bit different. However, with proper support in the debugger, this should be no problem. The debugger should be able to decode randomized structs, if it has the necessary seed.

Both approaches have long term effects. Static analysis can prevent some bugs (not all of them unless we restrict to non Turing complete languages). Randomization can prevent bugs being exploited. This includes bugs in newly added code. Which has more effect is hard to tell.

Randomizing structure layout

johill — Fri, 12 May 2017 07:48:04 +0000

I'm not sure you need that - you could have relocations for all struct references, given enough compiler support :-)

Randomizing snake-oil

nhippi — Fri, 12 May 2017 07:38:51 +0000

It is unfortunate security developers focus on probabilistic runtime defenses. The added complexity can easily become an attack surface itself. Making the code harder to understand and debug will inevitably create new bugs - some which will have security implications. I take working on better static checks (and integrating them into developer/maintainer workflow) would have better long term effect. But that of cause doesn't make nice bullet points to marketing brochures like "randomized structs" may make...

Randomizing structure layout

matthias — Fri, 12 May 2017 07:20:09 +0000

On my own systems, I did never run a distro provided kernel image, except for installation. When I started with Linux with a kernel from the 2.0.x series, it was quite common do compile the kernel even in binary distros. Having all hardware needed at boot inside the kernel (and not in modules) was common practice. Afterwards I changed to Gentoo, where even today it is quite common to build your own kernel.

Also a binary distro should be able to provide a package that builds a randomized kernel including all needed modules. This should not require the user to run make config, as the config would be provided by the distribution. Probably this would not be the default option, except maybe for distros that are specialized on security, but it could be an optional feature.