phc-discussions - Re: Some KDF stumbling blocks, plus Common

lists.openwall.net		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 linux-cve-announce 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]

Message-ID: <loom.20141213T144613-515@post.gmane.org>
Date: Sat, 13 Dec 2014 16:28:49 +0000 (UTC)
From: Adam Back <adam@...herspace.org>
To: discussions@...sword-hashing.net
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,
> > https://bitcointalk.org/index.php?topic=311000.0 )
> 
> 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
faster.

Adam