Discussion between woliveirajr and Abdelouahab Pp

1:58 PM

as I understand it, it's not so much the amount of memory being used per bcrypt evaluation (unless you evaluate millions of them simultaneously) but more the fact that bcrypt accesses this 4KiB buffer unpredictably. GPU's are extremely bad when it comes to memory latency. Graphics drivers try very hard to mask latency by doing other computations while waiting for a particular memory range to be fetched, and in most GPU applications it can do that because there's always other work to do.

but with bcrypt it can't, because everything depends sequentially on the values in that memory buffer, so it can't do anything except wait for that memory to be read, which is slow.

this is the basis of memory-hard problems

Abdelouahab Pp

2:20 PM

@Thomas so it forces the bucket to be 4ko to force the data to be sequential and not parallel?

Thomas

well the idea is that the GPU is going to have to wait anyway due to memory latency. So now it has two choices. It cannot keep working on this particular bcrypt invocation because every further calculation depends on the memory value which is currently being fetched, so it can either wait, or start working on a completely different bcrypt invocation (with a different input).

the first choice is obviously bad, but if the GPU takes the second one, it needs to allocate another 4KiB of memory AND still has to wait again for another memory latency, cascading until the GPU runs out of memory.

in other words, the GPU's parallelization abilities are severely hampered by the way bcrypt uses that memory buffer

Abdelouahab Pp

ah! now i get the idea, because i came from 3D world, where they say that using CUDA will accelerate render process many times (use in real time rendering) and this uses a lot the RAM, so this is why i was ambigus, i said, that RAM is used a lot and in huge amounts in those graphic computer software, so here, in contrast it is bcrypt algorithm that allows ONLY 4k and will not allow to use more than this?

Thomas

well no, with rendering algorithms generally memory access is predictable, and it is possible for the GPU to inexpensively switch to another task while waiting for the memory, but bcrypt makes that impossible because the buffer is accessed randomly with no apparent pattern and the algorithm is specifically designed so that nothing further can be done while memory is being read.

keep in mind bcrypt (and scrypt) was designed with the idea of making it run slow on the GPU and other parallel units

you can get the GPU to use all of its gigabytes of memory working on bcrypt but it won't help much because the GPU is going to spend its time accessing memory instead of actually doing work

since you come from a CUDA background, perhaps putting it like this

bcrypt is designed to have a ridiculously low computation/memory access ratio

whereas GPU's shine with algorithms with high computation/memory access ratio (stuff like: read input, do lots of work, write output). bcrypt goes (read input, do one operation, read another input, do another operation, and so on)

so the GPU spends 99% of its time actually waiting on memory latency instead of doing any useful work

in theory, anyway

Abdelouahab Pp

2:37 PM

ah, thank you! no i got the idea, and now came the question: so Scrypt uses more restrictions on accessing to RAM than BCrypt?

Thomas

I'm not too familiar with the differences between scrypt and bcrypt but scrypt has a configurable amount of memory (so now you can use, say, 60MB buffers which makes it even worse for GPU's as they can then barely run a few hashes in parallel) and probably a bit improved in other places

Abdelouahab Pp

euh, wait, in BCrypt it was 4k, and you said that 60M is worst? it is the bucket size? then it can send more data on it?

Thomas

well the GPU will run out of memory faster

Abdelouahab Pp

so do i understand that the more memory you give to the GPU, the more drawbacks you get?

Thomas

not necessarily, it's a balance between how that memory is used, how well can the GPU compensate for the latency hits each time memory is accessed, and how much parallel operations the GPU can ultimately do if it has X amount of memory and each task requires Y amount of memory.

if you have a 60MB buffer but don't use it like bcrypt does, the GPU is going to be really fast on it

this is an active area of research by the way, using memory constraints to defeat hardware superiority is actually quite a new idea in the grand scheme of things

so bcrypt and scrypt are somewhat "black magic" as they are mostly designed around existing hardware design and don't have that much theoretical support (afaik)

Abdelouahab Pp

2:46 PM

i thought in the beginning that both BCrypt and SCrypt use 4 Kilo, the only slow that SCrypt gains is using Salsa.
yes, it is really bizarre algorithms! even google when i search, it suggest replacing SCrypt by Script :p

Thomas

since you use CUDA, here's a nice exercise you can do try and observe the slowdown in action

on one side, have a kernel that adds two 4KiB vectors (of floats or whatever) together, and on another, have a kernel that has the same inputs, but shuffles the two vectors randomly before adding them

your GPU will do the first task extremely quickly, but is going to struggle on the second one, because it emulates the random access behaviour used by bcrypt with the blowfish tables it uses

PS: when I say shuffle, I mean instead of A[i] + B[i] you go A[random(i)] + B[random(i)] or something like that. keep it parallel of course

Abdelouahab Pp

so this is the Blowfish concept: take those 4K, and shuffle the table, so the reading will not be sequential, so like that, the program must struggle finding where is n+1 after n ?

Thomas

well, sort of, it's more complicated than that but yes. what happens is:
1. the GPU cannot keep the whole table in fast-access memory (most GPU's can only spare a few hundred registers at best)
2. the GPU then needs to read from the table in global memory, which is very slow, and it cannot do anything while it is reading this memory because n + 1 entirely depends on n
3. furthermore, the values of the table are accessed randomly, so the GPU cannot cache previously read table entries as it will probably need to read values in an entirely different location immediately after

so bcrypt is actively working against your GPU to make sure it cannot make full use of its capabilities

compare this to, say, iterated SHA256, where the GPU can just keep everything in registers (~256-512 bits) and churn through each calculation extremely fast as it does not need to read the memory at all until all iterations are complete

Abdelouahab Pp

ah, thank you, now i understand it! and about SHA256, this is where PBKDF2 lacks! if someone uses GPU, the algorithm is done!

Thomas

3:02 PM

exactly, with PBKDF2:
1. the GPU can keep everything inside registers (very low latency memory) as each SHA256 hash only takes a couple hundred bits of storage
2. the GPU doesn't need to access memory at all while it's working, as it already has everything it needs inside registers
3. everything is predictable, the GPU knows exactly how many iterations it's going to do and can easily distribute the work optimally

So the only way to slow down the GPU is to add more rounds, against which the attacker can respond by simply adding more GPU's

which is why a few years ago a couple thousand PBKDF2 iterations were sufficient whereas now you need around a hundred thousand to slow GPU's to any significant level

and that is becoming burdensome because as you keep adding more iterations, the real user has to wait longer and longer. that's not the case with bcrypt, or at least not as much

Abdelouahab Pp

ah! you made my day! no i become an expert in password protection :D thank you! sadly i cant vote here, else i programmed a GPU that will parallelize the vote :p
now, i have to understand what is SCrypt black magic, now i get BCrypt and PBKDF2 ;)
but, by the way, why BCrypt is limited to 56 characters ? is it By Design?

Thomas

just helping :) though note this is a very simplified overview, and I am by far not an expert on this.

about bcrypt, I don't know, really, I haven't studied the details of bcrypt that much. it could be by design or perhaps the authors decided to put this limit for another reason. in any case it should be enough for password hashing

Abdelouahab Pp

yes, thank you very much! now i can explain both PBKDF2 and Bcrypt, and when i come to SCrypt, i just try to explain Salsa, else, i'll stop there, but when we see all of these and people trying to understand such algorithms and others try to crack them and all of this head-breaking, and you find a system that stores passwords in plaint text!

Thomas

agreed. developers need to be more responsible when handling passwords, but it's been getting better over time, I have no doubt people are getting more educated about password hashing

I need to go, it's actually quite late over here and I need my sleep :P

Glad to have helped!

Abdelouahab Pp

yes, and they must oblige people to reset their passwords every 2 years, so they can make their password stronger !
thank you again :)

Transcript for

Discussion between woliveirajr and Ab…