[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <CA+E3k93cWuWLNeE7k1MeULeuJUtMHqrt0g7ZJgkwj0yMMBOXPQ@mail.gmail.com>
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 [1] - 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.
