Virgil Security is excited to announce Pythia - a technology that finally solves the password breach problem.
Virgil Security has taken Pythia, designed by Adam Everspaugh and Rahul Chaterjee, University of Wisconsin–Madison; Samuel Scott, University of London; Ari Juels and Thomas Ristenpart, Cornell Tech, and built a cloud service that protects password databases in the most secure way possible. Pythia provides multiple innovations over what’s considered current state-of-the-art in password security: cryptographic leverage for the defender (by eliminating offline password cracking attacks), detection of online attacks, and key rotation that renders stolen password databases useless.
Technical details can be found in the Virgil Security Pythia white paper. Sign up for the beta waitlist here.
So how does it work?
Let’s go directly to the source. One of the original authors of Pythia, Adam Everspaugh, explains how Pythia works and why it’s groundbreaking.
What’s wrong with passwords and password security today?
We all want to move beyond passwords. Unfortunately, it's the most prevalent form of authentication. The large majority of online services, devices, laptops, and phones require passwords. And worst, the way that most services are storing and protecting passwords is fundamentally flawed.
Criminals steal devices, break into online services, and steal password databases. Once they have these password databases they run cracking software to recover most passwords. On a single laptop an attacker can try 1 trillion different passwords in 2 weeks (2^20 passwords/second * 2^20 seconds/2 weeks = 2^40 = 1T). Serious attackers can throw a few thousand dollars of hardware - graphics processing units (GPUs) - and that number goes up to 10 quadrillion. That's insane. On the dark markets, passwords sell in the range of $1 to $30 per account 1. That's a big incentive for criminals.
So hardware for passwords cracking is getting faster, but human biology doesn't improve at a noticeable rate. We can't magically learn to memorize longer and more complex passwords - and at the same time we're adding more and more online services and devices each year.
The current industry-recommended best practice is for services that store passwords to use "hard functions" to process these passwords. These functions - scrypt, bcrypt, and iterated hashing tools - make password processing slower (or use more memory) and so the burden is also applied to the password attackers. Unfortunately, these techniques put the same burden on the good guys - the service also has to pay this performance penalty on every legitimate login. These techniques don't give any leverage to the defenders. (Unlike, say, encryption, where the legitimate key holder can encrypt and decrypt quickly, but attackers have an exponentially harder problem trying to crack the key.)
How does Pythia solve those problems?
Pythia provides multiple innovations over what’s considered state-of-the-art in password security today: cryptographic leverage for the defender (by eliminating offline password cracking attacks), detection for online attacks, and key rotation to recover from stolen password databases.
Pythia is designed for performance and scalability. If the crypto server and the requester (like a web server) are on the same local area network (so connections are fast) Pythia is faster than the existing techniques of iterated hashing, bcrypt, and scrypt. Instead of slowing down attackers (and defenders) by running harder and harder operations, we use cryptography to give defenders back the advantage.
We designed Pythia with the goal of scaling up to protect every password in the world. We haven't (yet) tested things like multi-region syncing, but we were designing with billions of passwords as our scalability target.
To handle other practical issues, Pythia builds in support for key rotations and detecting online guessing attacks.
When a password database is breached, Pythia renders the stolen passwords useless with key rotation. A website operator can request a key rotation from the Pythia server, update all the stored passwords, and request that the original key be destroyed. Once it is, any stolen passwords are useless. No one can recover them without the key.
Pythia also builds in online attack detection. If a password database is stolen it can't be cracked offline anymore, but an attacker can send requests to the crypto server. Pythia was designed so that all requests require an unforgeable user ID and client ID provided in plaintext (not blinded like passwords). This allows the crypto server to detect attacks. Detection is very powerful and often overlooked as a defensive mechanism - the crypto server can lock accounts, throttle (slow down) requests, and send out alerts to the website that owns the password database.
How did you come up with it? What was the rest of the team like?
I was working on my PhD in computer science at the University of Wisconsin and reading headlines each week about password database thefts and passwords being cracked. All I could think was, "there's gotta be a better way". I worked on the problem with two other PhD students: Sam Scott and Rahul Chatterjee (both now at Cornell Tech in NYC), my PhD advisor, Tom Ristenpart, and we pulled in Ari Juels because he had done a lot of work on other cryptographic password protection schemes. We went through a lot of iterations because the schemes we designed kept getting broken (by us) or we couldn't prove that they were secure enough. (Turns out, crypto is really hard to get right - who would have guessed?)
Eventually we created a construction that we could prove secure and it also gave us key-updatability, which is a big breakthrough for password protection. At this point what we had were equations on paper. The we had to build it in software and make it fast.
We built it twice, actually. Pythia uses a type of cutting edge cryptography called bilinear pairing elliptic curves. So we initially built Pythia using a research library that turned out to be low quality and not as performant as we wanted. But we got it working and got reasonable performance numbers and shipped off a paper submission to Usenix Security. Over the next several months we found a better crypto library, Relic, and re-wrote Pythia again from scratch. By the time we published the paper the scheme was much faster and more robust, but it was still a proof-of-concept.
Now Virgil Security has again re-written Pythia from scratch and created legit production libraries and bindings for multiple languages, not just Python. They've also improved security by moving to a stronger elliptic curve than the one we were using.
All in - I spent a full year thinking deeply about passwords full-time: examining every technique in use (or proposed) for passwords, and thinking about the problems from multiple angles: How can users protect themselves from insecure web servers? (Use a password manager with random passwords.) How can websites protect passwords without requiring users to remember complex passwords? (Use Pythia.) How can we protect passwords on our phones? On our laptops? How do sysadmins protect SSH keys and investors protect Bitcoin wallets? It was a busy year.
General overview of how it works
Here's a quick description of Pythia being used by, say, a web server that wants to protect and verify user passwords on login. The user authenticates to a website in the usual way: POSTs a username and password to a website via TLS (https). The website cryptographically "blinds" the password (using a per-request, random key) and sends a request to a crypto server with the blinded password, but also a client ID (for the web server) and a user ID (to detect online attacks). The crypto server uses all three inputs plus a cryptographic key that it stores to transform the password using a keyed pseudorandom function, or PRF, and sends the result back to the web server. The web server then "deblinds" the result using the same blinding key. In the end, the web server learns a cryptographically protected version of the password for storage (or checking against a stored password) but never learns the key. The crypto server holds the key, but never sees any passwords. The crypto server also sees the client and user IDs which are used to detect online attacks.
All together, Pythia brings three key security innovations: cryptographic leverage for the defender, online attack detection, and key rotation to recover from stolen password databases.
Cryptographic leverage comes from the keyed PRF applied by the crypto server. And because passwords are blinded before being sent to the crypto server there's no security risk of using the crypto server.
Online attack detection is also important. Pythia eliminates offline password cracking (which is brutally effective), but an attacker might resort to online attacks if they steal a password database. The crypto server needs to be able to distinguish between a large volume of legitimate requests (say, thousands of unique users logging into a website) and an online guessing attack (when an attacker submits thousands of requests to the crypto server to guess the correct password for one user account). Here's where the client and user IDs are important. They are unforgeable - if the request uses the wrong client or user ID, they'll never get the correct output since these are rolled into the protected version of the password. And if the crypto server sees too many requests for a single account, it can take action: alert the website owner, lock accounts, or throttle (slow down) requests.
Key rotation enables a website to recover even if they’ve been compromised. If a compromise is discovered, the website can request a key rotation, receive an update token, and update its password database from the old key to a new key - all without requiring users to login, change their password, or re-verify their accounts. And once the old key is removed from the crypto server, stolen information is useless (we call it "cryptographically erased"). Without that key, stolen passwords can never be recovered - stolen password databases become a giant chunk of useless, random bits.
Why is it significant?
Using Pythia instead of existing techniques mean no more offline password cracking; detection for online guessing attacks; and key rotation to recover from compromises.
Without key rotation, if you detect a password database theft you have only bad options, and this describes most websites today. Either ignore the breach (like Yahoo did) until it blows up; or flag all the accounts that were affected (like LinkedIn did) and require all users to perform email validation and change their passwords. Both of these options are terrible - both for companies that have their reputations impacted and for users that have to reset their password and worry about how many other accounts are at risk because of password reuse.
Plus, Pythia is fast and scalable. Instead of cranking up the work factor in bcrypt and slowing down legitimate client logins to painful levels, we can use cryptography, which is reasonably fast for defenders.
What does it mean for developers?
For developers or the security team: no more difficult conversations with management about what to do if a password database is compromised (or believed to be compromised). Instead of worrying about which is worse: bad PR from the announcement or risking customer security, site owners have the advantage - they know that passwords are still secure as long as the crypto server is not compromised and they can rotate keys to recover from compromises.
What does it mean for end users?
If one is using a website that uses Pythia to protect passwords, it means that password is much better protected. If the website gets broken into, the attackers won't get your password, and this also prevents attackers from accessing other online accounts that might have the same password. From the point of view of the website user, things thankfully don't change much - which is the goal. The user doesn't have to install any software, or change their normal authentication flow. Sadly, it means they still enter a password on login, but there's no additional hassle.
How does it fit into the evolution of cryptography and applied cryptography?
This is an important step forward for improving security. In the past two decades we've seen increasing use of cryptography and it's having a beneficial impact on security. But cryptographers (who are mostly academics) often overlook important practical aspects: things like key management, attack detection, and compromise recovery. In practice: things break, vulnerabilities get exploited, attackers break-in and steal things; we need tools and techniques that deal with these scenarios. Secure-if-nothing-goes-wrong is unacceptable in the real world.
We designed Pythia with this defense-in-depth mindset. Passwords are going to be weak: so we need to detect online guessing attacks. Passwords databases get stolen (over and over): so we need compromise recovery. Crypto servers will get broken into: we need key rotation to serve both sides.
What do you think about Virgil Security’s use of Pythia?
The implementation is great. You can tell looking through the code that these are talented developers with secure coding skills. It's great that they have a production implementation, and a service for providing the crypto server side. Plus, the implementation is open source and the entire implementation is there. It's possible to build and run your own Pythia crypto server if you have the security chops to do it right. I think that's really cool.
Is this the commercial application you imagined?
It's the major one I assumed would be rolled out. It's an enormous benefit to developers and website operators for someone like Virgil to provide the crypto server as a subscription service and provide the client libraries needed to connect and use that service. Having the crypto server managed by a dedicated group that's distinct from the requesting side makes it less likely that both the password database and the crypto server can be simultaneously compromised. Plus, developers and site operators are busy building code and features; they need solutions that are easy to roll out and secure-by-default. Using Virgil's Pythia client and a managed service is ideal for security and developer velocity.
I'm not privy to Virgil's plans, but there are uses for Pythia, too. It could be used to encrypt sensitive information on laptops, portable storage devices, and mobile phones. Requiring a password and an internet connection to access these files is a bit of a hassle, but for the most sensitive information (health records, financial and customer info) this is reasonable. Plus, the request to the crypto server creates a central audit log. Companies can see who is accessing their most sensitive information, how often, from where, and on which devices. Plus, if devices are lost or stolen, the information can be erased centrally by deleting the keys on the crypto server. This means that companies can show auditors that they're tracking all access to information and can demonstrate that lost devices have been wiped and the information can't be exposed. That's a big deal.
What are you up to now?
I'm the cryptography expert for Uptake Technologies in Chicago [https://www.uptake.com/expertise/security]. Uptake is an industrial analytics company: we collect and analyze telemetry from industrial assets (think: freight trains, wind turbines) to provide operating insight and predict failures. We process an enormous amount of our customers' data and it's my job to make sure that we're using cryptography properly. In addition to me, Uptake has a large and talented security team: two shifts of security analysts looking through logs and alerts; an internal application security and penetration testing team; distinct infrastructure and cloud security teams, and a group dedicated solely to tracking risks and ensuring compliance. It's a cool place to work.
[1][On the Economics of Offline Password Cracking - Purdue CS](https://www.cs.purdue.edu/homes/jblocki/papers/SP18EconomicsOfOfflinePasswordCracking.pdf)
----
Email Rebecca at VirgilSecurity.com with questions or suggestions.
Want to learn more about the Virgil Security products? Sign up for a free Virgil account and join our Slack community to start a conversation.
Virgil Security, Inc. is a stack of security libraries and all the necessary infrastructure to enable seamless, end-to-end encryption for any application, platform or device.
We guide software developers into the forthcoming security world in which everything will be encrypted (and passwords will be eliminated). In this world, the days of developers having to raise millions of dollars to build secure chat, secure email, secure file-sharing, or a secure anything have come to an end. Now developers can instead focus on building features that give them a competitive market advantage while end-users can enjoy the privacy and security they increasingly demand.