How hard is it to intercept SMS (two-factor authentication)?

GSM includes some protection through cryptography. The mobile phone and the provider (i.e. the base station which is part of the provider's network) authenticate each other relatively to a shared secret, which is known to the provider and stored in the user's SIM card. Some algorithms known under the code names "A3" and "A8" are involved in the authentication. Then the data (as sent through the radio link) is encrypted with an algorithm called "A5" and a key derived from A3/A8 and the shared secret.

There are several actual algorithms which hide under the name "A5". Which algorithm is used depends on the provider, who, in turn, is constrained by local regulations and what it could license from the GSM consortium. Also, an active attacker (with a fake base station) can potentially force a mobile phone to use another variant, distinct from what it would have used otherwise, and there are not many phones which would alert the user about it (and even fewer users who would care about it).

• A5/0 means "no encryption". Data is sent unencrypted. In some countries, this is the only allowed mode (I think India is such a country).
• A5/1 is the old "strong" algorithm, used in Europe and North America.
• A5/2 is the old "weak" algorithm, nominally meant for "those countries who are good friends but that we do not totally trust nonetheless" (it is not spelled out that way in the GSM specifications, but that's the idea).
• A5/3 is the newer algorithm for GPRS/UMTS.

A5/3 is a block cipher also known as KASUMI. It offers decent security. It has a few shortcomings which would make it "academically broken", but none really applicable in practice.

A5/2 is indeed weak, as described in this report. The attack requires a fraction of a second, subject to a precomputation which takes less than an hour on a PC and requires a few gigabytes of storage (not much). There are technical details, mostly because the GSM protocol itself is complex, but one can assume that the A5/2 layer is breakable.

A5/1 is stronger, but not very strong. It uses a 64-bit key, but the algorithm structure is weaker and allows for an attack with complexity about 2^42.7 elementary operations (see this article that I wrote 12 years ago). There have been several publications which turn around this complexity, mostly by doing precomputations and waiting for the algorithm internal state to reach a specific structure; although such publications advertise slightly lower complexity figures (around 2⁴⁰), they have drawbacks which make them difficult to apply, such as requiring thousands of known plaintext bits. With only 64 known plaintext bits, the raw complexity is 2^42.7. I have not tried to implement it for a decade, so it is conceivable that a modern PC would run it faster than the workstation I was using at that time; as a rough estimate, a quad core PC with thoroughly optimized code should be able to crack it in one hour.

The size of the internal state of A5/1, and the way A5/1 is applied to encrypt data, also make it vulnerable to time-memory trade-offs, such as rainbow tables. Again, see the Barkan-Biham-Keller article. This assumes that the attacker ran once a truly massive computation, and stored terabytes of data; afterwards, the online phase of the attack can be quite fast. Details very quite a bit, depending on how much storage space you have, how much CPU power is available for the online phase, and how long you are ready to wait for the result. The initial computation phase is huge but technologically doable (a thousand PC ought to be enough); there was an open distributed project for that but I do not know how far they went.

SMS interception is still a specific scenario. It is not a full voice conversation; the actual amount of exchanged data is small, and the connection is over after a quite short time. This may limit the applicability of the attacks exposed above. Moreover, the attack must be fast: the point of the attack is to grab the secret password sent as a SMS, so that the attacker can use it before the normal user. The attacker must be quick:

• The server typically applies a short timeout on that password, such as a few minutes. SMS transmission is supposed to be a matter of a few seconds.
• The user is not patient (users never are). If he does not get his SMS within five minutes, he will probably request a new one, and a well-thought two-factor authentication system on the server would then invalidate the previous one-time password.

Things are easier for the attacker if he already broke the first authentication factor (that's why we use two-factor authentication: because one is not enough). In that case, the attacker may initiate the authentication request while the target user is blissfully unaware of it, and thus unlikely to raise any alarm if he fails to receive a SMS, or, dually, if he receives an unwanted SMS (the attacker may do the attack late at night; the attacked user will find the unwarranted SMS only in the morning, when he wakes up, giving a few hours for the attacker to enact his mischiefs).

GSM encryption is only for the radio link. In all of the above, we concentrated on an attacker who eavesdrop on data as sent between the mobile phone and the base station. The needed radio equipment appears to be available off-the-shelf, and it is easily conceived that this scenario is applicable in practice. However, the SMS does not travel only from the base station to the mobile phone. Its complete journey begins at the server facilities, then goes through the Internet, and then the provider's network, until it reaches the base station -- and only at that point does it get encrypted with whatever A5 variant is used.

How is data secured within the provider's network, and between the provider and the server which wants the SMS to be sent, is out of scope of the GSM specification. So anything goes. Anyway, if the attacker is the provider, you lose. Law enforcement agencies, when they want to eavesdrop on people, typically do so by asking nicely to the providers, who invariably comply. This is why drug cartels, especially in Mexico and Colombia, tend to build their own cell networks.

GSM Network is encrypted. But that doesn't make it bullet-proof of course. It can be compromised. However, the attacks Rook (and later in much more detail Thomas Pornin) described are very localized and requires significant effort to accomplish. They are not impossible, but very difficult. It requires breaking the GSM network in proximity of the mobile phone at the same time the SMS is sent. There is also a potential for someone at the network operator to intercept SMS. If we're talking about national-security/espionage scenarios, where a specific person is targeted and the attackers have very sophisticated means and lots of money to spend, then it is definitely possible. Pretty much the same applies to getting the seed values from your hardware token provider though.

Even if this SMS attack is successful, it might also require obtaining the username and password (assuming SMS is not the only method of authentication, but rather a 2nd component). There are other alternatives, where the user initiates the SMS message to the server, and the server can check it matched the requested challenge/token. The server can also verify the originator caller ID. Of course this too has its limitations, but if done right can provide slightly more protection theoretically.

If, as in most cases, the idea is to improve security by offering 2 factor authentication, then adding SMS into the mix dramatically improves it over standard username/password. The fact that you're using two separate communication channels (TCP/IP and GSM) makes it already more secure. As a very rough personal estimate, I would say SMS tokens are more or less on par with hardware based tokens, security wise. Of course god (or the devil) is in the detail.

While discussions about encryption are interesting, I think the key question is: are the carriers incented to care about security? I fear the answer is "no". What is their incentive to spend money securing their SMS systems? Do they even manage them or is it out-sourced? What guarantees of security do they offer? How much do you trust the people administering the servers ?

Further, this about this: If you have 100 million customers and you make it slightly harder to reset your password your helpdesk calls would go through the roof. This is why it can be so easy to take-over someone's account.

Additionally, just as you see with the Certificate Authority framework, the SMS infrastructure will be a target for attack.

I recently wrote a blog post about summarizing these points with links: http://www.wikidsystems.com/WiKIDBlog/fraudsters-defeat-poor-risk-management-not-two-factor-authentication. From a risk management standpoint, SMS auth is better than passwords, but don't count on it for long. The current attacks target financial institutions, but as the cost of attacks drop, there will be more.