[Cryptography] Follow up on my password replacement idea

[Bill Cox]

On Mon, Sep 21, 2015 at 12:28 AM, Ilya Kasnacheev <ilya.kasnacheev at gmail.com
> wrote:

> What do you think of that? Because current situation with passwords on the
> internet is unmanageable and replacement is needed - waterproof enough to
> do users more good than harm.
>


I agree that a replacement, or at least a significant upgrade, is needed to
passwords.

Your scheme was fun to read.  It is yet another scheme to split secrets.
The "canonical" method is probably Shamir's Secret Sharing
<https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing>.  For arm-chair
crypto enthusiasts like you and me, I suspect you'll find that scheme a bit
heavy-weight for a low number of devices.  A simpler scheme for sharing
sharing a secret between 3 parties is to take the secret S and generate 3
pieces that must be XORed together.  Do this by computing 2 random values
R1 and R2:

A = R1
B = R1
C = S ^ R1 ^ R1

Recreating S requires A, B and C, like your scheme.  Distribute (A, B) to
Alice, (B, C) to Bob, and (A, C) to Charlie.  Each has a copy of what the
other two are missing to recreate the secret.  This scheme does not even
require a cryptographic hash function, though I think it does improve
security, in case we have biased random generators.  However, this scheme
scales poorly, requiring O(N^2) keys for N parties.  Shamir's Secret
Sharing scales linearly.  Your scheme is interesting in that it scales
better than the simple deterministic XOR scheme, but it is probabilistic.
For example, if we split the secret into 128 keys, and gave 1024 people
each one copy of one key, there would be 8 copies of each key.  The
likelihood that any random 512 of them could recover the secret would be
about 1 - (255/256)^128 ~= 60%.  However, if only 256 of them got together,
the chance would be about 1 in a million.  Using 2 keys per user, we can
tighten up the probability distribution considerably.  So, this scheme has
nice scaling properties.  It still is probably better just to use the
canonical method.

A good example of an attempt to use a secret sharing scheme in
authentication is the PolyPassHash
<https://password-hashing.net/submissions/specs/PolyPassHash-v1.pdf>
algorithm, though they only covered password security on the server.

I think the problem you are trying to solve is authentication, which is
tougher than password security.  Having even 2 devices participate in
authentication dramatically improves security.  Google does this with 2-Step
Verification <https://www.google.com/landing/2step/>.  However, the number
of people who have bothered to use this is an insignificant fraction of all
users, so the problem of authentication remains very tricky.

So, the problem we need to solve is making 2-devices (or more) for
authentication almost invisible to the user.  If even touching a screen is
required, 99% of all users will not bother to protect their bank accounts
with the required extra effort.  Imagine if you had to touch your phone to
log into your work account on your laptop.  That's no biggie, but let's say
you forgot to charge your phone and when you got to work it was dead?

This authentication problem is a lot tougher than it sounds.  It goes way
beyond what cryptographers worry about all day.  It will take solid
engineering to improve the situation, in addition to solid crypto.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150922/5fa2ff1c/attachment.html>