Tóm tắt
Các ứng dụng trực tuyến rất dễ bị đánh cắp thông tin nhạy cảm vì kẻ xấu có thể khai thác các lỗi phần mềm để
truy cập tới dữ liệu cá nhân, và vì các quản trị viên tò mò hoặc có ý đồ xấu có thể thu thập và làm rò rỉ dữ liệu.
CryptDB là một hệ thống cung cấp tính bảo mật đã được chứng minh chống lại được các tấn công vào các ứng
dụng cơ sở dữ liệu SQL. Nó hoạt động dựa trên việc thực hiện các truy vấn SQL trên dữ liệu được mã hóa sử
dụng một tập hợp các lược đồ mã hóa SQL hiệu quả (It works by executing SQL queries over encrypted data
using a collection of efficient SQL-aware encryption schemes). CryptDB cũng có thể kết hợp các key mã hóa
với các mật khẩu của người dung, vì vậy một mục dữ liệu (a data item) chỉ có thể được giải mã bằng cách sử
dụng mật khẩu của một trong những người sử dụng truy cập vào dữ liệu đó. Kết quả là, một quản trị viên cơ sở
dữ liệu không bao giờ truy cập được để giải mã dữ liệu, và kể cả khi tất cả server bị thỏa hiệp, đối phương
không thể giải mã dữ liệu của bất kỳ người dùng không đăng nhập nào. Một phân tích theo dõi 126 triệu truy
vấn SQL từ một server MySQL cho thấy rằng CryptDB có thể hộ trợ 95.5% các phép toán trên cơ sở dữ liệu
được mã hóa của 128,840 cột được thấy. Đánh giá của chúng tôi chỉ ra rằng CryptDB có chi phí thấp, giảm
14.5% thông lượng (throughput) cho phpBB, một ứng dụng web forum, và 26% cho các truy vấn từ TPCC, so
với unmodified MySQL. Chaining encryption keys to user passwords requires 11–13 unique schema
annotations to secure more than 20 sensitive fields and 2–7 lines of source code changes for three multi-user
web applications.

1.Giới thiệu
Trộm cắp thông tin cá nhân là một vấn đề quan trọng, đặc biệt là đối với các ứng dụng trực tuyến [40]. Đối
phương có thể khải thác các lỗ hổng bảo mật phần mềm để truy cập trái phép vào các server [32]; những quản
trị viên tò mò hay có ý đồ xấu tại các nhà cung cấp hosting hoặc ứng dụng có thể ăn cắp dữ liệu cá nhân [6]; và
những kẻ tấn công truy cập vật lý vào các server có thể truy cập tất cả dữ liệu trên đĩa và trong bộ nhớ [23].
Một trong các hướng để giảm thiểu những tổn hại gây ra bởi server bị thỏa hiệp là mã hóa dữ liệu nhạy cảm,
như trong SUNDR [28], SPORC[16], và Depot [30], và chạy tất cả các tính toán (logic ứng dụng) trên các
client. Không may là nhiều ứng dụng quan trọng không tiếp cận theo cách này, bao gồm các database-backed
web site mà xử lý các truy vấn để sinh ra dữ liệu cho người dùng, và các ứng dụng mà tính toán trên một lượng
lớn dữ liệu. Ngay cả khi phương pháp này được đảm bảo, việc chuyển đổi một ứng dụng phía server (serverside) hiện có sang dạng này có thể gặp khó khăn. Một cách tiếp cận khác sẽ là xem xét các giải pháp theo lý
thuyết như là mã hóa đồng cấu (homomorphic encryption) hoàn toàn [19], cho phép các server tính toán các
hàm (functions) tùy ý trên dữ liệu được mã hóa, trong khi chỉ các client xem dữ liệu được mã hóa. Tuy nhiên
mã hóa đồng cấu hoàn toàn vẫn rất tốn kém theo orders of magnitude [10, 21].

Bài viết này trình bày về CryptDB, một hệ thống nghiên cứu (explores) một điểm thiết kế trung gian
(intermediate design point) để cung cấp bảo mật cho các ứng dụng sử dụng các hệ quản trị cơ sở dữ liệu
(DBMSes). CryptDB tận dụng cấu trúc điển hình của các database-backen application, bao gồm một server
DBMS và một server ứng dụng riêng biệt, được thể hiện trong Hình 1; server ứng dụng riêng biệt này chạy code
ứng dụng và đưa ra các truy vấn DBMS thay cho một hoặc nhiều người dùng. Cách tiếp cận của CryptDB là để
thực thi các truy vấn trên dữ liệu được mã hóa, và điều làm nó thực tế là SQL sử dụng một tập xác định các toán
tử (operators), mỗi toán tử chúng ta có khả năng hỗ trợ hiệu quả trên dữ liệu mã hóa.


Hình 1: Kiến trúc của CryptDB bao gồm 2 phần: một database proxy và một unmodified DBMS. CryptDB sử
dụng các hàm người dùng định nghĩa (user-defined functions – UDFs) để thực hiện các tính toán mật mã trong
DBMS. Các hộp chữ nhật vuông và bo tròn đại diện các tiến trình và dữ liệu tương ứng. Các hình có màu đậm
chỉ ra các thành phần được thêm vào bởi CryptDB. Các đường nét đứt cho thấy sự tách biệt giữa các máy tính
của người dùng, server ứng dụng, một server đang chạy proxy cơ sở dữ liệu của CryptDB (nó thường giống một
server ứng dụng), và DBMS server. CryptDB giải quyết hai loại đe dọa, hiển thị dưới các đường chấm. Trong
mối đe dọa thứ nhất, một quản trị viên cơ sở dữ liệu tò mò với truy cập hoàn toàn tới DBMS server dòm ngó dữ
liệu cá nhân, trong trường hợp này CryptDB ngăn chặn DBA truy cập vào bất kỳ thông tin cá nhân nào. Trong
mối đe dọa thứ hai, kẻ xấu đạt đượt kiểm soát hoàn toàn cả phần mềm và phần cứng của ứng dụng, proxy, và
các DBMS server, trong trường hợp này CryptDB đảm bảo kẻ xấu không thẻ có được dữ liệu thuộc về người
đung chưa đăng nhập (ví dụ: user 2).
CryptDB giải quyết hai mối đe dọa. Mối đe dọa đầu tiên là một người quản trị cơ sở dữ liệu tò mò (curious
database administrator – DBA) người cố gắng tìm hiểu dữ liệu cá nhân (ví dụ các bản ghi sức khỏe,các báo cáo
tài chính, thông tin các nhân) bằng cách đánh cắp trên server DBMS;tại đây, CryptDB ngăn chặn DBA tìm ra dữ
liệu cá nhân. Mối đe dọa thứ hai là một kẻ tấn công đạt được quyền điều khiển hoàn toàn ứng dụng và các
server DBMS. Trong trường hợp này, CryptDB không thể cung cấp bất cứ đảm bảo nào cho những người dùng
đã đăng nhập vào ứng dụng trong khi tấn công đang xảy ra, nhưng vẫn có thể đảm bảo bí mật dữ liệu cho những
người dùng đã đăng xuất.
Có hai thách thức trong cuộc chiến chống lại những mối đe dọa này. Thách thức đầu tiên là sức ép giữa việc tối
giản hóa thông tin bí mật được tiết lộ cho server DBMS và khả năng thực thi có hiệu quả một loạt các truy vấn.
Các phương pháp tiếp cận hiện tại để tính toán trên dữ liệu mã hóa hoặc là quá chậm hoặc là không cung cấp đủ

tính bí mật, như chúng ta thảo luận trong phần 9. Mặt khác, việc mã hoa dữ liệu với một hệ thống mã hóa mạnh,
như AES, sẽ ngăn chặn server DBMS thực hiện nhiều truy vấn SQL, như những truy vấn số lượng nhân viên
trong bộ phận “sales” hoặc tên của các nhân viên có số lương lớn hơn $60,000. Trong trường hợp này, giải pháp
thực tế duy nhất sẽ là để cho server DBMS truy cập tới key mã hóa, nhưng điều đó cũng sẽ cho phép kẻ xấu đạt
được truy cập tới toàn bộ dữ liệu.
Thách thức thứ hai là tối thiểu dữ liệu bị rò rỉ khi kẻ xấu thỏa hiệp được server ứng dụng cùng với server
DBMS. Vì việc tính toán tùy ý trên dữ liệu mã hóa là không thực tế, ứng dụng phải có khả năng truy cập dữ liệu
đã được giải mã. Do đó khó khăn là đảm bảo rằng một ứng dụng đã bị thỏa hiệp có thể thu được chỉ một lượng
giới hạn dữ liệu đã được giải mã. Giải pháp gán cho mỗi người dùng một key mã hóa cơ sở dữ liệu khác nhau
cho dữ liệu của họ không thực hiện được cho những ứng dụng với dữ liệu chia sẻ, như các trang web bảng tin
và hội nghị.
CryptDB giải quyết những thách thức này bằng ba ý tưởng chính:


•

•

•

Đầu tiên là thực thi các truy vấn SQL trên dữ liệu mã hóa. CryptDB thực hiện ý tưởng này bằng cách sử
dụng một chiến lược mã hóa nhận biết SQL (SQL-aware encryption strategy) tận dụng thực tế rằng tất
cả truy vấn SQL được tạo thành từ một tập xác định các toán tử nguyên thủy, như là kiểm tra đẳng thứcequality check, so sánh thứ tự-oder comparison, tính tổng- aggregates (sums) , và kết hợp-join. Bằng
cách sửa lại cho phù hợp các lược đồ mã hóa đã biết (cho equality, additions, và odder checks) và sử
dụng một phương pháp mã hóa bảo quản riêng tư (privacy-pereserving) cho joins, CryptDB mã hóa mỗi
mục dữ liệu theo cách mà cho phép DBMS thực thi trên dữ liệu chuyển đổi. CryptDB hiệu quả bởi nó
chủ yếu sử dụng mã hóa đối xứng, tránh mã hóa đồng cấu đầy đủ (fully homomorphic encryption), và
chạy trên phần mềm DBMS không chỉnh sửa (bằng cách sử dụng các hàm chức năng người dùng định
nghĩa).
Kỹ thuật thứ hai là điều chỉnh mã hóa dựa trên truy vấn (adjustable query-based encryption). Một vài

lược đồ mã hóa làm rò rỉ thông tin về dữ liệu cho server DBMS nhiều hơn một số khác, nhưng được
yêu cầu xử lý các truy vấn nhất định. Để tránh tiết lộ tất cả mã hóa có thể của dữ liệu cho DBMS từ
trước đó (a priori), CryptDB cẩn thận điều chỉnh lược đồ má hóa nhận biết SQL (SQL-aware
encryption scheme) cho bất kỳ mục dữ liệu đã cho nào, tùy thuộc vào các truy vấn quan sát được trong
lúc chạy. Để thực hiện những điều chỉnh này một cách hiệu quả, CryptDB sử dụng onions of encryption.
Onions là một cách mới để lưu trữ một cách chặt chẽ nhiều bản mã trong mỗi onion khác trong cơ sở dữ
liệu để tránh chi phí trong việc mã hóa lại (re-encryptions).
Ý tưởng thứ ba là xâu chuỗi các key mã hóa với các mật khẩu người dùng, để mỗi mục dữ liệu trong cơ
sở dữ liệu chỉ có thể được giải mã thông qua một chuỗi của các key bắt nguồn từ mật khẩu của một
trong số những người dùng truy cập vào dữ liệu đó. Kết quả là nếu người dùng không đăng nhập vào
ứng dụng, và nếu kẻ xấu không biết mật khẩu của người dùng, kẻ xấu không thể giải mã dữ liệu của
người dùng, kể cả khi server DBMS và server ứng dụng bị thỏa hiệp hoàn toàn. Để xây dựng một chuỗi
của các key mà bắt (captures) dữ liệu riêng tư của ứng dụng và chính sách chia sẻ, CryptDB cho phép
nhà phát triển cung cáp các ghi chú chính sách trên giản đồ SQL của ứng dụng, chỉ rõ người dùng nào
(hoặc những principal khác, như các group chẳng hạn) có quyền truy cập tới từng mục dữ liệu.

Chúng tôi đã thực hiện CryptDB trên cả MySQL và Postgres; thiết kế của chúng tôi và hầu hết những thực hiện
của chúng tôi có thể áp dụng được với hầu hết các hệ quản trị cơ sơ dữ liệu SQL tiêu chuẩn. Phân tích một cuộc
theo dõi 10 ngày của 126 triệu truy vấn SQL từ nhiều ứng dụng tại MIT cho thấy rằng CryptDB có thể hỗ trợ
99.5% các phép toán (operations) trên dữ liệu mã hóa của 128,840 cột (colums) được thấy trong cuộc theo dõi.
Đánh giá của chúng tôi cho thấy rằng CryptDB có chi phí thấp, giảm 14.5% thông lượng (throughput) cho ứng
dụng phpBB web forum, và giảm 26% cho các truy vấn từ TPC-C, so với unmodified MySQL. Chúng tôi đã
đánh giá độ an toàn của CryptDB trên sáu ứng dụng thực( bao gồm phpBB, phần mềm quản lý hội nghị
HotCRP [27], và ứng dụng hồ sơ y tế OpenEMR); kết quả cho thấy rằng CryptDB bảo vệ hầu hết các trường
nhạy cảm với các lược đồ mã hóa bảo mật cao. Việc xâu chuỗi các key mã hóa với các mật khẩu người dùng
yêu cầu 11-13 chú thích giản lược độc nhất (unique schema anntotations) để thực thi các chính sách bảo mật
trên hơn 20 trường nhạy cảm (bao gồm một chính sách mới trong HotCRP for handling papers in conflict with a
PC chair) và 2-7 dòng mã nguồn thay đổi cho ba ứng dụng web nhiều người dùng.
Phần còn lại của tài liệu này được xây dựng như sau. Trong phần 2, chúng ta sẽ thảo luận chi tiết hơn các nguy
cơ mà CryptDB chống lại. Sau đó, chúng tôi sẽ mô tả thiết kế của CryptDB cho việc xử lý truy vấn mã hóa

trong phần 3 và cho quá trình xâu chuỗi key với mật khẩu người dùng trong phần 4. Trong phần 5, chúng tôi
trình bày một số case studies về cách các ứng dụng có thể sử dụng CryptDB, và trong phần 6, chúng tôi thảo
luận về những hạn chế của thiết kế của chúng tôi, và cách mà nó có thể mở rộng. Tiếp theo, chúng tôi miêu tả
những thực hiện nguyên mẫu của chúng tôi trong phần 7, và đánh giá hiệu quả và độ an toàn của CryptDB,


cũng như các nỗ lực cần thiết cho các nhà phát triển ứng dụng để sử dụng CryptDB, trong phần 8. Chúng tôi so
sánh CryptDB với công việc liên quan trong phần 9 và kết luận trong phần 10.

2.Security Overview
Hình 1 cho thấy kiến trúc của CryptDB và các mô hình de dọa. CryptDB làm việc bằng cách chặn lại tất cả truy
vấn SQL tại một database proxy, ở đó các truy vấn được viết lại để thực thi trên dữ liệu mã hóa (CryptDB coi
như tất cả các truy vấn đi qua proxy). Proxy mã hóa và giải mã tất cả dữ liệu, và thay đổi một vài toán tử truy
vấn, nhưng vấn đảm bảo ngữ nghĩa của truy vấn. DBMS server không bao giờ nhận được các key giải mã ở
dạng plaintext vì thế nó ko bao giờ thấy được dữ liệu nhạy cảm, đảm bảo rằng những DBA tò mò không thể
truy cập tới thông tin cá nhân (mối de dọa thứ nhất).
Để bảo vệ chống lại ứng dụng, proxy, và DBMS server thỏa hiệp (mối đe dọa thứ hai), các nhà phát triển chú
thích giản đồ SQL của họ (annotate their SQL schema) để xác định những người ủy quyền (principals) khác,
các key của những người đó sẽ cho phép giải mã các phần khác nhau của cơ sở dữ liệu. chúng cũng tạo một sự
thay đổi nhỏ tới các ứng dụng của chúng để cung cấp các key mã hóa cho proxy, điều này được mô tả trong
phần 4. Proxy xác định những phần nào của cơ sở dữ liệu nên được mã hóa bằng key nào. Kết quả là CryptDB
đảm bảo tính bí mật của dữ liệu thuộc về những người dùng không đăng nhập trong khi bị thỏa hiệp (ví dụ: user
2 trong Hình 1), và những ai không đăng nhập cho tới khi sự thỏa hiệp bị phát hiện và sửa chữa bởi người quản
trị.
Mặc dù CryptDB bảo vệ tính bí mật của dữ liệu, nó không đảm bảo tính toàn vẹn, tính mới, hay đầy đủ của kết
quả được trả về cho ứng dụng. Một kẻ xấu mà thỏa hiệp ứng dụng, proxy, hay DBMS server, hoặc một DBA
xấu, có thể xóa bất kỳ hoặc tất cả dữ liệu được lưu trữ trên cơ sở dữ liệu. Tương tự, tấn công vào máy của người
dùng, như cross-site scripting chẳng hạn, là nằm bên ngoài phạm vi của CryptDB.
Bây giờ chúng tôi sẽ miêu tả hai mô hình mối đe dọa được giải quyết bởi CryptDB và những đảm bảo an ninh
được cung cấp dưới những mô hình mối đe dọa đó.


2.1.Mối đe dọa thứ nhất: Thỏa hiệp DBMS Server - DBMS Server
Compromise
Trong mối đe dọa này, CryptDB bảo vệ chống lại một DBA tò mò hoặc kẻ tấn công bên ngoài khác với truy cập
hoàn toàn tới dữ liệu được lưu trên DBMS server. Mục tiêu của chúng ta là tính bí mật, không phải tính toàn
vẹn hay sẵn sàng. Giả sử kẻ tấn công là bị động (passive): hắn muốn tìm hiều dữ liệu bí mật, nhưng không thay
đổi các truy vấn được sinh ra bởi ứng dụng, các kết quả truy vấn, hay dữ liệu trong DBMS. Mối đe dọa này bao
gồm các thỏa hiệp phần mềm DBMS, truy cập root tới các máy DBMS, và kể cả truy cập tới RAM của máy vật
lý. Với sự gia tăng trong việc thống nhất cơ sở dữ liệu bên trong các trung tậm dữ liệu doanh nghiệp, lưu trữ các
cơ sở dữ liệu trên cơ sở hạ tầng điện toán đám mây công cộng, và sử dụng các DBA của bên thứ ba, mối đe dọa
này đang ngày càng trở nên quan trọng.
Tiếp cận. CryptDB nhằm mục đích bảo vệ tính bí mật của dữ liệu chống lại mối đe dọa này bằng cách thực thi
các truy vấn SQL trên dữ liệu mã hóa trên DBMS server. Proxy sử dụng các key bí mật để mã hóa toàn bộ dữ
liệu được thêm vào hoặc được bao gồm trong các truy vấn được sinh ra cho DBMS. Hướng tiếp cận của chúng
tôi là cho phép DBMS server thực hiện việc xử lý truy vấn trên dữ liệu mã hóa như là nó thực hiện trên một cơ
sở dữ liệu không mã hóa, bằng cách cho phép nó tính toán các hàm nhất định trên các mục dữ liệu dựa trên dữ
liệu mã hóa. Ví dụ, nếu DBMS cần thực hiện một GROUP BY trên cột c, DBMS server sẽ có thể xác định các


mục nào trong cột đó đều bình đẳng với nhau, nhưng không phải nội dung thực tế của mỗi mục. Do đó, proxy
cần phải kích hoạt DBMS server để xác định các mỗi quan hệ giữa dữ liệu cần thiết để xử lý một truy vấn. Bằng
cách sử dụng mã hóa nhận biết SQL (SQL-aware encryption) điều chỉnh tự động các truy vấn được đưa ra,
CryptDB cẩn thận xem xét những quan hệ nào nó tiết lộ giữa các bộ dữ liệu tới server. Ví dụ, nếu DBMS cần
thực hiện chỉ một GROUP BY trên một cột c, DBMS server không nên biết thứ tự của các mục trong cột c,
cũng như không nên biết bất kỳ thông tin nào khác về các cột khác. Nếu DBMS được yêu cầu thực hiện một
ORDER BY, hoặc tìm MAX hoặc MIN, CryptDB tiết lộ thứ tự của các mục trong cột đó, chứ không phải cột nào
khác.
Sự bảo đảm. CryptDB cung cấp tính bí mật cho nội dung dữ liệu và cho các tên của các cột và các bảng;
CryptDB không che giấu cấu trúc bảng tổng thể, số hàng, các loại của các cột, hay kích thước của dữ liệu theo
byte. Sự an toàn của CryptDB là không hoàn hảo: CryptDB tiết lộ cho DBMS server các mỗi quan hệ giữa các

mục dữ liệu tương ứng với các lớp tính toán (classes of computation) mà các truy vấn thực hiện trên cơ sở dữ
liệu, chẳng hạn như so sánh các mục có ngang bằng nhau không (comparing item for equality), sắp xếp, hoặc
thực hiện tìm kiếm từ. Granularity (Granularity là mức độ mà một bộ dữ liệu hay thông tin lớn, phức tạp được
chia ra thành các đơn vị nhỏ hơn) tại CryptDB nào cho phép DBMS thực hiện một lớp các tính toán là toàn bộ
một cột (hoặc một nhóm của các cột được join với nhau), có nghĩa là ngay cả khi một truy vấn yêu càu các kiểm
tra bằng (equality checks) cho một vài hàng, việc thực thi truy vấn đó trên server sẽ yêu cầu việc tiết lộ lớp tính
toán đó (that class of computation) cho cả một cột. Phần 3.1 miêu tả cách mà các lớp tính toán map với các lược
đồ mã hóa của CryptDB, và những thông tin chúng tiết lộ.
CryptDB cung cấp các tính chất sau:
•
•

•

Dữ liệu nhạy cảm không bao giờ tồn tại dưới dạng rõ trên DBMS server.
Thông tin bị lộ cho DBMS server phụ thuộc và các lớp tính toán được yêu cầu bởi các truy vấn của ứng
dụng, tùy theo những ràng buộc mà nhà phát triển ứng dụng chỉ ra trong lược đồ (phần 3.5.1):
o Nếu ứng dụng không yêu cầu bộ lọc vị từ quan hệ (relational predicate filtering) trên một cột,
không gì về nội dung dữ liệu nào bị rò rỉ (trừ kích thước của nó tính theo byte).
o Nếu ứng dụng yêu cầu equality checks trên một cột, proxy của CryptDB tiết lộ những mục lặp lại
trong cột đó (biểu đồ tần suất – the histogram), nhưng không phải là các giá trị thực tế.
o Nếu ưng dụng yêu cầu order checks trên một cột, proxy tiết lộ thư tự của các phần tử trong cột.
DBMS server không thể tính toán kết quả (được mã hóa) cho các truy vấn liên đến các lớp tính toán mà
không được ứng dụng yêu cầu.

CryptDB “tối ưu” an ninh như thế nào? Về cơ bản, tối ưu an ninh đạt được bằng các công việc gần đây trong lý
thuyết mật mã cho phép bất kì tính toán toàn trên dữ liệu mã hóa [18]; tuy nhiên, những đề xuất như vậy không
thực tế. Ngược lại, CryptDB là thực tế, và trong phần 8.3, chúng tôi sẽ chứng minh rằng nó cũng cung cấp
những bảo mật quan trọng trong thực tế. Cụ thể, chúng tôi sẽ cho chỉ ra rằng tất cả hoặc hầu như tất cả các
trường nhạy cảm nhất trong các ứng dụng thử nghiệm vẫn được mã hóa với các lược đồ mã hóa bảo mật cao.

Đối với các trường như vậy, CryptDB cung cấp tối ưu an ninh, giả sử giá trị của chúng độc lập với mô hình mà
trong đó chúng được truy cập (trường hợp với các thông tin y tế, số an sinh xã hội, vv…). CryptDB không tối
ưu cho các trường đòi hỏi tiết lộ nhiều hơn các lược đồ mã hóa (encryption shemes), nhưng chúng tôi tìm ra
rằng hầu hết các trường như vậy là bán nhạy cảm (semi-sensitive) (như nhãn thời gian-timestamp chẳng hạn).
Cuối cùng, chúng tôi tin rằng một mô hình tấn công bị động là thực tế vì các DBAs xấu có nhiều khả năng đọc
dữ liệu, có thể khó phát hiện, hơn là thay đổi dữ liệu hoặc các kết quả truy vấn, mà có nhiều khả năng được
khám phá. Trong phần 9, chúng tôi trích dẫn công việc liên quan đến toàn vẹn dữ liệu mà có thể được sử dụng


trong việc bổ sung với công việc của chúng tôi. Một kẻ xấu có thể chèn hoặc cập nhật dữ liệu có thể gián tiếp
thỏa hiệp bảo mật. Ví dụ, một kẻ xấu thay đổi một trường email trong cơ sở dữ liệu có thể có khả năng lừa ứng
dụng gửi một dữ liệu của người dùng tới một địa chỉ email sai, khi người dùng yêu cầu ứng dụng gửi email cho
cố ấy một bản sao dữ liệu của chính mình . Các cuộc tấn công chủ động như vậy trên DBMS thuộc mô hình đe
dọa thứ hai, và chúng ta sẽ thảo luận bây giờ.

2.2.Mối đe dọa thứ hai: Các mối đe dọa tùy ý - Arbitrary Threats
Bây giờ chúng tôi sẽ miêu tả mỗi đe dọa thứ hai khi các cơ sở hạ tầng server ứng dụng, proxy, và DBMS server
có thể bị thỏa hiệp tùy ý. Cách tiếp cận trong mối đe dọa thứ nhất là không đủ vì kẻ xấu bây giờ có thể đạt được
truy cập tới các key được sử dụng để mã hóa toàn bộ cơ sở dữ liệu.
Giải pháp là mã hóa các mục dữ liệu khác nhau (ví dụ, dữ liệu thuộc về các user khác nhau) với các key khác
nhau. Để xác định key nào được sử dụng cho mỗi mục dữ liệu, các nhà phát triển chú thích giản đồ cơ sử dữ
liệu của ứng dụng để thể hiện các chính sách bảo mật tốt hơn. Một DBA tò mò vẫn không thể có được dữ liệu
cá nhân bằng cách đánh cắp trên DBMS serve (mối đe dọa thứ nhất), và thêm vào đó, kẻ xấu thỏa hiệp server
ứng dụng hoặc proxy bây giờ có thể giải mã chỉ dữ liệu của những user đang đăng nhập (những dữ liệu đó
được lưu trữ trong proxy). Dữ liệu của những người hiện tại không hoạt động sẽ được mã hóa với các key mà
kẻ xấu không biết, và sẽ được giữ bí mật.
Trong dạng này, CryptDB cung cấp những đảm bảo mạnh khi đối mặt với các thỏa hiệp tùy ý phía server, bao
gồm cả những người đạt được truy cập root tới ứng dụng hay proxy. CryptDB rò rỉ các dữ liệu của người dùng
đang hoạt động trong suốt thời gian bị thỏa hiệp. “trong suốt thời gian bị thỏa hiệp” nghĩa là khoảng thời gian từ
khi bắt đầu của thỏa hiệp cho đến khi bất kỳ dấu viết của thỏa hiệp nào được xóa khỏi hệ thống. Với một tấn

công SQL injection thực tế, khoảng thời gian thỏa hiệp là thời gian kẻ tấn công thực hiện các truy vấn SQL.
Trong ví dụ trên, khi kẻ xấu thay đổi địa chỉ email của một user trong cơ sở dữ liệu, chúng ta xem xét hệ thống
bị xâm nhập cho đến khi địa chỉ email của kẻ tấn công vẫn tồn tại trong cơ sở dữ liệu.

3.Các truy vấn trên dữ liệu mã hóa
Phần này miêu tả cách mà CryptDB thực thi các truy vấn SQL trên dữ liệu mã hóa. Mô hình mối đe dọa trong
phàn là là mối đe dọa thứ nhất từ phần 2.1. Các máy DMBS và những người quản trị không đáng tin cậy,
nhưng ứng dụng và proxy được tin cậy.
CryptDB cho phép DBMS server thực thi các truy vấn SQL trên dữ liệu mã hóa gần như giống với nó được thực
thi cùng các truy vấn trên dữ liệu rõ. Các ứng dụng có sẵn không cần thiết thay đổi. Kế hoạch truy vấn của
DMBS cho truy vấn mã hóa thường giống như đối với các truy vấn nguyên gốc, ngoại trừ các toán tử
(operators) bao gồm truy vấn, chẳng hạn như lựa chọn (selections), phép chiếu (projections), kết hợp (joins),
tập hợp (aggregates), và xếp thứ tự (ordering), được thực hiện trên bản mã, và sử dụng các toán tử sửa đổi trong
một số trường hợp.
Proxy của CryptDB lưu trữ một secret master key MK, lược đồ cơ sở dữ liệu, và các lớp(layers) mã hóa hiện tại
của tất cả các cột. DBMS server thấy một lược đồ ẩn danh (trong tên bảng và tên cột nào được thay thế bởi các
định danh mờ - in which table and column names are replaced by opaque identifiers), dữ liệu người dùng mã
hóa, và một vài bảng phụ được CryptDB sử dụng. CryptDB cũng trang bị cho server với các chức năng người
dùng định nghĩa cụ thể (CryptDB-specific user-defined functions - UDFs) cho phép server tính toán trên các
bản mã cho các phép toán nhất định.


Việc xử lý một truy vấn trong CryptDB gồm 4 bước:
•

•

•
•


Ứng dụng sinh ra một truy vấn, proxy chặn lại và viết lại: để bảo vệ danh tính của các bảng và cột, nó tổ
chức lại mỗi tên bảng, tên cột, và , sử dụng master key MK, mã hóa mỗi hằng số (constant) trong truy
vấn với một lược đồ mã hóa phù hợp nhất cho phép toán (operation) mong muốn (phần 3.1).
Proxy kiểm tra xem liệu DBMS server có được đưa các key để điều chỉnh các lớp mã hóa trước khi thực
thi truy vấn, và nếu có, sinh ra một truy vấn UPDATE tại DBMS server để gọi một UDF để điều chỉnh
lớp mã hóa của các cột thích thợp (phần 3.2)
Proxy chuyển tiếp truy vấn được mã hóa đến DBMS server, nơi thực hiện nó sử dụng SQL tiêu chuẩn
(đôi khi gọi UDFs cho các hàm tập hợp (aggregation) hoặc tìm kiếm từ khóa).
DBMS server trả về kết quả truy vấn (được mã hóa), proxy sẽ giải mã và trả về cho ứng dụng.

3.1.SQL-aware Encryption
Bây giờ chúng ta sẽ mô tả các loại mã hóa mà CryptDB sử dụng, bao gồm một số các hệ mật hiện có, một tối ưu
hóa của một lược đồ gần đây, và một cơ sở mật mã (hoặc mật mã cơ sở - cryptographic primitive) mới cho các
kết hợp (joins). Với mỗi loại mã hóa, chúng tôi giải thích đặc điểm an toàn mà CryptDB yêu cầu từ nó, chức
năng của nó, và làm thế nào để nó được thực hiện.
Random (RND). RND cung cấp bảo mật tối đa trong CryptDB: an toàn ngữ nghĩa dưới một tấn công lựa chọn
bản rõ thích ứng (indistinguishability under an adaptive chosen-plaintext attack - IND-CPA)(tham khảo IND,
tham khảo CPA, tham khảo 2); lược đồ (scheme) là xác suất, có nghĩa là hai giá trị bằng nhau được ánh xạ tới
hai bản mã khác nhau với xác suất trội hơn (overwhelming probability). Mặt khác, RND không cho phép bất cứ
sự tính toán nào được thực hiện hiệu quả trên bản mã. Một cấu trúc hiệu quả của RND là sử dụng mã hóa khối
như AES hoặc Blowfish trong chế độ CBC với một vector khởi tạo ngẫu nhiên (IV). (chúng tôi hầu như sử dụng
AES, ngoại trừ các giá trị nguyên chúng tôi sử dụng Blowfish với kích thước khối là 64 bit vì khối 128 bit của
AES sẽ gây ra bản mã dài hơn đáng kể).
Kể từ đó, trong mô hình mối đe dọa này, CryptDB giả định server không thay đổi kết quả, CryptDB không yêu
cầu một cấu trúc IND-CCA2 (tham khảo CCA, tham khảo IND-CCA) mạnh mẽ hơn (ngăn chặn tấn công lựa
chọn bản mã). Tuy nhiên, nó sẽ được đơn giản hóa để sử dụng một thực hiện IND-CCA2 an toàn của RND thay
vào đó, như một mã hóa khối ở chế độ UFE [13], nếu cần thiết.
Tất định – Deterministic (DET) (“thuật toán” chia làm hai loại: thuật toán đơn định – Deterministic – là thuật
toán mà kết quả của mọi phép toán đều được xác định duy nhất; thuật toán không đơn định – NoDeterministic –
là thuật toán có ít nhất một phép toán mà kết quả của nó là không duy nhất). DET có một đảm bảo hơn yếu hơn,

nhưng nó vẫn cung cấp bảo mật mạnh mẽ: nó chỉ rò rỉ các giá trị mã hóa tương ứng với giá trị cùng một dữ liệu,
bằng cách sinh ra cùng bản mã cho cùng bản rõ. Lớp mã hóa này cho phép server thực hiện các kiểm tra bình
đẳng (equality checks), có nghĩa là nó có thể thực hiện các lựa chọn (selects) với equality predicates, equality
joins, GROUP BY,COUNT, DISTINCT,…
Trong giới hạn mật mã, DET phải là một phép hoán vị giả ngẫu nhiên (pseudo-random permutation – PRP –
tham khảo 1, tham khảo 2 hay còn gọi là Block ciphers) [20]. Với các giá trị 64 bit và 128 bit, chúng tôi sử dụng
một mã hóa khối với một kích thước khối phù hợp (Blowfish và AES tương ứng); chúng tôi tạo ra giả định
thông thường rằng thuật toán má hóa khối AES và Blowfish là PRPs. Chúng tôi đệm các giá trị nhỏ hơn 64 bít,
nhứng với dữ liệu dài hơn một khối AES 128 bit, chế độ CBC tiêu chuẩn của phép toán rò rỉ tiền tố bằng nhau
(ví dụ, nếu hai mục dữ liệu có một tiền tố giống hệt nhau dài ít nhất 128 bit). Để tránh ván đề này, chúng tôi sử
dụng AES với biến thể của chế độ CMC [24], có thể gần như coi là một vòng (round) của CBC, theo sau các


vòng khác của CBC với các khối theo thứ tự ngược lại. Vì mục tiêu của DET là để reveal equality, chúng tôi sử
dụng một zero IV (hoặc “tinh chỉnh – tweak” [24]) cho sự thực hiện AES-CMC của DET.
Mã hóa duy trì thứ tự - Order-preserving encryption (OPE) (tham khảo1, tham khảo 2). OPE cho phép
quan hệ thứ tự giữa các mục dữ liệu được thiết lập dựa theo các giá trị mã hóa của chúng, mà không tiết lộ dữ
liệu của chính nó. Nếu x < y, thì OPEK(x) < OPEK(y), cho bất cứ key bí mật K nào. Vì thế, nếu một cột được mã
hóa với OPE, server có thể thực hiện nhiều truy vấn khi các hằng số được mã hóa đã cho OPEK(c1) và OPEK(c2)
tương ứng với khoảng [c1, c2]. Server cũng có thể thực hiện ORDER BY, MIN, MAX, SORT, vv…
OPE là một mô hình mã hóa yếu hơn DET vì nó hiển thị thứ tự. Do đó, CryptDB proxy sẽ chỉ hiển thị các cột
được mã hóa OPE cho server nếu những người dùng yêu cầu thứ tự các truy vấn trên các cột đó. OPE có các
đảm bảo an toàn chứng minh được [4]: mã hóa tương đương với một ánh xạ ngẫu nhiên mà giữ theo thứ tự.
Mô hình chúng tôi sử dụng [4] là một mô hình an toàn có thể chứng minh được đầu tiên. Cho đến khi CryptDB
xuất hiện, không có thực hiện cũng như biện pháp thực tiến nào của mô hình. Việc thực hiện trực tiếp của mô
hình này mất 25 ms trên mỗi mã hóa của một số nguyên 32 bít trên một bộ xử lý Intel 2.8 GHz Q9550. Chúng
tôi cải tiến thuật toán bằng cách sử dụng cây tìm kiếm nhị phân AVL để mã hóa hàng loạt (ví dụ, các tải cơ sở
dữ liệu – database loads), giảm thiểu chi phí của má hóa OPE đến 7 ms trên mỗi mã hóa mà không làm ảnh
hưởng tới an toàn của nó. Chúng tôi cũng thực hiện một hypergeometric sampler mà nằm trong lõi của OPE,
porting a Fortran implementation from 1988 [25].

Mã hóa đồng cấu - Homomorphic encryption (HOM) (tham khảo 1, tham khảo 2, tham khảo 3). HOM là
một lược đồ mã hóa xác suất an toàn (IND-CPA-secure), cho phép server thực hiện các tính toán trên dữ liệu mã
hóa với kết quả cuối dùng được giải mã tại proxy. Trong khi mã hóa đồng cấu đầy đủ phục vụ chậm [10], mã
hóa đồng cấu cho các phép toán cụ thể là hiệu quả. Để hỗ trợ tổng kết, chúng tôi đã thực hiện hệ mật Paillier
[35]. Với Paillier,việc nhân các mã hóa của hai giá trị dẫn tới kết quả trong một mã hóa của tổng các giá trị, ví
dụ, HOMK(x) * HOMK(y) = HOMK(x + y), phép nhân được thực hiện theo modulo một vài giá trị khóa công
khai. Để tính tổng SUM (SUM aggregates), proxy thay thế SUM với các lời gọi tớ một UDF mà thực hiện phép
nhân Paillier trên một cột được mã hóa với HOM. HOM cũng có thể được sử dụng để tính toán giá trị trung
bình bằng cách DBMS server trả về giá trị tổng (sum) và đếm (count) riêng biệt, và cho việc tăng các giá trị. (ví
dụ, SET id=id+1) , mà chúng tôi xây dựng ngay (on wich we elaborate shortly).
Với HOM, bản mã là 2048 bít. Theo lý thuyết, nó có thể đóng gói nhiều giá trị từ một hàng đơn lẻ vào một bản
mã HOM cho hàng đó, sử dụng lược đồ của Ge và Zdonik [17], dấn tới kết quả là một khoảng trống khấu hao
gấp đôi (ví dụ một giá trị 32 bit chiếm 64 bit) cho một bảng với nhiều cột được mã hóa HOM. Tuy nhiên, chúng
tôi đã không thực hiện tối ưu hóa này trong mẫu thử nghiệm của chúng tôi. Sự tối ưu hóa này cũng sẽ làm phức
tạp các phép toán UPDATE hàng cục bộ (This optimization would also complicate partial-row UPDATE
operations) mà thiết lập lại một số - nhưng không phải là tất cả - các giá trị được đóng gói vào một bản mã
HOM.
Join (JOIN and OPE-JOIN). Một lược đồ mã hóa riêng là cần thiết để cho phép các equality join giữa hai cột,
vì chúng tôi sử dụng các key khác nhau cho DET để ngăn chặn các mối tương quan giữa các cột. JOIN cũng hỗ
trợ tất cả các phép toán được DET cho phép, và cũng cho phép server xác định những giá trị nhắc lại giữa hai
cột. OPE-JOIN cho phép tham gia theo các mối liên hệ thứ tự (OPE-JOIN enables joins by order relations).
Chúng tôi cung cấp một lược đồ mã hóa mới cho JOIN và chúng ta sẽ thảo luận về nó ở phần 3.4.


Hình 2: Các lớp mã hóa Onion và các lớp tính toán chúng cho phép (Onion encryption layers and the classes of
computation they allow). Các tên Onion viết tắt cho các phép toán chúng cho phép tại một vài lớp của chúng
(Equality, Order, Search, và Addition). Trong thực tế, một vài onion hoặc các lớp onion có thể bỏ qua, phụ
thuộc vào loại cột hoặc những chú giải lược đồ(schema annotations) được cung cấp bởi các nhà phát triển ứng
dụng (phần 3.5.2). DET và JOIN thường kết hợp trong một lớp onion đơn lẻ, vì JOIN là một sự nối tiếp cua
DET và JOIN-ADJ (phần 3.4). Một IV ngẫu nhiên cho RND (3.1), được chia sẻ bởi các lớp RND là Eq và Ord,

cũng được lưu trữ cho từng mục dữ liệu.
Word search (SEARCH). SEARCH được sử dụng để thực hiện các tìm kiếm trên văn bản được mã hóa để hỗ
trợ các phép toán như LIKE của MySQL chẳng hạn. Chúng tôi đã thực hiện giao thức mã hóa của Song và các
đồng nghiệp của ông [46], mà trc đây họ không thực hiện; chúng tôi cũng sử dụng giao thức của họ theo một
cách khác, dẫn tới kết quả là một đảm bảo an toàn tốt hơn. Cho mỗi cột cần SEARCH, chúng tôi chia văn bản
thành các từ khóa sử dụng các ký tự phân cách tiêu chuẩn (hoặc sử dụng một chức năng khai thác từ khóa đặc
biệt được quy định bởi người phát triển lược đồ). Sau đó chúng tôi loại bỏ những gì lặp lại trong những từ này,
hoán vị ngẫu nhiên vị trí của các từ, và rồi mã hóa mỗi từ sử dụng lược đồ của Song, đệm (padding) mỗi từ cho
cùng kích thước. SEARCH an toàn gần như RND: má hóa ko để lộ cho DBMS server có một từ nào đó lặp đi
lặp lại trong nhiều hàng, nhưng nó rò rỉ số lượng từ khóa được mã hóa với SEARCH; kẻ xấu có thể ước lượng
số lượng các từ riêng biệt hoặc trùng lặp (ví dụ, bằng cách so sánh kích thước của bản mã SEARCH và RND
với cùng dữ liệu).
Khi người dùng thực hiện một truy vấn như SELECT * FROM messages WHERE msg LIKE "% alice %"
chẳng hạn, proxy đưa cho DBMS server một token, là một mã hóa của alice. Server không thể giải mã token
để tìm ra từ cơ bản (underlying word). Sử dụng một hàm người dùng định nghĩa, DBMS server kiểm tra xem
bất cứ các mã hóa từ trong bất cứ thông điệp nào có phù hợp với token hay không. Trong cách tiếp cận của
chúng tôi, tất cả server sẽ tìm hiểu từ việc tìm kiếm xem liệu một token có phù hợp (matched) với một thông
điệp hay không, và điều này chỉ xảy ra đối với các token được người dùng yêu cầu. Server không tìm hiểu
những thông tin tương tự khi trả về tập kết quả thiếp những người dùng, do đó các lược đồ tìm kiếm tổng thể để
lộ ra ít thông tin cần thiết nhất để trả về kết quả.
Chú ý răng SEARCH cho phép CryptDB chỉ thực hiện các tìm kiếm từ khóa đầy đủ từ (full-word keyword
searches); nó không thể hỗ trợ các biểu thức chính quy tùy ý. Cho các ứng dụng yêu cầu tìm kiếm nhiều từ liền
kề, CryptDB cho phép nhà phát triển ứng dụng vô hiệu hóa loại bỏ trùng lặp và sắp xếp lại bằng cách chú giải
lược đồ(annotating the schema), mặc dù đây không phải là mặc định.


3.2.Adjustable Query-based Encryption
Một phần quan trọng của thiết kế của CryptDB là adjustable query-based encryption, tự động điều chỉnh lớp mã
hóa trên DBMS server. Mục đích của chúng tôi là sử dụng các lược đồ mã hóa an toàn nhất mà có thể chạy các
truy vấn được yêu cầu. Ví dụ, nếu ứng dụng không sinh ra truy vấn nào so sánh các mục dữ liệu trong một cột,

hoặc sắp xếp cột, cột phải được mã hóa với RND. Đối với những cột yêu cầu các equality check nhưng không
yêu cầu inequality check, DET cũng đủ. Tuy nhiên, tập truy vấn không phải lúc nào cũng được biết trước. Do
đó, chúng ta cần một lược đồ có khả năng thích ứng mà tự động điều chỉnh các chiến lược mã hóa.
Ý tưởng của chúng tôi là mã hóa từng mục dữ liệu trong một hoặc nhiều onion: tức là, mỗi giá trị sẽ được bọc
trong các lớp mã hóa ngày càng mạnh hơn, như minh họa trong hình 2 và 3. Mỗi lớp của mỗi onion cho phép
mỗi loại chức năng như được giải thích trong tiểu mục trước. Ví dụ, các lớp ngoài cùng như RND và HOM
cung cấp bảo mật tối đa, trong khi các lớp bên trong như OPE cung cấp nhiều chức năng hơn.
Trong thực tế cần nhiều onion, vì các phép toán được hỗ trợ bởi các lược đồ mã hóa khác nhau không luôn luôn
theo thứ tự một cách hoàn toàn, và vì cần phải cân nhắc hiệu suất thực hiện (kích thước của bản mã và thời gian
mã hóa cho các lớp onion lồng vào nhau). Phụ thuộc vào loại dữ liệu (và bất cứ chú thích (annotations) được
cung cấp bởi nhà phát triển ứng dụng trên lược đồ cơ sở dữ liệu, như được thảo luận trong phần 3.5.2),
CryptDB có thể không duy trì tất cả các onion cho mỗi cột. Ví dụ, Search onion không có ý nghĩa cho các số
nguyên (integers), và Add onion không có ý nghĩa cho các chuỗi (strings).
Với mỗi lớp của mỗi onion, proxy sử sử dụng cùng một key cho các giá trị đang mã hóa trong cùng một cột, và
các key khác nhau trên các bảng, các cột, các onion, và các lớp onion khác nhau. Việc sử dụng cùng một key
cho tất cả các giá trị trên một cột cho phép proxy thực hiện các phép toán trên một cột mà không phải tính toán
các key riêng biệt cho từng hàng mà sẽ được thao tác. (chúng tôi sử dụng các key mã hóa finer-grained trong
phần 4 để giảm khả năng tiềm ẩn dữ liệu bị tiết lộ trong trường hợp một ứng dụng haowcj proxy server bị thỏa
hiệp). Việc sử dụng các key khác nhau trên các cột ngăn chặn server tìm ra bất kỳ mối quan hệ thêm nào. Tất cả
những key này được bắt nguồn từ masterk key MK. Ví dụ, với bảng t, cột c, onion o, và lớp mã hóa l, proxy sử
dụng key
Kt,c,o,l = PRPMK(bảng t, cột c, onion o, lớp l),

(1)

với PRP là một hoán vị giả ngẫu nhiên – pseudo random permutation (ví dụ, AES)
Mỗi onion bắt đầu được mã hóa với lược đồ mã hóa an toàn nhất (RND cho onion Eq và Ord, HOM cho onion
Add, và SEARCH cho onion Search). Khi proxy nhận các truy vấn SQL từ ứng dụng, nó xác định xem các lớp
mã hóa nào cần được gỡ bỏ. Gán một vị từ (predicate) P trên cột c cần thiết để thực thi một truy vấn trên server,
proxy đầu tiên thiết lập lớp onion nào là cần thiết để tính toán P trên c. nếu mã hóa của c không phải là đã ở một

lớp onion mà cho phép P, proxy bóc tách các lớp onion để cho phép P trên c, bằng cách gửi key onion tương
ứng tới server. Proxy không bao giờ giải mã dữ liệu qua các lớp onion mã hóa kém an toàn (hoặc qua một vài
lớp mức khác, nếu được chỉ định bởi nhà phát triển ứng dụng trong lược đồ, 3.5.1).
CryptDB thực hiện việc giải mã lớp onion sử dụng UDFs chạy trên DBMS server. Ví dụ, trong hình 3, để giải
mã onion Ord của cột 2 trong bảng 1 tới lớp OPE, proxy sinh ra truy vấn sau tới server sử dụng
DECRYPT_RND UDF:
UPDATE Table1 SET
C2-Ord = DECRYPT_RND(K, C2-Ord, C2-IV)


với K là key phù hợp được tính toán từ phương trình (1). Tại cùng thời điểm, proxy cập nhật trạng thái bên
trong của chính nó để ghi nhớ rằng cột C2-Ord trong Table1 bây giờ đang ở lớp OPE trong DBMS. Mỗi giải mã
cột phải được bao gồm trong một giao dịch để tránh những vấn đề tính nhất quán với các client truy cập các cột
đang được điều chỉnh.

Hình 3:Bố trí dữ liệu tại máy chủ (Data layout at the server). Khi ứng dụng tạo bảng được hiển thị ở bên trái,
bảng được tạo tại DBMS server là một bảng được hiển thị ở bên phải. Bản mã được hiển thị là không đủ độ dài.
Chú ý rằng việc giải mã onion được thực hiện toàn bộ bởi DBMS server. Trong trạng thái ổn định, không giải
mã ở phía server nào là cần thiết, bởi vì việc giải mã onion xảy ra chỉ khi một lớp mới của tính toán được yêu
cầu trên một cột. Ví dụ, sau một equality check được yêu cầu trên một cột và server đưa cột đó vào lớp DET,
cột vẫn tồn tại trong trạng thái đó, và các truy vấn tương lai với các equality check không yêu cầu giải mã. This
property is the insight into why CryptDB’s overhead is modest in the steady state (see 8): the server mostly
performs typical SQL processing.

3.3. Thực thi trên dữ liệu mã hóa - Executing over Encrypted Data
Khi các lớp onion trên DBMS đang ở lớp cần thiết để thực thi một truy vấn, proxy biến đổi truy vấn để hoạt
động trên các onion này. Đặc biệt, proxy thay thế các tên cột trong một truy vấn với các tên onion tương ứng,
dựa trên lớp tính toán được thực hiện trên cột đó. Ví dụ, với lược đồ được thể hiện trong Hình 3, một tham
chiếu đến cột Name cho một equalyti comparison sẽ được thay thế với một tham chiếu tới cột C2-Eq.
Proxy cũng thay thế mỗi hằng số trong truy vấn với mã hóa onion tương ứng của hằng số đó, dựa trên các tính

toán trong đó nó được sử dụng. Ví dụ, nếu một truy vấn chứa WHERE Name = ‘Alice’, proxy mã hóa ‘Alice’
bằng cách áp dụng lần lượt tất cả các lớp mã hóa tương ứng với onion Eq mà vẫn chưa được loại bỏ khỏi C2Eq.
Cuối cùng, server thay thế các toán tử nhất định với các bản sao dựa trên hàm người dùng định nghĩa (UDFbased counterparts). Ví dụ, toán tử tính tổng SUM và toán tử cộng cột + phải được thay thế với một lời gọi của
một UDF mà thực hiện việc thêm HOM của các bản mã. Các toán tử đẳng thức và thứ tự (như = và < chẳng
hạn) không cần thiết thay thế như vậy và có thể được áp dụng trực tiếp vào các bản mã DET và OPE.
Khi proxy chuyển đổi truy vấn, nó gửi truy vấn tới DBMS server, nhận các kết quả truy vấn (bao gồm dữ liệu
mã hóa), giải mã các kết quả sử dụng các onion key tương ứng, và gửi kết quả giải mã cho ứng dụng.
Sự thực thi truy vấn đọc – Read query execution. Để hiểu sự thực thi truy vấn trên các bản mã, xem xét lược
đồ ví dụ trong Hình 3. Ban đầu, mỗi cột trong bảng được bọc trong tất cả các onion mã hóa, với RND, HOM, và
SEARCH là các lớp ngoài cùng, như trong Hình 2. Tại thời điểm này, server có không thể biết gì về dữ liệu
khác ngoài số cột, số hàng, và kích thước dữ liệu.
Để minh họa khi các lớp onion được gỡ bỏ, xem xét truy vấn:
SELECT ID FROM Employees WHERE Name = ‘Alice’,


mà yêu cầu giảm mã hóa của Name tới lớp DET. Để thực thi truy vấn này, proxy đầu tiên sinh ra truy vấn
UPDATE Table1 SET
C2-Eq = DECRYPT_RND(KT1,C2,Eq,RND, C2-Eq, C2-IV),

với cột C2 tương ứng với Name. Proxy sau đó sinh ra
SELECT C1-Eq, C1-IV FROM Table1 WHERE C2-Eq = x7..d,

Với cột C1 tương ứng với ID, và x7..d là mã hóa Eq onion của “Alice” với các key KT1,C2,Eq,JOIN và KT1,C2,Eq,DET
(xem Hình 2). Chú ý rằng proxy phải yêu càu IV ngẫu nhiên từ cột C1-IV để giải mã bản mã RND từ C1-Eq.
Cuối cùng, proxy giải mã các kết quả từ server sử dụng các key K T1;C1;Eq;RND, K T1;C1;Eq;DET, và K T1;C1;Eq;JOIN, thu
được kết quả 23, và trả nó về cho ứng dụng.
Nếu truy vấn tiếp theo là SELECT COUNT(*) FROM Employees WHERE Name = ‘Bob’, không cần thiết phải
giải mã ở phía server, và proxy trực tiếp sinh ra truy vấn SELECT COUNT(*) FROM Table2 WHERE C2-Eq =
xbb..4a, với xbb..4a là mã hóa Eq onion của “Bob” sử dụng K T1;C2;Eq;JOIN và K T1;C2;Eq;DET.
Sự thực thi truy vấn viết – Write query exexution. Để hỗ trợ các truy vấn INSERT, DELETE, và UPDATE,

proxy áp dụng cùng một xử lý cho các vị từ (vị ngữ - predicates) (ví dụ, mệnh đề WHERE) như cho các truy
vấn đọc. Các truy vấn DELETE không yêu cầu thêm tiến xử lý nào. Cho tất cả các truy vấn INSERT và
UPDATE mà thiết lập giá trị của một cột thành một hằng số (constant), proxy mã hóa từng giá trị của cột được
chèn vào với từng lớp onion mà vẫn chưa được gỡ bỏ trong cột đó.
Trường hợp còn lại là một UPDATE mà thiết lập một giá trị cột dựa vào một giá trị cột đang tồn tại, như
salary=salary+1 chẳng hạn. Một cập nhật như vậy phải được thực hiện sử dụng HOM, để xử lý bổ sung. Tuy
nhiên, làm như vậy, các giá trị trong các onion OPE và DET sẽ trở nên cũ. Thực tế, bất cứ lược đồ mã hóa giả
định nào (hypothetical encryption scheme) mà đồng thời cho phép bổ sung và so sánh trực tiếp trên bản mã là
không an toàn: nếu một server độc hại có thể tính toán thứ tự của các mục, và có thể tăng giá trị lên một, server
có thể liên tục thêm một vào mỗi trường (add one to each field homomorphically – homomorphically là một sự
chuyển đổi của một bộ sang một bộ khác mà vẫn giữ nguyên trong bộ thứ hai các phép toán giữa các thành viên
của bộ đầu tiên) cho đến khi nó trở nên bằng với một vài giá trị khác trong cùng một cột. Điều này sẽ cho phép
server tính toán sự khác nhau giữa hai giá trị trong cơ sở dữ liệu, mà gần như tương đương với các giá trị của
chúng đã biết.
Có hai cách tiếp cân để cho phép các cập nhật dựa trên các giá trị cột đang tồn tại. Nếu một cột được tăng lên và
sau đó chỉ được chiếu ra (projected) (không so sánh nào được thực hiện trên nó), giải pháp đơn giản: khi một
truy vấn yêu cầu giá trị của trường này, proxy phải yêu cầu bản mã HOM từ Add onion, thay vì các bản mã từ
các onion khác, vì giá trị HOM là mới nhất. Ví dụ, cách tiếp cận này áp dụng với các truy vấn tăng (increment
queries) trong TPC-C. Nếu một cột được sử dụng trong các so sánh sau khi nó được tăng lên, giải pháp là thay
thế truy vấn cập nhật với hai truy vấn: một SELECT của các giá trị cũ để được cập nhật, mà proxy tăng mà mã
hóa một cách phù hợp, tiếp theo là một UPDATE thiết lập các giá trị mới. Chiến lược này sẽ hoạt động tốt cho
các cập nhật mà ảnh hưởng đến một số lượng nhỏ các hàng.
Các đặc điểm DMBS khác – Other DBMS features. Hầu hết các cơ chế DMBS khác, như giao dịch
(transaction) và lập chỉ mục (indexing), hoạt động tương tự với CryptDB trên dữ liệu mã hóa như chúng làm
trên bản rõ, với không có sự thay đổi nào. Đối với các giao dịch (transactions), proxy gửi các bất kỳ truy vấn
BEGIN, COMMIT, và ABORT nào tới DBMS. Vì các toán tử SQL xử lý các giá trị NULL khác với các giá trị
không phải là NULL, CryptDB để lộ ra các giá trị NULL cho DBMS mà không mã hóa. CryptDB hiện tại


không hỗ trợ các thủ tục lưu trữ, mặc dù các thủ tục lưu trữ nhất định có thể được hỗ trợ bằng cách viết lại code

của chúng theo cùng cách mà proxy của CryptDB viết lại các câu lệnh SQL.
DBMS xây dựng các chỉ mục cho dữ liệu mã hóa theo cùng một cách như cho bản rõ. Hiện tại, nếu ứng dụng
yêu cầu một chỉ mục (index) trên một cột, proxy yêu cầu DBMS server xây dựng các chỉ mục trên các lớp DET,
JOIN, OPE, hoặc OPE-JOIN onion của cột đó (nếu chúng bị lộ), nhưng không cho RND, HOM, hoặc
SEARCH. Các thuật toán lựa chọn chỉ mục hiệu quả hơn có thể được điều tra.

3.4.Computing Joins
Có hai loại join được hỗ trợ bởi CryptDB: equi-joins, trong đó join predicate được dựa trên equality, và range
joins, trong đó liên quan đến các order check. Để thực hiện một equi-join của hai cột mã hóa, các cột phải được
mã hóa với cùng một key để server có thể tháy các giá trị khớp giữa hai cột. Tại cùng thời điểm, để cung cấp
bảo mật tốt hơn, DBMS server không được join cac cột mà ứng dụng không yêu cầu join, vì vậy các cột mà
không bao giờ được join không nên được mã hóa với cùng các key.
Nếu các truy vấn mà có thể được sinh ra, hoặc các cặp cột mà có thể được join, được biết từ trước đó (are
known a priori), equi-join rất dễ dàng để hỗ trợ: CryptDB có thể sử dụng mã hóa DET với cùng key cho mỗi
nhóm của các cột mà được join với nhau. Phần 3.5 mô tả cách mà proxy biết được các cột được join trong
trường hợp này. Tuy nhiên, trường hợp khó khăn là khi proxy không biết tập các cột được join từ trước đó (a
priori), và do đó không biết các cột nào phải được mã hóa với các key phù hợp.
Để giải quyết vấn đề này, chúng tôi giới thiệu một cơ sở mật mã mới, JOIN-ADJ (adjustable join), cho phép
DMBS server điều chỉnh key của từng cột tại thời điểm chạy. Bằng trực giác, JOIN-ADJ có thể được coi như là
một băm mật mã được bảo vệ bằng khóa (keyed cryptographic hash) (băm mật mã có khóa)với các đặc điểm bổ
sung mà các băm có thể được điều chỉnh để thay đổi key của chúng mà không cần truy cập tới bản rõ. JOINADJ là một chức năng xác định của các đầu vào của nó, có nghĩa là nếu hai bản rõ giống nhau, các giá trị JOINADJ tương ứng cũng bằng nhau. JOIN-ADJ chống được đụng độ (collision-resistant), và có chiều dài đầu ra đủ
dài (192 bít) để cho phép chúng ta thừa nhận rằng các đụng độ không bao giờ xảy ra trong thực tế.
JOIN-ADJ là không khả nghich (non-invertible), vì thế chúng ta định nghĩa lược đồ mã hóa JOIN là một chuỗi
kết nối JOIN(v) = JOIN-ADJ(v)||DET(v). cấu trúc này cho phép proxy giải mã một cột JOIN(v) để thu được v
bằng cách giải mã thành phần DET, và cho phép DBMS server kiểm tra hai giá trị JOIN có bằng nhau không
bằng cách so sánh các thành phần JOIN-ADJ.
Mỗi cột ban đầu được mã hóa tại lớp JOIN sử dụng key khác nhau, do đó ngăn chặn bất kỳ các join nào giữa
các cột. Khi một truy vấn yêu cầu một join, proxy đưa cho DBMS server một key onion để điều chỉnh các giá trị
JOIN-ADJ trong một hoặc hai cột, để nó phù hợp với JOIN-ADJ key của cột khác (được ký hiệu là cột joinbase). Sau khi điều chỉnh, các cột chia sẻ cùng một key JOIN-ADJ, cho phép DBMS server join chúng lại với
nhau. Các thành phần DET của JOIN vẫn được mã hóa với các key khác nhau.

Chú ý rằng join điều chỉnh được của chúng ta là bắc cầu:nếu người dùng join các cột A và B và rồi join cột B và
C, server có thể join A và C. Tuy nhiên, server không thể join các cột trong “các nhóm bắc cầu” khác nhau. Ví
dụ, nếu cột D và E được join với nhau, DBMS server không thể join cột A và D.
Sau một truy vấn join ban đầu, các giá trị JOIN-ADJ vẫn được chuyển đổi với cùng key, vì vậy không sự tái
điều chỉnh nào cần thiết cho các truy vấn join đến sau giữa cùng hai cột. Một ngoại lệ là nếu ứng dụng sinh ra
truy vấn khác, join một trong các cột đã được điều chỉnh với một cột thứ ba, sẽ khiến cho proxy điều chỉnh lại
cột sang một join-base khác. Để tránh những dao động (oscillations) và để hội tụ (converge) tại một trạng thái


mà tất cả các cột trong một nhóm bắc cầu chia sẻ cùng join-base, CryptDB chọn cột đầu tiên có tên theo thứ tự
từ điển trong bảng là join-base. Với n cột, số lượng tổng thế tối đa của các chuyển đổi join là n(n-1)/2.
Đối với các range join, một lược đồ tái điều chỉnh động tương tự là khó khăn để xây dựng do thiếu sót cấu truc
trong các lược đồ OPE. Thay vào đó, CryptDB yêu cầu cặp cột đó mà sẽ được liên hệ với nhau bằng các join
như vậy được ứng dụng khai báo trước, do đó các key phù hợp được sử dụng cho lớp OPE-JOIN của các cột đó;
nếu không, cùng một key sẽ được sử dụng cho tất cả các cột tại lớp OPE-JOIN. May mắn thay, các range join
hiếm khi xuất hiện; chúng không được sử dụng trong bất kỳ ứng dụng ví dụ nào của chúng tôi, và chỉ được sử
dụng 50 trong 128,840 cột trong cuộc theo dõi truy vấn SQL mà chúng tôi mô tả trong phần 8, tương ứng với
chỉ 3 ứng dụng riêng biệt.
JOIN-ADJ construction. Thuật toán của cúng tôi sử dụng mã hóa đường cong elliptic (elliptic-curve
cryptography - ECC). JOIN-ADJK(v) được tính toán như sau:

Với K là khóa khởi tạo cho bảng, cột, onion và lớp đó, P là một điểm trên một đường cong elliptic (là một tham
số public), và PRFK0 là một hàm giả ngấu nhiên (pseudo-random function) [20] ánh xạ các giá trị tới các số giả
ngẫu nhiên, như AESK0(SHA(v)) chẳng hạn, với K0 là một key mà là như nhau cho tất cả các cột và có nguồn
gốc từ MK. Các “lũy thừa” (“exponentiation”) thực tế là sự bổ sung các hình lặp đi lặp lại của các điểm đường
cong elliptic; nó nhanh hơn đáng kể so với lũy thừ RSA.
Khi một truy vấn join cột c và c’, mỗi khóa K và K’ tại lớp join, proxy tính toán ΔK = K/K’ (trong một nhóm
thích hợp) và gửi nó cho server. Sau đó JOIN-ADJK’(v) đã cho (các giá trị JOIN-ADJ từ cột c’) và ΔK, DBMS
server sử dụng một UDF để điều chỉnh key trong c’ bằng cách tính :


Bây giờ các cột c và c’ chia sẻ cùng JOIN-ADJ key, và DBMS có thể thực hiện một equi-join trên c và c’ bằng
cách lấy bộ phận JOIN-ADJ của JOIN onion cipertext.
Tại một mức cao hơn, an toàn của lược đồ này là server không thể suy ra các mối liên hệ join giữa các nhóm
của các cột mà không được yêu cầu bởi các truy vấn join hợp pháp, và lược đồ không để lộ bản rõ. Chúng tôi đã
chứng minh an toàn của lược đồ này dựa trên giả thiết chắc chắn Elliptic-Curve Decisional Diffie-Hellman tiêu
chuẩn, và đã thực hiện nó sử dụng NIST-approved elliptic curve. Chúng tôi dự định công bó một mô tả chi tiết
hơn về thuật toán này và bằng chứng trên website của chúng tôi [37].

3.5.Cải thiện độ an toàn và hiệu suất - Improving Security and Performance
Mặc dù CryptDB có thể hoạt động với một lược đồ không bị thay đổi và không được đánh dấu (an unmodified
and unannotated schema), như mô tả ở trên, an toàn và hiệu năng của nó có thể được nâng lên thông qua nhiều
tùy chọn tối ưu, như được mô tả dưới đây


3.5.1.Security Improvements
Các lớp onion tối thiểu - Minimum onion layers. Các nhà phát triển ứng dụng có thể chỉ rõ lớp mã hóa onion
thấp nhất mà có thể bị lộ cho server một cột cụ thể. Bằng cách này, nhà phát triển có thể đảm bảo rằng proxy sẽ
không thực thi các truy vấn lộ ra các mỗi liên hệ nhạy cảm với server. Ví dụ, nhà phát triển có thể chỉ rõ các số
thẻ tín dụng phải luôn luôn duy trì tại RND hoặc DET.
Xử lý trong proxy – In-proxy processing. Mặc dù CryptDB có thể ước lượng một số vị từ (predicates) trên
server, việc ước lượng chúng trong proxy có thể nâng cao an toàn bằng cách không để lộ các thông tin bổ sung
cho server. Một trường hợp phổ biến là truy vấn SELECT mà sắp xếp trên một trong các cột được chọn, mà
không có một LIMIT trên số cột được trả về. Vì proxy nhận một tập toàn bộ kết quả từ server, việc sắp xếp các
kết quả này trong proxy không yêu cầu một số lượng đáng kể các tính toán, và không tăng yêu cầu băng thông.
Làm như vậy tránh được việc lộ mã hóa OPE của cột đó tới server.
Training mode. CryptDB cung cấp một training mode, cho phép nhà phát triển cung cấp theo dõi các truy vấn
và thu được các lớp mã hóa onion kết quả cho từng trường (field), cùng với một cảnh báo trong trường hợp một
vài truy vấn không được hõ trợ. Nhà phát triển sau đó có thể nghiên cứu các lớp mã hóa kết quả để biết được
từng cơ lược đồ mã hóa rò rỉ, như miêu tả trong phần 2.1. Nếu một vài mức onion quá thấp cho một trường
nhạy cảm, cô ấy nên sắp xếp để có các truy vấn được xử lý trong proxy (như mô tả ở trên), hoặc để xử lý dữ

liệu trong một vài kiểu khác, chẳng hạn như bằng cách sử dụng một local instance của SQLite.
Onion re-encryption. Trong trường hợp một ứng dụng thực hiện các truy vấn ít xảy ra yêu cầu một lớp onion
thấp (ví dụ, OPE), CryptDB có thể được mở rộng tới các onion mã hóa lại quay trở về một lớp cao hơn sau khi
truy vấn ít xảy ra đó kết thúc thực thi. Cách tiếp cận này giảm thiểu sử rò rỉ cho các tấn công xảy ra trong cửa sổ
thời gian (time window) khi dữ liệu đang ở lớp onion cao hơn.

3.5.2. Các tối ưu hóa hiệu suất - Performance Optimizations
Developer annotations. Theo mặc định CryptDB mã hóa tất cả các trường và tạo tất cả các onion có thể áp dụng
cho từng mục dữ liệu dựa trên loại của nó. Nếu nheiefu cuột không nhạy cảm, nhà phát triển có thể cung cấp
các chú thích rõ ràng thay thế để chỉ ra các trường nhạy cảm (được mô tả trong phần 4), và để các trường còn lại
ở dạng rõ.
Tập truy vấn đã biết - Know query set. Nếu nhà phát triển biết một vài truy vấn trước đó, như trường hợp cho
nhiều ứng dụng web, nhà phát triển có thể sử dụng training mode được mô tả ở trên đê điều chỉnh các onion
sang lớp a priori chính xác, tránh chi phí của các điều chỉnh onion đang chạy (runtime onion adjustments). Nếu
nhà phát triển cung cấp tập truy vấn chính xác, hoặc các chú thích mà chỉ ra chức năng nhất định không cần
thiết trên một số cột, CryptDB cũng có thể loại bỏ các onion mà ko cần thiết (ví dụ loại bỏ Ord onion cho các
cột mà không sử dụng trong các truy vấn range, hoặc loại bỏ Search onion cho các cột khi tìm kiếm từ khóa
không được thự hiện), loại bỏ các lớp onion không cần thiết (ví dụ adjustable JOIN layer, nếu các join là a
priori), hoặc loại bỏ IV ngẫu nhiên cần cho RND cho một vài cột.
Ciphertext pre-computing and caching. Proxy dành một lượng đang kể thời gian mã hóa các giác trị được sử
dụng trong các truy vấn với OPE và HOM. Để giảm thiểu chi phí, proxy tính toán trước (pre-computes) (cho
HOM) và lưu trữ đệm (caches) (cho OPE) các mã hóa của các hằng số thường được sử dụng dưới các key khác
nhau. Vì HOM theo xác suất (probabilistic), các bản mã không thể được sử dụng lại. Vì vậy, ngoài ra, Proxy
tính toán lại các giá trị ngẫu nhiên Paillier rn của HOM cho các mã hóa sau này của bất cứ dữ liệu nào. Sự tối ưu
hóa này giảm thời gian CPU mà proxy dùng trên mã hóa OPE, và giải định proxy đôi khi nhàn rỗi để thực hiện
tính toán trước HOM, nó loại bỏ mã hóa HOM từ path quan trọng.


4.Multiple Principals
Bây giờ chúng tôi sẽ mở rộng mô hình đe dọa tới trường hợp khi cơ sở hạ tầng ứng dụng và proxy cũng không

được tin tưởng (mối đe dọa thứ 2). Mô hình này đặc biệt liên quan cho một website đa người dùng đang chạy
một web và server ứng dụng. Để hiểu được các vấn đề một ứng dụng web đa người dùng phải đối mặt và giải
pháp của CryptDB cho những vấn đề này, xem xet phpBB, một forum web trực tuyến phổ biến. Trong phpBB,
mỗi người dùng có một tài khoản và một mật khẩu, thuộc về các nhóm nhất định, và có thể gửi tin nhắn cá nhân
cho những người dùng khác. Phụ thuộc vào sự cho phép của nhóm của họ, những người dùng có thể đọc toàn
bộ forum, chỉ một vài forum, hoặc không có khẳ năng đọc một frum nào cả.
Có một số đảm bảo bí mật sẽ có ích trong phpBB. Ví dụ, chúng tôi muốn đảm bảo rằng một tin nhắn cá nhân
được gửi từ một người dùng tới người dùng khác không nhìn thấy được bởi bất cứ một ai khác; các bài viết đó
trong một forum chỉ có thể truy cạp được tới những người dùng trong một nhóm truy cập forum đó; và tên của
forum chỉ được hiển thị với những người dùng thuộc về một nhóm mà được cho phép xem nó. CryptDB cung
cấp những đảm bảo này khi đối mặt với những thỏa hiệp tùy ý, do đó hạn chế những thiệt hại gây ra khi bị thỏa
hiệp.
Để đạt được những đảm bảo này yêu cầu giải quyết hai thách thức. Đầu tiên, CryptDB phải nắm bắt (capture)
chính sách kiểm soát truy cập của ứng dụng cho dữ liệu được chia sẻ tại mức của các truy vấn SQL. Để làm
điều này, CryptDB yêu cầu các nhà phát triển chú thích (annotate) lược đồ cơ sở dữ liệu của họ để chỉ rõ các
principal và dữ liệu mà từng principal có quyền truy cập, như mô tả trong phần 4.1.
Thách thức thứ hai là để giảm lượng thông tin mà một kẻ xấu có thể đạt được bằng cách thỏa hiệp hệ thống.
Giải pháp của chúng tôi hạn chế sự rò rỉ từ một ứng dụng hay proxy server bị thỏa hiệp để chỉ dữ liệu của những
người dùng đã đăng nhập bị ảnh hưởng trong khi bị thỏa hiệp. Đặc biệt, kẻ tấn công không thể truy cập dữ liệu
của những người dùng mà không đăng nhập trong khi bị thỏa hiệp. Việc lộ dữ liệu của những người dùng đang
hoạt động trong trường hợp thỏa hiệp là không thể tránh được: để tính toán trên dữ liệu mã hóa, một vài dữ liệu
của người dùng hoạt động phải được ứng dụng giải mã.
Trong CryptDB, mỗi user có một key( ví dụ mật khẩu mức ứng dụng ) mà cho phép user đó truy cập tới dữ liệu
của mình. CryptDB mã hóa các mục dữ liệu khác nhau với các key khác nhau, và tăng cường chính sách kiểm
soát truy cập sử dụng các chuỗi bắt đầu bởi các key từ các mật khẩu người dùng và kết thúc bằng các key mã
hóa của các mục dữ liệu SQL, như mô tả trong phần 4.2. Khi một user đăng nhập, anh ta cung cấp mật khẩu của
mình cho proxy (thông qua ứng dụng). Proxy sử dụng mật khẩu này để lấy được các key onion để xử lý các truy
vấn trên dữ liệu mã hóa, như đã trình bày ở phần trước, và để giải mã các kết quả. Proxy chỉ có thể giải mã dữ
liệu mà user đã truy cập, dựa vào chính sách kiểm soát truy cập, Proxy đưa dữ liệu mã hóa cho ứng dụng, và
bây giờ có thể tính toán trên nó. Khi user đăng xuất, proxy xóa key của user.


4.1.Các chú thích chính sách – Policy Annotations
Để thể hiện chính sách bảo mật dữ liệu của một ứng dụng database-backed tại mức của các truy vấn SQL, nhà
phát triển ứng dụng có thể chú thích (annotate) lược đồ của một cơ sở dữ liệu trên CryptDB bằng cách chỉ rõ,
cho từng tập con mục dữ liệu, mà principal truy cập vào nó. Một principal là một thực thể, như một user của
một group chẳng hạn, mà nó là tự nhiên để xác định một chính sách truy cập. Từng truy vấn SQL kéo theo một
mục dữ liệu được chú thích đòi hỏi đặc quyền của principal tương ứng. CryptDB định nghĩa khái niệm principal
của bản thân nó thay vì sử dụng các DBMS principal có sẵn vì hai lý do sau: đầu tiên, nhiều ứng dụng không
ánh xạ (map) các user mức ứng dụng tới các DBMS principal một cách đầy đru, và thứ hai, CryptDB yêu cầu sự


ủy quyền rõ ràng của các đặc quyền giữa các principal mà khó để trích xuất một cách tự động từ một danh sách
kiểm soát truy cập chi tiết.
Một nhà phát triển ứng dụng chú thích lược đồ bằng cách sử dụng ba bước được miêu tả dưới đây và được
minh họa trong Hình 4. Trong tất cả ví dụ chúng tôi đưa ra, các chứ nghiêng chỉ các tên của bảng và cột, các
chữ in đậm chỉ ra các chú thích được thêm vào cho CryptDB.

Hình 4: một phần lược đồ của phpBB với các chú thích để đảm bảo riêng tư tin nhắn. Chỉ người gửi và người
nhận có thể thấy các tin nhắn riêng tư. Một kẻ tấn công mà đạt được truy cập hoàn toàn vào phpBB và DBMS
có thể truy cập các tin nhắn riêng tư của chỉ những user đang hoạt động.
Bước 1. Nhà phát triển phải định nghĩa principal types (sử dung PRINCTYPE) được sử dụng trong ứng dụng
của anh ta, như các user, các group, hoặc các message. Một principal là một trường hợp của một principal type,
ví dụ principal 5 của type user. Có hai lớp principal: external và internal. Các external principal tương ứng với
các end user người xác thực chính xác là họ với ứng dụng sử dụng một mật khẩu. Khi một user đăng nhập vào


ứng dụng, ứng dụng phải cung cấp mật khẩu user cho proxy để user có thể có được những đặc quyền của
external principal của anh ấy. Các đặc quyền của các (internal) principal khác chỉ có thể đạt được thông qua sự
ủy quyền, như được mô tả trong Bước 3. Khi user đăng xuất, ứng dụng phải báo cho proxy biết, để proxy quên
mật khẩu của user cũng như bất kỳ key nào có nguồn gốc từ mật khẩu của user.

Bước 2. Nhà phát triển phải chỉ rõ các cột nào trong lược đồ SQL của anh ta có chứa dữ liệu nhạy cảm, cùng với
các principal mà cần phải có quyền truy cập vào dữ liệu đó, sử dụng chú thích ENC_FOR. CryptDB yêu cầu
điều đó cho từng mục dữ liệu riêng trong một hàng, tên của principal mà cần phải có quyền truy cập tới dữ liệu
đó được lưu trữ trong cột khác trong cùng một hạng. Ví dụ, trong Hình 4, việc giải mã của msgtext x37a21f chỉ
có cho principal 5 của type msg.
Bước 3. Các lập trình viên có thể chỉ rõ các luật (rules) cho việc làm thế nào để ủy quyền các đặc quyền của một
principal cho các principal khác, sử dụng mốt quan hệ speak-for [49]. Ví dụ, trong phpBB, một user phải có các
đặc quyền của các nhóm mà anh ta thuộc về. Vì nhiều ứng dụng lưu trữ những thông tin như vậy trong các
bảng, các lập trình viên có thể chỉ ra cho CryptDB cách nào để suy ra các luật ủy thác từ các hàng trong các
bảng đang tồn tại. Đặc biệt, các lập trình viên có thể chú thích một bảng T với (a x) SPEAKS_FOR (b y). Chú
thích này chỉ ra rằng từng hàng hiện tại trong bảng đó quy định rằng principal a của type x đại diện (speaks for)
cho principal b của type y, có nghĩa rằng a có truy cập tới tất cả các key mà b truy cập. Ở đây, x và y phải luôn
luôn là các prinxipal type cố định. Principal b luôn luôn được chỉ rõ bởi tên của một cột trong bảng T. Mặt khác,
a cũng có thể là tên của một cột khác trong cùng một bàng, một hằng số, hoặc T2.col, nghĩa là tất cả các
principal từ cột col của bảng T2. Ví dụ, Trong Hình 4, principal “Bob” của type physical_user đại diện cho
principal 2 của type user, và trong Hình 6, tất cả các principal trong cột contactId từ bảng PCMember (type
contact) đại diện cho paperId principal của type review. Tùy chọn, lập trình viên có thể chỉ ra một vị từ
(predicate), mà đầu vào là các giá trị trong cùng một hàng, để chỉ ra một điều kiện mà theo đó sự ủy thác nào sẽ
xảy ra, như sự loại trừ các xung đột trong Hình 6 chẳng hạn. Phần 5 cung cấp nhiều ví dụ hơn trong việc sử
dụng các chú thích để đảm bảo an toàn các ứng dụng.

4.2.Key Chaining
Mỗi principal (ví dụ, mỗi trường hợp của mối principal type) được liên kết với một key bí mật, được lựa chọn
ngẫu nhiên. Nếu principal B đại diện principal A (như một kết quả của một số chú thích SPEAKS_FOR), thì key
của principal A được mã hóa sử dụng key của principal B, và được lưu trữ như một hàng trong bảng đặc biệt là
access_key trong cơ sở dữ liệu. Ví dụ, trong Hình 4, để trao cho user1 và user2 truy cập tới message 5, key của
msg 5 được mã hóa với key của user 1, và cũng được mã hóa riêng với key của user 2.
Mỗi trường nhạy cảm được mã hóa với key của principal trong chú thích ENC_FOR (ENC_FOR annotation).
CryptDB mã hóa trường nhạy cảm với các onion theo cùng cách như đối với principal CryptDB đơn lẻ, ngoại
trừ các key onion được suy ra từ key của một principal như trái ngược với một global master key.

Key của từng principal là một kết hợp của symmetric key và một cặp public-private key. Trong trường hợp phổ
biến, CryptDB sử dụng symmetric key của một principal để mã hóa bất kỳ dữ liệu nào và các key của các
principal khác có thể truy cập vào chính principal này, với chi phí CPU ít. Tuy nhiên, điều này thường không
khả thi, nếu một vài principal hiện đang không trực tuyến. Ví dụ, trong Hình 4, giả sử Bob gửi message 5 cho
Alice, nhưng Alice (user 1) không online. Điều này có nghĩa là CryptDB không có truy cập vào key của user 1,
vì thế nó sẽ không thể mã hóa key của message 5 với symmetric key của user 1. Trong trường hợp này,
CryptDB tìm public key của principal (ví dụ user 1) trong một bảng thứ hai, public_keys, và mã hóa key của
message 5 sử udngj public key của user 1. Khi user 1 đăng nhập, cô ta sẽ có thể sử dụng phần secret key của


key của cô ấy để giải mã key cho message 5 (và mã hóa lại nó bằng symmetric key của cô ấy để sử dụng sau
này).
Đối với các external principal (ví dụ, các physicla user), CryptDB gán một key ngẫu nhiên cũng như với bất kỳ
principal khác. Để cho một extenal user truy cập tới key tương ứng trên đăng nhập, CryptDB lưu trữ key của
từng external principal trong một bảng thứ ba, external_keys, được mã hóa với mật khẩu của principal. Điều này
cho phép CryptDB có được key của một user đã đưa mật khẩu của user, và cũng cho phép một user thay đổi mật
khẩu của cô ấy mà không thay đổi key của principal.
Khi một bảng với một mối quan hệ SPEAKS_FOR được cập nhật, CryptDB phải cập nhật bảng access_keys
phù hợp. Để chèn một hàng mới vào access_keys cho một mối quan hệ SPEAKS_FOR mới, proxy phải có truy
cập tới key của principal mà những đặc quyền của anh ta đang được ủy thác. Điều này có nghĩa là một kẻ xấu
mà xâm nhập vào một ứng dụng hoặc proxy server không thể tạo các mối quan hệ SPEAKS_FOR mới cho các
principal mà không đăng nhập, vì cả proxy cũng như kẻ xấu đều không truy cập được các key của họ. Nếu quan
hệ SPEAKS_FOR bị gỡ bỏ, CryptDB thu hồi truy cập bằng cách gỡ bỏ cột tương tứng khỏi access_keys.
Khi mã hóa dữ liệu trong một truy vấn hoặc giải mã dữ liệu từ một kết quả, CryptDB theo các key chain là bắt
đầu từ các mật khẩu của các user đăng nhập cho đến khi nó có được các key mong muốn.. Như là một tối ưu,
khi một user đăng nhập, proxy của CryptDB tải các key của một vào principal mà người dùng có quyền truy cập
(đặc biệt, các principal type đó không có quá nhiều trường hợp principal – ví dụ, cho cac group mà user trong
đó,nhưng không cho các message mà user được nhận).
Các ứng dụng thông báo cho CryptDB các user đăng nhập hay đăng xuất bằng cách sinh ra các truy vấn SQL là
INSERT và DELETE cho một bảng đặc biệt cryptdb_active có hai cột, username và password. Proxy chặn tất

cả các truy vấn cho cryptdb_active, lưu trữ các mật khẩu của user đăng nhập trong bộ nhớ, và không bao giờ để
lộ chúng cho DBMS server.
CryptDB bảo vệ dữ liệu của những user không hoạt động trong thời gian của một cuộc tấn công. Nếu một thỏa
hiệp xảy ra, CryptDB cung cập một một ràng buộc trên dữ liệu bị rò rỉ, cho phép các quản trị viên không sinh ra
các cảnh báo trống tới tất cả user của hệ thống. Trong chú ý này, CryptDB khác với những cách tiếp cận khác
tới an toàn cơ sở dữ liệu (xem phần 9). Tuy nhiên, một vài user dặc biệt như quản trị viên chẳng hạn có quyền
truy cập vào một lượng lớn dữ liệu cho phép một thỏa hiệp lớn hơn khi một cuộc tấn công diễn ra. Để tránh các
tấn công xảy ra khi quản trị viên đăng nhập, quản trị viên phải tạo một tài khoản user riêng với các quyền hạn
chế khi truy cập và ứng dụng như một user bình thường. Ngoài ra, trong thực tế, một ứng dụng tốt nên tự động
đăng xuất những user không hoạt động trong một khoảng thời gian.

5.Application Case Studies
Trong phần này, chúng tôi giải thích cách mà CryptDB có thể được sử dụng để đảm bảo an toàn cho 3 ứng dụng
web đa người dùng hiện hành. Cho ngắn gọn, chúng tôi cho thấy các lược đồ đơn giản, loại bỏ các trường
không liên quan. Nhìn chung, chúng tôi tìm ra rằng khi một lập trình viên chỉ ra các princial trong lược đồ của
ứng dụng, và cá quy tắc ủy quyền cho họ sử dụng SPEAKS_FOR, bảo vệ các trường nhạy cảm khác chỉ cần yêu
cầu thêm các chú thích ENC_FOR.


Hình 5: lược đồ chú thích cho việc đảm bảo an toàn truy cập tới các bài viết (posts) trong phpBB. Một user truy
cập để tháy nội dung của các bài viết trong một forum nếu bất kể group nào mà user thuộc về có quền như vậy,
được chỉ ra bởi optionid 20 trong bảng aclgroups cho sự tương tứng forumid và groupid. Tương tự, optionid 14
cho phép các user tháy tên của forum.
phpBB làm một forum mã nguồn mở được sử dụng rộng rãi với một tập phong phú các thiết lập điều khiển truy
cập. Các user được tổ chức trong các group; cả các user và các group đều có một loạt các quyền truy cập mà
quản trị viên ứng dụng có thể chọn. Chúng tôi đã cho thấy cách đảm bảo an toàn các tin nhắn riêng tư giữa 2
user trong phpBB trong Hình 4. Một trường hợp chi tiết hơn là đảm bảo an toàn truy cập các bài viết, như trong
Hình 5. Ví dụ này cho thế cách sử dụng các vị từ (ví dụ IF optionid=…) để thực hiện một quan hệ điều kiện
speaks-for trên các principal, và cũng là cách một cột (forumid) có thể được sử dụng để đại điện nhiều principal
(của các loại khác nhau) với các đặc quyền khác nhau. Có nhiều cách để truy cập vào một bài viết, nhưng chúng

tôi bỏ qua chúng ở đây cho ngắn gọn.


Hình 6: lược đồ chú thích cho đảm bảo an toàn các review trong HotCRP. Các review và danh tính của các
reviewer đang cung cấp review sẽ chỉ hiển thị cho các PC thành viên (bảng PCMember bao gồm các PC chủ
tọa) người mà không mâu thuẫn, và các PC chủ tọa không thể ghi đè lên sự giới hạn này.
HotCRP là một ứng dụng phê bình hội nghị (conference review application) phổ biến [27]. Một chính sách
quan trọng cho HotCRP là các PC thành viên không thể thấy ai đã phê bình (reviewed) các bài viết của chính
họ. Hình 6 cho thấy các chú thích CryptDB cho lược đồ của HotCRP để thực thi chính sách này. Ngày nay,
HotCRP không thể ngăn một PC chủ tọa cuộc họp tò mò hoặc bất cẩn đăng nhập vào database server và thấy ai
đã viết từng review cho một bài báo mà cô ấy mâu thuẫn với nó. Kết quả là, các hội nghị (conferences) thường
thieetps lập một server thứ hai để review các bài viết của chủ tọa hoặc sử dụng các email out-of –band bất tiện.
Với CryptDB, một PC chủ tọa không thể biết ai đã viết từng review cho bài viết của cô ấy, kể cả khi cô ấy
chiếm được ứng dụng hay cơ sở dữ liệu, vì cô ấy không có key giải mã (việc thực hiện đày đủ chính sách này
yêu cầu thiết lập 2 PC chủ tọa (PC chairs): một chủ tọa chính, và một chủ tọa backup chịu tránh nhiệm review
các bài viết của chủ tọa chính. HotCRP cho phép PC chủ tọa đóng vai các PC thành viên, vì thế các chú thích
CryptDB sẽ được sử dụng để ngăn chủ tọa chính đạt được truy cập tới các key của những người review được
gắn với bài viết của cô ấy.). Lý do là vị từ SQL “NoConflict” kiểm tra xem liệu một PC thành viên có mâu
thuẫn với một bài viết và ngăn chặn proxy cung cấp truy cập tới PC chủ tọa trong key chain. (chúng ta giải sử
rằng PC chủ tọa không thay đổi ứng dụng để log lại các mật khẩu của các PC thành viên khác để lật đổ hệ
thống).
grad-apply là một tuyển sinh sau đại học được sử dụng bởi MIT EECS. Chúng tôi chú thích lược đồ của nó để
cho phép một thư mục của ứng dụng chỉ được truy cập bởi những người ứng tuyển riêng và bất cứ giảng viên
đang sử dụng (reviewers.reviewer_id reviewer) trong bảng canddidatess, và … SPEAKS_FOR (letter_id letter)


trong bảng letter. Người nộp đơn có thể thấy tất cả thư mục dữ liệu của mình ngoại trừ thư giới thiệu. nhìn
chung, grad-apply có điều khiển truy cập đơn giản và vì thế chú thích cũng đơn giản.

6.Thảo luận – Discussion

Thiết kế của CryptDB hỗ trợ hầu hết các truy vấn quan hệ và các kết hợp trên các loại dữ liệu tiêu chuẩn, như
integer và text/varchar. Các tính toán bổ sung có thể được thêm vào CryptDB bằng cách mở rộng các onion đã
có, hoặc thêm các onion mới cho các loại dữ liệu cụ thể (ví dụ các truy vấn đa chiều – spatial and multidimensional range queries [43]). Ngoài ra, trong một vài trường hợp, nó có thể ảnh xạ các phép toán không hỗ
trợ phức tạp sang phép toán đơn giản hơn (ví dụ, trích ra tháng của một ngày đã mã hóa sẽ đơn giản hơn nếu các
trường ngày, tháng, năm của ngày đó được mã hóa riêng lẻ).
Có những phép toán nhất định CryptDB khong thể hỗ trợ trên dữ liệu mã hóa. Ví dụ, nó không hỗ trợ cả tính
toán và so sánh trên cùng một cột, như WHERE salary > age*2+10. CryptDB có thể xử lý một phần của truy
vấn này, nhưng nó cũng sẽ yêu cầu một vài xử lý trên proxy. Trong CryptDB, truy ván như vậy phải được (1)
viết lại thành một truy vấn con select cả một cột, SELECT age*2+10 FROM…, mà CryptDB tính toán sử dụng
HOM, và (2) mã hóa lại trong proxy, tạo một cột mới (gọi nó là aux) trên DBMS server bao gồm các giá trị mã
hóa mới. Cuối cùng, truy vấn ban đầu với vị từ WHERE salary > aux mới được chạy. Chúng tôi không bị ảnh
hưởng bởi giới hạn nà trong các ứng dụng kiểm tra của chúng tôi (TCP-C, phpBB, HotCRP, và grad-apply).
Trong chế độ đa principal, CryptDB không thể thực hiện các tính toán phía server trên các giá trị được mã hóa
cho các principal khác nhau, kể cả nếu ứng dụng có quyền của tất cả các principal mà ta đã thảo luận, bởi vì các
bản mã được mã hóa với các key khác nhau. Đối với một vài tính toán, thực tế có thể proxy thực hiện tính toán
sau khi giải mã dữ liệu, nhưng với những tính toán khác (ví dụ, tính toán trên phạm vi rộng lớn – large-scale
aggregates) cách tiếp cận này có thể quá tốn kém. Một khả năng mở rộng để CryptDB hỗ trợ những truy vấn
như vậy có thể để duy trì nhiều bản mã cho những giá trị như vậy, mã hóa dưới các key khác nhau.

7.Triển khai - Implementation
CryptDB proxy bao gồm một thư viện C++ và một modun Lua. Thư viện C++ bao gồm một phân tích cú pháp
truy vấn (query parser); một bộ mã hóa/ viết lại truy vấn (query encryptor/rewriter), để mã hóa các trường hoặc
bao gồm các UDF trong truy vấn; và một modun giải mã kết quả. Để cho phép ứng dụng trong suốt sử dụng
CryptDB, chúng tôi đã sử dụng MySQL proxy [47] và đã thực hiện một modun Lua để chuyển các truy vấn và
kết quả tới và từ modun C++ của chúng tôi. Chúng tôi đã thực hiện các giao thức mật mã mới của chúng tôi sử
dụng NTL [44]. Việc thực hiện CryptDB của chúng tôi bao gồm ~18,000 dòng code C++ và ~150 dòng code
Lua, với ~10,000 dòng code kiểm tra khác nữa.
CryptDB có tính di động (portable) và chúng tôi đã thực hiện các phiên bản cho cả Postgres 9.0 và MySQL 5.1.
Việc thực hiện ban đầu của chúng tôi dựa trên Postgress được mô tả trong một báo cáo kỹ thuật gần đây [39].
Việc để CryptDB hoạt động với MySQL yêu cầu thay đổi chỉ 86 dòng code, chủ yếu trong code để kết nối

MySQL server và khai báo các UDF. Như đã đề cập trước đó, CryptDB không thay đổi DBMS; chúng tôi
thuwcjhieenj tất cả các chức năng phía server với các UDF và các bảng phí server. Thiết kế của CryptDB làm
việc được trên bất kỳ SQL DBMS phổ biến nào mà hỗ trợ các UDF.


8.Đánh giá thí nghiệm – Experimental Evaluation
Trong phần này, chúng tôi đánh giá 4 khía cạnh của CryptDB: những khó khăn của việc điều chỉnh một ứng
dụng để chạy như một chương trình điều khiển tới CryptDB, các loại truy vấn và các loại ứng dụng CryptDB hỗ
trợ, lức độ an toàn CryptDB cung cấp, và hiệu quả tác động của việc sử dụng CryptDB. Với phân tích này,
chúng tôi sử dụng bảy ứng dụng, cũng như một lượng lớn các truy vấn SQL để đánh giá.
Chúng tôi đánh gái hiệu quả của các chú thích (annotations) của chúng tôi và các thay đổi ứng dụng cần thiết
trên 3 ứng dụng chúng tôi đã mô tả trong phần 5 (phpBB, HotCRP, và grad-apply), cũng như trên một kết hợp
truy vấn TPC-C (a standard workload in the database industruy). Sau đó chúng tôi phân tích chức năng và an
toàn của CryptDB trên 3 ứng dụng nữa, trên TPC-C, và trên một lượng lớn các truy vấn SQL Ba ứng dụng bổ
sung là OpenEMR, một ứng dụng hồ sơ ý tế điện tử lưu trữ dữ liệu ý tế riêng tư của bệnh nhân; ứng dụng web
của một lớp MIT (6.02), lưu trữ các lớp học sinh; và PHP-calendar, lưu trữ lịch làm việc của người. Lượng lớn
các truy vấn SQL để theo dõi đến từ một server MySQL tại MIT, sql.mit.edu. Server này được sử dụng chủ
yếu bởi các ứng dụng web chạy trên scripts.mit.edu, một dịch vụ hosting ứng dụng web chia sẻ được
điều hành bởi Ban xử lsy thông tin sinh viên của MIT (Student Information Processing Board – SIPB). Thêm
vào đó, server SQL này được sử dụng mởi một số các ứng udngj chạy trên các máy khác và sử dụng
sql.mit.edu chỉ để lưu trữ dữ liệu của chúng. Chúng tôi theo dõi trong khoảng 10 ngày, và có khoảng 126
triệu truy vấn. Hình 7 tóm tắt các số liệu thống kê sơ đồ cho sql.mit.edu; mỗi cơ sở dữ liệu gần như là một
trường hợp riêng biệt của một vài ứng dung.
Cuối cùng, chúng tôi đánh giá hiệu suất tổng thể của CryptDB trên ứng dụng phpBB và trên một truy vấn kết
hợp từ TPC-C, và thực hiện phân tích chi tiết thông qua microbenchmarks
Trong sáu ứng dụng (không tính TPC-C), chúng tôi chỉ mã hóa các cột nhạy cảm, theo một kiểm tra thủ công.
Một vài trường rõ ràng nhạy cảm (ví dụ, grades, private message, medical information), nhưng một số khác thì
không như vậy (ví dụ, thời gian khi một tin nhắn được post). Không có ngưỡng rõ ràng nào giữa nhạy cảm hay
không, nhưng nó hoàn toàn rõ ràng cho chúng tôi xác định những trường nào là chắc chắn nhạy cảm. Trong
trường hợp của TPC-C, chúng tôi mã hóa tất cả các cột trong cơ sở dữ liệu trong chế độ single-principal vì thế

chúng tôi có thể nghiên cứu hiệu suất và chức năng của một DBMS được mã hóa hoàn toàn.

8.1. Các thay đổi ứng dụng
Hình 8 tóm tắt số lượng kết quả lập trình cần thiết để sử dụng CryptDB trong ba ứng dụng web đa người dùng
và trong các truy vấn single-principal TPC-C. Kết quả cho thấy rằng, đối với chế độ multi-principal, CryptDB
yêu cầu từ 11 đến 12 chú thích lược đồ (29 tới 111 trong tổng số), và 2 đến 7 dòng code thay đổi để cung cấp
các mật khẩu người dùng cho proxy, để đảm bảo an toàn các thông tin nhạy cảm được lưu trữ trong cơ sở dữ
liệu. Một phần của sự đơn giản là vì việc đảm bảo an toàn một cột bổ sung yêu cầu chỉ một chú thích trong hầu
hết các trường hợp. Đối với các truy vấn single-principal TPC-C, việc sử dụng CryptDB không yêu cầu chú
thích ứng dụng nào cả.

8.2. Đánh giá chức năng
Để đánh giá các cột nào, các phép toán nào, và các truy vấn nào CryptDB có thể hỗ trợ, chúng tôi đã phân tích
các truy vấn được sinh ra bởi sáu ứng dụng web (bao gồm ba ứng dụng chúng tôi đã phân tích trong phần 8.1),
các truy vấn TPC-C, và các truy vấn SQL từ sql.mit.edu. Kết quả được thể hiện trong nửa bên trái của
Hình 9.


CryptDB hỗ trợ hầu hết các truy vấn; số lượng các cột trong cột “cần rõ – needs plaintext”, mà việc đếm các cột
không thể được xử lý ở dạng mã hóa bởi CryptDb, là tương đối nhỏ so với tổng số cột. Với PHP-calendar và
OpenEMR, CryptDB không hỗ trợ các truy vấn trên các trường nhạy cảm nhất định mà thực hiện thao tác chuỗi
(ví dụ các chuyển đổi chuỗi con và chữ thường) hoặc thao tác ngày (ví dụ, lấy ngày, tháng, hoặc năm của một
ngày mã hóa). Tuy nhiên, nếu các chức năng này được tính toán trước với kết quả được thêm vào như là các cột
độc lập (ví dụ, mỗi một ba phần của ngày được mã hóa tách riêng), CryptDB sẽ hỗ trợ các truy vấn này.
Hai cột tiếp theo, “needs HOM” và “needs SEARCH”, ánh xạ số lượng cột cho lược đồ mã hóa đó là cần thiết
để xử lý một vài truy vấn. Các số này gợi ý rằng những lược đồ mã hóa này là quan trọng; nếu không có những
lược đồ này, CryptDB sẽ không có khả năng hỗ trợ những truy vấn đó.
Dựa trên một phân tích theo dõi sql.mit.edu, chúng tôi thấy rằng CryptDB có khả năng hỗ trợ các tính
toán trên tất cả trừ 1,094 cột trong 128,840 cột quan sát được trong cuộc theo dõi. “in-proxy processing” cho
thấy các kết quả phân tích với giả định proxy có thể tực hiện một vài tính toán nhẹ (lightweight) trên các kết

quả được trả về từ DBMS server. Đặc biệt, điều này đã bao gồm bất kỳ phép toán nào mà không cần thiết để
tính toán tập các hàng kết quả hoặc để tập hợp các hàng (nghĩa là, các biểu thức mà không xuất hiện trong một
mệnh đề WHERE, HAVING, hay GROYP BY, hoặc trong một mệnh đề ORDER BY với một LIMIT, và không
phải là các toán tử tập hợp (aggregate operators)). Với xử lý trong proxy, CryptDB có khả năng xử lý các truy
vấn trên dữ liệu mã hóa trên tất cả trừ 571 cột trong tổng số 128,940 cột, vì thế hỗ trợ 99.5% các cột.
Trong 571 cột, 222 sử dụng một toán tử bitwise trong một mệnh đè WHERE hoặc thực hiện bitwise
aggregation, như ứng dụng Gallery2 chẳng hạn, sử dụng một bitmask của các trường cho phép và tham vấn
chúng trong các mệnh đề WHERE. Việc viết lại ứng dụng để lưu trữ các cho phép trong một cách khác sẽ cho
phép CryptDB hỗ trợ các phép toán như vậy. 205 cột khác thực hiện xử lý chuỗi trong các mệnh đề WHERE,
như so sánh phiên bản chữ thường của hai chuỗi có tương xứng không. Việc lưu trữ một keyed hash của phiên
bản chữ thường của từng chuỗi cho từng cột, tương tự lượt đồ JOIN-ADJ, có thể hỗ trợ các equality check
trường hợp nhạy cảm cho các bản mã. 76 cột là liên quan tới các chuyển đổi toán học trong mệnh đề WHERE,
như tháo tác ngày, thời gian, điểm, và tọa độ hình học. 41 cột gọi toán tử LIKE với một tham chiếu cột cho mô
hình (pattern); thường được sử dụng để kiểm tra một giá trị đặc biệt với một bảng lưu trữ motojdanh sách các
địa chỉ IP bị cấm, tên người dùng, các URL,… Một truy vấn như vậy cũng có thể được viết lại nếu các mục dữ
liệu là nhạy cảm.

8.3. Đánh giá an toàn
Để hiểu được số lượng thông tin mà sẽ bị lộ cho kẻ xấu trong thực tế, chúng tôi nghiên cứu các mức onion ở
trạng thái ổn định của các cột khác nhau cho một loạt các ứng dụng và truy vấn. Để định lượng mức độ an toàn,
chúng tôi xác định MinEnc của môt cột là lược đồ mã hóa onion yếu nhất bị lộ ra trên bất kỳ onion nào của một
cột khi các onion đạt tới trạng thái ổn định. (ví dụ, sau khi ứng dụng phát sinh ra tất cả các loại truy vấn, hoặc
sau khi chạy toàn bộ theo dõi). Chúng tôi xem xét RND và HOM là các lược đồ mạnh nhất, theo sau là
SEARCH, DET và JOIN, và kết thúc với lược đồ yếu nhất là OPE. Ví dụ, nếu một cột có onion Eq tại RND,
onion Ord tại OPE và onion Add tại HOM, MinEnc của cột này là OPE
Phía bên phải của hình 9 cho thấy mức độ onion MinEnc cho một loạt các úng dụng và truy vấn theo dõi.
Chúng tôi thấy rằng hầu hết các trường tại RND, là lược đồ an toàn nhất. Ví dụ OpenEMR có hàng trăm trường
nhạy cảm mô tả điều kiện y tế và lịch sử của bệnh nhân, nhưng các trường này hầu hết chỉ được chèn và được
lấy, và không được sử dụng trong bất cứ tính toán nào. Một số cột cũng vẫn ở DET, thường để thực hiện tra cứu
key và joins. OPE, với việc để lộ thứ tự (order), được sử dụng ít thường xuyên nhất, và hầu hết cho các trường



không mấy nhạy cảm (ví dụ nhãn thời gian, số lượng tin nhắn). Vì thế, bảo mật có thể điều chỉnh được của
CryptDB cung cấp một cải thiện đáng kể tính bảo mật trên việc tiết lộ tất cả các lược đồ mã hóa đến server.
Để phân tích an toàn của CryptDB cho các cột cụ thể mà đặc biệt nhạy cảm, chúng tôi xcas định một mức an
toàn mới, HIGH, bao gồm các lược độ RND và HOM, cũng như DET cho các cột không có sự lặp lại (trong
trường hợp DET tương đương một cách hợp lý với RND). Đây là những lược đồ mã hóa an toàn cao gần như
không rò rỉ gì về dữ liệu. DET cho các cột lặp đi lặp lại và OPE khoogn phải là phần của HIGH vì chúng để lộ
các mối quan hệ tới DBMS server. Cột ngoài cùng bên phải của Hình 9 cho thấy rằng hầu hết các cột đặc biệt
nhạy cảm (một lần nữa, theo kiểm tra thủ công) là tại HIGH.

10. Kết luận
Chúng tôi đã trình bày CryptDB, một hệ thống cung cấp các mức bảo mật mạnh mẽ đảm bảo tính bí mật khi
phải đối mặt với các mối đe dọa đáng kể cho các ứng dụng database-backed: DBAs xấu và các thỏa hiệp tùy ý
của server ứng dụng và DBMS. CryptDB đạt được mực đích của nó sử dụng ba ý tưởng: chạy các truy vấn trên
dữ liệu mã hóa sử dụng một chiến lược mã hóa SQL mới, tự động điều chỉnh mức mã hóa sử dụng các onion mã
hóa để tối thiểu các thông tin bị lộ cho DBMS không tin cậy, và kết hợp các key mã hóa với các mật khẩu của
người dùng để chỉ những người dùng hợp pháp mới có thể truy cập được tới dữ liệu mã hóa.
Đánh giá của chúng tôi trong một cuộc khảo sát lớn 126 triệu truy vấn SQL từ một server MySQL cho thấy rằng
CryptDB có thể hỗ trợ các tính toán trên dữ liệu mã hóa cho 99.5% trong số 128,840 cột được theo dõi. Phân
tích an toàn của chúng tôi cho thấy rằng CryptDB bảo vệ hầu hết các trường nhạy cảm với các lược đồ mã hóa
an toàn cao với sáu ứng dụng.
Mã nguồn có sẵn để tải về tại />