Coding contest byte: Meet in the middle

Coding contest trick: Meet in the middle

== code(c) |
def 4sum(A):

  S = {}

  sums = {}

  for a in A:
    for b in A:

      S[a + b] = (a, b)

      sums[a + b] = (a, b)

  for c in A:
    for d in A:
      if -(c + d) in sums:

        print (S[-(c + d)][0], S[-(c + d)][1], c, d)

        print (sums[-(c + d)][0], sums[-(c + d)][1], c, d)

        return
  print "No solution."

h2. Breaking 2DES
!<blog/meet-in-the-middle?2des.png 70%!

DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie-Hellman. 3DES is less susceptible as it encrypts the message 3 times using 2 keys.

DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie-Hellman. 3DES works around this problem by encrypting the message 3 times using 2 keys.

Let’s see why 2DES is vulnerable. Let $Ek$ be the encryption function using the secret key $k$ and $Dk$ the decryption function using the secret key $k$. 2DES uses two keys, k and K. Ek(EK(p)) = s does the encryption and DK(Dk(s)) = p does the decryption.

For the pattern p it tries all the possible keys to obtain a set of numbers corresponding Ek(p). Also for the pattern s it uses all the possible keys to decrypt s, Dk(s).
If we find any match in the two sets it means that Eki(p) = Dkj(s) so the secret keys are ki and kj.
The naive brute force algorithm does $2^56^ * 2^56^$ iterations going through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store all Eki(p) and does $2^56^$ work to find a match.

This is quite a bit of space and quite a bit of computation time. But a for a large enough company or country it starts being within the realm of posibility.

Breaking 2DES was basically the DOUBLE problem from the International Olympiad in Informatics 2001.

The problem DOUBLE the International Olympiad in Informatics 2001 was basically asking to break 2DES for keys of size 24 which is quite feasible.

h2. Discrete logarithm

The naive solution goes through all possible values of k and takes $O(n)$ time.
The baby-step, giant-step algorithm solves the problem more efficiently using the meet in the middle trick.

Let's write k = $i([sqrt(n)] + 1) + j$

Let's write k = $i[sqrt(n)] + j$

Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.

Replacing k in the equality we get $p^(i ([sqrt(n)] + 1) + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^(i[sqrt(n)] + 1)^ = qp^-j^ (mod n)$.

Replacing k in the equality we get $p^(i[sqrt(n)] + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^i[sqrt(n)]^ = qp^-j^ (mod n)$.

At this point we can brute force through the numbers on each side of the equality and find a colision.
The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.

public

protected