How to ensure file integrity cryptographically?

Question

Problem: I have a collection of files (source code for example) whose integrity has to be ensured. I don’t care if the files are corrupted (I can easily multiple backups). I just want to make sure that the files aren’t tempered.

Suppose I store the collection in a system which is now (possibly) compromised. In order to ensure that the files aren’t tempered, one thing I can do is to store the checksums (SHA256 for example) of the source code files in an external system. When the system is really compromised, I transfer the files (with a lot of care so that this may not become a security breach) into another system, and then verify the checksums. If the checksums match, the files are (most likely) safe.

However, this approach requires me to have a safe external system which stores the checksums. Worse still, the checksums may be tempered. If I can ensure that the checksums aren’t tempered, I can store all the files on that external system (assuming that space is not an issue) so that the files aren’t tempered.

Did I miss something important? Can I create a system which ensures file integrity? Alternatively, does a plain encryption of a collection of files suffice?

Answer 1

First of all: From a security perspective corrupt and tampered files are the same. Integrity is no longer given. Period. In both cases you need backups.

Checksums are a good approach. As you noticed, if the system storing your files is compromised, you need an external (this means trusted) system to ensure your security measures aren't undermined. Instead of using checksums on an external system, you can either sign the files and store the signature with them or use HMAC instead of plain SHA256. This ensures that an attacker cannot forge a signature/checksum if he/she makes changes to the files, so you notice any sort of tampering.

In both cases you only need to store one secret (private key or HMAC key) on an external machine. In addition, integrity checks can be performed from any machine having access to the secret (you don't need a list of checksums, as they can be stored with the files themselves).

There are several implementations of HMAC (or other key-based-hash-algorithms) and signature algorithms. What fits your needs best, depends on your environment.

Answer 2

A simple solution would be to store the checksums in a digitally signed file at the same location.

As long as you retain control of the private key used for signing, you can easily verify the integrity of the whole set of files without having any access to that key.

Something like this is trivial to implement with PGP.

Answer 3

If I understand the requirement correctly:

1. You have a collection of files in location A
2. You want to ensure the integrity of the files over time in location A
3. You have multiple backups of the files

The solution appears obvious to me, which suggest maybe I missed something in the requirements. But you already have the backups -- hence you already have the checksums (or can easily calculate them from the backups).

If location A were compromised, you don't need to take the files from location A anymore (and compare their checksums) -- just take the backups!

For example, I have a wordpress website (which is a collection of php files, image files and an .sql backup file). I backup the files everyday at 12am. If my site my compromised, or infected with malware, I simply restore from the backup.

As long as I have a reasonable history of backups (~30 days for example), I can always go back further in time then when the infection took place. For example, the attackers compromised by index.php file. I could go back and look at the file history over 30 days to figure out when that infection took place, and restore from the last known 'good' backup.

The issue in your initial question, was that you were trying to establish the integrity of files on a local system using only that local system.

Answer 4

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:

1. Have your files and your checksums on system or medium A.
2. 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.
3. 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.
4. 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.