Báo cáo nghiên cứu – Cài đặt Thuật toán RIPEMD – Khoa An toàn Thông tin – Học viện Kỹ thuật Mật mã
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản khá đầy đủ của tài liệu tại đây [ 445.58 KB, 25 trang ]
Bạn đang đọc : Cài đặt Thuật toán RIPEMD
HỌC VIỆN KỸ THUẬT MẬT MÃ
KHOA AN TOÀN THÔNG TIN
BÁO CÁO BÀI TẬP LỚN MÔN HỌC
MẬT MÃ HỌC NÂNG CAO
Chủ đề số 20
CÀI ĐẶT THUẬT TOÁN RIPEMD
Giảng Viên: TS.Trần Tuấn Anh
Thực hiện: Sinh viên
AT8C
1. Lê Xuân Đoàn
2. Bùi Đức Thiện
1
Ý KIẾN GIẢNG VIÊN
MỤC LỤC
2
LỜI NÓI ĐẦU
Ngày nay với việc ứng dụng của công nghệ thông tin càng ngày càng phổ biến rộng
rãi ảnh hưởng rất lớn đến diện mạo của đời sống kinh tế xã hội. Mọi công việc hàng
ngày của chúng ta đều có thể thực hiện với sự hỗ trợ của máy vi tính và mạng
internet[từ học tập giao dịch …] và máy tính và internet đã trở thành một phần khó có
thể tách rời với nhịp sống hiện đại ngày nay. Nhưng một
vấn đề khó đặt ra là làm sao
để giữ được bí mật thông tin cho đến khi chúng đến nơi mà chúng cần đến. Nhiều tổ
chức cá nhân đã tìm kiếm và đưa ra giải pháp bảo mật phương pháp mã hóa khá cao.
Như vậy mã hóa thông tin sẽ đảm bào cho thông tin tránh bị thay đổi hoặc sao chép.
Trong bài nghiên cứu này nhóm sẽ trình bày về vấn đề mã hóa thông tin sử dụng hàm
băm, tìm hiểu tổng quan về hàm băm và đi sâu tìm hiểu phân tích thiết kế cài đặt thuật
toán mã hóa RIPEMD
3
CHƯƠNG
1
HÀM BĂM MẬT MÃ
1.1 Tổng quan về hàm băm mật mã
Hiểu theo nghĩa đơn giản, hàm băm là hàm cho tương ứng một mảng dữ liệu
lớn với một mảng dữ liệu nhỏ hơn mà được dùng rộng rãi trong nhiều ứng dụng
tin học, không chỉ thuộc phạm vi mật mã. Ở đây, chúng ta chỉ xét đến các hàm
băm trong phạm vi các hàm băm mật mã, xem xét cụ thể đến các ứng dụng của
chúng trong việc đảm bảo tính toàn vẹn của dữ liệu.
Các hàm băm nhận đầu vào là một chuỗi bit có chiều dài hữu hạn tùy ý
và
tạo ra một chuỗi bit có chiều dài cố định bằng n bit [n > 0] gọi là mã băm [hash
code].
Trong mã hóa, mã băm được xem như là ảnh đại diện thu gọn [compact
representative image] của một chuỗi bit có độ dài hữu hạn tùy ý và được dùng
để nhận diện cho chuỗi bit đó. Kết hợp với công cụ tạo chữ ký số, các hàm băm
được dùng cho việc đảm bảo tính toàn vẹn của dữ liệu. Trong lược đồ chữ ký số,
mã băm của chuỗi bit được tính ở thời điểm T
1
và được bảo vệ để chống lại
mọi
sự thay đổi bất hợp pháp. Tại thời điểm T
2
sau đó, để kiểm tra xem chuỗi bit x có
bị thay đổi hay không, người ta thường tính giá trị hàm băm của chuổi bit này tại
thời điểm T
2
, mà ta ký hiệu là x
T2
, sau đó so sánh giá trị vừa tính với mã băm tại
thời điểm T1. Nếu 2 giá trị bằng nhau thì người ta chấp nhận chuổi bit tại thời
điểm T2 trùng khớp với chuổi bit tại thời điểm T1, tức chuỗi bit x vẫn chưa bị thay
đổi. Như vậy vấn đề bảo đảm tính toàn vẹn
của chuỗi bit có chiều dài tùy ý được
thay bằng việc bảo vệ sự toàn vẹn của chuỗi bit có chiều dài cố định.
1.2 Định nghĩa tổng quát của hàm băm
Hàm h[x] được gọi là một hàm băm nếu nó thoả mãn hai tính chất sau:
4
• Nén gọn [Compression]: Hàm h[x] tương ứng chuỗi bit đầu vào x
có chiều dài hữu hạn tuỳ ý vào chuỗi bit y = h[x] có chiều dài cố định
n >0 cho trước.
• Dễ tính toán [Easy of computation]: Với mọi chuỗi bit đầu vào x
có chiều dài hữu hạn tuỳ ý, h[x]
được tính toán dễ dàng.
1.3 Các tính chất của hàm băm mật mã
Một hàm băm mật mã lý tưởng có các tính chất sau :
1.3.1 Tính kháng tiền ảnh [Preimage resistance]
Với mọi đầu ra y cho trước, không thể tìm được bất kỳ dữ liệu đầu vào x sao
cho h[x] = y [hay không thể tìm được một thông điệp từ một giá trị băm cho trước].
1.3.2 Tính kháng tiền ảnh thứ hai [2
nd
– Preimage resistance]
Với mọi dữ liệu đầu vào x cho trước và y = h[x], không thể tính toán để tìm ra
được
giá trị x’ x sao cho h[x’]=h[x] [hay không thể tìm ra 2 thông điệp khác nhau
mà có cùng giá trị băm].
1.3.3 Tính kháng xung đột [Collision resistance]
Không thể tính toán để tìm được hai dữ liệu đầu vào x và x’ phân biệt sao cho
chúng có cùng giá trị băm h[x]=h[x’] [hay không thể sửa được một thông điệp mà
không làm thay đổi giá trị băm của nó].
1.4 Phân loại hàm băm mật mã
Dựa trên tham biến đầu vào của các hàm băm, các hàm băm mật mã được
phân thành hai lớp:
Lớp
các hàm băm sử dụng khoá [keyed hash functions], chẳng hạn như
MAC [Message Authentication Codes]: nhận hai giá trị đầu vào
o Thông điệp cần tính giá trị băm
o Khoá bí mật để băm văn bản theo đúng chuẩn quy định
Lớp các hàm băm không sử dụng khoá [unkeyed hash functions]: chỉ
nhận duy nhất một giá trị đầu vào là Thông điệp [message].
Trong lớp các hàm băm không sử dụng khoá thì MDCs [Modification
Detection Codes – mã nhận diện sự thay đổi] là lớp con của lớp này. Lớp
hàm
này lại tiếp tục phân thành các lớp con nhỏ hơn
5
– Hàm băm một chiều [One-Way Hash Functions – OWHFs]: các
hàm trong lớp này đều thoã tính chất là với mọi mã băm biết trước, không
thể tính toán để tìm được chuỗi bit đầu vào có mã băm bằng với mã băm
đã cho.
– Hàm băm kháng xung đột [Collision Resistant Hash Functions –
CRHFs]: các hàm trong lớp này thoã mãn tính chất không thể tính
toán để tìm ra hai chuỗi bit có cùng giá trị băm.
1.5 Cấu trúc của thuật toán
hàm băm
Khối dữ liệu đầu vào x có chiều dài tuỳ ý sẽ được phân thành các khối con liên
tiếp x1, x2, …, xm [với xi có chiều dài cố định là r]. Tuy nhiên do chiều dài khối ban
đầu là tùy ý nên ta cần thêm vào dữ liệu ban đầu một số bit phụ sao cho tổng số bit
của khối dữ liệu x sau khi thêm vào sẽ là bội số của r. Ngoài ra số bit phụ thêm vào
thường chứa một khối bit xác định chiều dài thực sự của khối dữ liệu khi chưa thêm
các bit phụ. Sau đó ta lần lượt cắt từng khối con r bit
từ khối x.
Mỗi khối con r bit xi ta thực hiện một hàm nén của hàm băm h[x] được ký hiệu
là f. Tại bước thứ i, hàm nến f nhận dữ liệu đầu vào là xi và kết quả trung gian của
bước trước đó để tạo đầu ra là kết quả trung gian bước thứ i, ký hiệu là Hi. Kết quả
trung gian tại mỗi bước Hi là một chuổi bit có độ dài cố định bằng n>0. Nếu ký hiệu
IV [init value] là giá trị khởi tạo ban đầu cho H0, thì quá trình lặp xử lý dãy các khối
con x1,x2,…, xm được mô tả như
sau:
H
0
=IV
H
1
= f[H
i-1,
x
i
], [i=1,…,m]
h[x] = g[H
m
]
H
i
là kết quả trung gian sau bước thứ i, là các biến dây chuyền. Hàm g[x]
ánh xạ biến dây chuyền cuối cùng để tạo ra mã băm kết quả. Và thông thường,
g[x] được chọn là ánh xạ đồng nhất: g[H
m
]
o
H
m
. Khâu then chốt trong xây dựng
hàm băm là thiết kế hàm nén f.
6
1.6 Ứng dụng của hàm băm mật mã
Một ứng dụng điển hình của một hàm băm mật mã học
như sau: Alice đưa cho
Bob một câu đố khó và tuyên bố rằng cô ấy đã giải được rồi. Bob muốn tự giải,
nhưng cũng muốn chắc chắn là Alice đúng là đã giải được. Do đó, Alice viết đáp án,
gắn thêm một nonce ngẫu nhiên, tính giá trị băm của nó, và đưa kết quả băm cho Bob
[trong khi vẫn giữ bí mật đáp án và nonce]. Bằng cách này, khi Bob tự giải xong,
Alice có thể chứng minh rằng cô đã có đáp án từ trước bằng cách đưa nonce cho
Bob. Trong thực tiễn, Alice và Bob thường là các chương
trình máy tính, và bí mật
thường là cái gì đó không dễ lừa bằng một lời giải cho câu đó. Ứng dụng trên được
gọi là một hệ thống tin cậy [commitment scheme].
Một ứng dụng quan trọng khác của các hàm băm bảo mật là sự kiểm tra tính
toàn vẹn của thông điệp. Ví dụ, việc xác định xem một file hay một thông điệp có bị
sửa đổi hay không có thể thực hiện bằng cách so sánh tóm tắt được tính trước và sau
khi gửi [hoặc một sự kiện bất kỳ nào đó]. Còn có thể dùng tóm tắt thông điệp
làm
một phương tiện đáng tin cậy cho việc nhận dạng file.
Một ứng dụng có liên quan là kiểm tra mật khẩu. Mật khẩu thường khôngđược
lưu dưới dạng văn bản rõ [clear text], mà ở dạng tóm tắt. Để xác thực một người
dùng, mật khẩu do người đó nhập vào được băm và so sánh với kết quả băm được
lưu trữ.
Do các lý do cả về bảo mật và hiệu năng chương trình, đa số các thuật toán
chữ ký số nói rằng chỉ có tóm lược của thông điệp, chứ không phải toàn văn thông
điệp, được “ký”. Các
hàm băm còn có thể được dùng để tạo các bit giả ngẫu nhiên
[pseudorandom].
1.7 Các hàm băm mật mã hiện nay
Trong danh sách dài các hàm băm mật mã dưới đây, có một số hàm băm được
cho là dễ bị tổn thương và không nên sử dụng. Ngay cả khi một hàm băm chưa bị
phá vỡ, một tấn công thành công đối với một biến thể yếu đó có thể làm giảm sự tự
tin của các chuyên gia và dẫn đến loại bỏ nó. Ví dụ, vào tháng 8 năm 2004 người ta
đã tìm ra những điểm yếu của một vài hàm băm phổ biến vào
thời đó, bao gồm SHA-
0, RIPEMD, và MD5. Điều này đã đặt ra câu hỏi an ninh lâu dài của các thuật
toán sau này được bắt nguồn từ những hàm băm này – đặc biệt, SHA-1 [một phiên
7
bản mạnh của SHA-0], RIPEMD-128, và RIPEMD-160 [cả hai phiên bản mạnh của
RIPEMD]. Vì vậy, cả SHA-0 và RIPEMD đều không được sử dụng rộng rãi kể từ
khi chúng được thay thế bởi các phiên bản mạnh.
Thuật toán Kích thước đầu ra Kíc
h
thước
trạng
thái
Xem thêm : Nuanced là gì
trong
Kích
thước
khối
Thông
điệp tối
đa
Kích
thước
word
Xung
đột
HAVAL 256/224/192/160/12
8
256 1024 64 32 Có
MD2 128 384 128 No 8
Kh
ả
năng
lớn
MD4 128 128 512 64 32 Có
MD5 128 128 512 64 32 Có
PANAMA 256 8736 256 No 32 Có lỗi
RIPEMD 128 128 512 64 32 Có
RIPEMD-
128/256
128/256 128 512 64 32 Khôn
g
RIPEMD-
160/320
160/320 160/320 512 64 32 Khôn
g
SHA-0 160 160 512 64 32 Có
8
Bảng 1: Các hàm băm mật
mã
9
CHƯƠNG 2
HÀM BĂM RIPEMD
2.1 Tổng quan về hàm băm RIPEMD
RIPEMD [RACE Integrity Primitives Evaluation Message Digest] là một họ
của hàm băm mật mã được phát triển ở Leuven- Bỉ bởi Hans Dobbertin, Antoon
Bosselaers và Bart Preneel tại nhóm nghiên cứu COSIC tại Katholieke Universiteit
Leuven và lần đầu tiên được xuất bản vào năm 1996. RIPEMD được dựa trên các
nguyên tắc thiết kế được sử dụng trong MD4, nhưng hiệu năng hoạt động phổ biến
hơn MD4
2.2
RIPEMD-128
RIPEMD – 128 là một hàm băm 128 -bit sử dụng xây dựng như mở rộng của
Thuật toán Merkle Damgard : hàm băm được xây dựng bằng cách duyệt một chức
năng nén 128 -bit mà mất như một đầu vào 512 -bit với đẩu ra là 128 bit.
Các chức năng nén RIPEMD – 128 dựa trên MD4, với các đặc thù mà nó sử
dụng hai trường hợp song song của nó, Chúng ta phân biệt hai chi nhánh tính toán của
nhánh trái và nhánh phải và chúng ta hiển thị bởi X
i
[resp. Y
i
] 32 bit của nhánh
trái
[resp. right branch].Quá trình này sẽ được cập nhật trong bước i của hàm nén .Quá
trình này bao gồm 64 bước chia thành 4 vòng 16 bước từng ở cả hai chi nhánh cụ thể
về quá trình:
Khởi tạo: Các đầu vào 128 -bit chuỗi cv
i
biến được chia thành 4 từ h
i
mỗi 32 bit, sẽ
sử dụng để khởi tạo các nhánh trái và phải 128 -bit trạng thái nội bộ :
10
Mở rộng tin: Khối tin đầu vào 512 -bit được chia thành 16 từ Mi của mỗi 32 bit. mỗi
từ Mi sẽ được sử dụng một
lần trong mỗi vòng theo một thứ tự hoán vị [ tương tự như
MD4 ] và cho cả 2 nhánh.
Chức năng của từng bước: Tại mỗi bước i ,sổ đăng ký X
i+1
và Y
i+1
được cập nhật
với các chức năng f
1
j
và f
r
j
điều đó phụ thuộc vào những vòng j trong mà i thuộc về:
Kết thúc quá trình: Một quyết toán và một feed-forward được áp dụng khi tất cả 64
bước đã được tính toán trong cả 2 chi nhánh. Bốn 32 -bit từ h
i
‘
soạn ra chuỗi biến cuối
cùng đã
thu được bằng cách :
2.3 RIPEMD-160
RIPEMD-160 là một hàm băm mật mã 160-bit, được thiết kế bởi Hans Dobbertin ,
Antoon Bosselaers và Bart Preneel. Nó được thiết kế để sử dụng như là một thay thế
an toàn cho các hàm băm 128-bit MD4, MD5 và RIPEMD. MD4 và MD5 được phát
triển bởi Ron Rivest cho RSA Data Security, trong khi RIPEMD được phát triển trong
khuôn khổ của dự án RIPE EU [ RACE Integrity Primitives Evaluation, 1988-1992 ] .
Có ba lý chính để xem đây là một sự thay
đổi tốt :
• Một kết quả băm 128 -bit không cung cấp đủ bảo vệ nữa, một cuộc tấn công
brute force vào hàm 128 bit chỉ đòi hỏi 2
64
hoặc 2.10
19
giá trị của hàm. Năm
1994 Paul van Oorschot và Mike Wiener cho thấy việc brute- lực lượng này có
thể được thực hiện trong vòng chưa đầy một tháng với một khoản đầu tư $
10.000.000
• Trong nửa đầu năm 1995 Hans Dobbertin tìm thấy va chạm đối với một phiên
bản của RIPEMD hạn chế đến hai vòng cùng của ba .Sử dụng kỹ thuật
tương tự
được sản xuất Hans vào mùa thu năm 1995 cho các va chạm [tất cả 3 vòng ]
11
MD4. Cuộc tấn công vào MD4 chỉ đòi hỏi một vài giây trên một máy tính, và
vẫn còn để lại một ít tự do để lựa chọn các tin nhắn, cầm quyền rõ ràng ra MD4
như là một hàm băm kháng va chạm. Ngay sau đó, vào mùa xuân năm 1996,
Hans cũng tìm thấy va chạm cho các chức năng nén MD5. Mặc dù chưa được
mở rộng đến va chạm với MD5 bản thân, cuộc tấn công này phôi nghi ngờ
nghiêm trọng về sức mạnh
của MD5 là một vụ va chạm
• Crypto 2004 Xiaoyun Wang, Dengguo Feng, Xuejia Lai và Hongbo Yu tìm
thấy sự xung đột trong: MD4, MD5, RIPEMD, and the 128-bit version of
HAVAL.
RIPEMD – 160 là một phiên bản được tăng cường của RIPEMD với một kết
quả băm 160 -bit, và dự kiến sẽ được an toàn trong mười năm tới hoặc hơn. Triết lý
thiết kế là xây dựng càng nhiều càng tốt về kinh nghiệm thu được bằng cách đánh giá
MD4, MD5, và RIPEMD. Giống như người tiền nhiệm của nó, RIPEMD – 160
được điều chỉnh cho bộ vi xử lý 32 -bit, mà chúng ta cảm thấy sẽ vẫn quan trọng
trong thập kỷ tới .
RIPEMD – 256 và RIPEMD – 320 là phần mở rộng tùy chọn tương ứng cho
RIPEMD – 128 và RIPEMD – 160, và được dành cho các ứng dụng của các hàm băm
mà đòi hỏi một kết quả hash lâu hơn mà không cần một mức độ bảo mật lớn hơn
12
CHƯƠNG 3
PHÂN TÍCH THIẾT KẾ VÀ CÀI ĐẶT RIPEMD
3.1 Phân tích
hình 3.1 Sơ đồ thuật toán
Mô tả thuật toán
13
Input : Thông điệp [văn bản] có
độ dài tùy ý
Ouput: Bản băm,đại diện cho văn bản gốc,độ dài cố định [ phụ thuộc vào thuật toán
RIPEMD mà bản băm có kích thước 128 bit,160 bit,256 bit,320 bit].
Giả sử thông điệp đầu vào là a có độ dài b [ b có thể bằng 0]
Phân tích thuật toán RIPEMD-160
RIPEMD-160 nén một chuỗi đầu vào kích thước tùy ý bằng cách chia thành
khối của mỗi 512 bit. Mỗi khối được chia thành 16 chuỗi 4 byte mỗi,và mỗi chuỗi 4-
byte đó được chuyển đổi thành một từ 32-bit
Để đảm bảo rằng kích
thước tổng số đầu vào là một bội số của 512 bit,đầu vào
được đệm thêm chuỗi n các số 0 [ 0 < n < 511] .Thông điệp đầu vào sẽ được xử lí qua
5 vòng song song .Kết quả của RIPEMD-160 được chứa trong 5 từ 32 bit
Hoạt động của thuật toán
1 :
A := [A + f [B; C; D] + X + K
]