two potential randstruct improvements

[Jann Horn <jannh@google.com>]

Hi!

I'm currently in the middle of writing a blogpost on some Linux kernel
stuff; while working on that I looked at the randstruct version in
Linus' tree a bit and noticed two potential areas for improvement. I
have no idea whether any of this (still) applies to the PaX/grsecurity
version, but since the code originates from there, I figured I should
also send this to the original authors.


=== no explicit randomization of padding holes ===
The randstruct plugin works by shuffling the list of C struct members.
So if you have a struct like this:

struct foo { u32 a; /*4-byte hole*/ u64 b; u64 c; };

randstruct might rearrange it into one of the following layouts:

struct foo { u32 a; /*4-byte hole*/ u64 b; u64 c; };
struct foo { u32 a; /*4-byte hole*/ u64 c; u64 b; };
struct foo { u64 b; u32 a; /*4-byte hole*/ u64 c; };
struct foo { u64 b; u64 c; u32 a; /*4-byte hole*/ };
struct foo { u64 c; u32 a; /*4-byte hole*/ u64 b; };
struct foo { u64 c; u64 b; u32 a; /*4-byte hole*/ };

So if there is only a single 4-byte member among multiple 8-byte
members, the 4-byte member "a" will still always be 8-byte aligned;
and if there is a small number of 4-byte members among lots of 8-byte
members, it'll probably still end up that way. This means that if an
attacker e.g. manages to type-confuse "struct foo" and an array of
pointers on a little-endian system, they'll be able to use arithmetic
operations on "a" to shift one of the pointers in "a" up and down.
This wouldn't be possible if, after the existing randomization, struct
members with following padding holes were explicitly randomized with
regard to the padding (subject to alignment constraints, of course).
(In practice I guess that might be implemented in the existing
randstruct plugin by computing padding holes after elements and then
randomly inserting dummy members in front of those members, with
dummy_size%member_alignment==0 and dummy_size<=padding_size.)

(Yes, I realize that this becomes less interesting if you have a
different mitigation that makes type confusion between single-struct
allocations and arrays harder.)


=== non-cryptographic RNG used for randomization ===
I haven't looked at this in detail; but randstruct uses a
non-cryptographic RNG
(http://burtleburtle.net/bob/rand/smallprng.html) to derive randomized
structs from a 256-bit seed. In theory, this means that an attacker
with knowledge of at least 256 bits worth of information about
structure layouts in a given build _may_ be able to recover the seed,
and from there, the layouts of all other structs.

It might be possible to indirectly determine some amount of
information on structure layouts through various side channels; for
example:

 - cacheline grouping might change if performance-mode is disabled,
   which might be measurable through false sharing effects
 - function sizes might change slightly because the encoding of an access
   to the first element is shorter, which might be measurable e.g. through
   icache and branch predictor state

I don't know whether the amount of information leakage would be enough
to actually determine the seed - and I'm not a cryptographer, I have
no clue how much output from the RNG you'd actually need to recover
the seed (and an attacker would not even be getting raw RNG output,
but RNG output after additional modulo operations). But if the goal
here is to ensure that an attacker without access to the binary kernel
image can't determine struct layouts without a proper leak primitive,
even if they know exactly from which sources and with what
configuration the kernel was built, then I think this needs a
cryptographically secure RNG.