ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
PHẠM THỊ BẠCH HUỆ NGHIÊN CỨU VÀ PHÁT TRIỂN MỘT SỐ
GIẢI PHÁP BẢO MẬT VÀ BẢO VỆ TÍNH RIÊNG TƯ
TRONG CƠ SỞ DỮ LIỆU THUÊ NGOÀI (ODBS)
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 62.48.01.01
TÓM TẮT LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN TP. HỒ CHÍ MINH – 2013

Công trình được hoàn thành tại Trường Đại học Khoa học Tự nhiên,
ĐHQG TP. HCM
dữ liệu (Data Owner - DO) tự đầu tư tài nguyên để lưu trữ và quản lý dữ
liệu của chính họ. Khi đó, chi phí quản lý dữ liệu cao làm tăng chi phí hoạt
động của tổ chức.
Xu hướng mới trong việc quản lý dữ liệu là sử dụng dịch vụ quản lý
CSDL thuê ngoài (Outsourced Database Service - ODBS). DO không phải
đầu tư tài nguyên cho việc lưu trữ và quản lý dữ liệu mà thuê nhà cung cấp
(Service Provider - SP) thực hiện điều này. Chi phí hoạt động của tổ chức
giảm đi đáng kể để họ trung vào các hoạt động chính yếu hơn.
Có bốn loại thực thể tham gia vào một hệ thống ODBS: (1) Chủ sở hữu
dữ liệu (Data Owner - DO): người tạo ra hoặc làm chủ dữ liệu (2) Máy chủ:
máy tính đặt tại SP có nhiệm vụ lưu trữ và quản lý dữ liệu của DO (3) Người
dùng: cá nhân hay ứng dụng truy cập CSDL lưu ở máy chủ theo quyền DO
đã cấp (4) Máy khách: thiết bị đầu cuối có nhiệm vụ tiếp nhận yêu cầu (từ
DO hoặc người dùng) và giao tiếp với máy chủ để đáp ứng cho yêu cầu nhận
được (Hình 1). Hình 1 Mô hình chung của ODBS
Thông qua máy khách, DO có thể gửi CSDL đến SP, hoặc yêu cầu máy
chủ tại SP cập nhật CSDL. DO gửi siêu dữ liệu đến người dùng để người
DO

CSDL


2).
Do máy chủ của SP được xem là
không đáng tin cậy, và quá trình tương
tác giữa các thực thể trong ODBS đều
thông qua mạng diện rộng, nên ODBS
đối diện với nhiều vấn đề về bảo mật
và bảo vệ tính riêng tư.
Mục tiêu đề tài
Hình 2 Mô hình SMS
Vì lý do trên, cùng với quá trình khảo sát hiện trạng các vấn đề bảo mật và
bảo vệ tính riêng tư cụ thể trong ODBS, chúng tôi nghiên cứu và phát triển
giải pháp cho bốn bài toán sau:
• Bảo vệ tính riêng tư người dùng (User privacy): đảm bảo thông tin
về câu truy vấn (mà người dùng thực hiện) hoặc kết quả truy vấn
không bị tiết lộ đối với máy chủ không tin cậy tại SP.
• Bảo vệ tính riêng tư dữ liệu (Data privacy): giúp DO giới hạn quyền
truy cập trên một số trường nhạy cảm của CSDL, giảm chi phí quản lý
truy cập, tạo thuận lợi cho người dùng khi tương tác với hệ thống.
• Xác thực (Authentication): đảm bảo thông tin đăng nhập của người
dùng không bị tiết lộ đối với máy chủ, ngăn chặn tấn công thường gặp
trong quá trình xác th
ực giữa máy khách và máy chủ.
DO
Người dùng
Máy chủ3
• Ghi nhật ký hệ thống (Auditing): giúp việc ghi nhật ký hệ thống phục
vụ giải trình (khi cần thiết) mà không làm vi phạm tính bí mật dữ liệu

vệ câu truy vấn mà người dùng thực hiện trên CSDL và kết quả truy vấn.
Giải pháp cho bài toán bảo vệ tính riêng tư người dùng thể hiện qua phương
pháp thực thi truy vấn. Các phương pháp thực thi truy vấn trên CSDL mã hóa
hiện có chỉ có thể sử dụng cho mục tiêu bảo vệ tính bí mật dữ liệu mà không
thể dùng cho mục đích bảo vệ tính riêng tư người dùng ([6], [32], [26], [43],
[50]). Lý do là máy chủ có thể thực hiện tấn công thống kê tần suất thực hiện
một câu truy vấn và kết hợp thông tin đã biết với những câu truy vấn được
thực hiện với tần suất cao, để suy ra ngữ nghĩa của câu truy vấn mà người
dùng thực hiện. Điều này làm vi phạm tính bí mật dữ liệu và tính riêng tư
người dùng.
Tính riêng tư dữ liệu được bảo vệ bằng một cơ chế quản lý truy cập. Sử
dụng những giải pháp quản lý truy cập hiện có, DO gặp phải những khó khăn
sau: (1) Không thể giới hạn quyền truy cập của người dùng trên một số thuộc
tính nhạy cảm của CSDL (2) DO thường xuyên phải xây dựng lại cấu trúc
quản lý khóa, phát sinh lại khóa, mã hóa lại dữ liệu khi có sự thay đổi về
người dùng, tài nguyên và quyền truy cập trong hệ thống (3) DO thường
xuyên giải quyết bài toán thay khóa (rekey) ngay cả trong những trường hợp
không cần thiết ([2], [3], [13], [18]). Khi thay khóa, DO phải tải về dữ liệu từ
máy chủ (nếu DO không lưu lại bản sao dữ liệu), phát sinh lại khóa, mã hóa
lại dữ liệu, phân phối lại khóa cho những người dùng có liên quan. Việc thay
khóa gây tốn kém nhiều chi phí.
Nghi thức xác thực rất cần thiết trong dịch vụ ODBS. Trong nhiều ứng
dụng thực tế, thông tin đăng nhập của người dùng tiết lộ danh tính của người
dùng. Trong ODBS, tính riêng t
ư người dùng phải được đảm bảo, ngay cả đối
với máy chủ. Các nghi thức xác thực hiện có không đặt ra mục tiêu bảo vệ
tính riêng tư người dùng chứa đựng trong thông tin đăng nhập; tất cả đều hoạt

5
động trên cơ sở máy chủ biết chính xác định danh của người dùng đang đăng

), ký hiệu r(R). Ký
hi
ệu R
+
để chỉ tập tất cả các thuộc tính của quan hệ r(R): R
+
= {A
1
, A
2
, …,
A
n
}. Ứng với mỗi quan hệ r, DO tạo một quan hệ r
S
có lược đồ quan hệ là:
R
S
(t
S
, A
1
S
, A
2
S
, …, A
n
S
)

i
S
= Map
Ai
(v)
• Attribute < Value: Mapcond(Ai < v) ⇒ Ai
S
∈ Map
<
Ai
(v)
• Attribute
1
= Attribute
2

Map
cond
(A
i
= A
j
) ⇒
ϕ
∨
(A
i
S
= ident
Ai


7
• Nguyên lý thứ hai: Mỗi lần thực hiện phép chọn đều chọn (n + m) giá
trị chỉ mục từ máy chủ. Tập hợp (n + m) giá trị chỉ mục này luôn thay
đổi cho dù (các) người dùng thực hiện một câu truy vấn nhiều lần.
Trong đó, n, m là các tham số nhận giá trị nguyên dương được DO
thiết lập cho hệ thống nhằm mục đích bảo vệ tính riêng tư người dùng.
• Nguyên lý thứ ba: Giảm thiểu công việc tại máy khách.
2.1.4 Giải pháp chung truy cập dữ liệu từ máy chủ
Thuật toán Select_NTimes được dùng để truy cập dữ liệu từ máy chủ phục
vụ cho tất cả các phép toán ĐSQH nhằm đảm bảo tính riêng tư người dùng.
Thuật toán 2.1 Select_NTimes(r(R), A, I, n, m)
Input: Quan hệ r(R), thuộc tính A ∈ R
+
, I là tập các giá trị chỉ mục (của thuộc
tính A) cần lấy, các tham số n, m.
Output: Các dòng (ở dạng mã) thuộc quan hệ r
S
thỏa: A
S
∈ I.
Bước Máy khách Máy chủ
1 Kết quả trả về KQ = ∅
Xác định tập tạo nhiễu T từ
(ident(r.A) – I). Tập T gồm các giá trị
chỉ mục ứng với thuộc tính A (là A
S
)
không chứa các giá trị thuộc I.


phần tử từ T để được Z có (n + m)
phần tử.
• Trường hợp thứ tư: Nếu card(I) >
(n + m) thì lấy ngẫu nhiên (n + m)
phần tử từ I, xem đây là tập Z.
4
5
)r(σ←KQ1
S
Z∈
S
A
SS

6
7 KQ2 ← Loại bỏ khỏi KQ1 những
dòng dư (thỏa A
S
∉ I), nếu có.

8 KQ ← KQ ∪ KQ2
9 Kết thúc lặp
2.1.5 Phương pháp thực thi các phép toán ĐSQH
Hai tham số n, m được sử dụng trong quá trình thực thi truy vấn nhằm

KQ2 = D(KQ1)
KQ ← σ
C
(KQ2)
return KQ

9
nhất một cặp giữa chúng (I và J) có chứa giá trị thỏa C: A
i
θ A
j
.
KQ1 = Select_NTimes_Grouped(r(R), A
i
, I, n, m, A
i
)
KQ2 = Select_NTimes_Grouped(t(T), A
j
, J, n, m, A
j
)
KQ3 = D(KQ1), KQ4 = D(KQ2)
KQ ← (KQ3 ⋈
C
KQ4)
return KQ
Phép chiếu
Thuật toán 2.5 Projection(r(R), n, m, L): chiếu r(R) trên tập thuộc tính L
A ∈R

10
2.1.7 Phân tích độ an toàn của UPP
• Nhận xét 1: Nên chọn T có lực lượng khá lớn và chọn m ≈ (card(T)/2).
• Nhận xét 2: Nên chọn T ⊂ (ident(A
i
) – I), m ≈ (card(T)/2) và m >
card(T)/2 để giải pháp thực thi truy vấn đề xuất an toàn hơn.
• Nhận xét 3: Với các phép toán cần thực thi trên toàn bộ quan hệ (chiếu,
tính tổng hợp và gom nhóm, sắp xếp, loại bỏ trùng lắp, hội, giao, hiệu), ta
nên chọn n, m để quá trình truy xuất dữ liệu diễn ra theo trường hợp 4
của thuật toán Select_NTimes, nhằm tiết kiệm chi phí xử lý dữ liệu thừa
tại máy khách lẫn máy chủ.
• Nhận xét 4: DO hoặc chuyên gia trong lĩnh vực ứng dụng, những người
am hiểu về hoạt động của hệ thống, nên xác định giá trị n và m đối với
mỗi thuộc tính có liên quan đến câu truy vấn của người dùng. Tất cả
những câu truy vấn trên cùng một thuộc tính nên sử dụng cùng giá trị n,
m giúp cho hệ thống bảo mật hơn.
• Nhận xét 5: Để đảm bảo giải pháp thực thi truy vấn đề xuất là an toàn
trong trường hợp truy vấn trên thuộc tính có miền giá trị hẹp, DO nên
chèn thêm dữ liệu giả.
2.2 Kết quả thực nghiệm Hình 2.4 Chi phí thực thi phép chọn của ba cách thực thi truy vấn, gồm thực

truy v
ấn phía máy khách (CC) chênh lệch không đáng kể so với chi phí tương
ứng của phương pháp thực thi truy vấn không đảm bảo tính riêng tư người
dùng của Hacigümüs và cộng sự; thời gian thực thi truy vấn phía máy chủ
12
(SC) cao hơn không đáng kể, và tùy thuộc vào giá trị tham số m hoặc kích
thước phân hoạch. Chi phí SC và CC đối với phép kết khi dùng UPP gần
giống như chi phí tương ứng khi thực thi phép kết trên CSDL rõ. Điều này
chứng tỏ UPP hoàn toàn có thể áp dụng trong thực tế.
CHƯƠNG 3 - BẢO VỆ TÍNH RIÊNG TƯ DỮ LIỆU –
CƠ CHẾ QUẢN LÝ TRUY CẬP MỨC CỘT
3.1 Bài toán quản lý truy cập trong ODBS
Tính riêng tư dữ liệu được đảm bảo bằng cách sử dụng một cơ chế quản lý
truy cập. Yêu cầu của bài toán quản lý truy cập trong ODBS là đề xuất cơ chế
để hệ thống cho phép người dùng chỉ có thể truy cập được trên các đơn vị dữ
liệu được DO cấp quyền. Qua khảo sát hiện trạng, chúng tôi nhận thấy rằng,
cần đề xuất giải pháp cho việc quản lý truy cập mức cột giúp DO giới hạn
quyền truy cập trên những cột dữ liệu nhạy cảm. Với hướng nghiên cứu này,
chúng tôi đã công bố các công trình sau: FGAC (Fine-grained Access
Control) – cơ chế quản lý truy cập mức cột [CT7]; thực nghiệm đánh giá
FGAC [CT4]; EFGAC (Enhanced Fine-grained Access Control) – là cơ chế
cải tiến của FGAC [CT3].
Bộ tiêu chí xây dựng cơ chế quản lý truy cập
Một giải pháp quản lý truy cập được đánh giá dựa trên một số tiêu chí phổ
biến như sau:
(1) Độ mịn của đơn vị dữ liệu mà giải pháp có thể giới hạn truy cập (quan
hệ, dòng, cột).

• Bước 3: Xây dựng EFGAC nhằm khắc phục thêm hạn chế thứ 3 của
FGAC.
3.3.1 Chứng minh tính đúng đắn
Định nghĩa 3.1 (Hàm suy dẫn khóa)
G
ọi K là tập hợp các khóa dùng trong hệ thống. T là tập hợp những token
công khai, H là không gian các giá trị băm.
Hàm suy dẫn khóa trực tiếp ε: K → H được định nghĩa như sau:

14
ε(k
i
) = {k
j
∈ K | ∃t
i,j
∈ T}.
Hàm suy dẫn khóa ε
*
: K → H là hàm sao cho ε
*
(k
i
) trả về tất cả các khóa
suy dẫn từ k
i
dùng chuỗi các token, và bao gồm cả k
i
.
Hình 3.2 Hình minh họa việc gán khóa và suy dẫn khóa dùng token

thống phải giữ khi áp dụng EFGAC sau cải tiến 1, EFGAC sau cải tiến 3
và cơ chế quản lý truy cập đề xuất bởi El-khoury và cộng sự [19] – từ
đây sẽ được đề cập đến với tên gọi là El-khoury’s.
(iv) So sánh thời gian suy dẫn khóa trung bình để truy cập 1 dòng dữ liệu khi
áp dụng EFGAC sau cải tiến 1 và cải tiến 2 với thời gian suy dẫn khóa
trung bình dùng phương pháp suy dẫn khóa dùng hàm một chiều.

Hình 3.3 So sánh thời gian mã dữ liệu bởi CRT so với RSA, DES và AES 16

Hình 3.4 Biểu đồ so sánh thời gian hồi đáp truy vấn cho Q1 CHƯƠNG 4 - XÁC THỰC VÀ GHI NHẬT KÝ HỆ THỐNG TRONG ODBS
4.1 Xác thực trong ODBS
4.1.1 Bài toán xác thực trong ODBS
Qua phân tích hiện trạng, chúng ta cần xây dựng cơ chế xác thực dùng
trong ODBS thỏa: là quá trình xác thực lẫn nhau giữa máy chủ và người
dùng, thông tin về tài khoản của người dùng phải được giữ bí mật đối với
máy chủ, có khả năng chống lại những tấn công phổ biến của một cơ chế xác
thực [3]. Chúng tôi đã xây dựng cơ chế xác thực đáp ứng mục tiêu đặt ra trên
cơ sở vận dụng mô hình mã hóa theo từ khóa phục vụ tìm kiếm dựa trên ma
tr
ận giả nghịch đảo (PEKS-PM). Kết quả này được công bố ở [CT5].

Hình 3.7 Thời gian suy dẫn khóa
trung bình để người dùng truy
cập một dòng dữ liệu khi dữ liệu
thay đổi: (a) Số nhóm người d

dùng đến máy chủ. Dữ liệu lưu tại DO gồm:
• <un, PEKS(A
pub
, un)>: tên đăng nhập của từng người dùng và giá trị
mã hóa tương ứng của tên đăng nhập. PEKS(A
pub
, un) được DO gửi
đến người dùng và máy chủ phục vụ cho quá trình lưu dữ liệu và xác
thực sau này.
4.1.2.2 Giai đoạn xác thực
Giai đoạn xác thực gồm các bước:
• Bước 1: Tại máy khách C, người dùng U thông qua màn hình đăng
nhập, nhập vào tên đăng nhập un và mật khẩu pw. Vì lý do bảo mật,
C không gửi thông tin đăng nhập dạng rõ đến máy chủ S mà gửi
Trapdoor T
W
cho S, trong đó T
W
được tính dựa vào khóa bí mật A
priv

c
ủa U theo công thức: T
W
= Trapdoor (A
priv
, un). C phát sinh ngẫu
nhiên giá trị N
U
. C gửi T

, U biết chắc rằng S thực sự là máy chủ mà U muốn
kết nối đến vì chỉ có S mới tìm đúng tên đăng nhập và mật khẩu của
U (thông qua giá trị trapdoor, tìm trên các từ mã dùng thuật toán
PEKS) để tính đúng giá trị của H. Trường hợp H ≠ H
1
, U hủy kết nối
vì có kẻ đang mạo danh S. U tính H
2
= h(h(pw) || (N
S
+1)) và gửi H
2
đến S.
Hình 4.1 Dữ liệu dùng cho cơ chế xác thực

DO

Ngư
ời d
ùng


un
2
PEKS(A
pub
2
, un
2
)
… …
un
n
PEKS(A
pub
n
, un
n
)

S_USERS
E_UN H_PW
PEKS(A
pub
1
, un
1
) h(pw
1
)
PEKS(A
pub

4.1.2.3 Phân tích độ an toàn
Tính chất hai chiều của cơ chế xác thực đề nghị không chỉ giúp máy chủ
xác thực quyền đăng nhập của người dùng mà còn giúp người dùng xác thực
máy chủ mà họ muốn giao tiếp để tránh trường hợp tin tặc giả mạo máy chủ
lấy cắp thông tin hoặc chiếm quyền điều khiển (hijacking attacks).
Trong quá trình xác thực, tên đăng nhập của người dùng được mã hóa khi
gửi đến máy chủ nên nghi thức xác thực đề nghị đảm bảo thông tin là bí mật,
loại bỏ được tấn công kiểu nghe lén dữ liệu trên đường truyền. Yếu tố ngẫu
nhiên N
U
và N
S
thay đổi sau mỗi lần thực hiện xác thực nhằm ngăn chặn tấn
công kiểu lặp lại (replay attacks). Chúng tôi đề nghị sử dụng hàm băm SHA-
1 hoặc MD5 trong nghi thức xác thực đề nghị; các giá trị ngẫu nhiên cũng
được tạo bằng cách vận dụng các hàm băm này. Khi sử dụng PEKS-PM, kết
quả cho bởi thuật toán Trapdoor (và PEKS) là khác nhau sau mỗi lần thực thi
lại, cho dù dùng cùng tham số đầu vào; điều này giúp nghi thức xác thực đề
xuất có thể chống lại tấn công từ điển (dictionary attacks).
4.2 Ghi nhật ký hệ thống trong ODBS
4.2.1 Bài toán ghi nhật ký hệ thống trong ODBS
Yêu cầu đặt ra đối với cơ chế ghi nhật ký trong ODBS: đảm bảo tính bí
mật dữ liệu, đảm bảo tính riêng tư người dùng, có khả năng cung cấp thông
tin liên quan đến quá trình làm việc của các thực thể trong hệ thống khi cần
thiết. Các yêu cầu này đặt ra có vẻ như trái ngược nhau [7].
Do có hiệu năng cao và có thể ngăn chặn tấn công từ điển (dictionary
attacks), t
ấn công thống kê tần suất (frequency attacks), PEKS-PM được

21

tin liên quan đến tính bí mật dữ liệu và tính riêng tư người dùng. C
phải giấu M trước khi gửi đến S dùng thuật toán mã hóa theo từ khóa
của PEKS. M được mã hóa thành M
S
.
• Máy chủ S: lưu dữ liệu nhật ký do C gửi đến dưới dạng đã mã hóa
M
S
. Do đặc tính của việc dùng PEKS, dù S không đọc được nội dung
của M nhưng khi cung cấp giá trị trapdoor của một từ khóa W cần
tìm , S có thể tìm kiếm trong dữ liệu nhật ký những mẩu tin có chứa
W.
4.2.2.2 Giai
đoạn ghi nhật ký
• T phát sinh cặp khóa (A
pub
, A
priv
) dùng thuật toán KeyGen của PEKS.
A
pub
được gửi công khai cho tất cả những người dùng trong hệ thống.

22
• Tùy mục đích ghi nhật ký được thiết lập ở ứng dụng phía máy khách,
chuỗi M ứng với thao tác của người dùng U được trích ra các từ khóa
phù hợp, M được máy khách C mã theo các từ khóa đó thành M
S

dùng thuật toán mã PEKS. Sau đó C gửi M

đến máy chủ S.
• Bước 3: Trên dữ liệu nhật ký dạng mã, S tìm và trả về cho T tất cả các
M
S
có chứa W dùng thuật toán kiểm tra Test.
23
• Bước 4: T giải mã các dòng M
S
nhận được từ S và trả kết quả cho B.
4.2.2.4 Phân tích kết quả đạt được
Về bảo mật
Bằng cách định nghĩa năm vai trò và phân công công việc cho từng vai trò
như đã trình bày ở trên, bài toán ghi nhật ký phục vụ giải trình trong ODBS
đã được giải quyết. Dữ liệu nhật ký không chỉ chứa đựng thông tin về nội
dung CSDL mà còn chứa đựng thông tin về tính riêng tư người dùng (ai, truy
cập vấn đề gì, kết quả là gì). Máy chủ không thể truy cập nội dung dữ liệu
nhật ký nên tính bí mật dữ liệu và tính riêng tư người dùng được đảm bảo.
Dù vậy, máy chủ vẫn có thể thực hiện vai trò tìm kiếm và trả về kết quả cần
tìm, tức là vẫn đảm bảo ý nghĩa của ODBS. DO, mặc dù là chủ sở hữu dữ
liệu nhưng không được quyền truy cập dữ liệu nhật ký để bảo vệ tính riêng tư
người dùng.
Về hiệu quả
Xét một CSDL nhật ký có N
L
mẩu tin, mỗi mẫu tin được trích ra k
L
từ