How to generate a key using any $m$ passwords out of total $n$?

Question

My application requires an AES-256 key K for some secure operation. In order to avoid saving this key in application, I have implemented following scheme:

1. There are 5 individuals who enters their passwords in application. Lets call them PW1..PW5

2. Using these passwords, I have generated the key as:

   K = KDF(PW1 || PW2 || PW3 || PW4 || PW5)
   

The problem is that now I need to modify the application such that it works even if only 3 out of 5 passwords are available (but no less than 3). This is required because even if we lose one or two passwords (accident, person refusing to enter password etc.), we are able to recover from that situation.

Please can you advise how it can be achieved?

Answer 1

One option would be to generate a random key, split it using Shamir's secret sharing, then encrypt each of the split parts individually under a key derived from each user's password.

So for example:

key = read from os.urandom()
d1,d2,...d5 = split(key=key,n=5,k=3)
e1 = encrypt(d1, KDF(PW1)), e2 = encrypt(d2, KDF(PW2))...

key can then be derived from all of the encrypted shares (e1, ...) and user's passwords (PW1, ...). You could store the encrypted shares in the application and be confident that without at least three of the passwords you wouldn't be able to derive the key.