I think what you are missing in the reasoning is the importance of redundancy. You say that if you need to rely on an external system or external media that you trust to store the checksums, then why not just store there the files and forget about integrity, since that system or medium will be trusted anyway? The thing is, you don't have to trust a system or a medium, but you have to trust the "redundancy", that is, the fact that it's less likely for data to be compromised at the same time on several different systems or media.
So what you have to do is this:
- Have your files and your checksums on system or medium A.
- Have your files and your checksums on other systems or media, B, C, D, etc. as backups, as many as you want. The more backups you have the more the redundancy and the higher the probability of detecting tampering. Note that you need to reduce the probability of all the data being compromised at the same time, so for example you could keep A and B in different places, etc.
- To check integrity on A, compute the checksums of all the files, and then do a
diff computed_checksums.txt stored_checksums.txt. If integrity is ok, diff should report no differences. Do the same for the other systems or media, B, C, etc.
- Now you just checked the integrity by simply trusting the checksums stored on the same system or media. But how can you make sure the checksums can be trusted? Easy: just compute the checksum of the checksums stored on A (like
sha256sum checksums_stored_on_A.txt), then do the same on B, C, etc. If the resulting checksum is the same, then it means that all the checksum files are the same. They can be trusted because you are trusting the fact that it's unlikely for them all to have been compromised in the same way in different systems or on different media. If one or more of the resulting checksums turn out to be different from the others, then of course you need to find out which backups are actually safe and which have been compromised.
A couple of notes:
Infected systems. This method is not guaranteed to work in theory if you are using an infected system to manage your files, connect external media, compute checksums, etc. The reason is that in theory an infected system cannot be trusted at all, so even the command
sha256sum could be compromised, or
cp, or bash in general, etc. To reduce the probability of issues related to an infected system, you could check the integrity on different systems, maybe even running different OS's, etc.
Verifying checksums. Why do I check the checksums using
diff computed_checksums.txt stored_checksums.txt, instead of
sha256sum -c stored_checksums.txt? It's because
sha256sum -c stored_checksums.txt will just check the files listed in
stored_checksums.txt, and won't make sure that every file in your backup has a corresponding checksum to check. In other words, if a malicious file is added to your backup, using
sha256sum -c stored_checksums.txt you will never know it. On the other hand, if you use my method with
diff, the added file will show up: it will be in the computed checksums, but not in the stored checksums.