One of the biggest pillars for Microsoft Edge is trust. Today, to further bolster that trust while keeping our customers safe, we introduce a new feature called Password Monitor. The feature notifies users if any of their saved passwords have been found in a third-party breach. All this is done while ensuring Microsoft doesn’t learn the user’s passwords. The underlying technology ensures privacy and security of the user’s passwords, which means that neither Microsoft nor any other party can learn the user’s passwords while they are being monitored.
This unique security feature is possible due to pioneering cryptography research and technology incubation done here at Microsoft Research. The feature is a culmination of our research on homomorphic encryption and its practical applications. It is the result of a collaboration between former research incubation group, the Cryptography and Privacy Research Group, and Edge product team. The teams have built on the Microsoft SEAL homomorphic encryption library to implement a new protocol to bring Password Monitor to our Edge users.
At a high level, when a password is saved in Edge, the browser needs to contact a server to check if the password was found in a breached list. It is also necessary to periodically check this in case there are new instances of breached passwords found. The most important aspect is that the Edge servers must never learn any information about the client’s usernames or passwords. It is also important to ensure that no outside party is able to gain access to this information while it travels between users and Edge servers (as in man-in-the-middle attacks).To learn how to enable Password Monitor in the Edge browser and access a list of frequently asked questions, read the Password Monitor support page (opens in new tab).
From the onset, this was a huge challenge for the teams. Microsoft Edge powers millions of users and supports a range of devices, old to new, with varying storage, computing power, and connectivity. We want to ensure that every Edge user on every platform can trust and benefit from this feature. For this, the Microsoft SEAL library was modified to support low-end devices, to have multi-platform support (Mac, ARM, x86), and to optimize the protocol for network efficiency. The protocol is based on the research done by the cryptography research team, presented in two papers: “Fast Private Set Intersection from Homomorphic Encryption” and “Labeled PSI from Fully Homomorphic Encryption with Malicious Security.”
How Password Monitor secures your information
Homomorphic encryption is a relatively new cryptographic primitive that allows computing on encrypted data without decrypting the data first. For example, suppose we are given two ciphertexts, one encrypting 5 and the other encrypting 7. Normally, it does not make sense to “add” these ciphertexts together. However, if these ciphertexts are encrypted using homomorphic encryption, then there is a public operation that “adds” these ciphertexts and returns an encryption of 12, the sum of 5 and 7.
First, the client communicates with the server to obtain a hash H of the credential, where H denotes a hash function that only the server knows. This is possible using a cryptographic primitive known as an Oblivious Pseudo-Random Function (OPRF). Since only the server knows the hash function H, the client is prevented from performing an efficient dictionary attack on the server, a type of brute force attack that uses a large combination of possibilities to determine a password. The client then uses homomorphic encryption to encrypt H(k) and send the resulting ciphertext Enc(H(k)) to the server. The server then evaluates a matching function on the encrypted credential, obtaining a result (True or False) encrypted under the same client key. The matching function operation looks like this: computeMatch(Enc(k), D). The server forwards the encrypted result to the client, who decrypts it and obtains the result.
In the above framework, the main challenge is to minimize the complexity of the computeMatch function to obtain good performance when this function is evaluated on encrypted data. We utilized many optimizations to achieve performance that scales to users’ needs. Check out both papers mentioned and linked earlier for a description of these optimizations and details on how the protocol works.
Microsoft research podcast
Collaborators: Silica in space with Richard Black and Dexter Greene
College freshman Dexter Greene and Microsoft research manager Richard Black discuss how technology that stores data in glass is supporting students as they expand earlier efforts to communicate what it means to be human to extraterrestrials.
To optimize the performance of our protocol, we further shard the database D of breached credentials, according to the first two bytes of a certain hash function applied to the username. When the browser submits a query, it will compute these two bytes from the username and send it along with the encrypted credentials. Suppose the database D consists of 4 billion credentials, then after sharding each subset, it will contain about 60,000 credentials on average. This significantly improves efficiency since the server only needs to perform the homomorphic evaluation on one such subset for each query.
The entire library has been optimized to run efficiently on the diverse set of devices, from the lowest end to the high end, and varied platforms supported by Edge. The core principles behind the optimization were to keep the Edge binary minimal, consume less network bandwidth, and ensure minimal impact to battery (in laptops) while keeping the CPU utilization to a minimum, both on the client side and the server side. It also required supporting a large number of clients.
At Microsoft, we are glad to bring this first consumer application that utilizes homomorphic encryption to help protect our users. We will continue to build on this to enable all developers to deploy such secure services using Homomorphic Encryption and other privacy-preserving technologies. Check out the Cryptography and Privacy Research Group page for more information on homomorphic encryption and other projects, and reach out to us if you are interested.
Acknowledgements
Password Monitor is the result of a great collaboration between former research incubation group, Cryptography and Privacy Research Group, and Microsoft Edge, with members including the authors of this post along with: Suhrid Palsule, Tulasi Menon, Ankit Jain, Prasenjit Mukherjee, Gurpreet Virdi, Austin Orion, Carlos Frias, Shabnam Erfani, Hamed Khanpour, Steven Chith, Melissa Chase, Esha Ghosh, Wei Dai, Qiaofei Ye, and Hao Chen (former Microsoft Senior Researcher).
Security, privacy, and cryptography