Fun with Gentoo: Why don't we just shuffle those ROP gadgets away?

First, it does. At scale, the probability of everyone running the exact version of every piece of software is 0. If you want, go take a look and see how many users are running a given version of Android.

Also, did you miss when I wrote

> Taking this a step further, create link N randomly sorted copies per version and randomly distribute those

I agree, doing it per version is only just a small amount of coverage. We're in agreement that generating N randomized copies and distributing those evenly is a stronger position because it makes the cost MN where you have M releases that are still running and N variants per release.

I wonder if there's a way to do just-in-time random relinking such that the performance cost is low, but the security benefit is still strong.

Just-in-time gets you reproducible builds, and also addresses the "local attackers who can read the binary or library" problem.

There would be a performance cost in terms of startup time, but since the number of possible permutations is a factorial function of the number of possible linking orders, it seems like even a very coarse-grained random relinking can go a long way.

You could accomplish this by doing static analysis of a binary to generate a file full of hints for ways to rewrite the binary such that its behavior is provably equivalent to the original. Then there could be a wrapper (perhaps at the shell or OS level) which uses the hints to randomly relink on the fly just prior to execution.

Another advantage is that this approach should be feasible on an OS like Ubuntu where everything is precompiled.

However the static analysis part could be a little tricky? I'm not familiar with the state of the art in static analysis of compiled binaries.

Performance-sensitive users could be given a way to turn the feature off, in cases where fast startup time was more important than security.

There are all kinds of things we're doing (e.g. rewriting things in memory-safe languages) to make it less likely for an attacker to become able to control a jump to somewhere, however, we don't expect to fully succeed any time soon, and this is defense in depth against cases when attackers once again do find a way to control transfer to some arbitrary gadget.