المجموعة 8

هذه ثانية مجموعتين ولّدناهما بعد المجموعات الست الأصلية.

تركّز هذه المجموعة على الجبر المجرد، بما في ذلك DH وGCM و(الأهم) تشفير المنحنيات الإهليلجية (elliptic curve cryptography). تحذير عادل --- إنها صعبة حقًا! هناك قدر هائل من المحتوى هنا، وهي أكثر طلبًا من أي شيء نشرناه حتى الآن. بحلول الوقت الذي تنتهي فيه، ستكون قد كتبت تنفيذًا مخصصًا، غير محدد المواصفات رسميًا، مليئًا بالأخطاء، وبطيئًا، لواحد بالمئة من SageMath.

57. عودة إلى تبادل مفاتيح ديفي-هيلمان: هجمات حصر الزمر الجزئية

ستركز هذه المجموعة على المنحنيات الإهليلجية. لكن قبل أن نصل إلى ذلك، سنبدأ ببعض من تبادل مفاتيح ديفي-هيلمان الكلاسيكي.

ثق بي، سيكون هذا منطقيًا لاحقًا.

لندخل في الموضوع مباشرة. أولًا، ابنِ اتفاق تبادل مفاتيح ديفي-هيلمان النموذجي: يتبادل Alice وBob المفتاحين العامين ويشتقان السر المشترك نفسه. ثم يرسل Bob إلى Alice رسالة مع رمز مصادقة (MAC) عليها. سهل كالفطيرة.

استخدم هذه المعطيات:

    p = 7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771
    g = 4565356397095740655436854503483826832136106141639563487732438195343690437606117828318042418238184896212352329118608100083187535033402010599512641674644143

رتبة المولّد g هي q:

    q = 236234353446506858198510045061214171961

«الرتبة» (order) كلمة جديدة، لكنها تعني ببساطة g^q = 1 بترديد p. قد تلاحظ أن q عدد أولي، تمامًا مثل p. وهذا ليس محض صدفة: في الحقيقة، اخترنا q وp معًا بحيث يقسم q العدد p-1 (رتبة الزمرة أو حجمها) قسمة تامة. وهذا يضمن وجود عنصر g من الرتبة q. (في الواقع، سيكون هناك q-1 عنصرًا كهذا.)

عودة إلى البروتوكول. ينبغي أن يختار Alice وBob مفتاحيهما السريين كأعداد صحيحة عشوائية بترديد q. لا فائدة من اختيارهما بترديد p؛ فبما أن g من الرتبة q، ستبدأ الأعداد بالتكرار بعد ذلك فقط. يمكنك أن تثبت هذا لنفسك بالتحقق من g^x mod p = g^(x + k*q) mod p من أجل أي x وk.

والباقي كما كان سابقًا.

كيف يمكننا مهاجمة هذا البروتوكول؟ تذكر ما قلناه سابقًا عن الرتبة: كون q يقسم p-1 يضمن وجود عناصر من الرتبة q. ماذا لو كان هناك قواسم أصغر للعدد p-1؟

تنبيه بخصوص الحرق: توجد. اخترت j = (p-1) / q ليكون له عوامل صغيرة كثيرة لأنني أريدك أن تكون سعيدًا. اعثر عليها بتحليل j، وهو:

    j = 30477252323177606811760882179058908038824640750610513771646768011063128035873508507547741559514324673960576895059570

لا تحتاج إلى تحليله كاملًا. اكتفِ بإيجاد مجموعة من العوامل الأصغر من، لنقل، 2^16. ينبغي أن تكون كثيرة. (نصيحة ودية: تجنّب على الأرجح أي عوامل متكررة. فهي تزيد الأمور تعقيدًا فقط.)

وجدتها؟ حسنًا. الآن يمكننا استخدامها لاستعادة مفتاح Bob السري باستخدام خوارزمية Pohlig-Hellman للوغاريتمات المتقطعة. وإليك الطريقة:

خذ أحد العوامل الصغيرة j. سمّه r. نريد إيجاد عنصر h من الرتبة r. لإيجاده، افعل:

       h := rand(1, p)^((p-1)/r) mod p

إن كان h = 1، فجرّب مرة أخرى.

أنت Eve. أرسل إلى Bob القيمة h كمفتاحك العام. لاحظ أن h ليس مفتاحًا عامًا صالحًا! لا يوجد x بحيث h = g^x mod p. لكن Bob لا يعرف ذلك.
سيحسب Bob:

       K := h^x mod p

حيث x مفتاحه السري وK هو السر المشترك الناتج. ثم يعيد Bob إرسال (m, t)، حيث:

       m := "crazy flamboyant for the rap enjoyment"
       t := MAC(K, m)

لا يمكننا (نحن Eve) حساب K، لأن h ليس في الواقع مفتاحًا عامًا صالحًا. لكننا لم نُهزم بعد.

تذكر كيف رأينا أن g^x يبدأ بالتكرار عندما x > q؟ للعنصر h الخاصية نفسها مع r. هذا يعني أن هناك r قيمة ممكنة فقط لـ K كان Bob قد ولّدها. يمكننا استعادة K بإجراء بحث بالقوة الغاشمة على هذه القيم حتى t = MAC(K, m).

الآن نعرف مفتاح Bob السري x بترديد r.
أعد الخطوات من 1 إلى 4 مرات كثيرة. في النهاية ستعرف:

       x = b1 mod r1
       x = b2 mod r2
       x = b3 mod r3
       ...

وبمجرد أن يصبح (r1r2...*rn) > q، ستكون لديك معلومات كافية لإعادة تجميع مفتاح Bob السري باستخدام نظرية الباقي الصيني.

58. طريقة Pollard لاصطياد الكناغر

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

إذن ماذا لو استطعنا استعادة جزء فقط من مفتاح Bob السري؟ يبدو أنه ينبغي أن تكون هناك طريقة لاستخدام تلك المعرفة لاستعادة الباقي. وهي موجودة: خوارزمية الكنغر لـ Pollard.

هذا هجوم عام لحساب لوغاريتم متقطع (أو «دليل») معلوم أنه يقع ضمن مجال متصل معين [a, b]. وعامل جهده يقارب الجذر التربيعي لحجم المجال.

الاستراتيجية الأساسية هي محاولة إيجاد تصادم بين متتاليتين شبه عشوائيتين من العناصر. تبدأ إحداهما من عنصر دليله معروف، وتبدأ الأخرى من العنصر y الذي نريد إيجاد دليله.

من المهم فهم كيفية توليد هذه المتتاليات. ببساطة، نعرّف دالة f تربط عناصر الزمرة (مثل المولّد g، أو مفتاح عام y) بقياسات (أس سري، مثل x)، أي:

    f(y) = <some x>

لا تقلق بشأن كيفية تنفيذ f الآن. اعلم فقط أنها دالة تربط مكاننا الحالي (بعض y) بالقفزة التالية التي سنأخذها (بعض x). وهي حتمية: من أجل y معين، ينبغي أن تعيد دائمًا قيمة x نفسها.

ثم نفّذ حلقة هكذا:

    y := y * g^f(y)

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

حسنًا، لنتحدث بتحديد أكبر قليلًا. ذكرت أننا سنولّد متتاليتين بهذه الطريقة. الأولى هي متتالية التحكم. هذا هو الكنغر الأليف في مثال Pollard. نفعل شيئًا مثل هذا:

    xT := 0
    yT := g^b

    for i in 1..N:
        xT := xT + f(yT)
        yT := yT * g^f(yT)

تذكّر أن b هو الحد الأعلى لدليل y. لذا نبدأ مسار الكنغر الأليف عند نهاية ذلك المجال تمامًا. ثم نأخذ N قفزة ونراكم إجمالي المسافة المقطوعة في xT. في نهاية الحلقة، yT = g^(b + xT). سيكون هذا مهمًا لاحقًا.

لاحظ أن هذه الخوارزمية لا تتطلب بناء جدول بحث كبير على طريقة خطوة الطفل الواسعة لـ Shanks، لذا فتعقيدها المكاني ثابت. هذا لطيف نوعًا ما.

الآن: لنمسك ذلك الكنغر البري. سننفّذ حلقة مشابهة، تبدأ هذه المرة من y. أملنا أن نتصادم في مرحلة ما مع مسار الكنغر الأليف. إن حدث ذلك، فسننتهي في النهاية إلى المكان نفسه. لذا في كل تكرار، سيتحقق من وصولنا.

    xW := 0
    yW := y

    while xW < b - a + xT:
        xW := xW + f(yW)
        yW := yW * g^f(yW)

        if yW = yT:
            return b + xT - xW

توقف لحظة لتتفكر في شرط الحلقة. ما تتحقق منه هذه العلاقة هو ما إذا كنا قد تجاوزنا yT وأفلتناه. بعبارة أخرى، أننا لم نتصادم. هذه خوارزمية احتمالية، لذا لا ضمان لأن تنجح.

تأكد أيضًا من فهمك لعبارة الإرجاع. فإن فكّرت في كيفية وصولنا إلى القيم النهائية لـ yW وyT، ينبغي أن يتضح أن هذه القيمة هي دليل الإدخال y.

هناك تفصيلان تنفيذيان تجاوزناهما --- تحديدًا الدالة f وعدد التكرارات N. أفعل شيئًا كهذا:

    f(y) = 2^(y mod k)

من أجل k ما، يمكنك اللعب به. جعل k أكبر يتيح لك أخذ قفزات أكبر في كل تكرار من الحلقة.

ثم يُشتق N من f --- خذ متوسط كل المخارج الممكنة لـ f واضربه في ثابت صغير، مثل 4. يمكنك جعل الثابت أكبر لتحسين فرصك في إيجاد تصادم بتكلفة (واضحة) هي حساب إضافي. سبب اعتماد N على f هو أن f يحكم حجم القفزات التي يمكننا أخذها. إن كانت القفزات أكبر، احتجنا مدرجًا أطول للهبوط عليه، وإلا خاطرنا بالقفز فوقه.

نفّذ خوارزمية الكنغر لـ Pollard. إليك بعض معطيات الزمرة (الأقل تساهلًا):

    p = 11470374874925275658116663507232161402086650258453896274534991676898999262641581519101074740642369848233294239851519212341844337347119899874391456329785623
    q = 335062023296420808191071248367701059461
    j = 34233586850807404623475048381328686211071196701374230492615844865929237417097514638999377942356150481334217896204702
    g = 622952335333961296978159266084741085889881358738459939978290179936063635566740258555167783009058567397963466103140082647486611657350811560630587013183357

وإليك قيمة y نموذجية:

    y = 7760073848032689505395005705677365876654629189298052775754597607446617558600394076764814236081991643094239886772481052254010323780165093955236429914607119

دليل y يقع في المجال [0, 2^20]. اعثر عليه بخوارزمية الكنغر.

انتظر، هذا صغير بما يكفي للقوة الغاشمة. إليك واحدًا دليله في [0, 2^40]:

    y = 9388897478013399550694114614498790691034187453089355259602614074132918843899833277397448144245883225611726912025846772975325932794909655215329941809013733

اعثر على ذلك أيضًا. قد يستغرق دقيقتين.

    ~~ later ~~

كفى حديثًا عن الكناغر، لنعد إلى Bob. افترض أننا نعرف مفتاح Bob السري x = n mod r من أجل r < q ما. في الواقع ليس واضحًا تمامًا كيف نطبّق هذه الخوارزمية للحصول على الباقي! لأننا نملك فقط:

    x = n mod r

ما يعني:

    x = n + m*r

من أجل m مجهول ما. هذه العلاقة تعرّف مجموعة قيم موزعة على فترات مقدارها r، لكن كنغر Pollard يتطلب مجالًا متصلًا!

في الواقع، هذه ليست مشكلة كبيرة. لأن انظر --- يمكننا ببساطة تطبيق التحويلات التالية:

    x = n + m*r
    y = g^x = g^(n + m*r)
    y = g^n * g^(m*r)
    y' = y * g^-n = g^(m*r)
    g' = g^r
    y' = (g')^m

الآن ابحث ببساطة عن الدليل m لـ y' بالنسبة إلى العنصر الأساس g'. لاحظ أن لدينا حدًا تقريبيًا لـ m: [0, (q-1)/r]. بعد إيجاد m، يمكنك إدخاله في معرفتك الحالية بـ x لاستعادة باقي السر.

خذ معطيات الزمرة أعلاه وولّد زوج مفاتيح لـ Bob. استخدم هجوم حصر الزمر الجزئية من المسألة الأخيرة لاستعادة أكبر قدر ممكن من سر Bob. ستتمكن من الحصول على جزء جيد منه، لكن ليس كله. ثم استخدم خوارزمية الكنغر لتعقّب البتّات المتبقية.

59. تبادل مفاتيح ديفي-هيلمان على المنحنيات الإهليلجية وهجمات المنحنيات غير الصالحة

لن أعرض عليك أي رسوم بيانية --- إن أردت رؤية أحدها، يمكنك إيجادها في، مثلًا، كل درس تعليمي آخر عن المنحنيات الإهليلجية على الإنترنت. شخصيًا، لم أستطع يومًا استخلاص الكثير من الفهم منها.

كما أنها صعبة الرسم جدًا بـ ASCII.

الأمر الأساسي لفهم المنحنيات الإهليلجية أنها إطار مشابه من نواحٍ كثيرة لإطار أكثر ألفة لنا، وهو الأعداد الصحيحة الضربية بترديد p. لذا إن تعلمنا كيفية تعريف بعض العمليات الأولية، أمكننا التفكير فيها باستخدام كثير من الأدوات التي نملكها أصلًا في أحزمتنا.

لنغص في التفاصيل. المنحنى الإهليلجي E مجرد معادلة مثل هذه:

    y^2 = x^3 + a*x + b

اختيار المعاملين a وb يحدد المنحنى.

عناصر زمرتنا ستكون إحداثيات (x, y) تحقق معادلة المنحنى. الآن، هناك عدد لا نهائي من الأزواج كهذه على المنحنى، لكننا نريد التفكير في بعضها فقط. سنقلّص مجموعة النقاط بالتفكير في المنحنى في سياق حقل منتهٍ.

في الوقت الحالي، ليس مهمًا كثيرًا معرفة ما الحقل المنتهي. يمكنك أساسًا التفكير فيه كـ«أعداد صحيحة بترديد p» مع كل العمليات المعتادة التي تتوقعها: الضرب، والقسمة (عبر المعكوس الترديدي)، والجمع، والطرح.

سنستخدم الترميز GF(p) للحديث عن حقل منتهٍ حجمه p. (الحرفان "GF" اختصار «حقل Galois»، وهو اسم آخر للحقل المنتهي.) عندما نأخذ منحنى E فوق الحقل GF(p) (ويُكتب E(GF(p))، ما نقوله هو أن النقاط التي تقع فيها x وy معًا في GF(p) فقط هي الصالحة.

على سبيل المثال، قد تكون (3, 6) نقطة صالحة في E(GF(7))، لكنها لن تكون نقطة صالحة في E(GF(5))؛ فالعدد 6 ليس عضوًا في GF(5).

و(3, 4.7) لن تكون نقطة صالحة على أي من المنحنيين، لأن 4.7 ليس عددًا صحيحًا وبالتالي ليس عضوًا في أي من الحقلين.

وماذا عن (3, -1)؟ هذه على المنحنى، لكن تذكر أننا في حقل GF(p) ما. لذا في GF(7)، العدد -1 هو في الواقع 6. هذا يعني أن (3, -1) و(3, 6) هما النقطة نفسها. وفي GF(5)، العدد -1 هو 4، لذا وهكذا دواليك، فهمت ما أقوله.

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

في الأعداد الصحيحة الضربية بترديد p، كنا ندمج عنصرين بضربهما معًا وأخذ باقي القسمة على p.

ندمج نقاط المنحنى الإهليلجي بجمعها. سنتحدث عن معنى ذلك بعد لحظة وجيزة.
استخدمنا 1 كمحايد ضربي: y * 1 = y من أجل كل y.

على المنحنى الإهليلجي، نعرّف المحايد O كنقطة مجردة «في اللانهاية» لا تقابل أي زوج (x, y) فعلي. قد يبدو هذا حيلة إلى حد ما، لكنه يعمل.

على المنحنى، لدينا القاعدة المباشرة P + O = P من أجل كل P.

في شيفرتك، يمكنك ببساطة كتابة شيء مثل O := object()، لأنه لا يُستخدم إلا في مقارنات المؤشرات. أو يمكنك استخدام إحداثي إشاري لا يحقق معادلة المنحنى؛ و(0, 1) اختيار شائع.
كان لدينا دالة modinv لعكس عدد صحيح بترديد p. وكانت تقوم مقام القسمة. بالنظر إلى y، تجد x بحيث y * x = 1.

العكس أسهل بكثير في المنحنيات الإهليلجية. اقلب إشارة y فقط، وتذكر أننا في GF(p):

       invert((x, y)) = (x, -y) = (x, p-y)

وكما في المعكوسات الضربية، لدينا هذه القاعدة على المنحنيات الإهليلجية:

       P + (-P) = P + invert(P) = O

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

لنتحدث عن الجمع. ها هو:

    function add(P1, P2):
        if P1 = O:
            return P2

        if P2 = O:
            return P1

        if P1 = invert(P2):
            return O

        x1, y1 := P1
        x2, y2 := P2

        if P1 = P2:
            m := (3*x1^2 + a) / 2*y1
        else:
            m := (y2 - y1) / (x2 - x1)

        x3 := m^2 - x1 - x2
        y3 := m*(x1 - x3) - y1

        return (x3, y3)

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

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

هناك أمر آخر نحتاجه. في الأعداد الصحيحة الضربية، عبّرنا عن الضرب المتكرر بالرفع إلى قوة، مثل:

    y * y * y * y * y = y^5

نفّذنا هذا باستخدام دالة modexp كانت تمشي على بتّات الأس بحلقة داخلية للتربيع والضرب.

على المنحنيات الإهليلجية، سنستخدم الضرب القياسي للتعبير عن الجمع المتكرر، مثل:

    P + P + P + P + P = 5*P

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

ستبدو دالة scalarmult لديك تمامًا مثل دالة modexp، إلا مع تبديل الأوليات.

في الواقع، أتريد سماع شيء رائع؟ يمكنك تعريف دالة قياس عامة محدَّدة على زمرة تعمل كتنفيذ بديل لكلتيهما. هكذا:

    function scale(x, k):
        result := identity
        while k > 0:
            if odd(k):
                result := combine(result, x)
            x := combine(x, x)
            k := k >> 1
        return result

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

لنوسّع هذا التشبيه، وإليك ديفي-هيلمان عام:

    function generate_keypair():
        secret := random(1, baseorder)
        public := scale(base, secret)
        return (secret, public)

    function compute_secret(peer_public, self_secret):
        return scale(peer_public, self_secret)

البساطة نفسها! الخاصيتان base وbaseorder تقابلان g وq في إطار الأعداد الصحيحة الضربية. الأمر مشابه تمامًا على منحنى: سيكون لدينا نقطة أساس G ورتبتها n بحيث:

    n*G = O

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

لنضع هذه المعرفة الجديدة موضع التنفيذ. نفّذ مجموعة من الدوال حتى الضرب القياسي على المنحنى الإهليلجي شاملًا. (تذكر أن كل الحسابات في GF(p)، أي بترديد p.) يمكنك استخدام هذا المنحنى:

    y^2 = x^3 - 95051*x + 11279326

فوق GF(233970423115425145524320034830162017933). استخدم نقطة الأساس هذه:

    (182, 85518893674295321206118380980485522083)

رتبتها 29246302889428143187362802287225875743.

آه أجل، الرتبة. تبيّن أن إيجاد رتبة زمرة منحنٍ إهليلجي أمر صعب قليلًا، لذا ثق بي فقط عندما أخبرك أن رتبة هذه هي 233970423115425145498902418297807005944. وهي تتحلل إلى 2^3 * 29246302889428143187362802287225875743.

ملاحظة: من الممكن تمامًا اختيار زمرة منحنٍ إهليلجي رتبتها عدد أولي مباشر. هذا سيعني أن كل نقطة على المنحنى (عدا المحايد) لها الرتبة نفسها، لأن رتبة الزمرة لن يكون لها قواسم أخرى. منحنيات NIST P كذلك.

منحنانا رتبته شبه أولية. لا يوجد سوى ذلك العامل المساعد الصغير 2^3، وهو مفيد لأسباب سنغطيها لاحقًا. لا تقلق بشأنه الآن.

إن عمل تنفيذك بشكل صحيح، ينبغي أن يسهل التحقق: تذكر أن ضرب نقطة الأساس في رتبتها ينبغي أن يعطي محايد الزمرة.

نفّذ ECDH وتحقق من قدرتك على إجراء مصافحة صحيحة. في هذه الحالة، سيكون سرّا Alice وBob قياسيين بترديد رتبة نقطة الأساس، وستكون عناصرهما العامة نقاطًا. وإن نفّذت الأوليات بشكل صحيح، فكل شيء ينبغي أن «يعمل» ببساطة.

الآن، أعد تهيئة بروتوكولك من رقم 57 لاستخدامه.

هل يمكننا تطبيق هجمات حصر الزمر الجزئية من رقم 57 في هذا الإطار؟ للوهلة الأولى، يبدو أن هذا سيكون صعبًا جدًا، لأن العامل المساعد صغير جدًا. يمكننا استعادة، مثلًا، ثلاث بتّات بإرسال نقطة رتبتها 8، لكن هذا كل شيء تقريبًا. لا توجد نقاط كافية ذات رتبة صغيرة على المنحنى.

ماذا عن نقاط ليست على المنحنى؟

انتظر، ماذا؟ نعم، نقاط ليست على المنحنى. انظر بدقة أكبر إلى دالة combine لدينا. تلاحظ أي شيء ناقص؟ المعامل b للمنحنى غير مأخوذ في الحسبان في أي مكان. السبب أن لدينا أربعة مدخلات للحساب: معطيات المنحنى (a, b) وإحداثيات النقطة (x, y). بالنظر إلى أي ثلاثة منها، يمكنك حساب الرابع. بعبارة أخرى، لا نحتاج b لأن b مدمج أصلًا في كل زوج (x, y) صالح.

هناك افتراض خطير هنا: ألا وهو أن الطرف الآخر سيرسل زوج (x, y) صالحًا. إن استطاعت Eve إرسال زوج غير صالح، فهذا يفتح لها اللعب حقًا: يمكنها الآن اختيار نقاط من أي منحنى يختلف في معامل b فقط. كل ما عليها فعله هو إيجاد بعض المنحنيات ذات الزمر الجزئية الصغيرة وانتقاء بضع نقاط ذات رتبة صغيرة. وستحسب Alice دون قصد السر المشترك على المنحنى الخاطئ وتسرّب بضع بتّات من مفتاحها الخاص في هذه العملية.

كيف نجد منحنيات مناسبة؟ حسنًا، تذكر أنني ذكرت أن عدّ النقاط على المنحنيات الإهليلجية صعب. إن كنت شجاعًا جدًا، فيمكنك تنفيذ Schoof-Elkies-Atkins. أو يمكنك استخدام نظام جبر حاسوبي مثل SageMath. أو يمكنك ببساطة استخدام هذه المنحنيات التي ولّدتها لك:

    y^2 = x^3 - 95051*x + 210
    y^2 = x^3 - 95051*x + 504
    y^2 = x^3 - 95051*x + 727

رتبها هي:

    233970423115425145550826547352470124412
    233970423115425145544350131142039591210
    233970423115425145545378039958152057148

ينبغي أن يكون فيها عدد لا بأس به من العوامل الصغيرة. إذن: اعثر على بعض النقاط ذات الرتبة الصغيرة وأرسلها إلى Alice. يمكنك استخدام الحيلة نفسها من قبل لإيجاد نقاط ذات رتبة أولية r. افترض أن رتبة الزمرة q. اختر نقطة عشوائية واضربها في q/r. إن هبطت على المحايد، فابدأ من جديد.

قد لا يتضح فورًا كيف تختار نقاطًا عشوائية، لكن يمكنك ببساطة اختيار x وحساب y. سيتطلب هذا منك تنفيذ خوارزمية جذر تربيعي ترديدي؛ استخدم Tonelli-Shanks، فهي مباشرة جدًا.

نفّذ هجوم استعادة المفتاح من رقم 57 باستخدام نقاط صغيرة الرتبة من منحنيات غير صالحة.

60. السلالم أحادية الإحداثي والالتواءات غير الآمنة

كل عملنا الشاق على وشك أن يثمر. إليك قائمة بمصطلحات المدوّنين الرائجة التي ستصبح قادرًا على استخدامها بعد إكمال هذا التحدي:

منحنى Montgomery
سلم أحادي الإحداثي
التماثل البنيوي (isomorphism)
التكافؤ الثنائي النسبي (birational equivalence)
الالتواء التربيعي (quadratic twist)
أثر Frobenius

ليس أنك ستفهمها كلها؛ لن تفهمها. لكنك على الأقل ستكون قادرًا على إسكات مدّعي التشفير على تويتر.

الآن، إلى المهمة المطروحة. في المسألة الأخيرة، نفّذنا ECDH باستخدام صيغة منحنى Weierstrass القصيرة، هكذا:

    y^2 = x^3 + a*x + b

كانت هذه، لفترة طويلة، أشهر صيغة منحنى. منحنيات NIST P المعيارية من التسعينيات تبدو هكذا. وهي ما ستراه أولًا في معظم دروس المنحنيات الإهليلجية (بما في ذلك هذا الدرس).

يمكننا فعل أفضل بكثير. تعرّف على منحنى Montgomery:

    B*v^2 = u^3 + A*u^2 + u

رغم أنه قديم تقريبًا قدم صيغة Weierstrass، فقد دُفن في الأدبيات حتى وقت قريب إلى حد ما. لمنحنى Montgomery ميزة قاتلة في صورة خوارزمية بسيطة وفعّالة لحساب الضرب القياسي: سلم Montgomery.

وإليك السلم:

    function ladder(u, k):
        u2, w2 := (1, 0)
        u3, w3 := (u, 1)
        for i in reverse(range(bitlen(p))):
            b := 1 & (k >> i)
            u2, u3 := cswap(u2, u3, b)
            w2, w3 := cswap(w2, w3, b)
            u3, w3 := ((u2*u3 - w2*w3)^2,
                       u * (u2*w3 - w2*u3)^2)
            u2, w2 := ((u2^2 - w2^2)^2,
                       4*u2*w2 * (u2^2 + A*u2*w2 + w2^2))
            u2, u3 := cswap(u2, u3, b)
            w2, w3 := cswap(w2, w3, b)
        return u2 * w2^(p-2)

ليس متوقعًا منك أن تفهم هذا.

لا، حقًا! معظم الناس لا يفهمونه. بدلًا من ذلك، يزورون قاعدة الصيغ الصريحة (https://www.hyperelliptic.org/EFD/)، المتجر الشامل لتقنيات تنفيذ ECC الحديثة. إنها مثل شيفرات الغش للمنحنيات الإهليلجية. تستحق الزيارة من أجل قائمة المراجع وحدها.

ومع ذلك، ينبغي أن نحاول إزالة بعض الغموض عن هذا قليلًا. إليك الملخص الموجز:

نقاط منحنى Montgomery أزواج (u, v)، لكن هذه الدالة تأخذ u فقط كمدخل. بالنظر إلى مجرد الإحداثي u لنقطة P، تحسب هذه الدالة مجرد الإحداثي u للنقطة k*P. وبما أننا نهتم بـ u فقط، فهذا سلم أحادي الإحداثي.
فما هو إذن w؟ إنه جزء من تمثيل بديل للنقطة. فبدلًا من إحداثي u، لدينا إحداثي u/w. فكّر فيه كطريقة لتأجيل عمليات القسمة المكلفة (أي العكس) حتى النهاية تمامًا.
cswap دالة تبدّل وسيطيها الأولين (أو لا تبدلهما) بناءً على ما إذا كان وسيطها الثالث واحدًا أم صفرًا. المنفّذون المنتقون يختارون تنفيذات حسابية لـ cswap، لا تنفيذات تفريعية.
جوهر الحلقة الداخلية جمع تفاضلي يتبعه عملية مضاعفة. الجمع التفاضلي يعني أننا نستطيع جمع نقطتين P وQ فقط إذا كنا نعرف أصلًا P - Q. سنأخذ هذا الفرق كمدخل u ونحافظ عليه كثابت طوال السلم. وفي الواقع، نقطتانا الابتدائيتان هما:

       u2, w2 := (1, 0)
       u3, w3 := (u, 1)

وتمثّلان المحايد والمدخل u. 5. عبارة الإرجاع تنفّذ العكس الترديدي باستخدام حيلة تعود إلى مبرهنة فيرما الصغرى:

       a^p     = a    mod p
       a^(p-1) = 1    mod p
       a^(p-2) = a^-1 mod p

من نتائج سلم Montgomery أننا نخلط بين (u, v) و(u, -v). لكن هذا الترميز يخلط أيضًا بين الصفر واللانهاية. فكلاهما ممثَّل بالصفر. لاحظ أن الحالة الشاذة المعتادة حيث w = 0 تُعالَج بسلاسة: حيلتنا للقيام بالعكس بالرفع إلى قوة تخرج صفرًا كما هو متوقع.

لا بأس بهذا: ما زلنا نعمل في زمرة جزئية رتبتها أولية.

تفضّل بتنفيذ السلم. تذكّر أن كل الحسابات في GF(233970423115425145524320034830162017933).

آه أجل، معطيات المنحنى. قد تفكر أنه بما أننا ننتقل إلى صيغة منحنى جديدة، فنحن بحاجة أيضًا إلى انتقاء منحنى جديد بالكامل. لكنك ستكون مخطئًا تمامًا! تبيّن أن بعض منحنيات Weierstrass القصيرة يمكن تحويلها إلى منحنيات Montgomery.

السبب أن كل الزمر الدورية المنتهية المتساوية في عدد العناصر تتشارك نوعًا من التكافؤ نسميه «التماثل البنيوي». هذا منطقي إن فكّرت فيه --- إن كانت الرتبة نفسها، فكل الزمر الجزئية نفسها ستكون موجودة، وبنسبها نفسها.

لذا كل ما نحتاج فعله هو:

إيجاد منحنى Montgomery برتبة مساوية لمنحنانا.
معرفة كيفية ربط النقاط ذهابًا وإيابًا بين المنحنيين.

يمكنك إجراء هذا التحويل جبريًا. لكنه مزعج نوعًا ما، لذا ها هو:

    v^2 = u^3 + 534*u^2 + u

بحكم الدهاء والبصيرة، اخترت هذا المنحنى تحديدًا ليكون له ربط بسيط جدًا بين صيغتي Weierstrass وMontgomery. ها هو:

    u = x - 178
    v = y

ما يجعل نقطة أساسنا:

    (4, 85518893674295321206118380980485522083)

أو، كما تعلم. مجرد 4.

على أي حال، نفّذ السلم. تحقق من أن ladder(4, n) = 0. اربط بعض النقاط ذهابًا وإيابًا بين تمثيلَي Weierstrass وMontgomery وتحقق منها.

من الأمور الجيدة في سلم Montgomery خلوه من الحالات الخاصة. تحديدًا، لا معالجة خاصة لـ: P1 = O؛ أو P2 = O؛ أو P1 = P2؛ أو P1 = -P2. قارن ذلك بدالة الجمع لدينا على Weierstrass وكتيبتها من عبارات if.

وهناك فائدة أمنية أيضًا: بتجاهل الإحداثي v، نسحب من المهاجم قدرًا كبيرًا من حرية الحركة. تذكّر أن القدرة على اختيار أزواج (x, y) اعتباطية أتاحت لهم انتقاء نقاط من أي منحنى يمكن أن يخطر ببالهم. أما السلم أحادي الإحداثي فيسلب المهاجم تلك الحرية.

لكن انتظر لحظة! جرّب هذا:

    ladder(76600469441198017145391791613091732004, 11)

ما هذا بحق السماء؟ ما الذي يجري هنا؟

لنجرِ تحققًا سريعًا من السلامة. ها هي معادلة المنحنى مجددًا:

    v^2 = u^3 + 534*u^2 + u

أدخل u وخُذ الجذر التربيعي لاستعادة v.

ينبغي أن تكتشف أن هناك خطأ كبيرًا. هذا الإحداثي u لا يمثّل نقطة على منحنانا! فليس كل u يمثّل نقطة.

هذا يعني أنه رغم أننا لا نستطيع إرسال سوى إحداثي واحد، فما زالت لدينا قليل من حرية الحركة لإيجاد نقاط غير صالحة. تحديدًا، إدخال u بحيث لا يكون u^3 + 534*u^2 + u بواقي تربيعيًا لا يمكن أن يمثّل نقطة على منحنانا أبدًا. فأين نحن بحق السماء؟

المنحنى الآخر الذي نحن عليه منحنى شقيق يُسمى «التواء تربيعي» (quadratic twist)، أو ببساطة «الالتواء». هناك في الواقع عائلة كاملة من الالتواءات التربيعية لمنحنانا، لكنها كلها متماثلة بنيويًا بعضها مع بعض. تذكّر أن هذا يعني أن لها العدد نفسه من النقاط، والزمر الجزئية نفسها، وما إلى ذلك. لذا لا يهم أي التواء معين نستخدمه؛ في الواقع، لا نحتاج حتى إلى انتقاء واحد.

نحن مهتمون أساسًا بالزمر الجزئية الموجودة على الالتواء، ما يعني أننا نحتاج إلى معرفة عدد نقاطه. لحسن الحظ، تبيّن أن عدّ مجموعة النقاط المشتركة على المنحنى والتوائه في الوقت نفسه أسهل. لنفعل ذلك:

لكل u غير صفري حتى المعيار p، إن كان u^3 + A*u^2 + u مربعًا في GF(p)، فهناك نقطتان على المنحنى الأصلي.
وإن كان المجموع أعلاه غير مربع في GF(p)، فهناك نقطتان على المنحنى الملتوي.

ينبغي أن يتضح أن هذين يجمعان إلى 2*(p-1) نقطة إجمالًا، بما أن هناك p-1 عددًا صحيحًا غير صفري في GF(p) ونقطتان لكل منها. لنكمل:

لكلٍّ من المنحنى الأصلي والتوائه نقطة (0, 0). هذه مجرد نقطة عادية، لا محايد الزمرة.
لكلٍّ من المنحنى الأصلي والتوائه نقطة مجردة في اللانهاية تقوم مقام محايد الزمرة.

إذن لدينا 2*p + 2 نقطة عبر المنحنيين. وبما أننا نعرف أصلًا عدد النقاط على المنحنى الأصلي، يمكننا بسهولة حساب رتبة الالتواء.

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

التحفظ الوحيد أنها لن تتمكن من استعادة السر كاملًا باستخدام نقاط خارج المنحنى، بل جزء منه فقط. لكننا نعرف كيف نتعامل مع ذلك.

إذن:

احسب رتبة الالتواء واعثر على عوامله الصغيرة. ينبغي أن يكون لرتبة هذا الالتواء مجموعة كبيرة تحت 2^24.
اعثر على نقاط بهذه الرتب. هذا بسيط:

a. اختر u عشوائيًا بترديد p وتحقق من أن u^3 + A*u^2 + u

      غير مربع في GF(p).

b. سمِّ رتبة الالتواء n. لإيجاد عنصر من الرتبة q،

      احسب ladder(u, n/q).

أرسل هذه النقاط إلى Alice لاستعادة أجزاء من سرّها.
عندما تستنفد كل الزمر الجزئية الصغيرة في الالتواء، استعد ما تبقى من سر Alice بهجوم الكنغر.

تلميح: قد تلاحظ أن ku = -ku، ما يؤدي إلى انفجار توافقي في مخارج CRT المحتملة. جرّب إرسال استعلامات إضافية لتضييق مجال الاحتمالات.

61. اختيار مفتاح بتوقيع مكرر في ECDSA (وRSA)

افترض أن لديك زوج رسالة وتوقيع. إن أعطيتك مفتاحًا عامًا يتحقق من التوقيع، فهل يمكنك الوثوق بأنني المؤلف؟

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

لننظر في حالة ECDSA.

أولًا، نفّذ ECDSA. إن كان تنفيذ DSA القديم لديك ما زال موجودًا، فينبغي أن يكون هذا مباشرًا. ومع ذلك، إليك تذكيرًا إن احتجته:

    function sign(m, d):
        k := random_scalar(1, n)
        r := (k * G).x
        s := (H(m) + d*r) * k^-1
        return (r, s)

    function verify(m, (r, s), Q):
        u1 := H(m) * s^-1
        u2 := r * s^-1
        R := u1*G + u2*Q
        return r = R.x

تذكّر أن كل العمليات القياسية بترديد n، رتبة نقطة الأساس G. و(d, Q) زوج مفاتيح الموقّع. وH(m) تجزئة الرسالة.

لاحظ أن دالة التحقق تتطلب جمع نقاط اعتباطيًا. هذا يعني أن سلم Montgomery لديك (الذي ينفّذ الضرب القياسي فقط) لن يعمل هنا. لا مشكلة كبيرة في ذلك؛ عُد ببساطة إلى تنفيذ Weierstrass القديم لديك.

بمجرد أن تنفّذ هذا، ولّد زوج مفاتيح لـ Alice واستخدمه لتوقيع رسالة m ما.

سيكون صعبًا على Eve إيجاد Q' للتحقق من هذا التوقيع لو كانت كل معطيات النطاق ثابتة. لكن معطيات النطاق قد لا تكون ثابتة --- بعض البروتوكولات تتيح للمستخدم تحديدها كجزء من مفتاحه العام.

لنعد ترتيب بعض الحدود. تأمل هذه المساواة:

    R = u1*G + u2*Q

لنجرِ بعض إعادة التجميع:

    R = u1*G + u2*(d*G)
    R = (u1 + u2*d)*G

اعتبر R وu1 وu2 ثابتة. هذا يترك سر Alice d ونقطة الأساس G. وبما أننا لا نعرف d، سنحتاج إلى اختيار زوج جديد من القيم تتحقق به المساواة. يمكننا فعل ذلك بالبدء من السر والعمل بشكل عكسي.

اختر d' عشوائيًا بترديد n.
احسب t := u1 + u2*d'.
احسب G' := t^-1 * R.
احسب Q' := d' * G'.
مفتاح Eve العام هو Q' مع معطيات النطاق (E(GF(p)), n, G'). وE(GF(p)) هو المنحنى الإهليلجي الذي اختارته Alice أصلًا.

لاحظ أن مفتاح Eve العام صالح تمامًا: فنقطة الأساس ونقطتها العامة كلتاهما عضوان في الزمرة الجزئية ذات الرتبة الأولية n. وبما أن E(GF(p)) وn لم تتغيرا عن مفتاح Alice العام، فينبغي أن تجتازا قواعد التحقق نفسها.

منتحلًا دور Eve، اشتق مفتاحًا عامًا ومعطيات نطاق للتحقق من توقيع Alice على الرسالة.

لنفعل الشيء نفسه مع RSA. الإعداد نفسه: لدينا رسالة ما وتوقيع عليها. كيف نصوغ مفتاحًا عامًا للتحقق من التوقيع؟

حسنًا، أولًا لننعش ذاكرتنا بشأن RSA. التحقق من التوقيع يبدو هكذا:

    s^e = pad(m) mod N

حيث (m, s) زوج الرسالة والتوقيع و(e, N) مفتاح Alice العام.

إذن ما نبحث عنه حقًا هو الزوج (e', N') الذي يجعل تلك المساواة تتحقق. إن كان هذا يبدو مألوفًا قليلًا، فمن حقه ذلك: فما نفعله هنا هو البحث عن اللوغاريتم المتقطع للعدد pad(m) بالنسبة إلى الأساس s.

نحن نعلم أن اللوغاريتمات المتقطعة يسهل حلها بـ Pohlig-Hellman في زمر لها كثير من الزمر الجزئية الصغيرة. واختيار الزمرة متروك لنا، فلا يمكن أن نفشل!

لكن ينبغي أن نتوخى بعض الحذر. فإن اخترنا أعدادنا الأولية بشكل خاطئ، فلن يوجد اللوغاريتم المتقطع.

حسنًا، تحقق من الطريقة:

اختر عددًا أوليًا p. إليك بعض الشروط على p:

a. ينبغي أن يكون p-1 أملس. مقدار النعومة متروك لك، لكنك ستحتاج

      إلى إيجاد اللوغاريتمات المتقطعة في كل من هذه الزمر الجزئية. يمكنك
      استخدام شيء مثل Shanks أو rho لـ Pollard لحسابها في
      زمن الجذر التربيعي.

b. ينبغي ألا يكون s في أي زمرة جزئية ليس pad(m) فيها. فإن كان كذلك،

      فلن يوجد اللوغاريتم المتقطع. أبسط ما تفعله هو
      التأكد من أن كليهما جذر أولي. للتحقق من أن عنصرًا g
      جذر أولي بترديد p، تحقق من أن:

          g^((p-1)/q) != 1 mod p

      من أجل كل عامل q للعدد p-1.

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

a. لا تعد استخدام أي من عوامل p-1 عدا 2. من الممكن

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

b. تأكد من أن p*q أكبر من معيار Alice N. هذا فقط

      للتأكد من أن التوقيع والرسالة المحشوّة سيتسعان تحت
      معيارك الجديد.

استخدم Pohlig-Hellman لاشتقاق ep = e' mod p وeq = e' mod q.
استخدم نظرية الباقي الصيني لجمع ep وeq معًا:

       e' = crt([ep, eq], [p-1, q-1])

معيارك العام هو N' = p * q.
يمكنك اشتقاق d' بالطريقة المعتادة.

سهل كالفطيرة. ستكون e' أكبر بكثير من الأس العام المعتاد، لكن هذا يظل مشروعًا.

بما أن توقيع RSA وفك التشفير عمليتان مكافئتان، يمكنك استخدام التقنية نفسها لنتائج مفاجئة أخرى. جرّب توليد نص مشفَّر عشوائي (أو مختار) وإنشاء مفتاح لفك تشفيره إلى نص صريح تختاره أنت!

62. هجمات استعادة المفتاح على ECDSA بقيم عشوائية وحيدة منحازة

رأينا في المجموعة 6 كيف أن «nonce» تسمية مغلوطة نوعًا ما لقيمة k في DSA. فهي أقرب إلى مفتاح عابر. والمؤسف أن أمان مفتاحك الخاص طويل الأمد معلّق عليها.

انكشاف قيمة nonce؟ تهانينا، لقد تخلصت للتو من مفتاحك السري.

قيمة nonce متوقعة؟ المثل نفسه.

وحتى بتكرار قيمة nonce فإنك تخسر كل شيء.

إلى أي مدى يمكننا أخذ هذا؟ تبيّن أن بعيدًا جدًا: حتى انحياز طفيف في توليد قيم nonce يكفي ليستعيد المهاجم مفتاحك الخاص. لنرَ كيف.

أولًا، لنوضّح ما نعنيه بقيمة nonce «منحازة». كل ما نحتاجه حقًا لهذا الهجوم هو معرفة بضع بتّات من قيمة nonce. للتبسيط، لنقل إن البايت المنخفض من كل قيمة nonce هو صفر. لذا خذ أي شيفرة كنت تستخدمها لتوليد قيم nonce واكتفِ بإخفاء البِتّات الثماني الأقل دلالة.

كيف يساعدنا هذا؟ لنراجع خوارزمية التوقيع:

    function sign(m, d):
        k := random_scalar(1, q)
        r := (k * G).x
        s := (H(m) + d*r) * k^-1
        return (r, s)

(ملاحظة سريعة: استخدمنا سابقًا "n" للدلالة على رتبة نقطة الأساس. في هذه المسألة سأستخدم "q" لتجنب تصادم الأسماء. تتعامل مع الأمر.)

ركّز على حساب s. لاحظ أنه إن كانت البتّات l المنخفضة من k منحازة إلى ثابت c ما، أمكننا إعادة كتابة k بالشكل b2^l + c. في حالتنا، c = 0، لذا سنعيد كتابة k بالشكل b2^l بدلًا من ذلك. هذا يعني أننا نستطيع ربط قيمتي r وs العامتين هكذا:

    s = (H(m) + d*r) * (b*2^l)^-1

بعض الجبر المباشر يوصلنا من هناك إلى هنا:

    d*r / (s*2^l) = (H(m) / (-s*2^l)) + b

تذكّر أن هذه الحسابات كلها بترديد q، رتبة نقطة الأساس. الآن، لنعرّف بعض البدائل:

    t =    r / ( s*2^l)
    u = H(m) / (-s*2^l)

الآن يمكن كتابة معادلتنا أعلاه هكذا:

    d*t = u + b

تذكّر أن b صغير. فبينما t وu والمفتاح السري d كلها بحجم q تقريبًا، فإن b بحجم q/2^l تقريبًا. إنه خطأ تقريب. ولأن b صغير جدًا، يمكننا أساسًا تجاهله والقول:

    d*t ~ u

بعبارة أخرى، u تقريب لـ d*t بترديد q. لنعجن الأعداد أكثر. بما أن هذا بترديد q، يمكننا بدلًا من ذلك القول:

    d*t ~ u + m*q
      0 ~ u + m*q - d*t

هذا المجموع لن يكون صفرًا حقًا --- إنه مجرد تقريب. لكنه سيكون أقل من حد ما، لنقل q/2^l. المغزى أنه سيكون صغيرًا جدًا بالنسبة إلى الحدود الأخرى في اللعبة.

يمكننا استخدام هذه الخاصية لاستعادة d إن كان لدينا ما يكفي من أزواج (u, t). لكن لفعل ذلك، نحتاج إلى معرفة قليل من الجبر الخطي. ليس كثيرًا، أعدك.

الجبر الخطي يتعلق بالمتجهات. يمكن أن يكون المتجه أي شيء تقريبًا، لكن للتبسيط سنقول إن المتجه تسلسل ثابت الطول من الأعداد. هناك أمران رئيسيان يمكننا فعلهما بالمتجهات: يمكننا جمعها ويمكننا ضربها بقياسات. لجمع متجهين، اجمع ببساطة مكوناتهما الزوجية. ولضرب متجه بقياس k، أضفه ببساطة إلى نفسه k مرة. (أو، على نحو مكافئ، اضرب كل عناصره في القياس.) تُسمى هاتان العمليتان معًا تركيبات خطية.

إن كانت لدينا مجموعة متجهات، نقول إنها تولّد فضاء متجهيًا. والفضاء المتجهي هو ببساطة النطاق الكامل للمتجهات الممكنة التي يمكننا توليدها بجمع متجهات مجموعتنا وضربها بقياسات. ونسمي مجموعة التوليد الدنيا أساسًا للفضاء المتجهي. و«الدنيا» تعني أن إسقاط أي من متجهاتنا من المجموعة سيؤدي إلى فضاء متجهي أصغر. أما المتجهات المضافة فإما ستكون زائدة (أي يمكن تعريفها كمجاميع لمتجهات موجودة) وإما ستعطينا فضاءً متجهيًا أكبر. لذا يمكنك التفكير في الأساس بأنه «بالضبط المناسب» للفضاء المتجهي الذي يولّده.

سنستخدم الأعداد الصحيحة فقط كقياسات. والفضاء المتجهي المولَّد باستخدام قياسات صحيحة فقط يُسمى شبيكة (lattice). الأفضل تصوّر ذلك في المستوى ثنائي الأبعاد. افترض أن مجموعة متجهاتنا هي {(3, 4), (2, 1)}. تشمل الشبيكة كل التركيبات الصحيحة لهذين الزوجين. يمكنك رسم هذا على الورق لتستوعب الفكرة؛ وينبغي أن تنتهي بنمط من النقاط المنقّطة نوعًا ما.

قلنا إن الأساس بالحجم المناسب تمامًا للفضاء المتجهي الذي يولّده، لكن لا ينبغي أن يُفهم من ذلك أنه وحيد. في الواقع، أي من الشبيكات التي سنهمّ بها لها عدد لا نهائي من الأسس الممكنة. المتطلبان الوحيدان أن يولد الأساس الفضاء وأن يكون الأساس دنيويًا في الحجم. بهذا المعنى، كل أسس شبيكة معينة متساوية.

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

لماذا يحب الناس هذه الأسس الأصغر؟ أساسًا لأنها أكثر كفاءة في الحساب. وبصراحة، لا يهم كثيرًا سبب حب الناس لها. المهم أن لدينا طرقًا فعّالة نسبيًا لـ«اختزال» الأساس. بالنظر إلى أساس مدخل، يمكننا إنتاج أساس مكافئ لكن بمتجهات أقصر بكثير. كم أقصر؟ حسنًا، ربما ليس الأقصر الممكن، لكنه قصير جدًا جدًا.

وهذا يتضمن نهجًا أنيقًا حقًا لحل المسائل:

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

انتظر، هذا كل شيء؟ نعم، سمعتني --- اختزال أساس الشبيكة تقنية بالغة القوة. لقد سحقت وحدها أنظمة تشفير حقائب الظهر في الثمانينيات، وجمعت كومة من الجوائز منذ ذلك الحين. ما دمتَ قادرًا على تعريف شبيكة تحتوي متجهًا قصيرًا يرمّز حل مسألتك، يمكنك تشغيلها لصالحك.

من الواضح أن تعريف الشبيكة هو الجزء الصعب. كيف نرمّز ECDSA؟ حسنًا، عندما توقفنا، كان لدينا التقريب التالي:

    0 ~ u + m*q - d*t

افترض أننا جمعنا مجموعة من التوقيعات. عندها يصبح ذلك التقريب الواحد كثيرًا:

    0 ~ u1 + m1*q - d*t1
    0 ~ u2 + m2*q - d*t2
    0 ~ u3 + m3*q - d*t3
    0 ~ u4 + m4*q - d*t4
    0 ~ u5 + m5*q - d*t5
    0 ~ u6 + m6*q - d*t6
    ...
    0 ~ un + mn*q - d*tn

معامل كل u هو دائمًا 1، ومعامل t هو دائمًا المفتاح السري d. لذا يبدو طبيعيًا أن نصطف هذه في متجهين:

    bt = [ t1 t2 t3 t4 t5 t6 ... tn ]

    bu = [ u1 u2 u3 u4 u5 u6 ... un ]

يحتوي كل تقريب أيضًا على عامل ما للعدد q. لكن المعامل m مختلف في كل مرة. هذا يعني أننا سنحتاج إلى متجه منفصل لكل واحد:

    b1 = [  q  0  0  0  0  0 ...  0 ]

    b2 = [  0  q  0  0  0  0 ...  0 ]

    b3 = [  0  0  q  0  0  0 ...  0 ]

    b4 = [  0  0  0  q  0  0 ...  0 ]

    b5 = [  0  0  0  0  q  0 ...  0 ]

    b6 = [  0  0  0  0  0  q ...  0 ]

            ...              ...

    bn = [  0  0  0  0  0  0 ...  q ]

    bt = [ t0 t1 t2 t3 t4 t5 ... tn ]

    bu = [ u0 u1 u2 u3 u4 u5 ... un ]

أترى كيف تتطابق الأعمدة القاطعة لمتجهات الصفوف مع التقريبات التي جمعناها أعلاه؟ لاحظ أيضًا أن الشبيكة المعرّفة بهذا الأساس تحتوي على الأقل على متجه قصير معقول يهمّنا:

    bu - d*bt + m0*b1 + m1*b2 + m2*b3 ... + mn*bn

لكن لدينا مشكلة: حتى إن كان هذا المتجه ضمن أساسنا المختزل، فليس لدينا طريقة لتحديده. يمكننا حل ذلك بإضافة عمودين جديدين.

    b1 = [  q  0  0  0  0  0 ...  0  0  0 ]

    b2 = [  0  q  0  0  0  0 ...  0  0  0 ]

    b3 = [  0  0  q  0  0  0 ...  0  0  0 ]

    b4 = [  0  0  0  q  0  0 ...  0  0  0 ]

    b5 = [  0  0  0  0  q  0 ...  0  0  0 ]

    b6 = [  0  0  0  0  0  q ...  0  0  0 ]

            ...              ...

    bn = [  0  0  0  0  0  0 ...  q  0  0 ]

    bt = [ t0 t1 t2 t3 t4 t5 ... tn ct  0 ]

    bu = [ u0 u1 u2 u3 u4 u5 ... un  0 cu ]

أضفنا عمودين جديدين بقيم إشارية في bt وbu. هذا سيتيح لنا تحديد ما إذا كان هذان المتجهان مضمّنين في أي من متجهات الخرج وبأي نسب. (ليست هذه المشكلة الوحيدة التي يحلها هذا. فمجموعة متجهاتنا الأخيرة لم تكن حقًا أساسًا، لأننا كان لدينا n+2 متجهًا من الدرجة n، فكانت هناك بوضوح بعض الزوائد فيها.)

يمكننا تحديد المتجه الذي نبحث عنه بالبحث عن cu في الخانة الأخيرة من كل متجه في أساسنا المختزل. حدسنا أن الخانة المجاورة ستحتوي -d*ct، ويمكننا القسمة على -ct لاستعادة d.

حسنًا. للمضي قدمًا، نحتاج إلى الخوض في تفاصيل اختزال الأساس. هناك استراتيجيات مختلفة لإيجاد أساس مختزل لشبيكة، لكننا سنركز على خوارزمية بسيطة وفعّالة متعددة الحدود: Lenstra-Lenstra-Lovasz (LLL).

معظم الناس لا ينفّذون LLL. بل يستخدمون مكتبة، وهناك عدة مكتبات ممتازة. NTL خيار شائع.

لأغراض تعليمية فقط، سنكتب تنفيذنا الخاص.

إليك بعض الشيفرة الزائفة:

    function LLL(B, delta):
        B := copy(B)
        Q := gramschmidt(B)

        function mu(i, j):
            v := B[i]
            u := Q[j]
            return (v*u) / (u*u)

        n := len(B)
        k := 1

        while k < n:
            for j in reverse(range(k)):
                if abs(mu(k, j)) > 1/2:
                    B[k] := B[k] - round(mu(k, j))*B[j]
                    Q := gramschmidt(B)

            if (Q[k]*Q[k]) >= (delta - mu(k, k-1)^2) * (Q[k-1]*Q[k-1]):
                k := k + 1
            else:
                B[k], B[k-1] := B[k-1], B[k]
                Q := gramschmidt(B)
                k := max(k-1, 1)

        return B

B هو أساسنا المدخل. Delta معامل بحيث 0.25 < delta <=

يمكنك ببساطة ضبطه على 0.99 ونسيانه.

Gram-Schmidt خوارزمية لتحويل أساس إلى أساس مكافئ من متجهات متعامدة متبادلة (كلمة فاخرة تعني «متعامدة»). إنها بديهية تمامًا:

    function proj(u, v):
        if u = 0:
            return 0
        return ((v*u) / (u*u)) * u

    function gramschmidt(B):
        Q := []
        for i, v in enumerate(B):
            Q[i] := v - sum(proj(u, v) for u in Q[:i])
        return Q

تجد proj إسقاط v على u. هذا أساسًا الجزء من v المتجه في «اتجاه» u نفسه. وإن كان u وv متعامدين، فهذا هو المتجه الصفري. وGram-Schmidt يجعل الأساس متعامدًا بالتكرار على الأصل وطرح هذه الإسقاطات.

عودة إلى LLL. أفضل طريقة للإحساس بكيفية عمله وسبب عمله هي تنفيذه واختباره على بعض الأمثلة الصغيرة بكثير من مخرجات التنقيح. لكن أساسًا: نصعد وننزل في الأساس B، مقارنين كل متجه b بالأساس المتعامد Q. وكلما وجدنا متجهًا q في Q يحاذي b في معظمه، طرحنا تقريبًا صحيحًا لإسقاط q على b. تذكّر أن الشبيكة تتعامل بمعاملات صحيحة، وعليّنا نحن أيضًا. بعد كل تكرار، نستخدم بعض القواعد الإرشادية لتقرير ما إذا كان ينبغي أن نتقدم أو نتأخر في B، وما إذا كان ينبغي أن نبدّل بعض الصفوف، وهكذا.

أمر آخر: الوصف أعلاه لـ LLL ساذج جدًا وغير فعّال. على الأرجح لن يكون سريعًا بما يكفي لأغراضنا، لذا قد تحتاج إلى تحسينه قليلًا. مكان جيد للبدء هو عدم إعادة حساب مصفوفة Q كاملة في كل تحديث.

إليك أساس اختباري:

    b1 = [  -2    0    2    0]
    b2 = [ 1/2   -1    0    0]
    b3 = [  -1    0   -2  1/2]
    b4 = [  -1    1    1    2]

يختزل إلى هذا (مع delta = 0.99):

    b1 = [ 1/2   -1    0    0]
    b2 = [  -1    0   -2  1/2]
    b3 = [-1/2    0    1    2]
    b4 = [-3/2   -1    2    0]

نسيت أن أذكر: ستحتاج إلى كتابة تنفيذك ليعمل على متجهات من الأعداد النسبية. وإن كانت لديك أعداد عائمة دقيقة لانهائيًا، فستفي بالغرض أيضًا.

كل ما تبقى هو ربط بعض الأطراف المترهلة. أولًا، كيف نختار قيمنا الإشارية ct وcu؟ هذا تفصيل تنفيذي نوعًا ما، لكننا نريد أن «نوازن» أحجام المدخلات في متجهنا المستهدف. وبما أننا نتوقع أن تكون كل المدخلات الأخرى بحجم q/2^l تقريبًا:

    ct = 1/2^l
    cu = q/2^l

تذكّر أن ct ستُضرب في -d، وd بحجم q تقريبًا.

حسنًا، أصبحت أخيرًا مستعدًا لتشغيل الهجوم:

ولّد مفتاح ECDSA السري d.
وقّع مجموعة من الرسائل باستخدام d ومولّد قيم nonce المنحاز لديك.
بوصفك المهاجم، اجمع أزواج (u, t) لديك. يمكنك التجريب في الكمية. مع انحياز قدره ثماني بتّات في قيمة nonce، أحصل على نتائج جيدة بعشرين توقيعًا فقط. النتائج قد تختلف.
احشُ قيمك في مصفوفة واختزلها بـ LLL. فكّر في اللعب بمصفوفات أصغر قليلًا للإحساس بالمدة التي سيستغرقها التشغيل.
في الأساس المختزل، اعثر على متجه مدخله الأخير q/2^l. هناك فرصة جيدة أن يكون مدخله قبل الأخير -d/2^l. استخرج d.

63. هجمات استعادة المفتاح على GCM بقيم عشوائية وحيدة متكررة

GCM هو أكثر أوضاع شيفرات الكتل انتشارًا للتشفير الموثَّق مع بيانات مرافقة (AEAD). إنه أساسًا مجرد وضع CTR مع دالة MAC غريبة ملفوفة حوله. وتعمل دالة MAC بتقييم كثيرة حدود على GF(2^128).

أتذكر مقدار المشاكل التي يسببها تكرار قيمة nonce لتشفير CTR؟ الأمر نفسه صحيح هنا: يستطيع المهاجم دمج النصوص المشفَّرة معًا بـ XOR واستعادة النص الصريح بطرق إحصائية.

لكن هناك نتيجة أكثر تدميرًا لـ GCM: إنه يسرّب مفتاح المصادقة فورًا!

وإليك الصورة عالية المستوى:

تعمل دالة MAC في GCM (وهي GMAC) ببناء كثيرة حدود معاملاتها هي كتل البيانات المرافقة (AD)، وكتل النص المشفَّر (C)، وكتلة ترمّز طول AD وC، وكتلة تُستخدم لـ«قناع» الخرج. هكذا نوعًا ما:

       AD*y^3 + C*y^2 + L*y + S

لحساب MAC، نعوّض بمفتاح المصادقة مكان y ونقيّم.

AD وC وطولهما معروفان. ومن أجل رسالة معينة، يعرف المهاجم كل شيء عن كثيرة حدود MAC إلا كتلة القناع.
تُولَّد كتلة القناع باستخدام المفتاح وقيمة nonce فقط. وإن تكررت قيمة nonce، تكرر القناع. وإن تمكّنا من جمع رسالتين مشفَّرتين تحت قيمة nonce نفسها، فستكونان قد استخدمتا القناع نفسه.
في هذا الحقل، الجمع هو XOR. يمكننا دمج رسالتينا معًا بـ XOR لـ«محو» القناع واستعادة كثيرة حدود معلومة مفتاح المصادقة جذر لها. ويمكننا تحليل كثيرة الحدود لاستعادة مفتاح المصادقة فورًا.

ربما تبدو الخطوة الأخيرة سحرية قليلًا، لكنك لا تحتاج فعلًا إلى فهمها لتنفيذ الهجوم: يمكنك حرفيًا تعويض القيم الصحيحة في نظام جبر حاسوبي مثل SageMath والضغط على «factor».

لكن هذا غير مُرضٍ. لم تصل إلى هنا لتهزم اللعبة في الوضع السهل، أليس كذلك؟

لم أظن ذلك. الآن، لنغص في دالة MAC تلك. كما قلت، كثيرة حدود على GF(2^128).

حتى الآن، كل الحقول التي عملنا بها كانت بحجم أولي p، أي GF(p). وتبيّن أننا نستطيع بناء GF(q) من أجل أي q = p^k لأي عدد صحيح موجب k. وGF(p) = GF(p^1) مجرد صيغة واحدة شائعة في التشفير. وأخرى هي GF(2^k)، وفي هذه الحالة لدينا GF(2^128).

بالنسبة إلى GF(2^k)، سنمثّل عناصرها بكثيرات حدود معاملاتها في GF(2). وهذا يعني أن كل معامل سيكون 0 أو

قبل أن نبدأ الحديث عن حقل معين (أي اختيار معين لـ k)، لنتحدث عن كثيرات الحدود هذه فقط. إليك بعضها:

                    0
                    1
                x
                x + 1
          x^2
          x^2     + 1
          x^2 + x
          x^2 + x + 1
    x^3
    x^3           + 1
    x^3       + x
    x^3       + x + 1
    x^3 + x^2
    x^3 + x^2     + 1
    x^3 + x^2 + x
    x^3 + x^2 + x + 1
    ...

وهكذا دواليك.

إن أغمضت عينيك قليلًا فستبدو كالتوسعات الثنائية للأعداد الصحيحة المتزايدة من الصفر. وهذا ملائم لأنه يمنحنا اختيارًا واضحًا للتمثيل بأعداد صحيحة غير موقّعة.

الآن نحتاج إلى بعض الدوال الأولية للعمل على كثيرات الحدود هذه. لنتسلح:

الجمع والطرح بين كثيرات حدود GF(2) بسيطان حقًا: كلاهما مجرد دالة XOR.
الضرب والقسمة أعقد قليلًا، لكن كليهما يقاربان الخوارزميات التي تعلمتها في المدرسة الابتدائية. ها هما:

       function mul(a, b):
            p := 0

            while a > 0:
                if a & 1:
                    p := p ^ b

                a := a >> 1
                b := b << 1

            return p

        function divmod(a, b):
            q, r := 0, a

            while deg(r) >= deg(b):
                d := deg(r) - deg(b)
                q := q ^ (1 << d)
                r := r ^ (b << d)

            return q, r

دالة deg(a) تعيد درجة كثيرة الحدود. فمن أجل كثيرة الحدود x^4 + x + 1، ينبغي أن تعيد 4. ومن أجل 1، ينبغي أن تعيد 0. ومن أجل 0، ينبغي أن تعيد قيمة سالبة ما.

الآن بعد أن لدينا نواة صغيرة من الدوال للعمل على كثيرات الحدود في GF(2)، لنرَ كيف يمكننا استخدامها لتمثيل عناصر في GF(2^k). ولنكن محددين، لنقل k = 4.

مجموعة عناصرنا هي المجموعة نفسها المذكورة أعلاه:

                    0
                    1
                x
                x + 1
          x^2
          x^2     + 1
          x^2 + x
          x^2 + x + 1
    x^3
    x^3           + 1
    x^3       + x
    x^3       + x + 1
    x^3 + x^2
    x^3 + x^2     + 1
    x^3 + x^2 + x
    x^3 + x^2 + x + 1

الجمع والطرح بلا تغيير. ما زلنا ندمج العناصر بـ XOR فقط.

أما الضرب فمختلف. كما في الحقول التي حجمها p، نحتاج إلى إجراء اختزالات ترديدية بعد كل ضرب للإبقاء على عناصرنا في النطاق. وسيكون معيارنا x^4 + x + 1. وإن بدا هذا اعتباطيًا قليلًا، فهو كذلك فعلًا --- يمكننا استخدام أي كثيرة حدود واحدية من الدرجة الرابعة غير قابلة للتحليل على GF(2). والكثيرة الحدود غير القابلة للتحليل تشبه نوعًا ما العدد الأولي في هذا الإطار.

إليك modmul ساذجة:

    function modmul(a, b, m):
        p := mul(a, b)
        q, r := divmod(p, m)
        return r

عمليًا، سنريد أن نكون أكثر كفاءة. لذا سنشابك خطوات الضرب مع خطوات الاختزال:

    function modmul(a, b, m):
        p := 0

        while a > 0:
            if a & 1:
                p := p ^ b

            a := a >> 1
            b := b << 1

            if deg(b) = deg(m):
                b := b ^ m

        return p

يمكنك تنفيذ النسختين لتثبت لنفسك أن الخرج هو نفسه.

القسمة مختلفة أيضًا. تذكّر أننا في الحقول التي حجمها p عرّفناها كضرب بالمعكوس. لذا ستحتاج إلى كتابة دالة modinv. وينبغي أن يكون تحويل دالة modinv الصحيحة الموجودة لديك سهلًا جدًا. سأترك ذلك لك.

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

حسنًا، الآن بعد أن أصبحت سيد GF(2^k)، يمكننا أخيرًا الحديث عن GCM. كما قلت (قبل كلمات كثيرة): وضع CTR للتشفير، وMAC غريبة في GF(2^128).

إليك معيار ذلك الحقل:

    x^128 + x^7 + x^2 + x + 1

اختير حجم هذا الحقل تحديدًا شديدًا ليتطابق مع عرض شيفرة كتل بطول 128 بتًا. يمكننا تحويل كتلة إلى عنصر حقل ببداهة؛ فالبتّة اليسرى هي معامل x^0، وهكذا دواليك.

وصفت MAC على مستوى عالٍ جدًا. وإليك صورة أكثر تفصيلًا:

خذ مفتاح AES لديك واستخدمه لتشفير كتلة من الأصفار:

       h := E(K, 0)

h هو مفتاح المصادقة لديك. حوّله إلى عنصر حقل.

احشُ بايتات البيانات المرافقة (AD) بالأصفار لتقبل القسمة على طول الكتلة. وإن كانت مصطفة أصلًا على كتلة، فاتركها كما هي. افعل الشيء نفسه مع النص المشفَّر. سلسلها معًا بحيث يصبح لديك شيء مثل:

       a0 || a1 || c0 || c1 || c2

أضف كتلة أخيرة تصف طول AD وطول النص المشفَّر. الأطوال الأصلية، لا الأطوال المحشوّة؛ أطوال بالبتّات، لا بالبايتات. هكذا:

       len(AD) || len(C)

خذ h وسلسلة كتلك وافعل هذا:

       g := 0
       for b in bs:
           g := g + b
           g := g * h

حوّل الكتل إلى عناصر حقل أولًا، بالطبع. والقيمة الناتجة g تجزئة بمفتاح لكتل الإدخال.

يأخذ GCM قيمة nonce بطول 96 بتًا. افعل بها هذا:

       s := E(K, nonce || 1)
       t := g + s

من الناحية المفهومية، نُقنّع التجزئة بقيمة سرية مشتقة من قيمة nonce. المزيد عن ذلك لاحقًا.

t هو وسمك. حوّله مرة أخرى إلى كتلة وأرسله.

نفّذ GCM. استخدم AES-128 كشيفرة الكتل لديك. يمكنك على الأرجح إعادة استخدام أي شيء كان لديك سابقًا لوضع CTR. الشيء الجديد المهم الذي يجب تنفيذه هنا هو MAC. الوصف أعلاه موجز وغير رسمي؛ راجع المواصفة للنقاط الأدق. وبما أنك تملك أصلًا الأدوات للعمل في GF(2^k)، فلا ينبغي أن يستغرق هذا وقتًا طويلًا.

حسنًا. لنعد التفكير في نظرتنا إلى MAC. سنستخدم حمولتنا النموذجية من أعلاه. ها هي:

    t = (((((((((((h * a0) + a1) * h) + c0) * h) + c1) * h) + c2) * h) + len) * h) + s

كلام ثقيل نوعًا ما. لنعد كتابته:

    t = a0*h^6 + a1*h^5 + c0*h^4 + c1*h^3 + c2*h^2 + len*h + s

بعبارة أخرى، نحسب MAC ببناء كثيرة الحدود هذه:

    f(y) = a0*y^6 + a1*y^5 + c0*y^4 + c1*y^3 + c2*y^2 + len*y + s

وحساب t = f(h).

تذكّر: بوصفنا مهاجمين، لا نعرف كثيرة الحدود كاملة. نحن نعرف كل معاملات AD والنص المشفَّر، ونعرف t = f(h)، لكننا لا نعرف القناع s.

ماذا يحدث إن كررنا قيمة nonce؟ لنفترض هذه الحمولة الإضافية المشفَّرة تحت قيمة nonce نفسها:

    b0 || d0 || d1

هذه كتلة واحدة من AD وكتلتان من النص المشفَّر. ستبدو MAC هكذا:

    t = b0*h^4 + d0*h^3 + d1*h^2 + len*h + s

لنضعهما جنبًا إلى جنب (ونعيد كتابتهما قليلًا):

    t0 = a0*h^6 + a1*h^5 + c0*h^4 + c1*h^3 + c2*h^2 + l0*h + s
    t1 =                   b0*h^4 + d0*h^3 + d1*h^2 + l1*h + s

أترى كيف أن قناعي s متطابقان؟ إنهما يعتمدان فقط على قيمة nonce ومفتاح التشفير. وبما أن الجمع في حقلنا هو XOR، يمكننا جمع هاتين المعادلتين معًا وسينمحو ذلك القناع تمامًا:

    t0 + t1 = a0*h^6 + a1*h^5 + (c0 + b0)*h^4 + (c1 + d0)*h^3 +
              (c2 + d1)*h^2 + (l0 + l1)*h

وأخيرًا، سنجمع كل الحدود في طرف واحد:

    0 = a0*h^6 + a1*h^5 + (c0 + b0)*h^4 + (c1 + d0)*h^3 +
        (c2 + d1)*h^2 + (l0 + l1)*h + (t0 + t1)

ونعيد كتابتها كثيرة حدود في y:

    f(y) = a0*y^6 + a1*y^5 + (c0 + b0)*y^4 + (c1 + d0)*y^3 +
           (c2 + d1)*y^2 + (l0 + l1)*y + (t0 + t1)

الآن نعرف كثيرة حدود f(y)، ونعرف أن f(h) = 0. بعبارة أخرى، مفتاح المصادقة جذر. هذا يعني أن كل ما علينا فعله هو تحليل المعادلة للحصول على قائمة قصيرة جدًا من المرشحين لمفتاح المصادقة. وتبيّن أن هذا ليس صعبًا كثيرًا، لكننا سنحتاج إلى مزيد من الأدوات.

أولًا، نحتاج إلى القدرة على العمل على كثيرات حدود معاملاتها في GF(2^128).

(لا تختلط عليك الأمور: استخدمنا سابقًا كثيرات حدود معاملاتها في GF(2) لتمثيل عناصر في GF(2^128). الآن نبني فوق ذلك للعمل على كثيرات حدود معاملاتها في GF(2^128).)

أبسط تمثيل هو على الأرجح مجرد مصفوفة من عناصر الحقل. وستكون الخوارزميات كلها أساسًا كما في أعلاه، لذا لن أعيد سردها هنا. الفرق الوحيد أنك ستحتاج إلى نداء دوالك الأولية لكثيرات حدود GF(2^k) بدلًا من عوامل الحساب المدمجة في لغتك.

وبعد تجاوز ذلك، لنبدأ التحليل. تحليل كثيرة حدود على حقل منتهٍ يعني فصلها إلى كثيرات حدود أصغر غير قابلة للتحليل على الحقل. تذكّر أن كثيرات الحدود غير القابلة للتحليل تشبه الأعداد الأولية نوعًا ما.

لتحليل كثيرة حدود، نمضي في ثلاث (بل أربع) مراحل:

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

التحليل الخالي من المربعات والتحليل إلى درجات متمايزة كلاهما سهل التنفيذ. ابحث عنهما على ويكيبيديا وابدأ العمل.

أريد التركيز على التحليل إلى درجات متساوية. تعرّف على Cantor-Zassenhaus:

    function edf(f, d):
        n := deg(f)
        r := n / d
        S := {f}

        while len(S) < r:
            h := random_polynomial(1, f)
            g := gcd(h, f)

            if g = 1:
                g := h^((q^d - 1)/3) - 1 mod f

            for u in S:
                if deg(u) = d:
                    continue

                if gcd(g, u) =/= 1 and gcd(g, u) =/= u:
                    S := union(S - {u}, {gcd(g, u), u / gcd(g, u)})

        return S

إنها رائعة نوعًا ما.

تذكّر أننا قلنا سابقًا إن حقلًا منتهيًا حجمه p^k يمكن تمثيله بكثيرة حدود في GF(p) بترديد أي كثيرة حدود واحدية غير قابلة للتحليل من الدرجة k؟ خذ لحظة لتقنع نفسك بأن حقلًا حجمه q^d يمكن تمثيله بكثيرات حدود في GF(q) بترديد كثيرة حدود من الدرجة d.

f هو حاصل ضرب r كثيرة حدود من الدرجة d. كل منها معيار صالح لحقل منتهٍ حجمه q^d. وكل حقل بهذا الحجم يحتوي زمرة ضربية حجمها q^d - 1. وبما أن q^d - 1 دائمًا يقبل القسمة على 3 (في حالتنا)، فكل زمرة بهذا الحجم لها زمرة جزئية حجمها 3. وهي تحتوي المحايد الضربي (1) وعنصرين آخرين.

لدينا حيلة بسيطة لإجبار العناصر على الدخول في تلك الزمرة الجزئية: ارفعها ببساطة إلى الأس (q^d - 1)/3. وعندما نجبر عنصرنا العشوائي على الدخول في تلك الزمرة الجزئية، هناك احتمال 1/3 أن نهبط على 1. وهذا يعني أننا عندما نطرح 1، هناك احتمال 1/3 أن نكون على 0.

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

لذا نفعلها: ولّد كثيرة حدود ما، وارفعها إلى (q^d - 1)/3، واطرح 1. (كل ذلك بترديد f، بالطبع.) احسب القاسم المشترك الأكبر لهذه الكثيرة حدود ولكل من مركباتنا المتبقية. من أجل أي عامل متبقٍ معين، هناك احتمال 1/3 أن تكون كثيرة حدود لدينا مضاعفًا. بعبارة أخرى، ينبغي أن تكشف عواملنا عن نفسها بسرعة كبيرة.

واصل فعل هذا حتى تتحلل الكثيرة كلها إلى أجزاء غير قابلة للتحليل.

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

    y + c

حيث c عنصر ثابت في GF(2^128). وهو أيضًا مرشح للمفتاح. من الممكن أن تنتهي ببضعة عوامل من الدرجة الأولى كهذه. وسيكون المفتاح أحدها.

وإن كان لديك أكثر من مرشح واحد، فهناك طريقتان لتضييق القائمة:

استعد زوجًا آخر من الرسائل المشفَّرة تحت قيمة nonce نفسها. أجرِ التحليل مرة أخرى وحدّد العوامل المشتركة. وعلى الأرجح سيكون المفتاح العامل الوحيد.
جرّب ببساطة تزويرًا بكل مرشح. هذا على الأرجح أسهل.

64. هجمات استعادة المفتاح على GCM مع MAC مقتطع

هذا هو المفضل لدي.

من الشائع إلى حد ما استخدام وسم MAC مقتطع. على سبيل المثال، قد تكون تصادق بـ HMAC-SHA256 وتقصّر الوسم إلى 128 بتًا. الفكرة أنك توفر بعض النطاق أو التخزين وتبقى بمستوى أمان مقبول.

هذا مطلب معقول تمامًا.

في بعض البروتوكولات، قد تذهب بهذا إلى أقصى حد. فإن كان طرفان يتبادلان الكثير من الحزم الصغيرة، وكانت قيمة تزوير أي حزمة واحدة منخفضة جدًا، فقد يستخدمان وسمًا بطول 16 بتًا ويتوقعان 16 بتًا من الأمان.

في GCM، هذه كارثة.

لنرَ كيف، سنراجع أولًا دالة MAC في GCM. نجري حسابًا هكذا:

    t = s + c1*h + c2*h^2 + c3*h^3 + ... + cn*h^n

نجري بعض التغييرات في الترميز هنا للراحة؛ وأبرزها أننا نستخدم فهرسة تبدأ من الواحد. الكتلة c1 ترمّز الطول، و[c2, cn] كتل من النص المشفَّر.

وسنتجاهل هنا أيضًا احتمال وجود كتل AD، لأنها لا تهم كثيرًا لأغراضنا.

تذكّر أن معاملاتنا (ومفتاح المصادقة h) عناصر في GF(2^128). وقد رأينا عدة تمثيلات مختلفة، وهي كثيرات الحدود في GF(2) والأعداد الصحيحة غير الموقّعة. وسنضيف إلى ذلك تمثيلًا آخر: متجهًا من الدرجة 128 على GF(2). إنه أساسًا مجرد متجه بتّات؛ ليس مختلفًا كثيرًا عن أي من تمثيلَينا السابقين، لكننا نريد أن نضع عقولنا في وضع الجبر الخطي.

المفهوم الأساسي الذي نريد استكشافه هنا هو أن عمليات معينة في GF(2^128) خطية.

إحداها الضرب بثابت. افترض أن لدينا هذه الدالة:

    f(y) = c*y

حيث c وy عنصران في GF(2^128). هذه الدالة خطية في بتّات y. وهذا يعني أن هذه الدالة مكافئة:

    g(y) = c*y[0] + c*y[1] + c*y[2] + ... + c*y[127]

أي دالة خطية يمكن تمثيلها بضرب مصفوفات. لذا إن اعتبرنا y متجهًا، يمكننا بناء مصفوفة Mc بحيث:

    Mc*y = f(y) = c*y

لبناء Mc، احسب ببساطة c1 وcx وcx^2 و... وcx^127، وحوّل كل حاصل ضرب إلى متجه، واجعل هذه المتجهات أعمدة مصفوفتك. يمكنك التحقق بإجراء ضرب المصفوفة على y وفحص النتيجة. سأفترض أنك تعرف كيف يعمل ضرب المصفوفات أو لديك وصول إلى ويكيبيديا للبحث عنه.

التربيع خطي أيضًا. السبب أن (a + b)^2 = a^2 + b^2 في GF(2^128). مجددًا، هذا يعني أننا نستطيع استبدال هذه الدالة:

    f(y) = y^2

بضرب مصفوفة. مجددًا، احسب 1^2 وx^2 و(x^2)^2 و... و (x^127)^2، وحوّل النتائج إلى متجهات، واجعلها أعمدة. ثم تحقق من أن:

    Ms*y = f(y) = y^2

حسنًا، لنضع هذه المصفوفات جانبًا الآن. لتزوير نص مشفَّر c'، سنبدأ بنص مشفَّر صالح c ونقلب بعض البتّات، آملين أن:

    sum(ci * h^i) = sum(ci' * h^i)

وهناك طريقة أخرى لكتابة هذا:

    sum((ci - ci') * h^i) = 0

وإن جعلنا ei = ci - ci'، يمكننا تبسيط هذا:

    sum(ei * h^i) = 0

لاحظ أننا إن تركنا كتلة دون مساس، فإن ei = ci - ci' = 0. سنترك معظم قيم ei = 0. في الواقع، سنقلب البتّات فقط في الكتل di = e(2^i). هذه هي الكتل d0 وd1 وd2 و... وdn (لاحظ أننا عدنا إلى فهرسة تبدأ من الصفر) بحيث:

    sum(di * h^(2^i)) = 0

نأمل أن يساوي صفرًا، على أي حال. ربما من الأفضل أن نقول:

    sum(di * h^(2^i)) = e

حيث e كثيرة حدود خطأ ما. بعبارة أخرى، الفرق في وسم MAC الناتج عن قلبنا للبتّات.

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

    sum(Mdi * Ms^i * h) = e
    sum(Mdi * Ms^i) * h = e

    Ad = sum(Mdi * Ms^i)

    Ad * h = e

نريد إيجاد Ad بحيث Ad * h = 0.

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

    e[0] = Ad[0] * h
    e[1] = Ad[1] * h
    e[2] = Ad[2] * h
    e[3] = Ad[3] * h
    ...

بعبارة أخرى، e[i] هو الضرب الداخلي للصف i من Ad مع h. وإن استطعنا إجبار صفوف من Ad على الصفر، أمكننا إجبار حدود كثيرة حدود الخطأ على الصفر. وكل صف نجبره على الصفر سيضاعف فرصنا في التزوير أساسًا.

افترض أن MAC بطول 16 بتًا. إن استطعنا قلب البتّات وإجبار ثمانية صفوف من Ad على الصفر، فذاك ثماني بتّات من MAC نعلم أنها صحيحة. ويمكننا قلب البتّات المتبقية باحتمال 2^-8 للتزوير، وهو أفضل بكثير من المتوقع 2^-16!

تبيّن أنه من السهل حقًا إجبار صفوف Ad على الصفر. فـ Ad مجموع مجموعة من العمليات الخطية. وهذا يعني أننا نستطيع ببساطة تحديد أي بتّات من d0 وd1 و... وdn تؤثر في أي بتّات من Ad وقلبها وفقًا لذلك.

في الواقع، لنترك d0 وشأنه. فهو الكتلة التي ترمّز طول النص المشفَّر. وقد تتعقد الأمور بسرعة إن بدأنا العبث به.

ما زال لدينا d1 و... وdn للعب بها. هذا يعني n*128 بتّة يمكننا قلبها. وبما أن صفوف Ad كل منها 128 بتًا، فسيتعين علينا الاكتفاء بإجبار n-1 منها على الصفر. نحتاج إلى إبقاء بعض البتّات للعب بها.

تحقق من الاستراتيجية: سنبني مصفوفة اعتماد T بعدد n*128 عمودًا و(n-1)*128 صفًا. كل عمود يمثّل بتّة يمكننا قلبها، وكل صف يمثّل خلية من Ad (بالقراءة من اليسار إلى اليمين، ومن الأعلى إلى الأسفل). وتسجّل الخلايا التي يتقاطعان فيها ما إذا كانت بتّة حرة معينة تؤثر في بتّة معينة من Ad.

كرّر على الأعمدة. ابنِ الـ Ad الافتراضي الذي ستحصل عليه بقلب البتّة المقابلة فقط. كرّر على أول (n-1)*128 خلية من Ad واضبط الخلايا المقابلة في هذا العمود من T.

بعد فعل هذا لكل عمود، ستكون T مليئة بالآحاد والأصفار. نبحث عن مجموعات من قلبات البتّات تجعل أول n-1 صفًا أصفارًا. بعبارة أخرى، نبحث عن حلول لهذه المعادلة:

    T * d = 0

حيث d متجه يمثّل كل بتّات n*128 التي يمكنك اللعب بها.

إذا كنت تعرف قليلًا من الجبر الخطي، ستعرف أن ما نريد إيجاده حقًا هو أساس لـ N(T)، الفضاء الصفري لـ T. والفضاء الصفري هو بالضبط مجموعة المتجهات التي تحل المعادلة أعلاه. هذا ما نبحث عنه بالضبط. تذكّر أن الأساس مجموعة دنيا من المتجهات تغطي تركيباتها الخطية الفضاء كله. لذا إن وجدنا أساسًا لـ N(T)، أمكننا ببساطة أخذ تركيبات عشوائية من متجهاته للحصول على مرشحات صالحة لـ d.

إيجاد أساس للفضاء الصفري ليس صعبًا كثيرًا. ما تريد فعله هو نقل T (أي قلبه حول قطره) وإيجاد شكل الصف المتدرج المختزل باستخدام الحذف الغاوسي. الآن أجرِ العمليات نفسها على مصفوفة وحدة بحجم n*128. الصفوف التي تقابل الصفوف الصفرية في شكل الصف المتدرج المختزل لمنقول T تشكّل أساسًا لـ N(T).

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

الآن بعد أن أصبح لدينا أساس لـ N(T)، نحن مستعدون للبدء في تزوير الرسائل. خذ متجهًا عشوائيًا من N(T) وفك ترميزه إلى مجموعة قلبات بتّات في نصك المشفَّر C الصالح المعلوم. (تذكّر أنك ستقلب البتّات فقط في الكتل المضروبة في h^(2*i) من أجل i ما.) أرسل الرسالة المعدّلة C' إلى الأوراكل وانظر إن كان يجتاز المصادقة. وإن فشل، ولّد متجهًا جديدًا وحاول مرة أخرى.

وإن نجح، فقد كسبنا أكثر من مجرد تزوير سهل. افحص مصفوفة Ad لديك. ينبغي أن تكون مجموعة من الصفوف الصفرية يتبعها مجموعة من الصفوف غير الصفرية. تهمّنا الصفوف غير الصفرية التي تقابل بتّات الوسم. فإن كان وسمك 16 بتًا، وأجبرت ثماني بتّات على الصفر، فينبغي أن يكون لديك ثمانية صفوف غير صفرية مهمة.

انتقِ تلك الصفوف واحشُها في مصفوفة خاصة بها. سمّها، لا أعرف، K. وهناك أمر رائع نعرفه عن K:

    K * h = 0

بعبارة أخرى، h في الفضاء الصفري لـ K! في مثالنا، K مصفوفة 8x128. وبافتراض أن كل صفوفها مستقلة (لا شيء منها تركيبة لأي من الأخرى)، فإن N(K) فضاء جزئي بُعده 120 من الفضاء الأكبر ذي البُعد 128. وبما أننا نعلم أن h فيه، فإن نطاق القيم الممكنة لـ h انتقل من 2^128 إلى 2^120.

2^120 ما زال عددًا كبيرًا من القيم، لكن، مهما كان --- إنها بداية.

إن استطعنا إنتاج مزيد من عمليات التزوير، أمكننا إيجاد متجهات أكثر لإضافتها إلى K، ما يقلص نطاق القيم أكثر فأكثر. وانظر هذا: معرفتنا الجديدة بـ h ستجعل التزوير التالي أسهل. اعثر على أساس لـ N(K) وضع المتجهات في أعمدة مصفوفة. سمّها X. الآن يمكننا إعادة كتابة h هكذا:

    h = X * h'

حيث h' متجه مجهول بطول 120 بتًا. الآن بدلًا من القول:

    Ad * h = e

يمكننا القول:

    Ad * X * h' = e

وبينما Ad مصفوفة 128x128، فإن X مصفوفة 128x120. وAd * X أيضًا 128x120. وبدلًا من تصفير متجهات صفوف من الدرجة 128، يمكننا الآن تصفير متجهات من الدرجة 120. وبما أن لدينا العدد نفسه من البتّات للعب بها، يمكننا (ربما) تصفير صفوف أكثر من قبل. الصورة العامة أننا إن كان لدينا n128 بتّة للعب بها، أمكننا تصفير (n128) / (ncols(X)) صفًا. تذكّر فقط أن تترك على الأقل صفًا غير صفري واحدًا في كل محاولة؛ وإلا فلن تتعلم أي شيء جديد.

إذن: ابدأ من جديد وابنِ مصفوفة T جديدة، لكن هذه المرة لتصفير صفوف Ad * X. زوّر رسالة أخرى واحصد بعض المعادلات الخطية الجديدة على h. احشُها في K وأعد حساب X.

كرّر العملية مرارًا.

تأتي النهاية عندما يكون في K 127 صفًا مستقلًا خطيًا. عندها سيكون N(K) فضاءً جزئيًا بُعده 1 يحتوي بالضبط متجهًا غير صفري واحد، وسيكون ذلك المتجه هو h.

لنجرّب:

ابنِ نظامًا مصغرًا مع MAC بطول 32 بتًا. هذا أصغر طول وسم يعرّفه NIST في مواصفة GCM.
ولّد رسائل صالحة من 2^17 كتلة ليلعب بها المهاجم.
بوصفك المهاجم، ابنِ مصفوفاتك، وزوّر الرسائل، واستعد المفتاح. ينبغي أن تكون قادرًا على تصفير 16 بتّة من كل وسم في البداية، ولن تكسب رافعة إلا من هناك فصاعدًا.

65. عودة إلى GCM ذي MAC المقتطع: تحسين هجوم استعادة المفتاح

    via Ciphertext Length Extension

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

لخّص Niels Ferguson هذه نقاط الضعف (بين غيرها) في مذكرة قصيرة كُتبت في حدود زمن تصميم GCM. وكانت توصيته النهائية؟ «[استخدمه] فقط مع وسم بطول 128 بتًا.»

واستوعب NIST بدوره ملاحظاته ثم نشر مواصفته الرسمية لـ GCM، التي تقول امضِ واستخدم وسومًا قصيرة حتى 32 بتًا، إن كان لك مزاج. YOLO.

لا تقلق، لدى NIST ثقة كاملة فيك: «ينبغي أن يكون بوسع محترفي الأمان المطلعين إدارة المخاطر المتصلة بهذا الهجوم وتحسينه المحتمل».

إذن أي نوع من النصح يقدّمه NIST لمساعدتك على تجنب الكارثة؟ صفحتان من الاعتبارات تنتهيان بجداول تحدد:

الحد الأقصى لطول النص المشفَّر والبيانات الموثَّقة معًا في حزمة واحدة، و
الحد الأقصى لعدد نداءات دالة فك التشفير الموثَّق.

وبينما تكون هذه القيود الأخيرة بصراحة مسؤولية الطرف المستقبل، لا يقدّم وثيقة NIST أي توصيات محددة نحو الحد من طول الحزم.

ربما لا يهم ذلك. فما دام الأطراف الصادقون يولّدون الحزم ضمن المعطيات المسموحة فقط، ينبغي أن نكون بخير، صحيح؟

خطأ. من الممكن في الواقع إطالة النصوص المشفَّرة الصالحة إلى أي طول يقبله المستقبل.

لنرَ كيف. أولًا، تذكّر الصورة الكبيرة. من أجل نص مشفَّر من ثلاث كتل، يُحسب MAC هكذا:

    t = s + c1*h + c2*h^2 + c3*h^3 + c4*h^4

الكتلة c1 ترمّز الطول، و[c2, c4] هي الكتل الفعلية للنص المشفَّر (بترتيب معكوس). وs قناع مجهول يولَّد باستخدام قيمة nonce ومفتاح التشفير.

في التمرين الأخير، قلبنا بتّات في كتل من النص المشفَّر لإسقاط الأمان الفعلي لدالة المصادقة. واقتصرنا على العبث بكتل معينة: تلك التي يمكن نمذجة التغييرات فيها كدالة خطية على بتّات مفتاح المصادقة. وهذا يشمل كل كتلة هي معامل لحد من الصيغة h^(2^k).

حسنًا، ليست كل كتلة. استخدمنا c2 وc4 فقط؛ وتركنا c1 وشأنه، رغم أنه معامل لـ h = h^1 = h^(2^0). ضع ذلك في ذهنك، سنعود إليه.

تذكّر أنه مع n كتلة كاملة كان لدينا 128*n متغيرًا حرًا، أمكننا استخدامها لإجبار n-1 صفًا من مصفوفة الفرق Ad على الصفر. كنا نعدّل كتلة واحدة اعتباطيًا ونضبط الأخريات للتعويض. وإن حاولنا إجبار n صفًا على الصفر، فسيكون الحل الوحيد هو الحل الصفري الذي لا نعدّل فيه شيئًا.

افترض أن لدينا كتلة ناقصة. في مثالنا أعلاه، افترض أن الكتلة الأخيرة، c2، كانت ثماني بايتات فقط. هذه ليست مشكلة كبيرة. كان يمكننا أن نستخدم متغيراتنا الحرة الـ192 (عُدّها) لإجبار صف واحد على الأقل على الصفر. ومن هناك يمضي الهجوم بالطريقة نفسها: احصل على بعض المعادلات على h، وزد فرصك في التزوير، وفي النهاية استعد المفتاح. تعرف كيف تسير الأمور.

يقدّم Ferguson احتمالًا آخر قرب نهاية مذكرته. فبدلًا من ترك كتلة الطول c1 وشأنها، نعدّلها لنكمل الكتلة الأخيرة. في هذه الحالة، سنحوّل نصنا المشفَّر ذا 40 بايت إلى نص مشفَّر ذي 48 بايت. هذا سيمنحنا 64 بتّة إضافية للعب بها، ليرتفع الإجمالي إلى 256. لاحظ أن هذا لا يؤثر في أي من معاملات الحدود غير h^(2^k)، فالفرق ما زال دالة خطية على بتّات h.

والأهم أننا بإدخال تعديل على كتلة الطول، نزيل الحل الصفري. وهذا يتيح لنا إجبار n صفًا كاملًا من مصفوفة الفرق Ad على الصفر.

بينما كنا سابقًا نحل هذه المعادلة:

    T * d = 0

نحن الآن نحل هذه:

    T * d = t

حيث t الفرق غير الصفري في أول n صفًا من Ad الناتج عن تعديلنا لكتلة الطول. نريد حل المعادلة لإيجاد متجه d من التعديلات على متغيراتنا الحرة لإلغاء هذا الفرق. ولإيجاد المجموعة الكاملة من الحلول لـ d، اعثر أولًا على حل واحد معين، ثم أضف إليه أي متجه من N(T).

نفّذ هذا التحسين. عدّل شيفرة هجومك لتتعرّف على الحالات التي تكون فيها الكتلة الأخيرة من النص المشفَّر ناقصة وتستفيد منها بتعديل كتلة الطول.

بعض التنبيهات:

ستتغير أبعاد T وd. ينبغي أن تكون قادرًا على استنتاج كيف ذلك بقليل من التأمل.
ونتيجة لذلك، قد يتقلص N(T) تقلصًا هائلًا. وكنتيجة لذلك، قد تجد أنه لا يوجد تعديل يفضي إلى تزوير ناجح. وإن حدث هذا، يمكنك الرجوع إلى شيفرتك القديمة. أو انتظر ببساطة رسالة جديدة بطول مختلف.

66. استغلال أخطاء التنفيذ في تبادل مفاتيح ديفي-هيلمان

معظم المسائل التي استغللناها كانت أخطاء تصميم في طبقة التطبيق أو البروتوكول. لكن الأوليات التشفيرية يمكن أن تعاني أخطاء تنفيذ أيضًا!

من أصناف أخطاء التنفيذ النادرة (لكن القاتلة مع ذلك!) خطأ الحمل الشهير. وهو يسير هكذا:

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

هناك فرص للأخطاء في كل مكان، لكن الخطوة 5 خبيثة بوجه خاص. قد يصعب كشف أخطاء الحمل، لأن معدل الأعطال العشوائية قد يكون 2^-64 أو أسوأ. ولأن هذه الأخطاء تعتمد على التنفيذ إلى هذا الحد، فمتجهات الاختبار المعيارية، حتى تلك المخصصة لاختبار الحالات الشاذة، ليست جيدة عادة في إيجاد هذه العيوب.

سيداتي وسادتي، يا متابعي cryptopals، رجاءً: لحظة صمت على منفّذي التشفير.

تُذرف دمعة واحدة

حسنًا، كفى تعاطفًا. الآن لنعثر على تشاكل غير بسيط من حزنهم إلى نطاق الأرباح.

لنستهدف تبادل مفاتيح ديفي-هيلمان، الأولية الأساسية للمفتاح العام في البروتوكولات التشفيرية. سنلتزم بترميز EC. وإليك الصورة عالية المستوى للضرب القياسي:

function scalarmult(Q, k):

      R := Q

      # assume n-bit k with k[1] = 1
      # iterate bits from high to low, skip first bit
      for b in bits(k)[2..n]:
          R := add(R, R)
          if b = 1:
              R := add(R, Q)

      return R

في ECDH، Q نقطة عامة يزوّدها المهاجم، وk قياسنا السري. للتبسيط، لنفترض أن k ثابت الطول بالبتّات. (وهذا صحيح غالبًا في تنفيذات DH على أي حال.) نرقّم بتّات k من 1 إلى n حيث k[1] البتّة الأكثر دلالة وk[n] البتّة الأقل دلالة.

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

بدلًا من ذلك، لنغش:

إن كنت عملت على مسائل ECDH السابقة، ينبغي أن تكون قادرًا على استعارة شيفرة من تنفيذك الموجود. وإن لم تفعل، فاصنع واحدة من قوانين جمع EC القياسية من ويكيبيديا.
استبدل add() بـ faultyadd()، التي ينبغي أن تبدو هكذا:

     function faultyadd(Q1, Q2):
         if fault(Q1, Q2):
             raise
         return add(Q1, Q2)

ينبغي أن تجزّئ fault() النقاط ببساطة وتقارنها بقيمة إشارية ما. فعلت شيئًا كهذا:

     function fault(Q1, Q2):
         return (Q1.x * Q2.x) % p = 0

حيث p احتمال حدوث عطل.

لا يهم حقًا ما fault()، لكن يجب أن تكون حتمية. فقط تأكد من أنها ليست بطيئة جدًا، لأنها ستُنادى 2n مرة لكل ضرب قياسي. وتأكد من قدرتك على ضبط p بسهولة، من أجل سلامتك النفسية.

قبل أن نفكر في كيفية الهجوم، أظن أنه من المفيد التفكير في تنفيذ DH أعلاه.

اكتب لنفسك متتبعًا صغيرًا يمشي خلال عملية ضرب قياسي، ويطبع عند كل نداء إلى add المعاملين c و d لـ Q في كل نداء add(cQ, dQ). لا تتردد في إضافة أي مخرجات تنقيح منطقية.

على سبيل المثال، مع n = 6، يعطيني trace(58):

k = 111010

i = 2, b = 1

add(1Q, 1Q) add(2Q, 1Q)

i = 3, b = 1

add(3Q, 3Q) add(6Q, 1Q)

i = 4, b = 0

add(7Q, 7Q)

i = 5, b = 1

add(14Q, 14Q) add(28Q, 1Q)

i = 6, b = 0

add(29Q, 29Q)

وإليك trace(62):

k = 111110

i = 2, b = 1

add(1Q, 1Q) add(2Q, 1Q)

i = 3, b = 1

add(3Q, 3Q) add(6Q, 1Q)

i = 4, b = 1

add(7Q, 7Q) add(14Q, 1Q)

i = 5, b = 1

add(15Q, 15Q) add(30Q, 1Q)

i = 6, b = 0

add(31Q, 31Q)

العب بمدخلات مختلفة حتى تكتسب إحساسًا بديهيًا بالأمر.

وإليك بعض الأمور الجديرة بالملاحظة:

معاملات Q في كل نداء إلى k دالة على القياس السري وحده. وهذا يتضمن نموذجًا آخر للسر: تسلسل فريد من عمليات الزمرة. وبينما يختار المهاجم نقطة الإدخال، فإن الضحية وحده هو من يختار تسلسل العمليات عليها.
من أجل أي k معين، كل زوج من المدخلات إلى add() فريد. أي أننا لا نكرر زوج (Q1, Q2) أبدًا. السبب أن المراكم يتضاعف في كل تكرار.
في كل تكرار، تعتمد مدخلات add() على البتّة الحالية وكل البتّات السابقة. ولا تُؤخذ البتّات اللاحقة في الحسبان حتى وقت لاحق. المثالان أعلاه يختلفان في k[4] فقط. لاحظ أنهما يرمّزان تسلسلًا متطابقًا من العمليات قبل أن يتفرقا إلى الأبد عند i = 4.

وثمة طريقة أخرى لقول ذلك: بتّات k ترمّز شجرة قرار ثنائية:

                       add(1Q, 1Q)

                  /---/           \---\

            b = 0                       b = 1

         add(2Q, 2Q)                  add(2Q, 1Q)
                                      add(3Q, 3Q)

         /         \                  /         \

      b = 0       b = 1            b = 0        b = 1

add(4Q, 4Q) add(4Q, 1Q) add(6Q, 6Q) add(6Q, 1Q)

                add(5Q, 5Q)                   add(7Q, 7Q)

                         ...

وهكذا دواليك.

الآن، لنبدأ الهجوم. نعلم أن k[1] = 1 بالتعريف. لننظر في k[2]. بتفحّص الشجرة أعلاه، نرى أن add(2Q, 2Q) تُحسب إذا وفقط إذا كان k[2] = 0.

إذن:

ولّد قياسًا عشوائيًا d. أبقِه سرًا وأبقِه آمنًا. هذا هدف هجومنا.
عرّف أوراكلًا يقبل نقطة Q، ويضربها في d، ويعيد true أو false بناءً على ما إذا كان قد تحقق عطل. في إطار واقعي، قد يكون هذا نقطة نهاية تحسب مصافحة ECDH وتفك تشفير رسالة. يمكنك بناء ذلك إن كنت تشعر بالفخامة، لكن الأوراكل الاصطناعي مقبول أيضًا.
بالعمل دون اتصال، ولّد نقاطًا عشوائية واحسب add(1Q, 1Q) (الخطوة الأولى غير المشروطة في الضرب) ثم add(2Q, 2Q). أنت تبحث عن نقطة تنجو من الجمع الأول وتُفعّل عطلًا في الثاني.
عندما تجد نقطة تُفعّل عطلًا، استعلم الأوراكل. ستخبرك استجابة الأوراكل بقيمة k[2]. فإن نجح، فـ k[2] = 1. وإن فعّل العطل، فـ k[2] = 0 (على الأرجح.)

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

يمكننا إزالة هذه بتحسين محاكاتنا:

بدلًا من محاكاة فرع b = 0 فقط، حاكِ الفرعين معًا. اعثر على نقطة مرشحة تُفعّل عطلًا في أحدهما لا في الآخر.
افترض أن نقطتك تُفعّل عطلًا عندما k[2] = 1. استعلم الأوراكل. فإن لم يحدث عطل، فـ k[2] = 0. وإلا فنحن غير متأكدين، لذا عُد إلى الخطوة 1. (ينطبق المنطق نفسه إن كانت نقطتك تُفعّل العطل عندما k[2] = 0.)

من هنا، يمكننا تعميم الخوارزمية أعلاه لاستعادة البتّات التالية:

ولّد نقاطًا عشوائية وحاكِ بتّات المفتاح التي تعرفها. تأكد من عدم وجود خطأ.
حاكِ كل الحسابات الممكنة للبتّة المجهولة التالية من المفتاح. فإن فعّلت عطلًا، فامضِ. وإلا فعُد إلى الخطوة 1.
استعلم الأوراكل. النتيجة السلبية تسرّب بتّة مفتاح بيقين. أما النتيجة الإيجابية (أي عطل) فقد تسرّب بتّة مفتاح. وحسب كيفية ضبطك لاحتمال العطل، قد يمنحك هذا ثقة كافية للمضي.
كرّر العملية حتى تُستعاد كل بتّات المفتاح.

هذا كل شيء تقريبًا.

حسنًا، هناك بضع فرص للتفنّن، إن كنت تميل إلى ذلك:

حتى في وجود عدم اليقين، للنتائج الإيجابية قيمة. يمكنك حساب احتمال الإيجابية الكاذبة وتحديد ما إذا كانت لديك ثقة كافية للمضي.
بمجرد أن تحصل على بتّات كافية من المفتاح، يمكنك حساب ما تبقى من الهجوم دون اتصال باستخدام هجمات اللوغاريتم المتقطع القياسية (مثل كنغر Pollard).

السابق المجموعة 7