linux-kernel - Missing cache considerations in randstruct performance feature

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <f3ca77f0-e414-4065-83a5-ae4c4d25545d@student.tuwien.ac.at>
Date:   Sat, 7 Oct 2023 00:30:01 +0200
From:   Lukas Loidolt <e1634039@...dent.tuwien.ac.at>
To:     keescook@...omium.org, linux-hardening@...r.kernel.org
Cc:     linux-kernel@...r.kernel.org,
        Daniel Marth <daniel.marth@...o.tuwien.ac.at>
Subject: Missing cache considerations in randstruct performance feature

Hello!

I have been looking into the implementation of the "randstruct" 
gcc-plugin and noticed a potential bug in its performance version, which 
is supposed to limit randomization to cache-line sized groupings of 
structure members.
I haven't been able to find too much documentation on this version of 
randstruct, but my general understanding of its intended behavior is as 
follows:

- in performance mode, randstruct groups structure members into cache 
line sized partitions of 64 bytes each
- the order of these partitions is randomized
- the order of structure members within each partition is also randomized

In my tests, however, the performance version behaves more or less like 
the full version of randstruct.
For example, testing on a struct of 10 function pointers:

struct test_struct{
     void (*func1)(void);
     void (*func2)(void);
     void (*func3)(void);
     void (*func4)(void);
     void (*func5)(void);
     void (*func6)(void);
     void (*func7)(void);
     void (*func8)(void);
     void (*func9)(void);
     void (*func10)(void);
};

resulted in the following randomized memory layout:

func3 (offset 0)
func5 (offset 8)
func10 (offset 16)
func2 (offset 24)
func1 (offset 32)
func6 (offset 40)
func8 (offset 48)
func7 (offset 56)
func9 (offset 64)
func4 (offset 72)

I would have expected cache-line sized partitions of (up to) 8 pointers, 
so that func1 through func8 are adjacent in the final layout, but these 
partitions are seemingly not preserved.
Assuming that this is indeed not the intended behavior, the culprit is 
line 213 in "randomize_layout_plugin.c"
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/scripts/gcc-plugins/randomize_layout_plugin.c?id=f291209eca5eba0b4704fa0832af57b12dbc1a02#n213

where

randnum = ranval(prng_state) % (i + 1);

should probably be something like

randnum = size_group[x].start + ranval(prng_state) % size_group[x].length;

After changing this line, cache-line sized partitions are created and 
preserved as expected.
However, while structure members within each partition are randomized, 
the order of the partitions themselves is not randomized and remains the 
same as in the original struct declaration.
I assume that the for loop in lines 200 to 206 is intended to shuffle 
the partition_group structures

for (i = num_groups - 1; i > 0; i--) {
         struct partition_group tmp;
         randnum = ranval(prng_state) % (i + 1);
         tmp = size_group[i];
         size_group[i] = size_group[randnum];
         size_group[randnum] = tmp;
}

but the order of the partition_group structs is not written back into 
the newtree object, so the randomization from this loop is not reflected 
in the final layout.
I would be interested to know if this is an actual issue with the 
implementation or if I'm misinterpreting how randstruct is supposed to 
work here.

Thanks,
Lukas Loidolt