5 ms·

I think the article completely misses the point. The password hashes we have now are often considered to take millions of years to be bruteforced, which is a wr

by rorrr 14y ago

I think the article completely misses the point. The password hashes we have now are often considered to take millions of years to be bruteforced, which is a wrong assumption. We don't really know what the future tech will be like. Most changes are evolutionary, but who knows, maybe tomorrow we'll have a quantum CPU with a trillion times more computational power.

eru 14y ago
To go off a tangent: Quantum computers are not real, yet, but we already have a handle on the complexity class of problems they will be able to solve in polynomial time. (We do not know everything about that class, yet. But we strongly suspect that it is neither a superset nor a subset of NP.)
- dchest 14y ago
  Brute force on quantum computer will require around 2^(n/2) invocations of algorithm, compared to 2^n on classical computer. Not a huge problem. http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_computing_attacks_on_key_strength http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_comp...
- tiziano88 14y ago
  I was under the impression that QNP (the class of problems solvable by a quantum non-deterministic Turing machine in P-time) is a (non strict) subset of NP. Things might have changed since I last checked though.
  - eru 14y ago
    Did you mean superset instead of subset? Anyway for my statement I was only interested deterministic polynomial time (perhaps with access to randomness) with or without quantum capabilities. "Why Philosophers Should Care About Computational Complexity" (http://arxiv.org/abs/1108.1791v3 http://arxiv.org/abs/1108.1791v3) is a good read about this---amongst other things.
    - tiziano88 14y ago
      I did mean subset, apparently a quantum computer could not solve every NP-complete problem in polynomial time. factorisation seems to be one of the candidates to benefit from quantum computation (thanks to Shor's algorithm), but SAT (for instance) would not, at least based on current state-of-art
      - eru 14y ago
        Yes, I know. So I guess if you meant subset, then you didn't mean to write "quantum ___non-deterministic___ Turing machine in P-time"?
duaneb 14y ago
If you remove the human element, then we could all use 64-character passwords and it would be effectively impossible to brute force, even with quantum computers. Of course, we are human.
dchest 14y ago
Nobody seriously talks about "millions of years to bruteforce", especially when applied to passwords. People consider the monetary and/or energy costs. There are practical limits to both.
kolinko 14y ago
Quantum computers don't work this way. Solving 1024-bit key in SHA (or sth) will take as much as 512-bit key using a comparable traditional computer. So it's still hard, and will always be.
- eru 14y ago
  The problem is different for encryption schemes relying on hardness of integer factorization.
- rorrr 14y ago
  > So it's still hard, and will always be That's a pretty bold claim, considering we're just beginning to understand quantum phenomena. Plus you have zero clue about what else awaits us in the future.

by rorrr 14y ago

eru 14y ago

To go off a tangent: Quantum computers are not real, yet, but we already have a handle on the complexity class of problems they will be able to solve in polynomial time. (We do not know everything about that class, yet. But we strongly suspect that it is neither a superset nor a subset of NP.)

dchest 14y ago
Brute force on quantum computer will require around 2^(n/2) invocations of algorithm, compared to 2^n on classical computer. Not a huge problem. http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_computing_attacks_on_key_strength http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_comp...
tiziano88 14y ago
I was under the impression that QNP (the class of problems solvable by a quantum non-deterministic Turing machine in P-time) is a (non strict) subset of NP. Things might have changed since I last checked though.
- eru 14y ago
  Did you mean superset instead of subset? Anyway for my statement I was only interested deterministic polynomial time (perhaps with access to randomness) with or without quantum capabilities. "Why Philosophers Should Care About Computational Complexity" (http://arxiv.org/abs/1108.1791v3 http://arxiv.org/abs/1108.1791v3) is a good read about this---amongst other things.
  - tiziano88 14y ago
    I did mean subset, apparently a quantum computer could not solve every NP-complete problem in polynomial time. factorisation seems to be one of the candidates to benefit from quantum computation (thanks to Shor's algorithm), but SAT (for instance) would not, at least based on current state-of-art
    - eru 14y ago
      Yes, I know. So I guess if you meant subset, then you didn't mean to write "quantum ___non-deterministic___ Turing machine in P-time"?

duaneb 14y ago

If you remove the human element, then we could all use 64-character passwords and it would be effectively impossible to brute force, even with quantum computers. Of course, we are human.

dchest 14y ago

Nobody seriously talks about "millions of years to bruteforce", especially when applied to passwords. People consider the monetary and/or energy costs. There are practical limits to both.

kolinko 14y ago

Quantum computers don't work this way. Solving 1024-bit key in SHA (or sth) will take as much as 512-bit key using a comparable traditional computer. So it's still hard, and will always be.

eru 14y ago
The problem is different for encryption schemes relying on hardness of integer factorization.
rorrr 14y ago
> So it's still hard, and will always be That's a pretty bold claim, considering we're just beginning to understand quantum phenomena. Plus you have zero clue about what else awaits us in the future.