Hệ mã RSA được giới thiệu vào năm 1977 bởi 3 nhà khoa học Ron Rivest, Adi Shamir, Len Adlerman. Đây là một trong những hệ mã được sử dụng phổ biến nhất hiện nay, ứng dụng cho truyền dữ liệu an toàn qua internet, email. RSA còn là nền tảng mật mã cho các giao thức SSL/TLS, SET, SSH, PGP, … RSA cũng được ứng dụng trong chữ ký số Digial Signature.
Breaking RSA là dạng bài thường xuyên gặp phải trong các cuộc thi CTF dưới nhiều hình thức. Bài viết này tôi sẽ mô tả ngắn gọn về hệ mã này, liệt kê các điểm yếu có thể khai thác của nó, cũng như các công cụ toán học, các tool cần thiết giúp giải quyết các bài RSA hay gặp khi chơi CTF.
RSA Cryptosystem
RSA thuộc nhóm hệ mã khóa công khai, dựa vào độ khó của bài toán phân tích 1 số ra thừa số nguyên tố (factoring problem). Để tạo cặp khóa Public key và Private key, Alice cần:
-
- Chọn 2 số nguyên tố lớn
p, qvớip ≠ q - Tính
n = pq - Tính giá trị hàm số Ơle
φ(n) = (p-1)(q-1) - Chọn 1 số
esao cho1 < e < φ(n)vàgcd(e,φ(n)) = 1 - Tính
d = e-1 (mod φ(n)), sốdthỏa mãned ≡ 1 (mod φ(n))
- Chọn 2 số nguyên tố lớn
Public Key gồm:
n– module.e– số mũ mã hóa.
Private Key gồm:
n– module.d– số mũ giải mã.
Khi Bob muốn gửi một tin nhắn M cho Alice, Bob chuyển M thành một số m < n theo 1 cách thỏa thuận trước. Bob sẽ tính ra bản mã c từ bản rõ m theo công thức:
c = me (mod n)
Để giải mã, Alice dùng Private Key của mình để tính ngược lại:
m = cd (mod n)
Quá trình giải mã có thể thu lại được m ban đầu là do:
cd ≡ (me)d ≡ med (mod n) ≡ m (mod n) hay m = cd (mod n)
Dấu ≡ cuối cùng là tôi đã áp dụng định lý Euler. Chi tiết hơn về thiết kế hệ mã cũng như ví dụ có thể đọc ở đây RSA – Wikipedia
Độ mạnh của hệ mã RSA dựa trên việc bạn cần phân tích được n ra thừa số nguyên tố để tính d nếu muốn phá mã, và đến nay chưa có giải thuật nào hiệu quả trong thời gian đa thức giúp ta phân tích thừa số nguyên tố đối với các số lớn.
Hệ mã RSA nếu được thiết kế một cách đúng đắn với việc chọn các tham số n, p, q, e hợp lý thì sẽ rất an toàn, thế nhưng trong các bài CTF, các tham số này thường được chọn theo một cách nào đó khiến cho hệ mã yếu đi và dễ bị tấn công. Các điểm yếu thực thi của RSA sẽ được trình bày dưới đây.
Attack 1 – Small n
Nếu n nhỏ (chiều dài n < 256 bit), ta có thể dễ dàng factorize n bằng cách brute-force số p. Chiều dài n được khuyến cáo là 1024 bit.
Kể cả khi n lớn, đôi khi factorize của n đã có sẵn trong các database online như factordb. Hoặc dễ dàng factorize bằng các công cụ online như alpertron, trang web này sử dụng phương pháp Elliptic Curve Method để factorize. Vậy nên, việc đầu tiên bạn cần làm khi gặp các bài RSA là thử các trang web này trước 🙂
Attack 2 – Small e, small m
Để tối ưu hóa thời gian mã hóa, số e được chọn thường có dạng e = 2n+1. Số e = 21+1 = 3 là số nhỏ nhất. Khi số e = 216+1 = 65537 được sử dụng, hàm mã hóa chỉ cần 17 phép nhân để tính ra ciphertext trong khi nếu chọn e ngẫu nhiên thì số phép tính trung bình là ≈ 1000.
Nếu ta chọn số e nhỏ, ví dụ e = 3. Giả sử Alice gửi cho Bob 1 mẫu tin ngắn M (m nhỏ). Lúc này ciphertext là c = m3 (mod n). Vì m nhỏ nên m3 < n, khi đó phép toán module không có tác dụng. Vì vậy để tìm ngược lại c, ta chỉ việc tính m = c1/3.
Attack 3 – Fermat Attack (p and q are too close)
Trong thực tế, ta cần chọn p, q có cùng độ dài bit để tạo được 1 mã RSA mạnh, tuy nhiên nếu p, q quá gần nhau thì lại tạo ra lỗ hổng bảo mật khi mà attacker có thể dễ dàng factorize n.
Điều kiện cần
p - q < n¼
Fermat’s factorizing algorithm
Ta có: 
Vậy n có thể được phân tích thừa số nguyên tố như sau: n = (x-y)(x+y).
Giải thuật Fermat giúp tìm p, q:
Sourcecode dưới đây lấy từ 1 bài trong Pragyan CTF 2015: Weak RSA
Attack 4 – Hastad Broadcast Attack (same e, small e)
Đặt bối cảnh một mạng nội bộ sử dụng RSA làm phương thức bảo mật truyền tin. Mỗi máy tính trong mạng LAN sẽ có một bộ Public Key (ni, ei) riêng. Giả sử rằng, quản trị viên muốn sử dụng hệ thống mã hóa đơn giản nên anh ta chọn 1 số e nhỏ (e = 3) để dùng chung cho tất cả các máy trong mạng LAN, hay nói cách khác e1 = e2 = ... = e = 3.
Kịch bản tấn công xảy ra nếu máy chủ gửi cùng 1 tin nhắn broadcast m (đã được mã hóa thành c1, c2, ... cho nhiều máy tính trong mạng, và ta bắt được ít nhất e ciphertext c1, c2, ..., ce. Lúc này, ta sẽ có thể khôi phục lại plaintext m không mấy khó khăn.
Giả sử e = 3, đặt M = m3. Nhiệm vụ của ta là giải hệ phương trình đồng dư:
HPT đồng dư trên có thể giải dễ dàng bằng Chinese Remainder Theorem. Sau khi tính được M, ta sẽ tìm lại được m (vì m < ni nên M = m3 < N, ta chỉ cần tính căn bậc 3 của M).
Sourcecode bên dưới lấy từ một bài trong Qiwi CTF 2016:
Attack 5 – Common modulus (same n)
Tiếp tục với hệ thống mạng nội bộ như bài Attack 4, tuy nhiên lần này quản trị viên lại chọn cùng số n cho toàn bộ mạng lưới, nghĩa là n1 = n2 = ... = n và số e được chọn ngẫu nhiên. Như vậy mỗi thành viên trong mạng lưới sẽ được cấp một bộ tham số (n,ei,di)riêng.
Kịch bản 1: Internal Attack.
Giả sử bạn là 1 thành viên của hệ thống mạng. Trong trường hợp này, bạn sẽ được cấp bộ tham số (n,e,d). Từ (n,e,d)của mình, ta dễ dàng tìm được φ(n) theo cách sau:
Vì ed ≡ 1 (mod φ(n)) nên tồn tại số k sao cho ed - kφ(n) = 1. Do đó:
k = (ed-1)/φ(n) > (ed-1)/n
Vậy ta sẽ brute-force số k từ (ed-1)/n trở lên, tính ngược lại φ(n) = (ed-1)/k, cho đến khi thu được kết quả φ(n) là số nguyên. Có φ(n)ta dễ dàng tính được Private Key của victim:
dvictim = evictim-1 mod φ(n)
Bạn hoàn toàn có thể tiếp tục factorize n khi đã biết φ(n), nhưng lúc này thật sự không cần thiết nữa 🙂
Kịch bản 2: External Attack.
Giả sử bạn, với vai trò attacker, lại không phải là thành viên của hệ thống mạng, lẽ dĩ nhiên sẽ không được cấp Private Key d. Tuy nhiên bạn biết được các bộ (n,e) của các thành viên trong mạng (vì chúng là Public Key). Một lần tình cờ, server gửi cùng 1 message m cho 2 máy A, B, bạn nghe lén đường truyền và thu được (cA, cB). Thế là đủ để cho bạn khôi phục message m ban đầu.
Đầu tiên, dùng Extended Euclidean Algorithm để tìm u, v sao cho eA*u + eB*v = 1.
Ta tính m như sau:
m = m1 = m(eA*u + eB*v) = (meA)u * (meB)v = cAu * cBv
Như vậy ta đã có thể khôi phục message m.
Attack 6 – Wiener Attack (small d)
Để mã hóa hay giải mã, ta thực hiện các phép tính c = me (mod n) và m = cd (mod n). Các phép tính này khá hao tốn thời gian xử lý bởi nó chứa phép toán lũy thừa. Thời gian mã hóa phụ thuộc vào độ lớn của e, trong khi thời gian giải mã phụ thuộc độ lớn của d. Để giảm thời gian giải mã (ví dụ trong các tác vụ của 1 smartcard với CPU giới hạn), người ta thường chọn d nhỏ. Thế nhưng việc chọn d nhỏ lại khiến cho hệ thống trở nên yếu đi và có thể bị phá vỡ hoàn toàn bởi phương pháp tấn công Wiener Attack.
Điều kiện cần:
-
d < 1/3 n¼q < p < 2qe' < n3/2vớie' = e (mod n)hay Public Key không quá lớn
Nếu thỏa mãn các điều kiện trên (nhận biết thông qua việc đề cho e rất lớn), ta có thể dễ dàng tìm được d và phá vỡ toàn bộ hệ thống mã hóa.
Chứng minh:
Phép chứng minh sử dụng tính chất của liên phân số. Vì ed ≡ 1 (mod φ(n)) nên tồn tại một số nguyên k sao cho ed - kφ(n) = 1. Vì vậy:
Do đó k/d ≈ e/φ(n). Ta không biết φ(n) nhưng có thể dùng n để xấp xỉ. Thật vậy, φ(n) = n-p-q+1 và p+q-1 < 3√n nên n-φ(n) < 3√n. Sử dụng n thay cho φ(n)ta thu được:
Vì k < d < 1/3 n¼ nên ta được:
Từ đó, áp dụng định lý về dãy hội tụ liên phân số, ta tìm trong dãy hội tụ của khai triển liên phân số e/n sẽ tìm được k/d. Bằng cách thử từng cặp k/d này, ta tính φ(n) = (ed - 1)/k. Lúc này ta có:
p+q = n-φ(n)+1 và pq = n
Dùng định lý Vi-et đảo tính được p, q. Xác nhận lại pq = n để tìm ra cặp k/d đúng. Tìm được p, q sẽ tính được d và … done, RSA broken 🙂
Ví dụ
Cho (n,e) = (90581,17993). Khai triển liên phân số của e/n là:
[0; 5, 29, 4, 1, 3, 2, 4, 3]
Bạn có thể tự tính hoặc dùng tool online wolframalpha. Từ đó ta có được dãy hội tụ của e/n. Có thể kiểm tra bằng WolframAlpha:
Thử với phân số 1/5, ta giả sử k = 1 và d = 5. Tính được φ(n) = (ed - 1)/k = (17993*5 - 1)/1 = 89964. Do đó p+q = n-φ(n)+1 = 618 và pq = n = 90581. Nên p, q là nghiệm của PT: x2 - 618x + 90581 = 0. Giải PT tìm được q = 239; p = 379. Kiểm tra lại thấy rằng n = 90581 = 239 * 379 = pq. Như vậy có thể khẳng đinh được d = 5 là private key đúng.
Security Tip
Để tránh bị tấn công bởi phương pháp Wiener Attack, ta có thể dùng e nhỏ, nhưng lúc này bù lại d sẽ lớn và tốc độ giải mã là khá chậm. Nếu n là một số dài 1024 bit thì d phải dài ít nhất 256 bit.
M. Wiener đưa ra 2 giải pháp hiệu quả để phòng tránh hình thức tấn công trên mà vẫn giữ được tốc độ tính toán:
- Sử dụng định lý số dư Trung Hoa (Chinese Remainder Theorem – CRT).
- Giả sử ta chọn
dsao chodp = d mod (p-1)vàdq = d mod (q-1)đều là số nhỏ (khoảng 128 bit) nhưngdvẫn là số lớn. Quá trình giải mã vẫn có thể thực hiện nhanh chóng theo cách sau: Đầu tiên tínhmp = Cdp (mod p)vàmq = Cdq (mod q). Dùng định lý CRT để tìm số m thỏa mãnm = mp (mod p)vàm = mq (mod q). Kết quả m tính được sẽ thỏa mãn tính chấtm = cd (mod n)như yêu cầu. Vìdlớn nên Wiener Attack không hiệu quả nữa.
- Giả sử ta chọn
- Thay
ebằnge'vớie' = e + kφ(n)vớiklà một số nguyên đủ lớn sao choe' > n3/2, lúc này Wiener Attack sẽ không áp dụng được bất kểdnhỏ thế nào
Lời kết
Vẫn còn một số phương pháp attack RSA nữa nhưng bài viết đến đây đã khá dài, tôi xin dừng tại đây. Phần tiếp theo xin hẹn lại vào một ngày khác 🙂
Tham khảo:
- Attacking RSA for fun and ctf points – bitsdeep.com
- 15 ways to break rsa security – Renaud Lifchitz
- Twenty Years of Attacks on the RSA Cryptosystem – Dan Boneh
- Wiener’s Attack – Original paper
- Boneh – Durfee Attack
- Partial Key Exposure Attack
- New Partial Key Exposure Attack
- Bleichenbacher’s PKCS 1.5 Padding Oracle
- ROBOT Attack
Nhat Truong Blog 
em mới tập tành chơi ctf thôi, blog này giúp em nhiều lắm luôn đó anh, chi tiết cực. Hóng part2 ạ hihi. Chỉ muốn nói là cảm ơn anh nhiều lắm ❤
ThíchThích