RE: Database Encryption

Madison, I've heard, that the encryption algorithm, implemented in IDS 10, can produce different encrypted records for same input and same key (while the decryption is able to exactly reconstruct the original key). >From this perspective, even 'equal' search on encrypted data can be done by functional index - just because the encryption function can't be considered 'non-variant' -Alexey > -----Original Message----- > From: informix-list-bounces@iiug.org [mailto:informix-list-bounces@iiug.org] > On Behalf Of Madison Pruet > Sent: Thursday, June 29, 2006 4:33 PM > To: informix-list@iiug.org > Subject: Re: Database Encryption > > Neil Truby wrote: > > "Obnoxio The Clown" <obnoxio@serendipita.com> wrote in message > > news:mailman.395.1151597436.19084.informix-list@iiug.org... > >> Campbell, John \\(GE Cons Fin\\) said: > >>> Any impact to performance? > >> Yes, plus it makes indexing pointless (on encrypted columns). > > > > Why? > > > > > Neil, > > Encryption uses a key which is not part of the actually encrypted data, > but which is used to transform the bits in the encrypted value of the > plain-text representation of the data. For the same data if you use a > different key, then you get different encrypted values. > > Indexes are used for great than and less than as well as equality. > > > You can never use encrypted columns for less than or greater than on the > encrypted data itself. > > You can use equality on the encrypted data, but only if the same key is > used to encrypt all of the data. > > If you are using the same key to encrypt all of the data, then why encrypt? > > _______________________________________________ > Informix-list mailing list > Informix-list@iiug.org > http://www.iiug.org/mailman/listinfo/informix-list

Alexey Sonkin wrote: > Madison Pruet wrote: >> Neil Truby wrote: >>> Obnoxio The Clown wrote: >>>> Campbell, John asked: >>>>> Any impact to performance? >>>> Yes, plus it makes indexing pointless (on encrypted columns). >>> Why? >> >> Encryption uses a key which is not part of the actually encrypted >> data, but which is used to transform the bits in the encrypted >> value of the plain-text representation of the data. For the same >> data if you use a different key, then you get different encrypted >> values. >> >> Indexes are used for great than and less than as well as equality. >> >> You can never use encrypted columns for less than or greater than >> on the encrypted data itself. >> >> You can use equality on the encrypted data, but only if the same >> key is used to encrypt all of the data. >> >> If you are using the same key to encrypt all of the data, then why >> encrypt. > > I've heard, that the encryption algorithm, implemented in > IDS 10, can produce different encrypted records for same > input and same key (while the decryption is able to exactly > reconstruct the original key). > > From this perspective, even 'equal' search on encrypted data > can be done by functional index - just because the encryption function > can't be considered 'non-variant' So much almost right information floating around... To some extent, see my "Column-Level Encryption in IDS 10.00" presentation from IDUG 2006 or IMTC 2005 or various other conferences. Where to begin? ENCRYPTION FUNCTIONS The 'manual pages' for ENCRYPT_TDES() and ENCRYPT_AES() in the presentation make the point that given the same password and data, you get a different result each time. You should have to invoke ENCRYPT_TDES() around 2^56 times and ENCRYPT_AES() around 2^64 times before you get a repeat, somewhere in that collection of results. This is based on the "Birthday Paradox", which says that if you have N possible results uniformly distributed - such as 365 days in a year when you might have a birthday - then when you have about sqrt(N) samples, you can expect to see a pair with the same result (2 people with the same birthday). There's a constant factor too - sqrt(365) = 19.1, but you need 23 people for the probability that 2 share the same birthday to be greater than 50%. See http://en.wikipedia.org/wiki/Birthday_paradox for the details. When the IDS encryption functions operate, they take the password or pass phrase that you provide (6-128 characters), and hash it, along with a random IV or Initialization Vector, and use that to create a 112-bit key for ENCRYPT_TDES or a 128-bit key for ENCRYPT_AES. The encrypted data stores the IV, the encryption algorithm, and the encrypted data (I'm going to ignore hints in this discussion), and usually uses a Base-64 encoding to ensure that the data is printable. Note that the password is *NOT* stored. The presentation has the detailed formula to use for the size of the resulting data. Note that you might use different passwords for each row of data in a table (and even for each encrypted column in each row), or you might use the same password for any given encrypted column. I call these modes 'web mode' and 'MIS mode'. Web mode might be useful for a web site where each customer's credit card number is stored encrypted with a key known only to the customer. While an order is processed, the credit card number can be retained encrypted by a key known by the system, but between orders, the credit card number is stored using a password/key known only by the user. (Main point to note: if the user forgets their password, the data is lost - do not use this to store critical data that cannot be re-entered if necessary.) In MIS mode, a single password is used for all the data in a given column - and the user doesn't need to provide the password - but the applications will need to know how to determine the correct passwords to use. Indeed, IDS is not really aware that the data is stored encrypted, and you can - if you are careless - store unencrypted data in a column in some rows and encrypted data in other rows. The DECRYPT_CHAR function only needs the encrypted data and the password in order to decrypt the data. FUNCTIONAL INDEXES OK. The first problem with indexing encrypted data is that the order of the data in the index bears no resemblance to the order of the unencrypted data. Therefore, as mentioned above, only equality comparisons can ever work meaningfully. However, you cannot expect to regenerate the same encrypted data twice even given the same inputs - password and data - so the only way you can even manage equality joins on encrypted data is if you copy the encrypted value around. Now to functional indexes. First, note the the function must be invariant - which rules out the use of the encryption functions because they are the antithesis of invariant functions. So, the only possible use is for the decrypt functions. Now, if you are worried about the data being stored encrypted, you do not want the indexes to store the unencrypted data - but if you build an index using the decrypt functions, that is what you are doing. So, you've defeated the purpose of using encryption - the database is still storing the data in an unencrypted format. (There's another reason for not using an encryption functional index - to generate the function value, you need to store the unencrypted data value, which again defeats the object of the exercise.) CRYPTOGRAPHIC HASH FUNCTIONS So, if you need to convert an application that uses something sensitive such as a SSN or CCN (social security number or credit card number) as the joining key (or part of the joining key) between tables, you will need to redesign your database schema. You should either use a surrogate key (typically, a SERIAL or SERIAL8 column, or you might prefer to use a SEQUENCE instead), or you need an invariant non-invertible function that, given the same input each time, always produces the same output. For example, you might use an MD5(*) hash of the SSN or CCN - or maybe several fields - to generate the identifier. The join then equates these hash values. You have to store the original keys (SSN or CCN) separately, and in encrypted format, in the appropriate table. This involves application changes, in general. (*) Yes; you do need to be careful about MD5 and similar algorithms. It is feasible to compute the MD5 checksum of all 1 billion possible US SSNs (because they are 9 digits long). Maybe you should use SSN+DoB (date of birth) to reduce the possibility of precomputing the answers. But the most important thing is that it be reproducible - unlike the encryption functions. Additionally, there have been attacks on MD5 and even SHA-1 that make it somewhat questionable how secure they are. If you're interested, you can find more in the archives at http://www.schneier.com/blog - search in the archives for Feb and Mar 2005. OK - that'll do for now; if there's anything that's not clear, you'd better ask the questions. You can't afford to get this stuff wrong. -- Jonathan Leffler #include <disclaimer.h> Email: jl

Jonathan Leffler wrote: > > When the IDS encryption functions operate, they take the password or > pass phrase that you provide (6-128 characters), and hash it, along with > a random IV or Initialization Vector, and use that to create a 112-bit > key for ENCRYPT_TDES or a 128-bit key for ENCRYPT_AES. The encrypted > data stores the IV, the encryption algorithm, and the encrypted data > (I'm going to ignore hints in this discussion), and usually uses a > Base-64 encoding to ensure that the data is printable. Note that the > password is *NOT* stored. The presentation has the detailed formula to > use for the size of the resulting data. Dang it. I forgot that with disk encryption that we are storing the initialization vector in the data. We aren't doing that network encryption since the sender and receiver are both calculating the IV with each transmission and thus is not transmitting the IV. For anyone else reading this. --- There are several ways to 'chain' encryption. This means that the results of one block (usually 8 bytes) are hashed and used to transform the next block. This is done to reduce the patterns which might be found within the encrypted string and thus makes it much more difficult to determine the key used to encrypt the data. So the same data and password will generally generate a unique encrypted string on the same plain text. And the probability of having a false collision on two distinct plain text strings is highly remote since the IV is included in the encrypted string. So it is possible to use an index (well sort of) on an encrypted column. You'd still run into problems with less than and greater than on an encrypted column. Also - joins are going to be a problem using an index on encrypted data because unless the same key and the same IV is used on both tables involved in the join - well.... > > Note that you might use different passwords for each row of data in a > table (and even for each encrypted column in each row), or you might use > the same password for any given encrypted column. I call these modes > 'web mode' and 'MIS mode'. Web mode might be useful for a web site > where each customer's credit card number is stored encrypted with a key > known only to the customer. While an order is processed, the credit > card number can be retained encrypted by a key known by the system, but > between orders, the credit card number is stored using a password/key > known only by the user. (Main point to note: if the user forgets their > password, the data is lost - do not use this to store critical data that > cannot be re-entered if necessary.) In MIS mode, a single password is > used for all the data in a given column - and the user doesn't need to > provide the password - but the applications will need to know how to > determine the correct passwords to use. Indeed, IDS is not really aware > that the data is stored encrypted, and you can - if you are careless - > store unencrypted data in a column in some rows and encrypted data in > other rows. > > The DECRYPT_CHAR function only needs the encrypted data and the password > in order to decrypt the data. > > FUNCTIONAL INDEXES > > OK. The first problem with indexing encrypted data is that the order of > the data in the index bears no resemblance to the order of the > unencrypted data. Therefore, as mentioned above, only equality > comparisons can ever work meaningfully. However, you cannot expect to > regenerate the same encrypted data twice even given the same inputs - > password and data - so the only way you can even manage equality joins > on encrypted data is if you copy the encrypted value around. > > Now to functional indexes. First, note the the function must be > invariant - which rules out the use of the encryption functions because > they are the antithesis of invariant functions. So, the only possible > use is for the decrypt functions. Now, if you are worried about the > data being stored encrypted, you do not want the indexes to store the > unencrypted data - but if you build an index using the decrypt > functions, that is what you are doing. So, you've defeated the purpose > of using encryption - the database is still storing the data in an > unencrypted format. (There's another reason for not using an encryption > functional index - to generate the function value, you need to store the > unencrypted data value, which again defeats the object of the exercise.) > > CRYPTOGRAPHIC HASH FUNCTIONS > > So, if you need to convert an application that uses something sensitive > such as a SSN or CCN (social security number or credit card number) as > the joining key (or part of the joining key) between tables, you will > need to redesign your database schema. You should either use a > surrogate key (typically, a SERIAL or SERIAL8 column, or you might > prefer to use a SEQUENCE instead), or you need an invariant > non-invertible function that, given the same input each time, always > produces the same output. For example, you might use an MD5(*) hash of > the SSN or CCN - or maybe several fields - to generate the identifier. > The join then equates these hash values. You have to store the original > keys (SSN or CCN) separately, and in encrypted format, in the > appropriate table. This involves application changes, in general. > > (*) Yes; you do need to be careful about MD5 and similar algorithms. It > is feasible to compute the MD5 checksum of all 1 billion possible US > SSNs (because they are 9 digits long). Maybe you should use SSN+DoB > (date of birth) to reduce the possibility of precomputing the answers. > But the most important thing is that it be reproducible - unlike the > encryption functions. Additionally, there have been attacks on MD5 and > even SHA-1 that make it somewhat questionable how secure they are. If > you're interested, you can find more in the archives at > http://www.schneier.com/blog - search in the archives for Feb and Mar 2005. > > OK - that'll do for now; if there's anything that's not clear, you'd > better ask the questions. You can't afford to get this stuff wrong. >

Madison Pruet wrote: > Jonathan Leffler wrote: > >> >> When the IDS encryption functions operate, they take the password or >> pass phrase that you provide (6-128 characters), and hash it, along >> with a random IV or Initialization Vector, and use that to create a >> 112-bit key for ENCRYPT_TDES or a 128-bit key for ENCRYPT_AES. The >> encrypted data stores the IV, the encryption algorithm, and the >> encrypted data (I'm going to ignore hints in this discussion), and >> usually uses a Base-64 encoding to ensure that the data is printable. >> Note that the password is *NOT* stored. The presentation has the >> detailed formula to use for the size of the resulting data. > > > Dang it. I forgot that with disk encryption that we are storing the > initialization vector in the data. We aren't doing that network > encryption since the sender and receiver are both calculating the IV > with each transmission and thus is not transmitting the IV. > > For anyone else reading this. --- There are several ways to 'chain' > encryption. This means that the results of one block (usually 8 bytes) > are hashed and used to transform the next block. This is done to reduce > the patterns which might be found within the encrypted string and thus > makes it much more difficult to determine the key used to encrypt the data. > > So the same data and password will generally generate a unique encrypted > string on the same plain text. And the probability of having a false > collision on two distinct plain text strings is highly remote since the > IV is included in the encrypted string. > > So it is possible to use an index (well sort of) on an encrypted column. > > You'd still run into problems with less than and greater than on an > encrypted column. > > Also - joins are going to be a problem using an index on encrypted data > because unless the same key and the same IV is used on both tables > involved in the join - well.... > Just a few words on indexing encrypted data: 1 - Hash indexes only require an equality operation on the hashed value and the encrypted value and so can be applied to encrypted columns. 2 - Join comparisons between tables can be performed on record or column wide encrypted objects if the keys for each table or table.column is known to the engine (or has been user supplied) and can be used to decrypt the value from the independent table and reencrypt it using the password and algorithm of the dependent table for lookup in the hash index. Art S. Kagel