Applying Graphics Cards to Password Cracking

On the Beowulf list there has been a long thread on GPGPU and especially nVidia’s CUDA language. As part of it Prentice Bisbal posted about a friend of his, Mario Juric, who decided to write a proof of concept MD5 password hashing program to take advantage of CUDA.

In his message to the Beowulf list Prentice quoted Mario saying:

If you attempt to compute a single hash on an entire card, you won’t get any improvement. Same as you wouldn’t if you tried it on a single vs. quad core CPU. But if you compute four hashes, than single vs. quad makes a huge difference. And the GPU cards are effectively 128 core CPUs, so when you need to compute millions of hashes…

Now Mario Juric (who organised the AstroGPU workshop) has put up a web page on the program, which gives details of the sort of performance he got with a quick hack.

One way of visualizing this is noting that a single 8800 Ultra could brute-force break an MD5 hashed password of eight or less characters+numbers (A-Z, a-z, 0-9) in about ~16 days.

But this really is just a quick hack:

The MD5 code used here was written in less than 2 days, as a proof-of-concept, and with only a single one-liner GPU-specific optimization.

Of course if people do want to try playing with it the program is available, though at the moment there isn’t a software license included with it. I’ve emailed Mario about the license to see if he can clarify what the rules are.

Bletchley Park in Cash Trouble ?

For the past few weeks I’ve been reading “Codebreakers“, a collection of memoirs and essays by former staff at Bletchley Park, aka the Government Code and Cipher School (GCCS) War Station-X, Room 47 Foreign Office, etc. which worked throughout the war breaking enemy ciphers such as the German Enigma machine, the decrypts of which were called “Ultra“.

But today, via Bruce Scheiers blog, I’ve learnt that the trust that now runs BP has is facing financial problems as they receive no external funding and need cash to help preserve the buildings and the exhibits they restored after taking over the site in the 1990s.

The Bletchley Park Trust receives no external funding. It has been deemed ineligible for funding by the National Lottery, and turned down by the Bill & Melinda Gates Foundation because the Microsoft founder will only fund internet-based technology projects.

For the site that hosted the organisation that arguably saved the day in World War 2, not to mention being the birthplace of the first real computer, Colossus (( yes, I know it wasn’t Turing complete! )), it’s a sad predicament. 🙁

Ross Anderson’s “Security Engineering”

Back in 2006 Ross Anderson (Professor of Security Engineering at the Cambridge Computer Laboratory) announced on his blog that he had published the full contents of the first edition of his book “Security Engineering” in PDF format. The book covers a whole range of security issues from creating, managing, accrediting & breaking the mechanisms themselves through security politics and into topics like DRM.

Now the second edition of Security Engineering is about to arrive (published April 14th in the US, Amazon say stock expected in 1-4 weeks) and mine is on order already (along with a copy of Linus Torvalds Just for Fun).. 🙂

Taking the Myki ?

So Melbourne is investigating an electronic tag based ticketing system for public transport called Myki (presumably meant to be pronounced My Key and not mickey), and in an interesting coincidence Bruce Schneier reports a successful attack against a Dutch ticketing system that’s about to be deployed:

The first reported attack was designed by two students at the University of Amsterdam, Pieter Siekerman and Maurits van der Schee. They analyzed the single-use ticket and showed its vulnerabilities in a report. They also showed how a used single-use card could be given eternal life by resetting it to its original “unused” state.

The second attack is a reverse engineering of the crypto algorithm through a physical attack on the circuitry which will be a jumping off point for further attacks, I guess.

I wonder how long it’ll take for the Melbourne system to be similarly compromised ?

US Wants to Remove More Rights, Expand DMCA

It would appear a coalition of the repressive wish to expand the remit of US Copyright law, including the DMCA, to make it even harder to do research, play media on any OS but those you have to payed Microsoft/Apple for, or defend yourself against damaging software they put on silver circles they claim to be (but are not) Compact Discs.

Jessica Litman, who teaches copyright law at Wayne State University, views the DMCA expansion as more than just a minor change. “If Sony had decided to stand on its rights and either McAfee or Norton Antivirus had tried to remove the rootkit from my hard drive, we’d all be violating this expanded definition,” Litman said.

Even the current wording of the DMCA has alarmed security researchers. Ed Felten, the Princeton professor, told the Copyright Office last month that he and a colleague were the first to uncover the so-called “rootkit” on some Sony BMG Music Entertainment CDs–but delayed publishing their findings for fear of being sued under the DMCA.

..and how do they propose to get this through ? Fear of course! That resurgent American political tool.

During a speech in November, Attorney General Alberto Gonzales endorsed the idea and said at the time that he would send Congress draft legislation. Such changes are necessary because new technology is “encouraging large-scale criminal enterprises to get involved in intellectual-property theft,” Gonzales said, adding that proceeds from the illicit businesses are used, “quite frankly, to fund terrorism activities.”

Ed: my emphasis added

Elliptic Curve Cryptography

An interesting article from LWN about Elliptic Curve Cryptography and Open Source.

ECC is based on some very deep math involving elliptic curves in a finite field. It relies on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) in much the same way that RSA depends on the difficulty of factoring the product of two large primes. The best known method for solving ECDLP is fully exponential, whereas the number field sieve (for factoring) is sub-exponential. This allows ECC to use drastically smaller keys to provide the equivalent security; a 160-bit ECC key is equivalent to a 1024-bit RSA key.

As always though, there are the problems of patents..

The wild card in the ECC patent arena seems to be Certicom which claims a large number of ECC patents and has not made a clear statement of its intentions with regard to open source implementations. The NSA licensed Certicom’s patents for $25 million to allow them and their suppliers to use ECC, lending some credence to at least some of the Certicom patents. Other companies also have patents on various pieces of ECC technology.

Be interesting to see what happens..