Interview and Social Verification

I had an interview with an interesting company yesterday, Border Stylo. They have two products currently, both social networking applications: Write on Glass and Retrollect (a mobile app).  During the interview (for their Privacy Architect position) the question arose of how to secure password retrieval.  In a subsequent letter to their VP of Engineering, I proposed a solution which I include below.

The criteria are as follow:

  • The company doesn’t store the password in plaintext and therefore can’t retrieve it directly.  
  • The company doesn’t want to collect extraneous information (such as a person’s elementary school), choosing instead to minimize information collected to the absolute minimum.  This policy precludes a series of “security” questions which are often present those needing to reset passwords. [The security risk in this approach is that an attacker with access to details about a person could emulate that person’s response].
  • The company doesn’t want to send an email with a link to reset the password.  [This common method also runs the risk of a compromised email account being used to compromise the users account on this system].
Authentication typically requires a user to supply one of the following: something the know, something they have or something they are (a biometric identifier).  
Strong authentication involves providing 2 of the 3 authentication factors above.
In trying to solve this problem, I began thinking, what information does this social networking company have that the user can provide to authenticate themselves?  It dawned on me that beyond a name and email (which wasn’t usable for the above reason) they have information about the friends or contacts in the user’s social network.
Now the simple response would be to require the user to identify some of their friends, but this leaks information to a potential attacker as to who the friends are. The better approach is to require the user to contact their friends and get their friends to verify they user.  We can do this using m-of-n secret sharing.

Here is the process:

The most common method of securely storing passwords in databases is through hashing.  A user will enter a password on a website and that password is hashed and compared against the hashed password the system has for the user.  If the hashes match, the user is authenticated.  Even if someone were gain access to the database, they may not be able to authenticate in the system because they would have solve for x, from h(x) and the hashing function is considered one-way.

A more complex method involves adding random salt and iterative hashing to each authentication request in order prevent replay attacks, but I leave that for another post.

Assuming a social networking system uses the password hashing method discussed above and the user has forgotten the password, we can authenticate them by making their social circle authenticate them for us. During account setup, the user is prompted to set a security level, M (essentially the number of friends that need to authenticate them).

When the user attempts to login and can’t (because they’ve forgotten the password), they are given the option of authenticating through friends.  They are supplied a URL to give to their friends.  The friends, once they visit the URL, are informed the user is unable to log into the network and if they want to authenticate their friend to supply them a code.  The code is actually one slice of an m-of-n secret share of the password hash. The friends are encouraged “verify” their friends before giving them the code.  The assumption is while an impostor may be able to dupe a few friends, the chance of duping M friends decreases as M increases. Once the user collect M codes, they enter it into the login page, which reconstitutes the hash of their password, authenticates them and allows them to set a new password.

Choosing M fairly low, say 1 or 2, is mostly insecure since it allows one or two friends to collude to enter a user’s account.  Choosing M high may be unacceptably bothersome to most users but the benefit is that users can set their own security level.

Comments are most welcome.