phc-discussions - Re: [PHC] Bandwidth hardened algorithms?

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] [day] [month] [year] [list]

Message-ID: <CAOLP8p5SppU-s=ypErhW-OJudRdHBD_qGXu1o7urhhPGyiSvSg@mail.gmail.com>
Date: Mon, 13 Jul 2015 15:56:34 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Bandwidth hardened algorithms?

On Mon, Jul 13, 2015 at 3:45 PM, Peter Maxwell <peter@...icient.co.uk>
wrote:

>
>
> On 13 July 2015 at 22:39, Bill Cox <waywardgeek@...il.com> wrote:
>
>>
>>
>> I still have not seen a good PoW with rapid verification which I believe
>> will succeed in defending against ASICs in a popular crypto-currency mining
>> situation.
>>
>
>
> I haven't been keeping-up with a lot of the traffic on this list but
> could I quickly do a diversion and check what's meant by a proof-of-work
> scheme with fast verification?  (a daftie question, I know, but if it's
> what I think then may have a few suggestions)
>

Fast verification means we can in O(1) or even O(log(N)) verify that the
work has been done, given the proof.  BitCoin has very fast verification
time.  You just do 2 SHA-256 calculations on the block header digest, I
think.  This can be done in an ASIC massively in parallel at higher speed
per core, and lower power per core, leading to the loss of GPU and CPU
mining.

LiteCoin does better, with a 128 KiB Scrypt hash.  I literally laughed out
loud when I read LiteCoin only uses 128 KiB.  I thougth, "Are they nuts?
They'll still get shredded by ASICs."  What I did not realize is that rapid
verification is a key feature for a crypto-currency, and using far higher
than 128 KiB would cause some problems.  There are strong rumors that
LiteCoin ASICs are on their way.

So the problem addressed in this discussion is how to defend against ASIC
mining.  You have to find something that a CPU and/or a GPU can do well
that an ASIC wont do much better.  Requiring a lot of memory and serial
computation of the data you use to fill it makes the algorithm memory-hard,
but if you fill memory slowly due to slow cryptographic hash computations,
and ASIC will beat you on speed.  This seems to be where we are with
current algorithms, IMO.

Bill

Content of type "text/html" skipped