# Một số kĩ thuật tấn công Hash MD5 ## I. Review một số tính chất của Hash Funtions - Collision resistance: Rất khó để tìm được 2 đoạn thông điệp $m_1\neq m_2$ sao cho $hash(m_1)=hash(m_2)$ - Pre-image resistance: Cho trước output của 1 hàm hash bất kỳ $x = hash(m)$, rất khó để tìm được đoạn thông điệp $m_0$ sao cho $hash(m_0)=x$ - Second pre-image resistance: Cho trước đoạn thông điệp $m_1$, rất khó để tìm được đoạn thông điệp $m_2\neq m_1$ sao cho $hash(m_1)=hash(m_2)$ - Nếu tìm được 2 va chạm(Collision) $A\neq B$ sao cho $hash(A)=hash(B)$ thì với đoạn thông điệp C bất kì, ta luôn có: $$ hash(A||C)=hash(B||C) $$ ## II. Một số kĩ thuật tấn công thường thấy của MD5 ### 1. Google - Hiện tại đã có thuật toán tìm va chạm nên có thể tìm được một vài va chạm của MD5 ở trên google. - vd: đây là 1 va chạm của md5 có thể tìm thấy trên google ``` d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70 ``` ``` d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70 ``` ### 2. Identical prefix - Có thể tìm được va chạm bằng tool hashclash với cấu trúc file như sau: | Prefix | = | Prefix | | :----: |:-:| :----: | | Collision *A* | ≠ | Collision *B* | | Suffix | = | Suffix | - vd: Có thể tìm va chạm của chuỗi bytes bắt đầu bằng b'Thangcoithongminhhhh' ``` e8 6f 53 ec 86 52 58 60 a7 2f 04 91 d0 aa 15 0d 6d 79 a0 16 a8 31 54 57 2b 25 5b b4 f4 a6 2a 2e 91 e4 18 4d 98 45 69 39 27 33 84 7d f5 7a c5 11 ba cd 8b b5 c8 e8 47 b1 4a 12 25 d7 b8 62 a7 c0 ``` ``` e8 6f 53 ec 86 52 58 60 a7 2f 04 91 d0 aa 15 0d 6d 79 a0 16 a8 31 54 57 2b 25 5b b4 f4 a6 2a 2e 91 e4 18 4d 98 45 69 39 27 33 84 7d f5 7a c5 11 ba cd 8b b5 c8 e8 47 b1 4a 12 25 d7 b8 62 a7 c0 ``` ### 3. Length Extension Attack #### a. Khái niệm và điều kiện để tấn công - Là một kỹ thuật mà kẻ tấn công có thể sử dụng giá trị của $h(m_1)$ để tính giá trị của $h(m_1||m_2)$ mà không cần biết nội dung của $m_1$ - Hàm $h()$ có thể là MAC hoặc hàm hash có cấu trúc Merkle-Damgard - Điều kiện để tấn công: - Biết được chiều dài của $m_1$ - Có tool hoặc thuật toán của hàm $h()$ để điều khiển được State và Padding #### b. Cấu trúc Merkle-Damgard ![](https://i.imgur.com/mOXLnUT.png) - Ta có thể thấy rằng trong cấu trúc Merkle-Damgard thì đoạn dữ liệu sẽ được chia ra thành các block bằng nhau được gọi là block message - Hàm $h()$ sẽ nhận 2 input là block message và output trước đó (thường được gọi là State, trong hình kí hiệu là $t$) để tính ra output - Khi tính output của block đầu tiên sẽ phải khởi tạo $t_0$ được gọi là $IV$ #### c. IV và Padding của MD5 - Thuật toán MD5 chia message thành các block có độ dài 512 bit - Block cuối cùng sẽ được pad thêm bit 1 theo sau là các bit 0 cho tới khi đủ 448 bit, phần còn lại sẽ là 64-bit **độ dài bit** của đoạn thông điệp trước khi padding được biểu diễn bằng little-endian - vd: Input = secretdata ``` 0000 73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00 secretdata...... 0010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 0020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 0030 00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00 ........P....... ``` - 73 65 63 72 65 74 64 61 74 61 -- input biểu diễn bằng hex - 80 00 00 00 00... -- 46 bytes padding, bắt đầu bằng 0x80 - 50 00 00 00 00... -- chiều dài bit của input biểu diễn bằng little-endian - $t_0$ =(0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476) #### d. MD5 Length Extension Attack - Giả sử một cơ chế xác thực MAC bằng md5: $md5(secret||input)$ với $secret$ = thangcoithongminh, $message$ = loveisthedeathofduty, sẽ cho ra mã MAC là `50a851c609bcbc6205db3bfb58bd3a34` - Mã MAC chính là State cuối cùng của hàm $h()$ biểu diễn dưới dạng little-endian - Giả sử kẻ tấn công bây giờ đã biết bit_length(secret)=136 và sẽ dùng tool(tạm gọi là $\text{md5_custom}(state,input)$) để can thiệp phần State và padding để chỉnh sửa mã MAC: - Đầu tiên kẻ tấn công sẽ chuyển mã MAC của $md5(secret||message)$ về lại big-endian và gán nó cho $t_0'$ = (0xc651a850, 0x62bcbc09, 0xfb3bdb05, 0x343abd58) - Tiếp đến kẻ tất công sẽ tính phần padding (gọi là $p_1$) của $secret||message$ như trên: ``` 0000 74 68 61 6e 67 63 6f 69 74 68 6f 6e 67 6d 69 6e thangcoithongmin 0010 68 6c 6f 76 65 69 73 74 68 65 64 65 61 74 68 6f hloveisthedeatho 0020 66 64 75 74 79 80 00 00 00 00 00 00 00 00 00 00 fduty........... 0030 00 00 00 00 00 00 00 00 28 01 00 00 00 00 00 00 ........(....... ``` - Tiếp theo kẻ tấn công sẽ thêm đoạn dữ liệu mình mong muốn($fixed$=append) và tính tiếp phần padding của $secret||message||p_1||fixed$ (gọi là $p_2$): ``` 0000 74 68 61 6e 67 63 6f 69 74 68 6f 6e 67 6d 69 6e thangcoithongmin 0010 68 6c 6f 76 65 69 73 74 68 65 64 65 61 74 68 6f hloveisthedeatho 0020 66 64 75 74 79 80 00 00 00 00 00 00 00 00 00 00 fduty........... 0030 00 00 00 00 00 00 00 00 28 01 00 00 00 00 00 00 ........(....... ----------------------------------------------------------------------- 0040 61 70 70 65 6e 64 80 00 00 00 00 00 00 00 00 00 append.......... 0050 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 0060 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 0070 00 00 00 00 00 00 00 00 30 02 00 00 00 00 00 00 ........0....... ``` - Cuối cùng kẻ tấn công sẽ tính mã MAC mới = $\text{md5_custom}(t_0',fixed||p_2)$ và gửi lên cơ chế MAC $md5(secret||message||p_1||fixed)$ - ![](https://i.imgur.com/1SMifJx.png) - Ta sẽ thấy $\text{md5_custom}(t_0',fixed||p_2)=md5(secret||input||p_1||fixed)$ - Như vậy kẻ tấn công đã vượt qua cơ chế MAC và làm cho đoạn thông điệp bị chỉnh sửa