One random (heh) thing that occurs to me reading this article is that if you are using hashing for security (e.g. password hashing, key derivation, ...) then what the author is calling "invertibility", i.e. there are few values in the input space that map to some value in the output space, is actually a good thing. All other things being equal, the more such input values there are, the more feasible collision/preimage attacks become. It seems clear that for these purposes, the information content of the output should be at least equal to that of the input.
Why should hard be secure enough? Information and non-invertibility
21–30 of 48 posts
Re: Why should hard be secure enough? Information and non-invertibility
#22Earlier quoted context omitted.
Nitpicking, but you can have a uniform distribution on the unit interval, which is infinite :). What you cannot have is a uniform distribution on an unbounded set. Edit: As pointed out, the correct assumption is not unboundedness, but having infinite measure (since then no normalization constant exists). I thought they were equivalent, but a simple counterexample is [0,1] \cup Z.
It's an interesting exercise in measure to figure out what falls apart between a uniform distribution on [0,1] and the lack of one on [0, inf]. (Adding a point at infinity to compactify the set, which makes the two intervals topologically equivalent.)
To elaborate, the reason topological equivalence doesn't help here is because probability is defined in terms of measure spaces, not topological spaces.
Re: Why should hard be secure enough? Information and non-invertibility
#23A good hash function doesn't, and cannot, ensure that you have no information about the input. It can't take information away from you.
A good hash function ensures that, whatever information you have about the input, you have no more information upon seeing the hash. If you believe x is equiprobable over some range, seeing H(x) should cause you to continue to believe it's equiprobable over that range. If you believe x is the square of some random variable y which is equiprobable in some range, seeing H(x) won't convince you that x is equiprobable!
If your prior for x is equiprobable over the space of Microsoft Word documents confessing to high treason and 0 probability elsewhere, seeing H(x) won't tell you which Word document it is, but it certainly won't cause you to believe that it might be an MP3, either.
Re: Why should hard be secure enough? Information and non-invertibility
#24I don't understand why the x^2 thing is interesting at all. If I multiply x by 0, the distribution is now just 0. If I take abs(x) now it is positive. Are these confusing to anyone?
It's confusing to me why the author is confused by these. As you say, he's literally saying "if I know nothing about x, then I should also know nothing about 0x". Wtf? No.
I think the confusion is between the idea that a hash function conveys zero information about the input, and the idea that you will have zero information about the input once seeing the output of the hash.
But if we move it out of math, it's easier to understand: if you have some guesses about x, and I tell you nothing, you have the same guesses about x. You don't stop having guesses.
Re: Why should hard be secure enough? Information and non-invertibility
#25The concepts are a bit sloppy here. "Zero information" is a bit of hand waving which relies on the idea of having a uniform distribution on a set with infinite measure, which is not mathematically sound nor is it useful as an approximation.
All messages that you choose to transmit follow some probability distribution with each message having finite, nonzero probability. This is what the author gets wrong, on a very fundamental level. If this were not true, your messages would require an infinite number of bits to transmit.
Studies of the usefulness of hash functions are based on comparisons to an "ideal" hash function called a random oracle. The idea behind a random oracle is that you can't reverse it, but you can try to remember what outputs it gives for known inputs.
This "perfect hash function" has been extensively studied and still suffers from all of the flaws that the author mentions in this article. And yet people prove rather strong properties of cryptography systems under the random oracle assumption. So the author's criticisms, fortunately, have no bearing or relationship to real cryptography, because the good systems are already designed to be immune to such attacks.
I'm on mobile so I can't really give a play by play but the article is really based on nothing more than bad math.
Re: Why should hard be secure enough? Information and non-invertibility
#26Earlier quoted context omitted.
Nitpicking, but you can have a uniform distribution on the unit interval, which is infinite :). What you cannot have is a uniform distribution on an unbounded set. Edit: As pointed out, the correct assumption is not unboundedness, but having infinite measure (since then no normalization constant exists). I thought they were equivalent, but a simple counterexample is [0,1] \cup Z.
Mathematician here. You can't have a uniform distribution on a set with infinite measure. Unbounded sets are fine as long as they have finite measure.
A point distribution (single point) might be considered uniformly distributed. :-)
Re: Why should hard be secure enough? Information and non-invertibility
#27I think information can not be defined based on the source material alone. Why don't we define information like this?
An observer X has a prior estimate of the distribution d1 of variable x.
The source material yields a distribution d2 of variable x.
Then for that observer, the information gained from the source is something like |d1-d2|.
Re: Why should hard be secure enough? Information and non-invertibility
#28diogomonicapt writes "Light does not travel at the speed of light (no pun intended) because it is hard for it to do otherwise. No. It travels (and does so at that particular speed), because it is impossible for light to do otherwise." Actually,the speed of light in a vacuum is an upper bound. The actual speed of light can be substantially slower. https://en.wikipedia.org/wiki/Slow_light Some cosmological theories do…
He didn't say "the speed of light in a vacuum", he just said "the speed of light". And in the next sentence he said > … it is simply not possible for light to be still, or even propagate at a different speed in the same medium. So he's already acknowledged the fact that the speed of light depends on the medium. His point, though, is that light must still travel at this speed (even though the speed itself depends on t…
The speed of light in a medium is still the speed of light in vacuum if you look carefully enough. The apparent slowdown is just an emergent effect due to the interaction of photons and the particles making up the medium.
Re: Why should hard be secure enough? Information and non-invertibility
#29Earlier quoted context omitted.
Nitpicking, but you can have a uniform distribution on the unit interval, which is infinite :). What you cannot have is a uniform distribution on an unbounded set. Edit: As pointed out, the correct assumption is not unboundedness, but having infinite measure (since then no normalization constant exists). I thought they were equivalent, but a simple counterexample is [0,1] \cup Z.
Mathematician here. You can't have a uniform distribution on a set with infinite measure. Unbounded sets are fine as long as they have finite measure.
What is an unbounded set with finite measure?
Re: Why should hard be secure enough? Information and non-invertibility
#30The author considers speed of light being the absolute, irrevocable certainty, but how does he know that?
Does he know _why_ c is constant? Had he mastered general relativity enough to be 100% sure that it can't vary in time or space? Or that our current understanding of physics is total and there absolutely can't be something that we don't know about speed of light?
https://en.m.wikipedia.org/wiki/Time-variation_of_fundamenta... https://en.m.wikipedia.org/wiki/Variable_speed_of_light