phc-discussions - Re: [PHC] 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]

Message-ID: <CAOLP8p4Vr_pA9nkOHNRrZxvzJh8s2XoKi8zeMfGMX39sq9GJHw@mail.gmail.com>
Date: Thu, 2 Jul 2015 08:17:21 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] RE: Password hashing as a self-overwriting Turing machine

On Wed, Jul 1, 2015 at 11:13 AM, Marsh Ray <maray@...rosoft.com> wrote:

> 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.
>

Executing truly random machine instructions on the defender's machine will
be essentially impractical to make go faster than a good CPU ran run them,
even with a custom ASIC.  If it were easy to do, the CPU manufacturer would
have done it.

In contrast, an attacker's custom ASIC would heavily pipeline the
encryption hardware, attempting many password guesses in parallel.  That's
why we need the large memory for hashing.

Taking this line of reasoning further, it might be very cool to randomly
generate a set of op-codes that are commonly available, and to compile them
natively for execution.  This is not entirely unlike how the fastest circle
drawing code used to write it's own machine code based on the circle
parameters, and then execute it.

BusyBeaver could have been an educational and entertaining entry :-)  I can
think of a lot of fun directions to go with this.

Bill

Content of type "text/html" skipped