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: Tue, 14 Oct 2014 12:49:48 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...swordhashing.net" <discussions@...swordhashing.net>
Subject: Re: [PHC] What is "basic cryptography" ?
Hi Thomas,
I think that your hesitancy can be resolved rather easily. Let us consider
preimage resistance. Since we deal with a single hash function, not a
family, the notion of "always preimageresitance" (aPre) by
RogawayShrimpton seems to be the most relevant. So you just consider an
adversary who is given function H(), salt S, and image Y = H(P,S) of random
P. You measure the advantage of the adversary of finding any P' such that
H(P',S) = Y as a function of available resources R. Let m be the
dimension of the password space (i.e. there are less than 2^m passwords)
and n be the length of Y (i.e. output length of H)
If R is measured in the number of calls to H (or amount of computations
equivalent to it), then an aPresecure function, intuitively, should satisfy
Adv(A) < C*max(R/2^m,R/2^n),
where C<1 is some constant that accommodates for minor computational
shortcuts (like computing only a subset of bits, or more sophisticated
stuff like biclique attacks).
If the password distribution is not uniform, then you correct the
definition, i.e. Y= H(P,S) where P is chosen according to some distribution
Q, and the resistance is measured as
Adv(A) < max(f(R),R/2^n),
where f(R) is the maximum cumulative probability of R inputs.
If you want preimage resistance up to k <min(m,n) bits, then you use R/2^k
instead of the maximum function.
TMTO attacks are not relevant here as long as they do not decrease the
(amortized) computational cost of H.
Best regards,
Dmitry
On Sun, Oct 12, 2014 at 4:24 PM, Thomas Pornin <pornin@...et.org> wrote:
> Hello everybody,
>
> 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. 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".
>
>
> 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.
>
>
> It is with preimages (not secondpreimages) that I have a problem. The
> usual definition for a cryptographic hash function is the following:
>
> Given a hash function f() with inputs in space X and outputs in space
> Y, f() is said to be preimage resistant if it is not feasible, given
> y in Y, to find x in X such that f(x) = y with a computational
> average cost lower than #Y times the cost of evaluating f().
>
> It is important to note that preimages and secondpreimages are very
> different things. In the secondpreimage setup, there is no secret; in
> the preimage setup, the target output is a given and there is no
> information, indeed no condition on how it was generated.
>
> With normal hash functions such as SHA1, the output space is "all
> possible 160bit blocks" and, crucially, the space of possible inputs is
> much larger (even if we restrict ourselves to inputs that imply only
> minimal evaluation cost, we have 2^4481 possible inputs, i.e. all
> sequences of 0 to 447 bits). Under these conditions, it is rather easy
> to define preimage resistance with a target output taken randomly and
> uniformly in that welldefined output space.
>
> 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.
>
> 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.
>
> 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. If that can be proven, then it will imply
> that any successful attack on the function MUST be a "computational
> shortcut" that allows computing, say, 30 hash values for the cost of 25,
> or something like that.
>
> Now that is quite clunky and I don't really like it.
>
> Does anybody here has an idea on the subject ? Or maybe a reference to
> some existing published work that already covers these questions ?
>
>
> Thomas Pornin
>

Best regards,
Dmitry Khovratovich
Content of type "text/html" skipped
Powered by blists  more mailing lists