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  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 23:09:01 +0000
From: Marsh Ray <maray@...rosoft.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: RE: [PHC] Password hashing as a self-overwriting Turing machine

I think we’re talking about an attacker model where there is a fixed salt. So one specific sequence of instructions is given, and data-dependent branching is disallowed.

The relevant question is: is processing of a candidate password guess an operation that is reducible. I don’t think you get to invoke the hardness of the halting problem when your computation is known to complete in a fixed number of steps.


-          Marsh

From: Bill Cox [mailto:waywardgeek@...il.com]
Sent: Thursday, July 2, 2015 2:53 PM
To: 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<mailto: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

Powered by blists - more mailing lists