ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Sỹ Tuấn
NGHIÊN CỨU VÀ XÂY DỰNG MỘT HỆ THỐNG GÁN
NHÃN THỜI GIAN KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành : Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Sỹ Tuấn
Gán nhãn thời gian cho phép chúng ta chứng minh được sự tồn tại của một tài
liệu tại một thời điểm cụ thể nào đó trong quá khứ. Dịch vụ này rất quan trọng trong
nhiều ứng dụng: chứng minh tính không thể phủ nhận của chữ ký số, chứng minh sự
tồn tại trước hay sau của các phát minh khoa học, xác nhận thời điểm của các giao dịch
điện tử, …. Một cách đơn giản cho phép ta xác địch thời điểm tồn tại của tài liệu là
thêm 1 dòng ngày tháng vào trong tài liệu điện tử bằng 1 phần mềm xử lý văn bản.
Tuy nhiên, phương pháp này không an toàn, chúng ta có thể dễ dàng xóa hay thay đổi
ngày tháng này. Khóa luận khảo cứu một giao thức gán nhãn thời gian an toàn cho
phép người dùng gán thời gian vào tài liệu đồng thời cho phép chứng minh tính đúng
đắn của mốc thời gian đó mà không cần yêu cầu một bên ủy quyền thứ ba.
Hệ thống gán nhãn thời gian dựa trên giao thức liên kết đáp ứng được đầy đủ các
yêu cầu nêu trên. Giao thức hoạt động bằng việc liên kết các nhãn thời gian đã được
cấp lại với nhau, mỗi nhãn thời gian đều chứa thông tin về các nhãn khác. Điều đó làm
giảm việc phải tin tưởng hoàn toàn vào server cấp nhãn như trong các hệ thống đơn
giản và như vậy hệ thống sẽ bảo mật hơn.
MỤC LỤC
MỜ ĐẦU 1
Chƣơng 1. HỆ THỐNG GÁN NHÃN THỜI GIAN 2
1.1 Giới thiệu hệ thống gán nhãn thời gian 2
1.1.1 Gán nhãn thời gian là gì? 2
1.1.2 Nguyên tắc hoạt động của hệ thống gán nhãn thời gian 2
1.1.3 Phân loại 2
1.1.4 Các công nghệ dùng trong hệ thống 3
1.2 Các công nghệ sử dụng trong hệ thống gán nhãn thời gian 4
1.2.1 Hàm băm mật mã học – cryptographic hash function 4
1.2.1.1 Định nghĩa hàm băm 4
1.2.1.2 Định nghĩa hàm băm mật mã học – cryptographic hash function 4
1.2.1.3 Tính chất hay yêu cầu đối với hàm băm mật mã 4
1.2.1.4 Giới thiệu về các hàm băm chuyên dụng trong lớp MDx 4
1.2.1.5 Giải thuật MD5 5
3.1.2.2 Sau khi kết thúc vòng 32
3.1.3 Server thực thi theo vòng 32
3.1.4 Định dạng XML sử dụng trong hệ thống cài đặt 34
3.2. Kết quả đạt được và đánh giá 35
3.2.1 Kết quả đạt được 35
3.2.2 Đánh giá 36
3.2.3 Hướng nghiên cứu 36
KẾT LUẬN 37
CÁC TÀI LIỆU THAM KHẢO 38
DANH SÁCH CÁC HÌNH
Hình 1 Lịch sử của MDx-class 5
Hình 2 Thực thi bước của MD5 6
Hình 3 Thực thi bước của SHA-1 8
Hình 4 Từ điển xác thực 10
Hình 5 Cây merkle với 8 node lá 11
Hình 6 Merkle tree của các tài liệu cùng nhãn thời gian 13
Hình 7 Chuỗi các giá trị băm được kết nối với nhau 13
Hình 8 Cây Merkle tổng hợp giá trị AHV 14
Hình 9 Ví dụ Skiplist 15
Hình 10 Tìm kiếm giá trị 39 trong skiplist 16
Hình 11 Quá trình ký và xác thực chữ ký số 19
Hình 12 Sử dụng chữ ký số trong hệ thống e-timestamp 20
Hình 13 Hoạt động của hệ thống gán nhãn đơn giản 21
Hình 14 Cây Merkle với 7 yêu cầu được gửi 23
Hình 15 Giá trị các vòng được liên kết với nhau 23
Hình 16 Thực thi hệ thống dựa trên giao thức liên kết 24
Hình 17 Hệ thống e-TS 27
Hình 18 Giao diện của client khi gán nhãn 30
Hình 19 Giao diện của client khi xác thực 31
dựa trên giao thức liên kết do những ưu điểm của nó.
Khóa luận này trình bày về hệ thống gán nhãn thời gian một cách chính xác, cụ
thể, tổng quan nhất. Dựa trên cơ sở lý thuyết đã tìm hiểu được, tác giả đã đưa ra thiết
kế và xây dựng một hệ thống gán nhãn thời gian dựa trên giao thức liên kết.
Khóa luận được chia làm ba phần chính.
Phần đầu gồm chương 1, 2 giới thiệu về gán nhãn thời gian. Chương 1 giới thiệu
tổng quan về gán nhãn thời gian, về các công nghệ sử dụng trong hệ thống gán nhãn,
cách thức chúng được sử dụng như thế nào trong các hệ thống. Chương 2 nói về các hệ
thống gán nhãn trên lý thuyết và trong thực tế.
Phần thứ hai giới thiệu về thiết kế của hệ thống gán nhãn thời gian được xây
dựng dựa trên giao thức liên kết. Phần này gồm chương 3, trình bày về việc triển khai
hệ thống gán nhãn sử dụng các kỹ thuật được đề cập ở phần đầu, kết quả đạt được,
đánh giá cũng như hướng nghiên cứu trong tương lại.
Phần thứ ba là kết luận.
Cuối cùng là các tài liệu tham khảo.
2
Chƣơng 1. HỆ THỐNG GÁN NHÃN THỜI GIAN
1.1 Giới thiệu hệ thống gán nhãn thời gian
1.1.1 Gán nhãn thời gian là gì?
Là một kỹ thuật mật mã cung cấp bằng chứng chứng minh sự tồn tại của một tài
liệu kỹ thuật số tại một thời gian nhất định.[1]
1.1.2 Nguyên tắc hoạt động của hệ thống gán nhãn thời gian
Thông thường nguyên tắc hoạt động của hệ thống gán nhãn chỉ gồm hai phần:
- Gán nhãn: người dùng gửi giá trị băm của tài liệu cần gán nhãn cho TSA.
TSA thực thi và trả lại cho người dùng nhãn thời gian của tài liệu. Người
dùng lưu nhãn này cho quá trình xác thực.
- Xác thực nhãn: người dùng gửi giá trị băm của tài liệu cần xác thực và nhãn
thời gian của tài liệu đó cho TSA. TSA thực thi và trả về kết quả nhãn thời
hệ thống liên kết và hệ thống phân tán làm cho giả định này là không cần
thiết.
1.1.4 Các công nghệ dùng trong hệ thống
Có bốn kỹ thuật được dùng phổ biến trong các hệ thống gán nhãn là:
- Hàm băm mật mã học
- Từ điển xác thực
- Chữ ký số
- Nguồn thời gian
Hàm băm mật mã học dùng để băm các tài liệu cần gán nhãn, giá trị băm nhận
được được dùng trong quá trình gán nhãn cũng như xác thực vì khi tài liệu bị thay đổi
dẫn tới giá trị băm cũng thay đổi theo. Mặt khác việc gửi tài liệu qua mạng sẽ tốn băng
thông và không an toàn, việc băm tài liệu ra và gửi giá trị băm sẽ tiết kiệm được băng
thông và mức độ bảo vệ quyền riêng tư cũng cao hơn.
Từ điển xác thực thường được sử dụng trong hệ thống gán nhãn dựa trên giao
thức liên kết. Nó được sử dụng để liên kết thông tin của các nhãn thời gian đã được
cấp lại với nhau, tạo ra nhãn thời gian chứa các thông tin của các nhãn thời gian khác.
Việc này làm tăng tính bảo mật của hệ thống chống lại các hình thức tấn công.
Chữ ký số được sử dụng trong hệ thống để ký vào nhãn thời gian cấp phát cho
người dùng. Việc sử dụng chữ ký số làm tăng tính an toàn, tránh việc làm giả nhãn
thời gian.
4
Nguồn thời gian dùng để đồng bộ hóa thời gian của các yêu cầu gán nhãn được
gửi đến TSA, dùng trong việc liên kết các nhãn thời gian đã được cấp phát theo thứ tự
thời gian.
1.2 Các công nghệ sử dụng trong hệ thống gán nhãn thời gian
1.2.1 Hàm băm mật mã học – cryptographic hash function
1.2.1.1 Định nghĩa hàm băm
Là hàm sinh ra các giá trị băm tương ứng với mỗi khối dữ liệu (có thể là một
chuỗi kí tự, một đối tượng, v.v ). Giá trị băm đóng vai gần như một khóa để phân biệt
thiết kế như là một biến thể tăng cường của MD4. Giải thuật này tính ra giá trị băm dài
128 bit , vì vậy loạt các biến được chia thành 4 thanh ghi (A, B, C, D) 32 bit mỗi
thanh. Thiết kế của MD5 tương tự như MD4 nhưng có một số thay đổi:
- Hàm nén bao gồm 64 bước liên tiếp, chia ra thành 4 vòng ( MD4 chỉ có 48
bước và 3 vòng).
- Việc thực hiện bước chỉ khác nhau nhỏ : mỗi bước bây giờ được thêm vào
kết quả của bước trước.
- Sự sắp xếp được áp dụng tại vòng 2 và vòng 3 khác với MD4.
- Hàm Boolean ở vòng 2 được chuyển từ hàm đa số sang hàm lựa chọn ( khác
với hàm lựa chọn dùng ở vòng 1). Một hàm Boolean mới được giới thiệu
cho vòng 4.
6
- Mỗi bước bây giờ sử dụng hằng số thêm vào duy nhất (như vậy là có 64
hằng số).
- Hắng số quay được thay đổi, các vòng khác nhau không bao giờ sử dụng
cùng giá trị hằng số quay.
Việc thực hiện bước của MD5 theo mẫu sau:
A ←( A + f
r
(B, C, D) + W
j
+ U
r
)
<< vs
+ B
Hình 2 Thực thi bƣớc của MD5
Bốn bước liên tiếp cập nhật giá trị của thanh ghi A, D, C, B tương ứng, và việc
j
với j = 1, , 15.
Bên trong, hàm nén chia thành 80 bước liên tiếp. Một sự phân biệt nữa là việc
chia vòng: nó có 4 vòng, mỗi vòng gồm 20 bước. Phép tính bước của SHA-1 theo mẫu
sau:
E ← E + f
r
(B, C, D) + A
<<5
+ W
j
+ U
r
B ← B
<<30
Mỗi bước tính giá trị mới cho 2 trong 5 thanh ghi. Trong trường hợp này ta xét
đến bước cập nhật giá trị cho thanh ghi E và cũng quay giá trị của thanh ghi B một
khoảng 30 bit về bên trái. Phép tính cập nhật giá trị cho thanh ghi E phụ thuộc vào 4
thanh ghi còn lại và theo :
8
- Từ mang thông điệp W
j
với j ={0,1, ,79}
- Hàm Boolean f
r
phụ thuộc vào vòng.
- Hằng số thêm vào U
Hình 3 Thực thi bƣớc của SHA-1
9
Tuy nhiên sau 80 bước , hàm nén sử dụng phép toán feed-forward để thêm các
giá trị khởi tạo vào giá trị cuối. Kết quả là chuỗi biến đầu ra của hàm nén. Vì vậy hàm
nén không bị nghịch đảo .
1.2.1.7 So sánh các hàm băm MD5 và SHA-1 trong lớp MDx
Hàm băm MD5 cho kết quả băm là xâu 128 bit nên nó thực thi nhanh hơn hàm
băm SHA-1 ( 160 bit kết quả) nhưng cũng chính vì thế nên nó yếu hơn SHA-1 khi bị
tấn công brute force và tấn công nghịch đảo.
Một đội nghiên cứu của Trung Quốc đã công bố tài liệu về các phương thức mà
họ dùng để phá vỡ giải thuật băm SHA-1 và MD5 sử dụng hình thức tấn công tìm
kiếm sự va chạm. Một dạng tấn công va chạm đòi hỏi phải tìm hai thông báo mà có
cùng giá trị băm. Kiểu tấn công này thực sự tốn kém nhưng mà nó chỉ ra các điểm yếu
của các giải thuật trên [7].
1.2.2 Từ điển xác thực - Authenticated Dictionary
1.2.2.1 Giới thiệu
Từ điển xác thực ( authenticated dictionary) là cấu trúc dữ liệu được sử dụng để
duy trì tập các phần tử S, nó cho phép truy vấn và cập nhật tập S [8].
Trong hệ thống timestamp, từ điển xác thực gồm ba phần : nguồn đáng tin,
đường dẫn đáng tin và người sử dụng. Nguồn (source) định nghĩa là một tập S hữu hạn
phần tử tăng lên theo thời gian trong suốt quá trình chèn và xóa. Đường dẫn (
directory) duy trì một bản sao chép của tập S. Nó nhận nhãn thời gian cập nhật từ
nguồn đồng thời với cập nhật thông tin xác thực, như việc đăng báo về việc cập nhật
và những phần tử của tập hợp hiện tại. Người dùng thực hiện các truy vấn của thành
viên trên tập S dưới dạng ”phần tử e có trong tập S không?”, nhưng thay vì liên hệ trực
tiếp với nguồn, nó truy vấn đường dẫn. Đường dẫn cung cấp cho người dùng với câu
trả lời đúng/sai để truy vấn đồng thời câu trả lời thông tin xác thực, để tiến hành chứng
thực câu trả lời được lắp ráp bằng cách kết hợp các tài liệu được ký bởi nguồn. Người
Giá trị N cần được xác thực là ở lá thứ N của cây. Ta có thể chọn giá trị của lá
tùy thích, nhưng thông thường là các giá trị của hàm băm mật mã học cần được xác
thực. Trong trường hợp này các giá trị đó được gọi là tiền ảnh lá. Một lá có thể được
chứng nhận với một giá trị root công khai được biết đến và đường dẫn xác thực của nó
[2].
Hình 5 Cây merkle với 8 node lá
1.2.2.3.2 Đƣờng dẫn xác thực
Gọi Auth
h
là giá trị của node anh em có độ cao h trên đường từ lá đến root. Mỗi
lá có độ cao 0 và hàm băm của 2 lá có độ cao 1, … Trong cách này, root có độ cao H
khi cây có 2
H
= N lá. Với mỗi lá thì đường dẫn xác thực là tập {Auth
h
|0 ≤h≤H}. Vì vậy
lá có thể được xác thực bằng cách: đầu tiên áp dụng hàm băm f cho lá và anh em
Auth
0
, sau đó áp dụng f cho kết quả và Auth
1
, vì vậy tất cả đường đi đều tới root. Nếu
tính được giá trị của root bằng với giá trị đã được công khai thì giá trị của lá được chấp
nhận [2].
1.2.2.3.3 Giải thuật tạo cây
Khi xây dựng, mỗi giá trị node được xác định bằng giá trị của các lá bên dưới nó.
Giải thuật này được gọi là TREEHASH . Khi thực hiện 2
h+1
– 1 bước, nó chứa được tối
l
) = LEAFCALC(leaf)
Push P( n
l
) vào Stack
Tăng leaf
4. Quay lại bước 2.
1.2.2.3.4 Sử dụng Merkle tree trong hệ thống gán nhãn
Trong hệ thống Surety [7], hai cây merkle được sử dụng để lưu trữ các giá trị
băm của văn bản và xây dựng đường dẫn xác thực cho mỗi văn bản đó.
Cây Merkle thứ nhất được sử dụng khi mà hệ thống nhận được giá trị băm của
văn bản, nó lưu giá trị băm này và nhãn thời gian tương ứng vào Surety’s Universal
Registry. Xảy ra trường hợp nhiều văn bản có cùng nhãn thời gian, Surety giải quyết
vấn đề này bằng cách sử dụng Merkle tree. Trong ví dụ này, các giá trị băm của văn
bản ở các node dưới cùng được gán cùng timestamp. Việc tính toán giá trị băm trung
gian được kết hợp với nhau cho đến khi đạt tới node root .
13 Hình 6 Merkle tree của các tài liệu cùng nhãn thời gian
Giá trị của node root sau đó được kết hợp với giá trị cuối cùng của SHV
(Summery Hash Value) trong chuỗi băm.
Hình 7 Chuỗi các giá trị băm đƣợc kết nối với nhau
Việc tính toán AHV (Aggregate Hash Value) để công bố cũng bằng cách tạo
Merkle Tree thứ hai sử dụng tất cả các bản ghi SHV trong chuỗi. Từng cặp của bản ghi
được kết hợp với nhau cho đến khi kết quả cuối cùng được tính ra. Để cho giá trị này
được sử dụng để xác nhận bất kỳ một file gốc điện tử nào, thành phần của đường dẫn
được sử dụng trong việc tính toàn cần được biết đến. Như việc đã nói đến ở trên, giá trị
băm của một vài file điện tử được gửi trong cùng cửa sổ trong suốt quá trình tính toán
phần tử trong S
i-1
. Để định nghĩa ví dụ từ một mức này đến mức kết tiếp, chọn mỗi
phần tử của S
i-1
một cách ngẫu nhiên với xác suất ½ là vào trong S
i
. Các phần tử đầu
cuối -∞ và +∞ luôn luôn được đưa vào trong mức lên tiếp theo, và ở mức cao nhất,t,
nó được duy trì để luôn là O(log n). Mức cao nhất được đảm bảo là chỉ có đầu cuối. Vì
thế phân biệt node ở trên cùng danh sách S
t
lưu giá trị -∞ như là node bắt đầu s.
Phần tử tồn tại trong S
i-1
nhưng không ở trong S
i
phần tử cao nguyên của tập S
i-1
.
Phần tử mà ở cả S
i
và S
i-1
được gọi là phẩn tử tháp ở S
i-1
. Giữa hai phần tử tháp nào
cũng có vài phần tử cao nguyên. Tronsg xác định skiplist, số lượng của phần tử cao
nguyên giữa hai tháp ít nhất là một và nhiều nhất là ba. Số lượng mong đợi của phần
tử cao nguyên giữa hai phần tử tháp là một.
Hình 10 Tìm kiếm giá trị 39 trong skiplist
Tiến trình tìm kiếm trên chạy trong khoảng thời gian mong đợi là O(log n), vì
vậy, với xác suất cao, độ cao t của skiplist ngẫu nhiên là O(log n) và số lượng mong
muốn của node được thăm ở bất kỳ mức nào là ba. Hơn nữa, các nghiên cứu thực
nghiệm thường tốt hơn 2-3 cây, cây đỏ-đen, và các kiến trúc cây tìm kiếm khác.
Để chèn thêm một phần tử x, ta phải xác định danh sách nào chứa phần tử mới x
bằng một chuỗi các mô phỏng tung đồng xu. Bắt đầu với i = 0, khi đồng xu là mặt
ngửa, sử dụng stack A để lần vết đường quay lại vị trí của danh sách S
i+1
nơi mà x nên
đến, thêm node mới lưu x vào danh sách này, đặt i = i +1. Tiếp tục quá trình chèn cho
đến khi đồng xu là mặt sấp. Nếu mà đạt tới mức cao nhất với quá trình chèn này thì
thêm mức cao nhất mới vào đỉnh của mức hiện tại. Thời gian của phương thức chèn
này là O(log n) với xác suất cao. Để xóa phần tử đã tồn tại x, loại bỏ tất cả các phần tử
chứa x. Độ phức tạp của giải thuật này là O(log n) với xác suất cao.
Copyright: Tài liệu đại học ©