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]

Message-ID: <CAOLP8p7OZNPc3SBSiEHq_6j8s2PBCEZkpvbYWenJcAeO0XFbvQ@mail.gmail.com>
Date: Thu, 2 Jul 2015 14:53:00 -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 Thu, Jul 2, 2015 at 11:16 AM, Dennis E. Hamilton <dennis.hamilton@....org
> wrote:

> I don't understand this hand-waving about Turing completeness.  Or, as has
> been said in other contexts, "I don't think this means what it is being
> used to mean."
>
> In particular, it is not enough to be a Turing Machine in order to be a
> Universal Turing Machine.  Collapsing the terms together creates mischief''
>

Ugh... this is trivially Turing complete.  Can I ask you do to a bit of the
proof yourself?

ARX instructions are Turing complete.  Google it.  He's got all kinds of
constants in the data space to use in operations.  I let the salt determine
branching, which leads to O(n^2) memory to write any regular program of
length n.  Can you figure it out or do I have to spell it out?  I hate
showing my work :-)

BIll

Content of type "text/html" skipped