On 2/28/23 12:39, Richard W.M. Jones wrote:
On Tue, Feb 28, 2023 at 12:24:04PM +0100, Laszlo Ersek wrote:
On 2/27/23 17:44, Richard W.M. Jones wrote:
On Mon, Feb 27, 2023 at 08:42:23AM -0600, Eric Blake wrote:
Or intentionally choose a hash that can be computed out-of-order, such as a Merkle Tree. But we'd need a standard setup for all parties to agree on how the hash is to be computed and checked, if it is going to be anything more than just a linear hash of the entire guest-visible contents.
Unfortunately I suspect that by far the easiest way for people who host images to compute checksums is to run 'shaXXXsum' on them or sign them with a GPG signature, rather than engaging in a novel hash function. Indeed that's what is happening now:
If the output is produced with unordered writes, but the complete output needs to be verified with a hash *chain*, that still allows for some level of asynchrony. The start of the hashing need not be delayed until after the end of output, only after the start of output.
For example, nbdcopy could maintain the highest offset up to which the output is contiguous, and on a separate thread, it could be hashing the output up to that offset.
Considering a gigantic output, as yet unassembled blocks could likely not be buffered in memory (that's why the writes are unordered in the first place!), so the hashing thread would have to re-read the output via NBD. Whether that would cause performance to improve or to deteriorate is undecided IMO. If the far end of the output network block device can accommodate a reader that is independent of the writers, then this level of overlap is beneficial. Otherwise, this extra reader thread would just add more thrashing, and we'd be better off with a separate read-through once writing is complete.
In my mind I'm wondering if there's any mathematical result that lets you combine each hash(block_i) into the final hash(block[1..N]) without needing to compute the hash of each block in order.
I've now checked: https://en.wikipedia.org/wiki/SHA-2 https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction https://en.wikipedia.org/wiki/One-way_compression_function#Construction_from... https://en.wikipedia.org/wiki/One-way_compression_function#Davies%E2%80%93Me... Consider the following order of steps: - precompute hash(block[n]), with some initial IV - throw away block[n] - wait until block[n-1] is processed, providing the actual IV for hashing block[n] - mix the new IV into hash(block[n]) without having access to block[n] If such a method existed, it would break the security (i.e., the original design) of the hash, IMO, as it would separate the IV from block[n]. In a way, it would make the "mix" and "concat" operators (of the underlying block cipher's chaining method) distributive. I believe then you could generate a bunch of *valid* hash(block[n]) values as a mere function of the IV, without having access to block[n]. You could perhaps use that for probing against other hash(block[m]) values, and maybe determine repeating patterns in the plaintext. I'm not a cryptographer so I can't exactly show what security property is broken by separating the IV from block[n].
(This is what blkhash solves, but unfortunately the output isn't compatible with standard hashes.)
Assuming blkhash is a Merkle Tree implementation, blkhash solves a different problem IMO. In your above notation, hash(block[1..N]) is a hash of the concatenated plaintext blocks, and that's not what a Merkle Tree describes. The "mix" and "concat" operators remain non-distributive; it's the operator trees that differ. With a Merkle Tree, there are sub-trees that can be evaluated independently of each other. With SHA256, we have a fully imbalanced operator tree, one where the tree depth is maximal. Laszlo