On: United declares 4-digit pin login and lack of SSL “functioning as designed”

[curryhoward]

> That means the attack surface for accessing someone's account is NP hard, but N is always equal to 4.

FYI, the "N" in "NP hard" is not a number. It stands for nondeterministic. The mention of "NP hard" in the first place just seems...unnecessary.

[UnoriginalGuy → curryhoward]

To be honest both the email and tweet read like someone trying very very hard to sound smart. They're over-using concepts that don't help clarify the issue, so the only reason I can assume they even included that was so that we knew they knew that those concepts existed.

[blintzing → curryhoward]

Is he perhaps joking? Even a brief read of the Wikipedia article makes it clear that NP-hard isn't a mathematical expression in which 'N' stands for a number...

[UnoriginalGuy → blintzing]

He could be in the tweet (giving the benefit of the doubt), but there's no way he is in the email reading it in context.

[Dylan16807 → curryhoward]

Yes, it's a different N. He didn't say or imply they were the same N. It makes perfect sense to talk about the size parameter when discussing complexity.

[mmarx → curryhoward]

> The mention of "NP hard" in the first place just seems...unnecessary.

Furthermore, trying all possible passwords of length n for a fixed alphabet can be done in polynomial time, hence finding the password deterministically only takes polynomial time. Thus, it's only NP-hard if P=NP.

Edit: You're right, I mixed up length and size of the alphabet, so disregard that comment. I probably should go to sleep.

[Dylan16807 → mmarx]

k^n is exponential, not polynomial.