February 23, 2015

NSA and GCHQ stealing SIM card keys: a few things you should know

(Updated: February 27, 2015)

Last Thursday, February 19, the website The Intercept broke a big story about how NSA and GCHQ hacked the security company Gemalto in order to acquire large numbers of keys used in the SIM cards of mobile phones.

The story has quite some background information about how these keys are used and how NSA and GCHQ conducted this operation. But as we have often seen with revelations based upon the Snowden-documents, media once again came with headlines like "Sim card database hack gave US and UK spies access to billions of cellphones", which is so exaggerated that it is almost a scandal in itself.

Instead, analysing The Intercept's article and the original documents leads to the conclusion that the goals of this operation were most likely limited to tactical military operations - something that was completely ignored in most press reports. Also there is no evidence that Gemalto was more involved in this than other SIM card suppliers.

To what extent was Gemalto involved?

According to The Intercept, NSA and GCHQ planned hacking several large SIM card manufacturers, but in the documents we find only one for which this was apparently successful: Gemalto. Other documents merely show that GCHQ wanted to "investigate Gemalto" "for access to Gemalto employees" "to get presence for when they would be needed".

An internal GCHQ wiki page from May 2011 lists Gemalto facilites in more than a dozen countries, like Germany, Maxico, Brazil, Canada, China, India, Italy, Russia, Sweden, Spain, Japan and Singapore, but also without explicitly saying whether or not these were successfully hacked.

One report and a few slides from a presentation that was not fully disclosed mention large numbers of SIM card keys that had been collected, but this is not specifically linked to Gemalto. Although Gemalto is the largest manufacturer, it seems likely these data were also collected from other companies, like Bluefish, Giesecke & Devrient, Oberthur, Oasis, Infineon, STMicroelectronics, and Morpho.

Therefore, we actually don't know to what extent NSA and GCHQ used the access they apparently had to Gemalto's network, and it is definitely not correct to say that all 2 billion SIM cards that Gemalto produces every year were compromised by this hack.

And given the fact that other SIM card suppliers were targeted and/or hacked too, one wonders why The Intercept didn't left out the name of Gemalto. Because now its competitors profit from not being named, while Gemalto shares already had a huge drop on the stock market.

On February 25, Gemalto came with a press release in which results of its investigation into the alleged hack were presented. Gemalto concluded that NSA and GCHQ probably "only breached its office networks and could not have resulted in a massive theft of SIM encryption keys". The report also says Gemalto never sold SIM cards to four of the twelve operators listed in the GCHQ documents, in particular to the Somali carrier, and that in 2010-2011, most operators in the targeted countries were using the vulnarable 2G networks, mostly with prepaid cards which have a very short life cycle, typically between 3 and 6 months.

The Netherlands

Gemalto is a digital security company providing software applications, secure smart cards and tokens and is also the world’s biggest manufacturer of SIM cards. It's essentially a French company, but it has some 12.000 employees in 44 countries all over the world.

The Gemalto headquarters are officially in Amsterdam in the Netherlands, which made Dutch media claiming that "NSA hacked a company in the Netherlands". This was rather premature, since the two Dutch locations of Gemalto seem not to be likely targets in this case.

The Amsterdam headquarters is very small, consisting of only some 30 people. The reason they are in Amsterdam is apparently mainly because the Dutch capital was already the seat of Axalto, one of Gemalto's predecessors, and because the company wanted access to the Amsterdam stock exchange.

Unnoticed by Dutch national media is the fact that Gemalto also has a plant in the city of Breda, where, according to an unrelated press report from last year, (only) bank cards are personalised. This plant also has a customer service team, but strangely enough Breda isn't in the list of locations on Gemalto's website.

The plant of Gemalto in the southern Dutch city Breda
(photo: Tom van der Put/MaRicMedia)

Also interesting is that last month, Gemalto acquired the US manufacturer of security products SafeNet. This company, founded in the late 1980s by former NSA officials, not only makes encryption devices used by commercial companies and banks all over the world, but also the KIV-7 link encryptor, which is used by the US Army, as well as the Enhanced Crypto Card (KSV-21), which provides the encryption functions for the US government's STE secure telephone.

How does the SIM card key work?

SIM cards, produced by companies like Gemalto, have a microchip which among other data includes a unique 128 bit Authentication Key, also known as "Ki". A copy of this key is given to the phone provider, so when a phone call is made, this key number can be used to make sure the handset connects to a valid provider, and the provider knows it connects to a handset that belongs to a known customer.

The Intercept's report suggests that this Ki number is also used as the encryption key to protect the subsequent communications, but in reality this is a bit more complex. Here's how it works for 3rd Generation (UMTS) networks:

1. After a handset connects to the base station, the latter sends the handset a 128 bit random number, a 48 bit sequence number and an authentication token.

2. The chip in the SIM card combines the Ki number with the random number and the sequence number to also calculate an authentication token and a response number, which are used to authenticate the network and the handset, respectively.

3. By combining the Ki number with the random number, the SIM card chip also calculates the:
- 128 bit Confidentiality Key (CK) for encrypting messages
- 128 bit Integrity Key (IK) for checking the integrity of messages
4. The actual (voice) data are then encrypted through the f8 algorithm (which is based upon the KASUMI block cipher) using the Confidentiality Key.

5. For additional security, both the Confidentiality Key and the Integrity Key have a limited lifetime. The expiration time is variable and send to the handset after establishing a connection.

Although for the actual encryption key CK, the Ki number from the SIM card is mixed with a random number, this provides no extra security: the base station sends this random number to the handset over the air unencrypted, so it can be intercepted easily by anyone.

Eavesdroppers would therefore only need the SIM card Ki to recreate the encryption key and use that to decrypt the conversation (see also this US Patent for a "Method of lawful interception for UMTS").

Why were these SIM card keys collected?

The press reports, speaking in general terms of "unfettered access to billions of cellphones around the globe", suggest that everyone's mobile phone could now be at risk of being intercepted by NSA or GCHQ.

One important thing they forgot, is that one only needs to steal SIM card keys when you are trying to intercept mobile phone traffic when it travels by radio between the handset and the cell tower. Only that path is encrypted.

Once the communications arrive at the provider's network, they are decrypted and sent over telephone backbone networks to the cell tower near the receiving end as plain text. It's then encrypted again for the radio transmission between the cell tower and the receiving handset.

As we know from previous Snowden-leaks, NSA and GCHQ have vast capabilities of filtering fiber-optic backbone cables that are likely to contain communications that are of interest for military or foreign intelligence purposes. The big advantage here is that on those backbone cables there's no encryption (although people can use end-to-end encryption methods themselves).

Therefore, the SIM card keys are only needed when NSA and GCHQ want to listen in or read traffic that is or has been intercepted from the wireless transmission between a handset and a cell tower. This narrows down the field where these keys can be useful substantially.

Tactical military operations

Intercepting the radio signal of mobile phones needs to be done from rather close proximity. To do this, the NSA uses StingRay and DRT devices, which are highly sophisticated boxes that in a passive mode are capable of detecting and intercepting the radio transmissions of multiple cell phones. In an active mode they can mimic a cell tower in order to catch individual phone calls and as such they are better known as IMSI-catchers.

These devices are widely used by the NSA and the US military in tactical ground operations, like in Afghanistan and previously in Iraq, as well as in other crisis regions. StingRays and DRT boxes can be used as a manpack, in military vehicles, but also aboard small signals intelligence aircraft like the C-12 Huron. Surveillance drones also have similar capabilities.

A Prophet Spiral Humvee which uses DRT devices
for collecting radio and cell phone signals

This military, or at least anti-terrorism purpose is confirmed by a disclosed slide which shows that Kis for mobile networks from Somalia, Kuwait, Saudi Arabia, Afghanistan, Iran and Bahrain were found among collected data.

A GCHQ report that was also published as part of The Intercept's story says that key files from "Somali providers are not on GCHQ's list of interest, [...] however this was usefully shared with NSA", which clearly shows that both agencies were looking for keys from specific countries.

The report also says that during a three month trial in the first quarter of 2010, significant numbers of Kis were found for cell phone providers from Serbia, Iceland, India, Afghanistan, Yemen, Iran, Tajikistan and Somalia, which is shown in this chart:

According to the report, this chart reflects "a steady rate of activity from several networks of interest", which again indicates that GCHQ is specifically looking for keys for countries where the US and the UK are involved in military operations.

The same reports says that Iceland appearing in this list was unexpected, but Dutch newspapers guessed this could be explained by the fact that in 2010, Julian Assange and other people related to WikiLeaks were staying there.

One also wonders why The Intercept didn't trace the companies that in 2010 and 2011 provided the SIM cards to the countries mentioned in the GCHQ report. The fact that SIM keys for those countries were collected, seems a strong indication that the security of those suppliers was apparently weak.

Eavesdropping in foreign capitals

Remarkably, the use of SIM card keys for tactical military operations is completely ignored by The Intercept, even though this is probably the main purpose (which was also expressed by at least two security experts). The Intercept does however claims that such keys would be useful to eavesdrop on mobile phone traffic somewhere else:

The joint NSA/CIA Special Collection Service (SCS) has eavesdropping installations in many US embassies, and because these are often situated in the city center and therefore near a parliament or government agencies, they could easily intercept the phone calls and data transfers of the mobile phones used by foreign government officials.

With the current UMTS (3G) and LTE (4G) mobile networks using encryption that is much harder to crack than that of the older GSM network, having the SIM card keys would make it easy to decrypt already collected mobile communications, as well as listing in to them in real-time.

A 16 port IMSI catcher from the Chinese manufacturer Ejoin Technology

As easy it may be to decrypt conversations when having the key, the more difficult it seems to get hold of keys that are useful for this purpose. SIM cards are shipped in large batches of up to several hundred thousand cards and while it is known to which provider in which country they go, one cannot predict in whose phone the individual cards will eventually end up.

So when NSA and GCHQ are stealing large numbers of keys, they have to wait for some of them ending up by people that are on their target lists - which really seems a very small chance. This method is also useless against people using an old SIM card, which could be the case for German chancellor Merkel, who has a phone number that was already used in 1999. For these kind of targets it would be much more efficient to hack or tap into local telephone switches.

The way to make it work would be to "collect them all" and create a database of keys that will eventually cover every newly assigned phone number. But in one of the documents, GCHQ notices that large SIM suppliers increasingly use strong encryption for their key files, which will make it hard to achieve such a full coverage.

This is another reason, why stealing SIM card keys is most likely focussed on war zones: over there, very large amounts of phone calls and metadata are collected, which, given the large number of suspects and targets over there too, makes much better chances of finding keys that are actually useful. But still, stealing these keys looks not like a very efficient method.

Could these hacking operations be justified?

This brings us to the question of how justified this method of stealing SIM card keys could be. The fact that NSA and GCHQ are hacking commercial telecommunication and security companies is seen as one of the biggest scandals that have been revealed during the Snowden-revelations.

It's not only because of breaking into their networks, but also because for this, the communications of specific employees like system administrators are intercepted to acquire the passwords and usernames for their Facebook-accounts, despite the fact that they themselves aren't a threat to the US or the UK.

They are targeted not as an end, but as means in order to get access to the communications of other targets elsewhere. These ultimate targets could maybe justify these means, but without knowing what the actual goals are, it's difficult to come with a final judgement.

Although this kind of hacking affects innocent civilians, it's still very focussed. According to The Intercept, "In one two-week period, they accessed the emails of 130 people associated with wireless network providers or SIM card manufacturing and personalization" - which is a rather small number given that Gemalto alone has some 12.000 employees.

Targeting companies and organizations like Swift, Belgacom and Gemalto should not have come as a complete surprise. Nowadays internet and telecommunication providers have become similar of interest for national security as military contractors and top technological research institutions have always been.

This is also reflected by the last of the 16 Topical Missions in the NSA's Strategic Mission List from 2007:

"Global Signals Cognizance: The core communications infrastructure and global network information needed to achieve and maintain baseline knowledge.
Capture knowledge of location, characterization, use, and status of military and civil communications infrastructure, including command, control, communications and computer networks: intelligence, surveillance, reconnaissance and targeting systems; and associated structures incidental to pursuing Strategic Mission List priorities.
Focus of mission is creating knowledge databases that enable SIGINT efforts against future unanticipated threats and allow continuity on economy of force targets not currently included on the Strategic Mission List."

Links and Sources
- Motherboard.vice.com: Did the NSA Hack Other Sim Card Makers, Too?
- NRC.nl: Simkaartsleutels vooral van belang bij afluisteren in Midden-Oosten
- Tweakers.net: Gemalto: geen sim-sleutels buitgemaakt bij aanval geheime diensten
- Reuters.com: Hack gave U.S. and British spies access to billions of phones: Intercept
- Crypto.com: How Law Enforcement Tracks Cellular Phones
- Presentation about Network Security: GSM and 3G Security (pdf)
- Matthew Green: On cellular encryption
- GCHQ's aspirations for mobile phone interception: 4 slides + 2 slides
- This article appeared also on the weblog of Matthew Aid

February 12, 2015

Snowden would not have been able to legally "wiretap anyone"

(UPDATED July 5, 2017)

During his very first interview, former NSA contractor Edward Snowden pretended that he, sitting behind his desk "certainly had the authorities to wiretap anyone, from you, or your accountant, to a federal judge, or even the President if I had a personal e-mail".

Right from the beginning, intelligence experts doubted that individual NSA analysts would have such far-reaching powers. By looking at the legal authorities and procedures that regulate NSA's collection efforts, it becomes clear that it is highly unlikely that Snowden, or other analysts could have done that in a legitimate way.

Targeting US citizens under FISA authority

The National Security Agency (NSA) collects foreign signals intelligence outside the US, but in a few special cases, it is also allowed to collect data about US citizens or to collect data inside the US. This is shown in the following decision tree:

Diagram with a decision tree showing the various legal authorities
under which NSA can collect Signals Intelligence (SIGINT)
(click to enlarge)

In the interview, Snowden was talking about wiretapping ordinary US citizens as well as US government officials. According to the Foreign Intelligence Surveillance Act (FISA) from 1978, the NSA is only allowed to monitor the communications of such US citizens, US residents or US corporations when they are suspected of espionage or terrorism.

If NSA thinks that's the case, then they have to apply for an individual warrant from the Foreign Intelligence Surveillance Court (FISC) by showing that there is probable cause that the intended target is an agent of a foreign power (section 105 FISA/50 USC 1805), or associated with a group engaged in international terrorism. Depending on the type of surveillance, the FISC then issues a warrant for a period of 90 days, 120 days, or a year.

Acquiring an individual FISA warrant

So, when Snowden really had the authority to wiretap ordinary Americans and US government officials even up to the President, then he would have had to provide probable cause that these people were either foreign agents or related to terrorist groups.

For the President this would only be imaginable in films or television series, and it would only apply to very few other Americans. In other cases the NSA would and will not get a FISA warrant to eavesdrop on US citizens or residents.

Snowden often said that he sees the FISA Court as a mere "rubber stamp" because it approves almost all requests from the intelligence agencies. However that may be, obtaining an individual FISA warrant isn't easy: a request needs approval of an analyst's superior, the NSA's general counsel, and the Justice Department, before it is presented to the FISA judge.*

Collection under section 702 FAA

Maybe some people would ask: wouldn't it be easier to target US persons through the PRISM program, under which NSA collects data from major US internet companies like Facebook, Google, Yahoo, Microsoft?

The answer is no, despite the fact that PRISM is governed by section 702 of the FISA Amendments Act (FAA), which was designed to collect data faster and easier. As such, section 702 was enacted in 2008 to legalize the notorious warrantless wiretapping program, authorized by president George W. Bush right after the attacks of 9/11.

But what many people don't realize, is that the special authority of section 702 FAA can only be used to collect communications of non-US persons located outside the United States.

The NSA uses section 702 not only to gather data through the PRISM program, but also by filtering internet backbone cables operated by major US telecommunication providers, in order to grab the communications associated with specific e-mail addresses. This is called Upstream collection.

(click to enlarge)

Section 702 FAA certifications

What makes section 702 FAA collection faster is that instead of an individual warrant from the FISA Court, NSA gets a general warrant for some specific topics, which is valid for one year.

For this, the US Attorney General and the Director of National Intelligence (DNI) annually certify that specific legal requirements for the collection of time-sensitive and higher volumes of data have been met and how these will be implemented.

These certifications are then reviewed by the FISA Court to determine whether they meet the statutory requirements, like hiding names and addresses of US citizens when their communications come in unintended. The court then issues an order that approves the certification.

Until now, we know of section 702 FAA certifications for three topics:
- Foreign Governments (FG, Certification 2008-A, including cyber threats?)
- Counter-Terrorism (CT, Certification 2008-B)
- Counter-Proliferation (CP, Certification 2009-C)

These certifications include some general procedures and specific rules for minimizing US person identifiers. They do not contain lists of individual targets. Maybe this contributed to Snowden's idea that analysts are allowed to select targets all by themselves. But even then, this only applies to foreign targets and only to a few specific categories.

Dual authorities

In a report by The Washington Post from July 5, 2014, it was said that Snowden, in his final position as a contractor for Booz Allen at the NSA’s Hawaii operations center, had "unusually broad, unescorted access to raw SIGINT under a special ‘Dual Authorities’ role", which reportedly refers to both section 702 FAA (for collection inside the US) and EO 12333 (for collection overseas).

Those two authorities allowed him to search stored content and initiate new collection without prior approval of his search terms. "If I had wanted to pull a copy of a judge’s or a senator’s e-mail, all I had to do was enter that selector into XKEYSCORE", so he did not need to circumvent [access] controls, Snowden said to the Post.

So, when Snowden apparently had the 702 FAA and EO 12333 authorities, this means he wasn't authorized to target American judges or senators, in the sense of initiating real-time wiretapping, because for that the traditional FISA authority and a warrant from the FISC is needed. It looks like he confirms this by saying "If I had wanted to pull a copy of a judge’s or a senator’s e-mail", which sounds more like pulling such an e-mail from a database.

This also seems to be confirmed by the fact that Snowden points to XKeyscore for getting such e-mails. XKeyscore is mainly used to search data that already have been collected in one way or another, particularly at access points outside the US. The common way to start new surveillances is through the Unified Targeting Tool (UTT, see below).

Backdoor searches

Indeed there's a legal way to search for communications of US persons in data that have already been collected: according to an entry in an NSA glossary published by The Guardian in August 2013, the FISA Court on October 3, 2011 allowed using certain US person names and identifiers as query terms on data already collected under 702 FAA:

This became known as "back-door searches". These queries might be questionable, but unlike the term "back-door" suggests, they are not illegal, as the practice was approved by the FISA Court. In a letter to senator Wyden from June 2014, DNI Clapper revealed that not only NSA, but also CIA and FBI are allowed to query already collected 702 FAA data in this way.

In August 2014, former State Department official John Napier Tye revealed that NSA is also allowed to use US person names to query data collected under EO 12333, but only those that have been approved by the Attorney General and for persons considered to be agents of a foreign power.

Backdoor search approvals

Clapper explained that these backdoor queries are subject to oversight and limited to cases where there is "a reasonable basis to expect the query will return foreign intelligence". Querying by using US person identifiers is only allowed for data from PRISM, not from Upstream collection. In 2013, NSA approved 198 US person identifiers to be queried against the results of PRISM collection.

The PCLOB report (pdf) about 702 FAA operations says that "content queries using U.S. person identifiers are not permitted unless the U.S. person identifiers have been pre-approved (i.e., added to a white list) through one of several processes, several of which incorporate other FISA processes".

The NSA's Minimization Procedures from October 2011 also say that US person identifiers may only be used as query terms after prior internal approval (as is the case with such queries under EO 12333).

For such searches, NSA for example approved identifiers of US persons for whom there were already individual warrants from the FISA Court under section 105 FISA or section 704 FAA. US person identifiers can also be approved by the NSA’s Office of General Counsel after showing that using that US person identifier would "reasonably likely return foreign intelligence information". All approvals to use US person identifiers to query content must be documented.

Circumventing official procedures

So far, we examined the legal options for analysts to get access to American e-mails, but in an interview from June 10, 2013, Glenn Greenwald explained that the "authority" Snowden was talking about, was not an authority in a legal sense.

According to Greenwald, Snowden meant that "NSA have given [analysts] the power to be able to go in and scrutinize the communications of any American; it may not be legal, but they have the power to do it".

So it may not be legally allowed that "any analyst at any time can target anyone, any selector, anywhere", but they may have the technical capability to do so. In other words, wiretapping anyone is only possible when analysts (intentionally) circumvent the official procedures and safeguards.

In this interpretation, Snowden apparently warned against the risk that individual analysts could misuse their power, which contradicts his claim earlier on in the interview, saying he that the whole agency "targets the communications of everyone" and then ingests, filters, analyses and stores them.

Unified Targeting Tool

Illegally intercepting American e-mails by circumventing official procedures could be conducted by manipulating targeting instructions given through the Unified Targeting Tool (UTT), which is a webbased tool that is used to start the actual collection of data.

A rogue analyst could for example confirm that there's a FISA warrant, when there's not, or provide a fake foreigness indicator, so someone could be targeted under the authority of Executive Order 12333, which doesn't require the procedure of acquiring a FISA court approval.

A rare screenshot of the Unified Targeting Tool (UTT), which shows some of the
fields that have to be filled in. We see that data about a "FAA Foreign
Governments Cert." is missing and therefore not valid to task (see below),
and also a drop down menu with various Foreigness Factors.

Unfortunately no manual for this tool has been disclosed, although that would have been useful to learn more about internal safeguards to prevent misuse. The NSA itself also didn't release such documents, which could have contributed to more trust in the way they actually operate.

Targeting procedures

We have no details about the NSA's internal procedure for intercepting individual US citizens, but we do know about the process for collection under the PRISM program.

As PRISM is used for collecting data about foreigners, it can be considered somewhat less restrictive than collecting data about US persons, for which there may be some extra safeguards and checks. The PRISM tasking process is shown in this slide:

Slide that shows the PRISM tasking process
(click to enlarge)

We see that after the analyst has entered the selectors (like a target's phone number or e-mail address) into the UTT, this has to be reviewed and validated by (in this case) either the FAA adjudicators in the S2 Product Line, or the Special FISA Oversight unit.

A final review of the targeting request is conducted by the Targeting and Mission Management unit. Only then the selectors are released and put on lists which the FBI presents to the various internet companies, who will then pull the associated communications from their servers and systems.

For targeting foreigners on collection systems outside the US (which is governed by EO 12333), there are less restrictions, but also this is still not completely at the will of individual analysts. At least every eavesdropping operation has to be in accordance with the goals set in the NSA's Strategic Mission List and other policy documents.


Nonetheless, recently declassified NSA reports to the president's Intelligence Oversight Board (IOB) show that there have been cases in which there was an abuse of the collection system, either wilfully or accidentally. The majority of incidents both under FISA and EO 12333 authority occured because of human error.

It shows that despite the safeguards, some unauthorized targeting and querying can still happen, but also that the internal oversight mechanisms detected them afterwards, with the selectors involved being detasked, the non-compliant data being deleted and the analysts being counseled.


Snowden talked as if it would be easy for NSA analysts to wiretap anyone, but as we have seen, the official procedures do not authorize targeting US persons. He apparently did have the authority to use US person identifiers for querying data that were already collected.

But contrary to what Snowden said, these queries are only allowed after prior approval, which makes it highly unlikely that e-mail addresses from American judges or senators, let alone from the President would make it through.

Without an easy legal way, Glenn Greenwald tried to rescue Snowden's claim by saying that it wasn't about legal authorities, but about the technical capabilities that enable NSA analysts to access American e-mails, whether that would be legal or not.

Internal NSA reports do show that it is possible to enter incorrect or unapproved e-mail addresses into the collection system, but also that most of these cases are (afterwards) detected by oversight systems.

(Edited after adding Greenwald's interpretation of Snowden's words and adding the non-compliance incidents. Also added an addendum about Snowden's authorities based upon a 2014 report by The Washington Post, and added an explanation about the back-door searches)

Links and Sources
- Privacy and Civil Liberties Oversight Board: Section 702 Program Report (pdf)
- Webpolicy.org: Executive Order 12333 on American Soil, and Other Tales from the FISA Frontier
- Stanford Law Review: Is the Foreign Intelligence Surveillance Court Really a Rubber Stamp?
- The Guardian: The top secret rules that allow NSA to use US data without a warrant
- EmptyWheel.net: Postings about section 702 FAA
- Robert S. Litt, ODNI General Counsel: An Overview of Intelligence Collection
- Related documents:
  - President Policy Direction (PPD) 28 Section 4 Procedures (pdf) (2015)
  - Foreign Intelligence Surveillance Act - Summary Document (2008)

In Dutch: Meer over het wetsvoorstel voor de Tijdelijke wet cyberoperaties