4 ms·

This seems like it would be vulnerable to accidental or malicious hash collision generation. You need a hash plus some "authorized mirrors list" or some other

by hakfoo 5y ago

This seems like it would be vulnerable to accidental or malicious hash collision generation. You need a hash plus some "authorized mirrors list" or some other anti-poisoning measure. Not sure offhand how BitTorrent does it.

telotortium 5y ago
Unless you are using an older hash function that doesn't have sufficient collision or preimage resistance, that should not be an issue, because finding 2 files that hash to the same output is infeasible. It does point to the need to be able to upgrade the hash function in your protocol at some point, and preferably associate a set of hashes generated by different hash functions to the same file contents.
derefr 5y ago
Any hash algorithm for which a single collision has ever been generated would be an inappropriate choice for a URN system. Re: malicious collisions, any modern hash algorithm currently in wide use, if "broken" by some kind of vulnerability, would cause far worse problems for the world than just some URN system breaking down. As such, literal man-millenia of cryptanalysis has gone into ensuring that there are no vulnerabilities in popular algorithms. Re: accidental collisions, please note that 128 bits of entropy (i.e. a UUID) is already enough to ensure no accidental collisions before the heat-death of the universe. And most modern hashes have ≥256-bit residues.
- ltbarcly3 5y ago
  FYI UUIDs are 128bits but only have 122 bits of entropy. Still not going to get a collision with a good implementation.
  - api 5y ago
    UUIDs are long enough but are not cryptographic hashes. They can be deliberately collided pretty easily. A cryptographic hash like sha384 or blake2 makes it infeasible to come up with any input that would ever yield the same output. That’s what you would use for such a network.
    - derefr 5y ago
      You're thinking of UUIDv1s, which pretty much nobody uses. UUIDv4s — the ones that are specified as being populated with 122 bits entropy from a HWRNG — cannot "be collided pretty easily." Those are what anyone clearly means if they're talking about "bits of entropy" in relation to UUIDs. (Also, as it happens, UUIDv3s and UUIDv5s are specified as having their payload bits populated with the cryptographic hash of a user-defined input. But just to muddle your point further, the cryptographic hashing algorithms used in v3 and v5 are not ones that you'd trust today for collision-resistance; MD5 [v3] and SHA1 [v5] have both had at least one collision attack successfully done against them.)
      - ltbarcly3 5y ago
        Also, the concern needs to be around 'accidental' collisions of the same uuid within the same logical namespace. For example, generating the same UUID as a key for two rows in the same table. Even with weak non-v4 uuids, this is extremely unlikely with any dataset you are likely to be working with, just because even the worst UUID versions still have a fair amount of entropy, so population sizes have to be absurdly large to get even a tiny probability of a collision. UUID's are not meant to be 'secret' or 'hard to guess', and implementations can not be relied on to take care in generating the right kind of random state to ensure they aren't predictable. From the RFC: https://datatracker.ietf.org/doc/html/rfc4122 https://datatracker.ietf.org/doc/html/rfc4122 Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example. A predictable random number source will exacerbate the situation.

by hakfoo 5y ago

telotortium 5y ago

Unless you are using an older hash function that doesn't have sufficient collision or preimage resistance, that should not be an issue, because finding 2 files that hash to the same output is infeasible. It does point to the need to be able to upgrade the hash function in your protocol at some point, and preferably associate a set of hashes generated by different hash functions to the same file contents.

derefr 5y ago

Any hash algorithm for which a single collision has ever been generated would be an inappropriate choice for a URN system. Re: malicious collisions, any modern hash algorithm currently in wide use, if "broken" by some kind of vulnerability, would cause far worse problems for the world than just some URN system breaking down. As such, literal man-millenia of cryptanalysis has gone into ensuring that there are no vulnerabilities in popular algorithms. Re: accidental collisions, please note that 128 bits of entropy (i.e. a UUID) is already enough to ensure no accidental collisions before the heat-death of the universe. And most modern hashes have ≥256-bit residues.

ltbarcly3 5y ago
FYI UUIDs are 128bits but only have 122 bits of entropy. Still not going to get a collision with a good implementation.
- api 5y ago
  UUIDs are long enough but are not cryptographic hashes. They can be deliberately collided pretty easily. A cryptographic hash like sha384 or blake2 makes it infeasible to come up with any input that would ever yield the same output. That’s what you would use for such a network.
  - derefr 5y ago
    You're thinking of UUIDv1s, which pretty much nobody uses. UUIDv4s — the ones that are specified as being populated with 122 bits entropy from a HWRNG — cannot "be collided pretty easily." Those are what anyone clearly means if they're talking about "bits of entropy" in relation to UUIDs. (Also, as it happens, UUIDv3s and UUIDv5s are specified as having their payload bits populated with the cryptographic hash of a user-defined input. But just to muddle your point further, the cryptographic hashing algorithms used in v3 and v5 are not ones that you'd trust today for collision-resistance; MD5 [v3] and SHA1 [v5] have both had at least one collision attack successfully done against them.)
    - ltbarcly3 5y ago
      Also, the concern needs to be around 'accidental' collisions of the same uuid within the same logical namespace. For example, generating the same UUID as a key for two rows in the same table. Even with weak non-v4 uuids, this is extremely unlikely with any dataset you are likely to be working with, just because even the worst UUID versions still have a fair amount of entropy, so population sizes have to be absurdly large to get even a tiny probability of a collision. UUID's are not meant to be 'secret' or 'hard to guess', and implementations can not be relied on to take care in generating the right kind of random state to ensure they aren't predictable. From the RFC: https://datatracker.ietf.org/doc/html/rfc4122 https://datatracker.ietf.org/doc/html/rfc4122 Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example. A predictable random number source will exacerbate the situation.