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: Fri, 17 Apr 2015 08:37:32 0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...swordhashing.net" <discussions@...swordhashing.net>
Subject: Re: [PHC] Information theoretic security for delegated hardening was:
winner selection
Thanks for the great explanation!
In summary, your scheme is substantially more efficient since a lowpowered
device does not need to compute two modular exponents for blinding.
However, your scheme is more complex. Also, Adam's scheme is a subset of
your scheme. Is this a fair summary of the situation?
Also, the "informationtheoretic" argument against Makwa posted on this
list is flawed. Factoring n is no harder than solving the knapsack problem
 both Adam's scheme and Makwa are provably about equally secure, and both
schemes fail when the attacker has unlimited computing power.
I was thinking that Adam's scheme has an advantage in that a lowpowered
microcontroller need not store hundreds of huge blinding factors like we do
with Makwa. Then I realized that the blinding factors could just be the
output of a CPRNG, such as SHA256(secret + i) for enough i values. The
only advantage of Adam's scheme I can see is lower complexity. For the
considerable improvement in performance, I prefer Makwa.
Bill
On Fri, Apr 17, 2015 at 7:41 AM, Thomas Pornin <pornin@...et.org> wrote:
> On Fri, Apr 17, 2015 at 06:39:12AM 0700, Bill Cox wrote:
> > This is simpler than Makwa, but I haven't put any thought into attacking
> > it. Thomas Pornin, what do you think of this again?
>
> I am preparing an implementation and some documentation, to be
> published some time next week.
>
> Roughly put: for Makwa, and for Adam's RSAbased proposal, the core
> hashing operation is computing x^e mod N for input x, a huge exponent e,
> and a composite modulus N (in Makwa, e = 2^w, while Adam uses e =
> 2^w1). Blinding is done by assembling a "mask pair" (a, a^e), because:
>
> x^e = (a*x)^e * a^e
>
> (All computations are done modulo N.)
> So "a*x" is what is sent to the delegation server, and that server
> raises that value to exponent e.
>
> We need a new mask pair for each delegation, so the problem is about
> producing such pairs efficiently, and without leaking information about
> the input x.
>
> In the Makwa specification, I described (and implemented) a scheme by
> which I precompute 300 mask pairs (a_i, a_i^e), and generate a new mask
> pair by multiplying some of them together (on average half of them):
>
> a = (prod_{b_i=1} a_i, prod_{b_i=1} a_i^e) for random bits b_i
>
> What Adam suggests is starting with a single mask pair (g, g^e) and
> computing a new mask pair by using (g^b, (g^e)^b) with a random
> exponent b.
>
> Adam's method can be said to be "information theoretic secure" if b is
> large enough and g is a generator of the subgroup containing inputs,
> because it implies that after blinding, every single element of the
> subgroup may be reached with roughly equal probability for any input, so
> the delegation server (the untrusted system to which you delegate the
> core of the hashing) provably learns nothing from the exchange, even if
> it has unlimited computing power. With my scheme, an evil delegation
> server with unlimited computing power may solve the knapsack problem and
> thus, for each password guess x, test whether that x would lead to a
> value that can be generated from the a_i, and thus filter out bad
> guesses. Note that the attacker would solve a O(2^150) problem for each
> password guess, so when we say "unlimited power" we mean it.
>
> Adam's scheme has an issue here, because for N = pq (and p != q), there
> is no such thing as a generator for all invertible integers modulo N
> (the problem here being that p1 and q1 are both even: the order of any
> g modulo N will be at most lcm(p1,q1), and that value is lower than
> N/2). However, this is fixed in Makwa, in which we work in the subgroup
> of invertible quadratic residues (the input is always a square), of size
> (p1)(q1)/4, and there we can have a generator g (*)(**).
>
> Makwa's delegation, as currently specified, requires about 300
> multiplications per instance. With a 2048bit modulus, you need the
> exponent b to be 2100bit or so, so you end up with two modular
> exponentiations that will cost, in total, roughly 16 times as much as my
> implementation (depending on the kind of optimization implemented for
> the modular exponentiations). If you want to speed up Adam's scheme then
> you can precompute (g^2, g^2e), (g^4, g^4e), (g^8, g^8e)... at which
> point you are indeed back to the basic scheme, albeit with 2100 source
> mask pairs instead of 300, thus implying a 7x overhead.
>
> So Adam's scheme and mine are really the same, which has the nice
> property that my implementation already supports Adam's scheme, provided
> that the precomputed (g^(2^i), (g^e)^(2^i)) values are input as
> "delegation parameters". What needs to be updated is the support code
> that generates these base mask pairs.
>
>
>
> (*) Reliably computing a generator can be hard in all generality. It is
> easy at modulus generation time, if factorizations of p1 and q1 are
> known. If the p and q factors are "safe primes" ((p1)/2 and (q1)/2 are
> also prime), then g = 4 will work; but generating random safe primes is
> rather expensive. I think I will generate p as p = p1*p2+1 where p1 and
> p2 are two distinct primes of roughly the same size; g = 4 will be a
> generator with overwhelming probability and I can check that at
> generation time.
>
> (**) Note that we ignore noninvertible elements modulo N here.
> Probability that a given input (padded password) is noninvertible is
> about 2/sqrt(N), i.e. 2^1023, and I am reasonably sure we can neglect
> _that_.
>
>
> Thomas Pornin
>
Content of type "text/html" skipped
Powered by blists  more mailing lists