Elcomsoft trying to patent faster GPU-based password cracker

Trei, Peter ptrei at rsasecurity.com
Thu Oct 25 13:18:36 EDT 2007


I was the person who originated the DES Challenges at RSA, and also
helped set up and run them.

I knew that there was a stealth effort underway at SGI, but didn't 
know any of the details. 

A good deal of cool stuff came out of the contests.

Other prior art against this patent would include using the DSP
chip in the Amiga graphics set for non-graphics purposes, which
was often done back in the 80s.

Peter Trei

-----Original Message-----
From: owner-cryptography at metzdowd.com [mailto:owner-cryptography at metzdowd.com] On Behalf Of Ian Farquhar (ifarquha)
Sent: Wednesday, October 24, 2007 7:35 PM
To: 'Cryptography'
Subject: RE: Elcomsoft trying to patent faster GPU-based password cracker

ROTFL.

When SGI's "stealth" DES Challenge project was underway in 1997, it's main client ran on the host's (MIPS) CPU(s), implemented with a variant of Eli Biham's bit-slice DES implementation.  The 64-bit 195MHz R10000 could do 2.5M keys/sec.  I was peripherally involved in the project.

One of the things I was looking into was offloading the client into the VICE ASIC on the O2.  The VICE ASIC was a compression offload engine, and combined with the MACE ASIC (which had the 3D rendering pipeline), provided graphics support on the O2.  At the time, SGI put a workstation on everyone's desk in the company, so there were thousands of O2's around the company.

The VICE itself had two CPU's in it, the "MSP" which was a R4000-derived core with a 128bit vector unit, and the "BSP" which was a custom little RISC core designed for efficiently slicing non-word-aligned multimedia bit streams.  Biham's algorithm would have run beautifully on the VICE.

I'd just gotten the devkit when the project came to an end with DESCHALL's successful keyfind.

So I'm feeling a little bit of déjà vu about Elcomsoft's patent here.  Offloading keyfinding algorithms to a programmable graphics accelerator.  Wow, sounds *very* familiar.  But alas, probably not sufficient for a prior art claim.  Gotta also wonder if the mailing list traffic would still exist in SGI too.

Mind you, if the patent system wasn't totally broken, this application would fail the obviousness test anyway.  The GPU's mentioned below are basically just optimized little co-processors anyway.  How much innovation is there in offloading crypto to a coprocessor? 

Ian.

-----Original Message-----
From: owner-cryptography at metzdowd.com [mailto:owner-cryptography at metzdowd.com] On Behalf Of mheyman at gmail.com
Sent: Thursday, 25 October 2007 3:25 AM
To: Cryptography
Subject: Elcomsoft trying to patent faster GPU-based password cracker

From:

   <http://www.elcomsoft.com/EDPR/gpu_en.pdf>

  Moscow, Russia - October 22, 2007 - ElcomSoft Co. Ltd. has
  discovered and filed for a US patent...Using the "brute force"
  technique of recovering passwords, it was possible, though
  time-consuming, to recover passwords from popular
  applications. For example...Windows Vista uses NTLM hashing
  by default, so using a modern dual-core PC you could test up to
  10,000,000 passwords per second, and perform a complete
  analysis in about two months. With ElcomSoft's new technology,
  the process would take only three to five days..Today's [GPU]
  chips can process fixed-point calculations. And with as much as
  1.5 Gb of onboard video memory and up to 128 processing
  units, these powerful GPU chips are much more effective than
  CPUs in performing many of these calculations...Preliminary
  tests using Elcomsoft Distributed Password Recovery product
  to recover Windows NTLM logon passwords show that the
  recovery speed has increased by a factor of twenty, simply by
  hooking up with a $150 video card's onboard GPU.

-Michael Heyman

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list