After spending half a day trying to fix the Ubuntu images (which aren’t broken) I have eventually started debugging the host.
It’s a docker problem. Ubuntu makes use of syscalls for better key security, which Docker didn’t support yet. The solution is to update docker… or use nerdctl, runc or something similar.
Instead of apt getting the message that the syscalls aren’t supported, it gets the message that permission is denied, which results in the confusing error messages.
You could technically patch ubuntu to be less secure, and to work with older docker, but that is sadly not a long term solution.
This is the PR that fixes it in the Docker(/moby) project. Note that the problem may occur in other Docker images (or other software in Ubuntu) as well, since it is ultimately caused by a change in glibc that was incompatible with the default seccomp profile of Docker.