المكتبة العربية لعلوم الحاسوب
تحديات كريبتوبالز › المجموعة 5 5 / 8 السابق التالي

المجموعة 5

هذه أول مجموعة من تحديات التشفير النظري-العددي (number-theoretic cryptography)، وهي أيضًا تغطيتنا لمصادقة الرسائل.

هذه المجموعة أصعب بكثير من المجموعة السابقة. المفاهيم جديدة، والهجمات لا تشبه هجمات المجموعات السابقة، و... رياضيات.

في المقابل، هجومنا التحليلي التشفيري المفضل على الإطلاق موجود في هذه المجموعة (ستراه قريبًا). نحن راضون عن هذه المجموعة. لا تضعف هنا. لقد أوشكت على الانتهاء!

33. تنفيذ تبادل مفاتيح ديفي-هيلمان (Diffie-Hellman)

بالنسبة لواحد من أهم الخوارزميات في التشفير، لم يكن هذا التمرين ليصبح أسهل كثيرًا.

اضبط المتغير "p" على 37 و"g" على 5. هذه الخوارزمية سهلة لدرجة أنني لن أشرحها حتى. افعل ما أفعله فقط.

ولّد "a"، وهو عدد عشوائي بترديد 37. الآن ولّد "A"، وهو "g" مرفوعًا إلى القوة "a" بترديد 37 --- A = (g**a) % p.

افعل الشيء نفسه مع "b" و"B".

"A" و"B" مفتاحان عامان. ولّد مفتاح جلسة بهما؛ اضبط "s" على "B" مرفوعًا إلى القوة "a" بترديد 37 --- s = (B**a) % p.

افعل الشيء نفسه مع A**b، وتحقق من حصولك على "s" نفسه.

لتحويل "s" إلى مفتاح، يمكنك ببساطة تجزئته (hash) لإنشاء 128 بتًا من المادة المفتاحية (أو تجزئته بـ SHA256 لإنشاء مفتاح للتشفير ومفتاح لرمز مصادقة MAC).

حسنًا، كان ذلك ممتعًا، والآن أعد التمرين بأعداد ضخمة كما في العالم الحقيقي. إليك معطيات يحبها NIST:

p:
ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024
e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd
3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec
6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f
24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361
c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552
bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff
fffffffffffff
 
g: 2

هذا سهل جدًا في Python أو Ruby أو لغات عالية المستوى أخرى ترقّي الأعداد الثابتة تلقائيًا إلى أعداد ضخمة، لكنه ليس «صعبًا» في أي لغة.

لاحظ أنك ستحتاج إلى كتابة modexp خاص بك (هذه رياضيات سبورة، لا تُرعب نفسك)، لأنك ستفجّر مكتبة الأعداد الضخمة برفع "a" إلى قوة عدد بطول 1024 بتًا. يمكنك إيجاد روتينات modexp على Rosetta Code لمعظم اللغات.

34. تنفيذ هجوم تثبيت المفتاح بالوسيط على تبادل مفاتيح ديفي-هيلمان مع حقن المعطيات

استخدم الشيفرة التي أعددتها للتو لبناء بروتوكول وروبوت «صدى». لست ملزمًا فعلًا بتنفيذ الجزء الشبكي من هذا إن لم ترغب؛ حاكِه فقط. البروتوكول هو:

A->B أرسل "p" و"g" و"A" B->A أرسل "B" A->B أرسل AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv B->A أرسل AES-CBC(SHA1(s)[0:16], iv=random(16), رسالة A) + iv

(بعبارة أخرى، اشتق مفتاح AES من DH باستخدام SHA1، واستخدمه في الاتجاهين، ونفّذ CBC بمتجهات تهيئة عشوائية تُلحق بالرسالة أو تُضاف في مقدمتها).

الآن نفّذ هجوم الوسيط (MITM) التالي:

A->M أرسل "p" و"g" و"A" M->B أرسل "p" و"g" و"p" B->M أرسل "B" M->A أرسل "p" A->M أرسل AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv M->B مرّر ذلك إلى B B->M أرسل AES-CBC(SHA1(s)[0:16], iv=random(16), رسالة A) + iv M->A مرّر ذلك إلى A

ينبغي أن يكون M قادرًا على فك تشفير الرسائل. لقد استُبدلت "A" و"B" في البروتوكول --- المفتاحان العامان على الشبكة --- بـ "p". أجرِ رياضيات DH على هذا سريعًا لترى ما يفعله ذلك بقابلية التنبؤ بالمفتاح.

فك تشفير الرسائل من موقع M أثناء مرورها.

لاحظ أنك لست ملزمًا فعليًا بحقن معطيات مزيفة ليعمل هذا الهجوم؛ يمكنك ببساطة توليد Ma وMA وMb وMB كمعطيات DH صالحة لتنفيذ هجوم وسيط عام. لكن نفّذ هجوم حقن المعطيات؛ فسيظهر مجددًا.

35. تنفيذ تبادل مفاتيح ديفي-هيلمان مع مجموعات متفاوض عليها، وكسره بمعطيات "g" خبيثة

A->B أرسل "p" و"g" B->A أرسل ACK A->B أرسل "A" B->A أرسل "B" A->B أرسل AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv B->A أرسل AES-CBC(SHA1(s)[0:16], iv=random(16), رسالة A) + iv

نفّذ هجوم الوسيط مرة أخرى، لكن العب بـ "g". ماذا يحدث مع:

    g = 1
    g = p
    g = p - 1

اكتب هجومًا لكل حالة.

متى يحدث هذا في الواقع؟

بصراحة، ليس بهذا التكرار في الأنظمة الواقعية. إن كنت قادرًا على العبث بـ "g"، فالأرجح أنك قادر على العبث بشيء أسوأ. معظم الأنظمة تتفق مسبقًا على مجموعة DH ساكنة. لكن التركيب نفسه موجود في تبادل مفاتيح ديفي-هيلمان على المنحنيات الإهليلجية (Elliptic Curve Diffie-Hellman)، وهناك يصبح أكثر صلة.

36. تنفيذ كلمة المرور الآمنة عن بُعد (SRP)

لفهم SRP، انظر إلى كيفية توليدك مفتاح AES من DH؛ الآن، لاحظ فقط أنك تستطيع تنفيذ العملية «المعاكسة» وتوليد معطى رقمي من تجزئة. ثم:

استبدل A وB بـ C وS (العميل والخادم)

C وS يتفقان على N=[NIST Prime] وg=2 وk=3 وI (البريد الإلكتروني) وP (كلمة المرور) S

  1. ولّد الملح كعدد صحيح عشوائي
  2. ولّد السلسلة xH=SHA256(salt|password)
  3. حوّل xH إلى العدد الصحيح x بطريقة ما (ضع 0x أمام hexdigest)
  4. ولّد v=g**x % N
  5. احفظ كل شيء عدا x وxH

C->S أرسل I، A=ga % N (على طريقة ديفي-هيلمان) S->C أرسل salt، B=kv + gb % N S، C احسب السلسلة uH = SHA256(A|B)، u = العدد الصحيح لـ uH C

  1. ولّد السلسلة xH=SHA256(salt|password)
  2. حوّل xH إلى العدد الصحيح x بطريقة ما (ضع 0x أمام hexdigest)
  3. ولّد S = (B - k * gx)(a + u * x) % N
  4. ولّد K = SHA256(S)

S

  1. ولّد S = (A * v**u) ** b % N
  2. ولّد K = SHA256(S)

C->S أرسل HMAC-SHA256(K, salt) S->C أرسل "OK" إذا تحققت صحة HMAC-SHA256(K, salt)

ستحتاج إلى فعل هذا في REPL من نوع ما؛ قد يستغرق بضع محاولات.

لا يهم كيف تنتقل من العدد الصحيح إلى السلسلة أو من السلسلة إلى العدد الصحيح (حيث تدخل الأشياء إلى SHA256 أو تخرج منه) ما دمتَ تفعل ذلك باتساق. اختبرت باستخدام التمثيل العشري ASCII للأعداد الصحيحة كمدخل إلى SHA256، وبتحويل hexdigest إلى عدد صحيح عند معالجة مخرجاته.

هذا أساسًا ديفي-هيلمان مع تعديل بخلط كلمة المرور في المفتاحين العامين. ويتخذ الخادم خطوة إضافية لتجنب تخزين ما يكافئ كلمة المرور وقابل للكسر بسهولة.

37. كسر SRP بمفتاح صفري

شغّل SRP خاصتك في إعداد فعلي للعميل والخادم. «سجّل الدخول» بكلمة مرور صالحة باستخدام البروتوكول.

الآن سجّل الدخول دون كلمة مرورك بجعل العميل يرسل 0 كقيمة "A" الخاصة به. ماذا يفعل ذلك بقيمة "S" التي يحسبها الطرفان؟

الآن سجّل الدخول دون كلمة مرورك بجعل العميل يرسل N وN*2 وما إلى ذلك.

جائزة أفضل مساهم تحليلي تشفيري

علّمنا Trevor Perrin وNate Lawson هذا الهجوم قبل 7 سنوات. إنه ممتاز. هجمات DH صعبة «تشغيليًا». لكن هذا الهجوم يستخدم المفاهيم نفسها، ويفضى إلى تجاوز المصادقة. كل تنفيذ لـ SRP رأيناه تقريبًا فيه هذا العيب؛ إن رأيت تنفيذًا جديدًا، فاذهب وابحث عن هذا الخطأ.

38. هجوم قاموس دون اتصال على SRP المبسط

S

x = SHA256(salt|password)
    v = g**x % n

C->S

I, A = g**a % n

S->C

salt, B = g**b % n, u = 128 bit random number

C

x = SHA256(salt|password)
    S = B**(a + ux) % n
    K = SHA256(S)

S

S = (A * v ** u)**b % n
    K = SHA256(S)

C->S أرسل HMAC-SHA256(K, salt) S->C أرسل "OK" إذا تحققت صحة HMAC-SHA256(K, salt)

لاحظ أن معطى الخادم "B" في هذا البروتوكول لا يعتمد على كلمة المرور (إنه مجرد مفتاح عام لديفي-هيلمان).

تأكد من أن البروتوكول يعمل بكلمة مرور صالحة.

الآن، شغّل البروتوكول كمهاجم وسيط: انتحل شخصية الخادم واستخدم قيمًا اعتباطية لـ b وB وu وsalt.

اكسر كلمة المرور من HMAC-SHA256(K, salt) الخاص بـ A.

39. تنفيذ RSA

هناك أمران مزعجان في تنفيذ RSA. كلاهما يتعلق بتوليد المفاتيح؛ أما التشفير وفك التشفير الفعليان في RSA فبديهيان.

أولًا، تحتاج إلى توليد أعداد أولية عشوائية. لا يمكنك ببساطة الاتفاق على عدد أولي مسبقًا، كما تفعل في DH. يمكنك كتابة هذه الخوارزمية بنفسك، لكنني أغش فقط وأستخدم مكتبة BN من OpenSSL لإنجاز العمل.

الأمر الثاني أنك تحتاج إلى عملية «invmod» (المعكوس الضربي)، وهي ليست عملية مدمجة في لغتك. الخوارزمية سطران فقط، لكنني أخسر ساعة دائمًا لإتقان عملها.

أنصحك بألا تتكبد عناء توليد الأعداد الأولية، لكن خذ وقتك في إتقان خوارزمية EGCD وinvmod الخاصة بك.

الآن:

  • ولّد عددين أوليين عشوائيين. سنستخدم أعدادًا صغيرة للبداية، فيمكنك اختيارهما من جدول أعداد أولية. سمِّهما "p" و"q".
  • ليكن n هو p * q. رياضيات RSA لديك بترديد n.
  • ليكن et هو (p-1)*(q-1) («دالة أويلر» totient). تحتاج هذه القيمة لتوليد المفتاح فقط.
  • ليكن e هو 3.
  • احسب d = invmod(e, et). قيمة invmod(17, 3120) هي 2753.
  • مفتاحك العام هو [e, n]. ومفتاحك الخاص هو [d, n].
  • للتشفير: c = me%n. ولفك التشفير: m = cd%n
  • اختبر هذا بعدد، مثل "42".
  • أعد التمرين بأعداد أولية ضخمة (أبقِ e=3).

أخيرًا، لتشفير سلسلة، افعل شيئًا مبتذلًا، مثل تحويل السلسلة إلى ست عشري ووضع "0x" في مقدمتها لتحويلها إلى عدد. لا تبالي الرياضيات بمدى غباء الطريقة التي تغذّيها السلاسل.

40. تنفيذ هجوم البث E=3 على RSA

افترض أنك مبرمج JavaScript. أي أنك تستخدم RSA بدائيًا مكتوبًا يدويًا للتشفير دون حشو.

افترض أنه يمكن إجبارك على تشفير النص الصريح نفسه ثلاث مرات، تحت ثلاثة مفاتيح عامة مختلفة. يمكن ذلك؛ لقد حدث.

عندها يستطيع المهاجم فك تشفير رسالتك بسهولة، عبر:

  1. التقاط أي ثلاثة من النصوص المشفَّرة ومفاتيحها العامة المقابلة
  2. استخدام نظرية الباقي الصيني (CRT) لإيجاد العدد الذي تمثله النصوص المشفَّرة الثلاثة (وهي بواقٍ بترديد مفاتيحها العامة)
  3. أخذ الجذر التكعيبي للعدد الناتج

تقول نظرية الباقي الصيني إنه يمكنك أخذ أي عدد وتمثيله كتركيبة من سلسلة بواقٍ بالنسبة إلى سلسلة من المعايير. في حالة البواقي الثلاث، لديك:

result =
  (c_0 * m_s_0 * invmod(m_s_0, n_0)) +
  (c_1 * m_s_1 * invmod(m_s_1, n_1)) +
  (c_2 * m_s_2 * invmod(m_s_2, n_2)) mod N_012

حيث:

 c_0, c_1, c_2 are the three respective residues mod
 n_0, n_1, n_2

 m_s_n (for n in 0, 1, 2) are the product of the moduli
 EXCEPT n_n --- ie, m_s_1 is n_0 * n_2

 N_012 is the product of all three moduli

لفك تشفير RSA باستخدام جذر تكعيبي بسيط، اترك عملية الترديد النهائية؛ خذ النتيجة الخام المتراكمة فقط وخُذ جذرها التكعيبي.

السابق المجموعة 4 التالي المجموعة 6