المجموعة 6

هذه آخر مجموعة من تحديات التشفير الأصلية لدينا.

تغطي هذه المجموعة حصريًا التشفير النظري-العددي، وتحديدًا RSA وDSA.

هذه المجموعة صعبة. المفاهيم جديدة مجددًا. تتضمن الهجمات بعض الرياضيات --- لكن لا شيء لم تتعلمه في الصف التاسع --- وقدرًا كبيرًا من البرمجة.

لكنها تستحق العناء. اثنان من هذه الهجمات تحديدًا من أكثر الهجمات قيمة في التشفير الواقعي.

41. تنفيذ أوراكل استعادة الرسائل غير المحشوّة

يقول Nate Lawson إنه ينبغي أن نتوقف عن تسميته «حشو RSA» ونبدأ بتسميته «تدريع RSA». وإليك السبب.

تخيّل تطبيق ويب، مرة أخرى بتشفير JavaScript، يستقبل رسائل مشفَّرة بـ RSA وهي (مجددًا: JavaScript) غير محشوّة قبل التشفير إطلاقًا.

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

{
  time: 1356304276,
  social: '555-55-5555',
}

تودّ التقاط رسائل الآخرين واستخدام الخادم لفك تشفيرها. لكن عندما تحاول، يأخذ الخادم تجزئة النص المشفَّر ويستخدمها لرفض الطلب. وأي بتّة تقلبها في النص المشفَّر تُفسد فك التشفير إفسادًا لا رجعة فيه.

وتبيّن أن هذا قابل للكسر بسهولة:

التقط النص المشفَّر C وليكن N وE هما المعيار والأس العامين على التوالي وليكن S عددًا عشوائيًا > 1 بترديد N. لا يهم أي عدد. الآن:

C' = ((S**E mod N) C) mod N

أرسل C'، الذي يبدو مختلفًا تمامًا عن C، إلى الخادم، واستعد P'، الذي يبدو مختلفًا تمامًا عن P. الآن:

          P'
    P = -----  mod N
          S

عفوًا!

نفّذ ذلك الهجوم.

احذر القسمة في الزمر الدورية.

تذكّر: لا تقسم ببساطة بترديد N؛ بل اضرب بالمعكوس الضربي بترديد N. لذا ستحتاج إلى دالة modinv().

42. هجوم Bleichenbacher على RSA بـ e=3

لوحة معلومات سياحة تشفيرية.

كسر هذا الهجوم التحقق من شهادات TLS في Firefox قبل عدة سنوات. كان يمكنك كتابة نص Python لتزوير توقيع RSA لأي شهادة. نجد حالات جديدة منه كل سنة أو سنتين تقريبًا.

RSA بأس تشفير يساوي 3 شائع، لأنه يجعل رياضيات RSA أسرع.

مع RSA بـ e=3، التشفير مجرد تكعيب عدد بترديد معيار التشفير العام:

 c = m ** 3 % n

يكون e=3 آمنًا ما دمنا قادرين على وضع افتراضات بشأن كتل الرسائل التي نشفّرها. القلق في RSA ذي الأس المنخفض أن كتل الرسائل التي نعالجها لن تكون كبيرة بما يكفي لتجاوز المعيار بعد تكعيبها. الكتلة 00:02 (تخيّل حشوًا صفريًا كافيًا) يمكن «تشفيرها» في RSA بـ e=3؛ إنها ببساطة 00:08.

عندما يُستخدم RSA للتوقيع بدل التشفير، تنعكس العمليات؛ فيقوم المتحقق بـ«فك تشفير» الرسالة عبر تكعيبها. وينتج عن ذلك «نص صريح» يتحقق منه المتحقق للتحقق من صلاحيته.

عندما تستخدم RSA لتوقيع رسالة، تمرّر إليه كتلة إدخال تحتوي على ملخص الرسالة. يصوغ معيار PKCS1.5 تلك الكتلة هكذا:

00h 01h ffh ffh ... ffh ffh 00h ASN.1 GOOP HASH

وكما هو مقصود، تتمدد بايتات ffh في تلك الكتلة لتملأ الكتلة كلها، منتجة تجزئة «محاذاة لليمين» (آخر بايت من التجزئة هو آخر بايت من الرسالة).

كان هناك، قبل 7 سنوات، عيب تنفيذي شائع في متحققَات RSA: كانت تتحقق من التوقيعات عبر «فك تشفيرها» (تكعيبها بترديد الأس العام) ثم «تحليلها» بالبحث عن 00h 01h ... ffh 00h ASN.1 HASH.

هذا خطأ لأنه يعني أن المتحقق لا يتحقق من كل الحشو. وإن لم تتحقق من الحشو، فأنت تفتح احتمال أنه بدلًا من مئات بايتات ffh، لديك بايتات قليلة فقط، وهذا إن فكرت فيه يعني أن هناك عددًا هائلًا من الأعداد الممكنة التي قد تنتج توقيعًا يبدو صالحًا.

كيف تجد كتلة كهذه؟ اعثر على عدد، عند تكعيبه، (أ) لا يتجاوز المعيار (وبذلك يتخطى المفتاح كليًا) و(ب) ينتج كتلة تبدأ بـ "00h 01h ffh ... 00h ASN.1 HASH".

هناك طريقتان لمعالجة هذه المسألة:

• يمكنك العمل من كتابة Hal Finney، المتاحة على Google، عن كيفية شرح Bleichenbacher للرياضيات «بحيث يمكنك فعلها يدويًا بقلم رصاص».
• يمكنك تنفيذ جذر تكعيبي صحيح في لغتك، وصياغة كتلة الرسالة التي تريد تزويرها، مع ترك أصفار لاحقة كافية في النهاية لتُملأ بالعشوائيات، ثم أخذ الجذر التكعيبي لتلك الكتلة.

زوّر توقيع RSA بطول 1024 بتًا للسلسلة "hi mom". تأكد من أن تنفيذك يقبل التوقيع فعلًا!

43. استعادة مفتاح DSA من قيمة nonce

الخطوة 1: انتقل بعيدًا بحيث لا تكون ضمن مسافة سفر سهلة إلينا.

الخطوة 2: نفّذ DSA، حتى التوقيع والتحقق، بما في ذلك توليد المعطيات.

ها ها أنت بعيد جدًا بحيث لا يمكنك المجيء لكيما تضربنا.

أمزح فقط يمكنك تخطي جزء توليد المعطيات إن أردت؛ إن فعلت، استخدم هذه المعطيات:

 p = 800000000000000089e1855218a0e7dac38136ffafa72eda7
     859f2171e25e65eac698c1702578b07dc2a1076da241c76c6
     2d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebe
     ac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2
     b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc87
     1a584471bb1
 
 q = f4f47f05794b256174bba6e9b396a7707e563c5b
 
 g = 5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119
     458fef538b8fa4046c8db53039db620c094c9fa077ef389b5
     322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a047
     0f5b64c36b625a097f1651fe775323556fe00b3608c887892
     878480e99041be601a62166ca6894bdd41a7054ec89f756ba
     9fc95302291

(«لكنني أريد معطيات أصغر!» إذن ولّدها بنفسك.)

تولّد عملية توقيع DSA مفتاحًا فرعيًا عشوائيًا "k". أنت تعرف هذا لأنك نفّذت عملية توقيع DSA.

هذا أول تحدٍّ وأسهله من تحدّيين يتعلقان بالمفتاح الفرعي "k" في DSA.

بالنظر إلى "k" معروف، من البديهي استعادة مفتاح DSA الخاص "x":

          (s * k) - H(msg)
      x = ----------------  mod q
                  r

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

والآن. استخدمت المعطيات أعلاه. ولّدت زوج مفاتيح. مفتاحي العام هو:

  y = 84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4
      abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004
      e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed
      1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07b
      bb283e6633451e535c45513b2d33c99ea17

وقّعت

For those that envy a MC it can be hazardous to your health
So be friendly, a matter of life and death, just like a etch-a-sketch

(كانت قيمة SHA1 لهذه السلسلة d2d0714f014a9784047eaeccf956520045c45265؛ لا أعرف ما يريد NIST أن تفعله، لكنني عندما أحوّل تلك التجزئة إلى عدد صحيح أحصل على: 0xd2d0714f014a9784047eaeccf956520045c45265).

أحصل على:

  r = 548099063082341131477253921760299949438196259240
  s = 857042759984254168557880549501802188789837994940

وقّعت هذه السلسلة بتنفيذ معطوب لـ DSA كان يولّد قيم "k" بين 0 و2^16. ما مفتاحي الخاص؟

بصمة SHA-1 له (بعد تحويلها إلى ست عشري) هي:

0954edd5e0afe5542a4adf012611a91912a3ec16

ومن الواضح أنه يولّد التوقيع نفسه لتلك السلسلة أيضًا.

44. استعادة قيمة nonce في DSA من قيمة متكررة

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

هذا الهجوم (في زمرة منحنيات إهليلجية) كسر جهاز PS3. إنه هجوم عظيم عظيم.

في هذا الملف ستجد مجموعة من الرسائل الموقّعة بـ DSA. (ملاحظة: كل رسالة تنتهي بمسافة.)

وُقّعت هذه تحت المفتاح العام التالي:

y = 2d026f4bf30195ede3a088da85e398ef869611d0f68f07
    13d51c9c1a3a26c95105d915e2d8cdf26d056b86b8a7b8
    5519b1c23cc3ecdc6062650462e3063bd179c2a6581519
    f674a61f1d89a1fff27171ebc1b93d4dc57bceb7ae2430
    f98a6a4d83d8279ee65d71c1203d2c96d65ebbf7cce9d3
    2971c3de5084cce04a2e147821

(باستخدام معطيات النطاق نفسها من التمرين السابق)

لا ينبغي أن يكون صعبًا العثور على الرسائل التي استخدمنا فيها بالخطأ قيمة "k" متكررة. بالنظر إلى زوج من هذه الرسائل، يمكنك اكتشاف قيمة "k" التي استخدمناها بالصيغة التالية:

         (m1 - m2)
     k = --------- mod q
         (s1 - s2)

رياضيات الصف التاسع: ادرسها!

إن أردت إزالة الغموض عن هذا، اشتق تلك المعادلة من معادلات DSA الأصلية.

عمليات الزمر الدورية الأساسية تريد أن توقعك في المشاكل

تذكّر أن كل هذه الرياضيات بترديد q؛ فقد تكون s2 أكبر من s1، مثلًا، وهذا ليس مشكلة إن كنت تجري الطرح بترديد q. وإن كنت مثلي، فستخسر بالتأكيد ساعة بسبب نسيان قوس أو ترديد q. (ولا تنسَ دالة المعكوس الضربي تلك!)

ما مفتاحي الخاص؟ بصمة SHA-1 له (من الست عشري) هي:

   ca8f6f7c66fa362d40760d135b763eb8527d3d52

45. التلاعب بمعطيات DSA

خذ شيفرة DSA من التمرين السابق. تخيّلها جزءًا من خوارزمية يُسمح فيها للعميل باقتراح معطيات النطاق (المعياران p وq، والمولّد g).

سيكون هذا سيئًا، لأن المهاجمين قد يخدعون الضحايا لقبول معطيات فاسدة. أعطى Vaudenay مثالين على معطيات مولّد فاسدة: مولّدات تساوي 0 بترديد p، ومولّدات تساوي 1 بترديد p.

استخدم المعطيات من التمرين السابق، لكن استبدل "g" بـ 0. ولّد توقيعًا. ستلاحظ شيئًا سيئًا. تحقق من التوقيع. الآن تحقق من أي توقيع آخر، لأي سلسلة أخرى.

الآن، جرّب (p+1) كـ "g". مع هذا "g"، يمكنك توليد توقيع سحري s وr لأي مفتاح DSA عام يتحقق مع أي سلسلة. من أجل z اعتباطي:

  r = ((y**z) % p) % q

        r
  s =  --- % q
        z

وقّع "Hello, world". و"Goodbye, world".

46. أوراكل التكافؤ في RSA

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

هذه مسألة أشبه بلعبة، لكنها مفيدة جدًا لفهم ما يفعله RSA (وأيضًا لفهم لماذا يكون التشفير النظري-العددي الخالص مرعبًا). ثق بنا، تريد فعل هذا قبل تجربة التحدي التالي. وهو ممتع أيضًا.

ولّد زوج مفاتيح RSA بطول 1024 بتًا.

اكتب دالة أوراكل تستخدم المفتاح الخاص للإجابة عن سؤال «هل النص الصريح لهذه الرسالة زوجي أم فردي» (هل آخر بتّة من الرسالة 0 أم 1). تخيّل مثلًا خادمًا يقبل رسائل مشفَّرة بـ RSA ويتحقق من تكافؤ فك تشفيرها للتحقق منها، ويبصق خطأً إن كان تكافؤها خاطئًا.

على أي حال: دالة تعيد true أو false بناءً على ما إذا كان النص الصريح المفكوك زوجيًا أم فرديًا، ولا شيء غير ذلك.

خذ السلسلة التالية وفك ترميز base64 لها في شيفرتك (دون النظر إليها!) وشفّرها بالمفتاح العام، منتجًا نصًا مشفَّرًا:

VGhhdCdzIHdoeSBJIGZvdW5kIHlvdSBkb24ndCBwbGF5IGFyb3VuZCB3aXRoIHRoZSBGdW5reSBDb2xkIE1lZGluYQ==

بدالة الأوراكل لديك، يمكنك فك تشفير الرسالة بسهولة.

وإليك السبب:

• النصوص المشفَّرة في RSA مجرد أعداد. يمكنك إجراء رياضيات بسيطة عليها. يمكنك مثلًا ضرب نص مشفَّر بتشفير RSA لعدد آخر؛ وسيكون النص الصريح المقابل حاصل ضرب العددين.
• إن ضاعفت نصًا مشفَّرًا (ضربته بـ (2**e)%n)، فسيكون النص الصريح الناتج (بوضوح) إما زوجيًا أو فرديًا.
• إن كان النص الصريح بعد المضاعفة زوجيًا، فمضاعفة النص الصريح لم تتجاوز المعيار --- فالمعيار عدد أولي. وهذا يعني أن النص الصريح أقل من نصف المعيار.

يمكنك تطبيق هذه القاعدة الإرشادية مرارًا، مرة لكل بتّة من الرسالة، مع فحص دالة الأوراكل في كل مرة.

تبدأ دالة فك التشفير لديك بحدود للنص الصريح هي [0,n].

تقلص كل تكرار من فك التشفير الحدود إلى النصف؛ فإما ينخفض الحد الأعلى إلى النصف وإما ينخفض الحد الأدنى.

بعد log2(n) تكرار، يكون لديك فك تشفير الرسالة.

اطبع الحد الأعلى للرسالة كسلسلة في كل تكرار؛ سترى الرسالة تُفك تشفيرها «على الطريقة الهوليوودية».

فك تشفير السلسلة أعلاه (بعد تشفيرها بمفتاح خاص مخفي).

47. أوراكل حشو PKCS 1.5 لدى Bleichenbacher (الحالة البسيطة)

درجة الصعوبة: متوسطة

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

لندع Google تبحث لك عن هذا: "Chosen ciphertext attacks against protocols based on the RSA encryption standard"

هذا بحث Bleichenbacher من CRYPTO '98؛ أحصل على مجموعة نسخ .ps في أول صفحة بحث.

اقرأ الورقة. تصف هجوم أوراكل حشو على PKCS#1v1.5. الهجوم مشابه في روحه لأوراكل حشو CBC الذي بنيته سابقًا؛ إنه «هجوم نص مشفَّر مختار تكيفي»، أي أنك تبدأ بنص مشفَّر صالح وتفسده مرارًا، وتقذف النصوص المشفَّرة المغشوشة نحو الهدف لتتعلم أشياء عن الأصل.

هذا عيب شائع حتى في الأنظمة التشفيرية الحديثة التي تستخدم RSA.

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

الإعداد:

• ابنِ دالة أوراكل، كما فعلت في التمرين السابق، لكن اجعلها تتحقق من plaintext[0] == 0 وplaintext[1] == 2.
• ولّد زوج مفاتيح بطول 256 بتًا (أي سيكون p وq كل منهما عددًا أوليًا بطول 128 بتًا)، [n, e, d].
• ضع d وn في دالة الأوراكل لديك.
• احشُ رسالة قصيرة، مثل "kick it, CC"، بحشو PKCS1.5 وسمِّها "m". شفّرها للحصول على "c".
• فك تشفير "c" باستخدام أوراكل الحشو لديك.

في هذا التحدي، استخدمنا معيار RSA صغيرًا بشكل غير مقبول (يمكنك تحليل هذا الزوج فوريًا). لأن هذا التمرين يستهدف خطوة محددة في ورقة Bleichenbacher --- الخطوة 2c، التي تنفّذ بحثًا سريعًا شبه O(log n) عن النص الصريح.

أمور تريد أن تضعها في ذهنك وأنت تقرأ الورقة:

• النصوص المشفَّرة في RSA مجرد أعداد.
• RSA «متماثل» بالنسبة إلى الضرب، ما يعني أنك تستطيع ضرب c * RSA(2) للحصول على c' سيُفك تشفيره إلى plaintext * 2. هذا مذهل لكن يسهل رؤيته إن لعبت به في الشيفرة --- جرّب ضرب نصوص مشفَّرة بتشفيرات RSA لأعداد حتى تتأكد من استيعابك.
• ما تحتاج إلى استيعابه لهذا التحدي أن Bleichenbacher يستخدم الضرب على النصوص المشفَّرة كما يستخدم أوراكل CBC عمليات XOR على كتل عشوائية.
• النص الصريح المتوافق مع PKCS#1v1.5، الذي يبدأ بـ 00:02، يجب أن يكون عددًا بين 02:00:00...00 و02:FF:FF..FF --- بعبارة أخرى، 2B و3B-1، حيث B هو حجم المعيار بالبتّات ناقص أول 16 بتًا. عندما ترى 2B و3B، فهذه هي الفكرة التي تلعب بها الورقة.

لفك تشفير "c"، ستحتاج إلى الخطوة 2a من الورقة (البحث عن أول "s" ينتج، عند تشفيره وضربه بالنص المشفَّر، نصًا صريحًا متوافقًا)، والخطوة 2c، البحث السريع O(log n)، والخطوة 3.

من المرجح ألا يحتاج رمز الخطوة 3 لديك إلى معالجة نطاقات متعددة.

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

48. أوراكل حشو PKCS 1.5 لدى Bleichenbacher (الحالة الكاملة)

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

هذا هجوم مفيد بشكل استثنائي. حشو PKCS#1v15، رغم كونه غير آمن إطلاقًا، هو الحشو الافتراضي الذي تستخدمه تنفيذات RSA. ومعيار OAEP الذي يحل مكانه غير مُنفَّذ على نطاق واسع. هذا الهجوم يكسر SSL/TLS بانتظام.

هذا استكمال للتحدي رقم 47؛ إنه ينفّذ هجوم BB'98 الكامل.

جهّز نفسك كما فعلت في رقم 47، لكن ولّد هذه المرة معيارًا بطول 768 بتًا.

لتعمل الهجوم مع زوج مفاتيح RSA واقعي، تحتاج إلى إعادة إنتاج الخطوة 2b من الورقة، ويحتاج تنفيذك للخطوة 3 إلى معالجة نطاقات متعددة.

يعمل هجوم Bleichenbacher الكامل أساسًا هكذا:

• بدءًا من أصغر 's' يمكنه إنتاج نص صريح أكبر من 2B، ابحث تكراريًا عن 's' ينتج نصًا صريحًا متوافقًا.
• من أجل 's1' و'n' المعلومين، حُلّ m1=m0s1-rn (مجددًا: هذا مجرد تعريف للضرب بترديد) لإيجاد 'r'، عدد مرات تجاوزنا المعيار.
• 'm0' و'm1' مجهولان، لكننا نعلم أن كليهما نصان صريحان متوافقان مع PKCS#1v1.5، وبالتالي يقعان بين [2B,3B].
• نستبدل الحدود المعلومة لكليهما، فلا يبقى حرًا سوى 'r'، ونحل من أجل نطاق من قيم 'r' الممكنة. ينبغي أن يكون هذا النطاق صغيرًا!
• حُلّ m1=m0s1-rn مرة أخرى، لكن هذه المرة لإيجاد 'm0'، بإدخال كل قيمة من قيم 'r' التي ولّدناها في الخطوة السابقة. يعطينا هذا فترات جديدة نعمل بها. استبعد أي فترة خارج 2B,3B.
• أعد العملية لقيم أعلى متتالية من 's'. في النهاية، ستوصلنا هذه العملية إلى فترة واحدة فقط، وعندها نعود إلى التمرين رقم 47.

ما يحدث عندما نصل إلى فترة واحدة هو أننا نتوقف عن زيادة 's' عمياء؛ بل نبدأ بزيادة 'r' بسرعة واستخراج قيم 's' منه بحل m1=m0s1-rn لإيجاد 's' بدلًا من 'r' أو 'm0'. يا لكثرة الجبر! اجعل ابنك المراهق يفعلها نيابة عنك! ملاحظة: لا تعمل جيدًا عمليًا