Breach-proof Password Use Case

Introduction

Most data breaches are actually caused by password breaches. A password is known as a universal enabler of fraud: most users re-use the same password across all their accounts. Breach it once, use it multiple times. In theory, two-factor authentication & login fraud detection techniques can mitigate password breaches, but in practice they're inconvenient and users don't actually utilize them.

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.

Breach-proof password - the most cryptographically protected user password. It allows developers to protect their user passwords if the database is stolen or compromised.

Press here to read more about our solution

Problem

In standard password security implementation, passwords are hashed and stored in the user table. Even though hashing is a one-way transformation, there are techniques to reverse engineer them back to the original passwords: rainbow table attacks, brute-force & dictionary attacks.
In advanced password security implementations, a random salt is added to the password before hashing. The problem is that this random salt has to be stored in the user table, so that the login function can verify the password. Obviously this is a security weakness.

Solution

Virgil Security presents Pythia, a new technology that gives you a new, more secure mechanism that "breach-proofs" user passwords and lessens the security risks associated with weak passwords. With Pythia, passwords are no longer the weakest link in your system.

Virgil Pythia protects users' passwords without having to know a user's identity, password or its hash. Virgil Pythia doesn't generate a new user password; it just makes a password cryptographically safer.
You can easily integrate Virgil Pythia with your Server side. Pythia technology doesn't change a business logic of your digital solution and doesn't affect your authentication mechanism.
Pythia detects online attacks and if Pythia or your user database is compromised, attackers still can't run offline attacks.
You can quickly update a user's breach-proof password in the event someone compromises your database without having to create new user passwords, nor do you need to terminate work of your system.

How it works

A user sends his or her password and login to your Application Server and you identify a user using your own authentication mechanism.
Then you have to pass a user's password or its hash to Pythia SDK.
Pythia SDK blinds a user's password.
Then Pythia SDK sends a request to Pythia Service in order to receive a user's transformed blinded password.
Pythia Service creates a transformed blinded password and sends it to your App Server.
The Pythia SDK de-blinds the transformed blinded password on the App Server and get a deblinded password (breach-proof password).
Then Pythia SDK compares this calculated user's breach-proof password with a value that is stored in your DB.

Pythia Introduction

So, you perform all operations under user's password on your App Server, thus Virgil Pythia protects users' passwords without having to know a user's identity, password or its hash. Pythia SDK blinds and de-blinds users passwords each time a user logs in, and a user won't even know it's happening. Technical details can be found in the Virgil Security Pythia white paper.

Going through the tutorial you find the following expressions:

Parameter	Description
Blinded Password	a user's password that is hidden from Pythia Service with unique random number.
Transformed Blinded Password	a blinded password, protected using Pythia Service data.
Deblinded Password	user's breach-proof password, that is a cryptographically the most protected.

What Virgil provides for developers

Virgil Pythia Service for storing & managing Pythia Application and its parameters.
Virgil Pythia SDK which allows you to easily manage a Crypto Library and communicate with Virgil Services.

Let's get started!

Collect account information

The first thing you need to do is to create Pythia Application on Virgil dashboard and grab all the necessary information to set up your Server side.

You need the following account and application parameters from your dashboard:

Parameters	Description
API Private Key	Unique Private Key for an access to Virgil Services. API Key is used to generate a JWT token and authenticate you at Pythia Service - generate one here.
API Key ID	Unique identifier of your API Private Key in Virgil infrastructure. You'll find your API Key ID in the API Key section on your Virgil Dashboard.
App ID	Presents your Pythia application in Virgil Services.
Proof Key	Value that is used to verify Pythia Service responses.

Also, going through the tutorial you find the following expressions:

Parameter	Description
Blinded Password	a user's password that is hidden from Pythia Service with unique random number.
Transformed Blinded Password	a blinded password, protected using Pythia Service data.
Deblinded Password	user's breach-proof password, that is a cryptographically the most protected.

Install and configure Pythia SDK

On this step you need to install and set up Virgil SDK to communicate with the Virgil Pythia Service.

Install SDK Package

Virgil Pythia SDK uses the Virgil Crypto library to perform cryptographic operations.

Click here to see complete instructions for SDK installation

The Virgil .NET Pythia is provided as a package named Virgil.Pythia. The package is distributed via NuGet package management system.

The package is available for .NET Framework 4.5 and newer.

Supported Platforms

.Net Core 2.0 (MacOS, Linux)

Installing the package using Package Manager Console:

Run PM> Install-Package Virgil.SDK -Version 0.1.0-beta

The Virgil Pythia Go SDK is provided as a package named pythia-go. The package is distributed via GitHub.

The package is available for Go 1.10 or newer.

Step #1. Install a Crypto Library (C++)

Pythia Go SDK requires a Crypto Library (Virgil Crypto Library) to perform cryptographic operations.

There two ways to install the Crypto Library:

The first, if you are building from sources, install prerequisites as described here and then install the library:

go get -u -d gopkg.in/virgilsecurity/virgil-crypto-go.v5
cd $(go env GOPATH)/src/gopkg.in/virgilsecurity/virgil-crypto-go.v5
make

The second, if you use Linux x64 or Darwin x64 architecture, you can use the pre-built crypto binaries for Linux:

CRYPTO_LIB=virgil-crypto-2.4.4-go-linux-x86_64.tgz

or for MacOS:

CRYPTO_LIB=virgil-crypto-2.4.4-go-darwin-17.5-x86_64.tgz

and then install the library:

go get -u -d gopkg.in/virgilsecurity/virgil-crypto-go.v5
wget https://cdn.virgilsecurity.com/virgil-crypto/go/$CRYPTO_LIB
tar -xvf $CRYPTO_LIB --strip-components=1 -C $(go env GOPATH)/src/gopkg.in/virgilsecurity/virgil-crypto-go.v5/

Step #2. Installing Virgil Pythia Go package

If the Virgil Crypto Library is installed, install Pythia SDK library with the following code:

go get -u github.com/VirgilSecurity/pythia-go

The Virgil Java SDK is provided as a package named com.virgilsecurity.sdk. The package is distributed via Maven repository.

The package is available for:

Java 7 and newer
Android API 16 and newer

Prerequisites:

Java Development Kit (JDK) 7+
Maven 3+

You can easily add SDK dependency to your project, just follow the examples below.

Maven

Apache Maven is a software project management and comprehension tool.

To integrate Virgil SDK into your Java project using Maven, set up dependencies in your pom.xml:


    
        com.virgilsecurity
        pythia
        0.1.0

Gradle

Gradle is an open-source build automation system that builds upon the concepts of Apache Ant and Apache Maven and introduces a Groovy-based domain-specific language (DSL) instead of the XML form used by Apache Maven for declaring the project configuration.

Server

To integrate Virgil SDK into your Java project using Gradle, set up dependencies in your build.gradle:

dependencies {
    compile 'com.virgilsecurity:pythia:0.1.0'
}

Android

To integrate Virgil SDK into your Android project using Gradle, add jcenter() repository if missing:

repositories {
    jcenter()
}

Set up dependencies in your build.gradle:

dependencies {
    implementation 'com.virgilsecurity.sdk:crypto-android:5.0.2@aar'
    implementation ('com.virgilsecurity:pythia:0.1.0') {
        exclude group: 'com.virgilsecurity.sdk', module: 'crypto'
    }
}

Add INTERNET permission to AndroidManifest.xml

The recommended way is to install form npm:

npm install virgil-pythia

The Virgil Pythia SDK is compatible with node.js 6 or newer.

You will also need to install the virgil-sdk and virgil-crypto packages separately:

npm install virgil-sdk virgil-crypto

Although intended only for server-side usage, the pre-built version of the library can also be added to an html page via <script> tag:

For the pre-built version all name exports of virgil-pythia are available on the VirgilPythia global namespace.

Note that the virgil-crypto and virgil-sdk scripts must also be included. Also, the name of virgil-crypto script must be "virgil-crypto-pythia.browser.umd.min.js" not "virgil-crypto.browser.umd.min.js". The latter would give you a smaller bundle without the Pythia-related algorithms.

Configure SDK

When you create a Pythia Application on the Virgil Dashboard you will receive Application credentials including: Proof Key and App ID. Specify your Pythia Application and Virgil account credentials in a Pythia SDK class instance.

These credentials are used for the following purposes:

generating a JWT token that is used for authorization on the Virgil Services
creating a user's breach-proof password

Here is an example of how to specify your credentials SDK class instance:

// here set your Virgil Account and Pythia Application credentials
var config = new PythiaProtocolConfig
{
    AppId     = "APP_ID",
    ApiKeyId  = "API_KEY_ID",
    ApiKey    = "API_KEY",
    ProofKeys = new[] {
        "PK.1.PROOF_KEY"
    }
};

var pythia = PythiaProtocol.Initialize(config);

package main

import (
  "github.com/VirgilSecurity/pythia-go"
)


func main() {
  // here set your Virgil account and Pythia Application credentials
  ctx, err := pythia.CreateContext("API_KEY", "API_KEY_ID", "APP_ID", "PK.1.PROOF_KEY")
  if err != nil{
    panic(err)
  }

  pythia := pythia.New(ctx)
}

// here set your Virgil Account and Pythia Application credentials
PythiaContext context = new PythiaContext.Builder()
    .setAppId("APP_ID")
    .setApiPublicKeyIdentifier("API_KEY_ID")
    .setApiKey("API_KEY")
    .setProofKeys(Arrays.asList("PK.1.PROOF_KEY"))
    .setPythiaCrypto(new VirgilPythiaCrypto())
    .build();

Pythia pythia = new Pythia(context);

// server.js

const express = require('express');
const bodyParser = require('body-parser');

// require 'virgil-crypto' bundle with Pythia-related algorithms implementations.
// Simple `require('virgil-crypto')` would give you a smaller bundle without those algorithms
const {
  VirgilCrypto,
  VirgilPythiaCrypto,
  VirgilAccessTokenSigner
} = require('virgil-crypto/dist/virgil-crypto-pythia.cjs');
const { JwtGenerator, GeneratorJwtProvider } = require('virgil-sdk');
const { createPythia, BreachProofPassword } = require('virgil-pythia');

const virgilCrypto = new VirgilCrypto();

const jwtProvider = new GeneratorJwtProvider(new JwtGenerator({
  apiKey: virgilCrypto.importPrivateKey(process.env.VIRGIL_API_KEY),
  apiKeyId: process.env.VIRGIL_API_KEY_ID,
  appId: process.env.VIRGIL_APP_ID,
  accessTokenSigner: new VirgilAccessTokenSigner(virgilCrypto)
}));

const pythia = createPythia({
  virgilCrypto: virgilCrypto,
  virgilPythiaCrypto: new VirgilPythiaCrypto(),
  accessTokenProvider: jwtProvider,
  proofKeys: process.env.MY_PROOF_KEY // 'PK.1.'
});

const app = express();
const db = {
  users: []
};

app.use(bodyParser.urlencoded({ extended: false }));

Create breach-proof passwords

Now, you have to set up your database to store users' breach-proof passwords. Create additional columns in your database for storing the following parameters:

Parameters	Type	Size (bytes)	Description
salt	blob	32	Unique random string that is generated by Pythia SDK for each user
deblindedPassword	blob	384	user's breach-proof password
version	int	4	Version of your Pythia Application credentials. This parameter has the same value for all users unless you generate new Pythia credentials on Virgil Dashboard

Now we can start creating breach-proof passwords for users. Depending on the situation, you will use one of the following Pythia SDK functions:

Create BreachProofPassword is used to create a user's breach-proof password on your Application Server.
Verify BreachProofPassword is used to verify a user's breach-proof password.

Create Breach-Proof Password

Use this flow to create a new breach-proof password for a user.

Remember, if you already have a database with user passwords, you don't have to wait until a user logs in into your system to implement Pythia. You can go through your database and create breach-proof user passwords at any time.

So, in order to create a user's breach-proof password for a new database or available one, go through the following operations:

Take a user's password (or its hash or whatever you use) and pass it into a Create BreachProofPassword function in SDK.
Pythia SDK will blind a password, send a request to Pythia Service to get a transformed blinded password and de-blind the transformed blinded password into a user's deblinded password (breach-proof password).

// create a new Breach-proof password using user's password or its hash
var pwd = await pythia.CreateBreachProofPasswordAsync("USER_PASSWORD");

// save Breach-proof password parameters into your users DB

// create a new Breach-proof password using user's password or its hash
pwd, err := pythia.CreateBreachProofPassword("USER_PASSWORD")

if err != nil{
panic(err)
}
// save Breach-proof password parameters into your users DB
fmt.Println(pwd.Salt, pwd.DeblindedPassword, pwd.Version)

// create a new Breach-proof password using user's password or its hash
BreachProofPassword pwd = pythia.createBreachProofPassword("USER_PASSWORD");

// save Breach-proof password parameters into your users DB

app.post('/register', (req, res) => {
  const { username, password } = req.body;
  // create a new Breach-proof password using user's password or its hash
  pythia.createBreachProofPassword(password)
    .then(bpPassword => {
      // save the breach-proof password parameters into your database
      db.users.push({
        name: username,
        salt: bpPassword.salt.toString('base64'),
        deblindedPassword: bpPassword.deblindedPassword.toString('base64'),
        version: bpPassword.version
      });

      // the user is registered
      // this is a good time to authenticate the user (e.g. create a session and
      // set a session cookie on the response)
      res.send(201);
    }).catch(err => {
      console.log('Unexpected error:', err);
      res.send(500, 'Unexpected error occurred. Please try again later');
    });
});

After performing Create BreachProofPassword function you get previously mentioned parameters (salt, deblindedPassword, version), save these parameters into corresponding columns in your database.

Check that you updated all database records and delete the now unnecessary column where user passwords were previously stored.

Verify Breach-Proof Password

Use this flow when a user already has his or her own breach-proof password in your database. You will have to pass his or her password into an Verify BreachProofPassword function:

// get user's Breach-proof password parameters from your users DB

...
// calculate user's Breach-proof password parameters
// compare these parameters with parameters from your DB
var isValid = pythia.VerifyBreachProofPasswordAsync("USER_PASSWORD", pwd);

if (!isValid) 
{
    throw new Exception("Authentication failed");
}

//get user's Breach-proof password parameters from your users DB

...
// calculate user's Breach-proof password parameters
// compare these parameters with parameters from your DB
err = pythia.VerifyBreachProofPassword("USER_PASSWORD", pwd, false)

if err != nil{
//authentication failed
}

// get user's Breach-proof password parameters from your users DB

// ...

// calculate user's Breach-proof password parameters
// compare these parameters with parameters from your DB
boolean isValid = pythia.verifyBreachProofPassword("USER_PASSWORD", pwd, true);

if (!isValid) {
    throw new Exception("Authentication failed");
}

// server.js

app.post('/login', (req, res) => {
  const { username, password } = req.body;

  // get user's Breach-proof password parameters from your users DB
  const user = db.users.find(u => u.name === username);
  if (!user) {
    return res.send(404, 'User with the given name could not be found');
  }

  const bpPassword = new BreachProofPassword(
    user.salt,
    user.deblindedPassword,
    user.version
  );

  // Calculate the Breach-proof password from the user-provided password and
  // compare to the one stored in DB.
  // The third parameter tells the server that we're not interested in the
  // proof that the calculated Breach-proof password is cryptographically correct
  // (this proof is included by default when creating a new breach-proof password)
  pythia.verifyBreachProofPassword(password, bpPassword, false)
    .then(verified => {
      if (verified) {
        // the user-provided password matches what is stored in the DB
        // this is a good time to authenticate the user (e.g. create a session
        // and set a session cookie on the response)
        res.send(200);
      } else {
        // the user-provided password didn't match what is stored in the DB
        res.send(400, 'Password is incorrect');
      }
    }).catch(err => {
      console.log('Unexpected error:', err);
      res.send(500, 'Unexpected error occurred. Please try again later');
    });
});

The difference between the Verify BreachProofPassword and Create BreachProofPassword functions is that the verification of Pythia Service is optional in Verify BreachProofPassword function, which allows you to achieve maximum performance when processing data. You can turn on a proof step in Verify BreachProofPassword function if you have any suspicions that a user or Pythia Service were compromised.

Request Limits for a user

For the safety of a user's account, the number of requests to Pythia Service that your server can make for one user is limited to 1 request every 2 seconds. Reaching the limit triggers a safeguard, which temporarily suspends the account.

You can send an authentication request again in a few seconds.

Update breach-proof passwords

This step will allow you to use an updateToken in order to update users' breach-proof passwords in your database.

Use this flow only if your database was COMPROMISED.

How it works:

Access your Virgil Dashboard and press the "My Database Was Compromised" button.
Pythia Service generates a special updateToken and new Proof Key.
You then specify new Pythia Application credentials in the Pythia SDK on your Server side.
Then you use Update BreachProofPassword function to create new breach-proof passwords for your users.
Finally, you save the new breach-proof passwords into your database.

Here is an example of using the Update BreachProofPassword function:

// get previous user's VerifyBreachProofPassword parameters from a compromised DB

...

// set up an updateToken that you got on the Virgil Dashboard
// update previous user's Breach-proof password, and save new one into your DB

var updatedPwd = pythia.UpdateBreachProofPassword("UT.1.2.UPDATE_TOKEN", pwd);

//get previous user's VerifyBreachProofPassword parameters from a compromised DB

...

// set up an updateToken that you got on the Virgil Dashboard
// update previous user's deblindedPassword and version, and save new one into your DB
updatedPwd, err := pythia.UpdateBreachProofPassword("UT.1.2.UPDATE_TOKEN", pwd)
fmt.Println(updatedPwd.DeblindedPassword, updatedPwd.Version)

// get previous user's VerifyBreachProofPassword parameters from a compromised DB

// ...

// set up an updateToken that you got on the Virgil Dashboard
// update previous user's Breach-proof password, and save new one into
// your DB

BreachProofPassword updatedPwd =
    pythia.updateBreachProofPassword("UT.1.2.UPDATE_TOKEN", pwd);

// migration-script.js

// this is just for demonstration purposes,
// updating a real database is much more work
function updatePasswords () {
  for (let user of db.users) {
    const bpPassword = new BreachProofPassword(
      user.salt,
      user.deblindedPassword,
      user.version
    );

    // update user's current deblindedPassword and version with the Update Token
    // you've got from Virgil Dashboard
    const updatedBpPassword = pythia.updateBreachProofPassword(
      'UT.1.2.',
      bpPassword
    );

    // save the new data back to your DB
    user.salt = updatedBpPassword.salt.toString('base64');
    user.deblindedPassword = updatedBpPassword.deblindedPassword.toString('base64');
    user.version = updatedBpPassword.version;
  }
}

Get Help

Need some extra help? Get help now from our support team:

on Slack.
Virgil Help Center
or chat with us directly via Intercom from the Virgil Documentation pages.

Have fun building your digital solution!