رمزنگاری کاربردی - قسمت پنجم : Key exchanges

در فصل پنجم کتاب اقای وونگ میرسیم به بحث تبادل کلید، مجدد قبل شروع تاکید میکنم این مقاله از سری مقدماتی رو بخونید و قسمت های قبلی یعنی hash function ، MAC و Authenticated Encryption رو هم مطالعه بکنید و بعد ادامه بدید

این فصل از چیز هایی که تا به الان خوندیم سخت تره و چون قراره یه سری مفاهیم پایه ای رمزنگاری نامتقارن رو هم یادبگیرید، باید تا اخر فصل دووم بیارید و زنده بمونید :)

اگر سخت بود حتما سوال بپرسید !

با مفهوم تبادل کلید اشنا هستید، اقا وونگ به صورت خلاصه اینطور بیان میکنه :

ما یه کلید عموم داریم و یه کلید خصوصی،طرف مقابلم همینه، کلید عمومی رو میدیم به طرف مقابل و طبق مقابلم کلید عمومیشو میده به ما ، حالا هردو با کلید های خصوصیمون و کلید عمومی طرف مقابل یه چیز مشترک میسازیم

یک نکته ای داریم : در passive MITM ما به مشکلی نمیخوریم از لحاظ دزدیده نشدن کلید در فرایند key exchange و مهاجم کاری ازش بر نمیاد ولی توی Active MITM مهاجم میتونه فرایند key Exchange رو شنود کنه و کلیدو خودش بسازه ، راه حلم استفاده از authenticated key exchanges هست که بهش میرسیم

اگر ما از unauthenticated key exchanges استفاده کنیم شرایط اینطوری میشه که مهاجم میتونه Active MITM انجام بده

اگر فرق Passive/Active رو نمیدونید باید به صورت خلاصه بگم که در Passive MITM مهاجم فقط شنود میکنه ارتباط رو و اطلاعات ردو بدل شده رو میتونه ببینه ولی نمیتونه تغییر توش ایجاد کنه ! ولی توی Active MITM مهاجم نه تنها میتونه شنود کنه بلکه میتونه اطلاعات رو تغییر بده و اطلاعات تغییر یافته رو به طرفین بده، درواقع خودش رو میتونه جای هرکدوم از طرفین جا بزنه و وسط مکالمه بشه و طوری وانمود کنه که شما دارید با طرف مقابل حرف میزنید ولی انگار دارید با مهاجم حرف میزنید

🔸نکته : authenticated key exchange چی هست؟ وقتی شما قبل فرایند key exchange به اون مقصد یا فردی که میخواید باهاش تبادل کلید کنید اعتماد داشته باشید که این اعتماد توسط کلید عمومی و امضا دیجیتال و اینا بدست میاد، و باید هر دو جهت این اعتماد باشه که به حالتی که هر دو کلید همو دارنو ارتباط امنه و همو میشناسن میگن mutually authenticated key exchange

و از همین رو ما از key exchanges خالی نمیتونیم استفاده کنیم، اینترنت خیلی وسیعه و باید یه مکانیزمی کنارش باشه که بدونیم طرفی که مقابل ماست اونیه که میگه و اینجاست که digital signature میاد وسط و این دوتا primitive باید باهم استفاده بشن ، توی فصل 7 دربارش بیشتر میگیم

🔸5.2 The Diffie-Hellman (DH) key exchange

اول میریم سراغ ریاضیاتش بعد میریم سراغ استاندارد هاش و ..

🔸5.2.1 Group theory

پشت دفی هلمن یک مفهوم ریاضیه به اسم group theory و این قضیه پشت اکثر الگریتم های نامتقارن هست و ریاضیات از اینجا شروع میشه

اولا group چیه ؟ یه سری elements و یه عملیات مثل ضرب یا جمع که بین این ها صورت میگیره ، حالا DH با multiplicative group کار میکنه که یه گروهه ولی در اون از ضرب استفاده میشه به عنوان عملیات باینری

اقای وونگ جلوتر میگه وقتی میخوام بنویسم a × b دیگه ضربشو نمیزارم و مینویسم ab (توی ریاضیت هم اکثرا یا نمینویسن یا . میزارن)

حالا این group ما 4 تا ویژگی خاص داره :

🔸ویژگی اول Closure : اگر روی دوتا المنت عملیات انجام بدیم ، نتیجه یه المنت جدید خواهد بود، طبق عکس مشهوده که برای دوتا المنت a و b وقتی ما عملیات انجام بدیم نتیجه میشه ab (مثلا عملیات ضرب a × b)

🔸ویژگی دوم Associativity : ما برای انجام عملیات ترتیب خاصی نیاز نیست رعایت کنیم، اگر بخوایم روی چندین المنت عملیات انجام دهیم، اینکه اول سراغ کدام برویم مهم نیست، برای مثال اگر ما سه تا المنت داشته باشیم تحت عنوان a و b و c و بنویسیم a(bc) یا (ab)c نتیجه تفاوتی نخواهد کرد

🔸ویژگی سوم Identity element : یه المنت خاص تعریف میکنیم که اگر با این المنت عملیاتی انجام بشه ، نتیجه متفاوت نخواهد بود و المنت جدیدی درکار نخواهد بود، در ریاضیات ضربدر 1 هیچ تغییری در عدد ایجاد نمیکند، پس 1 میود Identity element ما، پس a × 1 = a

🔸ویژگی چهارم Inverse element : باید هرالمنت گروه ما معکوس داشته باشد ، و ما معکوس رو با توان -1 نشون میدیم، پس معکوس a میشه a–1 و به این طریق هم مینویسمش : 1/a یا 1 تقسیم بر a و همیشه یادتون باشه که ضرب یک عدد در معکوس خودش میشه 1

اگر در ادامه یه سری چیز ها مثل عدد حسابی صحیح اعشاری کسری و... رو متوجه نشدید یا یادتون رفته و یا حتی عملیات های ضرب و جمع و... کسری یا اعشاری رو یادتون نیست، یه سرچی در گوگل به فارسی بکنید و مقالات و ویدیو های ساده ای هست که عالی توضیح دادند

حالا DH ما از اعداد صحیح مثبت استفاده میکنه که از 1 شروع میشه تا p – 1 که اینجا p یک عدد اوله (prime number) و 1 مون هم identity element ماست ، حالا اینکه این عدد اول چی باشه رو استانداردی که استفاده میکنیم معلوم میکنه و باید خیلی بزرگ باشه که امنیت ما خوب باشه !

عدد اول چیه ؟ یا از سری مقدماتی بلدید یا الان بخونید، عددیه که فقط بر خودش و 1 بخش پذیره ، یعنی جز این دوتا اگر به عدد دیگه ای تقسیم کنی باقی ماندش رند و درست درمون نیست، اعداد اول هم از 2 ،3 ، 5 ،7 و ... شروع میشن و ته ندارن ! دقت کنید که ته ندارن ! و پیدا کردن این اعداد برای رمزنگاری ها و cryptoanalyst ها چالشه ، توی رمزنگاری نامتقارن یا کلید عمومی بسیار از این ها استفاده میشه ، و خوشبختانه ما الگریتم های داریم که اعداد اول بزرگی رو پیدا کنن ولی اگر بخوایم از الگریتم هایی استفاده کنیم که سریع این کارو بکنن نمیتونن خوب انجامش بدن و ممکنه بجاش اعداد اول برن سراغ اعداد شبه اول pseudo-primes که خیلی بهشون میخوره که اول باشن ولی شاید نباشن :) و این درواقع یه ریسک امنیتی بزرگه ! که در سال 2017 هم کشف که که بیشتر از یک میلیون دستگاه اعداد اول درستی نمیسازن !

حالا این DH قصه ما از modular multiplication استفاده میکنه ولی قبل اینکه به اون برسیم باید بفهمید modular arithmetic چی هست :

محاسبات مدولار سیستمی از محاسبات است که در آن اعداد پس از رسیدن به مقدار معینی که مدول نامیده می‌شود، دور آن پیچیده می‌شوند. این بدان معناست که اعدادی که معمولاً بزرگتر از مدول هستند به عدد معادل کوچکتری در محدوده مدول "کاهش" می‌یابند.

برای یه مثال خیلی ساده در نظر بگیرید که ما 24 ساعت داریم، وقتی ساعت از 1 صبح شروع میشه میرسه به 12، دوباره از 1 شروع میشه ! حالا برای درک بیشتر بیایید پا تخته

اگر مفهوم mod یا modulus رو بدونید ، میدونید که باقی مانده رو به ما میده بجای خارج قسمت ، حالا وقتی ما 7 رو تقسیم بر 5 میکنیم، خارج قسمت میشه 1 ولی باقی مانده میشه 2 ، به همین ترتیب وقتی 8 رو تقسیم بر 5 میکنیم خارج قسمت میشه 1 ولی باقی مانده میشه 3 ، اینجا ما modulus رو عدد 5 در نظر گرفتیم !

حالا در علم ریاضی اینطوری میگیم : 7 مساوی 2 مود 5 ، یا 7 موافق 2 مود 5 عه (یا دوتا خط میزاریم یا سه تا خط و فرقی نداره !)

به شکل سنتی ، اینطوری نمایشش میدن :

حالا الان میتونید اینارو خودتون بدست بیارید :

8 = 1 mod 7
54 = 2 mod 13
170 = 0 mod 17

و اگر modulus ما 12 باشه ، ما اگر اعداد 13، 25 و 37 رو هم بر اون تقسیم کنیم باز به 1 میرسن و بعد زیاد میشن

پس تا اینجا فهمیدید که modular arithmetic درواقع یه نوع نشون داد تقسیمه ! ولی modular multiplication چیه ؟ اونم نزدیک همینه ، ما میدونیم که 3 ضربدر 2 میشه 6 : 3 × 2 = 6

و از بالا دیدیم که

6= 1 mod 5

حالا اگر بجای 6 بنویسیم 2 ضربدر 3 :

3 × 2 = 1 mod 5

به این میرسیم، حالا یک نکته ای اینجا هست ، به دو عددی که حاصل ضرب انها بشود 1 و mod یک عددی میگن multiplicative inverses ، به عبارت دیگر در مثال بالا 3 ضربدر 2 میشه 1 و ادامش mod5 ، ما فقط به این کار داریم که یه عددی ضربدر یک عددی باقی ماندشون 1 میشه ، به این اعداد ( که اینجا 3 و2 هستن) میگن multiplicative inverses ، و اگر بخوایم این رو نمایش بدیم اینطوری میگیم :

هر عدد به توان -1 میشد برعکس، یادتونه ؟ حالا ما اینجا میتونیم اینطوری بگیم که 3 و 2 معکوس های mod 5 هستن

🔸نکته : اگر با mod یه عدد ثابتی بخوایم مرتب کار کنیم ، مثل 5 ، دیگه نمینویسمش

3×2= 1 mod 5 => 3×2=1

نکته : عدد 0 رو ما اصلا تو محاسبات modulus مون نمیاریم چون هر چیزی ضرب یا تقسیم بر 0 میشه 0 و هیچ عددیم نمیتونی پیدا کنی که :

0×b=1 mod 5

اینجا b اون عددیه که نمیشه پیدا کرد 😂

حالا که ما group مون رو داریم، که از اعداد مثبت تشکیل شده تا p-1 و عملیات modular multiplication هم عملیات ماست، حالا گروه ما دوتا قابلیت داره :

🔸اول Commutative : یعنی جهت ضرب اصلا اهمیت نداره توی modular multiplication ، یعنی :

a×b=b×a mod 5

اینکه بنویسیم a ضربدر b یا برعکس هیچ مهم نیست (واقعا توی ریاضی اینا مهم نیست و فکر نکنید قانون خاصیه، نه اینا ریاضیت محضه)

و گروهی که این قابلیت رو داشته باشه بهش میگن Galois group

🔸دوم finite field : به Galois group ای میگن که علاوه بر عملیات ضرب بشه توش جمع هم استفاده کرد، مثلا اعداد 1.2.3.4 رو در نظر بگیرید :

2+3=5 ≡0 mod 5

3×2=6 ≡ 1 mod 5

فرقی اصلا نداره !

🔸نکته : همین finite field ای که الان باهم بررسیش کردیم، توی DH استفاده میشه و بهش میگن Finite Field Diffie-Hellman (FFDH)

🔸مفهوم subgroup و cyclic subgroup :

مفهوم group رو که یادتون هست؟ ما امدیم همون رو کوچیک کردیم و کردیم subgroup ، همونه و دقیقا همون 4 تا قابلیت group رو داره، ولی کوچیک تر شده هست ، درواقع subgroup ها در group هست

حالا cyclic subgroup همون subgroup عه که میتونه از روی یه generator یا base ساخته بشه

و حالا generator چیه ؟ generator میاد cyclic subgroup میسازه با ضرب کردن عدد در خودش تا اینکه تحت یه modulus خاص به یک برسه ، صبر کنید الان ساده توضیحش میدم 😂🙏 :

ما عدد 4 و mod 5 رو در نظر میگیریم :

4 mod 5 = 4

حالا میخوایم 4 رو ضربدر خودش کنیم ، یبار اینکارو میکنیم :

4 × 4 = 16 => 16 mod 5 = 1

16 تقسیم بر 5 میشه 3 و باقی ماندش میشه 1

سه بار 4 رو ضرب میکنیم :

4 × 4 × 4 = 4^3 = 64 => 64 mod 5 = 4

میبینید که در 3 امین تکرار ما جوابمون شد 4 ، حالا 4 بار در هم ضرب میکنیم :

4^4 = 256 mod 5 = 1

باز به یک رسیدیم (هی 4 و 1 تکرار میشه) ، و این تا ابد ادامه داره و هی 4 و 1 تکرار میشه ، حالا باید دقت کنید که اولین بار که 1 دیدید، قبل اون میشه اون order یا عدد ما یا تعداد المنت ما ، درواقع قبل اینکه دوبار بخوایم ضربش کنیم، پس اعداد المنت ما میشن 1 و 4 و ما دوتا عدد المنت یا 2 تا order داریم، بزارید بیشتر مثال بزنم:

مثال :

Subgroup generated by 1:

• 1^1 = 1

این یک subgroup عه که فقط یک عضو داره اونم identity element عه که 1 عه و order این subgroup عدد 1 عه

Subgroup generated by 2:

• 2^1=2
• 2^2 = 4 mod 5
• 2^ 3 = 8 mod 5 = 3 (8÷5= خارج قسمت 1 و باقی مانده 3)
• 2^4 = 16 mod 5 = 1
  (16÷5= خارج قسمت3 و باقی مانده1)

این یک cyclic subgroup هست با 4 عضو یا 4 order که میشن 2,4,3,1

Subgroup generated by 3:

• 3^1=3
• 3^2= 9 mod 5 = 4
• 3^3 = 27 mod 5 =2
• 3^4= 81 mod 5 =1

این یک cyclic subgroup هست با order 4 و این چهار تا order عبارتند از : 3, 4, 2, 1

Subgroup generated by 4 :

این همونطور که بالاتر گفته شد 2 تا order داره و {4, 1} هستن

پس فهمیدید Order of a Subgroup درواقع تعداد المنت های داخل subgroup هستن تا قبل اینکه سیکل تکرار بشه

دوتا نکته :

🔸نکته : وقتی modulus ما عدد اول باشه (مثل 5)، هر المنت توی group میاد و cyclic subgroup خودشو میسازه (یعنی ساخت این cyclic subgroup منوط به استفاده از عدد اول به عنوان modulus هست)

🔸نکته : FFDH که بالاتر گفتیم از این مفاهیم ساخت subgroups و generators ها استفاده میکنه برای ساخت یک کانال ارتباطی امن

پس خلاصه :

1. یک group حاوی یه سری اعداده که با اعمال باینری کار میکنن و 4 تا قانونم داره (closure, associativity identity element, inverse element)

2. الگریتم DH تحت Galois group کار میکنه که با اعداد مثبت سروکار داره (اعداد مثبت تا اعداد اول) و عملیاتشم modular multiplication هست ، همچنین commutativity هم داره

3. در DH group هر المنت خودش generator یه subgroup هست

مفاهیم Groups که بررسی کردیم، قلب خیلی از primitives های رمزنگاری هستند و باید به درک خوبی از مفاهیم بالا برسید اگر میخواید توی رمزنگاری درک خوبی از کارکرد بقیه primitives ها داشته باشید

🔸5.2.2 The discrete logarithm problem: The basis of Diffie-Hellman

این بحثو خیلی روون و ساده توی سری مقدماتی توضیح دادم که لینکشم اول مقاله هست، ولی طبق متن کتاب بخوام یه بار دیگه بگم : اگر ما یه generator داشته باشیم، مثلا 3 ، و یه المنت تصادفی ام انتخاب کنیم (مثلا 2 ) :

y=g^x mod p

یاداوری : که g درواقع generator هست ، p یه عدد اول و y اون المنت ماست

2 = 3^x mod 5

اگر ما اینجا بگیم x چیه ، و شما باید این x رو پیدا کنید، این همون مسئله لگاریتم گسستست ، درواقع میگه چند بار باید generator رو در خودش ضرب کنیم تا اون المنت بدست بیاد و عبارت صحیح بشه

هرچقد عدد اول ما بزرگ تر باشه، پیدا کردن x سخت تره ک امنیت DH به این وابستس

حالا چند تا نکته :

1. تمام افرادی که میخوان تبادل کلید کنن باید سر یه عدد اول خیلــــــــــی بزرگ p و یه generator یا همون g توافق کنن

2. تمامی این افراد باید یه عدد تصادفی به نام x بسازن که کلید خصوصیشون حساب میشه

3. تمام این افراد کلید عمومیشونو از این طریق بدست میارن :

g^x mod p

و اینکه ما میگیم حل مسئله لگاریتم گسسته سخته یعنی هیچکس نباید بتونه کلید پرایویت رو از روی کلید عمومی استخراج کنه

برای دراوردن این مقدار x الگریتم های زیادی ساخته شده ، ولی در عمل خیلی ناتوانن وقتی عدد اول بزرگی در نظر میگیرید، در ادامه میگه اگر به بحث محاسبه توان مادولار علاقه مندید (همین توانی که توی بحث لگاریتم گستته هست) روی square and multiply تحقیق کنید که به صورت بیت به بیت این اعدادو پیدا میکنه و بهنیه هست، که تحقیقش با خودتونه ;)

🔸نکته : از لحاظ ریاضی و اماری این امر اثبات شده هست که اگر شما عدد p رو بزرگ انتخاب کنید، حتی اگر صد ها سال به صورت تصادفی شروع به حدس زدن این عدد بکنید ، شانس شما برای پیدا کردن عدد اول بزرگ تقریبا صفره

حالا میریم سراغ DH :

آلیس (Alice) یه کلید خصوصی داره به اسم "a" و یه کلید عمومی به اسم "A" که کلید عمومی اینطوری بدست میاد : g^a mod p

از طرف دیگه باب (Bob) یه کلید خصوصی داره به اسم "b" و یه کلید عمومی داره به اسم "B" که کلید عمومی رو اینطوری بدست میاره : g^b mod p

اگر کلید عمومی باب رو بدونیم، آلیس میتونه اون کلید مشترک "shared secret" رو با کلید خصوصی خودش، اینطوری بسازه :

B^a mod p

باب هم میتونه کلید عمومی آلیس رو بگیره و با کلید خصوصی خودش، کلید مشترک رو اینطوری بسازه :

A^b mod p

درواقع آلیس امد کلید مشترک رو اینطوری ساخت که کلید خودش رو توان کلید عمومی باب قرار داد و mod p که یه عدد اول بزرگه کرد و برعکس

و نکته اینجاس که این دو طرفس ، یعنی هردو طرفی جواب میده و جفتشون به یک چیز میرسن

دقت کنید که در ریاضی اگر ما دوتا توان داشته باشیم، توان هارو در هم ضرب میکنیم ، یعنی اگر 2 به توان 3 داشتیم و یه توان 4 هم امد وسط ، اول 3 رو ضربدر 4 میکنیم و به رو به توان 12 میرسونیم ، اینجا هم جریان همینه و بجای کلید عمومی هر طرف امده باز شدشو نوشته ، اگر نفهمیدید عکسو حتما بپرسید

هیچکسی در خارج از مکالمه (یعنی بجز آلیس و باب) نمیتونه بفهمه کلید مشترک چی بوده ، چون فقط کلید عمومی رو داره و هیچی نداره !

دوتا مبحث هست، اول Computational Diffie-Hellman Assumption (CDH) :

این به صورت ساده میگه اگر مهاجم کلید عمومی هر دو رو بدونه هیچ غلطی نمیتونه بکنه ! و سختی کار همون حل مسئله لگاریتم گسستست

دوم Decisional Diffie-Hellman Assumption (DDH):

این فرض دوم قوی تر از اولی یا همون CDH هست ، میگه به فرض مهاجم دوتا کلید عمومی هارم داشت، و به فرض از یه z ای هم خبر داشت (که اینجا z میشه یه المنت داخل گروه مون) و این درو میدونست : z mod p با فرض دونستن این z ، نمیتونه بفهمه که این z چیه؟ ایا g^a×b عه ، ایا یه المنت سادست ؟ هیچ جوره نمیتونه بفهمه و نمیتونه تصمیم بگیره (نمیتونه پیدا کنه) که این z دقیقا چیه

انتخاب یک کلید امن خیلی مهمه ،(همون عدد p خودمون) و هر چی بزرگتر باشه بهتره، تا الان بر اساس قدرت کامپیوترا و حملاتی که شده میگن اگر 2048 باشه اون کلید ما، امنیت ما برقراره (عدد اول ما 2048 بیت باشه)، یه سری سایتا هستن مثل :

میان بر اساس استاندارد های مختلف کشور های جهان ، مثل NIST که برای امریکاست ، ANSSI ک برای فرانسس ، BSI که برای المانه و ... یه طول کلیدی پیشنهاد دادن ولی اکثرا روی همون 2048 توافق دارن (یا نزدیک اون)

در گذشته خیلی از کتابخانه ها (library) و برنامه ها میامدن پارامتر های مورد نیاز DH رو خودشون میساختن و hardcode میکردن و متاسفانه خیلی اوقات یا ضعیف بودن یا کاملا اسیب پذیر بودن؛ در 2016 یک نفر کشف کرد که برنامه معروف socat امده DH group خودشو عوض کرده و یه چیزی قرار داده که سال قبلش شکسته شده بوده و اسیب پذیریش سال قبلش معلوم شده بوده !! خیلیا گفتن این سهوی بوده و خیلیام گفتن بکدور گذاشتن از قصد ! حالا شاید بگید استفاده از گروه های DH استاندارد راه چاره بوده ولی نه ! چند ماه بعد این رسوایی socat یک نفر به اسم Antonio Sanso داشته داکیومنت RFC 5114 رو میخونده و فهمیده که توی استاندارد هم مقادیر اسیب پذیر DH group قرار داره 🫤😐

بخاطر همین پروتکل های جدید امدن بیخیال DH قدیمی شدن و رفتن به سمت دفی هلمن منحنی بیزوی Elliptic Curve Diffie-Hellman (ECDH) و یا بجای این کار استاندارد رو بجای RFC 5114 کردن RFC 7919 که که بهترین هم همینه ، برای مثال

توی این RFC جدید امدن از ffdhe2048 نام بردن که از 2048 بیت عدد اول استفاده میکنه و مقادیر حتی بزرگتر؛ یک نمونه عدد p 2048 بیتی :

p = 323170060713110073001535134778251633624880571334 89075174588434139269
80683413621000279205636264016468545855635793533081692882902308057347262
52735547424612457410262025279165729728627063003252634282131457669314142
23654220941111348629991657478268034230553086349050635557712219187890332
72956969612974385624174123623722519734640269185579776797682301462539793
30580152268587307611975324364674758554607150438968449403661304976978128
54295958659597567051283852132784468522925504568272879113720098931873959
14337417583782600027803497319855206060753323412260325468408812003110590
7484281003994966956119696956248629032338072839127039

و generatorهم همیشه اینه : g = 2 چرا ؟ چون کامپیوتر براش خیلی راحته ضربدر 2 بکنه چون این توی shift left تعبیه شده

(این دلیل بخاطر معماری پردازنده هاست و زبان اسمبلی، یکم پیچیدس ولی به صورت ساده وقتی توی کامپیوتر عمل shift left انجام میشه ، کامپیوتر ضربدر 2 میکنه ، و shift right کامپیوتر تقسیم بر 2 میکنه)

همچنین هم کلید عمومی هم کلید خصوصی 2048 بیت باید باشن، چرا ؟ چون سایز گروه یا همون order ما اینطوری تعریف میشه : q = (p – 1)/2 و چون در دنیای واقعی این ها خیلی بزرگ هستن (اگر از فصل 4 یادتون باشه ما برای رمزنگاری متقارن 128 بیت استفاده میکردیم) ما باید بریم سراغ یه روشی که همین امنیت رو داشته باشه ولی با کلید کمتر ، چه روشی؟ منحنی بیزوی یا Elliptic Curve Diffie-Hellman (ECDH)

🔸5.3 The Elliptic Curve Diffie-Hellman (ECDH) key exchange

امدن گفتن خب ما که فقط نیاز نیست multiplicative groups استفاده کنیم ، میتونیم از elliptic curves groups استفاده کنیم ، سایز کلیدش خیلی کوچیک و خوبیه و امنیتی که کلید 2048 بیتی توی معماری معمولی DH داشت رو این با حدود 256 بیت عرضه میکنه :) تقریبا 10 برابر کوچیکتر

🔸5.3.1 What’s an elliptic curve?

قبل ادامه این لینکو از سری مقدماتی بخونید که با محنی های بیضوی بیشتر اشنا بشید

بحث ساخت group در منحنی بیضوی بحث هم صادقه که یعنی ما همون عملیات جمع یا افزونگی یا addition رو که توی حالت معمولی داشتیم رو هم توی منحنی های بیضوی میتونیم داشته باشیم و این addition باید اون 4 تا ویژگی ای که گفتم رو داشته باشه : closure, associativity, identity, and inverse

یادتونه توی DH Group ای که تا الان داشتیم از multiplicative groups استفاده میکردیم؟ اینجا توی منحنی بیضوی از additive notation استفاده میکنیم (به زبان ساده اونجا ضرب و اینا داشتیم ولی اینجا جمع داریم و کارو برای ما انجام میده)

قبل ادامه بگم که این موردو من توی سری مقدماتی توضیح دادم، عملیات همون addition هست و اینجا ساده ازش عبور میکنیم !

چطوری دوتا نقطه رو بهم اضافه میکنیم ؟ میخوایم نقطه P و Q رو بهم وصل کنیم، یه خط میکشیم که از جفتش عبور کنه، این خط باید یه منحنی مارو در یک نقطه قطع کنه، حالا اونجا یه خط عمودی رسم میکنیم و این خط عمودی در اونور محور x ها یه جاییو قطعه میکنه و نقطه جدیدی به نام P+Q تشکیل میشه که متشکل از P و Q هست

اقای وونگ میگه دوتا استثنا هم داریم :

1 - Adding a Point to Itself (P+PP + PP+P) :

اگر یه نقطرو با خودش جمع بزنی ، یعنی یه خط مماس یا tangent line بکشی

2- Addition Resulting in the Point at Infinity :

اگر یه نقطه رو مثلP در شکل سمت راستی 5.10 بخوای با خودش جمع بزنی، چون هیچ جایی نداره بره پس درواقع یه خط کاملا عمودی رو ما داریم ، درواقع از لحاظ علمی این نقطه با منفی خودش جمع شده :

P+(−P)=O

و بهش میگیم نقطه در بینهایت یا point at infinity که دقیقا مثل identity element ما عمل میکنه؛ دقت کنید که به نقطه در بینهایت میگیم O

این نقطه در بینهایت یا point at infinity O ما همون حکم identity element مارو داره، مشابه 0 در عملیات جمع :

O+O=O and P+O=P

یعنی اگر ما یه نقطه رو بعلاوه این نقطه در بینهایت کنیم، هیچ تاثیری روی اون نقطه نداره !

واقعا اگر با این حجم از مطالب بر نمیتابید مشکلی نداره 😂 سری مقدماتی رو حتما بخونید و این هارو هم در کنارش بخونید و هر جا مشکلی بود بپرسید ، واقعا از طرز تدریس اقای وونگ راضی نیستم ! اصلا !!!

تا اینجا فهمیدیم که برای استفاده از ورژن منحنی بیضوی دفی هلمن باید یه عبارت ریاضی داشت مثل y2=x3+ax+b که یه سری نقاط بهمون بده ، بتونیم نقاط رو بهم اضافه کنیم ، و یه نقطه در بینهایت

🔸 ECC Over Finite Fields :

در رمزنگاری منحنی بیضوی ، یک منحنی بر روی اعداد واقعی تعریف نمیشه بلکه روی یک میدان محدود (finite field) تعریف میشه، مختصات نقاط روی منحنی اعدادی هستند که مادول یک عدد اول بزرگ هستند ؛ که این یعنی بجای کار با منحنی های پیوسته ، که در شکل سمت چپ از شکل 5.11 نشو نداده شده، با نقاط گسسته در سمت راست شکل 5.11 کار میکنیم

یعنی منحنی y2=x3+ax+b میشه y2=x3 + ax + b mod p که مختصات با p محدود میشوند

🔸 Discrete Logarithm Problem (ECDLP) :

مثل دفی هلمن معمولی که ما مسئله لگاریتم گسسته رو داشتیم، اینجا هم اونو داریم ، ولی ورژن منحنی بیضوی لگاریتم گسسته !

ما با یه نقطه شروع که G هست شروع میکنیم (یه نقطه شناخته شدس توی منحنی ها)

بعد میاییم این G رو چندین بار با خودش جمع میکنیم (scalar multiplication) و یه نقطه جدید بدست میاد

مثلا G رو میاییم x بار با خودش جمع میکنیم و Pبدست میاد

حالا مسئله لاگریتم گسسته منحنی بیضوی یا Elliptic Curve Discrete Logarithm Problem (ECDLP اینه که این x رو پیدا کنید، و فرض هم این هست که P و G رو دارید ! و خب خیلی خسته :))

نکته : بالاتر یه تیکه گفتم Scalar Multiplication و منظور اینه که ما بیاییم نقطه G رو به خودش اضافه کنیم (جمع G با G با G تا ...)

ریاضیش این شکلیه :

P=xG=G+G+⋯+G (x times)

توی پروتوکل های رمزنگاری مثل دفی هلمن منحنی بیضوی، مسئله لگاریتم گسسته امنیت پروتوکل رو تضمین میکنه ، یعنی اگر یه نفربدونه نقطه G و P که نتیجه G هست، خیلی سخته که بتونه x که تعداد دفعات ضرب بوده رو پیدا کنه

🔸5.3.2 How does the Elliptic Curve Diffie-Hellman (ECDH) key exchange work?

برای مرور : تمامی کسایی که مشارکت میکنن باید یه معادله رو انتخاب کنن (همگی روی یک معادله به توافق برسن) و یه میدان محدود (modulo a large prime number p) و یه generator یا G و یه نقطه شروع روی منحنی ، بعد باید هر مشارکت کننده که مثال همیشگیون آلیس و باب بود، یه عدد تصادفی بسازه ، مثلا آلیس a میسازه و باب b ، این میشه کلید خصوصیشون ، حالا هر مشارکت کننده میاد کلید عمومیش اینبار متفاوت میسازه ، چطوری؟ با استفاده از scalar multiplication که بالاتر خوندیم :

A=[a]G and B=[b]G

اینجا [a]G یعنی a دفعه بیاییم G رو با خودش ضرب کنیم و به یه نقطه جدید در منحنی برسیم

حالا آلیس و باب برای تبادل کلید اینطوری عمل میکنن :

کلید عمومی آلیس : A ، کلید عمومی باب : B

Alice : [a]B=[a][b]G

Bob : [b]A=[b][a]G

هردو به یه کلید مشترک میرسن (به یه نقطه مشترک روی منحنی) که اون [ab]G هست و مجدد تکرار میکنم، چرا یه مهاجم نمیتونه بفهمه کلید مشترک چی بوده؟ با اینکه به کلید های عمومی دسترسی داره؟ بخاطر مسئله لگاریم گستته منحنی بیضوی یا ECDLP !

مقایسه دفی هلمن معمولی با دفی هلمن منحنی بیضوی :

همونطور که توی عکس بالا میبینید، دفی هلمن معمولی از multiplicative group modulo a prime number استفاده کرده ، عملیات هاییم که داشته ضرب و توان مادولار یا modular exponentiation بودن ولی دفی هلمن منحنی بیضوی با گروه های تجمعی روی منحنی کار میکنه (additive group on elliptic curves) که عملیاتی که ازش استفاده میکنه تجمع نقاط با همه ، از scalar multiplication هم استفاده میکنه و از point at infinity هم به عنوان identity element است استفاده میکنه

تفاوت مسئله لگاریتم گسسته توی جفتشون

🔸مضایای امنیتی :

• ورژن منحنی بیضوی دفی هلمن یا همون ECDH امنیتی رو برای ما فراهم میکنه که همون ورژن معمولی DH فراهم میکردم ولی سایز کلی منحنی بیضوی به مراتب کمتره و این به سرعت این primitive اضافه میکنه و در دنیای واقعی هم ازش استفاده بیشتری میشه
• گروه های منحنی بیضوی مقاوم ترن نسبت به یه سری حملات مثل index calculus یا number field sieve attacks به نسبت گروه های قدیمی دفی هلمن

🔸5.3.3 The standards for Elliptic Curve Diffie-Hellman

در زمینه استاندارد های الگریتم های منحنی بیضوی ، ما NIST FIPS 186-4, “Digital Signature Standard,” رو داریم که 15 تا استاندارد داره ولی اینجا ما دوتاشونو معرفی میکنیم : P-256 و Curve25519

1. P-256 :

منحنی P-256 که معروف ترین و پر استفاده ترین در سطح اینترنت هست، یه اسم دیگشم secp256r1 هست ، حالا معادله ای که داره چیه ؟

y^2=x^3+ax+b mod p

که a اینجا -3 هست و b یه عدد بزرگ و p هم یه عدد بزرگ اول ، و ثابت هم هستن توی همه معادله های این منحنی ، این اعداد طوری انتخاب شدن که با اطمینان بالا ما بگیم منحنی ای که داریم امنه

منحنی ما یه n داره (بهش prime order میگن) که تعداد نقاط منحصر به فردیه که روی منحنی هست (از جمله نقطه point at infinity)، یه نقطه پایه یا شروع یا base point داریم و اعدادی که برای نقاط پایه در نظر گرفته میشه مختصات خاصی دارند

امنیت این P-256 ما 128 بیته و اگر امنیت بیشتری کسی بخواد باید بره سراغ P-521 که 256 بیت امنیت داره !ولی زیاده رویه دیگه ! نیاز نیست !

چون برای ساخت P-256 از یه عدد ثابتی استفاده میشه و همه هم اینو میدونن ، یک سری مناظرات و بحث ها هست که ممکنه این یه backdoor باشه و اینا ولی سند علمی ای اینو اثبات نکرده تاحالا و متخصص هام نگفتن چرا این اعدادو انتخاب کردن !!

2.Curve25519 :

از طرفی Curve25519 هم یک نوع منحنی دیگس و استانداردش RFC 7748 هست و 128 بیتم امنیت داره و دقیقا مثل P-256 ولی ساختارشون فرق داره یه منحنی دیگه هم هست به اسم Curve448 که از همین خانوادس ولی امنیت 224 بیتی میده

معادله ریاضی Curve25519 متفاوته نسبت به P-256 و اسمش منحنی مونتگومری هست :

y^2=x^3+486662x^2+x mod p

و طبق معمول p عدد اوله و مقدارشم نزدیک به اینه : 255^2 و منحی ایه که امنیت خوبی داره (ساختارش این شکلیه)

و مثل P-256 که گفتیم، Curve25519 هم یه prime order داره که نمایانگر تعداد نقاط روی منحنیه و نقطه شروع هم در اینجا با مجموعه ای از مختصات، مشابه P-256 مشخص می شه و نقطه شروع استاندارد برای عملیات رمزنگاریه

حالا امدن ECDH (Elliptic-Curve Diffie-Hellman) رو با Curve25519 ترکیب کردن و بچشون شده X25519😂 یک PRIMITIVE معتبر برای تبادل کلید و بسیار هم مورد اعتماد و پر استفاده !

🔸5.4 Small subgroup attacks and other security considerations

نویسنده میگه که کلا برید سراغ ECDH واز DH معمولی استفاده نکنید چون امنیت اون بهتره و سرعتش بیشتره و ... و مهم تر از حمله حملات کمتری برای نسخه منحنی بیضوی کشف شده، و اگر از DH استفاده کردید مطمئن باشید که از استاندارد های قدیمی و ضعیف مثل RFC 5114 استفاده نمیکنید !

🔸 استفاده از safe prime :

اگرم خواستید از DH استفاده کنید باید از اعداد اول امن یا safe prime استفاده کنید که فرمول safe prime اینه :

p = 2q + 1

در اینجا q عدد اوله و p هم عدد اوله !!

حالا دلیل اینکه این safe prime هارو باید ما استفاده کنیم چیه؟ اگر ما از safe prime استفاده کنیم، دوتا ساب گروپ یا زیر گروه خواهیم داشت : اولین زیر گروه خیلی کوچیکه وسایزش 2 هست و توسط -1 ساخته شده و دومی زیر گروه بزرگه (سایز q) و این ساب گروه ها خیلــــــــــــــــــــــــــــــــــــی مهمن چون جلوگیری میکنن از یه سری حملات به اسم small subgroup attack (بعدا بیشتر بهش میپردازیم)

حالا چرا safe prime ها خوبن ؟ دوتا دلیل داره :

1- The order of a multiplicative group modulo a prime p is p−1

2- The order of a group’s subgroups are the factors of the group’s order

چون p -1 =2q پس زیرگروه ها در دفی هلمن میتونن یا سایز 2 داشته باشن که خیلی کوچیکه یا سایز q که خیلی بزرگه و ریسک حملات مبتنی بر زیرگروه های کوچیک رو از بین ببرن

(این یه تیکشو فقط من زیاد باز نکردم و دوست داشتید از کتاب بخونید)

🔸منظور از Small Subgroup Attack چیه ؟

این حمله وقتی اتفاق می افته که مهاجم کلید های عمومی نامعتبر رو در فرایند تبادل کلید دفی هلمن وارد کنه (توی این فرایند تبادل بیاد و کلید عمومی رندوم و نامعتبر درج کنه) این کلید های نامعتبر باعث میشه که در فرایند دفی هلمن ما ، کلید های خصوصی نشت پیدا کنن (یه قسمت هایی از کلید های خصوصی) و اگر مهاجم این حمله رو زیاد انجام بده ، به مرور زمان قسمت های بیشتری از کلید خصوصی نشت پیدا میکنه و میتونه به کلید خصوصی پی ببره

از لحاظ ریاضیش حمله اینطوریه که مهاجم میاد کلید عمومی ای مثل -1 رو میفرسته توی فرایند دفی هلمن، که یه قسمت از زیرگروه ما هست، و اگر قربانی ندونه که مهاجم این وسط در کاره و فرض کنه مخاطب اصلیشه و بیاد باهاش تبادل کلید انجام بده ، چون قربانی کلید عمومی شو درگیر کرده ، پس کلید مشترک عمومی یا 1 میشه یا -1 (بسته به اینکه مهاجم کلید خصوصیش مثبت زوج باشه یا فرد) و این یه سری بیت رو از کلید خصوصی قربانی لیک میکنه و منتشر میکنه (نشست پیدا میکنه)

پس قبل تبادل کلید حتما مطمئن بشید که فردی که داره کلید عمومیشو به شما میده همونیه که میگه ! و در سال 2016 محققین فهمیدن که دفی هلمن اصلا توی این زمینه خوب نیست ، پس اقای دیوید وونگ میگه

🔸فرایند اعتبار سنجی کلید عمومی :

حتما مطمئن بشید کلید عمومی معتبره ، چطوریه ؟
فرمول کلید عمومی این بود :

Public key=g^private key mod p

حالا یه مثال :

Public key=5^6 mod 23=15625 mod 23=2

اگر بخای چک کنید که کلید عمومی (اینجا همون 2) قسمتی از زیر گروه هست یا نه میایی میگی n یا prime order چنده؟ p-1 یا 23-1 = 22

کلید عمومی رو به توان این prime order میرسونی و مادولارش میکنی با 23 که p عه

2^22 mod 23

اگر محاسباتو انجام بدی :

4194304 mod 23=1

به identity element میرسی ، یعنی کلید عمومی یا همون 2 ای ک ما تستش کردیم معتبره و اگر نتیجه یک نبود یعنی احتمالا مهاجمی در کاره و فصد داره small subgroup attack بزنه

🔸منظور از حمله invalid curve attack چیه ؟

در منحنی های بیضوی میشه از prime-order groups هم استفاده کرد که هیچ زیرگروهی نداره و از لحاظ تئوری امکان اجرای حمله small subgroup attacks براش نیست، ولی توی سال 2000 محققین حمله ای تحت عنوان invalid curve attack کشف کردن که مختص همین prime-order groups هست

در این حمله مهاجم میاد و در زمان تبادل کلید، از یه منحنی تقلبی استفاده میکنه و سیستم (جایی که تبادل دفی هلمن رو اجرا میکنه) رو گول میزنه و ازش اطلاعات میشکه بیرون ، یعنی سیستم نمیتونی بفهمه که این منحنی ای که بدستش رسیده درسته یا نه

فرض کنید ما یه منحنی داریم :

y^2=x^3+ax+b1​

و هر دونفر که توی این تبادل کلید میخوان شرکت کنن توافق کردن که از این معادله استفاده کنن، مهاجم که اینو میدونه و میاد یه منحنی دیگه میده ، این منحنی مهاجم خیلی مثل اصلیه ولی تفاوت ریزی داره :(b2)

y^2=x^3+ax+b2

مهاجم میاد و یه نقطه از این منحنی جدید انتخاب میکنه و میفرسته به سیستم به عنوان کلیدی که حق داشته انتخاب کنه

وقتی سیستم این نقطه رو دریافت میکنه ، نمیفهمه که ایا این نقطه متعلق به معادله اصلی بوده یا نه ! و کورکورانه تبادل کلید رو انجام میده

حالا دلیل اینکه این حمله هست چیه؟ چون منحنی های بیضوی زیرگروه هایی دارن که نقاط کمتری قبول میکنه نسبت به کل منحنی ! یعنی اگر نقطه ای که مهاجم انتخاب کرده متعلق باشه به یه زیرگروه کوچیکی از اون منحنی مهاجم ، وقتی تبادل کلید صورت میگیره ، کلید مشترکی که تولید میشه متعلق به یه زیر گروه کوچیکه ، یعنی چی؟ یعنی فرض کنید منحنی اصلی ما گروهی داره متشکل از 100 نقطه ولی مهاجم نقطه ای انتخاب میکنه از منحنی خودش که زیرگروه هاش سایز 5 تایی دارن !
مثال ساده : فرض کنید آلیس و باب میخوان تبادل کلید کنن ، باب نقطه یا P رو میفرسته به آلیس و آلیسم با کلید خصوصیش محاسبه میکنه اون کلید مشترکو :

Shared secret=kA​×P

اگر این وسط باب مهاجم ما باشه و Active MITM رخ بده ، بیاد یه منحنی متفاوت ولی مشابه انتخاب کنه با سایز زیرگروه کوچیک مثل 5 ، این اتفاق می افته :

Shared secret=kA​×Q

اینبار آلیس اون نقطه رو استفاده میکنه و چون سایز زیرگروه 5 تاست ، پس باب وقتی کلید به دستش رسید کافیه 5 بار حمله brute force رو انجام بده تا بفهمه کلید خصوصی آلیس چی بوده 😱

یعنی درواقع یه جورایی دوباره همون حملات small subgroup attacks رخ میده ولی متفاوته ، از چه لحاظ؟

• توی حمله small subgroup مهاجم میاد نقطه پیدا میکنه توی منحنی اصلی یا همون منحنی واقعی ولی در invalid curve مهاجم میاد یه از یه منحنی دیگه نقطه پیدا میکنه
• از طرفی توی حمله small subgroup مهاجم میاد از ضعف زیرگروه ها استفاده میکنه (ولی روی همون منحنی واقعی و اصلی) ولی در invalid curve مهاجم میاد از ضعف یا عدم بررسی نقطه روی منحنی تقلبی استفاده میکنه
• از دیدگاه دیگه حمله small subgroup میاد group order رو هدف قرار میده ولی Invalid Curve میاد curve validation رو هدف قرار میده !

برای جلوگیری از این حمله باید کلید عمومی اعتبار سنجی بشه ، اقای وونگ میگه حتما از X25519 استفاده کنید

اگر کلید عمومیو چک نکنید، حتی ما با X25519 هم به مشکل میخوریم ! و مهاجم میتونه خیلی کارا بکنه :(( یکی از چیز هایی که اقای وونگ میگه حتما حواستون باید بهش باشه اینه که چک کنید کلید مشترکی که دستتون همش 0 نباشه !

🔸نکته : Curve25519 درسته خیلی امن و خوبه ولی از prime order group استفاده نمیکنه و از این رو دوتا زیرگروه داره ، یه کوچیک که 8 تاسن و یه بزرگ ، حواستون باشه به این موارد قبل استفاده ، چون Curve25519 هم کلید عمومی رو چم نمیکنه !

واسه اینکه مشکل عدم استفاده از prime order group مال Curve25519 رو حل کنن ، امدن یه چیز جدید ساختن به اسم Ristretto که یه لایه انکودینگ اضافه تره برای Curve25519 و امن ترش میکنه و جور اون قسمت prime order groups رو میکشه

فصل پنجمم تموم شد، فصل بعدی سراغ مبحث رمزنگاری نامتقارن و ترکیبی میریم :)

امید وارم براتون مفید بوده باشه

منتظر سوالات، انتقاد و پیشنهاداتتون هستم

یاعلی ;)