On Thu, 17 Feb 2005 23:28:09 -0500, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > On the flip side, hash functions like MD5 or the SHA family are fairly > bulletproof, > but are essentially impossible to develop an incremental update for (if there > existed a fast incremental update for the hash function, that would imply a > very low preimage resistance, rendering it useless as a cryptographic hash).
Tree hashes. Divide the file into blocks of N bytes. Compute size/N hashes. Group hashes into pairs. Compute N/2 N' hashes, this is fast because hashes are small. Group N' hashes into pairs compute N'/2 N'' hashes etc.. Reduce to a single hash. A number of useful tradeoffs are possible: By enlarging N you improve the strength along various cryptographic dimensions. By changing the fanout, and deciding how many N your store, which N you store, which N' you store, etc you decide how easy it is to update the hash and you decide what the smallest increment you can test is... you trade off storage (and a little computation) for this ease. > Also, there's another issue - unlike standard ECC codes that can actually > *fix* > the problem (for at least small number of bit errors), it's unclear what you > should > do if you find a mismatch between the hash of a block and the block contents, > as > you don't know whether it's the actual data or the hash that's corrupted.... In my initial suggestion I offered that hashes could be verified by a userspace daemon, or by fsck (since it's an expensive operation)... Such policy could be controlled in the daemon. In most cases I'd like it to make the file inaccessible until I go and fix it by hand. It would also be useful to have the checker daemon watch the logs (or recieve notifications through some kernel interface)... and any block level errors (or smartd errors) backprojected up (through raid and lvm remappings) to the file system level ... After identifying the potentially corrupted file, it could then test the file. If the file has been corrupted, the configured action is taken. If this policy is in userspace, the level of action sopication could be very high: for example, if I was on a distribution with package management, and the file was outside of /home, and the package flags didn't indicate it was a config file.. then go fetch the package, and replace the file and send me an email so I don't forget how wonderful my OS is. :)
