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 242.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 240), 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 242.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.