2
$\begingroup$

As a preface, I have to say that I am a noob in this area. Having said that, I will ask the question.

I have a situation where I need to validate and protect against tampering a handful of large binary files (~1GB each with ~10GB total) distributed on an embedded system (think Android Tablet). These original files will have a need to have a hash which can ensure that the files have not been tampered with.

Now, the challenge is that these files can be updated with a patch periodically downloaded from a webserver. These patch files will also be distributed with a hash which will ensure that the patch is authentic. (The files will be downloaded over a secure connection.)

Finally the patch needs to be applied to the original files on the embedded system which will then result in the need to regenerate the hash for the newly patched files so that they can be subsequently verified in the future.

There are several challenges:

  • Since these are large files running in an embedded system, the 'recommended' algorithms for hashing like SHA256 may prove to be too expensive to compute at runtime on a mid-range embedded system. The back of the napkin calculation says that may take upwards of several minutes to compute. Since this verification must occur every time an application launched to read this data, it must be very fast for 10GBs of data - less than 5 seconds.
  • Since the patch is being applied on the embedded system, the actual hash for the newly patched file must be computed on the embedded system itself.

My idea:

I was thinking that we could simply compute a faster, "weak" hash (like MD5) on the large files first. Then I would make a server request (with mutual auth) to encrypt the MD5 hash with a private key and return an encrypted hash to the embedded system. Then whenever I want to verify the file integrity, I would use the public key to decrypt the encrypted hash and then verify the hash against the actual files.

Any thoughts on this approach? Does my idea work?

Thanks for your thoughts.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ It would probably be better to sign "the MD5 hash with a private key and return" a signed "hash to the embedded system", rather than trying to use encryption for that purpose. $\;$ $\endgroup$
    – user991
    Commented Oct 24, 2014 at 23:19
  • $\begingroup$ You want to hash at 2GB/s.. on an embedded system? MD5 is a quarter that speed on a 3GHz xeon. BLAKE2b is your fastest option. It may be prudent to validate the files only when they need to be accessed. $\endgroup$
    – Richie Frame
    Commented Oct 24, 2014 at 23:32
  • 1
    $\begingroup$ BLAKE2b on 64-bit ARM can operate at 164MB/s per GHz, which is a max of 410MB/s on a top end quad core unit @ 2.5GHz. Reducing the hash to 6 rounds will up that to 680MB/s and probably still be secure. $\endgroup$
    – Richie Frame
    Commented Oct 24, 2014 at 23:53
  • 2
    $\begingroup$ Also, how fast is the read speed of the storage device? sequential reads on those things usually tops out at 150MB/s, thats over a minute just to read the file from storage for verification $\endgroup$
    – Richie Frame
    Commented Oct 25, 2014 at 3:38
  • $\begingroup$ Richie, thanks for your comments. I want to make sure I was clear - my intent was to first compute a MD5 hash on the embedded system. I would then send this MD5 hash on the embedded system and then send it to a secure server to then digitally sign the MD5 hash with a private key. The public key on the embedded system can then verify the MD5. This would allow for the embedded system to verify the MD5 without requiring a connection to the secure server. $\endgroup$
    – McMurrich
    Commented Oct 27, 2014 at 17:34

2 Answers 2

Reset to default
1
$\begingroup$

You can make incremental changes that only touch small pieces of the file faster, at a cost in complexity.

Multiple hashes can help with that. Rather than a single hash value, you can amortise the cost of computation by storing multiple hashes. If you hash the large file in pieces, then you can create a single hash that covers the entire file by hashing all the resulting hashes, which should be quick.

Then you only have to calculate the hashes over the chunks that the patch touches, plus a final pass to combine them all.

This effectively splits the big file into many. The main consequences is that if the patch alters the size of chunks, the chunk boundaries have to move too. That means that you have to maintain the chunk boundaries too, so what you store is a list of offsets and hashes. And you'll have to be careful about applying the patch across a boundary. That makes cumulative patches tricky to get right.

As long as the hash reported with the patch (you'll want to authenticate this somehow) has the same understanding of the chunk boundaries, then you are ok. You could include the boundaries with the patch itself.

Don't use md5 if you care about preventing tampering, its collision resistance is miserable. SHA-2 is plenty fast if you don't have to run it over your entire data set all the time.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ delta updates will not help him if he needs to verify the entire file everytime the application is launched, but it will definitely make updating the program faster $\endgroup$
    – Richie Frame
    Commented Oct 25, 2014 at 3:39
  • $\begingroup$ You might avoid the need to check every time if you can be sure that the file hasn't been tampered with since you last checked. That's a fairly common assumption. $\endgroup$
    – Martin Thomson
    Commented Oct 26, 2014 at 22:09
  • $\begingroup$ Thanks for the suggestions. My understanding is as follows: Consider using multiple hashes for fixed block sizes. When applying updates, just re-calculate the hashes for those blocks that have been impacted with the update. Have a hash for the collection of hashes to verify the entire large file hasn't changed. Now, everytime the data is loaded, then just verify the hash of hashes to ensure the file hasn't been tampered with. Did I get that right? $\endgroup$
    – McMurrich
    Commented Oct 27, 2014 at 17:47
  • $\begingroup$ Yep. The only caveat there is if your patches adjust the size of a block. If you want to continue using the hashes for other blocks, you will have to track how that change affects the block boundaries. $\endgroup$
    – Martin Thomson
    Commented Oct 29, 2014 at 3:28
  • $\begingroup$ @McMurrich: what you described in above comment is a simple hash tree. As pointed by Richie Frame, it will not detect alteration of a block that was not supposed to have changed, but did (with no change of the stored hash, remaining at its former, original value, no longer matching the file content). I can't tell if that's a problem in your threat model: on one hand you trust the embedded system (when it accesses the data and compute hashes), and on the other you do not (when it comes to not changing this data). $\endgroup$
    – fgrieu ♦
    Commented Nov 24, 2014 at 5:34
0
$\begingroup$

Your idea does not seem to provide any security benefit. If an attacker was able to modify the data while preserving the MD5 hash, your encrypted MD5 hash would also stay the same.

One practicable aproach would be to simply use MD5 hashing. To tamper with the data without changing the hash, an attacker has to perform what’s called a second-preimage attack which is much more difficult than a collision attack and to the present day still computationally infeasible for MD5 (see Is MD5 second-preimage resistant when used only on FIXED length messages? ).

Alternatively you could use a modern fast cryptographic hash function such as SHA3-finalists Skein or BLAKE.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I believe you are saying that the MD5 hash has an inherent weakness that the same MD5 hash can be kept consistent even though the data changes. And if it's possible for a malicious attack to do this, a digital signature would have no additional benefit. $\endgroup$
    – McMurrich
    Commented Oct 27, 2014 at 17:42
  • $\begingroup$ It sounds like what your are suggesting is that if I were to use MD5 over fixed blocks of data size, then there may be sufficient security to leverage MD5 in that fashion. $\endgroup$
    – McMurrich
    Commented Oct 27, 2014 at 17:45
  • $\begingroup$ Yes. As I understand you want to ensure correctness of your data by storing a hash but are worried about SHA2's worse performance vs. MD5's worse security. My answer is that 1) MD5 is probably secure enough 2) you could instead use Skein or BLAKE. I did not care about the possibility of an attacker simply changing the stored hash which did not seem to be your concern. $\endgroup$
    – wonce
    Commented Oct 27, 2014 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.