I have been trying to find out more about the supposedly wonderful encryption system used in the Blackberry Messenger (BBM) system (see the earlier March article, and a more recent article on its use in the recent riots). My scepticism is because encryption is notoriously tricky. Most software types think all you need is to look up the code for an algorithm, paste it in and you are done. As a result most systems have glaring holes, which are gleefully exploited by hackers and governments.
One major, long-standing problem with encryption has been key management. Perhaps, I should start a little further back. The idea of encryption is to allow A to communicate with B in such a way that if C intercepts their messages, he is unable to make sense of them.
The earliest known cipher is supposed to be the Caesar cipher, used by Julius Caesar to communicate with his generals. The idea is to replace each letter in the message by the letter 4 further on in the alphabet. You wrap around, so Y gets replaced by C, Z by D and A by E. The snag is that once the method is suspected, it is trivial to decipher, even if you do not know whether he was using 4 or 15 letters on. There are only 25 possibilities and it takes little time to try them all (you stick to the same number on for the entire message).
People soon grasped that a good cipher needed both a well-chosen design and a key. To decipher you needed to know not just the design, but also the specific key. You could regard the 4 in the Caesar cipher as a key, but it is a lousy key, because there are only 25 possibilities (moving on 1, 2, 3, … , 25 letters – moving on 26 does not change the message!). You need a key which could be any of thousands, millions, billions or more possibilities.
The snag is that both A and B need the key. You have to change the key periodically, because C might somehow get hold of it. He is unlikely to boast about it, so the only safe thing is to keep changing the key. But now you have replaced the problem of exchanging messages safely with the problem of exchanging keys safely. You are not really much further forward.
Well, that is not quite true. You have probably done enough if you are an embassy. You can get a new key each week in a diplomatic bag brought by a trusted diplomatic courier, who keeps it with him in the aircraft cabin and is immune from inspection at customs. That key allows you to transmit and receive thousands of encoded messages during the week with reasonable safety.
Nonetheless, the solution is clearly not perfect. Four of those studying maths with me at Trinity at the end of the 60s went to work at GCHQ. I discovered much later that two of them, Malcolm Williamson and Clifford Cox, had been invented public key encryption. This used to be credited to Diffie and Hellman, who published it 1976. Williamson and Cox had discovered it a few years earlier, but GCHQ had decided it would hinder their work if it got out.
It was indeed a potential disaster for sigint. The idea is to have two different keys, E for encrypting and D for decrypting. (“Encipher” and “decipher”, or “encode” and “decode”, were the old terms, but as the whole business has migrated on to computers, the terminology has moved over to “encrypt” and “decrypt”). I keep D secret and publish E. Anyone who wants to send me a secret message just encrypts it with E. The ingenious part is that one can do this in such a way that a knowledge of E does not help in discovering D. So an interceptor can sit there with the encrypted message and the encrypting key E and still be quite unable to get anywhere.
Of course, to send you a reply, I use the key that you have published, which will be quite unrelated to the one I published (or its counterpart which I keep secret). Various schemes have been proposed of this type. The safest and best understood seems to be RSA, named after the three people (Rivest, Shamir and Adleman) who first published it in 1978. It is based on the extreme difficulty of factorising numbers whose factors are all sufficiently big. You should be able to factorise 111 in your head; 11111 should not cause you too much difficulty; 1111111 is getting distinctly tiresome without a computer. 300 digit numbers are currently beyond the capability of even supercomputers provided they have only two roughly similar sized factors.
Zimmermann’s publication caused major rows in the US. For the first time, it looked as though gangsters and Third World governments might have been given a tool to make it impossible for the NSA to intercept their communications. At that time, the relevant US laws had not caught up with developments in technology. High quality encryption software (which the NSA might have difficulty decrypting) was treated as a munition. The Arms Export Control Act (title 22, chapter 39, III, 2778) allowed the President to maintain the United States Munitions List. Items on it could not be exported without a licence. Bizarrely, the List banned the export of software, but not of the associated source code if it was printed out on paper, as opposed to transmitted electronically. This allowed Zimmermann to export PGP to Europe beyond the reach of the US courts, although he spent an uncomfortable two years under investigation by a Grand Jury.
His troubles did not end there, because R, S, A and others had filed patents which were still in force. Eventually, MIT stepped in and a fully authorised version was made freely available. Zimmermann’s text was fascinating, because he included a lengthy essay on the philosophy and mechanics of secure communications, as well as source code. I was hooked.
[Share price of RIM, the maker of the Blackberry, for the last 12 months (blue line) compared to the Dow Jones (red line). Its price has more than halved against the index.]
The Blackberry system seems to involve the following elements:
(1) each handset has a unique id (similar to a phone number), known as the PIN (made up of 8 hex characters, so just over 4 billion possible PINs);
(2) RIM (=Research in Motion Ltd, ticker RIM) maintains a series of Network Operations Centres (NOCs) around the world. Messages go from a Blackberry handset to the local cell tower of the mobile provider being used, then to the nearest RIM NOC, then to the RIM NOC nearest the recipient (if different), then to his mobile provider and thence to his handset.
According to the Wall Street Journal a year ago at the time of RIM’s row with the United Arab Emirates:
RIM said the BlackBerry network was set up so that “no one, including RIM, could access” customer data, which is encrypted from the time it leaves the device. It added RIM would “simply be unable to accommodate any request” for a key to decrypt the data, since the company doesn’t have the key. The BlackBerry network is designed “to exclude the capability for RIM or any third party to read encrypted information under any circumstances,” RIM’s statement said.
In principle, it would be possible for RIM to operate secure encryption for messaging between Blackberry handsets. One could envisage, for example, that each handset contained a unique RSA decryption key and that the corresponding encryption keys were also stored on the RIM NCOs. If user 1 wanted to send a secure message to user 2, then the RIM system would supply him (automatically) with user 2’s encryption key, the handset would RSA encrypt it and send it off. So from the moment it left the handset, only user 2 would be able to decrypt it, because only user 2 would have the appropriate decryption key. Group messages to 50 people would be fairly fiddly, because the handset would have to encrypt the message separately, using a different key, for each member of the group.
Indeed, something akin to this seems to be the approach used for Blackberry Enterprise Server (BES) systems (see p29f and p87f in the BES Security Technical Overview – pdf). The Blackberry was originally aimed at major corporate users, not kids. Each such customer would have its own BES, which would take the place of a local NOC and would handle the distribution of key pairs.
That this is not how it works for teenagers buying a Blackberry from the local store seems to get support from the fact that RIM has been able to reach satisfactory accords with authoritarian governments that want to eavesdrop on their citizens:
RIM respects both the regulatory requirements of government and the security and privacy needs of corporations and consumers.
On the other hand, all the UK police need to nail rioters communicating by BBM is to arrest one rioter with his handset. That gives them his PIN and they can then serve notice on RIM under RIPA requiring it: (1) to hand over full details of whom the rioter has called, and (2) to keep quiet about it. Repeating as necessary, they get plenty of information for a sophisticated traffic analysis. The point is that you do not need to see the actual messages to figure out who is involved and who the key players are. It is enough to see who is sending messages to large groups (directing them) and who is just responding.