Xem mẫu
- ----- -----
BÁO CÁO ĐỒ ÁN: MÔN HỌC BẢO MẬT
THÔNG TIN
ĐỀ TÀI: CHỮ KÝ SỐ
- Chữ ký số - Các thuật toán và tấn công 2009
BÁO CÁO ĐỒ ÁN
MÔN HỌC BẢO MẬT THÔNG TIN
(ĐỀ TÀI CHỮ KÝ SỐ)
A. Danh sách nhóm
STT MSSV Tên Email SDT
Huỳnh Văn Bách
1. 406170001 bach.huynhvan@gmail.com 01698815297
Lê Kiều Lệ Diễm
2. 406170006 lekieulediem@gmail.com 0983728190
Nguyễn Thị Tuyết Hải
3. 406170015 nguyenthituyethai@gmail.com 0938170788
Dương Thanh Thảo
4. 406170046 dthao18@yahoo.com 0932613917
Nội dung nghiên cứu
B.
Tổng quan về chữ ký số
I.
Các thuật toán tạo chữ ký số và so sánh
II.
Lý thuyết về cách tấn công chữ ký số
III.
Giới thiệu về Rainbow Crack Tool
IV.
Demo dùng Rainbow Crack Tool để tấn công chữ ký số.
V.
Ứng dụng chữ ký số trong thực tế tại Việt Nam
VI.
Chi tiết nội dung
C.
Tổng quan về chữ ký số
I.
Sự cần thiết của chữ ký số
1.
Cơ chế xác thực thông tin bảo vệ hai bên trao đổi thông điệp khỏi bên thứ ba. Tuy nhiên
cơ chế này không bảo vệ được một bên khi bên kia cố ý vi phạm, ví dụ nh ư:
A có thể làm giả một thông điệp và tuyên bố rằng thông điệp này do B gửi. A chỉ
-
cần tạo một thông điệp và thêm vào mã xác thực sử dụng khóa mà A và B chia sẻ.
Nhóm DSII [BDHT] Page 1
- Chữ ký số - Các thuật toán và tấn công 2009
B có thể phủ nhận đã gửi thông điệp. Bởi vì A có thể giả mạo thông điệp nên
-
không có cách nào chứng minh sự thật là B đã gửi.
Trong trường hợp không có sự tin tưởng hoàn toàn giữa người gửi và người nhận, cần có
một cơ chế tốt hơn xác thực. Giải pháp thu hút nhất cho vấn đề này là chữ ký số. Chữ ký
số tương tự như chữ ký tay, phải có các tính chất sau:
Phải xác nhận tác giả và ngày giờ, thời gian ký.
Phải xác nhận nội dung tại thời điểm ký.
Phải được xác minh bởi bên thứ 3 để giải quyết tranh chấp.
Dựa trên nền tảng các tính chất trên, chúng ta có thể hình thành các yêu cầu cho chữ ký
số như sau:
Chữ ký số là một khuôn mẫu các bit phụ thuộc vào thông điệp được ký .
Chữ ký số phải sử dụng những thông tin độc lập với người gửi để ngăn chặn giả
mạo và từ chối hành vi.
Phải tương đối dễ dàng để tạo ra chữ ký số
Phải tương đối dễ dàng để nhận ra và xác minh chữ ký số.
Không thể giả mạo được một chữ ký số, tức là tạo một thông điệp mới cho một
chữ ký đã tồn tại hoặc tạo một chữ ký giả cho một thông điệp cho trước.
Có thể sao chép được chữ ký số để lưu trữ.
2. Khái niệm chữ ký số
Chữ ký số là một cơ chế xác thực cho phép người tạo thông điệp có thể thêm vào 1 đoạn
mã có vai trò như là một chữ ký. Chữ ký số được tạo ra bằng cách lấy mã băm của thông
điệp và mã hóa bằng khóa riêng.
- Chữ kí số trong máy tính được biểu diễn bằng 1 chuỗi bit.
- Chữ kí số được tính tóan dựa trên các qui luật và các thông số cho phép sự đồng nhất
của chữ kí và tòan vẹn của dữ liệu được xác nhận.
- Chữ kí số được phát sinh cả cho dữ liệu lưu trữ và truyền đi.
- Chữ kí số được tạo ra bằng khóa riêng ( private key) và xác nhận chữ kí bằng khóa
chung tương ứng (public key)
Kỹ thuật tạo chữ ký số
3.
Nhóm DSII [BDHT] Page 2
- Chữ ký số - Các thuật toán và tấn công 2009
Ký trực tiếp:
i)
Chữ ký số trực tiếp chỉ liên quan tới các bên tham gia (nguồn, đích). Giả định rằng bên
đích biết khóa chung của nguồn. Một chữ ký số có thể được tạo ra bằng cách mã hóa toàn
bộ thông điệp bằng khóa riêng của người gửi:
hoặc mã hóa mã băm của thông điệp bằng khóa riêng của người gửi
Tính bí mật có thể có được bằng cách mã hóa toàn bộ thông điệp cộng chữ ký bằng khóa
chung của người nhận (public-key encryption) hoặc khóa bí mật được chia sẻ (Symmetric
encryption)
Nhóm DSII [BDHT] Page 3
- Chữ ký số - Các thuật toán và tấn công 2009
Trong trường hợp tranh chấp, một bên thứ ba cần phải xem được thông điệp và chữ ký
của nó. Nếu chữ ký được tính toán theo một thông điệp đã được mã hóa thì bên thứ ba
cần đến khóa giải mã để đọc được thông điệp gốc.
Tất cả dạng ký trực tiếp được nêu trên có một điểm yếu chung: Tính hợp pháp của dạng
ký này đều phụ thuộc vào sự bảo mật khóa riêng của người gửi. Nếu người gửi muốn phủ
nhận hành vi gửi thông điệp của mình, người gửi có thể tuyên bố rằng khóa riêng của
mình bị mất hay bị đánh cắp và có ai đó đã giả mạo chữ ký của mình. Có thể sử dụng các
cơ chế điều khiển quản lý liên quan tới bảo mật khóa riêng để ngăn chặn hoặc ít nhất là
giảm đi nguy cơ này, nhưng mối đe dọa vẫn còn ít nhất là một mức độ nào đó.
Một mối nguy hiểm khác là khóa riêng có thể bị đánh cắp thực sự từ X vào thời điểm T.
Đối thủ có thể gửi một thông điệp ký bằng chữ ký của X và thời gian trước hoặc bằng T.
Ký qua trọng tài
ii)
Vấn đề của ký trực tiếp có thể giải quyết bằng cách sử dụng một trọng t ài.
Có nhiều dạng ký qua trọng tài khác nhau. Mỗi thông điệp gửi từ bên X tới bên nhận Y đi
qua một trọng tài A, A kiểm tra chữ ký và thông điệp gửi tới Y kèm theo xác nhận thông
điệp đã được kiểm tra bởi trọng tài. Sự hiện diện của A giải quyết vấn đề thô ng điệp có
thể bị phủ nhận bởi X.
Trọng tài đóng một vai trò cốt yếu trong dạng này, và tất cả các bên phải có sự tin tưởng
tuyệt đối vào cơ chế làm việc của trọng tài.
Giả định rằng người gửi X và trọng tài A chia sẻ khóa bí mật Kxa, Y và trọng tài A chia sẻ
khóa bí mật Kay. X tạo ra một thông điệp M và tính toán mã băm của nó là H(M). Sau đó
X chuyển thông điệp và chữ ký tới A. Chữ ký bao gồm một định danh ID X của X cộng
với mã băm, tất cả được mã hóa dùng khóa Kxa. A giải mã chữ ký và kiểm tra mã băm để
xác thực thông điệp. Sau đó A chuyển thông điệp tới Y, mã hóa bằng K ay. Thông điệp
bao gồm định danh IDX, thông điệp gốc từ X, chữ ký và nhãn thời gian. Y có thể giải mã
Nhóm DSII [BDHT] Page 4
- Chữ ký số - Các thuật toán và tấn công 2009
để khôi phục thông điệp và chữ ký. Nhãn thời gian chỉ ra rằng thông điệp đúng thời đi ểm
và không phải là phát lại.
(1) X A: M||E(Kxa, [IDX||H(M)])
(2) A Y: E(Kay, [IDX||M||E(Kxa, [IDX||H(M)])||T])
(a) Mã hóa thông thường, trọng tài có thể thấy được nội dung thông điệp
(1) X A: IDX||E(Kxy, M)||E(Kxa, [IDX||H(E(Kxy, M))])
(2) A Y: E(Kay,[IDX||E(Kxy, M)])||E(Kxa, [IDX||H(E(Kxy, M))||T])
(b) Mã hóa thông thường, trọng tài không thấy được nội dung thông điệp
(1) X A: IDX||E(PRx, [IDX||E(PUy, E(PRx, M))])
(2) A Y: E(PRa, [IDX||E(PUy, E(PRx, M))||T])
(c) Mã hóa bất đối xứng, trọng tài không thấy được nội dung thông điệp
Trong các biểu thức:
= người gửi
X
= người nhận
Y
= Trọng tài
A
= thông điệp
M
= nhãn thời gian
T
Các thuật toán tạo chữ ký số
II.
1. ElGamal
ElGamal là một hệ thống chữ ký số dựa trên độ phức tạp của việc tính toán logarit rời rạc,
được mô tả bởi Taher ElGamal vào năm 1984.
Nhóm DSII [BDHT] Page 5
- Chữ ký số - Các thuật toán và tấn công 2009
Thuật toán ElGamal hiện nay trên thực tế hiếm khi được sử dụng. Phiên bản của ElGamal
do NSA phát triển, được biết đến và sử dụng rộng rãi hơn hiện nay là DSA. DSA ch o
phép độ dài của chữ ký ngắn hơn ElGamal.
Các bước tạo, ký và xác minh thực hiện như sau:
Tạo các tham số
i)
Bên người ký hoặc một bên thứ 3 đáng tin cậy nào đó chọn một số nguyên tố lớn p
Chọn g là một số ngẫu nhiên thuộc nhóm Z*p (g là một primitive root modulo p)
Tạo khóa
ii)
Chọn một khóa bí mật k với 1 ≤ k ≤ p
Tính toán giá trị v = gk(mod p)
Công bố khóa công khai là (p,g,v)
Ký lên một thông điệp D, với D là 1 số nguyên thỏa 1
- Chữ ký số - Các thuật toán và tấn công 2009
Chữ ký ElGamal có chiều dài vào khoảng 2log2(p) bits. Để bảo đảm an toàn khi hacker
tấn công vào bài toán logarit ngược, số nguyên tố p thường được chọn vào khoảng 1000
và 2000 bits, vậy chữ ký nằm trong khoảng 2000 và 4000 bits
2. DSA (Digital Signature Algorithm)
Các thao tác tạo khóa, ký và xác minh thực hiện như sau:
Tạo khóa
i)
Chọn một số ngẫu nhiên p đủ lớn sao cho 2L-1
- Chữ ký số - Các thuật toán và tấn công 2009
So sánh ElGamal và DSA: DSA là hệ thống được phát triển từ ElGamal nên các phép
tính toán gần tương tự như nhau, tuy nhiên khi tính toán giá trị r của chữ ký:
Đối với ElGamal, giá trị r tính bằng: r = ge (mod p) nên r nằm trong khoảng từ 1 đến p-1
Đối với DSA, giá trị r = (gk mod p) mod q nên r nằm trong khoảng 1 đến q-1
(e và k đều là những số ngẫu nhiên ứng với các message khác nhau)
Từ 2 công thức trên thấy rằng độ dài chữ ký của DSA là nhỏ hơn ElGamal
Một điểm ưu việt của DSA là có thể tăng tốc độ tính toán chữ ký. Ngoài giá trị hàm băm
H(M) của thông điệp được sử dụng để tính giá trị s thì tất cả các tham số còn lại đều có
thể tính trước và lưu trữ để sử dụng lúc cần (ví dụ như khi chọn được giá trị k ngẫu nhiên
phù hợp thì có thể lấy các giá trị k-1, r… đã tính trước). Điều này làm cho tốc độ tính toán
chữ ký được tăng lên.
DSA được sử dụng trong chuẩn chữ ký số DSS (Digital Signature Standard)
3. RSA
Thuật toán RSA được phát minh bởi Rivest, Shamir và Adelman. Việc sử dụng t huật toán
này để tạo khóa, xác minh khóa được chỉ rõ trong chuẩn American National Standard
(ANS) X9.31 và Public Key Cryptography Standard (PKCS) #1.
Tạo khóa:
i)
Chọn 2 số nguyên tố p, q. Chúng sẽ được giữ bí mật.
Chọn v sao cho:
gcd(v, (p - 1)(q - 1)) = 1
Công khai N = p*q và v
Tạo chữ ký:
ii)
Tính s sao cho:
sv ≡ 1 (mod (p − 1)(q − 1))
Ký tài liệu D bằng phép tính:
S ≡ Ds (mod N)
Nhóm DSII [BDHT] Page 8
- Chữ ký số - Các thuật toán và tấn công 2009
iii) Xác minh:
Tính Sv mod N
So sánh kết quả với D
Đánh giá độ an toàn và ứng dụng:
Không giống như DSA, RSA không thể sử dụng bởi nhiều hơn một người. Nếu 2
người muốn dung RSA thì phải cùng tính khóa chung, khóa riêng và không được
công khai.
Độ bảo mật của RSA phụ thuộc vào chiều dài của phép modulo và tính bảo mật
của hàm băm.
Thuật tóan RSA không dùng các thông số miền (domain parameters), chỉ có DSA
và ECDSA dùng , thông số miền được chính nó hay các tồn tại khác phát sinh.
4. ECDSA(Elliptic Curve Digital Signature Algorithm)
EDSA được đề xuất đầu tiên vào năm 1992 bởi Scott Vanstone, và được chấp nhận bởi
ISO 1998, ANSI 1999, IEEE 2000.
Tạo khóa:
i)
Khóa riêng d là số nguyên ngẫu nhiên thỏa : d Є [1, n - 1]
Khóa chung Q : Q = d*G
Tạo chữ ký:
ii)
Để sinh ra chữ ký cho thông điệp M của thực thể A, thực hiện các phép tính sau:
1. e = SHA-1(M)
k Є [1,n − 1]
2.
r = x1 (mod n), trong đó (x1, y1) = kQ. Nếu r = 0 quay lại bước 2
3.
s = k-1(e + dr) (mod n). Nếu s = 0 quay lại bước 2
4.
chữ ký (r, s)
iii) Xác minh:
Kiểm tra r, s có phải là các số nguyên thuộc [1, n - 1]. Nếu không thì kết luận
1.
không đúng
2. e = sha-1(m)
Nhóm DSII [BDHT] Page 9
- Chữ ký số - Các thuật toán và tấn công 2009
w = s-1 (mod n)
3.
4. u1 = ew (mod n)
5. u2 = rw (mod n)
6. (x1, y1) = u1*G + u2*Q
Chữ ký hợp lệ nếu r = x1(mod n), ngược lại là không đúng
7.
Đánh giá độ an toàn và ứng dụng:
Chiều dài khóa công khai của ECDSA nhỏ hơn DSA nên thuận tiện trong truyền
thông. Các phép toán trong thuật toán ECDSA cũng thực hiện nhanh hơn RSA, DSA.
Chính vì những lợi ích về chiều dài chữ ký, băng thông, tính toán nên ECDSA là sự lựa
chọn hấp dẫn hơn cho XML, smart card, máy gia tốc phần cứng, các ứng dụng kinh tế .
5. GGH
GGH là viết tắt của Goldreich – Goldwasser – Halevi, một lược đồ ký số được đề xuất
năm 1995 và công bố năm 1997, dựa trên việc giải quyết bài toán vecto gần nhất (closest
vector problem – CPV) trong 1 lưới (lattice). Người ký mô tả sự biết đến vecto cơ sở tốt
(good basis) của lưới bằng cách dùng nó để giải quyết CPV trên 1 điểm đại diện cho 1
thông điệp, người xác minh sử dụng một vecto cơ sở xấu (bad basis) cho cùng 1 lưới để
xác minh chữ ký dưới hình thức xem xét chữ ký có phải thực sự là một điểm trên lattice
và đủ gần với điểm thông điệp (message point) hay không.
6. NTRU(n-th degree truncated polynomial ring)
Tại CRYPTO ’96, một hệ thống mã hóa bất đối xứng mới có hiệu quả cao được giới
thiệu, đó là NTRU. Bên dưới NTRU là một bài toán khó về tìm kiếm một vecto ngắn
trong một lưới cố định. Giao thức xác thực và lược đồ ký số dựa trên thuật toán mã hóa
bất đối xứng NTRU được gọi là NSS (NTRU Signature Scheme). NTRUSign được chuẩn
hóa bởi IEEE P1363.
Chọn các tham số NTRU: (N, q, d) trong đó N là số nguyên tố; q, p là 2 số nguyên
tố cùng nhau và q luôn lớn hơn d
Tạo khóa:
i)
Chọn đa thức f, g Є T (d +1,d)
Tìm F, G thỏa: f * G – g * F = q
Tính h = f-1 * g (mod q)
Nhóm DSII [BDHT] Page 10
- Chữ ký số - Các thuật toán và tấn công 2009
Công khai khóa h
Tạo chữ ký:
ii)
Chọn D =(D1, D2) mod q
Tính: v1 = (D1 * G − D2 * F) / q
v2 = (-D1 * g + D2 * f) / q
Tính: s = v1 * f + v2 * F
Công khai chữ ký (D, s)
Xác minh chữ ký:
iii)
Tính t = h * s (mod q)
Kiểm tra (s, t) gần với (D1, D2)
Đánh giá độ an toàn và ứng dụng
Ntru nhanh hơn hẳn các các thuật toán tạo chữ ký số khác như ELGaml, RSA,
ECC. Với cùng mức độ an toàn k bít, mã hóa và giải mã với ELGamal, RSA, ECC
đòi hỏi O(k3) phép toán trong khi đó Ntru chỉ cần O(k2) phép toán. Các phép toán
này cũng dễ dàng thực hiện bởi phần cứng và phần mềm.
Bị tấn công malleableschemes. Tức là tạo ra một cặp thông điệp – chữ ký chưa
bao giờ được tiến hành bởi người ký hợp pháp. Chúng ta có thể tìm thấy một chữ
ký thứ 2 của cùng một thôn g điệp. Trong trường hợp này người ta không thể phân
biệt được chữ ký thứ 2 được tạo ra từ người biết khóa bí mật hay từ một kẻ giả
mạo, và để tìm ra đâu là thông điệp của người ký hợp pháp thì n gười đó không còn
cách nào khác là phải đưa ra khóa bí mật của mình. Dù vậy, kẻ tấn công vẫn
không thể thay đổi được nội dung của thông điệp.
Lý thuyết về cách tấn công chữ ký số
III.
Có nhiều phương pháp tấn công chữ ký số khác nhau, ở đây do giới hạn về thời gian nên
nhóm chỉ nghiên cứu tấn công vào chữ ký số trực tiếp không thông qua trọng tài.
Tấn công chữ ký nhằm 2 mục tiêu:
Giả mạo chữ ký (forgery attack):
Nhóm DSII [BDHT] Page 11
- Chữ ký số - Các thuật toán và tấn công 2009
Tìm chữ ký của một thông điệp M khi biết các khóa công khai, các thông điệp
-
khác và chữ ký tương ứng
Cho trước thông điệp M và chữ ký tương ứng, thay đổi nội dung thông điệp M
-
thành M’ sao cho chữ ký vẫn được xác minh là đúng.
Tìm khóa bí mật của người ký (key recovery attack): Phục hồi được khóa bí mật
của người ký từ các thông điệp M và chữ ký tương ứn g
Bản chất chữ ký số được tạo ra bới 2 thành phần: dùng hàm băm và dùng mã hóa bất đối
xứng (public – key cryptography)
Mỗi lược đồ ký số sử dụng một thuật toán mã hóa bất đối xứng khác nhau nên cách tấn
công cũng khác nhau. Ví dụ như các lược đồ ký số dùn g RSA có thể bị tấn công bằng
brute-force, mathematicalcal attack, timing attack hoặc chosen ciphertext attack. Mục
tiêu là tìm ra cách thức tạo một chữ ký giả cho một thông điệp M cho trước (ví dụ như
tìm khóa bí mật của người ký)
Một cách tấn công khác là nhằm vào điểm yếu của các hàm băm (hash function). Hàm
băm có chức năng biến đổi khối thông tin gốc độ dài bất kỳ thành khối thông tin có độ
dài cố định gọi là mã băm. Các tính chất một chiều, không tìm được đụng độ yếu và đụng
độ mạnh của nhiều hàm băm hiện nay đã bị phá vỡ bởi phân tích toán học, các công cụ và
máy tính.
2 dạng tấn công hàm băm thông dụng là Preimage attack và Collision attack. Trong tấn
công dạng Preimage, một người tấn công sẽ cố gắng tìm ra một thông điệp M nào đó mà
từ đó sinh ra một mã băm H(M) cho trước. Trong collision attack, người tấn công sẽ cố
gắng tìm kiếm 2 thông điệp có cùng mã băm.
Các hàm băm tìm thất đụng độ đã được công bố là SHA-0, MD4, MD5, HAVAL-128, và
hàm băm gần đây nhất bị phá vỡ là SHA-1
Tính chất đụng độ của hàm băm MD5
i)
Chứng minh khả năng tấn công MD5 bằng tool:
-Ta có kết quả từ hàm băm Md5 như sau:
Nếu Md5(x) =Md5(y) thì Md5( x+q)= Md5( y+q)
Nhóm DSII [BDHT] Page 12
- Chữ ký số - Các thuật toán và tấn công 2009
Nên nếu ta có một cặp message x, y có cùng giá trị Md5 ,thì chúng ta có thể gắn vào
thêm một lượng p thì giá trị md5 vẫn giống nhau, kích thước của q là bất kì,
-Trước hết ta tìm 1 căp vecto x,y ( bạn có thể tự tìm), ở đây ta dùng cặp vactơ sau ,
chúng có cùng giá trị Md5 do 2 điều tra viên người Trung Quốc Joux và Wang đưa ra là :
static byte[] vec1 =
{
0xd1, 0x31, 0xdd, 0x02, 0xc5, 0xe6 , 0xee , 0xc4 , 0x69 , 0x3d, 0x9a
, 0x06 , 0x98 , 0xaf , 0xf9 , 0x5c , 0x2f , 0xca , 0xb5 , /**/0x87 , 0x12 , 0x46 , 0x7e ,
0xab , 0x40 , 0x04 , 0x58 , 0x3e , 0xb8 , 0xfb , 0x7f , 0x89 , 0x55 , 0xad , 0x34 , 0x06 ,
0x09 , 0xf4 , 0xb3 , 0x02 , 0x83 , 0xe4 , 0x88 , 0x83 , 0x25 , /**/0x71 , 0x41 , 0x5a,
0x08 , 0x51 , 0x25 , 0xe8 , 0xf7 , 0xcd , 0xc9 , 0x9f , 0xd9 , 0x1d , 0xbd , /**/0xf2 , 0x80
, 0x37 , 0x3c , 0x5b , 0xd8 , 0x82 , 0x3e
, 0x31 , 0x56 , 0x34 , 0x8f , 0x5b , 0xae , 0x6d , 0xac , 0xd4 , 0x36 , 0xc9 , 0x19 , 0xc6
, 0xdd , 0x53 , 0xe2 , /**/0xb4 , 0x87 , 0xda , 0x03 , 0xfd , 0x02 , 0x39 , 0x63 , 0x06 ,
0xd2 , 0x48 , 0xcd , 0xa0 , 0xe9 , 0x9f , 0x33 , 0x42 , 0x0f , 0x57 , 0x7e , 0xe8 , 0xce ,
0x54 , 0xb6 , 0x70 , 0x80 , /**/0xa8 , 0x0d , 0x1e , 0xc6 , 0x98 , 0x21 , 0xbc , 0xb6 ,
0xa8 , 0x83 , 0x93 , 0x96 , 0xf9 , 0x65 ,/**/ 0x2b , 0x6f , 0xf7 , 0x2a , 0x70}
static byte[] vec2 =
{
0xd1 , 0x31, 0xdd , 0x02 , 0xc5 , 0xe6 , 0xee , 0xc4 , 0x69 , 0x3d ,
0x9a , 0x06 , 0x98 , 0xaf , 0xf9 , 0x5c, 0x2f , 0xca , 0xb5 , /**/0x07 , 0x12 , 0x46 , 0x7e ,
0xab , 0x40 , 0x04 , 0x58 , 0x3e , 0xb8 , 0xfb , 0x7f , 0x89 , 0x55 , 0xad , 0x34 , 0x06 ,
0x09 , 0xf4 , 0xb3 , 0x02 , 0x83 , 0xe4 , 0x88 , 0x83 , 0x25 ,/**/ 0xf1 , 0x41 , 0x5a ,
0x08 , 0x51 , 0x25 , 0xe8 , 0xf7 , 0xcd , 0xc9 , 0x9f, 0xd9 , 0x1d , 0xbd , /**/0x72 , 0x80
, 0x37 , 0x3c , 0x5b, 0xd8 , 0x82 , 0x3e , 0x31 , 0x56 , 0x34 , 0x8f , 0x5 b , 0xae , 0x6d ,
0xac , 0xd4 , 0x36
, 0xc9 , 0x19 , 0xc6 , 0xdd , 0x53 , 0xe2 , /**/0x34 , 0x87 , 0xda , 0x03 , 0xfd , 0x02 ,
0x39 , 0x63 , 0x06 , 0xd2 , 0x48 , 0xcd , 0xa0, 0xe9 , 0x9f , 0x33 , 0x42 , 0x0f , 0x57 ,
0x7e , 0xe8 , 0xce , 0x54 , 0xb6 , 0x70 , 0x80 , /**/ 0x28 , 0x0d , 0x1e, 0xc6 , 0x98 ,
Nhóm DSII [BDHT] Page 13
- Chữ ký số - Các thuật toán và tấn công 2009
0x21 , 0xbc , 0xb6 , 0xa8 , 0x83 , 0x93 , 0x96 , 0xf9 , 0x65 , /* flag byte*/0xab , 0x6f ,
0xf7 , 0x2a , 0x70 }
Mỗi vecto có kích thước 128 bye
-
chương trình tấn công sau theo format nhi phân , với đuôi file mở rộng là .bin , tạo
ra 2 file goodexe và evilexe từ 2 vecto trên, rối từ đó sinh ra 2 file good.bin và evil.bin, 2
file này có cùng giá trị Md5 như hình ảnh sau:
-Khi thêm lương dữ liệu trong goodexe.exe vào evilexe.exe thì giá trị hàm băm thay đổi
nhưng hash(good.bin)=hash(evil.bin)
- Ngược lại khi thêm lượng dữ liệu trong evilexe.exe vào file good thì giá trị hàm băm
cũng thay đổi nhưng hash(good.bin)=hash(evil.bin).
Nhóm DSII [BDHT] Page 14
- Chữ ký số - Các thuật toán và tấn công 2009
-Ờ đây ta có 2 file là good.bin và evil.bin , ta se kiểm tra xem chương trình nà y có đúng
không :
+ trước hết ta tính lại Hash của evil.bin , ta đươc như sau:
Nhóm DSII [BDHT] Page 15
- Chữ ký số - Các thuật toán và tấn công 2009
Nhóm DSII [BDHT] Page 16
- Chữ ký số - Các thuật toán và tấn công 2009
+ Tính lại hash của good.bin ta được như sau:
Nhóm DSII [BDHT] Page 17
- Chữ ký số - Các thuật toán và tấn công 2009
Như vây giá trị hàm băm của 2 file là đúng và có giá trị giống nhau
kết luận : việc tìm 2 file khác nhau có giá trị Md5 giống nhau là có thề thục hiện
được .=> hàm băm MD5 có khả năng bị tấn công
Tính chất đụng độ của hàm băm SHA-1
ii)
Năm 1993, NSA công bố một hàm băm tương tự như MD5, gọi là SHA (Secure Hash
Algorithm). Năm 1995, sau khi phát hiện điểm yếu của SHA, NSA c ải tiến thuật toán này
thành SHA-1. Hiện nay ngoài MD5, SHA-1 là một trong những hàm băm phổ biến nhất.
Hàm băm SHA-1 cho ra mã băm độ dài 160 bít, có nghĩa là mỗi thông điệp sẽ băm thành
1 số 160 bit. Nhưng vì số mã băm có thể có rất lớn, nên nếu băm 1^80 thông điệp ngẫu
nhiên thì sẽ tìm được một cặp thông điệp có mã băm giống nhau. Cách này gọi là tìm
đụng độ theo “ brute-force”, tìm bao nhiêu thông điệp phụ thuộc vào độ dài của mã băm.
Phá vỡ hàm băm nghĩa là có thể tìm ra đụng độ nhanh hơn cách trên, và 3 nhà nghiên cứu
người Trung Quốc, Xiaoyun Wang, Lisa Yiqun Yin và Hongbo Yu đã công bố vào năm
2005.
Theo như các nhà toán học này công bố thì có thể tìm thấy được đụng độ của SHA-1 sau
2^69 bước tính toán hàm băm, nhanh hơn 2000 lần so với brute-force. Khả năng thực
hiện 2^69 phép toán trên hàm băm(khoảng 590 tỷ) vượt quá khả năng của một máy tính
bình thường. Tuy nhiên theo định luật Moore, với sự phát triển của máy tính, việc tấn
công này theo thời gian sẽ càng trở nên khả thi hơn.
Bruce Schneier và John Kesley cũng đã nêu ra một lý thuyết về tính toán để tìm ra một
đụng độ thứ 2 (second preimage) sau 2^106 bước thay vì 2^160 bước brute -force.
Hiện nay SHA-1 đang dần dần được thay thế bởi các chuẩn hàm băm dài hơn và khó phá
vỡ hơn là SHA-224, SHA-256, SHA-384 và SHA-512.
Một ví dụ về đụng độ của SHA 64 vòng:
Chuỗi hex:
492068657265627920736F6C656D6E6C792070726F6D69736520746F2066696E69736
8206D7920506844207468657369732062792074686520656E64206F662032303035200
A0AEACBD7029E9F219821F0F0FF9213E43DF407CA4A69067368507F397C77DDD
F45C152AC0AB09D1511CFA15FDC789F4D86215D1D41F3C2A73C6AC2B5D3A11
EBB7DEEFFC27FB55C31535C8FB13DCEC26A4B890E82D2608CE731FB383B24D9
37FBECA9F5E390B6C12315D5C1A48ABE9AD3C1DFF6D550C96BD9572D
Và chuỗi hex:
Nhóm DSII [BDHT] Page 18
- Chữ ký số - Các thuật toán và tấn công 2009
492068657265627920736F6C656D6E6C792070726F6D69736520746F2066696E69736
8206D7920506844207468657369732062792074686520656E64206F662032303036600
A0AB88BD702DE7F21987350F0FF9293E43DB427CA4A6826736830FF397C769DDF
458392AC0AF3DD1511EDA15FDC7BDF4D86639D1D41B002A73C48C2B5D3A25E
BB7DBCBFC27FF5BC31530E2FB13DCE426A4BC92E82D261ACE7319BB83B24D8
77FBECEB35E390F5812315F7C1A48ABDDAD3C19D36D5508AABD9570F
Có chung mã băm là E9069CCAB770EC16F9ED4E3AD6FD5A866F829F0C
Chúng ta có thể đối chiếu với bảng mã ASCII để thấy rằng 586 bits đầu tiên của chuỗi
hex thứ nhất nghĩa là “I hereby solemnly promise to finish my PhD thesis by the end of
2005” và chuỗi hex thứ 2 là “I hereby solemnly promise to finish my PhD thesis by the
end of 2006”. Các bits còn lại là các bits chèn thêm để nhằm mục đích tạo nên 2 thông
điệp có mã băm giống nhau.
Giới thiệu về Rainbow Crack Tool
IV.
1. Rainbow Crack là gì?
Nguồn gốc: RainbowCrack là một thành phần trong dự án FASTER TIME-
a.
MEMORY TRADE-OFF TECHNIQUE của Philippe Oechslin. Nó phá vỡ các băm nhờ
rainbow tables.
Các chức năng chính:
b.
Hỗ trợ rainbow table của bất cứ thuật toán băm nào (lm,md5,sha-1…).
-
Hỗ trợ để phục hồi bất kỳ ký tự nào (chữ cái, số, ký tự đặc biệt).
-
Hỗ trợ hệ điều hành đã nhân, hoạt động trên nền 32bit.
-
Sử dụng bằng cách gõ lệnh hoặc dùng giao diện.
-
Tải về tại địa chỉ: http://project-rainbowcrack.com/
c.
Rainbow Crack hoạt động như thế nào?
2.
Hoạt động dựa trên Rainbow table.
a.
Rainbow table là một bảng tra cứu được sử dụng để khôi phục lại plaintext từ một
-
plaintext đã được băm bằng một hàm băm nào đó.
Rain bow table được thiết kế bởi thuật thuật toán đơn giản bởi Martin Hellman, nó
-
được sử dụng để đảo ngược lại một hash bằng cách tra cứu các chuỗi hash được tính toán
trước.
Cấu trúc của một rainbow table.
b.
Một Rainbow table là một chuỗi các record (bản ghi). Mỗi record có 2 fields, mỗi
-
field 8 bytes, tổng cộng một record có độ dài là 16 bytes. Do đó kích thước của một bảng
cầu vòng là một bội số của 16. Một record được đại diện bởi một chain (chuỗi). Field đầu
Nhóm DSII [BDHT] Page 19
nguon tai.lieu . vn