source: trunk/third/rpm/db/crypto/crypto.html @ 19079

Revision 19079, 38.5 KB checked in by ghudson, 22 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r19078, which included commits to RCS files with non-trunk default branches.
Line 
1<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
2<html>
3<head>
4   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
5   <meta name="GENERATOR" content="Mozilla/4.76 [en] (X11; U; FreeBSD 4.3-RELEASE i386) [Netscape]">
6</head>
7<body>
8
9<center>
10<h1>
11&nbsp;Security Interface for Berkeley DB</h1></center>
12
13<center><i>Susan LoVerso</i>
14<br><i>sue@sleepycat.com</i>
15<br><i>Rev 1.6</i>
16<br><i>2002 Feb 26</i></center>
17
18<p>We provide an interface allowing secure access to Berkeley DB.&nbsp;&nbsp;
19Our goal is to allow users to have encrypted secure databases.&nbsp; In
20this document, the term <i>ciphering</i> means the act of encryption or
21decryption.&nbsp; They are equal but opposite actions and the same issues
22apply to both just in the opposite direction.
23<h3>
24Requirements</h3>
25The overriding requirement is to provide a simple mechanism to allow users
26to have a secure database.&nbsp; A secure database means that all of the
27pages of a database will be encrypted, and all of the log files will be
28encrypted.
29<p>Falling out from this work will be a simple mechanism to allow users
30to request that we checksum their data for additional error detection (without
31encryption/decryption).
32<p>We expect that data in process memory or stored in shared memory, potentially
33backed by disk, is not encrypted or secure.
34<h2>
35<a NAME="DB Modifications"></a>DB Method Interface Modifications</h2>
36With a logging environment, all database changes are recorded in the log
37files.&nbsp; Therefore, users requiring secure databases in such environments
38also require secure log files.
39<p>A prior thought had been to allow different passwords on the environment
40and the databases within.&nbsp; However, such a scheme, then requires that
41the password be logged in order for recovery to be able to restore the
42database.&nbsp; Therefore, any application having the password for the
43log could get the password for any databases by reading the log.&nbsp;
44So having a different password on a database does not gain any additional
45security and it makes certain things harder and more complex.&nbsp; Some
46of those more complex things include the need to handle database and env
47passwords differently since they'd need to be stored and accessed from
48different places.&nbsp; Also resolving the issue of how <i>db_checkpoint</i>
49or <i>db_sync</i>, which flush database pages to disk, would find the passwords
50of various databases without any dbps was unsolved.&nbsp; The feature didn't
51gain anything and caused significant pain.&nbsp; Therefore the decision
52is that there will be a single password protecting an environment and all
53the logs and some databases within that environment.&nbsp; We do allow
54users to have a secure environment and clear databases.&nbsp; Users that
55want secure databases within a secure environment must set a flag.
56<p>Users wishing to enable encryption on a database in a secure environment
57or enable just checksumming on their database pages will use new flags
58to <a href="../docs/api_c/db_set_flags.html">DB->set_flags()</a>.&nbsp;
59Providing ciphering over an entire environment is accomplished by adding
60a single environment method: <a href="../docs/api_c/env_set_encrypt.html">DBENV->set_encrypt()</a>.&nbsp;
61Providing encryption for a database (not part of an environment) is accomplished
62by adding a new database method: <a href="../docs/api_c/db_set_encrypt.html">DB->set_encrypt()</a>.
63<p>Both of the <i>set_encrypt</i> methods must be called before their respective
64<i>open</i> calls.&nbsp; The environment method must be before the environment
65open because we must know about security before there is any possibility
66of writing any log records out.&nbsp; The database method must be before
67the database open in order to read the root page.&nbsp; The planned interfaces
68for these methods are:
69<pre>DBENV->set_encrypt(DBENV *dbenv,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* DB_ENV structure */
70&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char *passwd&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Password */
71&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int32_t flags);&nbsp;&nbsp;&nbsp;&nbsp; /* Flags */</pre>
72
73<pre>DB->set_encrypt(DB *dbp,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* DB structure */
74&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char *passwd&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Password */
75&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int32_t flags);&nbsp;&nbsp;&nbsp;&nbsp; /* Flags */</pre>
76The flags accepted by these functions are:
77<pre>#define DB_ENCRYPT_AES&nbsp; 0x00000001&nbsp; /* Use the AES encryption algorithm */</pre>
78Passwords are NULL-terminated strings.&nbsp; NULL or zero length strings
79are illegal.&nbsp; These flags enable the checksumming and encryption using
80the particular algorithms we have chosen for this implementation.&nbsp;
81The flags are named such that there is a logical naming pattern if additional
82checksum or encryption algorithms are used. If a user gives a flag of zero,
83it will behave in a manner similar to DB_UNKNOWN. It will be illegal if
84they are creating the environment or database, as an algorithm must be
85specified. If they are joining an existing environment or opening an existing
86database, they will use whatever algorithm is in force at the time.&nbsp;
87Using DB_ENCRYPT_AES automatically implies SHA1 checksumming.
88<p>These functions will perform several initialization steps.&nbsp; We
89will allocate crypto_handle for our env handle and set up our function
90pointers.&nbsp; We will allocate space and copy the password into our env
91handle password area.&nbsp; Similar to <i>DB->set_cachesize</i>, calling
92<i>DB->set_encrypt</i>
93will actually reflect back into the local environment created by DB.
94<p>Lastly, we will add a new flag, DB_OVERWRITE, to the <a href="../docs/api_c/env_remove.html">DBENV->remove</a>
95method.&nbsp; The purpose of this flag is to force all of the memory used
96by the shared regions to be overwritten before removal.&nbsp; We will use
97<i>rm_overwrite</i>,
98a function that overwrites and syncs a file 3 times with varying bit patterns
99to really remove a file.&nbsp; Additionally, this flag will force a sync
100of the overwritten regions to disk, if the regions are backed by the file
101system.&nbsp; That way there is no residual information left in the clear
102in memory or freed disk blocks.&nbsp; Although we expect that this flag
103will be used by customers using security, primarily, its action is not
104dependent on passwords or a secure setup, and so can be used by anyone.
105<h4>
106Initialization of the Environment</h4>
107The setup of the security subsystem will be similar to replication initialization
108since it is a sort of subsystem, but it does not have its own region.&nbsp;
109When the environment handle is created via <i>db_env_create</i>, we initialize
110our <i>set_encrypt</i> method to be the RPC or local version.&nbsp; Therefore
111the <i>__dbenv</i> structure needs a new pointer:
112<pre>&nbsp;&nbsp;&nbsp; void&nbsp;&nbsp;&nbsp; *crypto_handle;&nbsp;&nbsp; /* Security handle */</pre>
113The crypto handle will really point to a new <i>__db_cipher</i> structure
114that will contain a set of functions and a pointer to the in-memory information
115needed by the specific encryption algorithm.&nbsp; It will look like:
116<pre>typedef struct __db_cipher {
117&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (*init)__P((...));&nbsp;&nbsp;&nbsp; /* Alg-specific initialization function */
118&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (*encrypt)__P((...)); /* Alg-specific encryption algorithm */
119&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (*decrypt)__P((...)); /* Alg-specific decryption function */
120&nbsp;&nbsp;&nbsp; void&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *data;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Pointer to alg-specific information (AES_CIPHER) */
121&nbsp;&nbsp;&nbsp; u_int32_t flags;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Cipher flags */
122} DB_CIPHER;</pre>
123
124<pre>#define DB_MAC_KEY&nbsp;&nbsp;&nbsp; 20&nbsp;&nbsp;&nbsp; /* Size of the MAC key */
125typedef struct __aes_cipher {
126&nbsp;&nbsp;&nbsp; keyInstance&nbsp;&nbsp;&nbsp; encrypt_ki;&nbsp;&nbsp; /* Encrypt keyInstance temp. */
127&nbsp;&nbsp;&nbsp; keyInstance&nbsp;&nbsp;&nbsp; decrypt_ki;&nbsp;&nbsp; /* Decrypt keyInstance temp. */
128&nbsp;&nbsp;&nbsp; u_int8_t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mac_key[DB_MAC_KEY]; /* MAC key */
129&nbsp;&nbsp;&nbsp; u_int32_t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; flags;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* AES-specific flags */
130} AES_CIPHER;</pre>
131It should be noted that none of these structures have their own mutex.&nbsp;
132We hold the environment region locked while we are creating this, but once
133this is set up, it is read-only forever.
134<p>During <a href="../docs/api_c/env_set_encrypt.html">dbenv->set_encrypt</a>,
135we set the encryption, decryption and checksumming methods to the appropriate
136functions based on the flags.&nbsp; This function will allocate us a crypto
137handle that we store in the <i>__dbenv</i> structure just like all the
138other subsystems.&nbsp; For now, only AES ciphering functions and SHA1
139checksumming functions are supported.&nbsp; Also we will copy the password
140into the <i>__dbenv</i> structure.&nbsp; We ultimately need to keep the
141password in the environment's shared memory region or compare this one
142against the one that is there, if we are joining an existing environment,
143but we do not have it yet because open has not yet been called.&nbsp; We
144will allocate a structure that will be used in initialization and set up
145the function pointers to point to the algorithm-specific functions.
146<p>In the&nbsp; <i>__dbenv_open</i> path, in <i>__db_e_attach</i>, if we
147are creating the region and the <i>dbenv->passwd</i> field is set, we need
148to use the length of the password in the initial computation of the environment's
149size.&nbsp; This guarantees sufficient space for storing the password in
150shared memory.&nbsp; Then we will call a new function to initialize the
151security region, <i>__crypto_region_init</i> in <i>__dbenv_open</i>.&nbsp;
152If we are the creator, we will allocate space in the shared region to store
153the password and copy the password into that space.&nbsp; Or, if we are
154not the creator we will compare the password stored in the dbenv with the
155one in shared memory.&nbsp;&nbsp; Additionally, we will compare the ciphering
156algorithm to the one stored in the shared region.We'll smash the dbenv
157password and free it.&nbsp; If they do not match, we return an error.&nbsp;
158If we are the creator we store the offset into the REGENV structure.&nbsp;
159Then <i>__crypto_region_init&nbsp;</i> will call the initialization function
160set up earlier based on the ciphering algorithm specified.&nbsp; For now
161we will call <i>__aes_init</i>.&nbsp; Additionally this function will allocate
162and set up the per-process state vector for this encryption's IVs.&nbsp;
163See <a href="#Generating the Initialization Vector">Generating the Initialization
164Vector</a> for a detailed description of the IV and state vector.
165<p>In the AES-specific initialization function, <i>__aes_init</i>,&nbsp;
166we will initialize it by calling
167<i>__aes_derivekeys</i> in order to fill
168in the keyInstance and mac_key fields in that structure.&nbsp; The REGENV
169structure will have one additional item
170<pre>&nbsp;&nbsp; roff_t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; passwd_off;&nbsp;&nbsp; /* Offset of passwd */</pre>
171
172<h4>
173Initializing a Database</h4>
174During <a href="../docs/api_c/db_set_encrypt.html">db->set_encrypt</a>,
175we set the encryption, decryption and checksumming methods to the appropriate
176functions based on the flags.&nbsp; Basically, we test that we are not
177in an existing environment and we haven't called open.&nbsp; Then we just
178call through the environment handle to set the password.
179<p>Also, we will need to add a flag in the database meta-data page that
180indicates that the database is encrypted and what its algorithm is.&nbsp;
181This will be used when the meta-page is read after reopening a file. We
182need this information on the meta-page in order to detect a user opening
183a secure database without a password.&nbsp; I propose using the first unused1
184byte (renaming it too) in the meta page for this purpose.
185<p>All pages will not be encrypted for the first 64 bytes of data.&nbsp;
186Database meta-pages will be encrypted on the first 512 bytes only.&nbsp;
187All meta-page types will have an IV and checksum added within the first
188512 bytes as well as a crypto magic number.&nbsp; This will expand the
189size of the meta-page from 256 bytes to 512 bytes. The page in/out routines,
190<i>__db_pgin</i> and <i>__db_pgout</i> know the page type of the page and
191will apply the 512 bytes ciphering to meta pages.&nbsp; In <i>__db_pgout</i>,
192if we have a crypto handle in our (private) environment, we will apply
193ciphering to either the entire page, or the first 512 bytes if it is a
194meta-page.&nbsp; In <i>__db_pgin</i>, we will decrypt if the page we have
195a crypto handle.
196<p>When multiple processes share a database, all must use the same password
197as the database creator. Using an existing database requires several conditions
198to be true.&nbsp; First, if the creator of the database did not create
199with security, then opening later with security is an error.&nbsp; Second,
200if the creator did create it with security, then opening later without
201security is an error.&nbsp; Third, we need to be able to test and check
202that when another process opens a secure database that the password they
203provided is the same as the one in use by the creator.
204<p>When reading the meta-page, in <i>__db_file_setup</i>, we do not go
205through the paging functions, but directly read via <i>__os_read</i>.&nbsp;
206It is at this point that we will determine if the user is configured correctly.&nbsp;
207If the meta-page we read has an IV and checksum, they better have a crypto
208handle.&nbsp; If they have a crypto handle, then the meta-page must have
209an IV and checksum.&nbsp; If both of those are true, we test the password.&nbsp;
210We compare the unencrypted magic number to the newly-decrypted crypto magic
211number and if they are not the same, then we report that the user gave
212us a bad password.
213<p>On a mostly unrelated topic, even when we go to very large pagesizes,
214the meta information will still be within a disk sector.&nbsp; So, after
215talking it over with Keith and Margo, we determined that unencrypted meta-pages
216still will not need a checksum.
217<h3>
218Encryption and Checksum Routines</h3>
219These routines are provided to us by Adam Stubblefield at Rice University
220(astubble@rice.edu).&nbsp; The functional interfaces are:
221<pre>__aes_derivekeys(DB_ENV *dbenv,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* dbenv */
222&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *passwd,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Password */
223&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size_t passwd_len,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Length of passwd */
224&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *mac_key,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 20 byte array to store MAC key */
225&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; keyInstance *encrypt_key,&nbsp;&nbsp; /* Encryption key of passwd */
226&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; keyInstance *decrypt_key);&nbsp; /* Decryption key of passwd */</pre>
227This is the only function requiring the textual user password.&nbsp; From
228the password, this function generates a key used in the checksum function,
229<i>__db_chksum</i>.&nbsp;
230It also fills in <i>keyInstance</i> structures which are then used in the
231encryption and decryption routines.&nbsp; The keyInstance structures must
232already be allocated.&nbsp; These will be stored in the AES_CIPHER structure.
233<pre>&nbsp;__db_chksum(u_int8_t *data,&nbsp;&nbsp;&nbsp; /* Data to checksum */
234&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size_t data_len,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Length of data */
235&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *mac_key,&nbsp;&nbsp;&nbsp; /* 20 byte array from __db_derive_keys */
236&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *checksum);&nbsp; /* 20 byte array to store checksum */</pre>
237This function generates a checksum on the data given.&nbsp; This function
238will do double-duty for users that simply want error detection on their
239pages.&nbsp; When users are using encryption, the <i>mac_key </i>will contain
240the 20-byte key set up in <i>__aes_derivekeys</i>.&nbsp; If they just want
241checksumming, then <i>mac_key</i> will be NULL.&nbsp; According to Adam,
242we can safely use the first N-bytes of the checksum.&nbsp; So for seeding
243the generator for initialization vectors, we'll hash the time and then
244send in the first 4 bytes for the seed.&nbsp; I believe we can probably
245do the same thing for checksumming log records.&nbsp; We can only use 4
246bytes for the checksum in the non-secure case.&nbsp; So when we want to
247verify the log checksum we can compute the mac but just compare the first
2484 bytes to the one we read.&nbsp; All locations where we generate or check
249log record checksums that currently call <i>__ham_func4</i> will now call
250<i>__db_chksum</i>.&nbsp;
251I believe there are 5 such locations,
252<i>__log_put, __log_putr, __log_newfile,
253__log_rep_put
254</i>and<i> __txn_force_abort.</i>
255<pre>__aes_encrypt(DB_ENV *dbenv,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* dbenv */
256&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; keyInstance *key,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Password key instance from __db_derive_keys */
257&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *iv,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Initialization vector */
258&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *data,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Data to encrypt */
259&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size_t data_len);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Length of data to encrypt - 16 byte multiple */</pre>
260This is the function to encrypt data.&nbsp; It will be called to encrypt
261pages and log records.&nbsp; The <i>key</i> instance is initialized in
262<i>__aes_derivekeys</i>.&nbsp;
263The initialization vector, <i>iv</i>, is the 16 byte random value set up
264by the Mersenne Twister pseudo-random generator.&nbsp; Lastly, we pass
265in a pointer to the <i>data</i> to encrypt and its length in <i>data_len</i>.&nbsp;
266The <i>data_len</i> must be a multiple of 16 bytes. The encryption is done
267in-place so that when the encryption code returns our encrypted data is
268in the same location as the original data.
269<pre>__aes_decrypt(DB_ENV *dbenv,&nbsp;&nbsp;&nbsp; /* dbenv */
270&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; keyInstance *key,&nbsp; /* Password key instance from __db_derive_keys */
271&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *iv,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Initialization vector */
272&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; u_int8_t *data,&nbsp;&nbsp;&nbsp; /* Data to decrypt */
273&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size_t data_len);&nbsp; /* Length of data to decrypt - 16 byte multiple */</pre>
274This is the function to decrypt the data.&nbsp; It is exactly the same
275as the encryption function except for the action it performs.&nbsp; All
276of the args and issues are the same.&nbsp; It also decrypts in place.
277<h3>
278<a NAME="Generating the Initialization Vector"></a>Generating the Initialization
279Vector</h3>
280Internally, we need to provide a unique initialization vector (IV) of 16
281bytes every time we encrypt any data with the same password.&nbsp; For
282the IV we are planning on using mt19937, the Mersenne Twister, a random
283number generator that has a period of 2**19937-1. This package can be found
284at <a href="http://www.math.keio.ac.jp/~matumoto/emt.html">http://www.math.keio.ac.jp/~matumoto/emt.html</a>.&nbsp;
285Tests show that although it repeats a single integer every once in a while,
286that after several million iterations, it doesn't repeat any 4 integers
287that we'd be stuffing into our 16-byte IV.&nbsp; We plan on seeding this
288generator with the time (tv_sec) hashed through SHA1 when we create the
289environment.&nbsp; This package uses a global state vector that contains
290624 unsigned long integers.&nbsp; We do not allow a 16-byte IV of zero.&nbsp;
291It is simpler just to reject any 4-byte value of 0 and if we get one, just
292call the generator again and get a different number.&nbsp; We need to detect
293holes in files and if we read an IV of zero that is a simple indication
294that we need to check for an entire page of zero.&nbsp; The IVs are stored
295on the page after encryption and are not encrypted themselves so it is
296not possible for an entire encrypted page to be read as all zeroes, unless
297it was a hole in a file.&nbsp; See <a href="#Holes in Files">Holes in Files</a>
298for more details.
299<p>We will not be holding any locks when we need to generate our IV but
300we need to protect access to the state vector and the index.&nbsp; Calls
301to the MT code will come while encrypting some data in <i>__aes_encrypt.</i>&nbsp;&nbsp;
302The MT code will assume that all necessary locks are held in the caller.&nbsp;
303We will have per-process state vectors that are set up when a process begins.&nbsp;
304That way we minimize the contention and only multi-threaded processes need
305acquire locks for the IV.&nbsp; We will have the state vector in the environment
306handle in heap memory, as well as the index and there will be a mutex protecting
307it for threaded access.&nbsp; This will be added to the <i>__dbenv</i>
308structure:
309<pre>&nbsp;&nbsp;&nbsp; DB_MUTEX&nbsp;&nbsp;&nbsp; *mt_mutexp;&nbsp;&nbsp; /* Mersenne Twister mutex */
310&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *mti;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* MT index */
311&nbsp;&nbsp;&nbsp; u_long&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *mt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* MT state vector */</pre>
312This portion of the environment will be initialized at the end of _<i>_dbenv_open</i>,
313right after we initialize the other mutex for the <i>dblist</i>. When we
314allocate the space, we will generate our initial state vector. If we are
315multi-threaded we'll allocate and initialize our mutex also.
316<p>We need to make changes to the MT code to make it work in our namespace
317and&nbsp; to take&nbsp; a pointer to the location of the state vector and
318the index.&nbsp;&nbsp; There will be a wrapper function <i>__db_generate_iv</i>
319that DB will call and it will call the appropriate MT function.&nbsp; I
320am also going to change the default seed to use a hashed time instead of
321a hard coded value.&nbsp; I have looked at other implementations of the
322MT code available on the web site.&nbsp; The C++ version does a hash on
323the current time.&nbsp; I will modify our MT code to seed with the hashed
324time as well.&nbsp; That way the code to seed is contained within the MT
325code and we can just write the wrapper to get an IV.&nbsp; We will not
326be changing the core computational code of MT.
327<h2>
328DB Internal Issues</h2>
329
330<h4>
331When do we Cipher?</h4>
332All of the page ciphering is done in the <i>__db_pgin/__db_pgout</i> functions.&nbsp;
333We will encrypt after the method-specific function on page-out and decrypt
334before the method-specfic function on page-in.&nbsp; We do not hold any
335locks when entering these functions.&nbsp; We determine that we need to
336cipher based on the existence of the encryption flag in the dbp.
337<p>For ciphering log records, the encryption will be done as the first
338thing (or a new wrapper) in <i>__log_put.&nbsp; </i>See <a href="#Log Record Encryption">Log
339Record Encryption</a> for those details.
340<br>&nbsp;
341<h4>
342Page Changes</h4>
343The checksum and IV values will be stored prior to the first index of the
344page.&nbsp; We have a new P_INP macro that replaces use of inp[X] in the
345code. &nbsp;This macro takes a dbp as an argument and determines where
346our first index is based on whether we have DB_AM_CHKSUM and DB_AM_ENCRYPT
347set.&nbsp; If neither is set, then our first index is where it always was.
348&nbsp;If just checksumming is set, then we reserve a 4-byte checksum.&nbsp;
349If encryption is set, then we reserve 36 bytes for our checksum/IV as well
350as some space to get proper alignment to encrypt on a 16-byte boundary.
351<p>Since several paging macros use inp[X] in them, those macros must now
352take a dbp.&nbsp; There are a lot of changes to make all the necessary
353paging macros take a dbp, although these changes are trivial in nature.
354<p>Also, there is a new function <i>__db_chk_meta</i> to perform checksumming
355and decryption checking on meta pages specifically.&nbsp; This function
356is where we check that the database algorithm matches what the user gave
357(or if they set DB_CIPHER_ANY then we set it), and other encryption related
358testing for bad combinations of what is in the file versus what is in the
359user structures.
360<h4>
361Verification</h4>
362The verification code will also need to be updated to deal with secure
363pages.&nbsp; Basically when the verification code reads in the meta page
364it will call <i>__db_chk_meta</i> to perform any checksumming and decryption.
365<h4>
366<a NAME="Holes in Files"></a>Holes in Files</h4>
367Holes in files will be dealt with rather simply.&nbsp; We need to be able
368to distinguish reading a hole in a file from an encrypted page that happened
369to encrypt to all zero's.&nbsp; If we read a hole in a file, we do not
370want to send that empty page through the decryption routine.&nbsp; This
371can be determined simply without incurring the performance penalty of comparing
372every byte on a page on every read until we get a non-zero byte.
373<br>The __db_pgin function is only given an invalid page P_INVALID in this
374case.&nbsp;&nbsp;So, if the page type, which is always unencrypted, is
375P_INVALID, then we do not perform any checksum verification or decryption.
376<h4>
377Errors and Recovery</h4>
378Dealing with a checksum error is tricky.&nbsp; Ultimately, if a checksum
379error occurs it is extremely likely that the user must do catastrophic
380recovery.&nbsp; There is no other failure return other than&nbsp; DB_RUNRECOVERY
381for indicating that the user should run catastrophic recovery.&nbsp; We
382do not want to add a new error return for applications to check because
383a lot of applications already look for and deal with DB_RUNRECOVERY as
384an error condition and we want to fit ourselves into that application model.&nbsp;
385We already indicate to the user that when they get that error, then they
386need to run recovery.&nbsp; If recovery fails, then they need to run catastrophic
387recovery.&nbsp; We need to get ourselves to the point where users will
388run catastrophic recovery.
389<p>If we get a checksum error, then we need to log a message stating a
390checksum error occurred on page N.&nbsp; In <i>__db_pgin</i>, we can check
391if logging is on in the environment.&nbsp; If so, we want to log the message.
392<p>When the application gets the DB_RUNRECOVERY error, they'll have to
393shut down their application and run recovery.&nbsp; When the recovery encounters
394the record indicating checksum failure, then normal recovery will fail
395and the user will have to perform catastrophic recovery.&nbsp; When catastrophic
396recovery encounters that record, it will simply ignore it.
397<h4>
398<a NAME="Log Record Encryption"></a>Log Record Encryption</h4>
399Log records will be ciphered.&nbsp; It might make sense to wrap <i>__log_put</i>
400to encrypt the DBT we send down.&nbsp; The <i>__log_put </i>function is
401where the checksum is computed before acquiring the region lock.&nbsp;
402But also this function is where we call <i>__rep_send_message</i> to send
403the DBT to the replication clients.&nbsp; Therefore, we need the DBT to
404be encrypted prior to there.&nbsp; We also need it encrypted before checksumming.
405I think <i>__log_put </i>will become <i>__log_put_internal</i>, and the
406new <i>__log_put</i> will encrypt if needed and then call <i>__log_put_internal
407</i>(the
408function formerly known as <i>__log_put</i>).&nbsp; Log records are kept
409in a shared memory region buffer prior to going out to disk.&nbsp; Records
410in the buffer will be encrypted.&nbsp; No locks are held at the time we
411will need to encrypt.
412<p>On reading the log, via log cursors, the log code stores log records
413in the log buffer.&nbsp; Records in that buffer will be encrypted, so decryption
414will occur no matter whether we are returning records from the buffer or
415if we are returning log records directly from the disk. Current checksum
416checking is done in
417<i>__log_get_c_int.</i>&nbsp; Decryption will be done
418after the checksum is checked.
419<p>There are currently two nasty issues with encrypted log records.&nbsp;
420The first is that <i>__txn_force_abort</i> overwrites a commit record in
421the log buffer with an abort record.&nbsp; Well, our log buffer will be
422encrypted.&nbsp; Therefore, <i>__txn_force_abort</i> is going to need to
423do encryption of its new record.&nbsp; This can be accomplished by sending
424in the dbenv handle to the function.&nbsp; It is available to us in <i>__log_flush_commit</i>
425and we can just pass it in.&nbsp; I don't like putting log encryption in
426the txn code, but the layering violation is already there.
427<p>The second issue is that the encryption code requires data that is a
428multiple of 16 bytes and log record lengths are variable.&nbsp; We will
429need to pad log records to meet the requirement.&nbsp; Since the callers
430of <i>__log_put</i> set up the given DBT it is a logical place to pad if
431necessary. We will modify the gen_rec.awk script to have all of the generated
432logging functions pad for us if we have a crypto handle. This padding will
433also expand the size of log files. Anyone calling <i>log_put</i> and using
434security from the application will have to pad on their own or it will
435return an error.
436<p>When ciphering the log file, we will need a different header than the
437current one.&nbsp; The current header only has space for a 4 byte checksum.&nbsp;
438Our secure header will need space for the 16 byte IV and 20 byte checksum.&nbsp;
439This will blow up our log files when running securely since every single
440log record header will now consume 32 additional bytes.&nbsp; I believe
441that the log header does not need to be encrypted.&nbsp; It contains an
442offset, a length and our IV and checksum.&nbsp; Our IV and checksum are
443never encrypted.&nbsp; I don't believe there to be any risk in having the
444offset and length in the clear.
445<p>I would prefer not to have two types of log headers that are incompatible
446with each other.&nbsp; It is not acceptable to increase the log headers
447of all users from 12 bytes to 44 bytes.&nbsp; Such a change would also
448make log files incompatible with earlier releases.&nbsp; Worse even, is
449that the <i>cksum</i> field of the header is in between the offset and
450len.&nbsp; It would be really convenient if we could have just made a bigger
451cksum portion without affecting the location of the other fields.&nbsp;
452Oh well.&nbsp; Most customers will not be using encryption and we won't
453make them pay the price of the expanded header.&nbsp; Keith indicates that
454the log file format is changing with the next release so I will move the
455cksum field so it can at least be overlaid.
456<p>One method around this would be to have a single internal header that
457contains all the information both mechanisms need, but when we write out
458the header we choose which pieces to write.&nbsp; By appending the security
459information to the end of the existing structure, and adding a size field,
460we can modify a few places to use the size field to write out only the
461current first 12 bytes, or the entire security header needed.
462<h4>
463Replication</h4>
464Replication clients are going to need to start all of their individual
465environment handles with the same password.&nbsp; The log records are going
466to be sent to the clients decrypted and the clients will have to encrypt
467them on their way to the client log files.&nbsp; We cannot send encrypted
468log records to clients. &nbsp;The reason is that the checksum and IV&nbsp;are
469stored in the log header and the master only sends the log record itself
470to the client. &nbsp;Therefore, the client has no way to decrypt a log
471record from the master. &nbsp;Therefore, anyone wanting to use truly secure
472replication is going to have to have a secure transport mechanism.&nbsp;
473By not encrypting records, clients can theoretically have different passwords
474and DB won't care.
475<p>On the master side we must copy the DBT sent in.&nbsp; We encrypt the
476original and send to clients the clear record.&nbsp; On the client side,
477support for encryption is added into <i>__log_rep_put</i>.
478<h4>
479Sharing the Environment</h4>
480When multiple processes join the environment, all must use the same password
481as the creator.
482<p>Joining an existing environment requires several conditions to be true.&nbsp;
483First, if the creator of the environment did not create with security,
484then joining later with security is an error.&nbsp; Second, if the creator
485did create it with security, then joining later without security is an
486error.&nbsp; Third, we need to be able to test and check that when another
487process joins a secure environment that the password they provided is the
488same as the one in use by the creator.
489<p>The first two scenarios should be fairly trivial to determine, if we
490aren't creating the environment, we can compare what is there with what
491we have.&nbsp; In the third case, the <i>__crypto_region_init</i> function
492will see that the environment region has a valid passwd_off and we'll then
493compare that password to the one we have in our dbenv handle.&nbsp; In
494any case we'll smash the dbenv handle's passwd and free that memory before
495returning whether we have a password match or not.
496<p>We need to store the passwords themselves in the region because multiple
497calls to the <i>__aes_derivekeys </i>function with the same password yields
498different keyInstance contents.&nbsp; Therefore we don't have any way to
499check passwords other than retaining and comparing the actual passwords.
500<h4>
501Other APIs</h4>
502All of the other APIs will need interface enhancements to support the new
503security methods.&nbsp; The Java and C++ interfaces will likely be done
504by Michael Cahill and Sue will implement the Tcl and RPC changes.&nbsp;
505Tcl will need the changes for testing purposes but the interface should
506be public, not test-only.&nbsp; RPC should fully support security.&nbsp;
507The biggest risk that I can see is that the client will send the password
508to the server in the clear.&nbsp; Anyone sniffing the wires or running
509tcpdump or other packet grabbing code could grab that.&nbsp; Someone really
510interested in using security over RPC probably ought to add authentication
511and other measures to the RPC server as well.
512<h4>
513<a NAME="Utilities"></a>Utilities</h4>
514All should take a -P flag to specify a password for the environment or
515password.&nbsp; Those that take an env and a database might need something
516more to distinguish between env passwds and db passwds. Here is what we
517do for each utility:
518<ul>
519<li>
520berkeley_db_svc - Needs -P after each -h specified.</li>
521
522<li>
523db_archive - Needs -P if the env is encrypted.</li>
524
525<li>
526db_checkpoint - Needs -P if the env is encrypted.</li>
527
528<li>
529db_deadlock - No changes</li>
530
531<li>
532db_dump - Needs -P if the env or database is encrypted.</li>
533
534<li>
535db_load - Needs -P if the env or database is encrypted.</li>
536
537<li>
538db_printlog - Needs -P if the env is encrypted.</li>
539
540<li>
541db_recover - Needs -P if the env is encrypted.</li>
542
543<li>
544db_stat - Needs -P if the env or database is encrypted.</li>
545
546<li>
547db_upgrade - Needs -P if the env or database is encrypted.</li>
548
549<li>
550db_verify - Needs -P if the env or database is encrypted.</li>
551</ul>
552
553<h2>
554Testing</h2>
555All testing should be able to be accomplished via Tcl.&nbsp; The following
556tests (and probably others I haven't thought of yet) should be performed:
557<ul>
558<li>
559Basic functionality - basically a test001 but encrypted without an env</li>
560
561<li>
562Basic functionality, w/ env - like the previous test but with an env.</li>
563
564<li>
565Basic functionality, multiple processes - like first test, but make sure
566others can correctly join.</li>
567
568<li>
569Basic functionality, mult. processes - like above test, but initialize/close
570environment/database first so that the next test processes are all joiners
571of an existing env, but creator no longer exists and the shared region
572must be opened.</li>
573
574<li>
575Recovery test - Run recovery over an encrypted environment.</li>
576
577<li>
578Subdb test - Run with subdbs that are encrypted.</li>
579
580<li>
581Utility test - Verify the new options to all the utilities.</li>
582
583<li>
584Error handling - Test the basic setup errors for both env's and databases
585with multiple processes.&nbsp; They are:</li>
586
587<ol>
588<li>
589Attempt to set a NULL or zero-length passwd.</li>
590
591<li>
592Create Env w/ security and attempt to create database w/ its own password.</li>
593
594<li>
595Env/DB creates with security.&nbsp; Proc2 joins without - should get an
596error.</li>
597
598<li>
599Env/DB creates without security.&nbsp; Proc2 joins with - should get an
600error.</li>
601
602<li>
603Env/DB creates with security.&nbsp; Proc2 joins with different password
604- should get an error.</li>
605
606<li>
607Env/DB creates with security.&nbsp; Closes.&nbsp; Proc2 reopens with different
608password - should get an error.</li>
609
610<li>
611Env/DB creates with security.&nbsp; Closes.&nbsp; Tcl overwrites a page
612of the database with garbage.&nbsp; Proc2 reopens with the correct password.&nbsp;
613Code should detect checksum error.</li>
614
615<li>
616Env/DB creates with security.&nbsp; Open a 2nd identical DB with a different
617password.&nbsp; Put the exact same data into both databases.&nbsp; Close.&nbsp;
618Overwrite the identical page of DB1 with the one from DB2.&nbsp; Reopen
619the database with correct DB1 password.&nbsp; Code should detect an encryption
620error on that page.</li>
621</ol>
622</ul>
623
624<h2>
625Risks</h2>
626There are several holes in this design.&nbsp; It is important to document
627them clearly.
628<p>The first is that all of the pages are stored in memory and possibly
629the file system in the clear.&nbsp; The password is stored in the shared
630data regions in the clear.&nbsp; Therefore if an attacker can read the
631process memory, they can do whatever they want.&nbsp; If the attacker can
632read system memory or swap they can access the data as well.&nbsp; Since
633everything in the shared data regions (with the exception of the buffered
634log) will be in the clear, it is important to realize that file backed
635regions will be written in the clear, including the portion of the regions
636containing passwords.&nbsp; We recommend to users that they use system
637memory instead of file backed shared memory.
638</body>
639</html>
Note: See TracBrowser for help on using the repository browser.