6 ms·

There were several exploits against different languages (PHP, Python, Node) which allowed denial of service attacks by abusing the hash function to craft a spec

by esnard 9y ago

There were several exploits against different languages (PHP, Python, Node) which allowed denial of service attacks by abusing the hash function to craft a special hash table where all elements have the same key. Randomizing the hash function makes it unpredictible to an attacker.

ninkendo 9y ago
I think you’re skipping the most contentious point which is that if it’s random it’s not a hash function any more. It’s more of just a unique ID each object has, and calling it a hash any more is misleading.
- chrisseaton 9y ago
  These are identity hash maps, so they need an identity hash function. That's pretty conventional terminology, used by for example Java, Ruby, ...
  - ninkendo 9y ago
    I suppose you're right, I never really thought of an "identity hash" as being a thing, but if it's commonly accepted nomenclature then there you go.
    - deleted 9y ago
      [deleted]
  - onli 9y ago
    If it is a random number it is not an identity hash function. It is just a position. And in my terminology this makes no sense here, as you normally hash the id/content of the thing you want to store, which is not happening if you return something unrelated to the object. What am I missing? Edit: https://github.com/multiformats/multihash/issues/13 https://github.com/multiformats/multihash/issues/13 suggests this is a replacement for using the content of the object, which is not available, to replace the step of hashing something. Is that it? Then it would be a replacement for a replacement of a hash, and not a hash anymore.
    - chrisseaton 9y ago
      Objects in some programming languages (like JavaScript, but not like others such as Haskell) have an identity value. This is an abstract value. It's a theoretical thing. We pretend it's there but it's not like a usual value. It's not something you can actually see or calculate with. You can just compare them. A hash function takes a value or a compound value and produces a simpler integer from it. An identity hash function takes an identity value and produces a simpler integer from it. Based on all these definitions, returning a random integer, as long as you store it and return it again the next time, is an identity hash function. > you normally hash the id/content of the thing you want to store That's what we're doing. You've said it yourself. We hash the id (identity) of the thing you want to store. You could call the identity the content of the object as well if you wanted to. It's not about replacing the actual content on the object, because JavaScript maps are, by design and by definition (23.1.3.6, 7.2.10), explicitly identity maps. They don't want to consider the content of an object, except for this abstract identity content. I'm not sure if you're arguing I'm mistaken, or the that the whole idea is wrong. But this is what many languages do and it's all very conventional terminology and practice.
      - gpderetta 9y ago
        > An identity hash function takes an identity value and produces a simpler integer from it I would expect an identity hash function to be exactly that: i.e. a trivial function that takes a value and returns that value unmodified (i.e. the identity function). It happens to describe well this case because the input to the has function itself is the unique identifier and as it is already uniformly distributed, the has function can just return it unmodified.
        chrisseaton 9y ago
        In this context, an 'identity hash function' means that it's a 'hash function for an identity value'. It doesn't mean 'a hash function that is an identity function'. It's confusing!
        dfox 9y ago
        In the simple case of using memory location as object identity (ie. in system without moving GC) and typical textbook hashtable implementation simply using the pointer as hash value is highly suboptimal, because heap pointers do not have remotely uniform distribution (low order bits are always zero due to allignment constraints, high order bits tend to be constant and usually also zero...). On the other hand you can use more advanced hashtable design that is explicitly tuned for non-uniform hash value distribution. See CPythons dict for cannonical example of that, although it's motivations are somewhat different (the major reason is that in CPython even real hash values of object's content are intentionally non-uniform to allow for simple way of causing integer-valued floats to have same hash value as ints of same value).
- ubernostrum 9y ago
  In the case of Python, for certain built-in types, __hash__() combines information about the object with a salt value. The salt can be manually forced by an environment variable, but if not supplied that way will be randomly chosen on interpreter startup. The result is consistent hashing within a given interpreter process, but unpredictability across multiple processes/invocations, which is what's needed to avoid a denial-of-service vector created by predictable hash values for built-in types.
  - ninkendo 9y ago
    Salting isn’t what I mean by random, I mean literally having the hash value have nothing to do with the item you’re hashing. Either way, terminology is weird here, but it seems like in V8’s case the word “hashing” better describes what happens to the hash code when the hashtable algorithm decides what bucket to place the object in (likely a modulus operator or a bit shift), at which point the “hash code” isn’t a hash value at all but just a unique ID that’s a seed value for the real hash function... but again, terminology can be misleading.
    - ubernostrum 9y ago
      I was pointing it out because the feature is called "hash randomization".
- kqr 9y ago
  What are you saying here? That it does not classify as a hash function (determinism, uniformity, various forms of collision resistance, one-wayness) or that it is not a hash of the contents?
  - ninkendo 9y ago
    I’ve conceded elsewhere that “hashing” is an acceptable enough term for what’s happening here, but, for nomenclature I’m more familiar with, v8’s randomly-assigned “hash codes” are something I would be more comfortable calling “identifiers”, since they’re assigned values that exist as state on the underlying objects. When I think of a hash value, I think of something that’s calculated via some properties of an object, not just a stored number.

by esnard 9y ago

ninkendo 9y ago

I think you’re skipping the most contentious point which is that if it’s random it’s not a hash function any more. It’s more of just a unique ID each object has, and calling it a hash any more is misleading.

chrisseaton 9y ago
These are identity hash maps, so they need an identity hash function. That's pretty conventional terminology, used by for example Java, Ruby, ...
- ninkendo 9y ago
  I suppose you're right, I never really thought of an "identity hash" as being a thing, but if it's commonly accepted nomenclature then there you go.
  - deleted 9y ago
    [deleted]
- onli 9y ago
  If it is a random number it is not an identity hash function. It is just a position. And in my terminology this makes no sense here, as you normally hash the id/content of the thing you want to store, which is not happening if you return something unrelated to the object. What am I missing? Edit: https://github.com/multiformats/multihash/issues/13 https://github.com/multiformats/multihash/issues/13 suggests this is a replacement for using the content of the object, which is not available, to replace the step of hashing something. Is that it? Then it would be a replacement for a replacement of a hash, and not a hash anymore.
  - chrisseaton 9y ago
    Objects in some programming languages (like JavaScript, but not like others such as Haskell) have an identity value. This is an abstract value. It's a theoretical thing. We pretend it's there but it's not like a usual value. It's not something you can actually see or calculate with. You can just compare them. A hash function takes a value or a compound value and produces a simpler integer from it. An identity hash function takes an identity value and produces a simpler integer from it. Based on all these definitions, returning a random integer, as long as you store it and return it again the next time, is an identity hash function. > you normally hash the id/content of the thing you want to store That's what we're doing. You've said it yourself. We hash the id (identity) of the thing you want to store. You could call the identity the content of the object as well if you wanted to. It's not about replacing the actual content on the object, because JavaScript maps are, by design and by definition (23.1.3.6, 7.2.10), explicitly identity maps. They don't want to consider the content of an object, except for this abstract identity content. I'm not sure if you're arguing I'm mistaken, or the that the whole idea is wrong. But this is what many languages do and it's all very conventional terminology and practice.
    - gpderetta 9y ago
      > An identity hash function takes an identity value and produces a simpler integer from it I would expect an identity hash function to be exactly that: i.e. a trivial function that takes a value and returns that value unmodified (i.e. the identity function). It happens to describe well this case because the input to the has function itself is the unique identifier and as it is already uniformly distributed, the has function can just return it unmodified.
      - chrisseaton 9y ago
        In this context, an 'identity hash function' means that it's a 'hash function for an identity value'. It doesn't mean 'a hash function that is an identity function'. It's confusing!
      - dfox 9y ago
        In the simple case of using memory location as object identity (ie. in system without moving GC) and typical textbook hashtable implementation simply using the pointer as hash value is highly suboptimal, because heap pointers do not have remotely uniform distribution (low order bits are always zero due to allignment constraints, high order bits tend to be constant and usually also zero...). On the other hand you can use more advanced hashtable design that is explicitly tuned for non-uniform hash value distribution. See CPythons dict for cannonical example of that, although it's motivations are somewhat different (the major reason is that in CPython even real hash values of object's content are intentionally non-uniform to allow for simple way of causing integer-valued floats to have same hash value as ints of same value).
ubernostrum 9y ago
In the case of Python, for certain built-in types, __hash__() combines information about the object with a salt value. The salt can be manually forced by an environment variable, but if not supplied that way will be randomly chosen on interpreter startup. The result is consistent hashing within a given interpreter process, but unpredictability across multiple processes/invocations, which is what's needed to avoid a denial-of-service vector created by predictable hash values for built-in types.
- ninkendo 9y ago
  Salting isn’t what I mean by random, I mean literally having the hash value have nothing to do with the item you’re hashing. Either way, terminology is weird here, but it seems like in V8’s case the word “hashing” better describes what happens to the hash code when the hashtable algorithm decides what bucket to place the object in (likely a modulus operator or a bit shift), at which point the “hash code” isn’t a hash value at all but just a unique ID that’s a seed value for the real hash function... but again, terminology can be misleading.
  - ubernostrum 9y ago
    I was pointing it out because the feature is called "hash randomization".
kqr 9y ago
What are you saying here? That it does not classify as a hash function (determinism, uniformity, various forms of collision resistance, one-wayness) or that it is not a hash of the contents?
- ninkendo 9y ago
  I’ve conceded elsewhere that “hashing” is an acceptable enough term for what’s happening here, but, for nomenclature I’m more familiar with, v8’s randomly-assigned “hash codes” are something I would be more comfortable calling “identifiers”, since they’re assigned values that exist as state on the underlying objects. When I think of a hash value, I think of something that’s calculated via some properties of an object, not just a stored number.