lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Mon, 13 Oct 2014 17:47:19 +0400 From: Solar Designer <solar@...nwall.com> To: discussions@...swordhashing.net Subject: Re: [PHC] What is "basic cryptography" ? Thomas, I think I'm not good at precise definitions, yet I happen to have some comments: On Sun, Oct 12, 2014 at 04:24:43PM +0200, Thomas Pornin wrote: > in his survey, Dmitry Khovratovich includes a property called "basic > cryptography" and defined succinctly as: > > "Basic cryptography ??? collision/preimage resistance, unpredictability." > > While I can intuitively have a rough idea of what this means, I struggle > to write it down as a mathematically precise definition. Yes, this would be useful, and yes it's trickier than it might seem at first. > My goal is to > have sufficiently clean definitions so that I could set out to "prove" > security of some functions (in my case Makwa, but this may be applicable > to other candidates as well) in the sense that any successful attack > would have to either break a known underlying hard problem, _or_ to be a > computational shortcut such as a TMTO or something like that. In > informal terms, I want to separate the "cryptography" from the > "engineering". Shouldn't "a computational shortcut such as a TMTO or something like that" fall under "engineering", or under some inbetween category? This doesn't intuitively feel like "basic cryptography" when we're talking about hash functions. In fact, per your definitions below, some TMTOs (higher level ones, maybepossible for large password spaces) would fall under "preimage resistance" violations, and some would not (those present within each individual hash computation, as well as those maybepossible for large salt spaces). Maybe this is how we want it (or maybe not), but at least we probably want to treat password and salt spaces the same (for purposes of all attacks, not just potential TMTOs), or as one {password, salt} space. On a (not so) related note, I was surprised when Bill mentioned (not) keeping things in memory (I don't recall the exact wording) as falling under "basic cryptography". To me, it does not. It may be a property of the hashing scheme  that is, the scheme is such that sensitive data is naturally overwritten early on with no processing cost overhead compared to performanceoptimized evaluation of the hash  which is nice, but typically has drawbacks for some use cases (it typically implies slower memory usage growth than would be possible with a slightly different design). Or it may be a property of an implementation (explicit zeroization or e.g. selftest performed after actual hash computation). I think neither of these cases falls into a category overlapping with "basic cryptography". In fact, the latter  property of an implementation  is irrelevant to PHC at this point (can be taken care of later), although the PHC relevant aspect is that it's not as safe as the former (but might not have the drawback I mentioned). > For collision resistance, I can have something satisfactory: for a > password hashing function h(), that takes as inputs a salt s and > password p, collision resistance is about the computational > infeasibility of finding (s,p,p') where p <> p' and h(s, p) = h(s, p'). > Note that I am talking about infeasibility, regardless of the space of > plausible or potential passwords. While collisions can help an attacker > only within rather esoteric usage scenarios involving active misuse of > the function by the defender, it is still a nice thing to have. > > In particular, collision resistance implies secondpreimage resistance, > and THAT is good for security proofs, in the following sense: if the > attacker is given s and h(s, p), and is challenged with finding a > password p' such that h(s, p') = h(s, p) (that is the normal setup when > considering an authentication server), then secondpreimage resistance > means that if the attacker succeeds, then he found p' = p; otherwise, > that would contradict secondpreimage resistance. So far so good: if > secondpreimage resistance can be proven (and proving collision > resistance implies proving secondpreimage resistance), then we have > shown that if an attacker finds a matching password, then he found _the_ > password, meaning that no password entropy was lost in the process: the > space of potential passwords, already quite small (that's the problem > with passwords), is not unduly shrunk through some misbehaving of the > function. This looks good, except that you're only considering one salt value. I think a collision of the form h(s, p) = h(s', p') should also be a concern, falling under "basic cryptography". Like you say, these are not a problem for typical intended use of password hashing functions, but they may be for possible unintended uses. Also, they may undermine confidence in a password hashing scheme. Similar concerns about salts apply to all of the below, and to a much greater extent. A hash function that simply ignores the salt input would pass your definition of preimage resistance, yet would allow for obvious faster attacks on multiple hashes. I think that's not how we want it. > It is with preimages (not secondpreimages) that I have a problem. [...] > With password hashing, things are not as easy. The space of possible > inputs will be a lot smaller, and quite smaller than the apparent size > of the output space. For instance, a password hashing function may > produce a 128bit value, but since there are much fewer than 2^128 > possible passwords (realistically), then not all 128bit outputs are > actually possible. In any case, brute force on the input is assumed > to work (the input is a password). So I could try something like this: > > Passwordhashing function h() will be said to be preimage resistant > if it is not feasible, given s and h(s, p) for an unknown p chosen > randomly and uniformly in space P, to find p' such that > h(s, p) = h(s, p') with average cost less than #P/2 the cost of > evaluating h(). > > I am not satisfied with that definition for the two following reasons: > >  This depends on the space of potential passwords. For the definition > to be useful, it must hold for all spaces of a given size, and not > just "on average". That is, the "average cost of #P/2 evaluations" > must be understood as "over all p in P for a single, given P". I > fear that such a definition may be defeated by anomalous spaces of > passwords that are not realistic in any way. > >  This definition includes the cost of evaluating h(), i.e. it > postulates the lack of any shortcut. Thus, it fails at separating > cryptography from engineering. To address your second concern above, maybe you can refer to number of evaluations of h() rather than cost of evaluating h()? Then any shortcut that might let an attacker evaluate the required number of values of h() with less effort would be considered an engineering problem. BTW, I think such shortcuts can be of very different kinds. Some may reduce abstract computational cost of computing a hash, on average (so N hashes may be computed in less than N times the number of some kind of basic operations for computing one hash), whereas others may reduce some realworld cost metric (e.g., energy consumption on actual hardware) while not reducing the abstract computational cost. Do we really want to have both kinds in the same category? Maybe not. Maybe it's not "cryptography" vs. "engineering", but more like "cryptography" vs. two other categories (what do we call them?) Also, strictly speaking your definition can't be satisfied: there's always some processing that can be reversed (going back from a hash value to crack to some intermediate value), and this will only need to be done once per hash to crack rather than once per password to test. So testing many passwords is theoretically at least very slightly cheaper perpassword than testing one. In practice, for a good password hashing scheme this difference might be so small that it's not worth exploiting, but I think it does invalidate this sort of formal definition. > So far my best attempt at producing a clean, mathematical definition of > preimage resistance for a password hashing function is the following: > > For a given space P of inputs, the passwordhashing function h() will > be said to be preimageresistant over P if, given s and h(s, p), the > average cost (for p chosen randomly and uniformly in P) of finding p' > such that h(s, p) = h(s, p') is not less than the computational cost > of evaluating h(s, t) for all t in T, for any subset T of P such that > #T >= #P/2. > > h() will be said to be preimageresistant up to "k bits" if it is > preimageresistant over all possible spaces P of size less than 2^k. Are you sure about "#T >= #P/2", can this really be satisfied "for any subset T of P"? I think not. I think only the "#T = #P/2" can almost be satisfied, short of the detail I mentioned above and potential issues with odd #P where "average cost" may be noninteger, but #T is integer. Also, when we say "average cost", what set of costs are we considering? Is it e.g. for all possible orderings of candidate passwords, equally represented, to exclude chance? If so, should we spell this out? > The intuition behind this definition is that h() must be such that > cracking a password must involve obtaining the hashes for at least half > of the potential passwords. For an infinite number of all possible password cracking attempts against an ideal password hashing scheme, this should be exactly one half. (And what if the number of potential passwords is odd? When not using the bigO notation, we might have to be careful about detail like that in our definitions.) For a finite number, this can be more or less than one half, depending on luck. I think "at least" is wrong for a definition. All of this is assuming uniform distribution of the passwords to be cracked. Ideally, we'd have definitions not limited to that. If it's simpler to make this assumption, we may (like you did), but maybe it's worth trying to somehow approach the problem from a password cracking perspective, for distributions with arbitrary guessing entropy. The average number of hash computations (excluding a final, feasibly reversible portion of each hash computation) required to crack a password given a set of password hashes, each with its own salt, should be no smaller than (and actually the same as) it would be when probing passwords in an optimal order (given attacker's knowledge of the guessing entropy distribution) against an oracle. > Now that is quite clunky and I don't really like it. I think it's not only clunky, but also flawed  but it's a good start at showing where the problems are, and that maybe we should approach this differently. Thanks, Alexander
Powered by blists  more mailing lists