Tag Info

Hot answers tagged

31

RSA has not been cracked. No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA. There is no reason to change any of your practices. The first thing to understand is that D-Wave has a long history of repeatedly making bogus claims to the popular press. Experts in quantum computing have been criticizing and ...


18

Well, cryptographers have been contemplating a post-quantum world for some time now. Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the ...


15

After contacting D-Wave and asking them the implications of their quantum computer against RSA, they responded that they had not cracked RSA for the following reasons… Short answers: Q. Is RSA effectively cracked by your quantum computer A. No. Q. Should our customers be concerned that companies with quantum computers are intercepting our ...


14

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256! Gilles Brassard, Peter Høyer and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the ...


13

In short, the answer is yes, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, this provides security up to 2256 operations against Grover's quantum algorithm. Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2n/2 with a quantum computer. This is a generic attack in the sense that it applies to any ...


10

Do the post-quantum ciphers also automag/tically address the 1st problem? Not really, however to explore that in any detail, we need to explore what the 1st problem is. If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems ...


9

You can do key agreement with asymmetric encryption. Any asymmetric encryption algorithm (post-quantum or not) can be used for key agreement: just choose a random key and encrypt it. Password Authenticated Key Exchange looks harder, because it cannot be applied on just any key exchange or asymmetric encryption scheme. The IPAKE framework can be applied on ...


9

The huge key is definitely an issue. Another is the lack of standardization or recommendations. Should you use OAEP with McEliece, or some other padding? What parameters are actually secure? And so on. Part of the problem is that, while it has been around since the 70s, it was not considered particularly interesting until quite recently—so it probably ...


8

First, lets get some thing clear over here. The analysis of Grover's algorithm is asymptotic, so it is fairly unfair to perform something as concrete as the setting you have mentioned. Grover's algorithm gives you an asymptotic upper bound of $O(\sqrt{N})$ for searching in an unsorted array of size $N$ so I have trouble understanding how one can claim that ...


8

As far as I understand, the HSP is a hard problem such that: some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built); many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key. In particular, integer ...


8

Wide adoption of an asymmetric encryption algorithm, or a digital signature algorithm, requires at least the following: There must exist a reasonably clear standard which unambiguously says where each byte goes. It must cover endianness and similar issues. PKCS#1 is such a standard, for RSA. The algorithm must provide reasonably good performance, in ...


8

Biclique cryptanalysis is the current best known attack on AES. It reduces the security of AES-256 from $2^{256}$ to $2^{254.4}$. Related key attacks are not practical attacks as they should never occur in the wild. they are symptomatic of a poor implementation, and contrary to the recommended use of AES. The best known theoretical attack is Grover's ...


7

A quantum computer solves the discrete logarithm problem for both finite fields and elliptic curves. Being able to efficiently calculate discrete logarithms implies being able to break Diffie-Hellman, so Diffie-Hellman on either of them is not secure against an adversary who owns a large quantum computer. There might be other groups in which DL problem is ...


7

Yes there are. The first publicly accessible McEliece implementation was this one from The Error Correcting Codes (ECC) Page, but it isn't particularly useful for reading, being quite obfuscated. There's INRIA's SECRET group implementation called HyMES that implements something quite similar. FlexiProvider (java library) contains quite a good amount of ...


7

With any $n$ bit hash it is possible to: Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's ...


6

Grover's Algorithm would allow searching an unsorted database with N entries in $O(\sqrt{N})$ time rather than in the usual $O(N)$ time. For AES-256 it currently takes an average of $n/2$ guesses to break, i.e. $2^{255}$. However with quantum computing this can be done in $2^{128}$ time, which is very much faster. And on top of that that's only brute force ...


6

Adding more qubits does not increase the computation speed. A quantum computer with 4 qubits does not factorize faster than one with 2. The qubits are the "memory" of the quantum computer. More qubits mean you can factor bigger numbers. If I remember correctly, you need a superposition of $\Theta(N^2)$ terms, which means $\Theta(\log(N^2))$ qubits to factor ...


6

This is highly insecure, for the same reason that ECB mode and simple substitution ciphers are. Every time you use the word the in your message, it will be encrypted the same way. The same goes for other, lower-frequency (but still fairly common) words -- like as or with or will (or any of hundreds of other examples). This is a humongous clue to ...


6

McEliece NTRU Multivariate If you mean "syntactically public key" instead of "implies the existence of secure key agreement", then there is also hash-based signatures.


6

I can't agree with bullet 3. of the question stating quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year), at least in a context of cryptanalysis. Even the marketing people praising the device alluded to do not pretend that it is of a kind useful for cryptanalysis: they state about it: The ...


6

Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical algorithms, but the best known quantum attack against AES is effectively "try all the keys." In a quantum computer, the time taken to solve a general search problem ...


6

The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is ...


5

Answering myself... There is now a very analogous alternative to Diffie-Hellman in post-quantum cryptography: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies The research paper is very new, but if the results turn out to be secure, this is a very competitive key agreement scheme for post-quantum cryptography.


5

No, since finding $a$ allows offline checking of passwords. $\:$ No, although I can't back this part up.


5

"Frequency analysis of the output might help determine simple words in the ciphertext such as 'the' etc if that word is repeated and sent multiple times. This isn't necessarily a problem as it's only a simple word and doesn't convey much meaning to the message". If the word "the" doesn't convey much meaning, then why have you used that particular ...


5

Your scheme would make a nice puzzle for amateur codebreakers. That's about the best that can be said for it. It does not meet the generally accepted standards for a modern encryption scheme; in particular, it is not semantically secure. In fact, the security of your scheme would be seriously compromised if an attacker obtained even a small amount of ...


5

I'm not going to exactly answer your question, because I have no idea. I simply do not know how fast the quantum computer is that NSA is building in secret. However I could explain why people recommend 256-bit security in the face of quantum computing using some numbers. If you feel that $2^{128}$ is a comfortable security against bruteforcing, remember ...


5

If you need security against quantum attacks, there aren't that many options. I would go for a lattice-based encryption like NTRU or something based on ring learning with errors. There are no "magic numbers" involved and the assumptions they are based on have been scrutinized by the academic community. NTRU has been around for a decade and has pretty good ...


5

I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7). I am not sure if this completely ends braid cryptography, however, since there are other difficult problems in braid groups that have not been studied extensively.



Only top voted, non community-wiki answers of a minimum length are eligible