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 11:16:22 -0700
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Subject: RE: [PHC] Password hashing as a self-overwriting Turing machine

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.

Comments below,

 - Dennis

 ----- commenting inline to -----
From: Bill Cox [mailto:waywardgeek@...il.com] 
Sent: Thursday, July 2, 2015 07:46
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Password hashing as a self-overwriting Turing machine

On Wed, Jul 1, 2015 at 10:48 AM, Marsh Ray <maray@...rosoft.com> wrote:
Perhaps I misread, thinking of your description of a Turing machine which uses data-dependent addressing. If memory addresses are fixed in advance only by the salt, is it so easy to prove the resulting system is Turing complete?

-           Marsh

Yes, it's Turing complete.  Given a data memory size, each location will be read or written at a known time, and the program can wait for those times to continue a computation sequence.   

<orcmid>
   I see no claim that the algorithm of this hashing technique
   Is considered to provide a Universal Turing Machine.  You
   Might be able to claim that the hashing procedures is an
   Algorithm (i.e., produces a definite result in a finite 
   (not necessarily fixed) number of operations.  That's very
   different.

   If it were a UTM, it would be that *every* computable function
   From the represented input to represented output domains can 
   be achieve by some chosen input.  That also means, generally, 
   that the same function can be achieve in more than one way 
   (i.e., all manner of collisions occur and some computations are 
   indeed reversible, and some are trivial).  

   I don't think that Turing Completeness is even desirable.
   It is certainly not a features that supports a security
   argument.  There are all manner of computable functions
   on even finite domains that you don't want this procedure 
   to derive.

   The Wikipedia article is a bit sloppy in several respects,
   but it makes it clear that there is a universal quality
   that is expected of Turing completeness,
   < https://en.wikipedia.org/wiki/Turing_completeness>.
   (E.g., the Church-Turing thesis is not what is stated
   in the synopsis and in the details, but that and other
   deviations are immaterial here.)
</orcmid>