I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ possible plaintexts, and $N$ possible ciphertexts. Sadly, the Encryption function would make it easy to find the decryption function if the key was known. So, this isn't public. Next, For each pair of keys ($K_1$, $K_2$) we could find a third, $K_3$ such that $E_{K_1}(E_{K_2}(m)) = E_{K_3}(m)$ for all plaintexts, $m$. Generally, for every plaintext-ciphertext pair $(m,c)$, we'll have only one key $K$ such that $E_K(m) = c$. Now, assuming we know a plaintext-ciphertext pair $(m,c)$ how would I go about performing a birthday attack that finds the key $K$ in approximately $2*\sqrt{N}$ steps?

It's compelling me, but I'm unable to scratch the surface.

  • $\begingroup$ you may want to google 'birthday attack'; there are a lot of relevant results. $\endgroup$ – Coffee_Table Apr 18 '13 at 19:12
  • $\begingroup$ The birthday attack won't help at all here. The point is to have random pairs and looking for any coincidences in hash value. You are looking for a pair that gives $K$, which is fixed. That is presumably more work than just trying all possibilities directly. In birthday terms, you are looking in a group of $n$ people for somebody born a particular day (1 in $365 / n$) versus seeing if among classmates there are two with the same birthday (roughly 1 in $2 \cdot 365 / n^2$). $\endgroup$ – vonbrand Apr 18 '13 at 19:22
  • $\begingroup$ I understand, but the homework question wants this solved through the birthday attack. Which is where I'm a tad stumped. I understand what it is, but not how to set it up. $\endgroup$ – David Apr 18 '13 at 19:37
  • $\begingroup$ Do the $E_{K_i}$s commute? $\endgroup$ – John Douma Apr 19 '13 at 1:39

Your Answer

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

Browse other questions tagged or ask your own question.