1
$\begingroup$

I am trying to understand the paper "Breaking Symmetric Cryptosystems using Quantum Period Finding", and I reckoned the paper is roughly implying to break secret-key cryptographic system by finding the factors of the secret key. Is that correct?

$\endgroup$
  • 5
    $\begingroup$ AES is not related to integer factorization, so no. $\endgroup$ – forest Dec 11 '18 at 10:04
  • 2
    $\begingroup$ @forest i was thinking the same. So if its not about factorization, whats the paper all about? $\endgroup$ – hammad Dec 11 '18 at 10:25
  • 1
    $\begingroup$ The word factor only appears two times in the paper. 1. Shor. 2. In the references. $\endgroup$ – kelalaka Dec 11 '18 at 10:46
8
$\begingroup$

Two things:

Firstly, the paper is not talking about factorization at all; instead, it is using the Quantum Computer as a "constant-that-doesn't-change-the-output" algorithm (that is, find an $s$ such that $f(x) = f(x \oplus s)$ for all $x$) to break certain message authentication algorithms (which may just happen to use AES).

The paper notes that, with these specific message authentication algorithms, if you are able to find such a constant, that also gives you enough information to break the message authentication code.

Secondly, this is not actually a practical break. They run their attack in a "Quantum Oracle" model, where the attacker is given an Oracle where he can submit superpositioned queries, and get a superpositioned response. Now, in practice, this superposition state is extremely delicate; it would take rather complicated Quantum Error Correction logic to maintain it (which is actually a bit more than what we can actually implement just now). It would be quite impossible to send such a query over the internet and hope to get the correct response.

What the attacker would have to do is take this Oracle and build it in his Quantum Computer (which would implement this complication Quantum Error Correction logic), and use the attack that way. Which leads to the question: if the attacker has access to the actual implementation with the secret keys (so that he can reconstruct it within his quantum computer), why doesn't he just look inside for the keys?

$\endgroup$
  • $\begingroup$ thank you much for such an elaborate answer. I still find the paper confusing though. Whats the input to the 'Simon's Algorithm' in this scenario? Im guessing the formula you wrote is Simon's Algorithm. right? $\endgroup$ – hammad Dec 12 '18 at 16:06
  • $\begingroup$ @hammad: the formula is the problem that Simon's Algorithm solves. As for the inputs, well, that actually depends on the exact primitive that you're trying to attack; the paper covers a number of them... $\endgroup$ – poncho Dec 12 '18 at 16:27
  • $\begingroup$ can you please elaborate at least one of them? $\endgroup$ – hammad Dec 12 '18 at 17:05
  • $\begingroup$ @hammad: well, the easiest would probably by CBC-MAC (GCM is actually easier if you understand Galois math); for the two two-block messages $(a_0, x)$, $(a_1, y)$, they'll have the same tag iff $x \oplus E_k(a_0)) = y \oplus E_k(a_1))$. Hence, we give Simon's an Oracie with 129 bits of input; the first one selects between two fixed blocks $a_0, a_1$, and the other 128 bits is the second block of the message. Simon's will give an $s$ with the first bit set, and the other 128 bits being $E_k(a_0) \oplus E_k(a_1)$. From that, we know $(a_0, x, y)$ and $(a_1, x\oplus s, y)$ have the same tag $\endgroup$ – poncho Dec 12 '18 at 18:29

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.