Timeline for How much would it cost in U.S. dollars to brute-force a 256-bit key in a year?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 22, 2018 at 17:25 | review | Suggested edits | |||
| Feb 22, 2018 at 21:39 | |||||
| Nov 8, 2011 at 21:43 | comment | added | Thomas Pornin | @Briguy37: I cannot prove it, but some smart people can. Roughly speaking, if we can break a cipher with an $n$-bit key in less than $2^{n/2}$ operations on a quantum computer, then we can break it in less than $2^n$ operations on a classical computer. It is quite technical, but a part of the problem is that even if you have a superposition of many states, the "filtering out" part to get a classical result (a definite 0 or 1) is constrained and cannot be done "at will". | |
| Nov 8, 2011 at 21:03 | comment | added | Briguy37 | @Thomas Pornin: I don't know how you can say concretely that my assumption is incorrect. For example, can you prove that it is impossible to make a boolean quantum function that checks if any answer in the combination of qubits is a valid key? This function would allow us to fix one bit as 0 and provide the rest as qubits in both states. If the result our quantum function was true, then the bit we fixed is 0, otherwise it is 1. Thus, the number of operations to determine the key would be the number of bits in the key. | |
| Nov 8, 2011 at 19:36 | comment | added | Thomas Pornin | The bit about a quantum computer with 14 qubits being able to "try all combinations of 14 bits in one operation" is incorrect. It is a very tempting assumption (a view of quantum computers as zillions of computers all running in parallel through the magic of quantum), but it is wrong -- otherwise, a QC with 256 qubits could break a 256-bit key in time 1. QC does offer (theoretically) a performance boost on exhaustive search, but not to that point: it can reduce a space of size $N$ to $\sqrt{N}$ (hence 256-bit key search with a QC should be as hard as 128-bit "normal" key search). | |
| Nov 8, 2011 at 19:27 | comment | added | Briguy37 | @mikeazo: The mobsters are brutes, so "brute"-force...oh so funny ;) For my real answer I made the assumption that there was a way to test if any combination of the set of qubits plus a definite combination of the remaining bits is a solution. Worst case if that assumption is false, since a 256-bit quantum computer is able to reduce the key complexity by 128 bits, it is safe to assume that a 14-bit quantum computer would be able to reduce the key complexity by at least 7 bits, which is still a gain of $2^7 = 128$ times less resources. | |
| Nov 8, 2011 at 17:45 | comment | added | mikeazo | The non-technical method is often called rubber-hose cryptanalysis, not brute-force. Also note, that as far as we currently know, a quantum computer will only halve the key space for a symmetric cipher (such as AES). See en.wikipedia.org/wiki/Quantum_computer#Potential Thus AES-256 in a quantum world would be equal to AES-128 in the classical world. That result could be improved upon though. | |
| Nov 8, 2011 at 17:20 | history | answered | Briguy37 | CC BY-SA 3.0 |