Pardon my ignorance on the matter but,
Verifying passwords = Polynomial (linear)
Guessing passwords = Exponential
Since each guess has nothing to do with one another, exponential time is best possible time (but verifiable in linear time).
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ You would need a more rigorous formalization of the computational problem of "finding a password". If you do (If you lack the basic definitions to do this, our reference question can help ), then I believe the problem may reduce to the question whether there exist one-way functions, an open question that is harder than P vs NP! (or well, known to be at least as hard and not known to be equivalent, to be more precise) $\endgroup$ – Discrete lizard♦ Aug 12 '20 at 9:32
Add a comment
|
$\begingroup$
$\endgroup$
3
The main problem with your argument is that guessing a completely unknown password doesn't fit in the framework of P vs NP. P and NP are classes of decision problems. This means that you are given an input and you have to answer "yes" or "no". For example, in the Hamiltonian graph problem you are given a graph and you answer either "this graph is Hamiltonian" or "this graph is not Hamiltonian". There is also no hidden information. If you answer "no", I can't suddenly say "aha, there is an additional edge in the graph that I didn't tell you about, which makes it Hamiltonian, so you're wrong". Guessing a password doesn't have a yes-no answer and it involves hidden information, so it's not a decision problem.
Maybe you are thinking of some interpretation of password guessing that is a decision problem. If so, you should clarify what you mean.
-
$\begingroup$ "Guessing a password doesn't have a yes-no answer" Wait what... Of course it does. Is it the correct password or not? $\endgroup$ – master_of_privates Aug 12 '20 at 20:08
-
$\begingroup$ @master_of_privates Yes, "wait what". You should wait and take your time to understand what you are being told. You are far from prepared to understand not only what could be the answers to your question, but also to formulate the actual question that you want to ask. If you hope to fill that gap, instead being so fast in assuming that there is something wrong with what you are being told, take your time to understand it. And if you don't, ask about it, not assuming that what you are being told is wrong, but assuming, as it is in this case, that the problem is in your understanding. $\endgroup$ – plop Aug 12 '20 at 22:54
-
$\begingroup$ @master_of_privates A decision problem must be expressed like "Given input x, output Yes if XXXX, otherwise output No". There can't be hidden information: the correct answer must depend on x and nothing else. How would you express password guessing in this format? What is XXXX? $\endgroup$ – Ilkka Törmä Aug 13 '20 at 4:06
$\begingroup$
$\endgroup$
5
You just need a mathematical proof that cracking a password cannot possibly done in polynomial time. The only evidence is “all these clever people tried, and they did not succeed”, which is the exact same situation as for P≠NP.
-
$\begingroup$ I would say that all guesses are entirely independent of one another, therefore you have to brute force it. $\endgroup$ – master_of_privates Aug 12 '20 at 9:31
-
$\begingroup$ @master_of_privates “all guesses are entirely independent of one another” only if you've decided to use brute force to crack it. But there could be another way. For example, with a CRC instead of a password hash, there's a way to calculate a preimage that's faster than brute force. $\endgroup$ – Gilles 'SO- stop being evil' Aug 12 '20 at 10:18
-
$\begingroup$ You posted a one line opinion. That doesn’t exactly count as a mathematical proof. $\endgroup$ – gnasher729 Aug 12 '20 at 11:27
-
$\begingroup$ That's not an opinion. It's a fact. 1 combination has nothing to do with another. $\endgroup$ – master_of_privates Aug 12 '20 at 20:08
-
$\begingroup$
$\endgroup$
Problems in complexity theory have to scale with respect to some parameter. A 9x9 Sudoku for example can be solved by brute forcing all solutions - this in itself is not an exponential algorithm until we measure its growth with respect to $n$.
Back to your problem. Suppose we phrase the problem of guessing passwords as a decision problem. What is your input to describe a particular instance of the problem, if not the password itself?
Now suppose again we have the password is fixed with the problem statement. For example, one could have the password be digits of $\pi$, and the input is the length $n$. Well, there always "exists" a non deterministic Turing machine that can simply output that string without calculuation as well.
This just sheds some light on NP hardness. This link provides you with a definition of P, NP and NP-hardness.
