Two historical documents on traffic analysis

The NSA has kindly declassified two classic historical documents from the NSA Technical Journal on traffic analysis:

• Introduction to Traffic Analysis– April 1958 – Vol. III, No. 2 by Lambros D. Callimahos
• Chatter Patterns: A Last Resort– October 1957 – Vol. II, No. 4 by W. E. Stoffel

The first document is an extract from the classic Military Cryptonalytics, and contains the basics necessary to solve the Zendian Problem exercise. The second deals with linkability of operators, when traffic analysis countermeasures are deployed, thought their chatter habits.

Detecting suspicious call patterns

Ian Brown brought my attention to a very interesting article from Daniel Soar in the London Review of books on the traffic analysis of mobile phone calls to detect suspicious activity and perform target selection for Lawful Interception. A particularly spicy bit:

“[…] Of the 50 million subscribers ThorpeGlenprocessed, 48 million effectively belonged to ‘one large group’: they called one another, or their friends called friends of their friends; this set of people was dismissed. A further 400,000 subscriptions could be attributed to a few large ‘nodes’, with numbers belonging to call centres, shops and information services. The remaining groups ranged in size from two to 142 subscribers. Members of these groups only ever called each other – clear evidence of antisocial behaviour – and, in one extreme case, a group was identified in which all the subscribers only ever called a single number at the centre of the web. This section of the ThorpeGlen presentation ended with one word: ‘WHY??’ […]”

What is of further interest is that Daniel Soar finds intuitive that patterns of movement or behaviours would  link even “fresh” pay-as-you-go phone to profiles of established users. This is one key finding of our recent paper about Identification via Location-Profiling in GSM Networks. In particular he describes a product that may already be doing something similar:

“ThorpeGlen has a solution for that too. It also sells ‘profiling’ systems, which measure the behaviour pattern of an individual subscriber and, using statistical analysis, determine whether that same pattern is now appearing from another source. In other words, if your terrorist gets a new phone you’ll still know it’s him. If he keeps the same phone and starts changing his pattern, then he’s about to blow up Jakarta International Airport.”

Are location data personally identifiable?

A friend of mine recently dropped his phone in water, and found that he lost all his SMS messages for the last month. I advised him to use his subject access rights under the Data Protection Act 1998 and ask his phone company “Three” for the records of calls, SMS messages as well as locations of the phone (just for good measure). The results were quite unexpected.

Here is the answer he got back (edited to protect identities) with some added emphasis:

Dear Mr X,

Thank you for your below email.

Please be advised that we do not disclose details of incoming calls or texts unless required under a Court Order.

Please also be advised that location data does not constitute ‘Personal Data’ as defined under the Data Protection Act 1998 (personal data is information which relates to a living individual who can be identified from that data).

I can confirm that we have no solely automated decision making processes in place. Our credit checking system is not solely automated and requires manual intervention.

If you require details of your outgoing calls or texts (we do not retain the content of text messages) I would be grateful if you would forward proof of your identity and a cheque for £10 made payable to Hutchison 3G UK Ltd. A photocopy of your passport or photo drivers licence would be acceptable proofs of ID. Please send this to:

Data Protection and Privacy Officer
H3G UK Ltd
Star House
20 Grenfell Road
Maidenhead
Berkshire
SL2 2NE

Kind regards

Yours sincerely

Rhian T.
Compliance Executive
Legal
Hutchison 3G UK Ltd

This answer is very surprising. Three does not state that they do not hold the data relating to incoming calls or text messages, but simply that they are not happy to provide them — with no further explanation as to why. Similarly the fact that there is a human in the loop of their credit decision processing (maybe just pressing “OK” at some stage) seems to shield them from the burden of disclosing anything about their processing of the data.

Yet what is most interesting is the statement that location data is not personally identifiable. First, in the case of a phone operator this is simply not true. They hold all necessary records to link a particular record describing the location of a handset, to a physical person. Yet, most interestingly, recent work by myself and collaborators in COSIC, Leuven, focused on showing that even coarse grained anonymized location data can be quickly and efficiently linked back to a physical person. The reference, link and abstract are below for those interested in reading more.

• Yoni De Mulder, George Danezis, Lejla Batina and Bart Preneel. Identification via Location-Profiling in GSM Networks. Workshop on Privacy in the Electronic Society ( WPES 2008 ), Alexandria, Virginia, USA.
  
  Abstract: As devices in a cellular network move, they register their new location with cell base stations to allow for the correct forwarding of data. We show it is possible to identify a mobile user from these records of movement within the network and a pre-existing location profile, based on previous movement. Two different identification processes are studied, and their performances are evaluated on real cell location traces. The best of those allows for the identification of around 80$\%$ of users. We also study the misidentified users and characterise them using hierarchical clustering techniques. Our findings highlight the difficulty of anonymizing location data, and firmly establish they are personally identifiable.

[Update: URL of paper is now working.]

A quick fix for Minx

Last month I attended the Privacy Enhancing Technologies ( PET 2008 ) Symposium in Leuven, Belgium. The programwas fantastic, with a strong focus on anonymous communications, and many papers on traffic analysis. The associated HotPETS event, was also very fun, with plenty of time for discussion, and the added advantage that all the papers are on-line.

A paper that had to catch my attention was entitled “Breaking and Provably Fixing Minx” by Erik Shimshock, Matthew Staats, and Nicholas Hopper, that shows an attack against the Minx scheme Ben Laurie and myself had proposed back in 2004. Minx is a cryptographic packet format to be used by anonymous remailers (or mixes) for high-latency, email like, communication. It was designed to be space efficient, meaning that we radically cut down on the padding and redundancy within the packet, and used raw RSA.

That last use of raw RSA proved to be a bridge too far: recent results show that all bits of RSA are hardcore, meaning that if you do not know the key you cannot guess them. Sadly the inverse is also true, and if you can know even a single bit of the plaintext with non-negligible advantage, there is a polynomial time algorithm to extract the key.