phc-discussions - Re: 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: Wed, 1 Jul 2015 17:55:49 +0000
From: Brandon Enright <bmenrigh@...ndonenright.net>
To: Marsh Ray <maray@...rosoft.com>
Cc: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>,
 bmenrigh@...ndonenright.net
Subject: Re: Password hashing as a self-overwriting Turing machine

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wed, 1 Jul 2015 17:48:31 +0000
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


I don't see the problem.  The if the salt is the seed to some
pseudo-random function then you can think of the salt as the program.
Under basic assumptions about the prf (random oracle) there exists some
stream of instructions that can do arbitrary computation.

Actually finding a salt that produces this "useful" stream of
instructions seems irrelevant.

Brandon

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAlWUKa4ACgkQqaGPzAsl94J/dACgoTvBWPA/uL/RaQ6jQG9Nyles
l0sAniH4CN4g49+MXNt9biGmbINPQc+1
=r4to
-----END PGP SIGNATURE-----