<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Sep 21, 2015 at 12:28 AM, Ilya Kasnacheev <span dir="ltr"><<a href="mailto:ilya.kasnacheev@gmail.com" target="_blank">ilya.kasnacheev@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div><div><div>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.</div></div></div></div></div></div></div></div></div></div></blockquote><div><br></div><div><br></div><div>I agree that a replacement, or at least a significant upgrade, is needed to passwords.</div><div><br></div><div>Your scheme was fun to read.  It is yet another scheme to split secrets.  The "canonical" method is probably <a href="https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing">Shamir's Secret Sharing</a>.  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:</div><div><br></div><div>A = R1</div><div>B = R1</div><div>C = S ^ R1 ^ R1</div><div><br></div><div>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.</div><div><br></div><div>A good example of an attempt to use a secret sharing scheme in authentication is the <a href="https://password-hashing.net/submissions/specs/PolyPassHash-v1.pdf">PolyPassHash</a> algorithm, though they only covered password security on the server.<br></div><div><br></div><div>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 <a href="https://www.google.com/landing/2step/">2-Step Verification</a>.  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.</div><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>Bill</div></div></div></div>