Ngày 05 tháng 7 năm 2020 tanglei.name Bình luận 46 bình luận 83.944 lượt đọc

Mục lục

• So sánh chuỗi độc đáo
• Tấn công thời gian (Timing Attack)
• Hàm tương ứng của các ngôn ngữ lập trình
• Một điều thú vị nữa

So Sánh Chuỗi Độc Đáo

Trong khung Play Framework của Java có một đoạn mã để xác minh liệu dữ liệu trong cookie (session) có hợp lệ hay không (bao gồm cả việc kiểm tra chữ ký), như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

boolean safeEqual(String a, String b) {
  if (a.length() != b.length()) {
    return false;
  }
  int equal = 0;
  for (int i = 0; i < a.length(); i++) {
    equal |= a.charAt(i) ^ b.charAt(i);
  }
  return equal == 0;
}

Khi lần đầu tiên nhìn thấy đoạn mã nguồn này, chắc hẳn mọi người sẽ cảm thấy lạ lẫm. Chức năng của hàm này là so sánh hai chuỗi có bằng nhau hay không. Nếu muốn kiểm tra hai chuỗi có giống nhau hay không, cách viết thông thường sẽ như dưới đây (từ JDK8 của String.equals() - đã chỉnh sửa):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public boolean equals(Object anObject) {
  String anotherString = (String)anObject;
  int n = value.length;
  if (n == anotherString.value.length) {
    char v1[] = value;
    char v2[] = anotherString.value;
    int i = 0;
    while (n-- != 0) {
      if (v1[i] != v2[i]) // <- Thoát ngay khi gặp ký tự khác nhau đầu tiên
        return false;
      i++;
    }
    return true;
  }
  return false;
}

Chúng ta có thể thấy rằng cách so sánh hai chuỗi thông thường là:

1. Kiểm tra độ dài của hai chuỗi trước, nếu khác nhau thì trả về false ngay lập tức.
2. Nếu độ dài bằng nhau, thì tuần tự kiểm tra từng ký tự có giống nhau hay không, nếu khác game nổ hũ đăng ký tặng code thì trả về false.
3. Nếu tất cả đều giống nhau, thì trả về true. Ngay khi gặp ký tự khác nhau, hàm sẽ trả về false.

Tuy nhiên, đoạn mã trong Play Framework lại không làm như vậy, đặc biệt ở điểm thứ hai, nó sử dụng phép XOR. Những ai quen thuộc với toán tử bit dễ dàng hiểu rằng qua phép XOR 1^1=0, 1^0=1, 0^0=0, chúng ta có thể so sánh từng bit. Nếu tất cả các bit đều giống nhau, hai chuỗi chắc chắn sẽ bằng nhau và biến lưu trữ giá trị tích lũy XOR (equal) sẽ bằng 0 (vì các ký tự giống nhau luôn xuất hiện chẵn lần), ngược lại sẽ bằng 1. Nhưng cách này không dừng ngay khi gặp ký tự khác nhau mà phải so sánh toàn bộ chuỗi, điều này dường như không hiệu quả chút nào. Vậy tại sao? Lý do là vì bảo mật.

Tấn Công Thời Gian (Timing Attack)

Tấn công thời gian (Wikipedia) là một dạng của tấn công kênh bên (Side Channel Attack, viết tắt là SCA). Tấn công kênh bên là bất kỳ cuộc tấn công nào dựa trên thông tin thu thập được từ cách thức triển khai của hệ thống máy tính, thay vì dựa trên các lỗ hổng của thuật toán bản thân (ví dụ như phân tích mật mã và lỗi phần mềm). Thông tin về thời gian, mức tiêu thụ điện năng, rò rỉ điện từ thậm chí âm thanh đều có thể cung cấp nguồn thông tin phụ trợ cho kẻ tấn công. Trong nhiều môi trường bị cô lập vật lý (black-box), những loại tấn công mới này vẫn có thể phát huy hiệu quả vượt trội so với phương pháp phân tích mật mã truyền thống.

Tấn công thời gian là phương pháp phổ biến nhất. Vậy, cách so sánh chuỗi thông thường bị hacker lợi dụng để thực hiện tấn công thời gian như thế nào?

Chúng ta biết rằng, khi so sánh hai chuỗi, ngay khi gặp ký tự khác nhau, hàm sẽ trả về thất bại. Về mặt lý thuyết, thời gian so sánh hai chuỗi có hai ký tự đầu tiên giống nhau sẽ ngắn hơn so với hai chuỗi có mười ký tự đầu tiên giống nhau. Bạn có thể nghĩ rằng sự chênh lệch này là bao nhiêu? Có lẽ chỉ vài micro giây. Nhưng chúng ta có thể phóng đại vấn đề này. Ví dụ, trong ứng dụng web, chúng ta ghi lại thời gian phản Xeng Club Top 5 Game Bài Đổi Thưởng hồi mỗi yêu cầu (thông thường là miligiây). Nếu lặp lại quá trình này 50 lần, chúng ta có thể xem xét thời gian trung bình hoặc p50 để tìm ra ký tự nào mất nhiều thời gian phản hồi hơn. Nếu một chuỗi thử nghiệm của chúng ta mất nhiều thời gian hơn, chúng ta có thể kết luận rằng phần đầu của chuỗi này chắc chắn đúng.

Điều này có thể được áp dụng để tấn công HMAC. Để hiểu rõ hơn về HMAC, bạn có thể tham khảo bài viết “Thuật Xác Thực Và Phân Quyền API HTTP” trên trang web của tôi. Nói đơn giản, HMAC là khi khách hàng gửi tới máy chủ một chuỗi cùng với chuỗi chữ ký của nó (HMAC), sau đó máy chủ sử dụng một khóa riêng tư để tạo chữ ký cho chuỗi nhận được và so sánh chữ đỏ 99 vip ký này với chữ ký ban đầu.

Viết bằng pseudo-code, quá trình này trông như sau:

1
2
3
4

bool verify(message, digest) {
  my_digest = HMAC(key, message);
  return my_digest.equals(digest);
}

Như vậy, kẻ tấn công, dù không biết thuật toán chữ ký và khóa riêng tư, nhưng biết cấu trúc API, có thể sử dụng cách liệt kê và thống kê thời gian gọi API để phá vỡ chữ ký một cách hiệu quả. Bài viết “HMAC Timing Attacks” đã ghi lại toàn bộ quá trình. Trong bài viết có ghi rằng:

Nếu một chữ ký có độ dài 40 ký tự, ví dụ: f5acdffbf0bb39b2cdf59ccc19625015b33f55fe, kẻ tấn công bắt đầu liệt kê từ 0000000000000000000000000000000000000000. Dưới đây là bảng thống kê thời gian liệt kê ký tự đầu tiên (từ 0 đến f vì đây là phạm vi giá trị của HMAC).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

0 0.005450913
1 0.005829198
2 0.004905407
3 0.005286876
4 0.005597611
5 0.004814430
6 0.004969118
7 0.005335884
8 0.004433182
9 0.004440246
a 0.004860263
b 0.004561121
c 0.004463188
d 0.004406799
e 0.004978907
f 0.004887240

Chúng ta có thể thấy rằng kết quả đo thời gian lần đầu tiên (đơn vị giây) không có sự chênh lệch đáng kể giữa các giá trị, tất cả đều gần giống nhau. Nói cách khác, có quá nhiều nhiễu làm che khuất tín hiệu. Vì vậy, cần thực hiện nhiều mẫu thử (phóng đại quy mô thử nghiệm) và sử dụng công cụ thống kê để lọc tín hiệu khỏi nhiễu. Để phân biệt tín hiệu với nhiễu, chúng ta cần phóng đại quy mô thử nghiệm theo một hằng số tùy ý. Qua thí nghiệm, tác giả nhận thấy rằng 500 là một con số tốt. Nói cách khác: chạy thử nghiệm 500 lần và ghi lại kết quả của mỗi lần thử nghiệm. Sau đó, bằng mắt thường, chúng ta có thể thấy rằng thời gian gọi ‘f’ lâu hơn so với các ký tự khác, nhưng cách này khó tự động hóa.

Vì vậy, tác giả đưa ra một thuật toán thống kê khác. Thuật toán này gửi 16 yêu cầu tới máy chủ (từ 0 đến f) và ghi lại thời gian phản hồi của mỗi yêu cầu. Sau đó, sắp xếp kết quả từ 1 đến 16, trong đó 1 là yêu cầu lâu nhất (chậm nhất) và 16 là yêu cầu nhanh nhất. Lặp lại quá trình này 500 lần. Kết quả như sau (chỉ hiển thị 25 mẫu thử, ký tự ‘0’ lần lượt được xếp hạng 7, 1, 3, 3…):

1
2
3
4
5
6
7

{
"0"=>[7, 1, 3, 3, 15, 5, 4, 9, 15, 10, 13, 2, 14, 9, 4, 14, 7, 9, 15, 2, 14, 9, 14, 6, 11...],
"1"=>[13, 4, 7, 11, 0, 4, 0, 2, 14, 11, 6, 7, 2, 2, 14, 11, 8, 10, 5, 13, 11, 7, 4, 9, 3...],
"2"=>[14, 5, 15, 5, 1, 0, 3, 1, 9, 12, 4, 4, 1, 1, 8, 6, 9, 4, 9, 5, 8, 3, 12, 8, 5...],
...
"f"=>[3, 6, 1, 9, 4, 14, 15, 7, 5, 15, 9, 6, 13, 13, 13, 8, 5, 3, 13, 12, 3, 15, 9, 7, 10...]
}

Sau đó, lấy trung bình của 500 lần xếp hạng cho mỗi ký tự, ta có kết quả như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

"f", 5.302
"0", 7.17
"6", 7.396
"3", 7.472
"5", 7.562
"a", 7.602
"2", 7.608
"8", 7.626
"9", 7.688
"b", 7.698
"1", 7.704
"e", 7.812
"4", 7.82
"d", 7.826
"7", 7.854
"c", 7.86

Vậy là ‘f’ nổi bật hơn hết. Sau đó, lặp lại thuật toán này cho 39 ký tự còn lại.

Đây là một kỹ thuật thống kê giúp chúng ta lọc tín hiệu từ nhiễu. Tổng cộng cần thực hiện 16 * 500 * 40 = 320.000 yêu cầu, trong khi liệt kê toàn bộ sẽ cần 16^40 yêu cầu.

Bài báo học thuật này tuyên bố rằng họ đã dùng phương pháp tấn công thời gian để phá vỡ thuật toán mã hóa RSA của OpenSSL 0.9.7.

Hàm Đối Ứng Các Ngôn Ngữ

Dưới đây là các hàm đối ứng với tấn công thời gian trong các ngôn ngữ lập trình:

PHP:

1
2

bool hash_equals ( string $known_string , string $user_string )
boolean password_verify ( string $password , string $hash )

Java: Java có vấn đề ở phiên bản 1.6 và đã khắc phục từ 1.6.0._17(6u17). Đây là mã nguồn của JDK8 – MessageDigest.isEqual()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public static boolean MessageDigest.isEqual(byte[] digesta, byte[] digestb) {
  if (digesta == digestb) return true;
  if (digesta == null || digestb == null) {
    return false;
  }
  if (digesta.length != digestb.length) {
    return false;
  }
  int result = 0;
  // So sánh không phụ thuộc vào thời gian
  for (int i = 0; i < digesta.length; i++) {
    result |= digesta[i] ^ digestb[i];
  }
  return result == 0;
}

C/C++: Không tìm thấy hàm tương ứng trong thư viện thông dụng, nên bạn cần tự viết.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int util_cmp_const(const void * a, const void *b, const size_t size) 
{
 const unsigned char *_a = (const unsigned char *) a;
 const unsigned char *_b = (const unsigned char *) b;
 unsigned char result = 0;
 size_t i;
 for (i = 0; i < size; i++) {
  result |= _a[i] ^ _b[i];
 }
 return result; /* trả về 0 nếu bằng nhau, khác 0 nếu khác */
}

Python – 2.7.7+ sử dụng hmac.compare_digest(a, b), ngược lại sử dụng mã từ Django.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def constant_time_compare(val1, val2):
  """
  Trả về True nếu hai chuỗi bằng nhau, False nếu không.
  Thời gian thực thi không phụ thuộc vào số lượng ký tự trùng khớp.
  """
  if len(val1) != len(val2):
    return False
  result = 0
  for x, y in zip(val1, val2):
    result |= ord(x) ^ ord(y)
  return result == 0

Go – Sử dụng gói crypto/subtle

1
2
3
4
5
6

func ConstantTimeByteEq(x, y uint8) int
func ConstantTimeCompare(x, y []byte) int
func ConstantTimeCopy(v int, x, y ]byte)
func ConstantTimeEq(x, y int32) int
func ConstantTimeLessOrEq(x, y int) int
func ConstantTimeSelect(v, x, y int) int

Một Điều Thú Vị Nữa

Trước khi kết thúc bài viết, tôi muốn nhắc thêm một điều. Toàn bộ mã nguồn trên vẫn còn một vấn đề — chúng đều kiểm tra độ dài chuỗi trước, nếu khác nhau thì trả về ngay. Như vậy, qua tấn công thời gian, kẻ tấn công có thể biết được độ dài chuỗi, chẳng hạn như độ dài mật khẩu của bạn. Theo lý thuyết, độ dài chuỗi cũng nên được coi là “dữ liệu riêng tư” (trừ khi đó là chữ ký).

(Kết thúc bài viết)

Lưu ý: Khi đăng tải bài viết này, vui lòng ghi rõ tác giả và nguồn CoolShell – CoolShell, và không sử dụng vào mục đích thương mại.

• ![Xác Thực Số Nhận Diện Mạng Lưới
• !Nguyên Tắc Làm Hệ Thống Kiến Trúc
• !Thuật Xác Thực Và Phân Quyền API HTTP
• !10 Công Cụ Và Tài Nguyên Thiết Yếu Cho Phát Triển iOS
• !IoC/DIP Là Một Tư Duy Quản Lý
• !OMG, Windows 7 Đến Từ Tương Lai

!Rất Tệ!Không Tốt Lắm!Được Rồi!Tốt!Rất Tuyệt (110 Người Đã Đánh Giá, Điểm Trung Bình: 4.60 )

![](Thiết Kế Chương Trình, Bảo Mật Mạng HMAC, Thiết Kế Chương Trình, Bảo Mật Mạng

Bài Viết Liên Quan

• ![Xác Thực Số Nhận Diện Mạng Lưới
• !Nguyên Tắc Làm Hệ Thống Kiến Trúc
• !Thuật Xác Thực Và Phân Quyền API HTTP
• !10 Công Cụ Và Tài Nguyên Thiết Yếu Cho Phát Triển iOS
• !IoC/DIP Là Một Tư Duy Quản Lý
• !OMG, Windows 7 Đến Từ Tương Lai

Hướng Dẫn Bài Viết

Bài Trước Kiểm Soát Nghề Nghiệp Lập Trình Viên Bài Sau Paradigm Lập Trình Rust

Bình Luận Liên Quan Đến “Tấn Công Thời Gian - Timing Attacks”

1. iseki nói: Ngày 05 tháng 7 năm 2020 lúc 13:50 Xin hỏi, nếu thêm một độ trễ ngẫu nhiên trước khi trả về có giảm thiểu được vấn đề không?

   Trả lời

   1. cuill nói: Ngày 05 tháng 7 năm 2020 lúc 14:07 Tôi nghĩ không. Giả sử độ trễ ngẫu nhiên nằm trong khoảng 0-999ms. Chỉ cần số lần yêu cầu đủ lớn, thì tương đương mỗi yêu cầu chậm đi 500ms. Vẫn có thể thống kê được sự khác biệt.

      Trả lời

      1. likev nói: Ngày 05 tháng 7 năm 2020 lúc 16:41 Nếu thiết kế độ trễ tốt, thì vấn đề có thể giải quyết được. Ví dụ, chuỗi a cố định độ trễ hash(a) miligiây. Điều kiện là hàm hash không được công khai, không áp dụng cho phần mềm mã nguồn mở.

         Ngoài ra, tôi cảm thấy các phiên bản safeEqual trên có thể không chịu được tối ưu hóa của trình biên dịch. Một trình biên dịch thông minh có thể tối ưu thành phiên bản không an toàn trả về sớm.

         Trả lời

         …

(Tiếp tục theo cấu trúc tương tự để đảm bảo hoàn chỉnh)