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] [day] [month] [year] [list]

Date: Fri, 3 Jul 2015 01:01:09 -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 made a serious understatement of the number of functions from 2^n to 2^n.  The problem of achieving Turing Completeness is even worse.

From: Dennis E. Hamilton [mailto:dennis.hamilton@....org] 
Sent: Thursday, July 2, 2015 22:15
To: discussions@...sword-hashing.net
Subject: RE: [PHC] Password hashing as a self-overwriting Turing machine

Concerning claims for Turing Completeness, here is an argument to the contrary, below.

-   Dennis

[ … ]

<orcmid>
[ … ] 
<correction>
Now, the supposed total number of functions, Z -> Z for Z having 2^512 members is 
(2^512)^(2^512).  That’s a *lot* more than the number of functions that the 2^512 values in S can select among (and that assumes no duplicates arise in the selection).  
In addition, *all* of the (2^512)^(2^512) functions are computable.  Z is a finite domain, so the functions are enumerable. 
</correction>

While nrOps complicates things, it is too small (not more than 8 bytes) to overcome this limitation and very large values of nrOps impact running time too much.  Also, too small values of nrOps don’t produce much transformation in the iterative BusyBeaver operations.

[ … ]
</orcmid>

Content of type "text/html" skipped