[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <52C2D6CC.1020105@uni-weimar.de>
Date: Tue, 31 Dec 2013 15:38:04 +0100
From: Christian Forler <christian.forler@...-weimar.de>
To: crypt-dev@...ts.openwall.com
Subject: Re: Password Scrambling
On 27.12.2013 00:27, Solar Designer wrote:
> On Tue, Dec 24, 2013 at 11:52:46AM +0100, Christian Forler wrote:
>> 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.
>
> This is very nice. Is this something you're able to prove (that no
> better TMTO exists)?
Yes we have a pebble-game proof. BTW. our new design is based on two
security parameters: 1) the garlic value which reflects the
memory-consumption of the algorithm (i.e., about G=2^g units of memory
are needed to compute Catena with a minimal amount of operations.) 2)
the depth d which influences both the total amount of operations and
the TMTO).
For a fixed depth d, we claim that our new password scrambler Catena-d
(e.g, Catena-1 is specified in the current eprint version) has a TMTO of
about T = O( G^{d+1} / S^d). This conjecture is already proven for
d={1,2,3}. It is quite easy to extend the proof for d=4, but
unfortunately we have no generic prove (for arbitrary values) yet;
this is still a open research problem.
>> I'm confused. %-/
>> IMHO the hash and the salt are public knowledge, or at least should be
>> treated as public knowledge.
>
> In one of the relevant threat models (perhaps the most relevant one),
> yes. But not in all of them.
> Let's talk about this one:
[...]
OK. but it is sufficient to show that a password hashing scheme X is
secure against adversaries knowing the salt. Since then X is also
(implicit) secure against adversaries that do not know the salt.
Reason: Assume we have an adversary A which knows the salt and
can efficiently reconstruct the password from a hash. Then,
it quite easy to a construct a successful adversary B which knows the
salt. B strategy: 1) Invoke A with the hash, 2) return the
result of A.
Therefore, we should focus on the class of the mightiest adversaries
(i.e, off-line adversaries that knows everything beside the password).
>>> 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.
> I admit I had made an overly bold statement above, thinking that
> realistically someone with a copy of the hashes would work on them
> solely offline (like it's been happening so far, despite of e.g. bcrypt
> theoretically allowing for similar timing attacks) and not bother
> passively timing authentication attempts on the server (and possibly
> having too few per account for the attack duration). I would be
> surprised to see someone mount that attack in the wild - not because it
> is impossible (it can be demo'ed, and it's great that you're going to do
> just that) - but because it is probably usually impractical, because of
> a combination of reasons and constraints.
Sure, there is a very good chance that this attack will never be
mounted in the wild. But this is true for the vast majority of published
cryptanalytic attacks. :-)
It is all about properties that a next generation password scrambler
should (not) have, and the PHC is the best stage to discuss this.
Actually, one of the major design goal for Catena was to build a scheme
where the memory-access pattern does not depend on the password.
> If we can deal with the attack without compromising on other properties
> of the hashing scheme, this is definitely worth considering. It sounds
> like you may have achieved just that. :-)
We have compromised the sequential-memory hardness property. I think
this can not be achieved by a static memory-access pattern.
>
> For example, I oppose secret-dependent branching for that reason
> (including e.g. in a discussion around SunMD5 years ago) - we can
> achieve our desirable properties without that, so let's not take the
> risk of having this extra side-channel.
>
> However, if we have to compromise on real-world relevant security
> properties in order to mitigate an attack that is unlikely to ever be
> used in the wild and with actual benefit to the attacker (or loss for
> the defender), then I am not sure this is worth it. I wouldn't
> currently trade O(N^2) with indexing by secret for O(N^1.5) without, at
> least not unconditionally (supporting this as an option may be OK).
I agree. Actually, this is the reason why we upgraded our old design.
>> We claim that Catena is the first scheme that has biuld-in support for
>> both server relief and client-independent-updates.
>
> This may well be true.
>
> A possible improvement upon your server relief: allow for recovery from
> a compromise of a sniffed hash by computing 2 (and so on) final hash
> iterations on the server, and accordingly fewer on the client (the server
> admin would bump this number when needed). This is essentially S/Key.
> Unfortunately, this reduces the memory-hard portion.
Sure, you can do this. It is a kind of generalization. I doubt that our
PHC submission will support this behavior.
>>> 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.
>
> Great, but this is implementable on top of e.g. scrypt, with similar
> properties, except that the original password and salt are required due
> to how scrypt is defined at high level (the PBKDF2 steps). Right?
I'm not quite sure, sorry. We were more focused in "tweaking" the
awesome ROMix algorithm regarding our design goals rather than improving
scrypt.
[...]
>> In our paper, we denote "pepper" as secret salt. If you really mind we
>> can replace pepper by "secret salt".
>
> No, "pepper" is fine. Your use is not even all that different.
>
> I use the term "local parameter" for the site-specific salt, so there's
> no confusion here.
OK. Fine.
>> We are eager to see all the other designs. We hope that there are tons
>> of cool ideas.
>
> Yeah. I am even wondering if we maybe should propose a change to PHC
> timeline, introducing an extra round of submissions so that there's a
> chance for all to reuse ideas from others' submissions (with due
> credit). "Tweaks" are going to be allowed, but in some cases this could
> be more than mere tweaks.
Yes you should propose to introduce a extra round to the PHC since the
timeline is quite tight. Besides, I really do like the idea of an
additional round.
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.
