[Cryptography] on brute forcing 3DES to attack SIMs

Michael Kjörling michael at kjorling.se
Fri Jan 2 11:42:25 EST 2015


On 1 Jan 2015 23:21 +0000, from iang at iang.org (ianG):
> On 1/01/2015 21:02 pm, Jerry Leichter wrote:
>> 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.”
>> 
>> 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.
> 
> Yes, the "." is probably a thousands separator, see the table here:

Or a bit of math. I'll admit, the "." tripped me up as well, so I ran
the numbers. All of the below is to within experimental error.

If we read "245.760 Mcrypt/sec" as 245M760 crypt/sec, then we have
done in three days:

245M/sec × 3d × 86400 sec/d ~ 63.5e6 M = 63.5e12 = 6.35e13 encryptions

If instead we read it as 245760M crypt/sec, then we have done:

245G/sec × 3d × 86400 sec/d ~ 63.5e9 M = 63.5e15 = 6.35e16 encryptions

We know that:

2^55 ~ 3.6e16

2^56 ~ 7.2e16

And of course:

6.35e16 ~ [3.6e16 .. 7.2e16]

We do know that back in 1998, 56-bit DES was brute forced in less than
three days using custom hardware costing $250k (that's the EFF DES
Cracker). Working backwards, Deep Crack tried some 1.8e11 keys per
second (or about 9.63e7 keys per second per cracker chip, roundable to
1e8 keys per second per chip).

Which of course means that brute-forcing single-DES in three days
today (by trying 2.45e9 keys/second), on almost any class of hardware,
is certainly not a major achievement; only about one order of
magnitude faster after 15 years of technology advancement.

Hence, nothing to see here.

-- 
Michael Kjörling • https://michael.kjorling.semichael at kjorling.se
OpenPGP B501AC6429EF4514 https://michael.kjorling.se/public-keys/pgp
                 “People who think they know everything really annoy
                 those of us who know we don’t.” (Bjarne Stroustrup)


More information about the cryptography mailing list