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

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