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 18:13:00 +0000
From: Marsh Ray <maray@...rosoft.com>
To: Brandon Enright <bmenrigh@...ndonenright.net>
CC: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: RE: Password hashing as a self-overwriting Turing machine

Well, I'm not a computer scientist. Maybe there are a few on the list that can chime in.

But it seems to me that there are two possibilities: either your machine does data dependent branching, or it does not. The 'data' being derived from the password.
* If it does allow data dependent branching, then you need to worry about branch timing side channels leaking information about the password.
* If it does not allow data dependent branching, then you don't get to use the halting problem as proof of irreproducibility.

In other words, what is the advantage of executing a randomized stream of operations over, say, performing a large block encryption using the salt as key? The latter is something the defender's hardware may be able to help with.

- Marsh

-----Original Message-----
From: Brandon Enright [mailto:bmenrigh@...ndonenright.net] 
Sent: Wednesday, July 1, 2015 10:56 AM
To: Marsh Ray
Cc: 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-----