7
$\begingroup$

While discussing the 72 character limit of BCrypt, the question of resilience to quantum cryptanalysis came up. A search online didn't give me much of a lead as to what research has been done in this area.

So my question is, are there any candidates for algorithms that would decrease the security of Blowfish, and by extention of BCrypt? If so, by how much?

$\endgroup$
3
$\begingroup$

I'm not aware of any quantum-based cryptanalysis results of symmetric ciphers that would perform better than Grover's algorithm on any symmetric cipher.

Now here's the interesting part: Grover's algorithm. It allows you to search in an unsorted set of size $n$ in time $\sqrt n$. Now for Blowfish the implication is clear: It effectively halves the keysize from 448-bit to 224-bit which is still extremely strong. However you shouldn't use Blowfish because of its blocksize and the fact that it's nearly broken by cryptanalysis.

Now for bcrypt we need the following statement:

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just $\mathcal O(\sqrt n)$ evaluations of the function, where N is the size of the function's domain.

Now Grover's algorithm allows you to find passwords much faster, but won't evaluate bcrypt faster but probably much slower. So suppose you have a password hash that has a strength of 80-bit, ie one would need $2^{80}$ operations to find the password. Chance are bcrypt takes 20-bits from that leaving you with 60-bits provided by the entropy of the password. Grover's algorithm can now half this value so you end up at $2^{30}$ bcrypt evaluations and thus $2^{50}$ operations overall.

TL;DR: Quantum computers will weaken password hashing but "as bad" as they weaken standard encryption.

$\endgroup$
1
$\begingroup$

Current traditional processors can decrypt symmetric ciphers at 2n speed. Quantum computers effectively halve the blocksize because they can decrypt at 2n/2 speed (Grover's algorithm).

Blowfish is one of these symmetric ciphers that is affected by Grover's algorithm, and it is expected to follow the same metric.

What makes BCrypt unique is the ability to easily scale up the time it takes to perform this work. If the keysize is halved, just increase the rounds done by 50% so it becomes impractical again. I suspect that quantum computing wouldn't necessarily weaken BCrypt as much as force us to find more practical key stretching alternatives such as Argon2.

We're quite a ways off before general quantum computing becomes a thing (or even hobbyist quantum computing). I think it is best left up to your threat model and whether or not you are trying to protect against nation state resources, at that point.

$\endgroup$
  • $\begingroup$ Could you provide some resources on the application of Grover's algorithm to other algorithms than AES? $\endgroup$ – J.A.K. Mar 1 '17 at 0:22
  • $\begingroup$ I don't have any resources available specifically for Grover's algorithm, unfortunately. However, Grover's algorithm is applicable to all block ciphers where an exhaustive search can be performed. See emsec.rub.de/media/attachments/files/2016/03/… for a traditional cryptanalysis on it. BCrypt has a keysize of 2^32. If Grover's algorithm was applied, I suspect it to be most useful to attack the expandKeys part of the function. If that's all that's needed, then attacking it will be easy no matter how much work is given to it during EksBlowfishSetup. $\endgroup$ – Tuxxy Mar 1 '17 at 1:06
  • 1
    $\begingroup$ For further critique, I'd really need to defer to someone with more experience in cryptanalysis here. I would be very interested in hearing what Schneier, or Provos and Mazières have to say about this. $\endgroup$ – Tuxxy Mar 1 '17 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.