blind_index

Blind Index

Securely search encrypted database fields

Works with Lockbox (full example) and attr_encrypted (full example)

Learn more about securing sensitive data in Rails

How It Works

We use this approach by Scott Arciszewski. To summarize, we compute a keyed hash of the sensitive data and store it in a column. To query, we apply the keyed hash function to the value we’re searching and then perform a database search. This results in performant queries for exact matches. Efficient LIKE queries are not possible, but you can index expressions.

Leakage

An important consideration in searchable encryption is leakage, which is information an attacker can gain. Blind indexing leaks that rows have the same value. If you use this for a field like last name, an attacker can use frequency analysis to predict the values. In an active attack where an attacker can control the input values, they can learn which other values in the database match.

Here’s a great article on leakage in searchable encryption. Blind indexing has the same leakage as deterministic encryption.

Installation

Add this line to your application’s Gemfile:

gem "blind_index"

Prep

Your model should already be set up with Lockbox or attr_encrypted. The examples are for a User model with has_encrypted :email or attr_encrypted :email. See the full examples for Lockbox and attr_encrypted if needed.

Also, if you use attr_encrypted, generate a key.

Getting Started

Create a migration to add a column for the blind index

add_column :users, :email_bidx, :string
add_index :users, :email_bidx # unique: true if needed

Add to your model

class User (v) { v.downcase }
end

Validations

You can use blind indexes for uniqueness validations.

class User (v) { v.presence }
  validates :email, uniqueness: {allow_blank: true}
end

For case_sensitive: false, use:

class User (v) { v.downcase }
  validates :email, uniqueness: true # for best performance, leave out {case_sensitive: false}
end

Multiple Indexes

You may want multiple blind indexes for an attribute. To do this, add another column:

add_column :users, :email_ci_bidx, :string
add_index :users, :email_ci_bidx

Update your model

class User (v) { v.downcase }
end

Backfill existing records

BlindIndex.backfill(User, columns: [:email_ci_bidx])

And query away

User.where(email_ci: "[email protected]")

Index Only

If you don’t need to store the original value (for instance, when just checking duplicates), use a virtual attribute:

class User  { changes.key?(:first_name) || changes.key?(:last_name) }

  def set_initials
    self.initials = "#{first_name[0]}#{last_name[0]}"
  end
end

Migrating Data

If you’re encrypting a column and adding a blind index at the same time, use the migrating option.

class User 

Be sure to include the inspect at the end or it won’t be encoded properly in YAML.

Mongoid

For Mongoid, use:

class User
  field :email_bidx, type: String
  index({email_bidx: 1})
end

Key Generation

This is optional for Lockbox, as its master key is used by default.

Generate a key with:

BlindIndex.generate_key

Store the key with your other secrets. This is typically Rails credentials or an environment variable (dotenv is great for this). Be sure to use different keys in development and production. Keys don’t need to be hex-encoded, but it’s often easier to store them this way.

Set the following environment variable with your key (you can use this one in development)

BLIND_INDEX_MASTER_KEY=ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

or create config/initializers/blind_index.rb with something like

BlindIndex.master_key = Rails.application.credentials.blind_index_master_key

LIKE, ILIKE, and Full-Text Searching

Unfortunately, blind indexes can’t be used for LIKE, ILIKE, or full-text searching. Instead, records must be loaded, decrypted, and searched in memory.

For LIKE, use:

User.select { |u| u.email.include?("value") }

For ILIKE, use:

User.select { |u| u.email =~ /value/i }

For full-text or fuzzy searching, use a gem like FuzzyMatch:

FuzzyMatch.new(User.all, read: :email).find("value")

If the number of records is large, try to find a way to narrow it down. An expression index is one way to do this, but leaks which records have the same value of the expression, so use it carefully.

Reference

Set default options in an initializer with:

BlindIndex.default_options = {algorithm: :pbkdf2_sha256}

By default, blind indexes are encoded in Base64. Set a different encoding with:

class User (v) { [v].pack("H*") }
end

By default, blind indexes are 32 bytes. Set a smaller size with:

class User < ApplicationRecord
  blind_index :email, size: 16
end

Set a key directly for an index with:

class User < ApplicationRecord
  blind_index :email, key: ENV["USER_EMAIL_BLIND_INDEX_KEY"]
end

Compatibility

You can generate blind indexes from other languages as well. For Python, you can use argon2-cffi.

from argon2.low_level import Type, hash_secret_raw
from base64 import b64encode

key = '289737bab72fa97b1f4b081cef00d7b7d75034bcf3183c363feaf3e6441777bc'
value = '[email protected]'

bidx = b64encode(hash_secret_raw(
    secret=value.encode(),
    salt=bytes.fromhex(key),
    time_cost=3,
    memory_cost=2**12,
    parallelism=1,
    hash_len=32,
    type=Type.ID
))

Alternatives

One alternative to blind indexing is to use a deterministic encryption scheme, like AES-SIV. In this approach, the encrypted data will be the same for matches. We recommend blind indexing over deterministic encryption because:

1. You can keep encryption consistent for all fields (both searchable and non-searchable)
2. Blind indexing supports expressions

History

View the changelog

Contributing

Everyone is encouraged to help improve this project. Here are a few ways you can help:

• Report bugs
• Fix bugs and submit pull requests
• Write, clarify, or fix documentation
• Suggest or add new features

To get started with development and testing:

git clone https://github.com/ankane/blind_index.git
cd blind_index
bundle install
bundle exec rake test

For security issues, send an email to the address on this page.