phc-discussions - Information theoretic security for delegated hardening was: winner selection

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-next>] [day] [month] [year] [list]

Message-ID: <CAAS2fgSLLhyrtyRsaNZPzFAMW04ztf_vYuarJdGgFTSf68Vo9g@mail.gmail.com>
Date: Mon, 13 Apr 2015 19:28:00 +0000
From: Gregory Maxwell <gmaxwell@...il.com>
To: discussions@...sword-hashing.net
Subject: Information theoretic security for delegated hardening was: winner selection

On Mon, Apr 13, 2015 at 3:52 PM, Alexandre Anzala-Yamajako
<anzalaya@...il.com> wrote:
> The topic is not specifically about Makwa but I'm not sure that I
> understand Gregory's argument.
> To me it doesn't make sense to have only one of the crypto primivites
> of your system information theoritically secure.
> Everything else in Bitcoin relies on computational hardness
> assumptions does it not ?

Sorry for the tangent.  Let me give an example with computational hardness.

The application here is that there is some weak user passphrase, P.
There is a low power (think 8bit miccontroller) device that cannot
compute a good strengthening function to raise P to adequate security.

Instead they compute H(P) and send it to some untrusted device which
computes KDF(H(P))  and the device ultimately computes a key a
H(KDF(H(P)) || |P) or the like.

[Obviously things like salts and such simplified out]

The 'untrusted device' however, is able to perform dictionary attacks
against H(P); which is cheap because the device is limited.
Computational hardness at the 2^48 (user entropy) level is very
different than level the computational hardness of the rest of the
system..

So the untrusted device really can't be that untrusted, which is unfortunate.

Using the group of unknown order blind squaring puzzle  we can redo
the above as   BLIND(H(P),random);  then delegate to an untrusted
party which learns nothing (the received number is uniform); and they
can perform an expensive KDF and then the end device can unblind.
Since the device doing the hardening learns _nothing_ your use of it
can not reduce your security.

Since there is a straightforward way to achieve this (simpler than
Makwa; based on the same hardness assumption), I can't see us
bothering with anything less than information theoretic security if we
cared about delegation to untrusted parties. If we don't care much
above we can use the first protocol I gave with any PHC candidate as
KDF.