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

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: for each data ∈ list do
11: plaintext = DeclistOldKey(i)(data)
12: ciphertext = EnclistNewKey(i)(plaintext)
13: newkey.concat(ciphertext + "|")
14: i++;
15: end for
16: 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
 2 2
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) = n Sf tkc/x .
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
 Thuật toán Naive Bước 1 Bước 2 Bước 3
 Tên bảng Số bản ghi
 KeyChange(s) CSDL→HDFS(s) Đổi khóa(s) HDFS→CSDL(s)
 customer 150000 6908.127 18.897 36.312 66.872
 lineitem 6001215 309241.736 218.252 1376.162 4963.679
 nation 25 1.499 16.571 18.670 38.101
 orders 1500000 100763.852 42.734 202.997 618.088
 part 200000 9526.048 28.198 43.239 92.563
 partsupp 800000 36963.637 26.125 76.680 219.674
 region 5 0.595 21.734 17.518 19.521
 supplier 10000 449.528 16.766 19.995 25.807
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
 )
 s
 (
 250,000
 n
 ệ
 i
 h
 c 200,000
 ự
 h
 t
 n
 a 150,000
 i
 g
 i
 ờ
 h 100,000
 T
 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: 
 [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.
 [Online]. Available: 
[12]  [Online]. Available: 
[13]  [Online]. Available: 
 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: hkgiau@gmail.com. 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: hieuminhmta@gmail.com. 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