Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
you may want to google 'birthday attack'; there are a lot of relevant results. – Coffee_Table Apr 18 '13 at 19:12
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$). – vonbrand Apr 18 '13 at 19:22
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. – David Apr 18 '13 at 19:37
Do the $E_{K_i}$s commute? – John Douma Apr 19 '13 at 1:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.