Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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? –  user69810 Apr 19 '13 at 1:39
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.