Re: two potential randstruct improvements

Re: two potential randstruct improvements

[Kees Cook]

On Mon, Mar 29, 2021 at 09:26:35AM +0200, Jann Horn wrote:
> 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.)

Yup, it would be a nice improvement. It would need some work to reorganize
the shuffler, which doesn't have a way to insert fields currently. It
can sort of calculate padding (see partition_struct()), but that likely
needs improvement too.

Patches welcome! I've opened an issue for this:
https://github.com/KSPP/linux/issues/122

> === 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.

Since the RNG runs on every compilation unit on every randomized
structure, any performance hit from swapping the RNG could be large.
That said, folks using randstruct likely don't care. :)

This looks easier to do than the former idea, though. Again, patches
welcome! Issue captured at: https://github.com/KSPP/linux/issues/123

-Kees

-- 
Kees Cook