phc-discussions - Re: [PHC] Password hashing as a self-overwriting Turing machine

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Thu, 2 Jul 2015 08:20:48 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Password hashing as a self-overwriting Turing machine

On Wed, Jul 1, 2015 at 11:51 AM, Larry Bugbee <bugbee@....com> wrote:

> On Jul 1, 2015, at 9:14 AM, denis bider <pwhashing@...isbider.com> wrote:
>
> > Instead, we first use a trusted algorithm, SHA-512, to generate random
> data dependent on the salt and password; and then we interpret and execute
> that data as a self-overwriting Turing machine composed of
> entropy-preserving operations. The Turing machine is allowed to run for a
> fixed number of operations, but its memory access pattern is random
> (dependent on the salt), and its order of operations is random (dependent
> on the salt and password). The result is a cryptographic digest of the
> state of the Turing machine, after the specified number of operations.
>
> I very much doubt you have a true Turing machine.  A Turing machine is
> theoretically able to solve all computable problems.  The output of the
> hashing of the salt and password will be fixed length, and "programs" of a
> certain fixed length can only solve a subset of all computable problems.
>
> May I suggest a name change?
>

It is capable of performing any fixed-length calculation, if we can design
the program rather than having it generated with SHA512(salt), and can
adjust both the program and data sizes, as well as the output length.  In
practice, this is equivalent to anything any real computer can do.  Turing
machines get the added bonus of infinite memory.  What do we call finite
memory Turing machines?

Bill

Content of type "text/html" skipped