Khóa luận Nghiên cứu và xây dựng một hệ thống gán nhãn thời gian
ĐẠ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
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
Cán bộ hƣớng dẫn: PGS. TS Hồ Sĩ Đàm
Cán bộ đồng hƣớng dẫn: TS Lê Đức Phong
HÀ NỘI - 2010
LỜI CẢM ƠN
Trước tiên, em xin gửi lời cảm ơn sâu sắc đến PGS. TS Hồ Sĩ Đàm và TS Lê
Đức Phong, những người đã tận tình chỉ bảo, giúp đỡ em hoàn thành khóa luận này.
Em xin chân thành cảm ơn các thầy cô trong bộ môn Mạng và truyền thông máy
tính, trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo điều kiện cho em
thực hiện đề tài.
Cuối cùng, em xin cảm ơn những người thân trong gia đình và bạn bè đã giúp đỡ,
động viên em hoàn thành khóa luận.
Sinh viên
Nguyễn Sỹ Tuấn
TÓM TẮT KHÓA LUẬ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
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.3 Phân loại..........................................................................................................2
1.1.4 Các công nghệ dùng trong hệ thống.................................................................3
1.2.1.1 Định nghĩa hàm băm..................................................................................4
1.2.1.5 Giải thuật MD5..........................................................................................5
1.2.1.6 Mô tả giải thuật SHA-1..............................................................................7
1.2.2 Từ điển xác thực - Authenticated Dictionary....................................................9
1.2.2.1 Giới thiệu ..................................................................................................9
1.2.2.2 Mục tiêu của thiết kế ...............................................................................10
1.2.2.3 Từ điển xác thực sử dụng Merkle tree......................................................10
1.2.2.3.1 Định nghĩa Merkle tree.........................................................................10
1.2.2.3.2 Đường dẫn xác thực..............................................................................11
1.2.2.3.3 Giải thuật tạo cây..................................................................................11
1.2.2.4 Từ điển xác thực sử dụng SkipList...........................................................14
1.2.3.2 Giải thuật chữ ký số.................................................................................18
1.2.4 Nguồn thời gian – Time Source .....................................................................20
2.1 Hệ thống trên lý thuyết.........................................................................................21
2.1.1 Hệ thống đơn giản .........................................................................................21
2.1.2 Hệ thống dựa trên giao thức liên kết ..............................................................22
2.1.3 Bảo mật của hệ thống liên kết ........................................................................26
2.2 Hệ thống trên thực tế............................................................................................27
2.2.1 Hệ thống Electronic TimeStamping (e-TS) ....................................................27
2.2.2 Hệ thống Surety.............................................................................................28
3.1 Mô tả hệ thống cài đặt..........................................................................................30
3.1.2 Quá trình xác thực .........................................................................................31
3.1.2.1 Khi chưa kết thúc vòng ...............................................................................31
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.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
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 9 Ví dụ Skiplist ......................................................................................15
Hình 23 Các giá trị của vòng được công bố.....................................................36
DANH MỤC TỪ VIẾT TẮT
TSA
MD5
SHA
TimeStamping Authority
Message Digest 5
Secure Hash Algorithm
MỜ ĐẦU
Ngày nay trong thế giới của truyền thông kỹ thuật số, các dạng văn bản, âm
thanh, tranh ảnh và tài liệu hình trở nên hết sức phổ biến. Vấn đề nảy sinh là làm thế
nào để chứng thực một văn bản được tạo ra hoặc được sửa đổi gần nhất khi nào. Ví dụ
như trong vấn đề sở hữu trí tuệ, việc xác thực thời gian của một phát minh lần đầu tiên
được công nhận là rất quan trọng, mục đích là để được ưu tiên hơn trong việc cấp bằng
sở hữu khi có tranh chấp xảy ra. Thêm một ví dụ nữa về sự cần thiết của việc chứng
thực ngày tạo văn bản, đó là việc tạo di chúc, việc lưu di chúc bằng văn bản kỹ thuật
số được thực hiện hết sức dễ dàng nhưng để chứng minh thời gian nó được tạo ra lại
hết sức khó khăn. Khi có tranh chấp xảy ra, có thể có nhiều bản di chúc khác nhau
nhưng việc chứng minh được bản di chúc được tạo ra cuối cùng rất khó khăn.
Có khá nhiều vấn đề liên quan đến thời gian tạo tài liệu kỹ thuật số vì các tài liệu
này không dễ để gán nhãn, và sự thay đổi của nó không có tín hiệu vật lý nào báo hiệu.
Chính vì vậy việc xây dựng một hệ thống gán nhãn thời gian là rất cần thiết, nó giúp
cho ta chứng minh được một văn bản tồn tại ở một thời điểm. Có ba thiết kế của các hệ
thống gán nhãn được sử dụng phổ biến trên thế giới; đó là hệ thống đơn giản, hệ thống
dựa trên giao thức liên kết và hệ thống phân tán. Khóa luận lựa chọn thiết kế hệ thống
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.
1
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
gian hợp lệ hoặc không.
1.1.3 Phân loại
Các hệ thống gán nhãn thường được chia ra làm ba loại [6]:
- Hệ thống đơn giản: là giao thức từng bước, thường được chia thành hai phần (
client và TSA) tương tác và đồng bộ với nhau. Kết quả của hệ thống này là
các nhãn thời gian độc lập. Thiết kế này khá đơn giản và dễ thực hiện. Nhãn
thời gian được tạo ra bởi nhiều TSA khác nhau có thể so sánh được sử dụng
thời gian và các thông số về độ chính xác. Điểm yếu lớn nhất của hệ thống
này là việc phải tin tưởng vô điều kiện vào TSA. Khi mà TSA đảm bảo tính
đúng đắn của thông số thời gian, nó có đủ khả năng thay đổi nhãn thời gian
bằng tấn công back-date.
- Hệ thống liên kết: khó thực hiện hơn so với hệ thống đơn giản, nhưng việc
tấn công back-date khó thực hiện hơn. Trong trường hợp này, TSA tạo ra các
nhãn thời gian mà trong nó chứa các thông tin về các nhãn đã được cấp phát.
Kết quả là một chuỗi các nhãn thời gian được xây dựng, kết nối tất cả các
nhãn thời gian được tạo ra bởi TSA. Khi mà kẻ xấu cố gắng thay đổi một
nhãn thời gian thì toàn bộ chuỗi kết nối của các nhãn thời gian cũng bị thay
đổi theo. Đây chính là ưu điểm so với hệ thống đơn giản, nhưng điều đó cũng
2
dẫn đến việc phức tạp trong thủ tục xác minh, khi đó người dùng không thể
xác thực được nhãn thời gian mà không có sự giúp đỡ từ TSA.
- Hệ thống phân tán: hệ thống này bao gồm nhiều TSA thuộc một trong hai hệ
thống đã trình bày ở trên, cùng chịu trách nhiệm tạo ra nhãn thời gian. Trọng
tâm là thiết lập việc tăng cường bảo mật chống lại việc thao túng nhãn thời
gian bằng cách chia sẻ các giá trị bí mật (trong hầu hết trường hợp, khóa được
sử dụng để ký dữ liệu). Hệ thống này bảo mật hơn hệ thống đơn giản. Để việc
tấn công back-date có thể diễn ra, tất cả các TSA tham gia tạo nhãn thời gian
phải trở thành một phần của cuộc tấn công. Điều quan trọng là nhận ra rằng,
trong khi tất cả các hệ thống đơn giản giả định TSA là bên thứ ba đáng tin thì
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.
3
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
(nhờ việc so sánh các giá trị băm nhanh hơn việc so sánh những khối dữ liệu có kích
thước lớn) [14].
1.2.1.2 Định nghĩa hàm băm mật mã học – cryptographic hash function
điệp đầu vào. Điều đó có nghĩa là không khả thi khi tìm những thông điệp mà khi băm
chúng, ta nhận được cùng kết quả [5].
1.2.1.3 Tính chất hay yêu cầu đối với hàm băm mật mã
- Có thể áp dụng đối với thông báo M có độ dài bất kỳ, kết quả H(M) có độ dài
cố định.
- H(M) tính được dễ dàng với bất kỳ M nào.
- Tính một chiều : từ h rất khó để tính được M sao cho H(M) = h.
1.2.1.4 Giới thiệu về các hàm băm chuyên dụng trong lớp MDx
Các hàm băm trong nhóm này đều có ý tưởng thiết kế tương tự nhau [5]. Hàm
băm đầu tiên trong nhóm là giải thuật MD4, được đề xuất bởi R.Rivest vào năm 1990.
Mặc dù MD4 không phải là một hàm băm an ninh nhưng có một số giải thuật khác có
nguồn gốc từ MD4 với sự cải thiện về sức mạnh, người ta gọi đó là MDx-class. Trong
MDx-class bao gồm giải thuật MD5 ( một thiết kế khác của Rivest), giải thuật
HAVAL ( được đề xuất bởi một nhóm các nhà nghiên cứu ở Australia), giải thuật
SHA ( hàm băm chuẩn U.S của NIST ), và giải thuật RIPEMD ( ban đầu được phát
4
triển trong framework của dự án European RIPE ). Các hàm băm này được sử dụng
rỗng rãi nhất hiện nay.
Hình 1 Lịch sử của MDx-class
1.2.1.5 Giải thuật MD5
Giải thuật MD4 và MD5 [5] đều được thiết kế bởi Rivest. Giải thuật MD5 được
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.
5
- 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 + fr(B, C, D) + Wj + Ur) << 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
này được lặp lại 4 lần trong một vòng. Mỗi thanh ghi được cập nhật 16 lần bởi hàm
nén.
6
Tuy nhiên sau khi thực hiện 64 bước, hàm nén sử dụng các giá trị của thanh ghi
ban đầu để thêm vào giá trị cuối cùng ( sau 64 bước). Kết quả là một loạt các biến đầu
ra từ hàm nén. Tùy thuộc vào các giá trị ban đầu, hàm nén không thể đảo ngược .
1.2.1.6 Mô tả giải thuật SHA-1
Giải thuật SHA [5] được thiết kế bởi NSA và được công bố bởi NIST như là tiêu
chuẩn liên bang FIPS 180 vào năm 1993. SHA là một hàm băm khác lấy cảm hứng tư
MD4. Thiết kế của giới thiệu một thủ tục đặc biệt cho việc mở rộng khối thong điệp 16
từ đầu vào của hàm nén để tạo ra khối 80 từ. Nguyên tắc thiết kế của SHA không được
công bố , tuy nhiên năm 1994 NIST công bố rằng lỗ hổng kỹ thuật được tìm ra ở SHA
làm cho giải thuật kém an toàn hơn suy nghĩ ban đầu. Không có thêm chi tiết nào được
công bố nữa, nhưng có một sự thay đổi nhỏ trong hàm băm SHA-, và tiêu chuẩn tương
ứng FIPS 180-1. Vào năm 1998, F. ChaBaud và A. Joux tìm ra lý thuyết tấn công
đụng độ đối với phiên bản ban đầu của SHA ( giải thuật này thường được gọi là SHA-
0). Phân tích của họ giúp thay đổi hàm băm SHA-1.
Vào năm 2002, NIST cập nhật hàm băm tiêu chuẩn đến FIPS 180-2. Tiêu chuẩn
mới này xác định, bên cạnh SHA-1, 3 hàm băm mới là SHA-256, SHA-384 và SHA-
512. Chúng có đầu ra có độ dài lớn hơn để cung cấp mức độ an ninh chống lại tấn
công ngày sinh, tương tự như mức độ an ninh của thuật toán mã hóa khối AES với 128
bit, 192 bit và 256 bit độ dài khóa tương ứng. Vào năm 2004, một thong báo thay đổi
được đưa vào trong tiêu chuẩn, xác định hàm băm SHA-224.
Giải thuật SHA-1 tính toán kết quả băm dài 160 bit đối với thông điệp có độ dài
nhỏ hơn 264 bit. Giải thuật có độ dài của từ là 32 bit, chính vì vậy chuỗi biến được
chia thành 5 thanh ghi ( A, B, C, D, E) 32 bit mỗi thanh. Hàm nén làm việc với khối
thông điệp 512 bit, khối được chia thành 16 từ 32 bit biểu diễn bởi Wj 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 + fr(B, C, D) + A<<5 + Wj + Ur
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 :
7
- Từ mang thông điệp Wj với j ={0,1,..,79}
- Hàm Boolean fr phụ thuộc vào vòng.
- Hằng số thêm vào Ur phụ thuộc vào vòng.
Hàm Boolean được sử dụng ở các vòng khác nhau trong hàm nén là hàm lựa
chọn, đa số và exor. Hàm exor được sử dụng trong vòng 2 và 4. 16 từ đầu tiên Wj ( j =
0,1,…,15) bằng với khối thông điệp đầu vào của hàm nén. 64 từ còn lại Wj ( j = 16,
…, 79) được tính bằng thủ tục sau cho thông điệp mở rộng:
Wj = ( Wj-3 xor Wj-8 xor Wj-14 xor Wj-16)<<1
Sự khác biệt duy nhất giữa SHA-1 và SHA-0 trong công thức trên. SHA-0 không
có quay 1 bit về bên trái.
Hình sau biểu diễn việc tính bước trong SHA-1. 5 bước liên tiếp cập nhật giá trị
cho thanh ghi E, D, C, B, A tương ứng và cung quay giá trị của thanh ghi B, A, E, D,
C đi 30 bit vị trí sang bên trái. Sau 5 bước chuỗi biến được cập nhật hoàn chỉnh. Một
vòng của hàm nén bao gồm bốn chuỗi của 5 bước. Mỗi thanh ghi được cập nhật 4 lân
trong mỗi vòng và 16 lần trong hàm nén.
Hình 3 Thực thi bƣớc của SHA-1
8
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
dùng sau đó xác minh chứng thực bằng cách duy nhất là tin vào nguồn và các thông tin
được công bố về nguồn cho phép kiểm tra chữ ký của nguồn [8].
9
Hình 4 Từ điển xác thực
Có hai loại từ điển được dùng trong hệ thống gán nhãn là:
- Sử dụng Merkle tree.
- Sử dụng skip list.
1.2.2.2 Mục tiêu của thiết kế
Thiết kế của từ điển xác thực hướng tới những mục tiêu sau:
- Chi phí tính toán thấp: việc tính toán trong mỗi phần ( nguồn, đường dẫn,
người sử dụng) nên đơn giản và nhanh. Việc sử dụng bộ nhớ bởi cấu trúc dữ
liệu hỗ trợ cho việc tính toán phải nhỏ nhất có thể.
- Hạn chế việc giao tiếp giữa các tầng: việc giao tiếp giữa nguồn và danh mục
( cập nhật thông tin xác thực) và giao tiếp giữa đường dẫn với người dùng (
trả lời thông tin xác thực) nên giữ nhỏ nhất có thể.
- Mức độ an ninh cao: việc xác thực dữ liệu cung cấp bởi đường dẫn nên được
kiểm chứng với mức độ tin cậy cao.
1.2.2.3 Từ điển xác thực sử dụng Merkle tree
1.2.2.3.1 Định nghĩa Merkle tree
Trong [9] Merkle giới thiệu việc sử dụng cây nhị phân trong việc xác thực một
lượng lớn khóa công khai với một giá trị đơn lẻ, cụ thể là giá trị gốc của cây. Đó là
cách mà định nghĩa của cây Merkle được đưa vào sử dụng. Nó là một cây nhị phân
hoàn chỉnh với k-bit giá trị liên quan đến mỗi node như giá trị của node là hàm băm
của giá trị các node con của nó.
10
P là phép gán, nó gán tập của các node với tập xâu của chúng có độ dài k.
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 Authh 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ó 2H = N lá. Với mỗi lá thì đường dẫn xác thực là tập {Authh|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
Auth0, sau đó áp dụng f cho kết quả và Auth1, 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 2h+1 – 1 bước, nó chứa được tối
đa h+1 giá trị băm. Giải thuật TREEHASH hợp nhất các giá trị của node ở cùng độ
cao trước khi tính toán lá mới.
Giải thuật TREEHASH(start,maxheight) [2]
1. Leaf = start;
11
Stack = empty;
2. Hợp nhất: nếu 2 node trên cùng của Stack có cùng độ cao
Pop P( nright ) và P( nleft ) ra khỏi Stack
Tính P( nparent ) = f ( P( nleft ) || P( nright ) )
Nếu độ cao của P( nparent ) = maxheight, đưa ra P( nparent
Push P( nparent ) vào Stack và dừng lại.
3. Lá mới:
)
Tính P( nl ) = LEAFCALC(leaf)
Push P( nl ) 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 .
12
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
của SHV. Các giá trị này được kết hợp với nhau vào chuỗi băm. Cây nhị phân của tất
cả các SHV được tạo ra và tính toán giá trị AHV.
13
Hình 8 Cây Merkle tổng hợp giá trị AHV
1.2.2.4 Từ điển xác thực sử dụng SkipList
1.2.2.4.1 SkipList
Cấu trúc dữ liệu Skiplist [8] lưu trữ hiệu quả tập S các phần tử từ tập hợp yêu
cầu. Nó hỗ trợ các phép toán sau:
- Find(x) : xác định xem phần tử x có trong S hay không.
- Insert(x): chèn thêm x vào S.
- Delete(x): xóa phần tử x khỏi S.
14
Hình 9 Ví dụ Skiplist
Một skip list lưu một tập S các phần tử của một loạt danh sách liên kết S0,S1,…,
St. Danh sách cơ sở S0 lưu tất cả các phần tử của S theo thứ tự, cũng như liên kết với
các phần tử đặc biệt -∞ và +∞ . Mỗi danh sách kế tiếp Si, với i ≥ 1, lưu một ví dụ của
phần tử trong Si-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 Si-1 một cách ngẫu nhiên với xác suất ½ là vào trong Si. 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 St lưu giá trị -∞ như là node bắt đầu s.
Phần tử tồn tại trong Si-1 nhưng không ở trong Si phần tử cao nguyên của tập Si-1.
Phần tử mà ở cả Si và Si-1 được gọi là phẩn tử tháp ở Si-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.
Đối với mỗi node v thuộc Si, biểu diễn phần tử được lưu tại v là elem(v). Bên
cạnh đó, biểu diễn node trong Si-1 bên dưới v là down(v), node này lưu phần tử tương
tự như v, khi i = 0 thì down(v)=null. Tương tự, biểu diễn right(v) là node trong Si ngay
ở bên phải của v, khi v là phần tử cuối lưu +∞ thì right(v)= null.
Để thực hiện việc tìm kiếm phần tử x trong skiplist, bắt đầu với node bắt đầu s.
Lấy v biểu diễn node hiện tại trong quá trình tìm kiếm( khởi tạo v = s). Quá trình tìm
kiếm sử dụng hai hành động, hop forward và drop down, được lặp đi lặp lại cho đến
khi kết thúc tìm kiếm.
- Hop forward: tiến về bên phải của danh sách hiện tại cho đến khi tìm thấy
node của danh sách hiện tại với phần tử lớn nhất mà bé hoặc bằng với x.
Trong khi elem(right(v)) < x, cập nhật v = right(v).
15
- Drop down: nếu down(v) = null, việc tìm kiếm kết thúc: node v lưu phần tử
lớn nhất trong skiplist mà nhỏ hơn hoặc bằng x. Nếu không thì cập nhật v =
down(v).
Vòng lặp ngoài của quá trình tìm kiếm vẫn tiếp tục khi mà down(p) ≠ null, chạy
bên trong vòng lặp một hop forward được theo sau bởi một drop down. Sau khi hoàn
thành một chuỗi các bước forward và drop down, cuối cùng gặp node v với down(v) =
null. Nếu tại điểm này, elem(v) = x thì đã tìm ra phần tử x. Nếu không v là node của
danh sách cơ sở với phần tử lớn nhất nhỏ hơn x; cũng như vậy, trong trường hợp này,
right(v) là node của danh sách cơ sở với phần tử nhỏ nhất lớn hơn x, là
elem(v)<x<elem(right(v)).
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 Si+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.
16
1.2.2.4.2 Sử dụng skiplist trong hệ thống gán nhãn
Từ điển xác thực bao gồm một skiplist trong đó mỗi node v lưu nhãn được tính ra
từ các phần tử của tập hợp bằng hàm băn mật mã giao hoán h [8].
Đối với mỗi node v, định nghĩa nhãn f(v) trong giá trị tương ứng tại node
w=right(v) và u = down(v). Nếu right(v) = null, định nghĩa f(v) = 0. Định nghĩa của
f(v) theo cách thông thường phụ thuộc vào u tồn tại hay không đối với node v.
1. u = null, v ở mức cơ sở:
(a) Nếu w là node tháp, f(v) = h(elem(v),elem(w))
(b) Nếu w là node cao nguyên thì f(v) = h(elem(v),f(w))
2. u ≠ null, v không ở mức cơ sở:
(a) Nếu w là node tháp thì f(v) = f(u)
(b) Nếu w là node cao nguyên thì f(v) = h(f(u),f(w))
Sau khi thực hiện việc cập nhật trong skiplist, các giá trị băm phải được thay đổi
để phản ánh sự thay đổi đã xảy ra. Phần thời gian tính toán tăng lên cho việc cập nhật
tất cả các giá trị này được dự kiến là O(log n).
Việc xác minh câu trả lời cho các truy vấn khá đơn giản, do tính hữu dụng của
hàm băm giao hoán. Nhắc lại mục đích là tạo ra việc xác minh trong cả trường hợp
một vài phần tử x có hoặc không có trong skiplist. Trong trường hợp câu trả lời là có,
ta xác minh sự hiện diện của nó. Nếu không ta xác minh sự hiện diện của hai phần tử
x’ và x” được lưu ở hai node liên tiếp tại mức đáy S0 với x’<x<x”. Trong trường hợp
còn lại, câu trả lời thông tin xác thực là một chuỗi đơn các giá trị, cùng với chữ ký,
timestamp, nhãn f(s) của node bắt đầu s.
1.2.3 Chữ ký số - Digital signature
1.2.3.1 Định nghĩa
Một chữ ký số hoặc lược đồ chữ ký số [12] là một lược đồ toán học để chứng
minh định danh người gửi của một thông báo hoặc tài liệu số. Một chữ ký số hợp lệ
cho phép bên gửi chứng minh với bên nhận rằng tin nhắn do chính mình tạo ra, gửi
đến và không bị thay đổi nội dung trong quá trình truyền. Chữ ký số được sử dụng phổ
biến để phân phối phần mềm, giao dịch tài chính, và trong trường hợp khác, nơi mà
điều quan trọng là để phát hiện giả mạo và sự can thiệp.
17
Chữ ký số thường được sử dụng để thực hiện chữ ký điện tử, một thuật ngữ rộng
hơn mà đề cập đến bất kỳ dữ liệu điện tử, trong đó mang đến ý nghĩa của một chữ ký,
nhưng không phải tất cả chữ ký điện tử sử dụng chữ ký số. Trong một số quốc gia, bao
gồm Hoa Kỳ, và các thành viên của Liên minh châu Âu, chữ ký điện tử có ý nghĩa
pháp lý. Tuy nhiên, pháp luật liên quan đến chữ ký điện tử luôn luôn không rõ ràng
cho dù đó là mật mã số chữ ký theo nghĩa được sử dụng ở đây, để định nghĩa pháp lý,
và như vậy tầm quan trọng của chúng.
Chữ ký số là một ứng dụng của mật mã không đối xứng. Đối với thông tin được
gửi thông qua một kênh không bảo mật, việc triển khai chữ ký số một cách đúng đắn
làm cho người nhận tin rằng tin nhắn được gửi bởi người gửi. Chữ ký số tương đương
với chữ ký viết tay truyền thống ở nhiều khía cạnh; việc triển khai chữ ký số làm cho
việc giả mạo khó hơn so với kiểu viết tay. Đề án chữ ký số theo nghĩa được sử dụng ở
đây là dựa vào mã hóa, và phải được thực hiện có hiệu quả. Chữ ký số cũng có thể
cung cấp không thể thoái thác, nghĩa là người ký không phải bồi thường những thông
báo họ không ký vào, trong khi cũng đòi khóa riêng của họ vẫn còn bí mật; hơn nữa,
một số đề án chống thoái thác đưa ra một nhãn thời gian cho chữ ký số, do đó ngay cả
khi khoá bí mật bị lộ, chữ ký là vẫn hợp lệ. Những thông báo điện tử được ký là bất cứ
điều gì có thể được biểu diễn như một xâu bit: ví dụ bao gồm thư điện tử, hợp đồng,
hoặc một tin nhắn được gửi qua một số giao thức mật mã khác.
1.2.3.2 Giải thuật chữ ký số
Giải thuật chữ ký số [13] (Digital Signature Algorithm, viết tắt DSA) là chuẩn
sửa đổi nhỏ được đưa ra năm 1996 trong FIPS 186-1, chuẩn được mở rộng hơn năm
2000, được xem như FIPS 186-2.
Giải thuật chữ ký số gồm ba giải thuật chính là :
- Giải thuật tạo khóa bằng việc lựa chọn khóa bí mật gần ngẫu nhiên nhất từ
một tập có thể của các khóa bí mật. Giải thuật cho ra khóa bí mật và khóa
công khai tương ứng.
- Giải thuật ký, đưa vào thông báo và khóa bí mật, tạo ra chữ ký.
- Giải thuật xác thực chữ ký: đưa vào thông báo, khóa công khai và chữ ký,
có thể chấp nhận hoặc không yêu cầu xác thực của thông báo.
18
Hình 11 Quá trình ký và xác thực chữ ký số
Hai thuật toán đầu là bắt buộc. Đầu tiên, một chữ ký được tạo ra từ một thông
báo cố định và khóa riêng cố định nên xác minh tính xác thực của thông báo bằng cách
sử dụng khóa công khai tương ứng. Thứ hai, không thể thực hiện việc tính toán để tạo
ra một chữ ký hợp lệ cho bên không có khóa riêng.
Trong hệ thống gán nhãn thời gian đơn giản [4], chữ ký số được TSA sử dụng để
ký vào chứng nhận mà nó gửi cho người dùng. Nhờ việc sử dụng chữ ký số, người
dùng có thể xác định được chứng nhận là do TSA cấp .
Trong thực tế, Electronic Time-Stamping (e-TS) [10] và e-timestamp [11] của
Digistamp Inc là sự kết hợp giữa kỹ thuật băm và kiến trúc khóa công khai (Public
Key Infastructure – PKI). Như hình dưới, client sử dụng hàm băm SHA-256 để tạo ra
dấu văn tay (fingerprint) và gửi nó đến TSA. Digistamp sử dụng chương trình tạo
timestamp bảo mật để thêm thời gian và ký vào bản ghi sử dụng khóa bí mật của nó.
Đề án này có thể trả lời rõ ràng cho câu hỏi “ai” và “cái gì” của quá trình xác thực
nhưng câu trả lời “khi nào” không được chấp nhận vì phụ thuộc vào mức độ bảo mật
của khóa.
19
Hình 12 Sử dụng chữ ký số trong hệ thống e-timestamp
Giao thức liên kết có thể giải quyết vấn đề này bằng việc kiểm tra chắc chắn rằng
một yêu cầu nhãn thời gian đã được liên kết với các nhãn khác đến trước và sau nó, do
đó yêu cầu hay thậm chí là fingerprint gửi đến từ client được nối và được băm với đối
tượng bên cạnh nó theo thứ tự mà các yêu cầu đến.
1.2.4 Nguồn thời gian – Time Source
Để hữu ích thì hệ thống gãn nhãn phải có thời gian được công nhận bởi tất cả
mọi dùng. Để thực hiện việc này, [3] đưa ra giao thức NTP (Network Time
Protocol)để đồng bộ hóa các đồng hồ của mỗi máy tính. Belnet cung cấp dịch vụ NTP.
Giao thức thời gian mạng - Network Time Protocol ( NTP version 3, RFC 1305)
,là một giao thức phức tạp cho phép hệ thống có thể liên tục đồng bộ đồng hồ của nó
chống lại thời gian của nhiều server ( bảo vệ chống lại sự hỏng hóc của server trong
thời gian ngắn), với sự điều chỉnh cho độ trễ của mạng và sự xê dịch của đồng hồ. Mục
đích của nó là đồng bộ hóa các máy tính với nhau và với tham chiếu chung – Universal
Time, Coordinated – thông qua Internet.
NTP cho phép máy tính kết nối với mạng Internet có thể biết với độ chính xác đo
được thời điểm hiện tại là mấy giờ. Dịch vụ thời gian này được cung cấp trên mạng
Internet bởi các trạm làm việc và các router trên khắp thế giới.
20
Chƣơng 2. MỘT VÀI HỆ THỐNG GÁN NHÃN THỜI GIAN
2.1 Hệ thống trên lý thuyết
2.1.1 Hệ thống đơn giản
Thiết kế này được trình bày trong [4]. Giải pháp đơn giản nhất cho hệ thống
timestamp là sử dụng bên tin cậy thứ ba, đó là Time Stamp Authority (TSA) . TSA mở
rộng mỗi yêu cầu với ngày và thời gian hiện tại và ký vào kết quả để tạo ra
timestamp.Thiết kế này sử dụng hàm băm để nén văn bản gửi tới TSA. Việc này cho
phép lưu trữ bản gốc dữ liệu một cách bảo mật, làm giảm băng thông và nơi lưu giữ
cần thiết, làm tăng hiệu quả. Hệ thống này được xây dựng sử dụng hàm băm mật mã
và nguồn thời gian đã được giới thiệu ở các chương trước .
Hình 13 Hoạt động của hệ thống gán nhãn đơn giản
Quá trình gán nhãn hoạt động như sau:
- Client C gửi định danh và giá trị băm của văn bản (X) cần gán nhãn lên
Server TSA ( Time-Stamping Authority) : client gửi IDc , h(X).
- TSA gửi lại chứng nhận timestamp T=SK(IDC, h(X) , n , t), trong đó n là số
thứ tự của chứng nhận, t là ngày và thời gian hiện tại, SK là chữ ký điện tử
của TSA.
- Client nhận được chứng nhận và kiểm tra xem nó có phải được ký bởi TSA
hay không, chứng nhận đó bao gồm giá trị băm của văn bản client muốn gán
nhãn và thời gian chính xác.
Quá trình xác thực tương tự như quá trình gán nhãn, văn bản cũng được băm ra
và kết hợp với time stamp có được từ quá trình gán nhãn để xác thực xem văn bản hợp
lệ hay không theo các bước sau:
21
Tải về để xem bản đầy đủ
48 trang
10/06/2025
80
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Nghiên cứu và xây dựng một hệ thống gán nhãn thời gian", để 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:
- khoa_luan_nghien_cuu_va_xay_dung_mot_he_thong_gan_nhan_thoi.pdf
