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: Wed, 1 Jul 2015 18:13:00 +0000
From: Marsh Ray <>
To: Brandon Enright <>
CC: "" <>
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 [] 
Sent: Wednesday, July 1, 2015 10:56 AM
To: Marsh Ray
Subject: Re: Password hashing as a self-overwriting Turing machine

Hash: SHA1

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


Version: GnuPG v2


Powered by blists - more mailing lists