Re: [sqlite] equality searches and range searches with encrypteddata
On 8/27/08, Dennis Cote <[EMAIL PROTECTED]> wrote: > P Kishor wrote: > > > > > only badly written Perl, or Perl specifically written to be obfuscated > > such as in Perl golf, is inscrutable. Well written Perl (I practice as > > close to literal programming in Perl as possible) is quite pleasant > > and easy to read. > > > > > > This quote is from O'Reilly's Learning Perl (the Llama book) by Randal > Schwartz and Tom Phoenix (experts in Perl I believe). > > "Yes, sometimes Perl looks like line noise to the uninitiated, but to the > seasoned Perl programmer, it looks like checksummed line noise with a > mission in life." > > So I'm not the only one who thinks the syntax has room for improvement. :-) The keyword in the quote above is "sometimes" which is the same as "unintentionally badly written or intentionally obfuscated" -- here is the quote through a filter -- "Yes, unintentionally badly written or intentionally obfuscated Perl looks like line noise to the uninitiated, but to the seasoned Perl programmer..." usually this kind of code is produced by those new, trying to show off, or being competitive on purpose (as in a Perl golf competition), or just for kicks. It doesn't have any place in serious, production code, so there is much Perl code that is very lovely to read. But, my apologies for the small digression -- on to more pertinent SQLite-related discussions. > > Dennis Cote > > > -- Puneet Kishor ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
lovely discourse, but although I feel bad disagreeing (on a tiny point) with the otherwise very agreeable Mr. Cote... On 8/27/08, Dennis Cote <[EMAIL PROTECTED]> wrote: > Derek Developer wrote: > > Thanks for the link. Unfortunatly its a little expensive and probably > > 50% slower than my implementation. > > > > > On what basis do you make that claim? > > > > No offense, but C is a language that a lot of us tolerate and is not > > the panacea that some C developers like to believe it is. Reading C > > is like reading Chinese. ASM may not be a high level language, but it > > certainly is fast. > > > > > C is the lingua franca of the computer world. Every programmer should be > able to read it comfortably. I find reading well written C code, such as > SQLite, to be pleasant, and certainly much easier than assembler code. > Some languages, such as APL (which I liked) and Perl (which I really > don't know very well) are inscrutable to the casual reader. only badly written Perl, or Perl specifically written to be obfuscated such as in Perl golf, is inscrutable. Well written Perl (I practice as close to literal programming in Perl as possible) is quite pleasant and easy to read. Other than that, yes, agree with everything else you say. > C is not and > should not be in that category. > > Assembly language has two major drawbacks, it is not portable and it is > very verbose. The first means that any code you write for one platform > has to be completely rewritten for another. The second often leads users > to adopt the shortest, simplest, code sequence to accomplish their goal. > This is often not the fastest way to accomplish that task. Usually, > selecting a better algorithm will do far more to speed up code than > rewriting it in assembler. > > Studies have consistently shown that a good compiler can produce code > that is nearly as good as the best hand crafted assembly. There is > almost never a reason to write anything except the core inner loops of a > CPU intensive operation (such as encryption or decryption) in assembler. > It is quite simply a waste of time to do otherwise. > > The only effective way to write assembly code is in conjunction with > good measurement tools. Write the code in a high level language with a > good optimizing compiler, like C. Then measure the code to determine > where the program actually spends its time. Next, review the code > generated by the compiler for the inner most loops in those sections, > and replace with hand written assembly code only if you believe your > assembly code will be faster than that produced by the compiler. > Finally, measure the resulting code and see if it is in fact any faster > than the code the compiler generated. > > In this day of out of order and speculative execution of instructions, > and the critical dependency of the CPU on the performance of the memory > caching system, it is very difficult to guesstimate the execution speed > of a sequence of code especially assembly code. Modern compilers often > do a much better job of this than any developer can. > > Assembly can be used to write faster code snippets, but it is often > slower when used to write large applications because the difficulty in > writing higher level, more complex, algorithms in assembler often leads > to the use of simpler slower algorithms. > > In short, writing in assembly language does not guarantee that the > resulting program will be fast. Assembler can be fast, but it is by no > means certain that it is fast. > > > Dennis Cote > > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- Puneet Kishor http://punkish.eidesis.org/ Nelson Institute for Environmental Studies http://www.nelson.wisc.edu/ Open Source Geospatial Foundation (OSGeo) http://www.osgeo.org/ ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Derek Developer wrote: > Thanks for the link. Unfortunatly its a little expensive and probably > 50% slower than my implementation. > On what basis do you make that claim? > No offense, but C is a language that a lot of us tolerate and is not > the panacea that some C developers like to believe it is. Reading C > is like reading Chinese. ASM may not be a high level language, but it > certainly is fast. > C is the lingua franca of the computer world. Every programmer should be able to read it comfortably. I find reading well written C code, such as SQLite, to be pleasant, and certainly much easier than assembler code. Some languages, such as APL (which I liked) and Perl (which I really don't know very well) are inscrutable to the casual reader. C is not and should not be in that category. Assembly language has two major drawbacks, it is not portable and it is very verbose. The first means that any code you write for one platform has to be completely rewritten for another. The second often leads users to adopt the shortest, simplest, code sequence to accomplish their goal. This is often not the fastest way to accomplish that task. Usually, selecting a better algorithm will do far more to speed up code than rewriting it in assembler. Studies have consistently shown that a good compiler can produce code that is nearly as good as the best hand crafted assembly. There is almost never a reason to write anything except the core inner loops of a CPU intensive operation (such as encryption or decryption) in assembler. It is quite simply a waste of time to do otherwise. The only effective way to write assembly code is in conjunction with good measurement tools. Write the code in a high level language with a good optimizing compiler, like C. Then measure the code to determine where the program actually spends its time. Next, review the code generated by the compiler for the inner most loops in those sections, and replace with hand written assembly code only if you believe your assembly code will be faster than that produced by the compiler. Finally, measure the resulting code and see if it is in fact any faster than the code the compiler generated. In this day of out of order and speculative execution of instructions, and the critical dependency of the CPU on the performance of the memory caching system, it is very difficult to guesstimate the execution speed of a sequence of code especially assembly code. Modern compilers often do a much better job of this than any developer can. Assembly can be used to write faster code snippets, but it is often slower when used to write large applications because the difficulty in writing higher level, more complex, algorithms in assembler often leads to the use of simpler slower algorithms. In short, writing in assembly language does not guarantee that the resulting program will be fast. Assembler can be fast, but it is by no means certain that it is fast. Dennis Cote ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Thanks for the link. Unfortunatly its a little expensive and probably 50% slower than my implementation. No offense, but C is a language that a lot of us tolerate and is not the panacea that some C developers like to believe it is. Reading C is like reading Chinese. ASM may not be a high level language, but it certainly is fast. My knowledge of encryption is above adequate, while I will be the first to admit my understanding of the inner workings of a database is not. As I grapple to understand how Encryption may be applied to a database project I am developing, I have displayed my ignorance in the hope of learning. It is fairly obvious that some very talented developers on this forum would prefer to use this as an exercise in pedantic sniping rather than offer substantive help. To the others, I thank you. Cory Nelson <[EMAIL PROTECTED]> wrote: On Mon, Aug 25, 2008 at 6:33 PM, Derek Developer wrote: > Dennis thank you for taking the time to explain that. I have read the > Architecture page and I think I have a better idea. > > Since this does seem to be a viable way to protect the data I would like to > implement the schema, but using AES instead of MD5 which is unsecure. > > Has anyone done this and posted the code? > drh sells a version with encryption builtin here: http://www.hwaci.com/sw/sqlite/prosupport.html I don't mean any offense here, but in case you aren't doing this to learn and will really be storing people's credit cards and socials: you are not knowledgeable enough in this area to be writing any production encryption code. Doing so would be a disservice to any customers. Definitely use available tested code in this case, like drh's version. -- Cory Nelson ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
On Mon, Aug 25, 2008 at 6:33 PM, Derek Developer <[EMAIL PROTECTED]> wrote: > Dennis thank you for taking the time to explain that. I have read the > Architecture page and I think I have a better idea. > > Since this does seem to be a viable way to protect the data I would like to > implement the schema, but using AES instead of MD5 which is unsecure. > > Has anyone done this and posted the code? > drh sells a version with encryption builtin here: http://www.hwaci.com/sw/sqlite/prosupport.html I don't mean any offense here, but in case you aren't doing this to learn and will really be storing people's credit cards and socials: you are not knowledgeable enough in this area to be writing any production encryption code. Doing so would be a disservice to any customers. Definitely use available tested code in this case, like drh's version. -- Cory Nelson ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
>No, the index is stored in a separate Btree. The master table simply >stores the page number of that btree's root page. With that information >SQLite can read and decrypt the index's root page and begin a O(log N) >search for the first matching record, reading in and decrypting more >pages as required. >... an index will work securely and efficiently for such a search in an >encrypted database. Dennis thank you for taking the time to explain that. I have read the Architecture page and I think I have a better idea. Since this does seem to be a viable way to protect the data I would like to implement the schema, but using AES instead of MD5 which is unsecure. Has anyone done this and posted the code? ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Igor Tandetnik wrote: > > Since I'm not entirely clear of the set of premises you refer to as > "that", I'm not sure whether they happen to be the case or not. But > since I know the conclusion you arrived at is false, I can only assume > that one or more of those premises are incorrect, and/or the logical > deduction from the premises to the conclusion is flawed. > Classic. :-) Dennis Cote ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Derek Developer <[EMAIL PROTECTED]> wrote: > appologies, "master database" should read "MASTER TABLE" > This is where the index is stored I assume? An index is an index. It's not stored in any table, "MASTER" or otherwise. > You suggested that each record would NOT be decrypted for a SELECT > because the INDEX would handle that work. Index doesn't "handle" any work. It's just a data structure. The database engine does the work. It might use an index to speed up execution of certain statements. Yes, in many cases, the engine can avoid reading every record in the table, by using an index to narrow the search down to the relevant records. > Since the INDEX is > proabably not a MAC hash of the SS# then it would be accessible from > the MASTER TABLE yes? I'm not sure what this "MASTER TABLE" you speak of is, or how an index would be accessible from it. > If that is the case then clearly an Index is not a viable solution > and each page will have to be decrypted to perform and equlity/range > search. Since I'm not entirely clear of the set of premises you refer to as "that", I'm not sure whether they happen to be the case or not. But since I know the conclusion you arrived at is false, I can only assume that one or more of those premises are incorrect, and/or the logical deduction from the premises to the conclusion is flawed. >> Unlike the situation here, you can't encrypt individual columns > > I have several ASm implementations of AES and secure HASH Algos that > are very very fast. I can apply these to individual columns for each > row. Sure, you can build a homebrewn solution. It is then up to you to keep it secure, of course. I can't help but notice that you have conveniently omitted the second half of my statement above. > Before I implement this, I wanted to make sure I understand the > implementation at the page level. Obviously a single Row can take up > more than one page, but I am still not clear if a single page can > ever contain more than one Row? Yes it can. Igor Tandetnik ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Derek Developer wrote: > appologies, "master database" should read "MASTER TABLE" This is > where the index is stored I assume? > No, the index is stored in a separate Btree. The master table simply stores the page number of that btree's root page. With that information SQLite can read and decrypt the index's root page and begin a O(log N) search for the first matching record, reading in and decrypting more pages as required. > > If that is the case then clearly an Index is not a viable solution > and each page will have to be decrypted to perform and equlity/range > search. > No, an index will work securely and efficiently for such a search in an encrypted database. > > Before I implement this, I wanted to make sure I understand the > implementation at the page level. Obviously a single Row can take up > more than one page, but I am still not clear if a single page can > ever contain more than one Row? > Yes, a table page can contain multiple rows, and an index page can contain multiple index entries. You may want to review http://www.sqlite.org/arch.html. The encryption and decryption is done between the pager and the OS interface layers. Nothing else changes, and all the data is stored securely encrypted in the pages of the file. HTH Dennis Cote ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
appologies, "master database" should read "MASTER TABLE" This is where the index is stored I assume? You suggested that each record would NOT be decrypted for a SELECT because the INDEX would handle that work. Since the INDEX is proabably not a MAC hash of the SS# then it would be accessible from the MASTER TABLE yes? If that is the case then clearly an Index is not a viable solution and each page will have to be decrypted to perform and equlity/range search. That doesn't sound like it will be fast... >Unlike the situation here, you can't encrypt individual columns I have several ASm implementations of AES and secure HASH Algos that are very very fast. I can apply these to individual columns for each row. I suspect that, as has been pointed out, the disk access would be more time consuming than the encryption. I would then do a MAC index in a secondary column. Before I implement this, I wanted to make sure I understand the implementation at the page level. Obviously a single Row can take up more than one page, but I am still not clear if a single page can ever contain more than one Row? Igor Tandetnik <[EMAIL PROTECTED]> wrote: Derek Developer wrote: > So if the data is indexed prior to the encryption step, does SQLite > manage that index internally as a Btree that s stored somewhere? Is > it part of the MASTER database? I'm not sure what you mean by "MASTER database" (as opposed to which other database?) SQLite stores everything in a single file - data, indexes and all. > Obviously there would be a security issue if the index is accessible > as per this: > http://blogs.msdn.com/lcris/archive/2005/12/22/506931.aspx Unlike the situation here, you can't encrypt individual columns or tables with SQLite (at least not using any products I'm familiar with). You encrypt the whole file. > If I am storing CC# or SS#, the index would contain them yes? Well, if you created an index on those columns, then of course the index would contain values from them. -- With best wishes, Igor Tandetnik With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead. -- RFC 1925 ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Derek Developer <[EMAIL PROTECTED]> wrote: > So if the data is indexed prior to the encryption step, does SQLite > manage that index internally as a Btree that s stored somewhere? Is > it part of the MASTER database? I'm not sure what you mean by "MASTER database" (as opposed to which other database?) SQLite stores everything in a single file - data, indexes and all. > Obviously there would be a security issue if the index is accessible > as per this: > http://blogs.msdn.com/lcris/archive/2005/12/22/506931.aspx Unlike the situation here, you can't encrypt individual columns or tables with SQLite (at least not using any products I'm familiar with). You encrypt the whole file. > If I am storing CC# or SS#, the index would contain them yes? Well, if you created an index on those columns, then of course the index would contain values from them. -- With best wishes, Igor Tandetnik With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead. -- RFC 1925 ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Thanks Igor, So if the data is indexed prior to the encryption step, does SQLite manage that index internally as a Btree that s stored somewhere? Is it part of the MASTER database? Obviously there would be a security issue if the index is accessible as per this: http://blogs.msdn.com/lcris/archive/2005/12/22/506931.aspx If I am storing CC# or SS#, the index would contain them yes? Igor Tandetnik <[EMAIL PROTECTED]> wrote: Derek Developer wrote: > Thank you for your replys, but I am still not sure I understand how a > Query is executed on (page) encrypted data wihout either indexing the > data prior to encrption, creating a secondary hash column of the data > or simply decrypting every page to get at the underlying data? The data _is_ indexed prior to encryption (assuming you did create an index on the appropriate column, of course), then the pages containing the index are themselves encrypted when written to the file (and decrypted when read back, of course). Encryption is built into the I/O. Whenever a page-worth of data is read from disk, it is decrypted right afterwards. When a page is written, it's encrypted right before. The I/O engine doesn't care what kind of data is on that page - it's only concerned about shuffling bytes in and out of storage. The database engine doesn't care whether the file is encrypted or not - it always gets plaintext pages from I/O subsystem. Igor Tandetnik ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Derek, I'm more "onlooker" than "expert" here, but I think the answers are: 1) Yes, when a full table scan is performed, the entire table data is decrypted. (If you're using a LIMIT clause without an ORDER BY, then perhaps only part is decrypted -- the point being that the same pages are read and decrypted as would be simply *read* with a non-encrypted database.) For SELECTS where only index pages must be read, then only index pages must be decrypted. 2) For most modern computers, the time to read a sector from disk is much longer than the time to decrypt it, so that even though more CPU time is required, it may not significantly slow data delivery in many cases. This email and any attachments have been scanned for known viruses using multiple scanners. We believe that this email and any attachments are virus free, however the recipient must take full responsibility for virus checking. This email message is intended for the named recipient only. It may be privileged and/or confidential. If you are not the named recipient of this email please notify us immediately and do not copy it or use it for any purpose, nor disclose its contents to any other person. ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] equality searches and range searches with encrypteddata
Derek Developer <[EMAIL PROTECTED]> wrote: > Thank you for your replys, but I am still not sure I understand how a > Query is executed on (page) encrypted data wihout either indexing the > data prior to encrption, creating a secondary hash column of the data > or simply decrypting every page to get at the underlying data? The data _is_ indexed prior to encryption (assuming you did create an index on the appropriate column, of course), then the pages containing the index are themselves encrypted when written to the file (and decrypted when read back, of course). Encryption is built into the I/O. Whenever a page-worth of data is read from disk, it is decrypted right afterwards. When a page is written, it's encrypted right before. The I/O engine doesn't care what kind of data is on that page - it's only concerned about shuffling bytes in and out of storage. The database engine doesn't care whether the file is encrypted or not - it always gets plaintext pages from I/O subsystem. Igor Tandetnik ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
