by Jan Camenisch, Anja Lehmann, Anna Lysyanskaya and Gregory Neven
The authors have developed a three-pronged approach that can secure all of your passwords for social media, email, cloud files, shopping and financial websites, with one practically hack-proof password. This password is secured by the new “Memento protocol.”
In the 2000 film “Memento” by Christopher Nolan, the protagonist suffers from short-term memory loss. Throughout the film, he meets people who claim to be his friends but, due to his condition, he never really knows whether they are truly his friends, or whether they are just trying to manipulate him or steal something from him.
This scenario got the authors thinking, because it leads to an interesting cryptographic problem: If all you can remember is a single password, then how can you store your secrets among your friends, and later recover your secrets from your friends, even if you may not remember exactly who your friends were? Or, put differently, can a user protect all her sensitive data on a set of servers with a single password, in such a way that even malicious servers do not learn anything about the data or the password when the user tries to retrieve it?
These basic questions have many applications, including protecting and recovering data on mobile devices if they are lost, encrypted data storage in the cloud, and securing access to third-party websites such as social networks, online shops, healthcare portals, or e-banking. Users nowadays are expected to remember dozens of strong, different passwords at home and in the workplace. This is obviously unreasonable, so we need a better solution.
Something important to realize about password security is that, whenever a single server can tell you whether your password is correct, then that server must be storing some information that can be used by an attacker to mount an offline dictionary attack, where the attacker simply tries to guess the password by brute force. These attacks have become so efficient lately that, if this piece of information is stolen from the server, the password itself must be considered stolen too.
The Memento protocol [1] overcomes this limitation by storing the password and data in a distributed way across multiple servers. No single server can autonomously verify a user’s password; it always requires the collaboration of the other servers. To gain access, an attacker would either have to hack more than a given threshold of the servers simultaneously, or try to mount an online guessing attack on the password. The former can be addressed by using servers in different security domains and running different operating systems. The latter is prevented by letting honest servers throttle password attempts, e.g., by blocking the account after too many failed attempts, much like is done for ATM cards.
Furthermore, the Memento protocol keeps your password safe even if the user is tricked into entering her password and authenticating with a set of corrupt servers. For example, suppose you created your account on three different servers that you trust are unlikely to collude against you or to get hacked all at the same time, for example ibm.com, admin.ch, and icann.org. Next, you may be tricked in a phishing attack and you mistakenly log into ibn.com, admim.ch and ican.org. Game over for your password, right?
Wrong. With the Memento protocol, even in this situation the servers cannot figure out your password or impersonate you, because the protocol doesn’t let the servers reconstruct the password when testing whether it’s correct.
Instead, the protocol roughly proceeds as follows. When creating the account, the user’s password p is encrypted under a special key so that at least a threshold of the servers have to collaborate to decrypt it. When logging in with password attempt q, the servers send the encryption of p back to the user, who then uses special homomorphic properties of the encryption algorithm to transform the encryption of p into an encryption of “one” if p=q, or into a an encryption or a random string if p≠q. The servers jointly decrypt the resulting ciphertext to discover whether the password was correct.
Some more cryptographic machinery is added to the protocol to obtain strong security guarantees, e.g., for the case that the user makes a typo when entering her password or that the attacker has some side information about the password, but this is the basic idea.
When using the Memento protocol, the user only needs one username and password to retrieve all her secrets. At the same time, she can rest assured that even if some of her servers get hacked or she tries to log into the wrong servers, here password and secrets remain secure.
If only the lead character in the film “Memento” had it so easy!
Link:
http://www.zurich.ibm.com/csc/security/
Reference:
[1] J. Camenisch, A. Lehmann, A. Lysyanskaya, and G. Neven, “Memento: How to Reconstruct your Secrets from a Single Password in a Hostile Environment”, Advances in Cryptology – CRYPTO 2014, Springer LNCS, Volume 8617, 2014, pp 256-275.
Please contact:
Jan Camenisch, IBM Research Lab Zurich
E-mail
