[Cryptography] on brute forcing 3DES to attack SIMs

[Jerry Leichter]

On Jan 1, 2015, at 12:50 PM, ianG <iang at iang.org> wrote:
> http://threatpost.com/majority-of-4g-usb-modems-sim-cards-exploitable/110139
> 
> “To brute-force DES keys, we use a set of field-programmable gate arrays (FPGA), which became trendy for Bitcoin mining a couple of years ago and got cheaper after the hype was over,” the researchers wrote. “The speed of our 8 modules *ZTEX 1.15y board with the price tag of 2,000 Euro is 245.760 Mcrypt/sec. It is enough to obtain the key within 3 days.”
> 
> That was their fastest brute-force. If they had a partially known 3DES key, they could break it in 10 days.
The article goes on to state:  "Deploying standard processing power, like the Intel CPU (Core i7-2600k), would take roughly five years to break DES and more than 20 years to break 3DES."  Which is where my bullshit detector went off full blast.  Four times as long to break 3DES as DES?  We're talking simply brute force here; that's nonsense.  3DES has a key space 2^56 bits larger than DES, not 2^2.

Let's go back to the other claim.  They are claim about 3*10^8 encryptions/sec, or 3*24*60*60*3*10^8 ~= 4*10^6*3*10^5 ~= 10^12 encryptions in 3 days.  Using the standard approximation that 2^10 ~= 10^3, we get about 2^40 encryptions in three days.  That's about enough to break the old export 40-bit version of DES.  It's nowhere near a practical attack against full DES, much less 3DES.

Now, there's another reading of this:  Since they are European, the "." above may have been intended as a digits separator - i.e., it's 245760 Mcrypt/sec.  That gains a factor of about 10^3, or about 2^10, bring then to 50 bits of key. Using the complement property of DES, it actually has an effective key length of 55 bits, and we're talking expect time which means looking at half the keyspace, which they could do in 48 days or so.  If the speeds are for a single one of those 8 boards, they're back down to 6 days.  But that's still DES; 3DES remains way out of reach.
                                                        -- Jerry