Hacker News Reader

Comment by uptown | Hacker News Reader

How long would it take, given the immense computing capabilities of the government, to try every possible permutation of Apple's signing keys in order for them to be able to sign their own home-grown version of iOS? With over a billion devices at stake, isn't that what intelligence agencies would actively be targeting?

View on HN

Using brute force (i.e. "immense computing capabilities") for properly sized keys is unlikely to ever be practical with classical computers. With quantum computers, many currently deployed key lengths that would be impractical to brute force with classical computers would become vulnerable to attack, but nobody is currently known to have quantum computers of sufficient power. See Wikipedia for basic details[1].

IMO, an intelligence agency would be more likely to invest in other methods (algorithm implementation weaknesses, software bugs, insider access, etc), due to the higher liklihood of sucess.

That said, it's interesting to note that the NSA is moving towards "post-quantum" cryptography[2], under the assumption that suitably powerful quantum computers will be, or have been, built. Whether the NSA already has such suitably powerful quantum computers is anybodys guess.

[1] https://en.wikipedia.org/wiki/Key_size#Brute_force_attack [2] https://www.nsa.gov/ia/programs/suiteb_cryptography/

Very interesting. I wonder how one feasibly could test "quantum resistant algorithms" without having a quantum computer to test it against.

The same way we create and vet conventional cryptography: withstanding public scrutiny of experts until we are reasonably confident that there are no major issues. Most attacks are theoretical and require only novel analysis and a new bound on computational difficulty, not a proof of concept (i.e., algorithms are abandoned by cryptographers long before attacks become feasible).

Post quantum algorithms are simply algorithms designed and analyzed against a stronger threat model. Some of the attacks and techniques are still being developed, so no one knows if new quantum algorithms will be invented tomorrow that trivialize certain problems but the same danger is present to some extent for conventional cryptography today.

Reply on news.ycombinator.com