5 ms·

It seems that the authors have decent ideas, but don't have much experience with the subject matter. If you look at the assigned identifiers in the binary sche

by KMag 11y ago

It seems that the authors have decent ideas, but don't have much experience with the subject matter. If you look at the assigned identifiers in the binary scheme, the authors believe that 32-bit truncated cryptographic hash functions are useful. 64-bit truncated cryptographic hash functions are essentially useless from a security standpoint, so the 32- and 64-bit variants would be better served by CRC-32C and CRC-64ECMA. If your standard contains a 64-bit truncated cryptographic hash, people without subject matter expertise will assume that it provides more than a modicum of security. Also, the authors apparently vastly underestimate the utility of using Merkle trees. I used to be an engineer for LimeWire. Gnutella used SHA-1 as identifiers for the content. Unfortunately, this means only being able to integrity-check an entire large file instead of small pieces, or having to get a Merkle tree root out-of-band. LimeWire just got the Merkle tree root (plus one row of the tree) from the first peer it contacted for download data. This represents a simple denial-of-service poisoning attack where the attacker hands out Merkle trees corresponding to something like 10% of the blocks being corrupted. The clients would then repeatedly request the "corrupted" blocks from peers, until giving up, notifying the user that the download was corrupted, and most likely keeping around a file that had sections that weren't integrity checked. (Corruption really does happen. The TCP checksum is rather weak.) If they had used the Merkle tree root as the file identifier instead, then there would be no opportunity to trick the client into incorrectly associating the wrong Merkle tree with a given file. If you're going to define a hash URI scheme, please incorporate Sakura trees (a provably secure hash tree scheme) of degree 2 with a fixed leaf block size. Leaving the block size variable leads to the Bittorrent problem where a single set of identical files has multiple identifiers and clients using hashing at one granularity can't share information with clients using hashing at another granularity. Merkle trees with a single standard leaf block size allow different levels of the tree to be shared to in effect give different granularities, without dividing resources due to the multiple identifier problem. Also, in the case where there are 2^N + 1 blocks (or any other case where you'd be tempted to "optimize" by skipping a node at that level), please have a re-hashing node at each level for all blocks. This means that the final block (along with at most one extra hash per tree level) constitutes a cryptographic proof of the file length corresponding to the tree root. Otherwise, in order to avoid certain denial of service attacks, you also need to always put the length of the file as part of the URI, or the first client needs to send the entire bottom row of the Sakura tree. Note that the Bittorrent Merkle tree format is broken in the same way that the original Gnutella tiger tree proposal was broken (fixed before implementation in the Gnutella case). Use Sakura trees. They're provably as secure as the hash function you use.

davidp 11y ago
If you look at the assigned identifiers in the binary scheme, the authors believe that 32-bit truncated cryptographic hash functions are useful. No they don't. From Section 2: The sha-256 algorithm as specified in [SHA-256] is mandatory to implement; that is, implementations MUST be able to generate/send and to accept/process names based on a sha-256 hash. However, implementations MAY support additional hash algorithms and MAY use those for specific names, for example, in a constrained environment where sha-256 is non-optimal or where truncated names are needed to fit into corresponding protocols (when a higher collision probability can be tolerated). Truncated hashes MAY be supported. When a hash value is truncated, the name MUST indicate this. Therefore, we use different hash algorithm strings in these cases, such as sha-256-32 for a 32-bit truncation of a sha-256 output. A 32-bit truncated hash is essentially useless for security in almost all cases but might be useful for naming. With current best practices [RFC3766], very few, if any, applications making use of names with less than 100-bit hashes will have useful security properties.
- btrask 11y ago
  32-bit hashes are not useful for content addressing pretty much at all. If you look at the table here: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table https://en.wikipedia.org/wiki/Birthday_problem#Probability_t... (50% chance of collision with only 77,000 resources) See also: https://lkml.org/lkml/2010/10/28/287 https://lkml.org/lkml/2010/10/28/287 where Linus Torvalds says 12 hex digits (96 bits) is pretty much the minimum short-hash for the Linux kernel commit history. Extremely short hashes can be useful briefly for manually transcribing between devices, as long as you immediately "resolve" them back into a longer form, before new collisions can happen. But this is more on par with clicking "I'm feeling lucky" than creating a link. :)
  - batbomb 11y ago
    I came here to talk about this. I deal with data management for a bunch of physics and astronomy experiments it's quite typical to have many millions of files for any given experiment (say, 1PB of storage for a medium size experiment, 10 million 100MB files). CERN's experiments would easily have billions of files, so I was thinking 64 bits would be a minimal truncation, but 96 is probably more reasonable.

by KMag 11y ago

davidp 11y ago

If you look at the assigned identifiers in the binary scheme, the authors believe that 32-bit truncated cryptographic hash functions are useful. No they don't. From Section 2: The sha-256 algorithm as specified in [SHA-256] is mandatory to implement; that is, implementations MUST be able to generate/send and to accept/process names based on a sha-256 hash. However, implementations MAY support additional hash algorithms and MAY use those for specific names, for example, in a constrained environment where sha-256 is non-optimal or where truncated names are needed to fit into corresponding protocols (when a higher collision probability can be tolerated). Truncated hashes MAY be supported. When a hash value is truncated, the name MUST indicate this. Therefore, we use different hash algorithm strings in these cases, such as sha-256-32 for a 32-bit truncation of a sha-256 output. A 32-bit truncated hash is essentially useless for security in almost all cases but might be useful for naming. With current best practices [RFC3766], very few, if any, applications making use of names with less than 100-bit hashes will have useful security properties.

btrask 11y ago
32-bit hashes are not useful for content addressing pretty much at all. If you look at the table here: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table https://en.wikipedia.org/wiki/Birthday_problem#Probability_t... (50% chance of collision with only 77,000 resources) See also: https://lkml.org/lkml/2010/10/28/287 https://lkml.org/lkml/2010/10/28/287 where Linus Torvalds says 12 hex digits (96 bits) is pretty much the minimum short-hash for the Linux kernel commit history. Extremely short hashes can be useful briefly for manually transcribing between devices, as long as you immediately "resolve" them back into a longer form, before new collisions can happen. But this is more on par with clicking "I'm feeling lucky" than creating a link. :)
- batbomb 11y ago
  I came here to talk about this. I deal with data management for a bunch of physics and astronomy experiments it's quite typical to have many millions of files for any given experiment (say, 1PB of storage for a medium size experiment, 10 million 100MB files). CERN's experiments would easily have billions of files, so I was thinking 64 bits would be a minimal truncation, but 96 is probably more reasonable.