FAQ
First, thank you, Yves, for effectively admitting that the method is
indeed an ad-hoc unproven hack without any security.
On Tue, Jun 10, 2014 at 03:51:46PM +0200, demerphq wrote:
First, one has to analyze the potential impact of a problem, to see if
it's actually relevant (wasn't done for this change).
Which we did.
When I asked for that, I was simply told I am all wrong. I believe it when I
see it.
Then, if it is decided that something needs to be done, you find a way to
fix it, while showing that the fix works.
Which we did.
Same thing. I believe it when I see it.
One way (as recommended by the original paper that started this witch
hunt) to fix this is by using unpredictable seeds, using a csprng.
Which we did.
I don't think you did. I can't see it anywhere in 5.18 for example. The
prng used in 5.18 is definitely not cryptographically strong, which is the
whole point.
Regarding "with lots of strong seeds", I dont know what you mean.
Universal hashing alone isn't sufficient, as you should know, you also
need strong random seeds for it (the paper you reference explains
it).
Since I do know what Universal hashing is, having implemented it a
couple of times, I must assume *you* have no idea what universal hashing
is or you wouldn't say this so stupidly.
That's the kind of non-argument that I had to come to expect from
you: instead of usign an actual argument, you just insult anybody who
criticises you.
What has been implemented is a bit of entropy and some magic formula
involving shifts and adds, mixing some super-random things such as the
address of a variable, all of which resulting in a sequence that is
trivial to predict, and fails even superficial tests for security. It's
exactly the kind of ad-hoc algorithm somebody comes up with when he wants
some secure-looking results, regardless of security. Even the paper
explains that this isn't enough.
Clearly you have not actually looked at the code anywhere near as well as
you think.
Possibly. It would be simpler if somebody would just point out where it
is, because it seems to be very well hidden, borering on being not even
there.
The logic that uses the address of a variable is completely irrelevant to
the use of OAATH, which someone who posts as boldly as you have done here I
would expect you to know.
I wouldn't even know why the hash function is of relevance here - OAATH
isn't cryptographically strong, so it's mostly irrelevant w.r.t. a
solution.
2, 3, etc. Instead iterate in a pseudo-random order. The intent to this
change is to minimize information "leakage" about the order of the keys in
a bucket. If someone sees "a-b-c" they cannot know if the actual order was
"a-b-c" or if it was "c-b-a" or if it was "b-c-a" etc. So this does
nothing to the actual performance of the algorithm,
Yes, it also does nothing to the actual security - it's merely
obfuscation, which I have pointed out before. The requirement to use a
CSPRNG is crucial, anythign else leaks information, no matter how hard you
obfuscate it.
Additionally this highly volatile variable is used to "perturb" the order
that items that collide are inserted into the bucket.
There is nothing "highly volatile" about it. The variable contents aren't
hidden, not secured and change completely deterministically.
I admit this measure is not as complete as it should be.
The problem is that your whole method id ad-hoc, and has nothing to do with
an actual fix. IT is, as I pointed out, merely obfuscation.
So, we have a botched attempt to fix a problem, and 120 or so broken
modules
on CPAN. And as far as we know, the attacks are still possible.
No. You *think* you understand what is going on, and you paint a picture
that the uninitiated and unwary might believe is true, but to those more
informed it is pretty much just empty words and jargon.
That's what you say, but so far, apart from insulting those who criticise
your algorithm and claiming you are right, nothing much comes from you.

It's not enough to do some bit shifts to fix this problem. It is not
enough to make things *look* random. What you need for your chosen fix is
a csprng, no more, no less, and it's not there.

What you came up with is some algo that might look super random, but
really is just some ad-hoc hack that exemplifies bad security design: do
not invent your own primitives, and if you do, prepare to prove they are
safe.
The fact is that the paper from 10 years ago is NOT what we are responding
to. That is merely one straw on an overloaded camels back.
I would agree, just fixing that attack isn't enough, you have to fix
similar attacks. Would have to.
B) A working key-discovery attack was provided to the perl security list.
This attack could determine the seed used by OAAT in several seconds and
sufficiently few round trips that it was considered a serious failing. I
will not reveal how this attack worked, but it did.
Given the code, that's not surprising. What is bad is that you seem to wait
for actual attacks, rather then address theoretical weaknesses.

Sure, you can thwart any specific attack by slightly changing some magic
constants or slightl tweak the algorithm, but as long as you end up with
the same predictability in principle, you are just running after the
problems, rather than attempting to fix them.
The response to A was to remove the REHASH logic and switch to a
per-process randomized hash seed.

The response to B was to add random 4 byte suffix to all keys being hashed.

The response to C was to mix in the length of the key into the seed before
hashing.
I see that, but none of these fix the vulnerability in principle. You are
just tweakign your algo to obfuscate it, and wait for somebody to break
it.
Simply claiming others are wrong is an understandable strategy, but deeply
unprofessional: YOU have to show why your method is secure,
No. I dont. You cant prove something is secure. All you can do is prove is
it insecure.
Maybe somebody should tell this to the cryptographers who regularly
do security proofs. I think you do not understand what prove
means (I explained it earlier), but, yes, youc na certainly prove
things to be secure :)

Wikipedia has a simple enough introduction:
http://en.wikipedia.org/wiki/Provable_security

Besides, you are taking my words out of context. It's trivial to prove
that algorithms are secure with respect to this type of attack. Balanced
binary trees are, for example, trivially secure w.r.t. hash collisions -
the very concept doesn't apply to them.

The kind of proof required here is nontrivial - if you don't use a csprng,
then you need to prove that your method provides an equivalent level of
protection of your internal state under some suitable attack model.

While you claim it exists, you can't come up with a pointer...
YOU have to
explain why you didn't use one of the recommended methods,
Not sure what you mean by "one of the recommended methods" But then again I
don't think you understand what I did at all.
That is probably true - I probably do not understand what you did because
it was just some ad-hoc hack that you declared secure, and I am puzzling
over it see see where this security is supposed to come from.
If you mean why we didnt use universal hashing then you havent read my
mails, the blog post, or almost anything i have written on this subject or
you would see that I have actually talked about this in depth.
No, I asked why you don't use methods known to be safe against this
attack, as opposed to inventing your own without any proof (or at least
strong evidence) that it is secure.

I did not and do not suggest to use universal hashing. If I were in your
position, I'd probably look at detecting these cases and either switching to
an alternative algorithm that is known to be safe or simply throwing an
exception (the latter is not optimal, but better than leaving the problem
unpatched, I guess). The switching can be done at no performance loss, the
detection cannot, but I suspect it would still be cheaper than what you do
now.

The advantage would be a much more stable solution, one that doesn't
vest all it's security in one person claiming it's good, but into known
properties of your algorithms. It would provide upper bounds for runtime
overhead as well and would free perl to use whatever hahs function is
fastest, as opposed to requiring special properties from it that are hard
to prove.

It would also not have to rely on any secrecy that could, in whatever
way, leak. It doesn't require secret seeds either, which can be very hard
to come by on many systems that run webservers (embedded routers for
example).

I would attempt this simply because it is so much easier to manage, and
doesn't require a crypto expert at all, which perl doesn't have.

It is a conservative but still reasonably fast approach.

Maybe there are other solutions that have the same properties. Maybe you
can do much better with some better hashing scheme, but so far, nothing
seems to have come up.
and YOU have to
explain why your method has the required properties.
I have.
You keep repeating this, but you keep ignoring questions on where this can
be found.
You do understand why your scheme isn't cryptographically strong
Actually I don't know that. I don't know if it is cryptographically strong
OR weak.
Thanks for admitting that the problem is real.
What I do know is that with 64 of bits of seed it is feasible for a
determined attacker to brute force. But sufficiently hard that it would
have to be a very determined attacker.
Sure, you claim that. But why would it be so, given that your primitives are
not vetted for this?

All we have is your word, and the fact that you decided to now use hardened
primitives or another safe algorithm.

That's indistinguishable from obfuscation.

That's not enough.
What I also know is that the scenario that concerns us, that of Perl
operating as a server which returns serialized hashes, that the number of
requests required to attack the hash function is sufficiently large than it
would be indistinguishable from a data-flooding attack.
Ok, but how do you know? People without god-like qualities have to come to
this conclusion through proof.

What _I_ know, to the contrary, is that people who invent new algorithms
while "knowing" they are safe usually come up with the most tririvally
broken ones. That's why I wouldn't design such an algorithm without strong
theoretical support for it.

It is also telling that you claim that it's impossible to prove something
secure, but at the same time you "know" that the numbe of requests required
is sufficiently large.

I would say either put up or shut up - show that it really is so, or drop
the claim. So far, all we have is your repeated word that it is so, but no
other evidence.

And that's not enough to claim the problem has been fixed. It is enough to
say that no evidence has been produced that indicates that the problem is
fixed.

Or in other words, it is mere obfuscation protected by yelling at everybody
who points this out.

Whcih is where I go back to what I claimed in my first mail.
(as a
hmac scheme would be for example),
Why do you bring up hmac here?
Because a HMAC has the same qualities as you need form a CSPRNG, namely
decoupling your internal state from external visibility, which is the whole
point.

It's merely an example of an algorithm that has (or can have) the required
properties (proven, in fact, see http://eprint.iacr.org/2006/043.pdf,
which contains a security proof, somethign you say cannot be done).
This hash function is not being used to produce message digests, we do
not use the whole hash, only the lower K bits.
Indeed, this has nothing to do with message digests. The famous
http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf standard
shows how HMAC can be used as a CSPRNG.

In fact, using HMAC is one of the predominent methods used for CSPRNGs.
Moreso, HMAC is not about creating message digests, but about keying them
in a safe way.

I could insert some insulting remark here, as you do, about your obvious
lack of knowledge, but that's too far below my level :)
There is NO published research whatsoever about whether the low K
bits of a HMAC style digest is appropriate for a scaling hash table.
Actually, this property is part of the definition of cryptographic hash
functions.

Moreso, taking the lowest K bits isn't the only method, there are many ways
to extract bits from a digest.
Not to mention that such hash functions are very slow. If we were going
to use a hash function in that class we would use Siphash.
Absolutely - I don't propose using HMAC or a CSPRNG as hash function (and
have expliticly said so multiple times).
and you do understand why your method
isn't universal hashing with a strong (per-hash) random seed?
You really didn't read that Universal Hashing article very well.
I didn't read any specific universal hashing article in preparation for
this. I merely pointed out that you are not using it, which is true.
go read it again because to those who do know this subject you are making
yourself look like a complete moron, not just a plain old rude person. Rude
AND wrong is pretty embarrassing.
Ah right, insults to silence criticism instead of arguments. Can you do
better?
Now you want to use UH, with a different seed per hash, yet the UH seeds
No, I don't, and have said so. Why not spend energy on arguing the actual
criticism provided instead of making strawmen and then violently burning
them down?
needs to be proportional to the size of the keys in the hash. So you want
Perl to use ALL your memory for the hash seed?
Obviously not, you are the one who brought this up, I don't know why you
would want to...
Even if that weren't one of the dumbest things I have heard in ages, you
overlook the problem that in Perl we have a master hash table which holds
all the keys. The hash value for every key MUST be the same for every hash
in memory. This is hard systems requirement that is totally independent
from the hash function we choose.
It's not a hard systems requirement simply because Perl versions exist that
don't need this.

It might be desirable, but from that doesn't follow that you need to
invent some ad-hoc pseudo crypto code. Not at all.
are your reasons to not implement a (vetted) known-to-be-safe method,
but instead inventing your own much weaker one?
We did the modifications we did because they addressed the issues that we
knew about.
Well, they don't address thre issues at all apart form obfuscation.
I do not think you have *any* data to support the claim that what we do
now is weaker than the old one
The goal, Yves, is not to have a different algorithm, but one that avoids
the attacks. For that, it doesn't need to be weaker.
and I have considerable data that says it is harder than the old one.
Data can show that an algorithm is "harder"? In any case, where is this
data, I do not believe it exists.
Why do you claim your
hack method is secure, or solving the problem?
Because as far as I can tell it does.
That's what I wanted to hear - in other words, there is no research, no
theoretical foudnation. All we have is your word. You have no clue what
a CSPRNG is, what a HMAC is, but we have to believe that you are the
biggets crxypto expert possible, one that doesn't even need a proof or any
supporting evidence other than his word.

That is what I ame xpecting for along tiem, Yves, thanks, for basically
admitting it.
If you have useful feedback that it is not so then it will be considered
seriously.
That's the unprofessional way of doing things that I mentioned. Again, you
don't do security by inventing a new algo out of the air and then challenging
everybody else to break it.

You use an algorithm that is known to have the required properties, or, when
you invent one, you make sure there is good theoretical evidence that it is.

You don't just make up ad-hoc algorithms and claim it's secure until
somebody proves otherwise, as you continously do. That's what the 10 year
old kid from my leadign example does.
Please avoid the unprofessional tone of this mail in your
correspondence however.
All the unprofessional tone in "this" mail is by you, Yves. You are
the one who insults everybody who criticises the algorithm as lacking
security, while making big claims, instantly falling silent when somebody
asks for evidence.
Why do you claim that
others have to point out the problem with your method while at the
same time claiming that you are some kind of expert - this is a direct
contradiction...
Where did I make sure a claim?
Ugh, all over your mail, you do, for example. Basically your only claim to
the security of the method is that _you_ came up with it and data shows it
looks totally random or so - no other evidence required. What else, rather
than expertise, do you claim to have?

And just a paragraph or so above you claimed that _I_ have to come up with
evidence for you to consider the security of the algorithm, and that's not
the first time you mention this.

Fact is, _you_ should consider the security of the algorithm, and you
shouldn't rely on your personal beliefs, obviously.
This pretending that the problem is solved and trying to forcefully shut
up everybody else who points out that it isn't so is almost criminal: You
create the wrong impression that perl hashes are now safe, when they
weren't before, when this clearly isn't the case.
Well, I am quite confident that it is massively harder to launch a seed
discovery attack on Perls with my patches than without.
That might even be true: Obfuscation does that, for a time at least.

What I claim is that there is no theoretical security. This is just asking
for somebody investing enough effort to do it, afetrwhich you probably add
more obfuscation, continously running after the problem rather than solving
it.

That is exactly what I am claiming: instead of fixing the problem you merely
obfuscate it and challenge everybody who points this out to prove you wrong.
On the other hand I am quite open to someone making a breakthrough and
proving me wrong.
Yeah, I know, you expect others to prove your algorithm insecure, showing the
unprofessional way this problem is tackled.

Instead of solving the problem, you add a shift here and there, increasing
the workload for somebody to prove you wrong while never even attempting to
fix the problem.

What you do is really a hindrance attack on the good guys: actual
cryptographers are not interested into breaking ad-hoc algorithms that
continously change in simple ways but require a lot of analysis work.

The bad guys, of course, are happy enough to do this analysis once and
then just silently use it.

You are helping the criminals, while deceiving the innocents.
http://blog.booking.com/hardening-perls-hash-function.html i positively
welcome and invite cryptographers to attack and critique my work. So far
none have. :-(
Of course. Nobody analysis ad-hoc algorithms that are probably breakable, but
which are continously changed. That's not a challenge for a cryptographer.

That is *exactly* the behaviour I described in my mail that started this
subthread:

    The way you do "security" is the same way as some 10 year old kid who
    invents a super-duper-strong encryption algorithm using some shifts
    and some adds. Everybody who comes and explains why it's most likely
    not that strong, and not secure, is challenged to "prove me wrong" or
    "break this code". And when this doesn't happen he dances around in his
    room repeating "you are wrong, you can't break it!".

That nobody has taken you up on your challenge merely declares your
bankruptcy: If you designed an actual algorithm that ahs some security
proof or evidence, or that uses existing primitives, that is something
that security researches might want to challenge.
So here is what I will do, I will get in touch with TPF, I will give them a
donation of 500 euros, which will be for rewarding the first person that
proves that it is easier to attack Perl hashes in Perl 5.18 than it was in
Perl 5.16.
Exactly the unprofessional attitude of kids designing algorithms: I bet my
pet that you can't break it, show me! show me!

Obviously, this is bullshit - you know this cannot show anything about the
security of your algorithm.

In fact, I didn't know the situation was _that_ bad. When I wrote my
initial mail I thought the situation was similar as in my example, except
maybe you are atcually interested into a solution.

Now it's clear that you really have no clue about the problem, and work in
exactly the same way as in my example.

Perl5 development is in shambles if people are responsible for security
that have an attitude like you.
If you are right then not only will you earn bragging rights, but you will
get my 500 euros.
I don't need nor want your 500 euros. All I wanted is to point out that
perl hash security is practically nonexistant and all evidence we have is
you yelling at people and claiming evidence exists that almost certainly
doesn't exist.

I did think maybe there is some evidence, but you are just too arrogant to
point it out. By now it's clear you are just making it up.

Your childish challenges are designed to impress clueless people who
have absolutely no idea of what security or the attack means, and cannot
impress anybody who has had even a fleeting relationship with computer
security.

At least I have been proven right, and it's now obvious that your "all you
said is wrong" is just a feeble attempt at silencing valid criticism.
On the other hand I wont hold my breath.
You shouldn#t, you should put up the evidence that you claim exists but
you obviously don't come up with it.

I already proved you wrong - a CSPRNG isn't used to generate the
randomness for perturbation. Challenging me to show it's true is
obviously dishonest: I cannot show that something isn't there that isn't
there. _You_ have to show it exists.
Judging by the number of outright inaccuracies in your mail your
analytical skills are apparently not up to the job.
If you would point some of them out, maybe I could clarify so you are
able to understand. The problem is that all you do is handwaving, making
claims, but never point out where others are wrong, and never point out
where that mythical evidence is that you ask everybody else to believe
exists.

Let's start with a simple thing, where is the CSPRNG that generates the
randomness used in, say, hv_common? If it doesn't exist, where else is
the CSPRNG that generates any randomness used to perturb things? Or where
atcually is a CSPRNG in the code?

--
                 The choice of a Deliantra, the free code+content MORPG
       -----==- _GNU_ http://www.deliantra.net
       ----==-- _ generation
       ---==---(_)__ __ ____ __ Marc Lehmann
       --==---/ / _ \/ // /\ \/ / schmorp@schmorp.de
       -=====/_/_//_/\_,_/ /_/\_\

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

People

Translate

site design / logo © 2021 Grokbase