Date: Thu, 27 Nov 2014 16:24:48 -0900 From: Royce Williams <royce@...ho.org> To: john-users@...ts.openwall.com Subject: Re: ad-hoc work sharing, or proof of keyspace/mask exhaustion On Wed, Nov 26, 2014 at 3:55 PM, magnum <john.magnum@...hmail.com> wrote: > On 2014-11-25 17:23, Royce Williams wrote: >> >> Is there any practical way for JtR to provide evidence that a given >> keyspace has been exhausted for a given hash and mask -- such that >> someone else could verify it or skip it? > > Interesting question. I guess we could produce some kind of very fast hash > that doesn't really *guarantee* we did a "job" but that *indicates* we did. Exactly. Specifically, it would enable someone to say, "I exhausted mask Q, and discovered a set of passwords P for hash H. If you generate passwords in the same order that I did, then you should get checksum C." > No matter how we do it, it will affect performance though. Agreed. Tthe checksum would enable burning even more processor time -- but would have benefits at scale. > But how would the server/mother/master know that such a hash is correct? The > only way is to do that exact work yourself and that would defeat the whole > idea of it. So we could only use this for sample control. Or to verifiably distribute work. Instead of trying to spin up an ambitious BOINC-like platform, I'd like to suggest a small first step: a simple, open standard for reporting work. If other software adopted the format, then any number of wrappers or front-ends could enable platform-independent collaboration. It would also lower the barrier to entry -- allowing many nodes, with varying amounts of compute power, to join or leave a cracking project at any time. Specific use cases for verifiability on clusters might include: * Byzantine fault tolerance  - ensuring that exhausting a keyspace or mask with no resulting passwords is not due to errors in computation (bit flipping, memory errors, rays from space, etc.), falsified results, etc. * Verifying how many passwords produce a given hash. * Detecting impossible or corrupted hashes. * "Resuming" work (or at least reducing rework) if migrating to an entirely different platform or software suite. * Academic research. Other use cases of verification may be more clear when considering many autonomous systems working on a single hash. If it would take one node 20 years to traverse a keyspace for that hash, then even if that keyspace was traversed three times, 1000 nodes could still do it in 22 days. For BOINC/SETI@...e folks, this should all sound familiar. Perhaps distributed.net already has a file format that could be adapted? I'm honestly not sure how they divide up their work. In summary, and put another way ... Salts make us spend many cycles generating de-facto rainbow tables, and then promptly discarding them. Others have to take our word that we exhausted a mask or keyspace. With a standard way to describe and fingerprint the work and how it was performed, we can "fingerprint" that rainbow table, without having to store it. :-) This would allow others to verify our work, or focus on other masks. Royce 1. http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.