HadoopA51: Hadoop implementation of an rainbow table generator and searcher for cracking the A5/1 cypher

• Nume Scurt: HadoopA51
• SVN: ​https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/HadoopA51/ (imported from the GIT repository)
• GIT: ​http://github.com/luciang/hadoop-rainbow-table-a51/ (with development history)
• Project members: Lucian Adrian Grijincu - lucian.grijincu
• Project description: the A5/1 cypher used to encrypt data sent over the air between a cell phone and a cell tower was proven broken several times. In 2009 a group of reserchers started to generate rainbow tables for A5/1 using CUDA machines. We seek to analise the generation of rainbow tables and the search on those tables on a distributed Hadoop cluster.

History & Motivation

History

A5/1 is one of the most prolific stream ciphers used worldwide (surpassing the one used in ssh or https by total size of encrypted data per year). It is used to provide OTA communication privacy and authentification in the GSM cell phone networks between a cell phone and the first cell tower.

Though at first the algorithm was not public, it was made available by researchers through reverse engineering and hardware monitoring. A reference implementation is given in ​https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/HadoopA51/docs/a5/a5-1.c

Through time the algorithm was proven weak & broken (a selection of proofs):

• 1997 - Jovan Golic published "Cryptanalysis of Alleged A5 Stream Cipher" (​http://jya.com/a5-hack.htm). Their attach uses a time-memory trade-off attack (based on the birthday paradox) which reveals an unknown internal state at a known time for a known keystream sequence. This internal state is then used to obtain the secret key.
• 2000 - Eli Biham and Orr Dunkelman analize A5/1 in "Cryptanalysis of the A5/1 GSM Stream Cipher" demonstrate an attack on A5/1 which relies on ~2^{20 known plaintext data.}
• 2003 - Barkan et al. published several active attacks on GSM by forcing a phone to use A5/2 (which is weaker than A5/1). As the key used in A5/2 and A5/1 in GSM implementations is the same, this lead to breaking the A5/1 code.
• 2005 - The same authors in "Conditional Estimators: An Effective Attack on A5/1" provide yet another attack on A5/1.
• 2009 - Karsten Nohl and Chris Paget provide details of an rainbow table attack on A5/1 in "GSM: SRSLY?" at the 26th Chaos Communication Congress (26C3). This attack was announched in September 2009 and lead to this project (HadoopA51)

Motivation

Such a wide used weak cypher must have sparked the interest of government agencies and criminal groups which want to gain illegal information shared through the cell phone.

Altough the cypher was proved broken several times before since at least 13 years ago, the GSM Association has not deployed another strong cypher to replace A5/1 (the proposed A5/3 is not yet supported in all networks or devices and it too was proven broken).

This project seeks to demonstrate that using commodity hardware organised in a Hadoop cluster can lead to an effective attack against A5/1.

Related Work

• ​http://cryptome.org/jya/a5-hack.htm - Cryptanalysis of Alleged A5 Stream Cipher
• ​https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/HadoopA51/docs/a5/CS-2006-07.pdf - Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication
• ​https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/HadoopA51/docs/a5/a5-1.c - reference A5/1 implementation
• ​https://svn-batch.grid.pub.ro/svn/PP2009/proiecte/HadoopA51/docs/rainbow/Making%20a%20Faster%20Cryptanalytic%20Time-Memory%20Trade-Off%20-%20Oech03.pdf - A paper describing the rainbow table technique
• ​http://www.copacobana.org/paper/TC_COPACOBANA.pdf - Cryptanalysis with COPACOBANA