Monday May 23, 2016

BDB User Authentication

BDB User Authentication

(courtesy of  Brayden Zhang)


In Berkeley DB 6.2, user authentication extension is added into the SQL interface. The new user authentication layer is both secure and easy to use. In this article, we will introduce how to use the user authentication, and also explain some details.

The SQLite user authentication

User authentication was first included in SQLite 3.8.7, and was described well in the following page:  There are four user authentication APIs:

sqlite3_user_authenticate(conn, username, pwd, nPwd); sqlite3_user_add(conn, username, pwd, nPwd, isAdmin);

sqlite3_user_change(conn, username, pwd, nPwd, isAdmin);

sqlite3_user_delete(conn, username);

 A database becomes a user authentication required database once the first user is added with a sqlite3_user_add() call. To visit an authentication-required SQLite database, an authenticated user must be logged into the database connection first; otherwise attempts to read or write from the database will fail with errors.

From the implementation view, SQLite stores user/password-hash in an internal sqlite_user table and verifies user login with that table.

This SQLite userauth will be activated in Berkeley DB SQL layer with -


Security considerations about the SQLite userauth

Let’s rethink about user authentication. When we are talking about user login, we mean we are putting the sensitive data into a safe zone. If a user need to access the data, we will ask the user for his name/password. Once we are sure the user is authenticated, we will let him into the safe zone. Thinking about a client/server Database, it provides the safe zone as the data is physically stored in a backend host.

Next let’s go back into the SQLite userauth, where is the safe zone? I guess the answer is: “it does not exist (yet).” It will be SQLite application’s resposibilly to provide it. In some cases it should be not so easy, such as an Android application. Anyone who has the access to this Android device could read the database file in binary editor; also if you built a SQLite without the userauth compile option, you could access an authentication-required database freely(no need for a login) 

Encryption should be a common(and neccesary) way to provide a safe zone for SQLite user authentication. In SQLite, to visit an encrypted authentication-required database, we need a call sequence as:


/* Database is now usable */ 

The next question is: who will provide the key?

  • The application could keep the key in somewhere and call sqlite3_key_v2() with the key. This means the application needs to implement some mechanism to protect the key;
  • Or the key will be remembered by every user, and he needs to provide it as well as his username/password. This sounds less attractive. 


Keystore-based userauth in Berkeley DB

It will be much better if an authentication-required database is encrypted, but a user could access the database with only his user name/password. We provide such an enhancement with a keystore file. Encryption is mandatory for a keystore based authentication-required database and we take the responsibly to protect the database encryption key. This is totally transparent to the end user. A user just does the login with a call sequence as:


/* Database is now usable */ 

In our enhanced sqlite3_user_authenticate() , we actually do things as below: 

1. fetch the database encryption key from keystore file using user name and password;
2. apply the encryption key to the database(that is, calling sqlite3_key_v2() );
3. verify user/password via sqlite_user table, as the orignal userauth does. 

This enhanced keystore based userauth will be activated with - DBDBSQL_USER_AUTHENTICATION_KEYSTORE compile option.

How the keystore file works

We store keystore entries in the keystore file. Every entry is the database encryption key which is encrypted with a salted hash value of user’s password. Say we have items below:
DEK - database encryptio key
EDEK - encrypted database encryption key
PWD - user's password
SALT - a randomly generated byte string
USERNAME - user's name
encrypt - Berkeley DB's encryption function;
decrypt - Berkeley DB's decryption function;
hash - Berkeley DB's SHA1 Secure Hash Algorithm function

When a user was added, we get the database encryption key from memory cache, and we compute 

EDEK = encrypt(DEK, hash(SALT, PWD))

 then we save a keystore entry as: (USERNAME, SALT, EDEK) . During a user login, to get the database encryption key back, first we find the keystore entry with user’s name, then we compute the database encryption key with:

DEK = decrypt(EDEK, hash(SALT, PWD)); 

Thus, by using hash/encryption, We ensure that:

  • The database encryption key in the keystore file is encrypted and could never be leaked from the keystore file;
  • Only user’s password hash is stored, so user’s password could never be leaked from the keystore file.


Make the Berkeley DB keystore userauth robust

If keystore file get corrupted, some of the end users will not be able to access the database. We try to make our keystore authentication as robust as possible.

Checksum and backup/restore

We enable checksum for the keystore file and have the checksum verified every time when keystore file was used. We also implement a simple backup/restore mechanism of the keystore file.

Locking file for the keystore

We expect the database be visited by multiple processes. To avoid keystore file from messed by multiple process writes, we introduce a lock file. Only when a process could have the .lck file
created(exclusively), it could access the keystore file; when it finished, it will remove the .lck file.

In rare cases, if user application fails when accessing the keystore file,  the locking file may not be cleaned. In this case, user needs to clean the .lck file under the database environment.

Treat updates of sqlite_user table and keystore file as an atomic operation

When adding/deleting/updating a user, we will first update the sqlite_user database table then the keystore file. We need to ensure that: Updates to sqlite_user table and keystore file will both succeed or both fail. This is guaranteed by database transactions. We put the updates of sqlite_user table and keystore file in a transaction and only commit when we succeed to update the keystore file; if we
failed to update the keystore file, we will rollback the database updates. Please note as we use transactions internally in userauth API, you should not call the userauth API within an outside transaction. If you do that, userauth API will return an error message.

Sunday Jan 30, 2011

Is Berkeley DB a NoSQL solution?

Berkeley DB is a library. To use it to store data you must link the library into your application. You can use most programming languages to access the API, the calls across these APIs generally mimic the Berkeley DB C-API which makes perfect sense because Berkeley DB is written in C. The inspiration for Berkeley DB was the DBM library, a part of the earliest versions of UNIX written by AT&T's Ken Thompson in 1979. DBM was a simple key/value hashtable-based storage library. In the early 1990s as BSD UNIX was transitioning from version 4.3 to 4.4 and retrofitting commercial code owned by AT&T with unencumbered code, it was the future founders of Sleepycat Software who wrote libdb (aka Berkeley DB) as the replacement for DBM. The problem it addressed was fast, reliable local key/value storage.

At that time databases almost always lived on a single node, even the most sophisticated databases only had simple fail-over two node solutions. If you had a lot of data to store you would choose between the few commercial RDBMS solutions or to write your own custom solution. Berkeley DB took the headache out of the custom approach. These basic market forces inspired other DBM implementations. There was the "New DBM" (ndbm) and the "GNU DBM" (GDBM) and a few others, but the theme was the same. Even today TokyoCabinet calls itself "a modern implementation of DBM" mimicking, and improving on, something first created over thirty years ago. In the mid-1990s, DBM was the name for what you needed if you were looking for fast, reliable local storage.

Fast forward to today. What's changed? Systems are connected over fast, very reliable networks. Disks are cheap, fast, and capable of storing huge amounts of data. CPUs continued to follow Moore's Law, processing power that filled a room in 1990 now fits in your pocket. PCs, servers, and other computers proliferated both in business and the personal markets. In addition to the new hardware entire markets, social systems, and new modes of interpersonal communication moved onto the web and started evolving rapidly. These changes cause a massive explosion of data and a need to analyze and understand that data. Taken together this resulted in an entirely different landscape for database storage, new solutions were needed.

A number of novel solutions stepped up and eventually a category called NoSQL emerged. The new market forces inspired the CAP theorem and the heated debate of BASE vs. ACID. But in essence this was simply the market looking at what to trade off to meet these new demands. These new database systems shared many qualities. They were designed to address massive amounts of data, millions of requests per second, and scale out across multiple systems.

The first large-scale and successful solution was Dynamo, Amazon's distributed key/value database. Dynamo essentially took the next logical step and added a twist. Dynamo was to be the database of record, it would be distributed, data would be partitioned across many nodes, and it would tolerate failure by avoiding single points of failure. Amazon did this because they recognized that the majority of the dynamic content they provided to customers visiting their web store front didn't require the services of an RDBMS. The queries were simple, key/value look-ups or simple range queries with only a few queries that required more complex joins. They set about to use relational technology only in places where it was the best solution for the task, places like accounting and order fulfillment, but not in the myriad of other situations.

The success of Dynamo, and it's design, inspired the next generation of Non-SQL, distributed database solutions including Cassandra, Riak and Voldemort. The problem their designers set out to solve was, "reliability at massive scale" so the first focal point was distributed database algorithms. Underneath Dynamo there is a local transactional database; either Berkeley DB, Berkeley DB Java Edition, MySQL or an in-memory key/value data structure. Dynamo was an evolution of local key/value storage onto networks. Cassandra, Riak, and Voldemort all faced similar design decisions and one, Voldemort, choose Berkeley DB Java Edition for it's node-local storage. Riak at first was entirely in-memory, but has recently added write-once, append-only log-based on-disk storage similar type of storage as Berkeley DB except that it is based on a hash table which must reside entirely in-memory rather than a btree which can live in-memory or on disk.

Berkeley DB evolved too, we added high availability (HA) and a replication manager that makes it easy to setup replica groups. Berkeley DB's replication doesn't partition the data, every node keeps an entire copy of the database. For consistency, there is a single node where writes are committed first - a master - then those changes are delivered to the replica nodes as log records. Applications can choose to wait until all nodes are consistent, or fire and forget allowing Berkeley DB to eventually become consistent. Berkeley DB's HA scales-out quite well for read-intensive applications and also effectively eliminates the central point of failure by allowing replica nodes to be elected (using a PAXOS algorithm) to mastership if the master should fail. This implementation covers a wide variety of use cases. MemcacheDB is a server that implements the Memcache network protocol but uses Berkeley DB for storage and HA to replicate the cache state across all the nodes in the cache group. Google Accounts, the user authentication layer for all Google properties, was until recently running Berkeley DB HA. That scaled to a globally distributed system. That said, most NoSQL solutions try to partition (shard) data across nodes in the replication group and some allow writes as well as reads at any node, Berkeley DB HA does not.

So, is Berkeley DB a "NoSQL" solution? Not really, but it certainly is a component of many of the existing NoSQL solutions out there. Forgetting all the noise about how NoSQL solutions are complex distributed databases when you boil them down to a single node you still have to store the data to some form of stable local storage. DBMs solved that problem a long time ago. NoSQL has more to do with the layers on top of the DBM; the distributed, sometimes-consistent, partitioned, scale-out storage that manage key/value or document sets and generally have some form of simple HTTP/REST-style network API. Does Berkeley DB do that? Not really.

Is Berkeley DB a "NoSQL" solution today? Nope, but it's the most robust solution on which to build such a system. Re-inventing the node-local data storage isn't easy. A lot of people are starting to come to appreciate the sophisticated features found in Berkeley DB, even mimic them in some cases. Could Berkeley DB grow into a NoSQL solution? Absolutely. Our key/value API could be extended over the net using any of a number of existing network protocols such as memcache or HTTP/REST. We could adapt our node-local data partitioning out over replicated nodes. We even have a nice query language and cost-based query optimizer in our BDB XML product that we could reuse were we to build out a document-based NoSQL-style product. XML and JSON are not so different that we couldn't adapt one to work with the other interchangeably. Without too much effort we could add what's missing, we could jump into this No SQL market withing a single product development cycle.

Why isn't Berkeley DB already a NoSQL solution? Why aren't we working on it? Why indeed...


Information about Berkeley DB products directly from the people who build them.


« July 2016