Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Possible duplicate of Can I pre-define the points in Shamir's Secret Sharing algorithm. (Your question is somewhat more general, since it doesn't mention Shamir's scheme explicitly, but the answers apply to the more general case as well.) –  Ilmari Karonen Jan 23 '13 at 18:29
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks @Michael. You rock! (and I feel so stupid that I couldn't think of extending the scheme). –  Hemant Jan 24 '13 at 14:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.