Ch−¬ng tr×nh KC-01:
Nghiªn cøu khoa häc
ph¸t triÓn c«ng nghÖ th«ng tin
vµ truyÒn th«ng
§Ò tµi KC-01-01:
Nghiªn cøu mét sè vÊn ®Ò b¶o mËt vµ
an toµn th«ng tin cho c¸c m¹ng dïng
giao thøc liªn m¹ng m¸y tÝnh IP
Phô lôc: Mét sè nghiªn cøu vÒ hµm b¨m vµ
giao thøc mËt m·
Hµ NéI-2004
Môc lôc
Trang
Nghiªn cøu vÒ th¸m m· MD4, TrÇn Hång Th¸i 1
Va ch¹m vi sai cña SHA-0, Florent Chaboud vµ Antoiene Joux, Crypto’98 31
Ph©n tÝch SHA-1 trong chÕ ®é m· ho¸, Helena Handchuh, Lars R. Knudsen
vµ Matthew J. Robshaw, CT-RSA 2001
48
C¸c hµm b¨m dùa trªn m· khèi: ph−¬ng ph¸p thiÕt kÕ, Bart Preneel, RenÐ
Govaerts, Joã Vandewalle, CRYPTO’93
64
Nguyªn t¾c thiÕt kÕ cho hµm b¨m, Ivan Bjerre Damgard, Eurocrypt’91 75
Hµm b¨m nhanh an toµn dùa trªn m· söa sai, Lars Knudsen vµ Bart
Preneel, Crypto’97
87
§é mËt cña hµm b¨m lÆp dùa trªn m· khèi, Walter Hohl, Xuejia Lai,
Thomas Meier, Christian Waldvogel, Crypto 93
102
Ph©n phèi vµ tho¶ thuËn kho¸, NguyÔn Quèc Toµn 115
X¸c thùc vµ trao ®æi kho¸ cã x¸c thùc, Whitfield Diffie, Paul C. Van
Oorschot vµ Michael J. Wierner, Design, Codes and Cryptography, 192
123
CËp nhËt th«ng tin vÒ hµm b¨m SHA-1 145
N
NG
GH
HI
IÊ
ÊN
N
C
CỨ
ỨU
U
V
VỀ
Ề
T
TH
HÁ
ÁM
M
M
MÃ
Ã
M
MD
D4
4
Trần Hồng Thái
I
I.
.
M
MÔ
Ô
T
TẢ
Ả
T
TH
HU
UẬ
ẬT
T
T
TO
OÁ
ÁN
N
M
MD
D4
4
Thuật toán MD4 lấy một đầu vào là một message có độ dài bất kỳ và đầu ra là một
“tóm lược thông báo” (message digest), còn được gọi là “fingerprint”. Nó được
thiết kế khá gọn và nhanh trên máy 32-bit.
1. Mô tả thuật toán
Giả sử chúng ta có một message với độ dài là b-bit là đầu vào và chúng ta muốn
tìm tóm lược thông báo (message digest) của nó. Ở đây b là một số nguyên dương
bất kỳ, có thể bằng 0, hoặc lớn bất kỳ.
Ở đây chúng ta sử dụng các thuật ngữ sau: ‘word’ là biến 32 bit, byte là 8 bit. Quá
trình tính tóm lược thông báo này được thực hiện qua 5 bước sau:
Bước 1: Thêm vào các bit đệm (Padding bits)
Thông điệp được mở rộng bằng việc thêm các “bit đệm” sao cho độ dài (theo bit)
của nó đồng dư với 448 (modulo 512). Việc này sẽ đảm bảo khi thêm 64 bit (độ
dài - được trình bày sau) nữa, thì độ dài thông điệp là bội của 512.
Việc đệm được thực hiện như sau: một bit ‘1’ được nối với thông điệp và sau đó là
các bit ‘0’ cho đến khi độ dài thông điệp đồng dư với 448.
Bước 2: Thêm độ dài thông điệp (Length)
Độ dài thông điệp trước khi mở rộng b được biểu diễn bởi một số 64 bit (gồm 2
word) sẽ được thêm vào thông điệp sau bước 1 (theo thứ tự word thấp trước). Lúc
này độ dài thông điệp là bội của 512 bit (16 word 32 bit). Ký hiệu message kết quả
là M[0 … N-1], N là bội của 512.
Bước 3: Khởi tạo bộ đệm MD
Bốn biến A, B, C, D (là các thanh ghi 32 bit) được dùng để tính “message digest”.
Chúng được khởi tạo bằng các giá trị sau ở dạng Hexa, theo thứ tự các byte thấp
trước:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Bước 4: Xử lý thông điệp (message) theo từng khối 16-words
1
Trước tiên ta định nghĩa 3 hàm, mỗi hàm lấy 3 word (32 bit) làm đầu vào và đưa
ra một từ 32 bit:
F(X,Y,Z) = XY v not(X)Z
G(X,Y,Z) = XY v XZ v YZ
H(X,Y,Z) = X xor Y xor Z
Trong đó: XY là phép ‘and’ bit của X và Y, not(X) là phép lấy bù bit của X, X xor
Y là phép cộng modulo 2 theo bit của X và Y, X v Y là phép toán OR (hoặc) bit
của X và Y.
Thông điệp được xử lý theo từng khối 16 word như sau:
for i = 0 to N/16-1 do
/* Copy block i into X. */
for j = 0 to 15 do
set X[j] to M[i*16 +j]
end
/* Save A as AA, B as BB, C as CC, D as DD */
AA = A;
BB = B;
CC = C;
DD = D;
/* Round 1 */
/* Ký hiệu [abcd k s] là phép toán sau:
a = (a + F(b,c,d) + X[k]) <<< s
Thực hiện 16 lần như sau. */
[ABCD 0 3]; [DABC 1 7]; [CDAB 2 11]; [BCDA 3 19];
[ABCD 4 3]; [DABC 5 7]; [CDAB 6 11]; [BCDA 7 19];
[ABCD 8 3]; [DABC 9 7]; [CDAB 10 11]; [BCDA 11 19];
[ABCD 12 3]; [DABC 13 7]; [CDAB 14 11]; [BCDA 15 19];
/* Round 2 */
/* Ký hiệu [abcd k s] là phép toán sau:
a = (a + G(b,c,d) + X[k] + 5A82799) <<< s */
[ABCD 0 3]; [DABC 4 5]; [CDAB 8 9]; [BCDA 12 13];
[ABCD 1 3]; [DABC 5 5]; [CDAB 9 9]; [BCDA 13 13];
[ABCD 2 3]; [DABC 6 5]; [CDAB 10 9]; [BCDA 14 13];
[ABCD 3 3]; [DABC 7 5]; [CDAB 11 9]; [BCDA 15 13];
/* Round 3 */
/* Ký hiệu [abcd k s] là phép toán sau:
a = (a + H(b,c,d) + X[k] + 6ed9eba1) <<< s */
[ABCD 0 3]; [DABC 8 9]; [CDAB 4 11]; [BCDA 12 13];
[ABCD 2 3]; [DABC 10 9]; [CDAB 6 11]; [BCDA 14 13];
[ABCD 1 3]; [DABC 9 9]; [CDAB 5 11]; [BCDA 13 13];
[ABCD 3 3]; [DABC 11 9]; [CDAB 7 11]; [BCDA 15 13];
2
A = A + AA;
B = B + BB;
C = C + CC;
D = D + DD;
end; /* of loop on i */
Bước 5: Kết quả đầu ra (output)
Bản tóm lược thông điệp (message digest) là nội dung các thanh ghi A, B, C, D
theo thứ tự từ byte thấp của A đến byte cao của D.
2. Mã nguồn của MD4
Chúng tôi đã download mã nguồn của thuật toán mã hoá MD4 trên Internet.
Chương trình khá nhỏ gọn, gồm 3 file là global.h, md4.h (2 file header khai báo
các PROTOTYPE, hằng) và md4c.c - mã nguồn của MD4. Chúng tôi đã đọc hiểu
mã nguồn của MD4 và thử nghiệm nhỏ như sau: thực hiện băm một xâu có độ dài
nhỏ hơn 448 bit 1000000 lần trên máy Dell 350MHz. Thời gian tính toán này là
I
II
I.
.
T
TH
HU
UẬ
ẬT
T
T
TO
OÁ
ÁN
N
T
TH
HÁ
ÁM
M
M
MD
D4
4
Tác giả của thuật toán thám MD4 là Hans Dobbertin với bài “Cryptanalysis of
MD4” - năm 1997. Thuật toán MD4 được Rivest đề nghị năm 1990 và 2 năm sau
là RIPEMD được thiết kế mạnh hơn MD4. Năm 1995, tác giả đã tìm ra một tấn
công chống lại 2 vòng của RIPEMD. Phương pháp này được bổ sung và có thể sử
dụng cho tấn công đủ 3 vòng của MD4.
Theo tác giả thì thuật toán này có thể tìm ra “va chạm” (collision) cho MD4 chỉ
trong một vài giây trên một máy PC. Đặc biệt tác giả đã đưa ra một ví dụ rất cụ thể
có tính thực hành và thuyết phục cao bằng việc tìm ra va chạm của thông điệp có ý
nghĩa. Kết quả chính của bài báo này là khẳng định “MD4 là không phải hàm hash
không va chạm”.
Thuật toán này là kiểu tấn công tìm collision: tức là biết giá trị khởi đầu IVo, tìm
các thông điệp X và X’ sao cho hash(IVo, X) = hash(IVo, X’).
1. Tóm tắt thuật toán do Dobbertin trình bày.
1.1 Ký hiệu và qui ước sử dụng cho thuật toán
Tất cả các biến và hằng số được sử dụng đều là các số 32 bit. Các số hạng được
biểu diễn theo modulo 232. Các ký hiệu ^, v, ⊕ và ¬ lần lượt là các phép toán
AND, OR, XOR và lấy phần bù theo bit. Với một từ W - 32 bit, W<<32 ký hiệu của
phép dịch vòng trái W đi s vị trí (với 0 ≤ s ≤ 32). Và -W<<s viết tắt cho -(W<<s).
Ký hiệu X=(Xi), i<16 là toàn bộ 16 words (512 bits) và được thiết lập
như sau:
16
~~ )( <
=ii
XX
3