lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Thu, 2 Jul 2015 11:16:22 0700 From: "Dennis E. Hamilton" <dennis.hamilton@....org> To: <discussions@...swordhashing.net> Subject: RE: [PHC] Password hashing as a selfoverwriting Turing machine I don't understand this handwaving 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@...swordhashing.net Subject: Re: [PHC] Password hashing as a selfoverwriting 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 datadependent 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 ChurchTuring thesis is not what is stated in the synopsis and in the details, but that and other deviations are immaterial here.) </orcmid>
Powered by blists  more mailing lists