Force pushed new version with @dnicolodi's point fixed.

I only skimmed the changes and nothing looked obviously terrible. I don't like suggesting rotations if they can just be done automagically when appropriate, but didn't spend enough time groking the changes to appreciate why it might make the most sense.

Force pushed new version, only changes are the suggested ones. PTAL.

Force pushed a new version, with (most) points addressed, see above. ptal.

Force pushed a new version with the suggested changes

I'm trying to wrap my head around how effective this mitigation is.
It works fine in the case of systemd-journal-remote. So for that alone, it seems worth merging.
OTOH, local mitigation does not seem to be effective.
A local user who has access to journal files can read the hash off the file and produce output that generates hash table collisions.
In the previous version of the PR, the max chain length was proportional to the table size, so that attacker would be able to make journald slow down significantly while doing O(n²) iteration on those chains.
In the latest version of the PR, max chain length is fixed to a constant, so the attacker can force journald to rotate files. This also creates a load, and in addition allows the attacker to flush log entries.
Note that rate limiting only helps a little bit here, because we allow many data fields in a single message. So in principle it should be fairly easy to generate a large number of collisions with just one or few journal entries.

It seems that the only real solution would be to not write the hash key at all until the file is closed. Any readers would have to read the whole file and figure out where objects are stored on their own. This also means that they key should not be based on the file id, but separate. Before the file is archived, the actual hash table could be written. To preserve operation on journald restarts, the "private" hash key and table could be stored in a sidecar file with no read permissions.

Good point.

I have another suggestion - just drop the check for hash chain length completely. Even with access to the file ID used to key the hash, an attacker will still have to redo the work of generating new colliding messages for every file rather than relying on a precomputed table. This consumes more resources than are used for inserting the colliding messages in the hash table.

Note that rate limiting only helps a little bit here, because we allow many data fields in a single message.

The field hash table is much smaller than the data hash table, which is desirable in the normal use case. Is there an attack vector here where a user logs many different fields to fill up the field hash table and trigger early rotation? (No need for any hash collision, just maxing out the hash table fill fraction.)

I'm trying to wrap my head around how effective this mitigation is.
It works fine in the case of systemd-journal-remote. So for that alone, it seems worth merging.
OTOH, local mitigation does not seem to be effective.
A local user who has access to journal files can read the hash off the file and produce output that generates hash table collisions.
In the previous version of the PR, the max chain length was proportional to the table size, so that attacker would be able to make journald slow down significantly while doing O(n²) iteration on those chains.
In the latest version of the PR, max chain length is fixed to a constant, so the attacker can force journald to rotate files. This also creates a load, and in addition allows the attacker to flush log entries.
Note that rate limiting only helps a little bit here, because we allow many data fields in a single message. So in principle it should be fairly easy to generate a large number of collisions with just one or few journal entries.

So I had been thinking about this, and I think we can address this later too, but I think this should be independent of this PR. I mean, let me underline this: remote DoS is really important to fix, local DoS sucks and is something to fix, but there are so many others (think dbus) that I don't think it's as pressing

Specifically, what I'd propose in the long run is that we split the IO part of journald into per-UID processes. i.e. journald collects all incoming messages as before, augments them with metadata, does ratelimiting, yadda, yadda but then instead of calling journal_file_append() directly to write the stuff we got into a file we do so out-of-process from a per-client-UID process that we either fork off or that systemd forks off for us, gets the ready-made data and just writes it to disk. This process would drop privs entirely (possibly even setresuid() to the client's UID), and there would be one instance for each client UID that recently wrote stuff. This would mean metadata collection (the stuff we need privs for) and the IO stuff would be split. it would also mean that clients that manage to trigger hash table collisions will slow their own logging down, but nothing else. i.e. they can shoot themselves in the foot without affecting anything else.

Such a change would wouldn't even affect our global ordering guarantees, since the separations between journal files and between process would be the same here, and all ordering guarantees and absences would be maintained 1:1.

And it wouldn't be a complex patch I figure, writing the iovec[] that makes up the entry to a socket instead of journal_file_append() is easy...

It seems that the only real solution would be to not write the hash key at all until the file is closed. Any readers would have to read the whole file and figure out where objects are stored on their own. This also means that they key should not be based on the file id, but separate. Before the file is archived, the actual hash table could be written. To preserve operation on journald restarts, the "private" hash key and table could be stored in a sidecar file with no read permissions.

Well, but that just means all access goes from O(1) to O(n), so you basically make the effect of the DoS the default, who is helped by that?

I think as long as people can only fuck their own user up the ability to trigger hash collisions is not a problem.

But all that is independent of this patch. The remote DoS should definitely be dealt with independently, and any protection on top of that against slowing down/DoSing other users can then come on top of that.

Note that right now we actually have a pretty effective DoS protection in place already: per-user ratelimiting. Hence what I propose above isn't even necessary to even make local behaviour safe. It's still a wise thing to do so, because ratelimiting is an optional feature, and even with very high limits we should try to not fall over.

OTOH, local mitigation does not seem to be effective.

Another point here is that "local" log messages do not always come from local users. One example is the SSH server which logs failed login attempts with a message that can be partially controlled by an attacker (with sufficient control to give hash table collisions). However, the remote attacker has no way of reading the file ID..

Force pushed a new version with the points @keszybz pointed out addressed, no other fixes...

(And no fix that adds per-UID journald writer processes, as dicussed, will work on that eventually though. Added to the TODO list in this PR, for now)

So I had been thinking about this, and I think we can address this later too, but I think this should be independent of this PR.
I mean, let me underline this: remote DoS is really important to fix, local DoS sucks and is something to fix

Agreed.

Well, but that just means all access goes from O(1) to O(n), so you basically make the effect of the DoS the default, who is helped by that?

journald stays O(1). Clients which follow the journal might become worse (but don't have to, if they do some hashing on their own side).

Note that right now we actually have a pretty effective DoS protection in place already: per-user ratelimiting. Hence what I propose above isn't even necessary to even make local behaviour safe. It's still a wise thing to do so, because ratelimiting is an optional feature, and even with very high limits we should try to not fall over.

Yep.

I made a quick re-review of the changed parts and everything lgtm.