http://stackoverflow.com/questions/5447650

00_spec.md

Introduction

Imagine one was required to create a web-based password management system (over SSL! :) with the following requirements:

1. Individual users sign in to the system using their own unique pass phrase.
2. This pass phrase should be enough to allow the user to use the system effectively (e.g. from a smartphone, etc.)--the point being that they should not have to keep a key file with them.
3. Users can store arbitrary-length bits of data in the system ("entries").
4. Entries are encrypted in the database in such a way that there is not enough information in the database or application alone to read the encrypted entries.
5. Users should be able to "share" entries with other users of the system so that the other user(s) can read the contents of the entry.

I'm no expert in cryptography. After thinking about it for a while, I came up with the following. My question is: is this implementation secure? Am I missing something? If so, is the above spec even implementable? Or is this overkill?

Database

The database is set up as such:

+------------------------------------------------------------------------------+
|  users                                                                       |
+---------+--------------+--------------+---------------+----------------------+
| salt    | pub_key      | enc_priv_key | priv_key_hmac |                      |
+---------+--------------+--------------+---------------+----------------------+
|  entries                                                                     |
+---------+--------------+--------------+---------------+----------+-----------+
| user_id | parent_entry | enc_sym_key  | sym_key_sig   | enc_data | data_hmac |
+---------+--------------+--------------+---------------+----------+-----------+

Basic Use Cases

Let's imagine two users of the system, Alice and Bob.

Bob signs up for the site:

• Bob enters a password. This password is sent to the server (but not stored).
• The server generates a random salt and stores it in the salt field.
• The server generates the SHA-256 hash of Bob's password and salt.
• The server generates an RSA key pair. The public key is stored as plain text in the pub_key field. The private key is encrypted via AES-256 using the hash generated from Bob's password and salt as the key and stored in the enc_priv_key field.
• The server generates a hash-based message authentication code for Bob's private key using Bob's password and salt as the key and stores this in the priv_key_hmac field.

Bob stores an entry in the system:

• Bob enters some data to be stored as an entry along with his password. This data is sent to the server.
• The server generates a key to be used as a key for AES-256 encryption.
• The server uses this key to encrypt the data and stores the result in the enc_data field.
• The server generates a hash-based message authentication code for the data using the generated key and stores this in the data_hmac field.
• The symmetric key used to encrypt the data is encrypted with Bob's public key and stored in the enc_sym_key field.
• The server uses Bob's private key to generate a signature for the symmetric key.

Bob retrieves his stored entry:

• Bob enters his password and the ID of the entry to retrieve.
• The server generates the SHA-256 hash of Bob's password and salt.
• Bob's encrypted private key is decrypted via AES-256 encryption using the hash.
• The server verifies that Bob's encrypted private key has not been tampered with by checking the HMAC in priv_key_hmac.
• The server decrypts the symmetric key stored in the enc_sym_key field using Bob's private key.
• The server verifies that the encrypted symmetric key has not been tampered with by verifying the signature in sym_key_sign using Bob's public key.
• The server decrypts the data using the symmetric key.
• The server verifies that the encrypted data has not been tampered with by verifying the HMAC stored in the data_hmac field.
• The server returns the decrypted data to Bob.

Bob shares an entry with Alice:

• Bob wants Alice to have access to an entry he owns. He enters his password and the ID of the entry to share.
• The data for the entry is decrypted using the method in "Bob retrieves his stored entry."
• A new entry is created for Alice in the same fashion as in "Bob stores an entry in the system," with the following exceptions:
  1. The entry's parent_entry is set to Bob's entry.
  2. The signature for the symmetric key is calculated using Bob's private key (since Alice's private key is not available to Bob).
  3. When Alice accesses this new entry, the existence of a non-null parent_entry causes the system to use Bob's public key to verify the signature (since his private key was used to create it).

Bob changes the data in his shared entry:

• Bob decides to change the data in the entry he shared with Alice. Bob indicates the entry ID to modify and the new data it should contain.
• The system overwrites the data created in "Bob stores an entry in the system."
• The system finds every entry with a parent_entry equal to the entry that was just modified, and for each one overwrites the data created in "Bob shares an entry with Alice."

Analysis

Advantages:

• It is impossible to decrypt any data from the database without the password of the user that owns the data, as the private key necessary to decrypt the data is encrypted with the user's password, and that password (and it's hash) is not stored in the database.
• If a user wants to change their password, only their encrypted private key needs to be regenerated (decrypt the private key with the old password/hash, then re-encrypt it with the new password/hash).
• Shared entries are stored as actual separate records in the database, so there is no need to share a key between multiple users/groups of users.

Disadvantages/Problems (that I can think of):

• If a shared entry is modified, the system must re-encrypt every child entry; with a large number of users sharing data, this could potentially be computationally expensive.
• Shared entries depend on the parent user's public key for signature verification. If the user is deleted, or their key changes, the signatures are invalid.

Repeated from the introduction: my question is: is this implementation secure? Am I missing something? If so, is the above spec even implementable? Or is this overkill?

Thanks!

01_aescrypt.rb

require 'openssl'
require 'digest/sha2'

module AESCrypt
  DEFAULT_CIPHER = "AES-256-CBC"

  class << self
    def aes(method, data, key, type = AESCrypt::DEFAULT_CIPHER)
      aes = OpenSSL::Cipher.new(type).send(method)
      aes.key = Digest::SHA256.digest key
      aes.update(data) << aes.final
    end

    def encrypt(data, key, type = AESCrypt::DEFAULT_CIPHER)
      AESCrypt.aes(:encrypt, data, key, type)
    end

    def decrypt(data, key, type = AESCrypt::DEFAULT_CIPHER)
      AESCrypt.aes(:decrypt, data, key, type)
    end

    def hmac(data, key)
      OpenSSL::HMAC.digest OpenSSL::Digest.new("SHA256"), key, data
    end
  end
end

02_impl.rb

#!/usr/bin/env ruby

$:.unshift '.'

require 'sshkey'
require 'digest/sha2'
require 'base64'
require 'securerandom'

require 'aescrypt'

module B64
  def self.up(data)
    Base64.encode64(data).strip
  end

  def self.down(data)
    Base64.decode64(data)
  end
end

PLAIN     = "This is important data."
PLAIN2    = "This is even more important data."
PASSWORD  = "supersecret!"
PASSWORD2 = "evenmoresecret!"

class User
  attr_accessor :salt, :pub_key, :enc_priv_key, :priv_key_hmac

  def initialize(pass)
    # Generate the user's random salt
    @salt          = rand 1000000
    # Generate the RSA keypair and store the public key as plain text
    keypair        = OpenSSL::PKey::RSA.generate(2048)
    @pub_key       = keypair.public_key.to_pem.strip
    # AES-256-CBC encrypt the user's private key
    # using the user's salt and password.
    priv_key       = keypair.to_pem.strip
    pass_salt_hash = hash pass
    @enc_priv_key  = B64.up(AESCrypt.encrypt priv_key, pass_salt_hash)
    # Generate an HMAC for the encrypted private key.
    @priv_key_hmac = B64.up(AESCrypt.hmac    priv_key, pass_salt_hash)
  end

  # Share an entry with another user. Here, returns a new entry, but in a DB
  # driven app, this would create a new record for the given user to access.
  def share(entry, password, newuser)
    data = Entry.retrieve(self, password, entry)
    Entry.new(newuser, nil, data, private_key(password))
  end

  # Returns the user's private key. Checks the HMAC to see if the encrypted
  # private key has been tampered with, and raises an exception if it has.
  def private_key(password)
    key = AESCrypt.decrypt B64.down(@enc_priv_key), hash(password)
    raise "Private key tampering" unless private_key_valid?(password, key)
    OpenSSL::PKey::RSA.new key
  end

  # True if the encrypted private key has not been tampered with (e.g.
  # the HMAC is valid); false otherwise.
  def private_key_valid?(password, key)
    check = (key.is_a? OpenSSL::PKey::RSA) ? key.to_pem.strip : key
    @priv_key_hmac == B64.up(AESCrypt.hmac check, hash(password))
  end

  # Shortcut for User#salt_pass_hash if the user is known.
  def hash(password)
    User.salt_pass_hash(@salt, password)
  end

  # Generates a cryptographic hash based on the user's salt and password.
  def self.salt_pass_hash(salt, pass)
    Digest::SHA256.digest "#{salt}-#{pass}"
  end
end

class Entry
  attr_accessor :user, :enc_data, :data_hmac, :enc_sym_key, :sym_key_sig

  # Creates a new entry with the gien data owned by the given user. password
  # is necessary if priv_for_sig is nil; otherwise, a private key can be
  # passed as priv_for_sign to specify which private key to use to generate
  # the signature.
  def initialize(user, password, data, priv_for_sig = nil)
    @user          = user
    # Generate a symmetric key for AES-256-CDC use.
    symkey         = Digest::SHA256.digest SecureRandom.random_bytes(256)
    # Encrypt the data and generate an HMAC.
    @enc_data      = B64.up AESCrypt.encrypt data, symkey
    @data_hmac     = B64.up AESCrypt.hmac    data, symkey
    # Encrypt the symmetric key using the user's public key.
    pub            = OpenSSL::PKey::RSA.new(user.pub_key)
    @enc_sym_key   = B64.up pub.public_encrypt symkey
    # Generate a signature for the symmetric key.
    priv           = priv_for_sig || user.private_key(password)
    @sym_key_sig   = B64.up(priv.sign OpenSSL::Digest.new("SHA256"), symkey)
  end

  # Returns the symmetric key for this entry.
  def symmetric_key(pub_key, priv_key)
    key = priv_key.private_decrypt B64.down(@enc_sym_key)
    raise "Symmetric key tampering" unless sig_valid?(pub_key, key)
    key
  end

  # Returns the data for this entry.
  def data(sym_key)
    data = AESCrypt.decrypt(B64.down(@enc_data), sym_key)
    raise "Data tampering" unless data_valid?(sym_key, data)
    data
  end

  # Verifies that the encrypted signature hasn't been tampered with.
  def sig_valid?(pub_key, data)
    # TODO: How to verify the signature given only a public key?
    #####B64.down(@sym_key_sig) == priv_key.sign(OpenSSL::Digest.new("SHA256"), data)
    ####true
    pub_key.verify OpenSSL::Digest.new("SHA256"), B64.down(@sym_key_sig), data
  end

  def data_valid?(key, data)
    @data_hmac == B64.up(AESCrypt.hmac data, key)
  end

  def self.retrieve(user, password, entry, pub_for_sig = nil)
    # Retrieve the user's private key.
    priv   = user.private_key password
    pub    = pub_for_sig || user.pub_key
    pub    = OpenSSL::PKey::RSA.new(pub) if pub.is_a? String
    # Decrypt the symmetric key used to encrypt the data.
    symkey = entry.symmetric_key pub, priv
    data   = entry.data symkey
  end
end


bob    = User.new(PASSWORD)
alice  = User.new(PASSWORD2)
entry  = Entry.new(bob, PASSWORD, PLAIN)
entry2 = Entry.new(alice, PASSWORD2, PLAIN2)
puts "Bob getting Bob's entry:     #{Entry.retrieve(bob, PASSWORD, entry)}"
puts "Alice getting Alice's entry: #{Entry.retrieve(alice, PASSWORD2, entry2)}"
begin
  puts "Alice getting Bob's entry:   #{Entry.retrieve(alice, PASSWORD2, entry)}"
rescue
  puts "Alice cannot access Bob's entry."
end
puts "Sharing Bob's entry with Alice..."
entry3 = bob.share(entry, PASSWORD, alice)
puts "Alice getting Bob's entry:   #{Entry.retrieve(alice, PASSWORD2, entry3, bob.pub_key)}"

03_output.txt

[BinaryMuse ~/src/sandbox/encrypt]: ./impl.rb 
Bob getting Bob's entry:     This is important data.
Alice getting Alice's entry: This is even more important data.
Alice cannot access Bob's entry.
Sharing Bob's entry with Alice...
Alice getting Bob's entry:   This is important data.