[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 24 Dec 2013 11:52:46 +0100
From: Christian Forler <christian.forler@...-weimar.de>
To: crypt-dev@...ts.openwall.com
Subject: Re: Password Scrambling
On 24.12.2013 01:49, Solar Designer wrote:
> Christian (one or/and the other), all -
>
> On Tue, Sep 03, 2013 at 08:00:58PM +0200, CodesInChaos wrote:
>> On 9/2/2013 9:58 AM, Christian Forler wrote:
>>> Nevertheless, we came up with Catena, a new memory-hard
>>> password scrambler based on the bit reversal function. A detailed
>>> description of our scheme is available on eprint
>>> (http://eprint.iacr.org/2013/525).
>>
>> Doesn't the standard "store every 1/sqrt(n)th value and recompute the rest
>> using parallel cores" attack using a parallel computer break this?
> What's the current understanding on this? I think the attack does work
> against Catena, although I only skimmed over the paper. Does this mean
> some of the proofs in the paper are flawed?
Yes, the attack is working, but it does not invalidate any of our
security proofs.
In the meantime we have improved our design. The time-memory trade-off
of our current unpublished version ha T = O(G^4/S^3).
This means, having G^1.5 cores you need G^2.5 operations to
compute a hash with G^1/2 memory. For G=2^20 you need
about one billion (2^30) cores and 2^50 operations to compute it with
2^10 memory.
> Not indexing by secret is very nice, but I have yet to see a O(N^2) KDF
> that avoids indexing by secret. With typical/expected uses of scrypt
> (and bcrypt) the problem happens to be mitigated by the fact that the
> salt is normally not known to an attacker unless the hash is also known.
I'm confused. %-/
IMHO the hash and the salt are public knowledge, or at least should be
treated as public knowledge.
> In either case (salt not known or salt+hash are both known), the
> side-channel attack is almost irrelevant. It can be used to infer which
> user account a password is being tested against, but nothing about the
> password and the hash.
We currently working on a basic proof-of-concept implementation of an
password sieve for scrypt. It is exploiting its cache-timing
vulnerability. For you it might look irrelevant but the history of
side-channel attacks have shown that most of them can be useful in the
long run. Just saying.
[square-root attack]
Indeed, this attack is working. This is why we will soon release a
updated version with T(g) = O(G^4/S(g)^3).
> Other assorted feedback on Catena (again, based on having skimmed over
> the paper only):
>
> Of the two properties "marketed" as unique to Catena - Server Relief and
> Client-Independent Updates - I see most value in a sub-property of the
> latter, namely being able to increase not only processing cost, but also
> memory cost, without knowing the plaintext password.
We claim that Catena is the first scheme that has biuld-in support for
both server relief and client-independent-updates.
> However, I do not
> (yet) fully understand how and whether this sub-property is achieved.
> I think reviewing and experimenting with an actual implementation might
> help me understand and evaluate this in less time than (re-)reading the
> paper for real would. Is an implementation publicly available? (In any
> case, it's not long until it must be, for PHC.)
There is a good chance that we will publish our new version including a
reference implementation in the next couple of days.
> I had very briefly commented on this desirable property here:
>
> http://lists.randombit.net/pipermail/cryptography/2012-November/003451.html
>
> "A much trickier task: support upgrades to a higher memory cost for the
> already-computed iterations. Sounds impossible at first? Not quite.
> This would probably require initial use of some secret component
> (allowing for a lower-memory shortcut) and then dropping it at upgrade
> time."
Sound like CI-update. :-)
> Does Catena drop a previously-available part of the salt+hash for the
> memory cost upgrades? Does it achieve the memory cost increase "for the
> already-computed iterations", or maybe only for added iterations?
Only for the added. But to compute the additional iteration you
need about the doubled amount of effort (memory and time) as for
computing all the other iterations together. The cost per
iteration doubles. To compute the i-th round you need O(2^i) memory and
O(2^i) time.
> Or is the wording I had used somehow not applicable to Catena?
For a CI-update from cost=g to cost=g+j you need at least old hash form
h_g = Catena_g(salt, pwd, ...) and O(2^(g+j)) memory + Time O(2^(g+j))
to compute h_{g+j] = CI-Update(h_g. g, g+j) = Catena_{g+j}(salt,
pwd,...). Therefore, neither salt or pwd is required.
> As to the proposed Server Relief feature and algorithm, it is also
> implementable on top of any other password hashing scheme, by wrapping
> it in a fast hash (and this had been suggested on some occasions).
Sure, and this is quite cool. :-)
> If custom processing or protocol like that can be implemented for a
> given deployment, then chances are that the same server could also offer
> e.g. SCRAM, which would also protect against replay (and would not make
> use of the slow hash having Server Relief as a standard feature). So I
> am not sure if there's much value in having this property built into the
> hash. OK to have it for free, but implementing it is relevant to the
> drawbacks 1 vs. 2 above.
In Catena it is part of the specification. We explicitly mentioned it.
There is a gap between specified and possible.
> Finally, the paper appears to use the word stretching to refer to both
> iterations and throwing salt bits away. IIRC, the Kelsey et al. paper
> (reference [14] in the Catena paper) established the term stretching to
> refer only to the iterations, and another term - strengthening - to
> refer to dropping of salt bits.
"Key stretching is about adding a specific number of bits to a keysearch
or bruteforce attack of some kind." ([14], Chapter 2)
Iterations is only one way to implement key stretching.
> Also, I previously saw the term pepper as referring to a possible
> site-specific local parameter (site salt), whereas the Catena paper
> uses it differently. It could be preferable to stick to the way
> these terms had been used historically.
"As advertized, our scheme is very simple. We deploy two salts, one
public and one secret. The public salt is exactly the same as the
current one." ([19], Chapter 3)
In our paper, we denote "pepper" as secret salt. If you really mind we
can replace pepper by "secret salt".
> I am sorry if I sound too negative.
It is fine by me.
> I actually appreciate the effort very much, and it might influence my
> own work.
Cool. Do not forget to refer us. :-)
> It's just that I think feedback on what might be drawbacks can be
> most helpful.
Indeed it is.
> I am also sorry for not having read the paper thoroughly yet.
Do not worry. Save your time for the improved version. :-)
> I thought that it could help if I go ahead and comment anyway, instead
> of delaying this to possibly after the PHC submission deadline (as I
> don't expect to look into this much more closely until we're done
> with our own submission).
I wish you success for your submission. May the best scheme win. :-)
We are eager to see all the other designs. We hope that there are tons
of cool ideas.
BTW. Sorry for my brief responds. I'm currently sick at home. :-(
Maybe I give you an extended version in a couple of days. :)
Best regards,
Christian
Download attachment "signature.asc" of type "application/pgp-signature" (552 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
