Quản lý và thay đổi khóa cơ sở dữ liệu mã hóa trên môi trường thuê ngoài
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
QUẢN LÝ VÀ THAY ĐỔI KHÓA
CƠ SỞ DỮ LIỆU MÃ HÓA TRÊN
MÔI TRƯỜNG THUÊ NGOÀI
Hồ Kim Giàu1, Nguyễn Hiếu Minh2
Tóm tắt
Chủ sở hữu dữ liệu thuê ngoài dịch vụ cơ sở dữ liệu (Outsourced database) luôn muốn
bảo vệ thông tin (tránh bị đánh cắp, sửa đổi dữ liệu,...) trước kẻ tấn công trên môi trường
internet và kể cả từ nhà cung cấp dịch vụ. Để bảo vệ dữ liệu của mình, nhất là các thông tin
quan trọng, người chủ sở hữu dữ liệu dùng phương pháp mã hóa dữ liệu trước khi lưu trữ lên
đám mây. Khi khai thác dữ liệu, người dùng truy vấn thông tin trên dữ liệu mã và sử dụng
khóa được cung cấp bởi chủ sở hữu để giải mã kết quả truy vấn. Trong mô hình đa người
dùng, chủ sở hữu phải có chiến lược quản lý và phân phối khóa để hạn chế quyền truy cập
của các cá nhân khai thác dữ liệu, đồng thời phải có phương pháp thay đổi khóa phù hợp để
tránh tấn công do lộ thông tin khóa từ người dùng. Một phương pháp đổi khóa ngây thơ là
tải toàn bộ cơ sở dữ liệu về để giải mã, đổi khóa rồi mã hóa, cập nhập lại dữ liệu. Nếu cơ
sở dữ liệu lớn, cách tiếp cận này sẽ tốn nhiều thời gian xử lý và tài nguyên hệ thống. Trong
bài báo này, chúng tôi giới thiệu mô hình quản lý truy cập đa người dùng và đề xuất phương
pháp thay đổi khóa trên mô hình quản lý khóa mức cột. Kết quả thực nghiệm chứng minh
được hiệu quả của phương pháp đề xuất và có khả năng áp dụng vào thực tế.
Từ khóa
Cơ sở dữ liệu thuê ngoài; bảo mật dữ liệu; khóa người dùng; quản lý khóa, thay khóa.
1. Giới thiệu
Điện toán đám mây ra đời và phát triển nhanh chóng đã xuất hiện nhiều dịch vụ, giải
pháp hữu ích trong đó thuê ngoài cơ sở dữ liệu là dịch vụ cung cấp cho người dùng giải
pháp thiết yếu để giảm chi phí lưu trữ, bảo trì cơ sở dữ liệu. Khi cơ sở dữ liệu (CSDL)
được đưa lên dịch vụ thuê ngoài thì người chủ sở hữu dữ liệu (Data Owner - DO) giao
toàn quyền lưu trữ, quản trị cho nhà cung cấp dịch vụ (Database Service Provider –
DSP); như vậy, DSP có thể xem được nội dung dữ liệu của DO, điều này vi phạm tính
bí mật dữ liệu, đặc biệt là các dữ liệu nhạy cảm như: thông tin cá nhân, tài khoản ngân
hàng... Ngoài ra, có nhiều kẻ tấn công trên môi trường internet luôn luôn muốn khai
thác, đánh cắp dữ liệu. Để đảm bảo được tính bí mật của dữ liệu, DO phải có biện
pháp ngăn chặn sự truy cập trái phép trong quá trình lưu trữ và khai thác CSDL.
1Học viện Kỹ thuật quân sự, 2Học viện Kỹ thuật mật mã
77
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
Dữ liệu mã hoá
Người dùng
Internet
Nhà cung cấp dịch vụ
thuê ngoài CSDL
Chủ sở hữu
dữ liệu
Hình 1. Mô hình bảo mật thuê ngoài cơ sở dữ liệu
Giải pháp thông thường để bảo vệ CSDL trên dịch vụ thuê ngoài là mã hóa dữ liệu.
Hacigumus [1] là người đầu tiên đưa ra giải pháp thực hiện truy vấn trên CSDL đã
được mã hóa. Cơ chế mã hóa cơ sở dữ liệu của Hacigumus là mã hóa theo từng bản
ghi, và dùng bộ chuyển đổi truy vấn kết hợp với các chỉ mục được lưu trữ phía người
dùng để thực hiện tính toán trên dữ liệu mã hóa. Việc định nghĩa các chỉ mục do DO
đặt ra và không có cơ chế phân quyền và quản lý khóa. A. Popa và cộng sự [2] trình
bày một mô hình mã hóa và cách thức thực thi truy vấn trên CSDL mã hóa bằng cách
sử dụng một máy chủ làm trung gian gọi là CryptDB proxy. CryptDB proxy quản lý
lược đồ CSDL và thực hiện chuyển đổi câu truy vấn giữa người dùng và DSP. Máy chủ
DSP lưu trữ một lược đồ ẩn danh (tên bảng và tên cột được thay thế bằng định danh),
dữ liệu người dùng được mã hóa, và một số bảng phụ trợ được sử dụng bởi CryptDB.
Mỗi một trường CSDL rõ sẽ được mã hóa thành nhiều lớp củ hành (onion) phục vụ
nhiều mục đích truy vấn tương ứng. khóa bí mật được quy định bởi DO và lưu trữ ở
CryptDB proxy. Tuy nhiên, đề xuất này chưa đưa ra phương pháp thay đổi khóa bí mật
khi nghi ngờ mất an toàn. Các nghiên cứu [3], [4], [5], [6] dùng cấu trúc cây (XML)
lưu trữ các thông tin phụ trợ để hỗ trợ truy vấn hoặc truy vấn trực tiếp trên dữ liệu mã.
Tuy nhiên, các nghiên cứu này chỉ dùng chung một khóa mã hóa cho toàn bộ CSDL.
Điều này có thể dẫn đến sự tấn công theo kiểu bắt tay: nếu người dùng có khóa mã và
nhân viên của nhà cung cấp dịch vụ có toàn bộ cơ sở dữ liệu thì họ có thể thoả hiệp
để giải mã tất cả dữ liệu mà bỏ qua các bước xác thực khi truy cập.
Để hạn chế khả năng truy cập dữ liệu của người sử dụng, DO phải bổ sung các cơ
chế quản lý truy cập (FAGC: Fine-Grained Access Control) cho nhiều người dùng với
nhiều quyền khác nhau. Có nhiều mức độ kiểm soát truy cập: mức cơ sở dữ liệu (toàn
quyền truy cập CSDL), mức bảng, mức cột, mức dòng. Trong đó mức cơ sở dữ liệu
là đơn giản nhất với một khóa chung nhưng dễ bị rò rỉ thông tin nếu khóa bị lộ. Mức
dòng là là mức bảo mật cao nhất nhưng khó quản lý do cần nhiều khóa và tốn nhiều
thời gian sinh khóa. Hong và cộng sự [7] đã đề xuất cây RST (Resource Set Tree) để
quản lý khóa truy cập người dùng. Cây RST là cây mà mỗi nút lá chứa một danh sách
các lớp người dùng có cùng quyền truy cập vào tập dữ liệu, tuy nhiên phương pháp
này không đưa ra mối quan hệ giữa người dùng với khóa mã của CSDL. Hang và cộng
sự [8] đã đề xuất mô hình ENKI cho phép quản lý quyền truy cập. Khi người dùng đã
được xác thực bởi máy chủ thì họ sẽ có được khóa chính (masterkey) để giải mã khóa
78
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
mã hóa được lưu trữ trong tập khóa. Hang dùng trình điều khiển JDBC (có sửa đổi)
để viết lại câu truy vấn để thực thi câu truy vấn trên dữ liệu mã. Tuy nhiên, phương
pháp này không đề xuất việc thay đổi khóa mã hóa của CSDL.
Các phương pháp nghiên cứu sinh khóa và quản lý truy cập của người dùng chưa
quan tâm giải quyết bài toán thay khóa cho cơ sở dữ liệu thuê ngoài khi cần thiết như:
lộ khóa từ người dùng hay thu hồi quyền người dùng... Điều này dẫn đến tính bí mật
dữ liệu có thể không còn nhiều ý nghĩa. Trong các vấn đề liên quan đến tính bí mật dữ
liệu, thì bài toán phân phối khóa và bài toán thay khóa là những bài toán quan trọng
góp phần bảo vệ dữ liệu trước sự tấn công trên môi trường internet.
Trong phạm vi nghiên cứu này, nhóm đề xuất giải pháp quản lý truy cập của người
dùng theo mức cột. Cách tiếp cận này vẫn bảo bảo tính an toàn cho CSDL mà thời gian
sinh khóa, truy cập khóa nhanh. Bên cạnh đó, bài báo cũng đề xuất phương pháp thay
khóa cho dữ liệu với thời gian thực hiện ngắn, đáp ứng được tính sẵn sàng của dữ liệu.
Phần còn lại của bài báo được trình bày như sau: Phần 2 trình bày tổng quan về các
bài toán liên quan đến khóa mã và quyền truy cập của người dùng, phần 3 đề xuất mô
hình quản lý khóa và cơ chế truy cập dữ liệu của người dùng, phần 4 đề xuất phương
pháp đổi khóa mức cột, phần 5 là kết quả chứng minh tính hiệu quả của phương pháp
đề xuất, cuối cùng là kết luận và hướng nghiên cứu tiếp theo.
2. Tổng quan
2.1. Bài toán phân phối khóa
Khóa mã là một vấn đề quan trọng trong bài toán bảo mật. Khóa dùng để mã hóa -
giải mã dữ liệu theo một thuật toán mã hóa cho trước. Cho một CSDL có t bảng, giả
sử một bảng có m cột và n bản ghi. Nếu ta thực hiện mã hóa theo mức dòng và phân
phối khóa cho U người dùng thì số lượng khoá tối đa cần phải quản lý là t × n × U .
Cụ thể như trong bài toán quản lý điểm của sinh viên, CSDL được mã hóa để bảo
đảm nếu người quản trị vào được CSDL cũng không thể sửa đổi điểm của sinh viên.
Mỗi giáo viên có quyền xem và sửa điểm của mình dạy nên được cấp một khóa để mã
hóa - giải mã điểm. Khi tính điểm trung bình, hệ thống phải cần tất cả các khóa của
giáo viên có liên quan để giải mã điểm trước khi tính toán.
Mã hóa dữ liệu theo mức cột (trường) thì tính bảo mật dữ liệu thấp hơn mức dòng do
các dữ liệu trong cùng một cột sẽ dùng chung một khóa mã. Như vậy, số lượng khóa mã
cần có là: t×m. Tuy nhiên, ta cần có một cơ chế quản lý truy cập để hạn chế quyền của
người dùng vào các cột dữ liệu tương ứng. Giả sử với bảng T (f1, f2, . . . , fm), người
dùng u muốn truy cập vào thuộc tính fi thì phải có khóa ki, i = 1, ..., m.
2.2. Bài toán thay khóa
Bài toán thay khóa là quá trình thực hiện thay đổi lại khóa mã của các dữ liệu mã
hóa trên cơ sở dữ liệu thuê ngoài. Bài toán này thường được đặt ra trong trường hợp
79
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
Bảng 1. Ma trận kiểm soát truy cập cho bảng t1.
f1 f2 ... fm
u1
u2
0
1
1
1
...
...
1
0
.
.
.
up
1
0
...
1
DO muốn lấy lại quyền của các người dùng hoặc lo ngại khóa người dùng không còn
an toàn. Một phương pháp ngây thơ (naive method) có thể nghĩ đến là:
• Bước 1: DO tải toàn bộ CSDL về máy chủ của mình,
• Bước 2: Giải mã CSDL bằng khóa đã có,
• Bước 3: Mã hóa toàn bộ dữ liệu bằng khóa mã mới,
• Bước 4: Lưu trữ dữ liệu được mã hóa lên CSDL thuê ngoài.
Vấn đề đặt ra là nếu CSDL có dung lượng lớn (đơn vị từ Gigabytes, Terabytes...) thì
phương pháp ngây thơ sẽ tốn rất nhiều thời gian và có thể không thực hiện được. Thuật
toán đổi khóa ngây thơ đã được đề xuất trong nghiên cứu [9] và thời gian thực hiện đã
mô tả khả năng thực thi của phương pháp này.
2.3. Quản lý quyền truy cập dữ liệu
Quản lý quyền truy cập dữ liệu là bài toán bảo vệ tính riêng tư dữ liệu. Nghĩa là,
người dùng chỉ được phép truy cập vào những dữ liệu mà DO cấp quyền. Trong mô
hình dữ liệu thuê ngoài, nếu DO phân quyền người dùng bằng các bảng CSDL và lưu
trên đám mây thì DSP có thể xâm hại mà không thông qua cơ chế quản lý truy cập.
Như vậy, muốn tăng tính an toàn cho CSDL, một đề xuất được đặt ra là DO phân quyền
và quản lý truy cập trên máy chủ của mình, đồng thời DO phải kiểm tra quyền của
người dùng trước khi cho phép người dùng truy vấn đến dữ liệu thuê ngoài.
Để quản lý quyền truy cập dữ liệu của người dùng, DO dùng ma trận kiểm soát truy
cập. Cho bảng T (f1, f2, . . . , fm), và người dùng U (u1, u2, ..., up). Ma trận kiểm soát
truy cập A được biểu diễn như bảng 1 Trong đó, nếu A [i, j] = 1 thì người dùng thứ i
được truy cập vào cột dữ liệu thứ j với 1 ≤ i ≤ p, 1 ≤ j ≤ m. Ngược lại, A [i, j] = 0
nghĩa là người dùng thứ i không được truy cập vào cột dữ liệu thứ j. Tuỳ vào bài toán
phân quyền cụ thể mà ma trận kiểm soát truy cập sẽ thay đổi các cột f1, f2, . . . , fm
thành mức bảng, dòng... Véc-tơ quyền truy cập người dùng ui = f2, f3, fk, ... nghĩa là
người dùng thứ i được quyền truy xuất vào các cột f2, f3, fk... Véc-tơ quyền truy cập
cột fi = {u1, u3, uk, ...} nghĩa là người dùng 1, 2, k... được quyền truy cập vào cột
thứ i.
80
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
Hình 2. Cây quản lý khóa KMT của CSDL
3. Quản lý khóa và truy cập dữ liệu của người dùng
3.1. Mô hình quản lý khóa
Xét một bảng T (f1, f2, . . . , fm) với f1, f2, . . . , fm là các thuộc tính; T chứa n bản
ghi r = (ri1, ri2..., rim), trong đó rijlà dữ liệu tại dòng thứ i và cột thứ j với 1 ≤ i ≤ n,
1 ≤ j ≤ m.
Mã hóa dữ liệu mức cột Ek của thuộc tính f với khóa k được định nghĩa như sau:
:
Ek(f) = {Ek(ri)|ri ∈ f; i = 1, ..., n}
(1)
Mã hóa của bảng T (f1, f2, . . . , fm) là mã hóa tất cả các thuộc tính f1, f2, . . . , fm
và các dữ liệu trong các thuộc tính đó:
:
E(T ) = (Ek (f1), Ek (f2), ..., Ek (fm))
1
2
m
= {Ek (ri1), Ek (ri2), ..., Ek (rim)|rij ∈ fj; i = 1, ..., n; j = 1, ..., m}
(2)
1
2
m
Trong công thức (2), tập K (k1, k2, ..., km) là tập khóa mã của bảng T . Ta gọi K
là tập khóa mã theo mức cột của T .
Có nhiều hình thức tổ chức quản lý khóa mã, trong đó dùng cây (tree) để quản lý
khóa là một phương pháp dễ xây dựng, truy xuất nhanh. Mỗi cơ sở dữ liệu sẽ có một
cây quản lý khóa gọi là cây KMT (Key Management Tree). Nút gốc (mức 1) của cây
KMT là tên cơ sở dữ liệu, mức 2 là tên các bảng, mức 3 là tên các trường và nút lá
là các khóa của cột. Cây KMT quản lý tập trung các khóa của các cột trong CSDL,
dễ dàng quản lý, thay đổi khóa khi cần thiết thay vì giao các khóa cho người dùng.
Muốn truy xuất đến một khóa bất kỳ của một cột trong bảng, ta chỉ cần biết tên bảng
và tên cột. Khi kết hợp cây KMT với ma trận kiểm soát truy cập (bảng 1), người dùng
sẽ được phép truy cập vào cột với khóa của cột trong cây KMT. Cho CSDL DB gồm
2 bảng t1(f11, f12, f13), t2(f21, f22) và các tập khóa mã mức cột của bảng t1, t2
tương ứng là K1(k11, k12, k13), K2(k21, k22). Cây KMT được biểu diễn như hình 2,
trong đó các giá trị 0, 1, 2... là thứ tự của các nút trên cây. Khi tổ chức cấu trúc dữ
liệu, ta có thể biểu diễn KMT bằng một mảng quản lý khóa như bảng 2. Giả sử mỗi
nút có cấu trúc Node (Label, index). Ta dùng mảng K chứa các nút và IX là vị trí của
nút X trong mảng K.
81
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
Bảng 2. Cấu trúc quản lý khóa của cây MHT
0
1
2
3
4
5
6
7
8
9
10
11
12
← Chỉ số mảng
DB t1 t2 f11 f12 f13 f21 f22 k11 k12 k13 k21 k22 ← Nhãn của nút trên cây
-1
← Chỉ số nút cha
0
0
1
1
1
2
2
3
4
5
6
7
(=-1 nếu nút không có cha)
Tính chất:
• Nếu R là nút gốc, thì IR = −1
• Nút B là con nút A thì B.index = IA
Mặc dù DO quản lý và lưu trữ cây khóa trên server của mình nhưng để tránh trường
hợp nhân viên của mình can thiệp bất hợp pháp, DO cũng phải mã hóa cây khóa bằng
khóa MK riêng của mình. Quá trình tạo cây KMT được đề xuất trong thuật toán 1.
Algorithm 1 . Thuật toán tạo cây khóa KMT
Input: Outsourced database name
Output: Encrypted KMTree
1: KMTree ← createRoot("Database", "DBName", DBname);
2: tableName ← getTableName(DBname);
3: for each tb ∈ tableName do
4:
5:
tNode ← createNode("Table", "TableName", tb);
KMTree.appendChild(tNode);
fieldName ← getColumnName(DBname, tb);
for each f ∈ fieldName do
6:
7:
8:
key ← KeyGen(λ)
9:
tNode.addNode("Field", "FieldName", f, key)
end for
10:
11: end for
12: Outfile ← Encrypt(KMTree)
Số lượng bảng trong cơ sở dữ liệu là Sd, số cột trong mỗi bảng khác nhau, với Sf là
số lượng cột lớn nhất của một bảng. Ta quy ước thời gian tạo khóa của hàm KeyGen()
là tg; Thao tác thêm nút vào cây là thao tác gán chỉ số nút cha cho nút con tk. Độ phức
Sf
Sd
P P
tạp thời gian tính toán của thuật toán 1 là: O =
max(SdSf tg, SdSf tk).
(tg + tk) = SdSf tg + SdSf tk =
n=1
f=1
3.2. Mô hình quản lý truy cập dữ liệu của người dùng
Mỗi người dùng có quyền truy cập dữ liệu mức cột khác nhau do DO quản lý. Như
vậy, để truy cập các cột được cấp phép thì người dùng phải được cung cấp các khóa của
các cột tương ứng. Điều này dẫn đến việc một người dùng phải giữ rất nhiều khóa. Các
nghiên cứu [10], [7] đã đề xuất phương pháp suy dẫn khóa người dùng bằng thuật toán
82
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
KMT
Máy chủ DO
1
Thông tin người dùng
Khoá của u
+ câu truy vấn
i
f1
f2
...
fm
0
Ma trận kiểm soát truy cập
f1 f2 ... fm
k11 k12 ...
Kết quả truy vấn
(qua TLS)
Người dùng
ui
1
1
... 0
4
Khoá giải mã
2
3
Nhà cung cấp dịch vụ
thuê ngoài CSDL
Hình 3. Mô hình truy cập dữ liệu của người dùng
CRT (Chinese Remainder Theorem) và quản lý khóa bằng cây nhị phân; Tuy nhiên, số
lượng khóa người dùng cần giữ khi truy cập dữ liệu vẫn nhiều. Bên cạnh đó, việc sinh
khóa và suy dẫn khóa vẫn tốn nhiều thời gian nếu số lượng người dùng thay đổi liên
tục. Để giải quyết vấn đề này, chúng tôi đề xuất giải pháp người dùng chỉ sử dụng ID
người dùng, mật khẩu đăng nhập mà không giữ các khóa mã của CSDL. Khi người
dùng ui truy vấn dữ liệu và được máy chủ DO xác thực thì DO dựa vào ma trận quản
lý truy cập A để có được các tên cột dữ liệu mà ui có thể truy cập, đồng thời giải mã
cây KMT từ đó biết được các khóa của các cột tương ứng quyền truy cập người dùng
và tạo ra một bảng khóa tạm thời Ku . Bảng Ku này giữ ở máy chủ DO và không can
i
i
thiệp được từ người dùng. Sau đó, ui truy vấn dữ liệu theo ma trận kiểm soát truy cập
để lấy thông tin cần thiết và DO giải mã dữ liệu này bằng các khóa ở bảng Ku . Việc
trao đổi thông tin người dùng, kết quả truy vấn trả về giữa người dùng và máy cihủ DO
thông qua giao thức TLS (Transport Layer Security) để bảo đảm dữ liệu không bị tấn
công theo dạng man in the middle. Cơ chế truy cập dữ liệu của người dùng được thực
hiện qua 4 bước như sau:
• Bước 1: Người dùng gửi thông tin người dùng thông qua giao thức TLS. Sau khi
được máy chủ xác thực, người dùng gửi câu truy vấn dữ liệu đến máy chủ DO.
Máy chủ dựa vào ma trận kiểm soát truy cập và dùng khóa mã DO để giải mã cây
KMT. Từ đó, máy chủ đưa ra được bảng khóa của người dùng.
• Bước 2: Máy chủ DO dựa vào ma trận kiểm soát truy cập để truy vấn các cột dữ
liệu mà người dùng được phép truy cập trên DSP.
• Bước 3: DSP trả kết quả truy vấn là dữ liệu mã hóa về máy chủ DO.
• Bước 4: Máy chủ DO dựa vào bảng khóa của người dùng và giải mã dữ liệu, trả
kết quả dữ liệu rõ về cho người dùng thông qua giao thức TLS.
Với cơ chế truy cập dữ liệu của người dùng được đề xuất thì người dùng chỉ quản lý
thông tin người dùng mà không nắm giữ bất kỳ thông tin khóa của cây khóa KMT nên
không thể tấn công theo hình thức thoả hiệp. Bên cạnh đó, do cây khóa được quản lý ở
máy chủ DO và số lượng khóa tương ứng với số cột của các bảng trong cơ sở dữ liệu
83
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
nên việc thay khóa tương đối dễ dàng, không ảnh hưởng và cũng không phụ thuộc đến
người dùng tham gia trong hệ thống.
4. Phương pháp đổi khóa cơ sở dữ liệu mã hóa
4.1. MapReduce
MapReduce là một mô hình lập trình cho phép xử lý khối lượng dữ liệu lớn bằng
cách chia công việc thành các nhiệm vụ độc lập và thực hiện các tác vụ song song
thông qua các cụm máy tính (cluster) [11]. Lợi thế lớn nhất của một chương trình được
thực hiện bằng MapReduce là nó chạy trên bất kỳ nút (node) nào trong trung tâm xử
lý (một, hàng trăm hay hàng nghìn nút) mà không quan tâm đến mã lệnh của chương
trình. Lập trình MapReduce là việc tạo ra hai hàm map() và reduce(), mỗi hàm được
thực hiện song song trên các nút tính toán.
Giai đoạn đầu của MapReduce là giai đoạn map. MapReduce sẽ tự động phân chia
dữ liệu đầu vào cho các nút tính toán trong trung tâm dữ liệu. Mỗi nút tính toán đều
chạy một hàm map() với mục đích là chia nhỏ dữ liệu Trong giai đoạn map, hàm map()
xử lý đầu vào là các cặp khóa-giá trị (key-value), tạo ra các cặp khóa-giá trị trung gian
và được chuyển thành đầu vào cho giai đoạn reduce.
Giai đoạn thứ hai là giai đoạn reduce. Giai đoạn này tổng hợp và xử lý các dữ liệu
trung gian từ giai đoạn map. Reduce cũng được thực hiện trên các nút tính toán, mỗi
nút đều nhận một khóa, tuỳ thuộc vào giá trị ở giai đoạn map mà chia sẻ các khóa này
cho các nút xử lý, sau đó tổng hợp lại thành một giá trị cho mỗi khóa.
4.2. Đề xuất phương pháp đổi khóa mức cột
Thay đổi khóa mã của cơ sở dữ liệu mã hóa nhằm mục đích bảo vệ dữ liệu trước
nguy cơ bị lộ khóa. Đây là bài toán tốn nhiều thời gian xử lý và bộ nhớ nếu giải quyết
theo phương pháp ngây thơ [9]. Đổi khóa CSDL mức cột là thay đổi khóa cũ của các
cột trong bảng dữ liệu bằng các khóa mới tương ứng của cột đó. Để đổi khóa cho cơ
sở dữ liệu mã hóa, ta phải tạo ra cây khóa KMT mới (bài toán tổng quát là thay đổi
khóa của tất cả các cột trong bảng, các trường hợp riêng như thay đổi một số cột cụ
thể hoặc mã hóa một số cột nhạy cảm trong CSDL là tập con của bài toán này) và tiến
hành thay khóa cũ bằng khóa mới tương ứng từ cây khóa KMT cũ và KMT mới trên
các dữ liệu trong bảng. Thuật toán đổi khóa của dữ liệu mã hóa ở mức cột thực hiện
trên MapReduce theo 3 bước sau đây:
• Bước 1: Chuyển các bảng từ cơ sở dữ liệu thuê ngoài thành các tập tin có định
dạng HDFS trên hadoop framework.
• Bước 2: Sử dụng MapReduce để thực hiện đổi khóa với các tập tin đầu vào chứa
nội dung là các bảng dữ liệu. Quá trình này được thực hiện song song trên các
cụm máy tính. Dữ liệu đầu ra là các tập tin HDFS (thuật toán 2).
• Bước 3: Cập nhập dữ liệu trong các tập tin HDFS của hadoop lên cơ sở dữ liệu
thuê ngoài.
84
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
Hình 4. Mô hình đổi khóa trên Map-Reduce
Algorithm 2 . Thuật toán MR-EncColumnKeyChange
Input: HDFS file after imported database
Output: HDFS file with key change
1: listOldKey ← getKeyFromKMT("OldKMT.file");
2: listNewKey ← getKeyFromKMT("NewKMT.file");
3: Send (listOldKey, listNewKey) to REDUCE function
4: procedure MAP(key, value)
5:
emit(key, value)
6: end procedure
7: procedure REDUCE(key, value)
8:
list[] ← split key by ’, ’
9:
i=0
10:
11:
12:
13:
14:
15:
16:
for each data ∈ list do
plaintext = DeclistOldKey(i)(data)
ciphertext = EnclistNewKey(i)(plaintext)
newkey.concat(ciphertext + "|")
i++;
end for
emit(newkey, value)
17: end procedure
Quá trình thay khóa dữ liệu mã được mô tả như trong hình 4. Dữ liệu từ các tập tin
HDFS được xử lý qua hai giai đoạn: map và reduce. Giai đoạn map, các dòng dữ liệu
của bản ghi được chia thành nhiều phần và xử lý trên nhiều cụm máy tính(cluster); Giai
đoạn reduce tiến hành giải mã và mã hóa (thay khóa) các giá trị kết quả của giai đoạn
map. Kết thúc hai giai đoạn ta thu được tập tin mã hóa với khóa mã mới.
85
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
Thời gian thực hiện đổi khóa theo mức cột là tổng thời gian của quá trình chuyển
dữ liệu từ CSDL thuê ngoài thành các tập tin định dạng HDFS trên hadoop, thời gian
xử lý thay khóa trên các bảng dữ liệu và thời gian cập nhập dữ liệu từ hadoop lên máy
chủ dịch vụ. Trong đó, ta quan tâm đến thời gian xử lý thay khóa, vì lúc này số lượng
dữ liệu cần xử lý là lớn nhất. Thời gian chuyển đổi dữ liệu từ DSP vào các trung tâm
tính toán của MapReduce và ngược lại phụ thuộc quá trình phân chia xử lý, tính toán
được quản lý bởi các cụm máy tính. Giai đoạn thực hiện đổi khóa mức cột của bảng
CSDL được đề xuất trong thuật toán 2.
Một hàm map() làm việc trên một nút nên số lần thực hiện đồng thời của hàm map()
là x (x là số nút của MapReduce). Thời gian cho một lần lặp dữ liệu trong map() trên 1
nút là n (n là số lượng bản ghi). Như vậy, thời gian cần thực hiện xong map() trên x nút
là n/x. Hàm reduce() thực hiện đổi khóa, nghĩa là giải mã và mã hóa lại dữ liệu nhưng
vẫn giữ nguyên số lượng các bản ghi. Giả sử thời gian giải mã và mã hóa là tkc. Số
lượng cột trong bảng CSDL là Sf . Như vậy, thời gian thực hiện đổi khóa xong mỗi bản
ghi là Sf tkc. Từ đó, ta có thời gian hàm reduce() thực hiện trên x nút là n.Sf tkc/x. Khi
thực hiện xong mỗi map() sẽ tương ứng cho việc thực hiện reduce(). Do đó, độ phức
tạp thời gian tính toán của thuật toán 2 là O(n) = (n/x)(n.Sf tkc/x) = n2Sf tkc/x2.
5. Kết quả thử nghiệm
Để đánh giá mô hình đổi khóa được đề xuất, chúng tôi thực hiện thử nghiệm trên máy
tính CoreTM i7-6700 CPU @ 3.40GHz x 8, Ram 8GB. Hệ điều hành Ubuntu 16.10, bộ
cơ sở dữ liệu của TPC-H [12] với 1GB dữ liệu; Thuật toán mã hóa/giải mã là AES-128
bit chế độ OFB, ngôn ngữ lập trình Java. CSDL của TPC-H có 8 bảng và các cột trong
bảng tương ứng là:
1) nation(n_nationkey, n_name, n_regionkey, n_comment);
2) region(r_regionkey, r_name, r_comment);
3) part(p_partkey, p_name, p_mfgr, p_brand, p_type, p_size, p_container, p_retailprice,
p_comment);
4) supplier(s_suppkey, s_name, s_address, s_nationkey, s_phone, s_acctbal,
s_comment);
5) partsupp(ps_partkey, ps_suppkey, ps_availqty, ps_supplycost, ps_comment);
6) customer(c_custkey, c_name, c_address, c_nationkey, c_phone, c_acctbal,
c_mktsegment, c_comment);
7) orders(o_orderkey, o_custkey, o_orderstatus, o_totalprice, o_orderdate,
o_orderpriority, o_clerk,o_shippriority, o_comment);
8) lineitem(l_orderkey, l_partkey, l_suppkey, l_linenumber, l_quantity, l_extendedprice,
l_discount, l_tax, l_returnflag, l_linestatus, l_shipdate, l_commitdate, l_receiptdate,
l_shipinstruct, l_shipmode, l_comment);
Với cấu trúc bảng cơ sở dữ liệu của TPC-H, chúng tôi tiến hành tạo khóa cho các
cột theo thuật toán 1. Trong đó, thuật toán KeyGen(λ) là thuật toán khởi tạo khóa của
AES. Thời gian tạo cây KMT là 1.534s, dung lượng lưu trữ của cây là 4.8 KB. Cây
86
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
Bảng 3. Thời gian thực hiện đổi khóa của NaiveKeyChange[9]
và 3 bước đổi khóa mức cột trên MapReduce
Bước 2
Đổi khóa(s)
36.312
Thuật toán Naive
KeyChange(s)
6908.127
Bước 1
CSDL→HDFS(s)
18.897
Bước 3
HDFS→CSDL(s)
66.872
Tên bảng Số bản ghi
customer
lineitem
nation
150000
6001215
25
1500000
200000
800000
5
309241.736
1.499
100763.852
9526.048
36963.637
0.595
449.528
218.252
16.571
42.734
28.198
26.125
1376.162
18.670
202.997
43.239
76.680
17.518
4963.679
38.101
618.088
92.563
219.674
orders
part
partsupp
region
21.734
16.766
19.521
25.807
supplier
10000
19.995
KMT là cây quản lý khóa cột của các bảng trong CSDL nên chỉ phụ thuộc vào cấu
trúc CSDL mà không phụ thuộc vào kích thước dữ liệu. Việc tăng kích thước dữ liệu
không ảnh hưởng đến thời gian tạo cây và dung lượng cây.
Quá trình thực hiện thuật toán được đề xuất (thuật toán 2) thay đổi khóa tất cả các
cột dữ liệu trong các bảng CSDL tương ứng với các khóa trong cây KMT cũ và KMT
mới chạy trên nền Hadoop 2.7.0 [13] trên một máy tính. Kết quả thời gian tính toán
được mô tả trong bảng 3.
Thời gian thực hiện đổi khóa mức cột trên MapReduce: tMR = tI + tC + tE; trong
đó tI là thời gian nạp các bảng từ cơ sở dữ liệu thuê ngoài thành các tập tin định dạng
HDFS trên Hadoop, tC là thời gian thực hiện thay đổi khóa trên MapReduce, và tE là
thời gian xuất dữ liệu từ Hadoop lên cơ sở dữ liệu thuê ngoài. Thời gian thực hiện của
thuật toán NaiveKeyChange được trình bày ở [9]. Dựa vào bảng 3, toàn bộ thời gian
đổi khóa của phương pháp đề xuất được so sánh với phương pháp NaiveKeyChange
như hình 5.
Kết quả thực nghiệm cho thấy, khi dữ liệu các bảng có ít bản ghi như region: 5 dòng,
nation: 25 dòng thì thời gian thực hiện ngây thơ nhanh hơn so với phương pháp đề xuất
tương ứng là 0.6s/58.773s, 1.5s/73.342s.
Tuy nhiên, khi các bảng có số lượng bản ghi đáng kể như supplier với 10.000 dòng
thì thời gian thực hiện của phương pháp ngây thơ là 7.48 phút trong khi phương pháp
đề xuất chỉ 62.568s. Thậm chí đối với bảng orders có 1.5 triệu bản ghi thì thời gian
thực hiện của phương pháp ngây thơ ≈ 28 giờ, quá lớn so với 14 phút của phương pháp
đề xuất. Hình 5 cho thấy thời gian thực hiện trên số lượng bản ghi lớn thay đổi không
đáng kể so với số lượng bản ghi nhỏ. Nghĩa là khi dữ liệu càng lớn, hiệu quả phương
pháp đề xuất càng cao.
Khi số lượng bản ghi khoảng 6 triệu (bảng lineitem) phương pháp ngây thơ thực hiện
khoảng 3.5 ngày, quá lâu để tạo một phiên bảo trì CSDL và xem như không khả thi
cho tính sẵn sàng của dữ liệu, trong khi phương pháp đề xuất thực hiện đổi khóa trong
khoảng thời gian 1.8 giờ.
87
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
350,000
Đổi khoá ngây thơ
Đổi khoá mức cột đề xuất
300,000
250,000
200,000
150,000
100,000
50,000
0
5
25
10,000
150,000
200,000
800,000 1,500,000 6,001,215
Số lượng bản ghi (dòng)
Hình 5. Kết quả thực hiện đổi khóa ngây thơ và đề xuất.
6. Kết luận
Chủ sở hữu bảo vệ dữ liệu của mình trước các nguy cơ tấn công bằng cách mã hóa
dữ liệu và bảo vệ các khóa mã, quản lý quyền truy cập. Khi các khóa mã không còn
an toàn, chủ sở hữu phải thay khóa. Trong bài báo này, chúng tôi đã đề xuất mô hình
quản lý khóa, quản lý truy cập người dùng mà người dùng chỉ quản lý thông tin người
dùng và không nắm giữ bất kỳ thông tin về khóa mã của CSDL nên không thể tấn công
theo hình thức thoả hiệp. Bên cạnh đó, số lượng khóa mã của CSDL bằng với số cột
trong các bảng và được quản lý ở máy chủ DO nên việc thay khóa tương đối dễ dàng,
không phụ thuộc đến người dùng tham gia trong hệ thống. Bên cạnh đó, bài báo cũng
đã đề xuất phương pháp thay khóa với thời gian thực hiện ngắn, đảm bảo cho cơ sở
dữ liệu luôn sẵn sàng hoạt động khi thay khóa. Kết quả chứng minh được khi dữ liệu
càng lớn, tính hiệu quả của phương pháp càng cao, mà phương pháp tiếp cận ngây thơ
khó có thể thực hiện được.
Hướng phát triển tiếp theo, chúng tôi nghiên cứu bài toán quản lý phân phối khóa
mức dòng kết hợp với việc xác thực tính toàn vẹn của dữ liệu, nghĩa là khóa người
dùng kèm theo các thông tin hỗ trợ có thể kiểm tra được dữ liệu trả về từ nhà cung
cấp dịch vụ là chính xác.
Tài liệu tham khảo
[1] H. Hacigumus, B. Iyer, C. Li, and S. Mehrotra, “Executing sql over encrypted data in the database-service-
provider model,” in Proceedings of the 2002 ACM SIGMOD international conference on Management of data.
ACM, 2002, pp. 216–227.
[2] R. A. Popa, C. Redfield, N. Zeldovich, and H. Balakrishnan, “Cryptdb: Processing queries on an encrypted
database,” Communications of the ACM, vol. 55, pp. 103–111, 2012.
88
Journal of Science and Technique - Le Quy Don Technical University - No. 199 (6-2019)
[3] R. Brinkman, L. Feng, J. Doumen, P. H. Hartel, and W. Jonker, “Efficient tree search in encrypted data.”
Information systems security, vol. 13, no. 3, pp. 14–21, 2004.
[4] B. H. K. Chen, P. Y. S. Cheung, P. Y. K. Cheung, and Y. K. Kwok, “Cypherdb: A novel architecture for
outsourcing secure database processing,” IEEE Transactions on Cloud Computing, 2015.
[5] Z.-F. Wang and A.-G. Tang, “Implementation of encrypted data for outsourced database,” in Computational
Intelligence and Natural Computing Proceedings (CINC), 2010 Second International Conference on, vol. 2.
IEEE, 2010, pp. 150–153.
[6] S. Tu, M. F. Kaashoek, S. Madden, and N. Zeldovich, “Processing analytical queries over encrypted data,” in
Proceedings of the VLDB Endowment, vol. 6. VLDB Endowment, 2013, pp. 289–300.
[7] S. Hong, H.-I. Kim, and J.-W. Chang, “An efficient key management scheme for user access control in
outsourced databases,” World Wide Web, vol. 20, no. 3, pp. 467–490, 2017.
[8] I. Hang, F. Kerschbaum, and E. Damiani, “Enki: Access control for encrypted query processing,” in Proceedings
of the 2015 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’15. New
York, NY, USA: ACM, 2015, pp. 183–196. [Online]. Available: http://doi.acm.org/10.1145/2723372.2749439
[9] H. K. Giàu, V. T. Đào, and N. H. Minh, “Thay đổi khoá của cơ sở dữ liệu mã hoá trên môi trường thuê ngoài,”
in Một số vấn đề chọn lọc về an toàn an ninh thông tin, 2017.
[10] T. Hue, G. Luyen, N. Kha, S. Wohlgemuth, I. Echizen, D. Thuc, and T. Thuy, “An efficient fine-grained access
control mechanism for database outsourcing service,” in Information Security and Intelligence Control (ISIC),
2012 International Conference on. IEEE, 2012, pp. 65–69.
[11] J. Dean and S. Ghemawat, “Mapreduce: a flexible data processing tool,” Communications of the ACM, 2010.
Ngày nhận bài 01-2-2018; Ngày chấp nhận đăng 16-10-2018.
ꢀ
Hồ Kim Giàu Tốt nghiệp Đại học Khoa học - Tự nhiên, TP. Hồ Chí Minh năm 2005. Nhận
bằng Thạc sỹ tại Học viện Bưu chính Viễn thông TP.Hồ Chí Minh năm 2011. Đơn vị công tác:
Trường Đại học Thông tin liên lạc, Khánh Hoà. Hiện đang làm nghiên cứu sinh tại Học viện
Kỹ thuật Quân sự. Email: [email protected]. Hướng nghiên cứu hiện nay: An toàn mạng, an
toàn và bảo mật thông tin.
PGS. TS. Nguyễn Hiếu Minh Đơn vị công tác: Học viện Kỹ thuật mật mã, Bộ Quốc phòng,
Hà Nội. E-mail: [email protected]. Tốt nghiệp đại học và Thạc sĩ chuyên ngành Vô
tuyến Điện tử, Học viện Kỹ thuật Quân sự năm 1993 và 1999. Nhận bằng Tiến sĩ Công nghệ
Thông tin - Đại học Kỹ thuật Điện Saint-Peterburg, Liên bang Nga năm 2006. Hướng nghiên
cứu hiện nay: An toàn mạng, mật mã, công nghệ mạng.
89
Section on Information and Communication Technology (ICT) - No. 13 (6-2019)
MANAGEMENT AND CHANGING OF KEY
FOR ENCRYPTED DATA
IN OUTSOURCED DATABASE
Abstract
Data owners who have been outsourced database always want to protect information
(avoid being stolen, modified data, ...) from the attacker on internet and even from the service
provider. To protect their data, the data owners encrypt data before storing it in the cloud.
When querying data, users retrieve encrypted data and decrypt it by using key which is
provided by data owner. In a multi-user model, the data owner must have key management and
distribution to protect database from illegal accesses. On the other hand, changing the key is
necessary to avoid attacks due to the disclosure of key information. A naive method to change
the key is to download the whole database to decrypt them, change the key, encrypt them, and
then update the data. If the database is huge, this approach will take a lot of processing time
and system resources. In this paper, the authors introduce a multi-user access management
model and suggest a method of changing the key on a column-level management model. The
experiments demonstrate the effective of the proposed method on reducing processing time
of changing the key and it can be applied in practice.
90
14 trang
19060
Free
Bạn đang xem tài liệu "Quản lý và thay đổi khóa cơ sở dữ liệu mã hóa trên môi trường thuê ngoài", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- quan_ly_va_thay_doi_khoa_co_so_du_lieu_ma_hoa_tren_moi_truon.pdf
