Message-ID: <532FA15D.5030805@bindshell.nl>
Date: Sun, 23 Mar 2014 20:07:09 -0700
From: Jeremi Gosney <epixoip@...dshell.nl>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] pufferfish

Hey Alexander,

On 3/23/2014 10:57 AM, Solar Designer wrote:
> Jeremi,
>
> On Sun, Mar 23, 2014 at 07:59:48AM -0700, Jeremi Gosney wrote:
>> I've pushed code to a public repository for the candidate I will be
>> submitting, pufferfish. This repository will be frantically updated over
>> the coming week as I prepare my submission, but I wanted to get some
>> initial feedback before the cutoff.
>>
>> https://github.com/epixoip/pufferfish
> I definitely would have more comments on both the underlying idea (as I
> had thoughts along similar lines too, and found much of what you
> describe just not good enough) and the specific scheme and code, but I'm
> afraid I won't have time for that before the submission deadline, unless
> I decided right now that I won't be submitting escrypt.

I appreciate you taking the time to comment in spite of how busy you
are. And I'd much rather see you submit escrypt than spend time
discussing my submission.


> I haven't looked at your code yet, but have you introduced two layers of
> lookups - tiny yet frequent (bcrypt-like) vs. larger and infrequent
> (scrypt-like)?  If not, your scheme won't scale beyond L1 cache size, so
> will have only slight advantage over bcrypt (only due to modern CPUs'
> L1 caches allowing for up to ~12 or ~16 KiB per thread until there's a
> performance hit, vs. bcrypt's 4 KiB).  The way I'd try dealing with this
> when enhancing bcrypt is by having bcrypt-like S-boxes randomly move
> across a larger arena once in a while.

No, I have not introduced two layers of lookups in pufferfish. I'm
relying solely on the tiny-yet-frequent lookups. I did briefly consider
having larger, less frequent accesses, but I (perhaps arbitrarily)
decided against doing so.


> Well, you could accept that performance would drop when you no longer
> fit in L1 cache, hoping that attackers would have a similar performance
> hit anyway.  

Yes, that's the idea.


> This may be true for attackers with CPUs and GPUs, but
> perhaps not with ASICs.  Maybe that's OK, but this raises the question
> of why deviate from bcrypt at all if it's not against ASICs.  Well,
> maybe that's in case future/bigger GPUs are better at attacking bcrypt,
> which is likely, but not at attacking your scheme.

Correct. The goal of pufferfish is to defeat next-generation GPUs and
manycore CPUs. The idea is that one would use just enough memory to
force the use of global memory, and unlike blowfish, this can be
increased as cache sizes increase.

The ASIC threat, IMO, is greatly overstated. Most adversaries that one
might assume are using ASICs, or would consider using ASICs, are really
just using CPUs and GPUs for most things. There are of course some
exceptions, and due to NDAs and confidentiality agreements I cannot
elaborate on this, but I think you'd be surprised how many entities rely
on john and hashcat.


> And like I said in those tweets, I think the introduction of SHA-2 and
> HMAC is unnecessary (you can process > 72 chars using the same "trick"
> that BSDI crypt() did for > 8 chars with DES, and it did that well),
> and it removes much of the advantage of this being a tweak of bcrypt.

Yes, one could use the BSDI trick to support passwords > 72 chars. Well,
once we introduce the use of 64-bit words we already increase the
maximum length to 144 chars. But there are a couple reasons for the
introduction of HMAC, outside of supporting arbitrarily long passwords.
For one, using a fixed key length reduces the code complexity in the key
schedule. Second, we're already using HMAC to initialize the s-boxes, so
one more HMAC operation to generate a key doesn't increase the cost much
and removes the need for having to implement the BSDI trick. SHA512 also
sucks on GPU, so we get some added resistance as well. So this seemed to
be the best and least-complicated way to solve this problem.


> Oh, and you also introduce ChaCha?  With that mix, what's the advantage
> over scrypt?

ChaCha is only used in the s-box initialization, it is not used anywhere
else in the algorithm. The advantage is lower memory requirements, and
no TMTO.


> I think a key advantage of building upon bcrypt would be to stay with no
> external crypto primitives.  I understand, though, that as soon as you
> revise Blowfish, you no longer have _any_ studied crypto primitive in
> there, so that's probably what prompts you to introduce something extra.

Indeed. And it really doesn't increase the complexity that much.


> Maybe stay with classic Blowfish, then, and enhance the scheme in other
> ways (mentioned above).  Yes, you won't use 64-bit CPUs more optimally
> and won't rely on more than 4 KiB of L1 cache (but you may rely on some
> L2+ cache and RAM) then...  A nasty tradeoff.

I'm... not keen on that approach.


> Maybe you can introduce
> tunable parallelism, though, so that once we finally have faster gather
> loads, those could be used for defense (and we'd use more L1 cache in
> that way).

That is a possibility, and might be something I will consider for the
tweaking phase.


> Overall, with all of those concerns I think you can see why I chose not
> to go in that direction.

I understand your reasons for not going in that direction. And while
your concerns are valid, I think we just have different opinions on what
the most important aspects are and how to accomplish those goals.


> Add to that possibly frustrating the OpenBSD
> folks if we tried to build upon bcrypt too closely, and this becoming
> less reasonable if we deviate from bcrypt very far and introduce more
> crypto primitives.

You might have to elaborate on this. The bcrypt code in OpenBSD is
copyrighted by Niels Provos, but afaik David Mazieres didn't place any
copyright on the algorithm itself, and pufferfish doesn't use any of the
copyrighted code from bcrypt.c. In all sincerity, it is not my intention
to ruffle any feathers.


> That said, it's great that you're experimenting with this approach, at
> least to provide another baseline to compare other PHC submissions
> against.  Thank you, and good luck!

I appreciate that, Alexander, and thank you again for your comments.
Good luck to you as well!

Jeremi

Powered by blists - more mailing lists