GSM Hack Shows What Happens When You Use Weak Keys

If you saw the article this week on the GSM telephone hack and did not make a connection to protecting your cardholder data, shame on you.  One of the things that security people need to do is to look around and see all of the potential threats that might exist.  This sometimes means thinking like the people that are out to attack your organization.  So, what does this week’s announcement that GSM encryption has been broken?  Everything, if you are relying on encryption to protect your cardholder data.

What the researchers proved this week is that, no matter how strong your encryption algorithm, if the key length is not long enough, it is very easy to break.  The initialization key for GSM is a 64-bit key (8 characters) of which the first 10 bits are set to zero, meaning that the initialization key is actually only 54-bits long.  All remaining keys are 114-bits long (14.25 characters), the same length as the data stream it protects.  To make things better yet, the key is used to exclusive OR (XOR) the data stream it is protecting.  To strengthen the encryption method, the key is adjusted at pre-determined intervals.

There have been a number of attacks generated against the GSM encryption technique since it was made public in 1994.  However, what makes this attack unique is that the researchers used a cluster of computer systems to generate a ‘rainbow table’ of approximately 2TB in size.  With such a table, it is child’s play to break the encryption.

I am sure there are some of you reading this and are saying, “So what?”

The first ‘so what’ is that this issue is why the PCI DSS requires you to use a recognized encryption algorithm such as AES, TwoFish, BlowFish or similar algorithm approved and reviewed by a body such as the US National Institute of Standards and Technology (NIST).  The algorithm used for securing GSM was just barely strong enough when it was originally introduced in 1988.  However, given the limits of the processors in cell phones at that time, it was the best they could handle and maintain call quality.  A lot has changed since 1988 in regards to processor capability and encryption.  Unfortunately, the cell phone industry did not keep up with the advances in encryption algorithms and ended up with a not so secure solution.

The second ‘so what’ is that this is why the PCI DSS requires the use of strong encryption keys.  The purpose of strong keys is to make the generation of a ‘rainbow table’ as impossible as possible.  If you use 8 character long keys using upper and lower case characters along with numerical and special characters, that is slightly less than 6.1 quadrillion possible key combinations.  Generating that number of keys is not a big deal with today’s multi-threaded microprocessors running in a cluster.  Worse yet, enterprising programmers have provided methods for generating such keys using video processors and video game units in clusters.  The bottom line is that it only takes time to generate a rainbow table and that is exactly what attackers have a lot of.  As a result, if you think that generating strong keys is a waste of time, think again.

So, what are the take aways from this discussion?

  • Use a recognized and proven encryption algorithm.  If the algorithm has not been through a rigorous examination by an independent body such as NIST, do not use it.
  • Yes, 3DES can still be used as long as you use the 168-bit variant and strong keys.  But, if you have the option of using AES instead of 3DES, why use 3DES?  NIST has said it is just a matter of time before 168-bit 3DES is cracked.  Why put your organization at risk?
  • Use strong keys consisting of a minimum of 32 characters (256-bits) or greater with split knowledge.  Make sure that the keys use upper and lower case alphabetic characters as well as numeric and, if possible, special characters.  Use one of the random character generators available on the Internet to generate these character strings.  They may not be perfectly random; but they are good enough for this purpose.

2 Responses to “GSM Hack Shows What Happens When You Use Weak Keys”

  1. 1 Gourmet
    January 5, 2010 at 6:32 AM

    Firsteval, we all whould remember why the GSM session key (Kc) is so weak: it was a “request” from the US governement (thru the DoC if you prefer).
    The GSM consortium, back in 1988, wanted to implement a strong key as the session key for GSM communicationq (key generated thru A8 algorithm).
    But the US said, approx: either you reduce the key to ~50 bits either you’ll never reach the US market.
    It was so bizarre to see that the Kc length was 64 bits but 10 of these bits were systematically set to 0 leading to an effective length of 54 bits!
    The history is then well known: the GSM never reached the US market (that chose another very very weak technology) until GSM phase 3 (UMTS).

    Secondly, this “affair” is not very new. Back in 1999, the crack of the A5/1 was already published with the poor means of this old time: http://www.iol.ie/~kooltek/gsmpaper.html and

    Thirdly, I have to say that during security conferences that occured in the 1996-1998 frame, people were talking, aside of these conference, about using commercial equipments able to listen to GSM conversations in realtime. Which one ? I don’t know. And maybe they didn’t use the decipheration of A5/1 but the SIM cloning that was reaveled at the same time: http://www.isaac.cs.berkeley.edu/isaac/gsm.html

    Fourthly, A8 is now retired leaving place to more robust and more reviewed algorithms under the 3GPP umbrella but, effectively, A5 remains.


  2. January 1, 2010 at 1:57 PM

    Sweet hack, gotta love it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Welcome to the PCI Guru blog. The PCI Guru reserves the right to censor comments as they see fit. Sales people beware! This is not a place to push your goods and services.

December 2009

%d bloggers like this: