Allicient

Well, it’s finally happened: the elements necessary to build a computer setup capable of passively decrypting GSM have been cobbled together by cryptographer/computer scientist Karsten Nohl. It has been known for some years now that A5/1 – the stream cipher used to protect most GSM calls – was weak, c.f. the wikipedia page on A5/1 for a list of results. Practical attacks were considered slightly more difficult due the requirement for radio equipment and computation time. So despite expensive commercial products being available for a long time, there hasn’t been anything concrete that the general public can try. Until now.

Unveiled at the Chaos Communications Congress, he presents a solution utilising easily available open source software, inexpensive radio equipment and recently available rainbow tables. The combination means that it is now possible to capture and decrypt packets with a high degree of certainty.

What does this mean? It means that monitoring mobile calls and text messages is no longer limited to the Police, Government and criminal gangs that can afford the existing equipment retailing at around £20,000 – any spotty teenager that can afford around £1,500 worth of equipment can in theory intercept your calls. And make calls from your number, and fake SMS messages from your number, etc.

The bright shining light that the GSM consortium had in mind to replace A5/1 – A5/3, which is really just the Kasumi block cipher – is not going to help. Well, on a cursory reading it seems to depend on who you ask: the documentation I had previously read suggested the protocol was changed and that although Kasumi has theoretical breaks, it would be beyond the boundary of a practical attack (where have we heard that before); the presentation slides provided by Nohl however suggest that the mobile handset can be forced to encrypt packets using A5/1 with the same key allowing key recovery, and that Kasumi is fairly weak. Perhaps I’m just mixing up 3G specifications with the older GSM specs… if anyone actually knows the details here I’d appreciate them.

Personally, I think all this is a good thing: it evens the paying field – now everyone should know the security risks with non-provider mobile phone monitoring, not just criminals and bored rich folk.

There are commercial products available – again at significant cost – that can protect mobile calls by using strong encryption and forwarding calls via the data channel; they only however work on certain mobiles and are not in wide use. Given the ever increasing bandwidth available on mobile devices, I cannot imagine it will be long before an open source project pops up with a cross-platform solution of similar nature. The one caveat is that both handsets in the call must use the same software.

Well, its finally been done – Sgàil has been updated to fix the error described in this post which allowed second pre-image and collision attacks. An error in the reference implementation has been remedied, and a number of typographical corrections have been made to the specification. The known answer tests and intermediate value results have also been regenerated.

Although version 0.4 is considered to be immune to the previous design error and was submitted to NIST, it has not yet been approved/rejected as an official change. Updates will be posted as they happen.

Changelogs have been included in the Supporting_Documentation directory.

The performance of the reference implementation has dropped from 62 cycles/byte to 71 cycles/byte in asymptopic behaviour due to the corrections made to the key schedule. It is expected that an optimised version can improve this to at least 40 cycles/byte; I’m looking at coding this in the near future.

UPDATED 11th December 2009: I really should have updated this about six months ago; the corrections were not accepted by NIST and Sgàil did not progress to Round 2.

How many times have you looked at an apparent security measure and wondered what on earth was going through the mind of the person who implemented it?  Take the example of the humble garden shed; usually constructed from painfully thin wood panels nailed to a dodgy timber frame.  Then you look at the door and you see a padlock that looks like is was bought in a fire-sale from Alcatraz.  In reality, anybody wanting to steal from the garden shed would just kick in a few of the wood panels.

This sad state of affairs is pretty much what we’ve got as far as web and email security these days.  The recent proof of concept that created a real rogue CA certificate using MD5 collisions is a prime example. Everybody has known for quite some time now that MD5 is not collision resistant, it is so broke that collisions can be found within minutes on any standard desktop or laptop. That combined with the normal issues that arise with the use of HTTPS as I discussed previously really does leave web security in a sorry state of affairs.

There are sites that use decent certificate authorities (the ones that issue their certs using the SHA family and do more thorough checks before issuing a cert in the first place), and also implement HTTPS in a proper and secure manner. Most financial institutions, for example, follow good practice. Unfortunately, banks and financial institutions have also tacitly instilled a sense of trust amongst the web user. We assume online banking is secure, and online banking uses SSL/TLS: so other sites that use SSL/TLS must also be secure – and there-in lies the problem. It is in part why phishing sites work so well, we know our online banking is secure and the website in front of me is my online banking site… well, er, it certainly looks the same. How many times have you actually read and checked the warning your browser periodically spits out about certificate validity? For me its 50/50 at best, and I know better.

A fine example of this misplacement of trust was no better demonstrated than in a conversation I had the other day. The conversation in question was about how PGP public keys are exchanged. I’d highlighted that you have to get the fingerprint verified (either in person, over the phone, or by a trusted third-party keysign) before accepting or signing someone else’s public key. The response I received was somewhat dismissive – and this was from a group of information security professionals. Missing that one critical step may seem insignificant but it completely defeats the entire security model, hence rendering the use of cryptography in that situation nothing more than a big padlock on a wobbly garden shed.

So what’s my point? Firstly, technologies that employ the use of cryptography have to do it properly, or not at all. This blasé, half-assed, approach by developers and users alike is actually harmful; it takes hard earned trust from one area and transfers it into a wide-spread false sense of security. The second and more important point is that developers and system designers really need to shoulder much more of the responsbility. It’s not your email provider that’s going to have to deal with the fall-out of your account being hacked, it’s you. The business that’s purchased a cert from a CA that uses MD5 and had a load of their customers defrauded will have its reputation in gutter while the CA sits pretty.

The result of this is that its in our hands. If our browser spits out a warning about a site certificate, check it and find out why, then promply complain to the company in question. If your webmail provider isn’t using SSL/TLS properly then complain, if it’s not fixed then move providers. Probablty the best example of what end users screaming about an issue en masse can do is with Microsoft: for years their products were pretty bad in the security stakes, I would argue that there have been vast improvements since.

UPDATED 12th April 2010: Added [] extra meaning in title.

Sgàil, my submission to NIST’s SHA-3 competition, unfortunately has an error in it which makes finding a collision or second pre-image trivial.  The error crept in when I’d decided to change the key schedule late on from being a tree structure to a simple double block processing.

The measure which had originally protected the tree structure from block interchanges – the preliminary key – was unique for each 2048-bit block.  Unfortunately when redesigning the algorithm, I’d neglected to process a preliminary key for each 2048-bit block and instead processed a single preliminary key for each 4096-bit block.  The process where the 4096-bit block is reduced to the 2048-bit principle key uses the same preliminary key for both 2048-bit halves of the 4096-bit block, where they should have been different.  Hence the 2048-bit input pair is interchangable.

The resolution is to process a preliminary key for each 2048-bit input block and update the block counter at each 2048-bit input block rather than at each 4096-bit block.  The performance wouldn’t be significantly altered.  However since the submission deadline has now lapsed, I doubt any modifications will be accepted.

The following code generates a collision:

——-

int main() {

u8 data__a[ SGAIL__INPUT_BLOCK__SIZE * 2 ];
u8 data__b[ SGAIL__INPUT_BLOCK__SIZE * 2 ];
u8 result__a[ 64 ];
u8 result__b[ 64 ];

memset( data__a, 0, SGAIL__INPUT_BLOCK__SIZE * 2 );
memset( data__b, 0, SGAIL__INPUT_BLOCK__SIZE * 2 );

data__a[ 0 ] = 1;
data__a[ 256 ] = 2;

data__b[ 0 ] = 2;
data__b[ 256 ] = 1;

Hash( 512, data__a, ( SGAIL__INPUT_BLOCK__SIZE * 2 ) * 8, result__a );
Hash( 512, data__b, ( SGAIL__INPUT_BLOCK__SIZE * 2 ) * 8, result__b );

do__display_512_bit_hash__byte_wise( result__a );
do__display_512_bit_hash__byte_wise( result__b );

}
——–

I will post a revision of Sgàil in the next few days with the error fixed, although I don’t know of its applicability as concerns the SHA-3 competition.

UPDATED 21st November 2008: Ok, maybe a bit more than a few days, keep getting side-tracked. Will upload new revision once have fixed the specification document.

UPDATED 21st January 2009: Version 0.4 has been released here which corrects this error…. enjoy

UPDATED 12th April 2010: Added [] extra meaning in title.

NIST hasn’t even published the complete and proper candidates, but there’s already a full break (second pre-image) of one of the candidate hash algorithms in the SHA-3 competition, pretty exciting, huh?  The “WaMM” hash algorithm is the first to fall, see here for more info.  There’s also been an attack on another of the submissions, EnRUPT.  A list of some (I say some, there’s quite a lot on the list) of the candidates can be found at the SHA-3 zoo.

In this type of process, such a complete break so early on is certainly a good indicator that the process is working as intended – and getting good involvement.  It also serves as a stark warning to those who would use a home-grown crypto scheme in a commercial product without full peer-review of their algorithm, the consequences of which are no less apparent than the failure of the ubiqutous Mifare classic, used for example in the Oyster card in London.

UPDATED 12th April 2010: Added [] extra meaning in title.

For those who haven’t been following the hype, NIST advertised back in 2007 for submission candidates for a new cryptographic hash algorithm, much in the same vein that the Advanced Encryption Standard process was conducted (the website can be found here). The deadline for submissions is tomorrow, so I thought now would be a good time to upload a copy of my own submission, Sgàil.

A copy of the submission files can be found in the articles and papers section of this website – or even quicker the specification is here.

A copy of the original submission and revised files can be found here.

As with all submissions to the SHA-3 process, its totally royalty free and all that jazz – basically you can do what you like with it. If anyone ever fancies implementing it in real software, I would love to hear about it. Also, if anyone has comments or analysis on the actual algorithm, I may not want to hear them, but they are none-the-less very welcome

UPDATED 22nd January 2009: The new version, 0.4, of Sgàil is available which corrects a serious error, check the Sgàil page for more details.

UPDATED 13th April 2010: Updated links to submission packages.