Message-ID: <loom.20141213T224040-797@post.gmane.org>
Date: Sat, 13 Dec 2014 22:45:06 +0000 (UTC)
From: Adam Back <adam@...herspace.org>
To: discussions@...sword-hashing.net
Subject: Re: Some KDF stumbling blocks, plus Common

On 13 December 2014 at 20:34, Thomas Pornin <pornin@...et.org> wrote:
> On Sat, Dec 13, 2014 at 04:28:49PM +0000, Adam Back wrote:
>> I think you are saying this would be slower, take more storage than the
>> method I describe.  Do you see some advantage?
>
> In my method, the user needs not know the factorization of n at any
> point. This means that n can be shared by all users; the 300 blinding
> pairs can be shared as well. Thus, they can be hardcoded in the
> application, without requiring per-user storage of such data.

A master secret that could break all wallets is not something that
would be easily accepted in a system with security requirements as
high as bitcoins.  That requires all users to trust some central
entity to delete the factorisation.  Another alternative is to use an
RSA UFO however their characteristics are poor, and also vulnerable to
speedup via pre-computation (of partial factoring).

You see the same acceptance problem in zerocoin (which uses a Benaloh
accumulator) no one wants to trust that central entity.

Your blinding method is similar to Markus Jakobsson et al's "Secure
Server-Aided Signature Generation"
http://markus-jakobsson.com/papers/jakobsson-pkc01.pdf which I broke
but for different reasons (nothing wrong with the concept just the
implementation).

>> 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).
>
> Ah, I see: the _delegation_ is information-theoretic secure. However,
> if the attacker can get a copy of the resulting hash value (the
> classic situation with a server authenticating user against a
> database of hashed passwords), then we are back to "normal" security
> (if you know the factorization of n, you can compute square roots
> modulo n).

Yes.  I understand this forum is about KDFs and that is the more
common use, and the variant I have could also be used in this way, it
is something discussed as you saw on the referenced bitcointalk thread
and used that way it also loses information theoretic security.
Related example: some people have the bad practice of using so called
"brain wallets" where the password is the private key and the verifier
is the public key stored on the public blockchain.  Realistically
speaking many systems which store the encrypted private key on a
central server basically become vulnerable if compromised, where the
user or even server operator may not know when the compromise happens.

The idea there however is that the KDF parameters are chosen such that
it is uneconomic to attack the private key given the password entropy
estimate because the cost of brute forcing the KDF across expected
number of password guesses is greater than the protected coins values.

User devices could be stolen but that is different because they user
will notice, the interesting point about device theft is that the
previous outsourced KDF calculations do not help the thief because the
blinding value is one-use and deleted after use.  And the user himself
will notice the device theft.

The user can then use a backup procedure and transfer the coins to
different keys.  Of course at that point the attacker has the
grindable password validator, and so the user needs to change the
password securing the replacement device to retain the security model.

ps it would be nice if could cite my proposal if you are still able to
revise the paper submission as I presume it predates your work, and is
strongly related.

Adam

Powered by blists - more mailing lists