lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 13 Dec 2014 16:28:49 +0000 (UTC)
From: Adam Back <>
Subject: Re: Some KDF stumbling blocks, plus Common 

Thomas Pornin <pornin@...> writes:

cool I see you arrived at the idea of delegation via blinding and the 
same basic mechanism using Rivest-Wagner time-lock.

> On Fri, Dec 12, 2014 at 10:38:05PM +0000, Gregory Maxwell wrote:
> > I am saddened that none of the proposals supported delegation scheme
> > with information-theoretic security ( which are possible,
> > )
> Actually, the delegation system described in that page may leak some
> information. It blinds a message m to hash with:
>    r = (g^b)*m
> where g is a known generator, and b is chosen randomly. The value b
> tends to be reused 

It is a security assumption of blinding schemes in general that the blinding
factor, b here, is never reused.

> because the unblinding value y = g^e is expensive to
> compute

g^e is computed cheaply during the setup phase where the user
knows the factorisation of n.  I do not assume any trusted party that
knows the factorisation of n: n is generated by the user.

>  - There is not one secret blinding pair (x,y) (where y=x^e), but 300
>    public blinding pairs. The client generates a new pair for each
>    delegation instance by selecting randomly half (or so) of the pairs
>    and multiplying them together. Compared to the blinding described
>    previously, the cost for the client is higher (an average of 300
>    modular multiplications) but still acceptable (it is less than that
>    of a single RSA private key operation).

I think you are saying this would be slower, take more storage than the
method I describe.  Do you see some advantage?

> (Minor terminology nitpick: none of the above is "information-theoretic
> security". That term designates algorithms that remain secure against
> attackers with unbounded computing abilities. By definition, this cannot
> apply to password hashing, where exhaustive search always succeeds in
> the long run. Also, anything involving a non-prime modulus can be broken
> by factoring the modulus.)

My scheme does provide information theoretic security because all passwords
are equi-probable due to the random blinding and so no information is leaked.

I think your method loses information theoretic security because the 
way you generate the blinding factor has number of values 
c(300,150)<|n|.  With my method b is uniform random from [0,n).

Factoring the modulus does not change this fact it just makes calculations


Powered by blists - more mailing lists