[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <BY2PR03MB5544AF7A1895BD122E0BA09A7970@BY2PR03MB554.namprd03.prod.outlook.com>
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