4 ms·
We're lucky that hash collision attacks have a relatively simple mitigation like this. (Although you have to trust CAs to follow the rules and implement it prop
by agwa 11y ago
We're lucky that hash collision attacks have a relatively simple mitigation like this. (Although you have to trust CAs to follow the rules and implement it properly, and events of the last few years indicate that CAs need to have as few things to screw up as possible.)
However, we're not always going to be so lucky. The next major transition in digital certificates could very well be to post-quantum crypto due to advancements in quantum computing. Under that scenario, attackers will be able to simply compute a CA's private key and sign arbitrary certificates. There will be no mitigation short of clients ceasing to trust pre-quantum certs. But clients won't be able to do that unless servers are using post-quantum certs, and server operators won't want to do that if it would mean cutting off legacy clients that don't support post-quantum certs.
The solution to this first mover problem is to set a hard deadline after which legacy certs are retired. This forces clients and server operators to act. Pushing back the SHA-1 deadline at the 11th hour as CloudFlare proposes sends a dangerous message that such deadlines don't have to be taken seriously. This message will come back to haunt the Internet in the future.
- EGreg 11y agoCan someone explain to me in plain language / layman's terms how a quantum computer is supposed to reverse cryptographic hash functions? What would be the process EXACTLY?
- agwa 11y agoIt has nothing to do with "reversing" hashes. The attacker would use the quantum computer to determine the CA's private key (e.g. by factoring the RSA modulus using Shor's Algorithm), and would then be able to sign any hash they want. No need to attack the hash function; in fact hashes remain secure under quantum computing.
- tromp 11y ago> in fact hashes remain secure under quantum computing. Hashes will see their security cut in half, in terms of the effort needed to find a pre-image. (EDIT: security in bits = log of #evaluations needed) E.g. finding a SHA256 pre-image, which amounts to a search over a space of 2^256 candidates, can be sped up using Grover's algorithm, to roughly 2^128 hash evaluations.
- tromp 11y agoHashcash, the proof of work system employed by Bitcoin with hash function SHA256, is also vulnerable. Where a current mining chip might search a space of 6e13 nonces in 10mins, a quantum computer employing Grover's algorithm might be able to search a space of 1e18 nonces, even with much fewer circuits and slower cycle time (although in Bitcoin this is complicated by having limited nonce entropy in the header) Note that the potential for speedup is due to the extremely small time needed for a single proof attempt. A PoW that only allowed a hundred proof attempts in the block interval time would hardly be vulnerable.
- pyre 11y agoTheoretically, a quantum computer could reduce brute force time to a minimal amount. But really there are no "general purpose" quantum computers at the moment (so far as I know).
- paulirwin 11y agoWhen you say post-quantum certs, do you mean using a technique like key stretching (i.e. PBKDF2) to slow down the brute force time?
- agwa 11y agoI mean certs using post-quantum crypto for signatures (e.g. NTRU, hash-based signatures) rather than RSA or ECC, which are utterly defeated by quantum algorithms.
- guelo 11y agoAlso when we develop cold fusion, faster than light time travel, and exploit the many worlds theory crypto will be harder.