Giải pháp chống tấn công bằng phân tích năng lượng dựa trên thuật toán Elliptic - Edward - Bạch Hồng Quyết

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 105 GIẢI PHÁP CHỐNG TẤN CÔNG BẰNG PHÂN TÍCH NĂNG LƯỢNG DỰA TRÊN THUẬT TOÁN ELLIPTIC - EDWARD Bạch Hồng Quyết*, Đinh Thế Cường, Vũ Mạnh Tuấn Tóm tắt: Bài báo đề xuất giải pháp chống tấn công bằng phân tích năng lượng trên thẻ thông minh bằng cách sử dụng thuật toán Elliptic – Curve25519 làm thuật toán mã hóa dữ liệu trên thẻ thông minh. Giải pháp được xây dựng trên cơ sở toán học của các thuật toán mật mã nhằm mục đích chống rò rỉ và mất cắp dữ liệu qua các kênh bên. Hệ mã Elliptic – Curve25519 là hệ mã trên đường cong đạt chuẩn NIST – 256, với độ an toàn cao và tốc độ xử lý nhanh có thể được ứng dụng rộng rãi trong các thiết bị bảo mật tương lai. Từ khóa: Chống tấn công bằng phân tích năng lượng, Chống tấn công kênh bên, Curve25519. 1. MỞ ĐẦU Tấn công bằng phân tích năng lượng vi sai (DPA) đang là mối đe dọa tiềm tàng đến an toàn của các thiết bị mật mã, đặc biệt là các thiết bị nhúng như thẻ thông minh. Tấn công bằng DPA là phương pháp thám mã bằng cách đo và dự đoán năng lượng tiêu thụ của một thiết bị trong hoạt động của nó. Để tấn công bằng DPA, kẻ thám mã cần phải thực hiện một số lượng lớn các phép đo. Sau đó, thực hiện thống kê, phân tích sự sai khác giữa những dấu vết năng lượng thu được với giá trị năng lượng dự đoán dựa trên cơ sở “chia để trị” [1], tức là sẽ dự đoán một phần nhỏ của khóa bí mật tại một thời điểm, sau đó kết hợp với các giá trị đã biết khác trở thành đầu vào để dự đoán các hoạt động xử lý dữ liệu bên trong của thuật toán mật mã. Nếu các hoạt động này liên quan đến khóa bí mật (hoặc một phần của khóa bí mật), kẻ thám mã có thể sử dụng những thông tin có được từ thám mã để trích xuất từng bit của khóa bí mật, sau đó phục hồi khóa bí mật. Song song với các hoạt động thám mã và các nghiên cứu chống thám mã dựa trên cơ sở lý thuyết, thông qua thử nghiệm để đưa ra giải pháp thực tế. Giải pháp ngăn chặn tấn công bằng phân tích năng lượng có thể được chia làm hai loại sau: - Chống tấn công bằng phân tích năng lượng ở mức thuật toán: Làm cho năng lượng tiêu thụ biến thiên ngẫu nhiên trong quá trình hoạt động của các thiết bị sao cho năng lượng không liên quan đến kết quả trung gian. Có thể ngẫu nhiên hóa dấu vết năng lượng tiêu thụ bằng cách làm xáo trộn các hoạt động mật mã kết hợp với chu kì hoạt động của các mô – đun. - Chống tấn công bằng phân tích năng lượng ở mức mạch: Sử dụng các mạch có tính chất đặc thù, làm cho năng lượng tiêu thụ không phụ thuộc vào dữ liệu được xử lý. Tức là năng lượng tiêu thụ qua mạch là như nhau khi dữ liệu đầu vào là khác nhau hoặc năng lượng luôn không đổi ngay cả khi không xử lý dữ liệu, như vậy sự tương quan giữa năng lượng tiêu thụ và dữ liệu đầu vào sẽ mất đi và kẻ tấn công không có cở sở để thực hiện hoạt động thám mã. 2. CHỐNG TẤN CÔNG PHÂN TÍCH NĂNG LƯỢNG Ở MỨC MẠCH Chống tấn công bằng phân tích năng lượng ở mức mạch: là phương pháp chống tấn dựa vào cấu trúc của mạch, tức là dựa vào nguyên lý và cơ chế hoạt động của Công nghệ thông tin B. H. Quyết, Đ. T. Cường, V. M. Tuấn, “Giải pháp chống tấn công Elliptic - Edward.” 106 mạch. Giải pháp này sử dụng kỹ thuật là phẳng dòng điện [11] hoặc dấu tín hiệu bằng cách thêm một mạch giám sát dòng vào khối mật mã làm cho năng lượng tiêu thụ không đổi [12]. Ngoài ra, có thể thay đổi ngẫu nhiên điện áp nguồn và tần số của mạch hoặc ngắt bộ xử lý một cách ngẫu nhiên trong quá trình thực hiện thuật toán mật mã làm cho thời điểm thực hiện các hoạt động trung gian được ngẫu nhiên [9][10]. Tuy nhiên, kiến trúc các mạch trên khá phức tạp, gây tiêu tốn tài nguyên và năng lượng, khó đạt được trong thực tế, chỉ làm giảm sự tương quan giữa năng lượng tiêu thụ thực tế với dữ liệu xử lý mà không ngăn chặn được tấn công. 3. CHỐNG TẤN CÔNG BẰNG PHÂN TÍCH NĂNG LƯỢNG Ở MỨC THUẬT TOÁN Năm 2007, Bernstein đã đề xuất một dạng hệ mật trên đường cong Elliptic là Curve25519[11]. Hiện tại, Curve25519 có thể hỗ trợ bất kỳ ứng dụng bảo mật nào về mặt bảo mật phần mềm và phần cứng mà không gây ra khó khăn trong việc xử lý dữ liệu. Phương trình đường cong Elliptic Edward dạng Curve25519[1]:  2 3 2 255: 486662 2 19 E y x x x mod    - Phép nhân Montgomery trên Curve25519 Hình 1. Phép công điểm và nhân đôi điểm theo thang Montgomery. Thang Montgomery được đề xuất để tăng tốc phép nhân vô hướng trên các hệ mật đường cong Elliptic dạng Montgomery như Elliptic Edward dạng Curve 25519 (mọi đường cong Edwards xoắn trên trường phi nhị phân pF có thể chuyển thành một đường cong Montgomery tương ứng trên trường pF [2]). Trong thuật toán này, tọa độ _x xP của điểm P được biểu diễn dưới dạng Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 107 ( , ) p p p p p X X Z khi x Z  [2]. Giả sử có điểm P điểm, và ( , , )i i iQ X Y Z , theo dõi hai điểm trung gian ,Q Q và độ sai khác Q Q trên P . Trên Curve25519 phép cộng điểm và phép nhân đôi điểm được định nghĩa như các bước của thang Montgomery. Theo đó, đối với Curve25519 , phép cộng điểm và nhân đôi điểm chỉ dựa vào tọa độ x , z của hai điểm , Q Q [8]. Hình 1 mô tả thang Montgomery. Các bước tính:             2 2 22 2 2 2 2 2 ' ' 1 4 4 ' ' 4 ' ' Q Q Q Q Q Q X x z x z x z Z xz u Axz z X xx zz Z xz zx x               Ta thấy rằng, không phải tính toán tung độ y giúp tiết kiệm nhiều phép tính, dẫn tới thuật toán nhanh hơn so với các thuật toán nhị phân cổ điển và yêu cầu bộ nhớ ít hơn [8]. Trên Curve25519, phép nhân vô hướng k P bao gồm 255 phép nhân đôi điểm và phép cộng điểm, thực hiện theo sau là phép nhân nghịch đảo 1 X Z   . Hình 1 cho thấy trong thuật toán cho có 3 điểm 1, , Q Q Q với 1 , Q Q Q . Mỗi phép cộng điểm (hoặc trừ) sẽ kết hợp với một phép nhân điểm và ngược lại giúp cho việc thiết kế phần cứng hiệu quả. Ngoài ra, các hoạt động luôn thực thi như nhau, độc lập với dữ liệu xử lý và các tính toán được thực hiện liên tục, do đó có khả năng ngăn chặn tấn công thời gian (timing attacks). 3.1. Curve25519 – đơn lõi Thực thi thuật toán Curve25519 vào thiết bị mật mã, bên cạnh đó tích hợp bộ xử lý tín hiệu kỹ thuật số (Digital Signal Processors – DSP) vào các mô – đun mật mã để hỗ trợ quá trình tính toán. Hình 2 dưới đây mô tả thiết kế của một mô – đun nhân điểm. - Modul cộng điểm Modul cộng điểm thực hiện tính modc a b p  với 2 khối kỹ thuật xử lý tín hiệu số DSP. DSP đầu tiên thực thi các hoạt động chính ( c a b   ), DSP còn lại làm nhiệm vụ dự đoán kết quả c c p   . Giá trị của ,c c  được lưu trữ trong BRAM – thứ nhất và được dán nhãn để phân biệt với nhau. - Modul nhân điểm Thành phần chiếm bộ nhớ lớn nhất của Curve25519 là modul nhân điểm, với 18 khối DSP giúp cho quá trình xử lý dữ liệu Curve25519 nhanh hơn . Một modul nhân điểm gồm 55 chu kì, trong đó 34 chu kì dùng cho các phép nhân điểm thực tế, các chu kì còn lại dùng để tải và lưu trữ dữ liệu. Hình 2 cho thấy, trên thực tế chỉ có modul nhân điểm đầu tiên có 55 chu kì, còn các modul nhân điểm tiếp theo Công nghệ thông tin B. H. Quyết, Đ. T. Cường, V. M. Tuấn, “Giải pháp chống tấn công Elliptic - Edward.” 108 sẽ được thực hiện với độ trễ 17 chu kì. Hình 3 dưới đây tổng quan về Curve25519 – đơn lõi. Hình 2. Mô – đun nhân điểm. Hình 3. Tổng quan Curve25519. Curve25519 sử dụng hệ tọa độ ánh xạ ngẫu nhiên để che giấu các điểm công khai trên đường cong và các giá trị trung gian tính được từ công thức cộng điểm và nhân đôi điểm. Khi đó, điểm P trên đường cong được ánh xạ thành điểm P : ( , ) ( , , )P X Y P X Y Z Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 109 Mặt khác, phép cộng điểm và nhân đôi điểm trên đường cong Curve25519 chỉ phụ thuộc vào tọa độ ( , )X Z [8]. Giả sử: 1Z  . Khi đó, điểm P trên Curve25519 được che giấu bằng điểm P với: ( , ) ( , )P P X Z X        với  là một giá trị ngẫu nhiên 255bit Giá trị của điểm ( , )P X   thu được từ phép nhân điểm sẽ thay thế cho điểm ( , )P X Y được lưu trữ trong BRAM, bên cạnh đó tất cả các giá trị khác và các hằng số của việc tính toán không bị ảnh hưởng. Các giá trị  được chọn ngẫu nhiên cho mỗi thực hiện, do đó ngay cả khi thực hiện cùng một phép vô hướng cho các điểm thuộc đường cong có đầu vào giống nhau thì các kết quả trung gian có thể khác nhau trong quá trình thực hiện các phép nhân điểm nhưng kết quả cuối cùng vẫn chính xác. Mục đích của thiết kế Curve25519 – đơn lõi là để hỗ trợ thực hiện phép cộng điểm và nhân điểm trên hệ tọa độ ánh xạ theo các bước trong thuật toán Montgomery. Bước cuối cùng của thuật toán, lõi mật mã thực thi phép nhân điểm nghịch đảo để chuyển đổi đầu ra từ hệ tọa độ ánh xạ trở về hệ tọa độ ban đầu. Bộ vi xử lý số học (DSP) hỗ trợ hai chế độ hoạt động cơ bản: kết hợp chức năng nhân đôi điểm và cộng điểm vào một modul. Hình 3 cho thấy lõi sử dụng 2 BRAMs. BRAM – thứ nhất chỉ nhận được các kết quả của phép cộng điểm, sau đó chuyển kết quả thành đầu vào cho phép nhân điểm. BRAM – thứ hai lưu trữ kết quả phép nhân điểm và dữ liệu ban đầu, 2 BRAM này hoạt động song song với nhau. Trước mỗi một phép nhân điểm, sẽ có một bộ địa chỉ mới được tạo ra dùng để lưu các giá trị trung gian và các kết quả lưu trữ trong BRAM. Mỗi BRAM gồm 6 bit nên có thể sinh ra 6 2 bộ địa chỉ ngẫu nhiên được sinh ra sau mỗi phép nhân điểm thay vì một địa chỉ cố định. Địa chỉ ban đầu sẽ được xác định bằng thông tin phản hồi tuyến tính (LFSP) dựa trên công thức 6 5 1x x  . Khi đó, sử dụng 6bit ngẫu nhiên mở rộng như đầu vào cho LFSP. Sau khi lõi Curve25519 thực hiện một phép nhân đôi điểm thì LFSP và các địa chỉ ngẫu nhiên sẽ được lưu để sử dụng cho phép nhân điểm tiếp theo, khởi tạo BRAM mới bằng các giá trị và hằng số. Do các bộ địa chỉ được sinh ra ngẫu nhiên sau mỗi phép nhân điểm kéo theo giá trị năng lượng tiêu thụ của thiết bị thu được cũng mang tính chất ngẫu nhiên. Vì vậy, kẻ thám mã sẽ không phục hồi được khóa bí mật. 3.2. Curve25519 – đa lõi Để nâng cao tốc độ xử lý dữ liệu thì Curve25519 – đa lõi được thiết kế chuyên dụng chỉ hỗ trợ các bước chức năng (hoạt động nhân điểm và cộng điểm) mà không hỗ trợ phép nghịch đảo. Phép nghịch đảo sẽ được thực hiện cuối cùng bởi một modul chuyên dụng khác. Hình 4 mô tả thiết kế của Curve25519 đa – lõi. - Modul tính phần tử nghịch đảo Modul tìm phần tử nghịch đảo được xây dựng dựa trên cơ sở của thuật toán Euclid mở rộng, giúp cho tốc độ xử lý dữ liệu được nhanh hơn. Các lõi hoạt động đồng thời và độc lập với nhau. Dữ liệu đầu vào sẽ được chia thành các gói nhỏ và phân phối tới bất kỳ lõi nào đang ở trạng thái “sẵn sàng”, tạo ra sự xáo trộn dữ liệu. Mặt khác, lõi đang hoạt động sẽ được đánh dấu trạng thái Công nghệ thông tin B. H. Quyết, Đ. T. Cường, V. M. Tuấn, “Giải pháp chống tấn công Elliptic - Edward.” 110 “bận”. Sau đó, ngay khi lõi thực hiện tính toán xong thì kết quả sẽ được đưa ngay tới mô – đun tính phần tử nghịch đảo và lõi sẽ trở về trạng thái “sẵn sàng”. Do đó, tốc độ xử lý dữ liệu sẽ được nâng lên rất nhiều và cũng sẽ làm tăng thêm sự xáo trộn ngẫu nhiên năng lượng tiêu thụ của thiết bị qua các lõi, giúp ngăn chặn được tấn công. Hình 4. Curve25519 - đa lõi. 4. KẾT LUẬN Trên thực tế, các giải pháp chống tấn công phân tích năng lượng vi sai tại thời điểm hiện tại là chưa hoàn toàn triệt để. Để tấn công bằng DPA thành công, kẻ tấn công cần tiếp cận được thiết bị mật mã để đo được các đại lượng vật lý phát sinh từ thiết bị trong quá trình hoạt động. Như vậy, để chống tấn công thì việc đầu tiên là giữ bí mật thuật toán mật mã được sử dụng và bảo vệ chống truy cập vật lý đến thiết bị. Tuy nhiên, cách này khá thụ động và chỉ có điều kiện áp dụng cho một số ít thiết bị đặc biệt. Hai kỹ thuật Curve25519 – đơn lõi hay Curve25519 – đa lõi cung cấp mức độ bảo mật cao, có thể ứng dụng vào thiết bị mật mã khác nhau và đặc biệt thích hợp với các bộ vi xử lý hay vi điều khiển được sử dụng phổ biến hiện nay như thẻ thông minh. Năng lượng tiêu thụ thực tế của thiết bị độc lập tới dữ liệu cần bảo vệ, do đó ngăn chặn được tấn công phân tích năng lượng vi sai. TÀI LIỆU THAM KHẢO [1]. Pascal Sasdrich, Tim Guneysu, “Implementing Curve25519 for Side-Channel- Protected Elliptic Curve”, 2016. [2]. Michael Hutter · Christof Paar · Ana Helena Sánchez, "High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers”, 2015. [3]. Wesley Janssen, “Curve25519 in 18 tweets”, 2014. [4]. Pascal Sasdrich, Tim Guneysu, “Efficient Elliptic-Curve Cryptography using Curve25519 on Reconfigurable Devices”, 2014. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 111 [5]. Prof. Dr. Tanja Lange, Rick van Galen, “A Performance Study of X25519 on Cortex-M3 and M4”, 2015. [6]. Fabrizio De Santis, Georg Sigl, “Towards Side-Channel Protected X25519 on ARM Cortex-M4 Processors”, 2015. [7]. Đinh Quốc Tiến, Đỗ Đại Chí, “Về tấn công gây lỗi trên hệ mật đường cong elliptic dựa vào đường cong xoắn”, 2017 [8]. Daniel J. Bernstein, Tanja Lange, “Faster addition and doubling on elliptic curves”, năm 2007 [9]. S. Yang, “Power Attack Resistant Cryptosystem Design: A Dynamic Voltage and Frequency,Conf. on Design, Automation and Test in Europe, Washington DC”, 2005. [10]. C. Clavier, J. Coron, và N. Dabbous, “Differential Power Analysis in the Presence of Hardware Countermeasures, Workshop on CHES. London, Springer-Verlag” [11]. R. Muresan, “Current flattening in software and hardware for security applications, Conf. on hardware/software codesign and system synthesis”, 2004 [12]. D. Mesquita và các đồng nghiệp, “Current mask generation: a transistor level security against DPA attacks, Integrated circuits and system design”, 2005 ABSTRACT A SOLUTION FOR DEFENDING AGAINST POWER ANALYSIS ATTACKS WITH ELLIPTIC-EDWARD ALGORITHM In this paper, a solution for defending against power analysis attacks on smartcards by applying Elliptic-Curve25519 algorithm to encrypt data on cards is proposesed. The solution is based on the mathematics of encryption algorithms in order to prevent the leakage and lost of data through side channels. The proposed Elliptic-Curve25519 algorithm is an elliptic curve cryptography approved by NIST-256 with high security and high speed, and could be widely used in future encryption devices. Keywords: Resistance Against Differential Power Analysis, Resistance Against Side Channel Attack, Curve25519. Nhận bài ngày 16 tháng 8 năm 2017 Hoàn thiện ngày 26 tháng 11 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: Viện CNTT, Viện KHCN quân sự. * Email: bachhongquyet@gmail.com.