Luận văn Nghiên cứu họ hệ mật WG trong mật mã hạng nhẹ

ứng với ( )u x được gọi là chuỗi GMW tổng quát. * Các thuộc tính đặc trưng của dòng khoá mà được tạo ra bởi máy sinh WG: - Chu kỳ: Máy sinh dòng khóa WG có một LFSR 11 trạng thái trên 292F với một đa thức phản hồi nguyên thủy mà nó sinh ra một chuỗi có độ dài lớn nhất có chu 31 kỳ 211×29 - 1 trên 292F . Vì vậy, chu kỳ của dòng khóa được tạo ra bởi mật mã là 2319-1. - Cân bằng: Do chuỗi m {bi} trên 292F cân bằng và WG là một hàm bool cân bằng 292 F → F2, nên dòng khóa cũng được cân bằng. - Tính tự tương quan cấp hai: Chuyển đổi WG là một hàm trực giao và chuỗi chuyển đổi WG tương ứng có độ tự tương quan cấp độ 2. Ta xét (2): Đã chứng minh trong rằng nếu f là một hàm trực giao thì chuỗi tương ứng với nó u cũng có độ tự tương quan cấp hai. Do đó, dòng khóa được tạo ra bởi máy sinh dòng khóa WG có độ tương quan cấp cấp. - Phân phối t-tuple: Vì {bi} là chuỗi m trên 292F , với độ 11 và f là một hàm bool cân bằng từ 292F → F2, dòng khóa {ai} là phân bố t-tuple lý tưởng với 1 ≤ t ≤ 11. - Độ phức tạp tuyến tính: Từ công thức (2), độ phức tạp tuyến tính của dòng khóa có thể được tính chính xác theo công thức sau: w( ) 45.041529 11 2i i I LS     Với w( )i là khoảng cách hamming của i và I = I1 ∪ I2 Với: I1 = {219 + 29 + 2 + i |0 ≤ i ≤ 29 − 3}, I2 = {220 + 3 + 2i |0 ≤ i ≤ 29 − 2}. 1.4.2 Chuyển đổi WG Biểu thức chuyển đổi WG, 292F → F2, có thể được xem như một hàm bool trong 29 biến. Biểu diễn bool chính xác phụ thuộc vào cơ sở tính toán trong 292F . Cơ sở thông thường được lựa chọn sao cho biểu diễn bool tương ứng của chuyển đổi WG là 1- order linh hoạt, có độ là 11 và độ phi tuyến tính của nó là 228-214 = 268419072 1.4.3 An ninh chống lại các cuộc tấn công Phân tích tính bảo mật của mật mã WG đối với một số cuộc tấn công nổi tiếng trên mật mã dòng. Các loại tấn công được biết đến như các cuộc tấn công thương mại TMD, các cuộc tấn công đại số và các cuộc tấn công tương quan.  Tấn công về mặt thời gian /bộ nhớ/ dữ liệu (TMD): Xét cuộc tấn công thương mại thời gian/ bộ nhớ/ dữ liệu trên các mật mã dòng. Phương thức tấn công: có hai giai đoạn:  Giai đoạn tiền tính toán, kẻ tấn công khai thác cấu trúc của mật mã dòng và tổng hợp các phát hiện của mình trong các bảng lớn. 32  Giai đoạn tấn công, kẻ tấn công sử dụng các bảng này và dữ liệu quan sát được để tính toán khóa bí mật hoặc trạng thái bên trong của mật mã dòng. Để xác định được tính khả thi của cuộc tấn công này cần xác định rõ 3 vấn đề: o Thông tin khai thác được trong giai đoạn tiền xử lý. o Dòng khóa được yêu cầu. o Những tính toán cần thiết để khôi phục khoá bí mật. Giải pháp: giải pháp đơn giản để đảm bảo an ninh chống lại cuộc tấn công này là tăng không gian tìm kiếm. Một tấn công thương mại TM2D2 = N2 với D2 ≤ T ≤ N, trong đó T là thời gian cần thiết cho cuộc tấn công, M là bộ nhớ cần thiết để lưu trữ các bảng, D biểu diễn dữ liệu thời gian thực hoặc dòng khóa được yêu cầu, và N là kích thước của không gian tìm kiếm. Việc tăng không gian tìm kiếm có thể được thực hiện được bằng cách tăng kích thước của trạng thái nội bộ và sử dụng IV ngẫu nhiên cùng với khóa bí mật. Trong mật mã dòng WG, kích thước của trạng thái bên trong là 2319 gấp đôi kích thước của khoá lớn nhất. Nếu một IV ngẫu nhiên có cùng độ dài với khoá bí mật, mật mã sẽ được đảm bảo chống lại các cuộc tấn công thời gian/bộ nhớ/dữ liệu.  Tấn công đại số: Hình thức tấn công: Nhằm tấn công vào LFSR, tạo ra một hệ phương trình phi tuyến tính cho nhiều dòng khoá, để có thể khôi phục được trạng thái bên trong của LFSR. Chứng minh mật mã WG an toàn với cuộc tấn công đại số: Ta xét các cuộc tấn công đại số đã được sử dụng gần đây để phá nhiều thuật toán mã hóa nổi tiếng. Courtois đã chỉ ra rằng độ phức tạp của các cuộc tấn công này phụ thuộc vào bộ lọc phi tuyến tính và số lượng các kết quả đầu ra được tạo ra bởi mật mã. Nếu bộ lọc phi tuyến tính có thể tính xấp xỉ bằng một phương trình đa biến có độ thấp thì độ phức tạp này có thể giảm một cách đáng kể. Biểu diễn hàm bool của WG có 29 đầu vào, một đầu ra và có độ là 11. Một bộ lọc phi tuyến tính với 29 đầu vào và 1 đầu ra phải có xấp xỉ độ 14. Tuy nhiên độ này lớn hơn 11, độ của chuyển đổi WG. Để các xấp xỉ có ý nghĩa đối với chuyển đổi WG nên có độ nhỏ hơn 11. Giả sử rằng không có phép xấp xỉ của WG với độ nhỏ hơn 11, mật mã có thể được giảm xuống một hệ phương trình tuyến tính xấp xỉ  31911 . Độ phức tạp của việc giải quyết hệ thống như vậy là xấp xỉ   72 log 319 182 117 / 64* 2 . Nếu tồn tại phép xấp xỉ của WG với độ nhỏ hơn 11 được thì độ phức tạp của cuộc tấn công sẽ giảm. Theo [9], kết quả thí nghiệm trên chuyển đổi WG, đưa ra phỏng đoán rằng xác suất của sự tồn tại của phép xấp xỉ như vậy là rất thấp. Chuyển đổi WG trong các biến 11, 13 và 14 không có phép xấp xỉ với độ nhỏ hơn so với độ chuyển đổi WG. Vì cả hai biểu diễn bool và đa thức của chuyển đổi WG có số 33 lượng lớn các thuật ngữ đơn thức với độ cao thì nó không thể xóa được các thuật ngữ với độ cao hơn mà không ảnh hưởng đến đầu ra của chuyển đổi. Chuyển đổi WG có một số lượng lớn các thuật ngữ đơn trong đó biểu diễn đa thức và bool đảm bảo an ninh chống lại các cuộc tấn công đại số.   29 28 14 ` 29 2 (2 2 ) ( ) ( ) 0.5000305. 2 P f x l x       Các cuộc tấn công tương quan: Phương thức tấn công: Đối với loại tấn công này, kẻ thù sẽ khai thác bất kỳ mối tương quan nào có thể tồn tại giữa dòng khóa và đầu ra của LFSR trong mật mã để thực hiện tấn công. Trong các cuộc tấn công này, dòng khóa được coi là một phiên bản bị bóp méo hoặc gây nhiễu của đầu ra LFSR. Điều này làm giảm khả năng tìm ra trạng thái nội bộ của LFSR dẫn tới khả năng giải mã cũng giảm. Chuyển đổi WG được dùng trong mật mã WG là 1-order linh hoạt, nghĩa là đầu ra của chuyển đổi WG hay dòng khóa không có mối lên quan gì với bất kỳ bit đầu vào nào của đầu ra LFSR. Điều này cho thấy rằng mật mã WG đủ sức để chống lại các cuộc tấn công tương quan. Tuy nhiên, khi xét trường hợp chuyển đổi WG là xấp xỉ bằng các hàm tuyến tính. Những xấp xỉ tuyến tính này có thể được sử dụng để lấy ma trận máy sinh của một mã tuyến tính. Việc giải mã sau đó có thể được thực hiện bằng thuật toán giải mã Maximum Likelihood (ML) để phục hồi trạng thái nội bộ của LFSR. Chứng minh mật mã WG an toàn với cuộc tấn công tương quan: Ta sử dụng một số ràng buộc lý thuyết để ước tính độ phức tạp của cuộc tấn công vào mật mã WG. Cho `f là hàm bool biểu diễn chuyển đổi WG và l là một hàm tuyến tính với khoảng cách Hamming ngắn nhất đến `f . Ta có xác suất: 29 28 14 ' 29 2 (2 2 ) ( ( ) ( ) 0.5000305 2 P f x l x      Số lượng dòng khóa cần thiết cho một cuộc tấn công thành công là:   319 1/3 2 3.12.ln 2 . .2 k N k    Và độ phức tạp giải mã là: 6 2ln 2 2 . . (2 ) k decC k   Trong đó ( '( ) ( )) 0.5 0.000305P f x l x     và k là số bit trạng thái bên trong LFSR đã khôi phục. Nếu ta chọn k là rất nhỏ, tức k = 5, thì số lượng dòng khóa cần cho cuộc tấn công là khoảng 2133. Hơn nữa, độ phức tạp của pha tiền xử lý là hơn 2266. Vì số lượng dòng khóa lớn nhất có thể được tạo ra với một khoá đơn và IV là 245, ta chọn k = 274 để giảm lượng dòng khoá đến số này. Bây giờ độ phức tạp của giai 34 đoạn giải mã là khoảng 2366. Phân tích này cho thấy rằng mật mã WG được bảo vệ chống lại kiểu tấn công tương quan. 1.5 Công nghệ RFID và họ hệ mật WG [6], [8] RFID đã trở thành một phần không thể thiếu trong cuộc sống hàng ngày của chúng ta. RFID được coi là một công nghệ nhận dạng tự động không dây (AIDC). Bất kỳ đối tượng từ xa hoặc người nào có thiết bị RFID được gắn vào có thể được xác định tự động. Thông tin trong hệ thống RFID nói chung diễn ra giữa ba thành phần, thẻ RFID hoặc bộ thu, máy đọc RFID hoặc bộ thu phát và hệ thống cơ sở dữ liệu back- end. Thẻ RFID được chia thành ba loại; thụ động, chủ động và bán thụ động có thể hoạt động trên các băng tần số khác nhau; Tần số thấp (LF), tần số cao (HF), tần số cực cao (UHF)và tần số vi sóng. Các băng tần được mô thả như hình bên dưới Dải tần Mô tả < 135 KHz LF 6.765 – 6.795 MHz HF 7.4 – 8.8 MHz HF 13.553 – 13.567 MHz HF 26.957 – 27. 283 MHz HF 433 MHz UHF 868 – 870 MHz UHF 902 – 928 MHz UHF 2.4 – 2.483 GHz SHF 5.725 – 5.875 GHz SHF Bảng 1.3 Bảng dải tần RFID * Một số lợi ích của thẻ RFID so với mã vạch thông thường: - Thẻ RFID có thể hoạt động không cần có đường ngắm hay không cần có bất kỳ vị trí chính xác nào trong khi đó mã vạch quang học yêu cầu đường ngắm. - Máy đọc RFID có thể đọc (quét) hàng trăm thẻ mỗi giây trong khi mã vạch quang phải được đọc một cách thủ công mỗi lần. - Các thẻ RFID lưu trữ số định danh, lưu trữ dữ liệu ứng dụng cụ thể, thực hiện và trả lời các thông tin dữ liệu cho bất kỳ truy vấn cụ thể nào từ người đọc. - Các thẻ RFID có thể được thực hiện như các bộ cảm biến tích hợp, bộ nhớ đọc/ghi, có khả năng hỗ trợ các hệ thống mã hoá và kiểm soát truy cập. 35 RFID là "công nghệ quan trọng đầu tiên của thế kỷ 21". Do những tiến bộ kỹ thuật trong sản xuất chất bán dẫn, các nhà nghiên cứu đang co lại kích thước của các thẻ RFID. Trong những năm gần đây, Hitachi đã đưa ra các chip RFID nhỏ nhất trên thế giới được gọi là chíp Hitachi loại 0,40,4mm và nó sử dụng ROM để lưu trữ số định danh 128 bit. Do các công nghệ tiên tiến phát triển, chi phí của các thẻ RFID đã giảm đáng kể và kích thước của thẻ thay đổi tùy theo từng ứng dụng. RFID gồm 3 thành phần chính được biểu diễn như hình dưới:  Các thẻ  Máy đọc RFID  Hệ thống cơ sở dữ liệu backend. Hình 1.12 Hệ thống RFID Kích thước của các thiết bị RFID cơ bản phụ thuộc vào các định nghĩa chuẩn RFID được cài đặt. Một số tiêu chuẩn như Organization for Standardization (ISO) và International Electro-technical Commission (IEC) đóng một vai trò quan trọng trong việc điều chỉnh việc sử dụng RFID. Tóm lại, thẻ RFID là một chip silicon nhỏ được thiết kế để liên lạc với truyền thông dữ liệu không dây sử dụng sóng tần số vô tuyến (RF). Chip silicon lưu trữ thông tin định danh duy nhất của đối tượng hoặc con người và truyền định danh dưới dạng số ID duy nhất được gọi là Mã sản phẩm Điện tử ( EPC) tới đầu đọc RFID và lần lượt liên kết với hệ thống cơ sở dữ liệu cuối. Các thiết bị RFID còn được gọi là các thẻ EPC. * Các loại tấn công vào thẻ RFID  Tấn công từ chối dịch vụ: Với loại tấn công này, kẻ tấn công sẽ tạo ra những thẻ đặc biệt để gây ra sự nhầm lẫn cho máy đọc khi xác thực các thẻ cá nhân. 36  Giả mạo: Đây là một kỹ thuật mà kẻ tấn công sao chép dữ liệu thẻ và truyền cho máy đọc.  Làm giả hoặc nhân bản: Kẻ tấn công sao chép dữ liệu của một thẻ vào một thẻ khác sau đó sử dụng thẻ mà được sao chép đó để giao tiếp với máy đọc.  Làm giả (sửa đổi) dữ liệu: Kẻ tấn công cố gắng xóa dữ liệu trên thẻ và làm cho nó không thể truyền tin hoặc sửa đổi dữ liệu thẻ.  Kiểm kê bí mật: Thường được thực hiện ở thẻ EPC có chứa thông tin về nhà sản xuất của đối tượng, mã đối tượng, Vì vậy, bất kỳ ai có máy đọc có thể biết về thông tin người khác. 37 CHƯƠNG 2 CÁC HỆ MẬT WG-8 VÀ WG-16 2.1 Tổng quan hệ mật WG-8 [8] 2.1.1 Giới thiệu WG-8 WG-8 là phiên bản cải tiến của họ hệ mật mã dòng WG, áp dụng cho các thiết bị thông minh với tài nguyên hạn chế. WG-8 kế thừa các ưu điểm của họ mã hóa dòng WG về tính ngẫu nhiên và độ mã hóa, đồng thời có khả năng chống lại các các tấn công thường gặp ở mật mã dòng. So sánh các phần mềm chạy trên 2 thiết bị vi điều khiển công suất thấp, một cài đặt WG-8 và một cài đặt các mã hạng nhẹ khác, xét trên tiêu chí đảm bảo an toàn các phần mềm nhẹ, phần mềm cài đặt WG-8 mang lại hiệu quả cao hơn và tiêu thụ năng lượng ít hơn. Phần này sẽ mô tả chi tiết cấu trúc hoạt động của mật mã dòng WG-8. 2.1.2 Thuật ngữ và ký hiệu F2 = {0,1} là trường Galois với 2 phần tử 0 và 1. p(x) = x8 + x4 + x3 + x2 + 1, đa thức nguyên thuỷ bậc 8 trên 2 . Trường mở rộng 82F của F2 được định nghĩa bởi đa thức nguyên thuỷ ( )p x với 2 8 phần tử. Mỗi phần tử trong 82 được biểu diễn như 1 vector nhị phân 8 bít. Cho  là một phần tử nguyên thuỷ của 82 với p( ) = 0. 2 72 2 2( ) ....Tr x x x x x     , là hàm lưu vết 8 22 . 20 9 8 7 4 3 2( )l x x x x x x x x x          , là đa thức phản hồi của LFSR (cũng là 1 đa thức nguyên thuỷ trên 82 ). WGP-8(xd ) = q(xd + 1) + 1, hoán vị WG-8 với d từ 8 82 2 với d là nguyên tố cùng nhau với 28-1. WGT-8(xd) = Tr(WGP-8(xd )) = Tr(x9 + x37 + x53 + x63 + x127), chuyển đổi WG-8 với d , 8 22 với d là nguyên tố cùng nhau với 2 8-1. Cơ sở đa thức (PB) của 82 : Một cơ sở đa thức của 82 trên 2 là cơ sở có dạng 2 7{1, , ,..., }   . Cơ sở thông thường (NB) của 82 : Một cơ sở thông thường của 82 trên 2 là cơ sở có dạng 72 2{ , ,..., }   , với 5  . Tính tự tương quan: Tính tự tương quan của chuỗi nhị phân với chu kỳ T được định nghĩa khác nhau giữa việc ràng buộc và không ràng buộc khi 0 ánh xạ tới 1 và 1 ánh 38 xạ tới -1. Nếu tất cả đầu ra của giai đoạn tự tương quan đều bằng -1 thì chuỗi đó được gọi là tương quan lý tưởng cấp 2. Khoảng tuyến tính – LS: khoảng tuyến tính hay độ phức tạp tuyến tính của chuỗi nhị phân được định nghĩa là độ dài của thanh ghi dịch tuyến tính nhỏ nhất mà nó tạo ra toàn bộ chuỗi nhị phân Phi tuyến tính: phi tuyến tính của 1 hàm f được định nghĩa là khoảng cách ngắn nhất từ f tới 1 hàm affine bất kỳ với số lượng biến giống nhau. Khả năng miễn dịch đại số (AI): Khả năng miễn dịch đại số của hàm f được định nghĩa là độ nhỏ nhất của hàm bool g sao cho g tương đương với f hoặc là phần bù của f , tức: 0fg  hoặc ( 1) 0f g  . Trong điều kiện lý tưởng, khả năng miễn dịch đại số của hàm f sẽ bằng với độ của f , vì vậy nó có thể chống lại các cuộc tấn công đại số. Ký hiệu  là toán tử cộng bít (phép XOR). Ký hiệu Toán tử nhân trên 82 . 2.1.3 Đặc tả cấu trúc mật mã dòng WG-8 Mật mã dòng WG-8 là 1 biến thể của họ mật mã dòng WG với khóa bí mật là 80- bit và véc tơ khởi tạo là 80-bit; máy sinh lọc phi tuyến tính trên trường hữu hạn F28. Mật mã dòng WG-8 gồm 1 thanh ghi dịch phản hồi tuyến tính (LFSR) 20 trạng thái với đa thức phản hồi l(x) tiếp nối với mô-đun chuyển đổi WG-8 với decimation = 19, hoạt động trong 2 pha: pha khởi tạo và pha thực thi. Pha khởi tạo: Pha khởi tạo cặp khoá/IV của mã dòng WG-8 được minh họa như hình bên dưới. WGP-8(x19): Mô đun hoán vị WG-8 với with Decimation d = 19 Hình 2.1 Pha khởi tạo của mật mã dòng WG-8 39 Tại pha khởi tạo: Khóa bí mật 80-bit: K = (K79,,K0)2 . Véc tơ IV 80 bít: IV = (IV79,,IV0)2. Các trạng thái trung gian của thanh ghi dịch LFSR: 80 19 2,....,S S  , trong đó  ,7,..., ,0 2i i iS S S với 0,.....19i  Khóa và véc tơ IV được sinh ra theo quy luật:  2 8 3,...., 8 , 8 3,..., 8 2i i i i iS K K IV IV  và  2 1 8 7,...., 8 4, 8 7,..., 8 4 2i i i i iS K K IV IV     Với: 0,....9i  Khi khóa và IV được tải vào thanh ghi LFSR, thiết bị chạy trong 40 chu kỳ đồng hồ. Tại mỗi chu kỳ đồng hồ, 8 bít bên trong trạng thái S19 sẽ chạy qua hoán vị phi tuyến tính WG-8 với decimation d = 19 (tức mô-đun 19W 8( )GP x ) Kết quả của S19 sau khi chạy qua WGP-8(x19) được sử dụng để cập nhật trạng thái của thanh ghi LFSR. Thanh ghi này được cập nhật theo quan hệ đệ quy sau:  1920 1 2 3 4 7 8 9 19( ) W 8 ,0 40k k k k k k k k k kS S S S S S S S S GP S k                     Sau pha khởi tạo khóa/IV, WG-8 chuyển sang pha thực thi và sau mỗi chu kỳ đồng hồ sẽ tạo ra dòng khoá 1 bít. Pha thực thi: Pha thực thi của WG-8 được minh họa ở hình bên dưới: WGT-8(x19): Mô đun chuyển đổi WG-8 với Decimation d = 19 WGP-8(x19): Mô đun hoán vị WG-8 với Decimation d = 1057 40 Tr(·): Mô đun tính toán lưu vết Hình 2.13 Pha thực thi của mật mã WG-8 Tại pha thực thi, trạng thái S19 được truyền qua mã chuyển đổi phi tuyến tính WG-8 với decimation d = 19 (tức mô-đun 19W 8( )GT x ), sau khi thực hiện quá trình này sẽ tạo ra dòng khóa. Hàm phản hồi ở pha thực thi nằm ở LFSR và quan hệ đệ quy để cập nhật LFSR là: 20 1 2 3 4 7 8 9( ) , 40k k k k k k k k kS S S S S S S S S k                 Mô-đun chuyển đổi WG-8 bao gồm 2 mô-đun con: (1)Mô đun con 1: mô đun WG-8 hoán vị (WGP-8(x19)), mô đun này hoán vị các phần tử của F28 . (2)Mô đun con 2: mô đun tính toán vết Tr(.), mô-đun này nén chuỗi 8-bit đầu vào thành dòng khóa đầu ra 1-bit. Tính ngẫu nhiên của dòng khóa của WG-8 Dòng khóa sinh ra bởi mã hóa WG-8 có các đặc tính ngẫu nhiên sau: 1. Dòng khóa có chu kỳ 2160 - 1. 2. Dòng khóa cân bằng, nghĩa là số lượng bit-0 nhỏ hơn số lượng bit-1 chỉ 1, trong một chu kỳ của dòng khóa. 3. Dòng khóa là một chuỗi bit tự tương quan lý tưởng cấp 2. 4. Dòng khóa có phân bố t-tuple lý tưởng (1 ≤ t ≤ 20): mọi đầu ra t-tuple có khả năng xảy ra với xác suất như nhau trong một chu kỳ của dòng khóa. 5. Khoảng cách tuyến tính của dòng khóa có thể được xác định chính xác là 233.32. 2.1.4 Đánh giá các tấn công mật mã dòng WG-8 Tấn công đại số Hệ số miễn dịch đại số của WGT-8(x19) bằng 4. Theo cuộc tấn công đại số, độ phức tạp về thời gian và độ phức hợp dữ liệu để khôi phục lại trạng thái nội bộ của LFSR tương ứng là 7 2log 66.0037 1607 . 2 464       và 24.65 160 2 4       . Để thực hiện được các cuộc tấn công đại số nhanh vào mật mã dòng WG-8, ta cần phải tìm hai đa thức đa biến g và h với độ e và d (e <d) sao cho f.g = h. Với WGT-8(x19) và e = 1, không tồn tại một đa thức đa biến h trong 8 biến với độ nhỏ hơn 7. Do đó, đưa ra các cuộc tấn công đại số nhanh đòi hỏi phải có thêm bit dòng khóa với độ phức tạp cao hơn. Trong các 41 mạng 4G-LTE, kẻ tấn công khó có thể nhận được khoảng 224.65 bit dòng khóa từ một phiên truyền thông. Ngay cả khi kẻ tấn công có thể có được nhiều bit khoá cố định và IV, kẻ đó phải thực thi các phép toán với độ phức tạp về thời gian 266.0037, điều đó mới hoàn toàn đánh bại cuộc tấn công này. Tấn công tương quan Trong cuộc tấn công tương quan, kẻ tấn công nhằm mục đích tìm mối tương quan giữa một dòng khóa và một chuỗi đầu ra của LFSR hoặc giữa các dòng khóa. Cuộc tấn công tương quan giữa các dòng khóa sẽ không thực hiện thành công được, dựa vào tính chất tự tương quan hai cấp lý tưởng của dòng khóa đã được chuẩn hoá bởi WG-8. Bây giờ ta xét các cuộc tấn công tương quan nhanh, trong đó dòng khóa tạo ra bởi một mật mã dòng được coi là một phiên bản lỗi của đầu ra LFSR. Đối với việc thực hiện một cuộc tấn công tương quan nhanh, việc ước lượng tuyến tính của WGT-8(x19) có thể được sử dụng để lấy ma trận sinh của một mã tuyến tính, có thể sử dụng giải thuật Maximum Likelihood Decoding (MLD) để giải mã. Cho ( )f x là một hàm tuyến tính trong 8 biến, ta có:    8 19 8 2 108 Pr W 8( )( ) ( ) 0.578125 2 GT x x f x      . Cho t = 3, số lượng dòng khóa (được biểu thị bởi N) cần thiết cho cuộc tấn công để thành công:   1601 2 33.12.ln 2 . .2 k N k    và độ phức tạp giải mã:   6 2ln 2 2 . . 2 k decC k   trong đó  19Pr(W 8( ) ( )) 0.5 0.078125GT x f x      và k là số bit được khôi phục trạng thái bên trong LFSR.  Nếu chọn một giá trị k nhỏ (ví dụ k = 7), số bit cần thiết để thực hiện cuộc tấn công là khoảng 260.31, điều này là không khả dĩ trong thực tế.  Nếu chọn một giá trị của k lớn (ví dụ k = 80), số bit cần thiết để thực hiện cuộc tấn công là khoảng 237.15. Tuy nhiên, độ phức tạp giải mã của cuộc tấn công là khoảng 2102.68, còn tồi hơn so với việc tìm kiếm vét cạn. Vì vậy, mật mã dòng WG-8 cũng an toàn chống lại các cuộc tấn công tương quan nhanh. Tấn công vi phân Pha khởi tạo trong thiết kế đầu tiên của mật mã dòng WG là có thể bị tấn công bởi cuộc tấn công IV đã được chọn, kẻ tấn công có thể phân biệt một số bit đầu ra bằng cách xây dựng một dấu hiệu dựa trên phân tích vi phân. Điểm yếu này đã được sửa trong thiết kế sau này bằng cách đặt mô-đun hoán vị WG ở vị trí cuối cùng của LFSR. Mật mã dòng WG-8 hoán vị WGP-8 (x19) có phân bố vi phân là 8-uniform, tại pha khởi tạo, WGP-8 được chạy 40 lần. Do đó, sau pha khởi tạo, kẻ tấn công sẽ rất khó 42 phân biệt các bít dòng khóa đầu ra vì vi phân trở càng nên phức tạp hơn và bao gồm hầu hết các bit khoá/IV. Vì vậy, WG-8 là an toàn chống lại các cuộc tấn công vi phân. Tấn công hình lập phương Cube attack là một cuộc tấn công khôi phục khoá chung, có thể được áp dụng cho bất kỳ hệ thống mật mã nào, với điều kiện kẻ tấn công có thể lấy được một chút thông tin được biểu diễn bởi một đa thức nhiều biến với độ thấp. Trong mật mã dòng WG-8, sau 40 vòng khởi tạo key/ IV, độ của đa thức đầu ra có thể rất cao. Do đó, sẽ rất khó khăn cho kẻ tấn công để thu thập mối quan hệ độ thấp giữa các bít khóa bí mật. Tấn công phân biệt Gần đây, một cuộc tấn công phân biệt đã được đề xuất chống lại mật mã dòng WG- 7. Do một số nhỏ các vị trí tap trong LFSR của WG-7, đa thức đặc trưng của LFSR cho phép một kẻ tấn công thiết lập một người đặc biệt để phân biệt một dòng khóa được tạo ra bởi WG-7 từ một dòng khóa hoàn toàn ngẫu nhiên. Đối với mật mã WG- 8, đa thức đặc trưng của LFSR bao gồm 4 vị trí tap và một sự phân biệt được xây dựng như sau: 4 7 9( ,... , ,... )i i i iF S S S S   1 2 3 4 7 8 9W 8( )i i i i i i i iGT S S S S S S S S                 1 2 3W 8( ) W 8( ) W 8( ) W 8( )i i i iGT S GT S GT S GT S          4 7 8 9W 8( ) W 8( ) W 8( ) W 8( )i i i iGT S GT S GT S GT S           . Để phân biệt F, xác suất 1 Pr( ( ) 0) 2 F x    với 80 7 2( ,...., ), ix a a a  . Giá trị  sẽ khá nhỏ do một số lượng lớn các biến vi phân, yêu cầu kẻ tấn công phải lấy được nhiều bit dòng khoá để phân biệt dòng khoá. Tuy nhiên điều này gần như là bất khả thi vì số lượng các giá trị có thể của x là 264. Do đó, WG-8 an toàn đối với các tấn công phân biệt thông thường. Tấn công chuyển đổi Fourier rời rạc Tấn công DFT là một kiểu tấn công mới nhằm khôi phục trạng thái bên trong của của filtering generator, lần đầu tiên được đề xuất bởi Rønjom và Helleseth trong việc tấn công máy phát điện lọc qua F2n bởi Gong et al. Trong cuộc tấn công DFT, kẻ thù có thể phục hồi trạng thái bên trong của một filtering generator bằng cách khai thác các bit dòng khoá D với độ phức tạp O(D), trong đó D là độ phức tạp tuyến tính của dòng khoá, sau đó tính toán trước độ phức tạp O(D(log2D)3). Để thực hiện cuộc tấn công DFT chống lại mật mã dòng WG-8, một kẻ tấn công cần phải có được 233.32 bit dòng khoá liên tiếp. Do đó, độ phức tạp của cuộc tấn công để khôi phục lại trạng thái bên trong là 233.32. Đối với các ứng dụng nhúng hạng nhẹ như hệ thống RFID, đầu đọc và thẻ, vì chỉ trao đổi các số ngẫu 43 nhiên có độ dài 32-bit trong mỗi phiên làm việc nên kẻ tấn công sẽ không bao giờ có thể nhận được 233.32 bit dòng khoá. Tấn công thương mại TMD Tấn công thương mại Time-Memory-Data (TMD) là cuộc tấn công giải mã chung được áp dụng cho bất kỳ mật mã dòng nào, đặc biệt là những đối tượng có khả năng kháng mẫu thấp. Độ phức tạp của cuộc tấn công thương mại TMD là 22 n O       , trong đó n là kích thước của trạng thái bên trong. Đối với mật mã dòng WG-8, kích thước của trạng thái bên trong là 160-bit và do đó độ phức tạp của việc đưa ra tấn công TMD dự kiến là O(280). Hơn nữa, tính kháng mẫu của mật mã dòng WG-8 là cao do sử dụng WGT-8(x19) làm chức năng lọc. Biểu diễn ANF của WGT-8(x19) chứa 109 kỳ, trong đó chỉ có 4 kỳ tuyến tính và các kỳ khác có độ nằm trong khoảng (2,8). Do đó, chỉ cần cố định 7 trên 8 biến là có thể nhận được 1 đẳng thức tuyến tính. 2.2 Hệ mật WG-16 [1] 2.2.1 Giới thiệu WG-16 Các hệ thống viễn thông di động đã phát triển theo từng bước. Từ khi triển khai đầu tiên của điện thoại di động analog vào những năm 1980, các thế hệ mạng di động mới đã xuất hiện trên thị trường khoảng 10 năm một lần. Hệ thống thế hệ thứ hai chiếm ưu thế (2G), Hệ thống toàn cầu về điện thoại di động (GSM), được đưa ra vào đầu những năm 1990. Hệ thống 3G thế hệ thứ ba thành công nhất, hệ thống viễn thông di động toàn cầu (UMTS), đã được đưa vào sử dụng vào năm 2002. Kể từ năm 2010, công nghệ LTE (Long Term Evolution) đã trở thành công nghệ băng thông di động lớn không thua gì thế hệ thứ tư (4G). Tiêu chuẩn 4G-LTE nhằm đơn giản hóa cấu trúc của hệ thống, khi nó chuyển từ mạch UMTS và chuyển mạch gói mạng kết hợp sang một hệ thống Architec-ture (IP) toàn bộ Giao thức Internet (IP). Bằng cách kết nối điện thoại thông minh mới nhất với mạng 4G-LTE, các nhà khai thác di động có thể cung cấp cho người đăng ký tốc độ duyệt web nhanh hơn và trải nghiệm tin nhắn, thoại và video tốt hơn. Đối với mỗi sự phát triển của các hệ thống viễn thông, các tính năng bảo mật mới đã được nâng cấp để đáp ứng những kịch bản và ứng dụng triển khai mới. Vì các mạng 4G-LTE có nhiều cấu trúc phẳng hơn, với ít thành phần mạng hơn và hoàn toàn dựa trên IP nên các vấn đề về bảo mật truyền thông phải được giải quyết theo một cách hoàn toàn khác với GSM và 3G. Kiến trúc bảo mật của các mạng 4G-LTE hiện tại về cơ bản là việc tái sử dụng UMTS Authentication và Key Agreement (A-KA) với một số mở rộng và cải tiến nhất định để thích ứng với những thay đổi mà các mạng 4G-LTE đề cập đến. 3GPP-TSG đang tích cực nghiên cứu chi tiết các kỹ thuật của thuật toán bảo mật và mật mã 3GPP để giải quyết bất kỳ lỗ hổng bảo mật tiềm ẩn nào. Hiện tại, có ba bộ mật mã trong hệ thống 3GPP UMTS, bao gồm một mật mã khối Kasumi và hai mật mã dòng SNOW 3G (2006, từ Châu Âu) và ZUC (2010, từ Trung Quốc). Những bộ 44 mật mã này đã được đưa vào tiêu chuẩn 4G-LTE trong đó Kasumi được thay thế bằng AES. Vấn đề chính của bộ mật mã hiện tại được yêu cầu trong tiêu chuẩn 4G-LTE là tính ngẫu nhiên của dòng khoá được tạo ra bởi các thuật toán mật mã rất khó để cài đặt. Ngoài ra, một số cuộc tấn công vào các thuật toán mật mã dòng chính và một số điểm yếu của thuật toán toàn vẹn gần đây đã được phát hiện. Mật mã dòng hướng bít WG-16 là một biến thể mới của mật mã dòng WG nổi tiếng như đã gửi tới dự án eSTREAM. WG-16 thừa hưởng các thuộc tính ngẫu nhiên tốt của họ mật mã dòng WG như chu kỳ, sự cân bằng, sự tương quan lý tưởng cấp hai, phân phối t-tupe lý tưởng và độ phức tạp tuyến tính chính xác. Hơn nữa, WG-16 có thể chống lại các cuộc tấn công phổ biến nhất tấn công vào mật mã dòng, bao gồm tấn công đại số, tấn công tương quan, tấn công khác biệt, tấn công phân biệt, tấn công chuyển đổi Fourier rời rạc, và tấn công thương mại. Do đó, WG-16 là được đề xuất để đảm bảo truyền thông trong các mạng 4G-LTE đang nổi lên. Mã hóa dòng WG-16 có đầu vào là một khóa 128-bit và một véc tơ IV 128-bit và tạo ra một bit dòng khoá cho mỗi chu kỳ đồng hồ. Dòng khoá có thể được sử dụng để mã hóa/giải mã thông tin liên lạc giữa một điện thoại di động và một base station trong các mạng 4G-LTE. 2.1.2 Thuật ngữ và ký hiệu Một số thuật ngữ và các ký hiệu sẽ được sử dụng để mô tả mật mã dòng WG-16, kiến trúc của nó và các thuật toán bảo mật và toàn vẹn để mô tả đặc tính ngẫu nhiên và mật mã của WG-16. - F2 = {0,1}, trường Galois với 2 giá trị 0 và 1. - p(x) = x16+ x5 + x3 + x2 + 1, đa thức nguyên thuỷ mũ 16 trên 2 . - r(x) = x64 + x4 + x3 + x + 1, đa thức nguyên thuỳ mũ 64 trên 2 . - 162F là trường mở rộng của F2 được định nghĩa bởi đa thức p(x) với 2 16 phần tử. Mỗi phần tử trong 162F được biểu diễn bằng 1 véc tơ nhị phân 16 bit. Cho ω là một phần tử nguyên thuỷ của 162F sao cho p(ω) = 0. - 642F , trường mở rộng của F2 được định nghĩa bởi đa thức f(x) với 2 64 phần tử. Mỗi phần tử trong 642F được biểu diễn bằng 1 véc tơ nhị phân 64 bit. - 2 152 2 2( ) ....Tr x x x x x     là hàm lưu vết ánh xạ từ 16 22 . - l(x) = x32 + x31 + x22 + x9 + ω11, đa thức phản hồi của LFSR (cũng là 1 đa thức nguyên thuỷ trên 162F ). - 11 11 6 6 11 11 62 1 2 2 1 2 2 1 2 2 1( )q x x x x x x           là đa thức hoán vị trên 162F . - WGP-16(xd) = q(xd + 1) + 1, hoán vị WG-16 với d ánh xạ từ 16 162 2 , d nguyên tố cùng nhau với 216-1. - WGT-16(xd) = Tr(WGP-16(xd)), chuyển đổi WG-16 với d ánh xạ từ 16 22 , d nguyên tố cùng nhau với 216-1. 45 - Cơ sở đa thức (PB) của 162F : Một cơ sở đa thức của 162F trên F2 là cơ sở có dạng {1, ω, ω2, , ω15}. - Cơ sở thông thường (NB) của F28: Một cơ sở bình thường của 162F trên F2 là cơ sở có dạng 152 2{ , ,..., }   , với θ = ω11 - Tự tương quan: Tự tương quan của một chuỗi nhị phân với chu kỳ T được định nghĩa là sự khác biệt giữa các ràng buộc và không ràng buộc khi 0 ánh xạ đến 1 và 1 ánh xạ đến -1. Nếu tất cả các đầu ra của giai đoạn tự tương quan bằng -1 thì chuỗi được cho là tự tương quan lý tưởng cấp hai. - Khoảng tuyến tính (LS): Khoảng tuyến tính hay độ phức tạp tuyến tính của một chuỗi nhị phân được định nghĩa là độ dài của thanh ghi dịch tuyến tính nhỏ nhất (LFSR) mà sinh ra toàn bộ chuỗi nhị phân. - Phi tuyến tính: phi tuyến tính của một hàm f được định nghĩa là khoảng cách tối thiểu từ f đến bất kỳ hàm affine nào với cùng một số lượng biến. - Sự miễn dịch đại số (AI): Sự miễn dịch đại số của một hàm f được định nghĩa là độ nhỏ nhất của một hàm số bool g sao cho g tương đương với f hoặc là phần bù của f (tức là . 0f g  hoặc ( 1). 0f g  ). Trong điều kiện lý tưởng, phép miễn dịch đại số của một hàm f bằng với độ f , do đó làm cho nó miễn nhiễm với các cuộc tấn công đại số. - Ký hiệu  , toán tử cộng ( XOR). - Ký hiệu  , toán tử nhân trên 162F 2.1.3 Đặc tả cấu trúc mật mã dòng WG-16 WG-16 với khóa bí mật 128-bit và vector khởi tạo IV 128-bit. Mật mã dòng WG- 16 bao gồm một LFSR 32 trạng thái với đa thức thông tin phản hồi l (x) tiếp nối là một mô đun chuyển đổi WG-16 với decimation d = 1057. Do đó, nó có thể được coi là bộ lọc phi tuyến tính trên trường hữu hạn 162F . WG-16 hoạt động theo hai pha, bao gồm pha khởi tạo và pha thực thi. Pha khởi tạo: WGP-16(x1057): Mô đun hoán vị WG-16 với Decimation d = 1057. Hình 2.3 Pha khởi tạo của mật mã dòng WG-16 Pha khởi tạo khoá/IV của mật mã dòng WG-16 được thể hiện trong hình 2.3. 46 Cho khoá bí mật 128 bit là K = (K127, ..., K0) 2, IV 128-bit là IV = (IV127, ..., IV0)2, và trạng thái bên trong của LFSR là S0, . . . , S31 ∈ 162F , trong đó Si = (Si, 15, ..., Si, 0)2 cho i = 0,. . . , 31. Quá trình khởi tạo key/IV được thực hiện theo quy tắc dưới đây:  8 7 8 8 7 8 2 16 ,..., , ,..., ) , 0,1,....,15, , 16,17,....31S i i i i i K K IV IV i i S i      Khi cặp khoá/IV được tải vào LFSR, hệ thống sẽ chạy khoảng 64 chu kỳ đồng hồ. Trong mỗi chu kỳ đồng hồ, 16-bit bên trong trạng thái S31 được gửi đến hoán vị WG-16 phi tuyến tính với decimation d = 1057 (tức mô-đun WGP-16(x1057)) và đầu ra được sử dụng làm phản hồi để cập nhật trạng thái bên trong của LFSR. Thủ tục cập nhật trạng thái LFSR theo quan hệ đệ quy: 11 1057 32 9 22 31 31( ) W 16( ),0 64k k k k k kS S S S S GP S k             Sau pha khởi tạo khoá/ IV, tiếp đến là pha thực thi, dòng khóa 1-bit được tạo ra cho mỗi chu kỳ đồng hồ. Pha thực thi: Pha thực thi của mật mã dòng WG-16 được minh họa trong Hình 2.4. Trong pha thực thi, 16-bit trạng thái bên trong của S31 được gửi đến chuyển đổi phi tuyến tính WG-16 với decimation d = 1057 (tức là WGT-16(x1057) ) và đầu ra là dòng khoá 1- bit. Chỉ phản hồi trong pha thực thi là nằm trong LFSR và quan hệ đệ quy để cập nhật trạng thái bên trong của LFSR được đưa ra bên dưới: 11 32 9 22 31( ) , 64k k k k kS S S S S k         . Mô đun chuyển đổi 1057W 16( )GT x bao gồm hai mô đun con:  Mô đun hoán vị 1057W 16( )GP x .  Mô đun tính toán vết Tr (·). Khi mô đun 1057W 16( )GP x hoán vị các phần tử trên 162F , thì mô đun Tr (·) sẽ thực hiện việc nén 16-bit đầu vào thành một bít dòng khóa. WGT-16(x1057): Mô đun chuyển đổi WG-16 với Decimation d = 1057 47 WGP-16(x1057): Mô đun hoán vị WG-16 với Decimation d = 1057 Tr(·): Mô đun tính toán lưu vết Hình 2.14 Pha thực thi của mật mã WG-16 Tính ngẫu nhiên của dòng khoá WG-16 Dòng khoá được tạo ra bởi mật mã dòng WG-16 có các thuộc tính ngẫu nhiên sau: 1. Dòng khoá có chu kỳ là 2512-1. 2. Dòng khoá cân bằng, nghĩa là số lượng bit-0 nhỏ hơn số lượng bit-1 chỉ 1, trong một chu kỳ của dòng khóa. 3. Dòng khoá là một chuỗi bit tự tương quan lý tưởng cấp hai. 4. Dòng khóa có phân bố t-tuple lý tưởng (1 ≤ t ≤ 32): mọi đầu ra t-tuple có khả năng xảy ra với xác suất như nhau trong một chu kỳ của dòng khóa. 5. Khoảng cách tuyến tính của dòng khóa có thể được tính toán chính xác là 279.046. 2.1.4 Đánh giá các tấn công mật mã dòng WG-16 Tấn công đại số Cuộc tấn công đại số lần đầu tiên được Courtois và Meier đề xuất để tấn công LFSR dựa trên cơ sở sinh chuỗi lọc, mục tiêu của nó là tạo ra phương trình nhiều biến biến với độ thấp hơn, bằng cách nhân hàm lọc bằng đa thức bậc thấp. Cuộc tấn công đại số tạo ra một hệ phương trình phi tuyến tính cho nhiều dòng khoá để phục hồi trạng thái bên trong của LFSR. Hệ số miễn dịch đại số của WGT-16(x1057) bằng 8. Theo cuộc tấn công đại số, độ phức tạp về thời gian và dữ liệu cần để khôi phục lại trạng thái nội bộ của LFSR tương ứng là 7 2log 155.764 5127 . 2 864       và 56.622 512 2 8       . Để thực hiện được các cuộc tấn công đại số nhanh vào mật mã dòng WG-16, ta cần phải tìm hai đa thức đa biến g và h với độ e và d (e <d) sao cho f.g = h. Với WGT-16(x1057) và e = 1, không tồn tại một đa thức đa biến h trong 16 biến với độ nhỏ hơn 15. Do đó, để thực hiện được các cuộc tấn công đại số nhanh đòi hỏi phải có thêm bit dòng khoá với độ phức tạp cao hơn. Trong các mạng 4G-LTE, kẻ tấn công khó có thể nhận được khoảng 256.622 bit dòng khoá từ một phiên truyền thông. Ngay cả khi kẻ tấn công có thể có được nhiều bit cho khoá và IV, kẻ đó phải thực hiện những phép tính với độ phức tạp về thời gian 2155.764 thì mới có thể hoàn toàn đánh bại cuộc tấn công này trong các mạng 4G-LTE. Tấn công tương quan Trong cuộc tấn công tương quan, kẻ tấn công nhằm mục đích tìm mối tương quan giữa dòng khoá và một chuỗi đầu ra của LFSR hoặc giữa các dòng khoá [8, 15, 19]. Nhờ vào tính chất tự tương quan lý tưởng cấp hai của dòng khoá đã được 48 chuẩn hoá bởi mật mã WG-16, cuộc tấn công tương quan giữa các dòng khoá sẽ không thể thành công. Bây giờ ta xét các cuộc tấn công tương quan nhanh, trong đó dòng khoá được tạo ra bởi một mật mã dòng được coi là một phiên bản lỗi của đầu ra LFSR. Đối với việc thực hiện một cuộc tấn công tương quan nhanh, việc ước lượng tuyến tính của WGT-16(x1057) được sử dụng để lấy ma trận sinh của một mã tuyến tính, có thể sử dụng giải thuật MLD để giải mã. Cho ( )f x là một hàm tuyến tính trong 16 biến, ta có:    16 1057 16 2 32160 Pr W 16( )( ) ( ) 0.509277 2 GT x x f x      . Số lượng dòng khoá (được biểu thị bởi N) cần thiết để cuộc tấn công thành công là:   1601 2 33.12.ln 2 . .2 k N k    Độ phức tạp giải mã là:   6 2ln 2 2 . . 2 k decC k   Với  1057Pr(W 16( ) ( )) 0.5 0.009277GT x f x      và k là số bit được khôi phục trạng thái bên trong LFSR. Nếu chọn một giá trị k nhỏ (k = 7), thì số bit cần thiết để thực hiện cuộc tấn công là khoảng 266.46, điều này không thể thực hiện được trong mạng 4G-LTE. Tương tự, nếu ta chọn một giá trị k lớn (k = 80), thì số bit cần thiết để thực hiện cuộc tấn công là khoảng 243,3. Tuy nhiên, độ phức tạp giải mã của cuộc tấn công là khoảng 2121,31, còn tồi hơn so với việc tìm kiếm đầy đủ. Vì vậy, mật mã dòng WG- 16 cũng an toàn chống lại các cuộc tấn công tương quan nhanh. Tấn công vi phân Pha khởi tạo của mật mã dòng WG là có thể bị tấn công bởi cuộc tấn công IV đã được chọn, nơi kẻ tấn công có thể phân biệt một số bit đầu ra bằng cách xây dựng một dấu hiệu dựa trên phân tích vi phân. Điểm yếu này đã được sửa trong thiết kế sau này bằng cách đặt mô đun hoán vị WG ở vị trí cuối cùng của LFSR. Trong mật mã dòng WG-16 hoán vị WGP-16 (x1057) được thực thi 64 lần trong pha khởi tạo. Kết quả là tất cả các bit trạng thái bên trong của LFSR sẽ bị ảnh hưởng sau 64 chu kỳ đồng hồ và sẽ rất khó khăn cho việc kẻ thù phân biệt các bit dòng khoá vì sự khác biệt trở nên phức tạp hơn và bao gồm hầu hết các bit key/IV. Vì vậy, WG-16 là an toàn chống lại các cuộc tấn công vi phân. Tấn công hình lập phương Cube attack là một cuộc tấn công khôi phục khoá, có thể thực hiện trên bất kỳ hệ mật mã nào, kẻ tấn công có thể lấy được các thông tin được biểu diễn bởi đa thức đa biến bậc thấp trong ANF. Trong mật mã dòng WG-16, sau 64 vòng khởi tạo 49 khoá/ IV, độ của đa thức đầu ra sẽ rất cao. Do đó, sẽ rất khó khăn cho kẻ tấn công để thu thập mối quan hệ độ thấp giữa các bít khoá bí mật. Tấn công phân biệt Cuộc tấn công phân biệt đã được đề xuất có thể phá được mật mã dòng WG-7. Vì trong thanh ghi dịch LFSR của mật mã WG-7 có một lượng nhỏ vị trí tap, nên đa thức đặc trưng của LFSR cho phép một kẻ tấn công thiết lập một đối tượng đặc biệt để phân biệt dòng khoá được tạo ra bởi WG-7 từ một dòng khoá hoàn toàn ngẫu nhiên. Trong mật mã WG-16, đa thức đặc trưng của LFSR bao gồm 4 vị trí tap và sự phân biệt được xây dựng như sau: 9 22 31( ,... , ,... )i i i iF S S S S   11 9 22 31W 16(( ) )i i i iGT S S S S          9 22 31W 16( ) W 16( ) W 16( ) W 16( )i i i iGT S GT S GT S GT S         Cho phân biệt F, xác xuất: 1 Pr( ( ) 0) 2 F x    với 160 15 2( ,...., ), ix x x x  . Giá trị  sẽ khá nhỏ do một số lượng lớn các biến phân biệt, yêu cầu kẻ tấn công phải lấy được nhiều bít dòng khóa để phân biệt dòng khóa. Tuy nhiên, không thể tính toán chính xác được giá trị của  vì giá trị chấp nhận được của x là 264. Vì vậy mật mã dòng WG-16 có thể chống lại cuộc tấn công phân biệt. Tấn công chuyển đổi Fourier rời rạc Tấn công Fourier Transform rời rạc (Discrete Fourier Transform) là một kiểu tấn công mới nhằm khôi phục trạng thái bên trong của của máy sinh lọc. Trong cuộc tấn công DFT, kẻ thù có thể phục hồi trạng thái bên trong của một máy sinh lọc bằng cách khai thác các bit dòng khoá D với độ phức tạp trực tiếp O(D), với D là phức tạp tuyến tính của dòng khoá, sau đó tính toán trước độ phức tạp O(D(log2D)3). Để thực hiện cuộc tấn công DFT phá được mật mã dòng WG-16, kẻ tấn công cần phải có được 279.046 bit dòng khoá liên tiếp. Do đó, độ phức tạp của cuộc tấn công này để khôi phục lại trạng thái bên trong là 279.049, sau khi tính toán ngoại tuyến với độ phức tạp 297.96. Đối với các phiên truyền thông bình thường trong mạng 4G-LTE, kẻ tấn công không bao giờ có thể nhận được 279.046 bit dòng khoá liên tiếp, do đó làm cho tấn công DFT không còn khả thi. Tấn công thương mại TMD Tấn công thương mại Time-Memory-Data (TMD) là cuộc tấn công giải mã được thực thi cho bất kỳ mật mã dòng nào, đặc biệt là những đối tượng có khả năng kháng mẫu thấp. Độ phức tạp của cuộc tấn công thương mại TMD là 2(2 ) n O , trong đó n là kích thước trạng thái bên trong. Đối với mật mã dòng WG-16, kích thước của trạng thái bên trong là 512-bit. Do đó độ phức tạp của việc thực hiện tấn công TMD dự kiến là 2256. Hơn nữa, tính kháng mẫu của mật mã dòng WG-16 được cho là cao do sử dụng WGT-16(x1057) làm hàm lọc. Vì vậy, WG-16 có thể chống lại tấn công của TMD. 50 CHƯƠNG 3 ĐỀ XUẤT CẢI TIẾN HỆ MẬT WG – UET VÀ CHƯƠNG TRÌNH DEMO 3.1 Đề xuất cải tiến hệ mật WG-UET Như đã mô tả phương thức tấn công vi phân vào mật mã WG ở mục bên trên, trong phần này tôi sẽ thực hiện phân tích chi tiết khả năng thành công của loại tấn công này khi tấn công vào WG với các cặp khoá khác nhau, và đề xuất cải tiến tấn công vào hệ mật WG. Tấn công WG với cặp khoá 80 bít và véc tơ IV 80 bít Khoá K = k1, k2, k3, · · · , k80 và IV = IV1, IV2, IV3, · · · , IV80. Tiến hành tải các cặp khoá/ IV này vào LFSR. Tấn công IV đã được lựa chọn thực hiện như sau: Với mỗi khoá bí mật K sẽ chọn ra 2 véc tơ IV là IV’ và IV’’ sao cho chúng đồng nhất 6 byte nhưng khác nhau ở 2 byte: ' ''17,...,24 17,...,24IV IV và ' '' 49,...,56 49,...,56IV IV , chúng thoả mãn điều kiện: ' '' ' ''17,...,24 17,...,24 49,...,56 49,...,56IV IV IV IV   Trạng thái ( )S i (1 11)i  tại bước j được ký hiệu là ( )jS i và ký hiệu khoá/IV tải là 0th. Sau đó tải khoá và IV đã được chọn vào LFSR. Ta có trạng thái S(2) và S(5): '0 ''0 '0 ''0(2) (2) (5) (5)S S S S   , ta ký hiệu biểu thức này là vi phân 1 = '0 ''0 '0 ''0(2) (2) (5) (5)S S S S   . Bây giờ xác định vi phân trong 22 bước khi thiết lập khoá/IV. Bảng 3.1 biểu diễn các vi phân này. Vi phân '6 '6 ''6 ''6 2 ( (11) W '( (11)) ( (11) W '( (11))S G S S G S        '0 '0 ''0 ''0( (5) W '( (5)) ( (5) W '( (5))S G S S G S      . Tương tự ta có thể tính được '0 '0 ''0 ''0 3 ( (2) W '( (2)) ( (2) W '( (2))S G S S G S       . S(1) S(2) S(3) S(4) S(5) S(6) S(7) S(8) S(9) S(10) S(11) Bước 0 0  1 0 0  1 0 0 0 0 0 0 bước 1 0 0  1 0 0  1 0 0 0 0 0 bước 2 0 0 0  1 0 0  1 0 0 0 0 bước 3 0 0 0 0  1 0 0  1 0 0 0 bước 4 0 0 0 0 0  1 0 0  1 0 0 bước 5 0 0 0 0 0 0  1 0 0  1 0 bước 6  1 0 0 0 0 0 0  1 0 0  1 bước 7  2  1 0 0 0 0 0 0  1 0 0 bước 8  1 ⊕ 2  2  1 0 0 0 0 0 0  1 0 bước 9 0  1⊕ 2  2  1 0 0 0 0 0 0  1 bước 10  1 ⊕ 2 ⊕ 3 0  1 ⊕ 2  2  1 0 0 0 0 0 0 51 bước 11  2 ⊕ 3  1 ⊕ 2 ⊕ 3 0  1 ⊕  2  2  1 0 0 0 0 0 bước 12  1 ⊕ 2  2 ⊕ 3  1 ⊕ 2 ⊕ 3 0  1 ⊕ 2  2  1 0 0 0 0 bước 13  2 ⊕ 3  1 ⊕ 2  2 ⊕ 3  1 ⊕  2 ⊕ 3 0  1 ⊕ 2  2  1 0 0 0 bước 14  3  2 ⊕ 3  1 ⊕ 2  2 ⊕  3  1 ⊕ 2 ⊕ 3 0  1 ⊕ 2  2  1 0 0 bước 15  1 ⊕ 2 ⊕ 3  3  2 ⊕ 3  1 ⊕  2  2 ⊕ 3  1 ⊕ 2 ⊕ 3 0  1 ⊕ 2  2  1 0 bước 16  1 ⊕ 2 ⊕ 3  1 ⊕ 2 ⊕ 3  3  2 ⊕  3  1 ⊕ 2  2 ⊕ 3  1 ⊕ 2 ⊕ 3 0  1 ⊕  2  2  1 bước 17  1 ⊕ 4  1 ⊕ 2 ⊕ 3  1 ⊕ 2 ⊕ 3  3  2 ⊕ 3  1 ⊕ 2  2 ⊕ 3  1 ⊕ 2 ⊕ 3 0  1 ⊕  2  2 bước 18  3 ⊕ 4 ⊕ 5  1 ⊕ 4  1 ⊕ 2 ⊕ 3  1 ⊕  2 ⊕ 3  3  2 ⊕ 3  1 ⊕ 2  2 ⊕ 3  1 ⊕  2 ⊕ 3 0  1 ⊕ 2 bước 19  1 ⊕ 2 ⊕ 3 ⊕  5 ⊕ 6  3 ⊕ 4 ⊕ 5  1 ⊕ 4  1 ⊕  2 ⊕ 3  1 ⊕ 2 ⊕ 3  3  2 ⊕ 3  1 ⊕ 2  2 ⊕  3  1 ⊕  2 ⊕ 3 0 bước 20  4 ⊕ 6  1 ⊕ 2 ⊕ 3 ⊕  5 ⊕ 6  3 ⊕ 4 ⊕ 5  1 ⊕  4  1 ⊕ 2 ⊕ 3  1 ⊕ 2 ⊕ 3  3  2 ⊕ 3  1 ⊕  2  2 ⊕  3  1 ⊕ 2 ⊕ 3 bước 21  4 ⊕ 5 ⊕ 7  4 ⊕ 6  1 ⊕ 2 ⊕ 3 ⊕  5 ⊕ 6  3 ⊕  4 ⊕ 5  1 ⊕ 4  1 ⊕ 2 ⊕ 3  1 ⊕ 2 ⊕ 3  3  2 ⊕  3  1 ⊕  2  2 ⊕ 3 bước 22  2 ⊕ 3 ⊕ 4 ⊕  5 ⊕ 6 ⊕ 7 ⊕ 8  4 ⊕ 5 ⊕ 7  4 ⊕ 6  1 ⊕  2 ⊕ 3 ⊕  5 ⊕  6  3 ⊕ 4 ⊕ 5  1 ⊕ 4  1 ⊕ 2 ⊕ 3  1 ⊕ 2 ⊕ 3  3  2 ⊕  3  1 ⊕ 2 Bảng 3.1 Bảng biểu diễn vi phân trong 22 bước Từ bảng 3.1 ta có thể thấy vi phân ở bước 22 22 2 3(10)S   Giá trị của 2 3 được tính bởi ' '' '' '' 17,....,24 49,....,64 9,....24 49,....,56 9,....24 49,....,56, , , , ,k k IV IV IV IV . Nếu 2 3 0  thì các bít dòng khoá đầu tiên của IV’ và IV’’ giống nhau. Tính chất này sẽ được sử dụng trong cuộc tấn công để tìm ra giá trị của 2 3 liệu có bằng 0 hay không. Giả sử, giá trị của 1 2 3 0   là phân phối ngẫu nhiên thì xác suất để 2 3 0  sẽ là 2 -29. Ta cần tạo ra khoảng 229 cặp 2 3( , ) với điều kiện 2 3 0  . Sẽ có 3 byte IV và 1 byte vi phân được lựa chọn, vì thế luôn có sẵn khoảng 24 312 255 / 2 2  cặp 2 3( , ) , như vậy có thể dễ dàng tạo ra 229 cặp 2 3( , ) thoả mãn điều kiện trên. 52 Cải tiến tấn công vi phân Xét vi phân tại 2 trạng thái 22 (7)S và 22 (8)S , các vi phân này là 1 2 3  . Nếu 1 2 3 0   thì các bít thứ 3, thứ 4 của 2 dòng khoá sẽ khác nhau, khoá 17,....,24k và 49,....,64k có thể khôi phục với 20 29 30.4 1 1 1 1 2 2 2 2 2i ii i              IV được chọn. Thực hiện cuộc tấn công này, bằng việc quan sát các bít dòng khoá thứ 1,3,4 thì việc khôi phục khoá 17,....,24k và 49,....,64k cần khoảng 28 1.13 30.12 2 2 2   IV được chọn Thiết lập vi phân tại trạng thái 0 (3)S và 0 (6)S và quan sát các bít thứ 2,3 của dòng khoá để có thể khôi phục được 24 bít của khoá bí mật, 25,....,40k và 65,....,72k cần 2 30.4 IV được chọn. Như vậy với khoảng 30.1 30.4 31.32 2 2  IV được chọn ta có thể khôi phục được 48 bít khoá bí mât (80 bít). Dưới đây là bảng tấn công WG với các cặp khoá/IV có kích thước lớn hơn 80 bít Khoá k bít (bit) IV k bít (bit) Số lượng bít khoá có thể khôi phục (bit) 96 96 48 112 112 72 128 128 72 hoặc 96 Bảng 3.2 Bảng tấn công WG với các cặp khoá/IV có kích thước lớn hơn 80 bít 53 3.2 Bài toán và cài đặt chương trình Bài toán Xây dựng hệ thống RFID áp dụng mật mã WG-5. Tập trung vào xây dựng mô hình sử dụng mật mã WG-5 để xác thực lẫn nhau của máy đọc và thẻ thụ động trong hệ thống RFID. Quy trình xác thực lẫn nhau giữa máy đọc và thẻ Hệ thống RFID bao gồm máy đọc RFID, thẻ và máy chủ lưu trữ dữ liệu. Thẻ với khóa bí mật k0 80 bít và một IDi duy nhất. Phiên làm của RFID với mật mã WG-5 gồm 5 bước như hình bên dưới: Hình 15 Sơ đồ giao thức xác thực lẫn nhau của RFID sử dụng WG-5 Bước 1: Máy đọc gửi yêu cầu cùng với một Rr ngẫu nhiên 40-bit tới thẻ. Bước 2: Khi nhận được Rr, phía thẻ sẽ tạo ra Rt ngẫu nhiên 40 bít, tính toán r tIV R R . Sau đó phía thẻ sẽ sử dụng đầu vào là IV và khóa bí mật k0 80 bít để chuyển tới WG5func và tạo ra các bít dòng khóa có độ dài 160 bít. Phía thẻ tạo ra WGt có độ dài 40 bít và gửi cặp (WGt, Rt) tới máy đọc Bước 3: Máy đọc sẽ tìm kiếm tất cả các thẻ IDi và khóa ki được lưu trên máy chủ cho tới khi tìm được W ' Wt tG G . Tóm lại, máy đọc sẽ kiểm tra MSB bít của chuỗi dòng 54 khóa, nếu khớp, máy đọc sẽ kiểm tra thêm các bít dòng khóa của chuỗi. Nếu MSB bít không khớp nó sẽ ngừng sinh thêm chuỗi dòng khóa và chọn khoá mới. Bước 4: Khi xác thực thẻ, máy đọc cập nhật cặp thẻ ' ' 0( , W )sk G . Để xác thực, máy đọc tạo ra 'W rG có độ dài 40 bit và gửi nó tới thẻ. Bước 5: Khi phía thẻ nhận được 'W rG , phía thẻ sẽ kiểm tra điều kiện 'W Wr rG G . Nếu nó bằng nhau thì máy đọc đã xác thực thành công. Sau khi máy đọc xác thực, phía thẻ sẽ cập nhật giá trị khóa hiện tại k0 vào WGs. Khi đó, cả phía thẻ và máy đọc đều đã xác thực lẫn nhau. 55 KẾT LUẬN Các kết quả đã đạt được Thẻ RFID đã và đang được phát triển mạnh mẽ không chỉ trên thế giới mà tại việt nam cũng đang ngày càng sôi động, hứa hẹn tạo một bước ngoặt mới cho thị trường thẻ với những ứng dụng và tiện ích vô cùng độc đáo. Ngoài các cơ hội là những thách thức không hề nhỏ, đó chính là vấn đề bảo mật thông tin ngày nay đang đặt lên hàng đầu. Trong khóa luận này tôi đã trình bày được những kết quả sau: - Trình bày giới thiệu nguyên tắc hoạt động cơ bản của họ hệ mật WG, phân tích các thuộc tính ngẫu nhiên của dòng khoá, đánh giá các cuộc tấn công thành công vào họ hệ mật WG. - Nghiên cứu về hệ mật WG-8 và WG-16. - Ứng dụng mật mã WG-5 trong thẻ RFID. Đặc tả cấu trúc mật mã dòng WG-16 o Initialization Phase o Running Phase o Tính ngẫu nhiên của dòng khoá WG-16 Đánh giá các tấn công mật mã dòng WG-16 o Tấn công đại số o Tấn công tương quan o Tấn công vi phân o Tấn công hình lập phương o Tấn công phân biệt o Tấn công chuyển đổi Fourier rời rạc o Tấn công TMD - Trình bày và đánh giá, so sánh mức độ an toàn, tối ưu của hai hệ mật WG- 16 và WG-8. - Đánh giá cuộc tấn công vi phân vào họ hệ mật WG. - Đánh giá ưu và nhược điểm, những thách thức và xu hướng phát triển mật mã này vào các thiết bị nhỏ nhẹ được ở Việt Nam. - Đề xuất cải tiến hệ mật WG - UET 56 HƯỚNG NGHIÊN CỨU TIẾP THEO Chú trọng vào việc thiết kế thuật toán mã hóa, tìm ra các lỗ hổng tấn công và đề xuất cải tiến phù hợp với cài đặt trong môi trường có tài nguyên hạn chế. 57 TÀI LIỆU THAM KHẢO [1] Specification of the Stream Cipher WG-16 Based Confidentiality and Integrity Algorithms Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, N2L 3G1, CANADA [2] Comparison of Lightweight Stream Ciphers: MICKEY 2.0, WG-8, Grain and Trivium. [3] The WG Stream Cipher Yassir Nawaz and Guang Gong Department of Electrical and Computer Engineering University of Waterloo Waterloo, ON, N2L 3G1, CANADA. [4] Cryptanalysis of WG-7: A Lightweight Stream Cipher Center for Advanced Computing – Algorithms and Cryptography, Department of Computing, Faculty of Science, Macquarie University, Sydney, NSW 2109, Australia [5] CRYPTREC Cryptographic Technology Guideline (Lightweight Cryptography) [6] Role of Cryptographic Welch-Gong (WG-5) Stream Cipher in RFID Security Rajesh Kumar Mota. [7] Optimized Hardware Implementations of Lightweight Cryptography, Gang qiang Yang, Waterloo, Ontario, Canada, 2017. [8] A Lightweight Stream Cipher for Resource-Constrained Smart Devices, Xinxin Fan, Kalikinkar Mandal and Guang Gong, Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, N2L 3G1, CANADA [9] W. Meier, E. Pasalic, and C. Carlet, Algebraic Attacks and Decomposition of Boolean Functions, Advances in Cryptology EUROCRYPT-2004, LNCS 3027, pp.474-491, Springer-Verlag, 2004. [10] Chosen IV Attack on Stream Cipher WG Hongjun Wu and Bart Preneel Katholieke Universiteit Leuven, Dept. ESAT/COSIC