Công nghệ thông tin & Cơ sở toán học cho tin học<br />
<br />
NGHIÊN CỨU PHÁT TRIỂN<br />
GIAO THỨC TRAO ĐỔI KHÓA NHÓM<br />
Đỗ Việt Bình*<br />
Tóm tắt: Trong việc phát triển các giao thức trao đổi khóa nhóm, có rất nhiều<br />
các mục tiêu mà các nhà phát triển phải đặt ra để khắc phục các hạn chế như:<br />
Giảm số lần giao dịch, giảm độ phức tạp tính toán, tránh để lộ khóa cặp và đảm<br />
bảo các thay đổi trạng thái trong nhóm động. Trong khuôn khổ bài báo này, xin<br />
được đề cập đến hai hạn chế chính mà các giao thức tập trung khắc phục và nâng<br />
cao hiệu quả đó là tránh để lộ khóa cặp và giảm khối lượng giao dịch và tính toán.<br />
Từ khóa: Trao đổi khóa; Trao đổi khóa nhóm; Giao thức.<br />
<br />
1. MỞ ĐẦU<br />
Trao đổi khóa Diffie - Hellman [2] (DH) là cơ sở cho các giao thức trao đổi khóa trong<br />
trường hợp hai bên. Hơn nữa, theo giả thiết DH quyết định giao thức này là giả định an<br />
toàn trong một mô hình với kênh chứng thực. Tất cả các giao thức trao đổi khóa quan<br />
trọng được trình bày sau thuộc về lớp lớn các giao thức nhóm, có thể được xem như là<br />
phần mở rộng tự nhiên của giao thức hai bên DH thành trao đổi với các trường hợp bên.<br />
Trong việc xây dựng giao thức trao đổi khóa nhóm có một số đặc điểm mà chúng ta lưu<br />
ý, để có thể có được một giao thức tốt, đảm bảo cả về mặt hiệu quả thực hiện cũng như độ<br />
bảo mật.<br />
- Hiệu quả giao thức được quan tâm nhiều hơn do số lượng người tham gia và khoảng<br />
cách giữa họ.<br />
- Do nhóm là động nên các thành viên có thể tham gia hay rời khỏi nhóm bất kỳ lúc<br />
nào. Như vậy giao thức phải có những dự phòng và xử lý để đạt được hiệu quả cao nhất.<br />
- Khả năng lộ khóa do những yếu tố phi kỹ thuật sẽ cao hơn vì vậy cần có cách thức để<br />
nhanh chóng thay đổi khóa nhưng phải đảm bảo tính hiệu quả của thuật toán.<br />
Bài báo tập trung phân tích giao thức GDH nguyên thủy và một số phát triển của giao<br />
thức này, từ đó đề xuất giao thức trao đổi khóa nhóm mới, khắc phục điểm yếu của các<br />
giao thức trước đây.<br />
2. NỘI DUNG NGHIÊN CỨU<br />
2.1. Giao thức trao đổi khóa Diffie-Hellman<br />
Để bắt đầu, hai đối tượng Alice (A) và Bob (B) thỏa thuận lựa chọn một nhóm hữu hạn<br />
có cấp là và một phần tử , với là phần tử sinh của , là một số nguyên tố<br />
lớn. Các giá trị và có thể được sinh ra nhờ các thuật toán mô tả trong [5], [6].<br />
Các tham số đầu vào chung: , với là một số nguyên tố lớn, là một phần tử<br />
sinh của nhóm nhân .<br />
Đầu ra: Một giá trị (phần tử) thuộc được chia sẻ giữa A và B.<br />
Các bước thực hiện:<br />
- A phát sinh một giá trị ngẫu nhiên , tính và<br />
gửi giá trị này cho B;<br />
- B phát sinh một giá trị ngẫu nhiên , tính và<br />
gửi giá trị này cho A;<br />
<br />
<br />
<br />
104 Đỗ Việt Bình, “Nghiên cứu phát triển giao thức trao đổi khóa nhóm.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
- A tính giá trị<br />
- B tính giá trị<br />
Dễ dàng thấy rằng cả A và B đã nhận được một giá trị khóa bí mật chung chia sẻ, nó có<br />
thể được sử dụng trên các hệ mật khóa bí mật.<br />
Một số khuyến nghị khi thực hiện và sử dụng giao thức DH:<br />
- Lựa chọn số nguyên tố đủ lớn ( ).<br />
- Lựa chọn là phần tử sinh của nhóm .<br />
- A và B sẽ xóa các giá trị và khi kết thúc hoạt động của giao thức. Khi thực hiện<br />
điều này chúng sẽ có đặc tính bảo mật thẳng.<br />
Năm 1996, M. Steiner đề xuất hai giao thức trao đổi khóa nhóm phát triển từ giao thức<br />
DH, là IKA.1 và IKA.2 [3], [5] (còn được biết đến với tên GDH2 và GDH3). Năm 2011,<br />
Om Pal và các cộng sự đề xuất giao thức trao đổi khóa nhóm dựa trên giao thức IKA.2, sử<br />
dụng mô hình bên thứ ba tin cậy [4], cung cấp khả năng chống tấn công kẻ đứng giữa và<br />
có độ phức tạp tương đương IKA.2.<br />
2.2. Giao thức IKA.1<br />
Giao thức này thực hiện hai bước chính:<br />
- Bước 1: Hình thành tất cả các tích . Thực hiện<br />
bằng cách tính và truyền theo thứ tự từ đến với .<br />
- Bước 2: Truyền quảng bá và từng thành viên<br />
sẽ tính ra khóa của nhóm.<br />
2.3. Giao thức IKA.2<br />
IKA.2 được chia làm bốn bước:<br />
- Bước 1: Thu thập đóng góp của các thành viên từ đến , sẽ nhận được<br />
.<br />
- Bước 2: sẽ gửi lại giá trị này cho tất cả các thành viên. Các thành viên nhận<br />
<br />
được sẽ tính mũ nghịch đảo để được .<br />
<br />
- Bước 3: Các thành viên sẽ gửi lại giá trị tương ứng<br />
cho .<br />
<br />
- Bước 4: tính và gửi lại giá trị cho các<br />
thành viên. Các thành viên tính được khóa nhóm .<br />
2.4. Đánh giá độ phức tạp giao thức<br />
Bảng 1. Độ phức tạp của giao thức IKA.1 và IKA.2.<br />
Giao thức Số giao dịch Số phép tính lũy thừa<br />
IKA.1<br />
<br />
IKA.2<br />
<br />
2.5. Đề xuất giao thức trao đổi khóa nhóm NGDH1<br />
2.5.1. Mô tả giao thức<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 105<br />
Công nghệ thông tin & Cơ sở toán học cho tin học<br />
<br />
Trong tư tưởng về giao thức trao đổi khóa nhóm (GDH) nguyên thủy và các cải tiến<br />
trong IKA.1 và IKA.2 đều không thực hiện được việc bảo mật khóa cặp. Điều này làm cho<br />
các đối tượng tham gia vào nhóm phải lưu giữ thêm một khóa cho các giao dịch trao đổi<br />
khóa cặp. Với môi trường truyền thông hiện nay, một đối tượng tham gia vào rất nhiều các<br />
giao dịch, hơn nữa, việc sinh khóa và quản lý khóa cũng có những thủ tục và khó khăn<br />
nhất định. Do vậy, việc tiết kiệm được lượng khóa cho các đối tượng là rất cần thiết.<br />
Giao thức trao đổi khóa nhóm được thực hiện như sau:<br />
- Chia nhóm thành từng cặp hai thành viên, nếu số thành viên là lẻ thì thành viên cuối<br />
cùng ghép với thành viên đầu tiên. Ta được các cặp với .<br />
- Từng cặp trao đổi thiết lập khóa bí mật chung chính là khóa bí mật hình thành bởi<br />
giao thức trao đổi khóa cặp DH. Ta được .<br />
- Thực hiện tiếp theo IKA.2 với nhóm . Lưu ý bước cuối cùng của IKA.2<br />
thực hiện truyền đến tất cả các thành viên chứ không phải là đại diện của cặp. Ở bước này,<br />
2 thành viên trong nhóm sẽ thực hiện song song, từ đó, có thể giảm bớt thời gian tính toán.<br />
<br />
<br />
<br />
<br />
Bước 1 (trao đổi khóa cặp)<br />
, nếu thì ;<br />
<br />
<br />
<br />
<br />
Bước 2 (nâng lũy thừa)<br />
<br />
<br />
Bước 3 (Gửi quảng bá)<br />
<br />
<br />
<br />
Bước 4 (Gửi lại)<br />
<br />
<br />
<br />
<br />
Bước 5 (Gửi quảng bá)<br />
Hình 1. Sơ đồ giao thức NGDH1.<br />
2.5.2. Đánh giá giao thức<br />
a) Không để lộ khóa cặp<br />
Như đã trình bày ở trên, khóa cặp chính là khóa sử dụng giữa hai đối tượng, theo giao<br />
thức DH được tính là . Trong giao thức NGDH1, thay<br />
vì trao đổi trên đường truyền ta thực hiện trao đổi hay . Vì vậy, các<br />
được giữ bí mật.<br />
<br />
<br />
<br />
<br />
106 Đỗ Việt Bình, “Nghiên cứu phát triển giao thức trao đổi khóa nhóm.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
Xa hơn nữa, ta nhận thấy giao thức không chỉ bảo mật được khóa<br />
cặp mà còn bảo vệ được các tập con, chính là các khóa<br />
của các nhóm con trong mô hình GDH truyền thống.<br />
Điều này cũng có ý nghĩa lớn vì trong mô hình GDH khi có một hoặc một vài thành viên<br />
rời khỏi nhóm thì ít nhất một thành viên còn lại sẽ phải thay đổi giá trị bí mật của mình để<br />
hình thành khóa nhóm mới do khóa nhóm cũ đã tham gia trên kênh truyền không an toàn.<br />
b) Dễ dàng hoán vị để hình thành khóa mới<br />
Trong các giao thức IKA.1 và IKA.2 hay GDH truyền thống, giá trị của khóa nhóm<br />
luôn là . Như vậy, khi vì một sự cố nào đó mà khóa bị lộ đơn giản như chỉ cần<br />
một thành viên để lộ, khi đó sẽ phải thay đổi khóa nhóm. Việc thay đổi này thực hiện thật<br />
không dễ dàng, sẽ chỉ thực hiện được khi một thành viên hoặc một nhóm con thành viên<br />
thay đổi các giá trị bí mật của mình và tính toán lại khóa.<br />
Với NGDH1 thì lại khác, khóa nhóm lúc này không phải là mà là ,<br />
ta có thể thấy ngay khi thay đổi giá trị của thì khóa nhóm cũng thay đổi. Mà việc thay<br />
đổi lại được thực hiện khá đơn giản bằng việc thay đổi các sắp xếp các cặp. Ví dụ thay<br />
vì xếp cặp 1-2 và 3-4 ta đổi 1-3 và 2-4 hay 1-4 và 2-3 là ta đã thu được các mới. Như<br />
vậy, chính việc thay đổi hoán vị ta đã thu được giá trị mới hay khóa nhóm mới.<br />
Ta có thể tính số khả năng hay số các khóa nhóm có thể có bằng cách tính hoán vị và tổ<br />
hợp như sau: Với một thay đổi để hình thành khóa mới ta sẽ phải tính toán trên ít nhất 4<br />
thành viên. Ví dụ ta đang có các cặp là 1-2 và 3-4. Bây giờ sử dụng hoán vị 1-3 thì hiển<br />
nhiên cặp đôi còn lại cũng phải thay đổi, ta được 2-4. Vậy với nhóm 4 thành viên ta được ba<br />
hoán vị: {1-2, 3-4}, {1-3, 2-4}, {1-4, 2-3} tất cả các hoán vị khác đều cho giá trị khóa nhóm<br />
trùng với các giá trị trên. Như vậy, ta thu được 3 giá trị khóa khác nhau. Mở rộng bài toán<br />
cho n thành viên ( ) ta tính được số các hoán vị mà không bị trùng bằng các lấy ra tập<br />
con 4 phần tử và hoán vị trên chúng. Việc lấy số tập con này chính là tổ hợp chập 4 của<br />
. Vậy số hoán vị có thể có là hay số khóa nhóm khác nhau thu được là:<br />
<br />
<br />
<br />
Có thể thấy số khóa nhóm khác nhau có được sẽ rất lớn do sự tăng nhanh của hàm giai<br />
thừa. Ví dụ, với ta có được 630 giá trị khóa khác nhau.<br />
Việc có được số lượng khóa nhóm khác nhau lớn mà không phải thay đổi giá trị khóa<br />
bí mật của các thành viên có ý nghĩa rất lớn trong thực tế. Vì trong vấn đề quản lý và trao<br />
đổi khóa hiện nay, các giá trị khóa bí mật và công khai thường được sử dụng trong một<br />
khoảng thời gian nhất định, và thường có một bên thứ 3 đứng ra cấp và quản lý. Ví dụ<br />
trong mô hình hạ tầng khóa công khai PKI thì các khóa thường có giá trị trong khoảng 6<br />
tháng. Việc thay đổi khóa liên tục không những lãng phí, tốn thời gian và công sức mà còn<br />
phải thực hiện lại các giao dịch và tính toán lại các khóa với các đối tượng đã giao dịch<br />
trước đó, thêm vào đó đối tượng giao dịch cũng phải tính toán và xác thực lại sự bảo đảm<br />
của khóa mới.<br />
c) Độ phức tạp tính toán<br />
Bảng 2. Kết quả đánh giá giao thức NGDH1.<br />
Giai đoạn Số giao dịch Số phép tính lũy thừa<br />
1<br />
2<br />
<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 107<br />
Công nghệ thông tin & Cơ sở toán học cho tin học<br />
<br />
3<br />
4<br />
5<br />
Tổng<br />
3. THỬ NGHIỆM<br />
Cài đặt chương trình:<br />
- Ngôn ngữ lập trình: Java<br />
- Bước 1 (trao đổi khóa cặp), các nhóm thực hiện đồng thời.<br />
- Bước 5 (gửi quảng bá), hai thành viên của nhóm cuối cùng ( ) tính toán song<br />
song và gửi lại cho các thành viên.<br />
Tham số thử nghiệm:<br />
- Độ dài : 1024 bit<br />
Bảng 3. Kết quả thử nghiệm.<br />
Số lượng thành viên NGDH1 IKA.2<br />
50 306 ms 569 ms<br />
100 587 ms 1397 ms<br />
150 954 ms 1841 ms<br />
200 1258 ms 2253 ms<br />
4. KẾT LUẬN<br />
Bài báo đã phân tích giao thức GDH nguyên thủy và IKA.1 và IKA.2 đều không thực<br />
hiện được việc bảo mật khóa cặp, tác giả đề xuất xây dựng giao thức cải tiến trong trường<br />
hợp trao đổi khóa nhóm NGDH1 nhằm tránh lộ khóa cặp, đưa ra lượng khóa dồi dào thuận<br />
lợi cho những biến động của nhóm và giảm các bước tính toán.<br />
Đây là những cải tiến tốt, có ý nghĩa thiết thực và được chứng minh tương đối chặt chẽ<br />
bằng cả lý thuyết và thực nghiệm. Hướng nghiên cứu tiếp theo là cung cấp khả năng xác<br />
thực giữa các thành viên trong nhóm.<br />
TÀI LIỆU THAM KHẢO<br />
[1]. Bresson, Emmanuel, Olivier Chevassut, and David Pointcheval. 2001.<br />
“Provably authenticated group Diffie-Hellman key exchange — the dynamic case.”<br />
Edited by Colin Boyd, Advances in Cryptology – ASIACRYPT ’2001, Lecture Notes<br />
in Computer Science. International Association for Cryptologic Research Gold Coast,<br />
Australia: SpringerVerlag, Berlin Germany, 290–309.<br />
[2]. Diffie W and Hellman M. New Directions in Cryptography, “IEEE Transactions on<br />
Information Theory”, IT-22(6), 1976: 644-654.<br />
[3]. Michael Steiner,” Secure Group Key Agreement”,Saarlandes Univ., Saarbrucken,<br />
Germany, 2002.<br />
[4]. Om Pal, Anupam Saxena, Uttam Kumawat, Ravi Batra, Zia Saquib (2011), “Secure<br />
Group Deffie-Hellman Key Exchange with ID Based Cryptography, International<br />
Conference on Advances in Communication, Network, and Computing”,CNC<br />
2011: Computer Networks and InformationTechnologies, pp 498-503.<br />
[5]. Steiner, Michael, Gene Tsudik, and Michael Waidner. 1996, March.<br />
“Diffie-Hellman Key Distribution Extended to Groups.” Edited by<br />
Clifford Neuman, Proceedings of the 3rd ACM Conference on Computer and<br />
<br />
<br />
<br />
108 Đỗ Việt Bình, “Nghiên cứu phát triển giao thức trao đổi khóa nhóm.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
Communications Security. New Delhi, India:ACM Press, 31–37.<br />
[6]. Wenbo Mao (2003), “Modern Cryptography”, Theory and Practice Prentice Hall<br />
PTR, p. 648.<br />
[7]. William Stallings (2005), “Cryptography and Network Security Principles and<br />
Practices”, Fourth Edition, Prentice Hall PTR, p. 592<br />
ABSTRACT<br />
A SOLUTION FOR GROUP KEY EXCHANGE PROTOCOLS<br />
To develop a group key exchange protocols, there are many objectives that<br />
needed to be concerned such as: reducing number of transactions, avoiding<br />
complicated calculations, securing key pairs and guaranteeing/maintaining status<br />
changing in dynamic groups. In this paper, clearifying two main drawbacks of<br />
group key exchange protocols as well as proposees solutions to improve the<br />
protocol will be focused on.<br />
Keywords: Key exchange; Group key exchange; Protocol.<br />
<br />
Nhận bài ngày 15 tháng 5 năm 2017<br />
Hoàn thiện ngày 16 tháng 6 năm 2017<br />
Chấp nhận đăng ngày 20 tháng 6 năm 2017<br />
<br />
Địa chỉ: Viện Công nghệ thông tin/ Viện KH-CN quân sự.<br />
*<br />
Email: binhdv@gmail.com<br />
<br />
<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 109<br />