ImperialViolet

How good is a 64-bit DH exchange? (15 Mar 2008)

In my last post, I suggested that a register based modexp for 64-bit numbers could run at about 500K ops/sec. Well, I wrote one and got 450K ops/sec on an older Core2. (That's with gcc -O3, but no tuning of the code. Plus, I don't know the standard algorithm for 128-bit modulus using 64-bit operations, so I wrote my own, which is almost certainly suboptimal.). Roughly that's 220 ops/s, so a brute force solution of 64-bits would take about 242 seconds, which is more than enough for us.

However, there are much better solutions to the discrete log problem than that. Here I'm only dealing with groups of prime order. There are very good solutions for groups of order 2n, but DH uses prime order groups only.

The best information I found on this are a set of slides by djb. However, they are a little sparse (since they are slides after all). Quick summary:

In short, attacks against discrete log in prime order groups are a lot stronger that I suspected. The index calculus method, esp, seems be a killer against 64-bit DH exchanges providing any sort of security. Since we don't have the time (on the server) or the space (in the TCP options) to include a unique group for each exchange, the precomputation advantage means that it's very possible for a sniffer to be breaking these handshakes in real time.

Damm.

So it would appear that we need larger key sizes and, possibly elliptic curve based systems (the EC systems, in general, can't be attacked with index calculus based methods). RFC 2385 suggests that 16 bytes in a TCP header is about as much as we would want to add (they are talking about SYN packets, which we don't need to put public values in, but the absolute max is 36 bytes.), which gives us 128-bit public values. Looks like I need to read up on EC systems.