4 ms·

RFC 7574 Merkle tree solves that rather strictly (I am the author of the scheme). Max file size is 2^64 bits, so the hash tree is defined as a binary tree cove

RFC 7574 Merkle tree solves that rather strictly (I am the author of the scheme). Max file size is 2^64 bits, so the hash tree is defined as a binary tree covering the entire 2^64 range, leaf layer made of 1KB pieces. A hash of an empty range is defined to be 0, at any level. That way, each hash is reliably fixed to its interval ("bin"). There are some features derived from that. For example, you can prove file size by showing a logarithmic number of hashes. A file is identified by its root hash (covering the entire 2^64 range), no additional metadata needed. And so on. These days, the 7574 scheme is used in the DAT protocol.

KMag 9y ago
Having an RFC is better than nothing, and I don't see any obvious vulnerabilities in your scheme. I've posted several places about being able to take the hash of the rightmost chunk and log(N) other hashes as a compact proof of file length for a hash tree root. (Including, I think, the posts I had arguing with the IPFS folks about using BEP 30 Merlke Trees.) That's handy, but there's nothing novel about RFC 7574 there. However, 2^64 bits is a bit of an arbitrary limit. What's the justification there? SHA-512 and SHA-384 support up to 2^128-1 bits, and SHA-3 doesn't have such a limit. More importantly, I don't recognize the names of the RFC authors from any cryptographic analysis. There's a big difference between a scheme that looks pretty good to a ton of random people who have looked at it and a scheme designed and published by world-famous cryptographers. Has your custom tree construct undergone formal review by qualified cryptographers? It looks pretty good to me, but if I had to bet by career on the security of a tree hash scheme, I'd prefer to go with the people who brought us Keccak/SHA-3 (and one of the people who brought us AES, despite its known weaknesses).
- gritzko 9y ago
  1. 7574 is not "novel" indeed. About 10 years old, if you count the original draft. 2. 2^64 is quite a lot, for a single file. The variant I described deals with a single static file. Also, it is a part of a network protocol, so there are some requirements. Like, using standard integer arithmetics for packet-level processing. 3. Feel free to show it to any people you like.
DrJosiah 9y ago
Looking at 7574 and Bittorrent's BEP 30, unless I'm missing something, the only part that is resisting the attack mentioned in the source article and what you are replying to, comes from also specifying the total length of the data hashed, along with the block size. So you're getting the root hash, total size, and leaf block sizes - it's that secondary information that is necessary to prevent the imaging attacks mentioned in the source article and what you are replying to. With a better construction (Sakura, ...), that total and block size information are unnecessary. I wonder if any almost-compliant RFC 7574 or BEP 30 tools accidentally ignore those other sizes.

KMag 9y ago

Having an RFC is better than nothing, and I don't see any obvious vulnerabilities in your scheme. I've posted several places about being able to take the hash of the rightmost chunk and log(N) other hashes as a compact proof of file length for a hash tree root. (Including, I think, the posts I had arguing with the IPFS folks about using BEP 30 Merlke Trees.) That's handy, but there's nothing novel about RFC 7574 there. However, 2^64 bits is a bit of an arbitrary limit. What's the justification there? SHA-512 and SHA-384 support up to 2^128-1 bits, and SHA-3 doesn't have such a limit. More importantly, I don't recognize the names of the RFC authors from any cryptographic analysis. There's a big difference between a scheme that looks pretty good to a ton of random people who have looked at it and a scheme designed and published by world-famous cryptographers. Has your custom tree construct undergone formal review by qualified cryptographers? It looks pretty good to me, but if I had to bet by career on the security of a tree hash scheme, I'd prefer to go with the people who brought us Keccak/SHA-3 (and one of the people who brought us AES, despite its known weaknesses).

gritzko 9y ago
1. 7574 is not "novel" indeed. About 10 years old, if you count the original draft. 2. 2^64 is quite a lot, for a single file. The variant I described deals with a single static file. Also, it is a part of a network protocol, so there are some requirements. Like, using standard integer arithmetics for packet-level processing. 3. Feel free to show it to any people you like.

DrJosiah 9y ago

Looking at 7574 and Bittorrent's BEP 30, unless I'm missing something, the only part that is resisting the attack mentioned in the source article and what you are replying to, comes from also specifying the total length of the data hashed, along with the block size. So you're getting the root hash, total size, and leaf block sizes - it's that secondary information that is necessary to prevent the imaging attacks mentioned in the source article and what you are replying to. With a better construction (Sakura, ...), that total and block size information are unnecessary. I wonder if any almost-compliant RFC 7574 or BEP 30 tools accidentally ignore those other sizes.