You have some file that has ownereship such that root can not access
the
file via permissions.
You need to turn on full auditing to get the path of the offending file.
Execute
auditctl -w /etc/shadow -p w
And see if you can generate the error again. Then you should get a path
with the next avc message.
As far as I know, for this to work I would need to have auditd running,
isn't that the case? As I pointed in my initial post, auditd cannot start!
OK, I can force permissive mode, then start auditd, switch back to
enforced mode and then execute auditctl. Then, may be, I could find the
offending path/files causing the issues with the other programs I have
listed in my logs, but how do I deal with the auditd itself? auditctl
requires auditd to be running in order to show the paths, isn't that not
the case?