ممحاة جبرية

بروتوكول Algebraic Eraser ( AE ) ^{[ ملاحظة 1 ]} هو بروتوكول اتفاقية مفاتيح مجهولة المصدر ، يسمح لطرفين، يمتلك كل منهما زوجًا من المفاتيح العامة والخاصة لبروتوكول AE، بإنشاء سر مشترك عبر قناة غير آمنة . ^{[ 1 ]} يمكن استخدام هذا السر المشترك مباشرةً كمفتاح، أو لاستخلاص مفتاح آخر يُستخدم لتشفير الاتصالات اللاحقة باستخدام تشفير المفتاح المتناظر . طُوّر بروتوكول Algebraic Eraser بواسطة إيريس أنشيل، ومايكل أنشيل، ودوريان غولدفليد ، وستيفان ليميو. تمتلك شركة SecureRF براءات اختراع تغطي البروتوكول ^{[ 2 ]} ، وقد حاولت دون جدوى (حتى يوليو 2019) توحيد البروتوكول كجزء من معيار ISO/IEC 29167-20، ^{[ 3 ]} وهو معيار لتأمين أجهزة تحديد الهوية بترددات الراديو وشبكات الاستشعار اللاسلكية .

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

• ${\displaystyle N}$عدد الخيوط في الضفيرة،
• ${\displaystyle q}$حجم الحقل المنتهي${\displaystyle \mathbb {F} _{q}}$،
• ${\displaystyle M_{*}}$، مصفوفة البذور الأولية NxN في${\displaystyle \mathbb {F} _{q}}$،
• ${\displaystyle \mathrm {T} }$، مجموعة من${\displaystyle N}$العناصر في الحقل المنتهي${\displaystyle \mathbb {F} _{q}}$(وتسمى أيضًا قيم T)، و
• ${\displaystyle A,B}$مجموعة من المترافقات في مجموعة الجدائل مصممة للتبادل مع بعضها البعض.

تتمثل العملية الأساسية للممحاة الجبرية في دالة أحادية الاتجاه تسمى الضرب الجبري. بفرض مصفوفة، تبديل، مولد أرتين${\displaystyle \beta }$في مجموعة الجدائل، وقيم T، يتم تطبيق الضرب E عن طريق تحويل المولد إلى مصفوفة بوراو ملونة وتبديل الجدائل.${\displaystyle (CB(\beta ),\sigma _{\beta })}$بتطبيق التبديل وقيم T، ثم ضرب المصفوفات والتبديلات. ناتج عملية الضرب E هو في حد ذاته زوج من المصفوفة والتبديل:${\displaystyle (M',\sigma ')=(M,\sigma _{0})*(CB(\beta ),\sigma _{\beta })}$.

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

يجب أن يمتلك كل طرف زوجًا من المفاتيح مشتقًا من مجموعة المفاتيح، ويتكون من مفتاح خاص (على سبيل المثال، في حالة أليس).${\displaystyle (m_{A},\mathrm {B} _{a})}$أين${\displaystyle m_{A}}$هي متعددة حدود مختارة عشوائياً من مصفوفة البذور${\displaystyle m_{A}=\sum _{i=0}^{N-1}{a_{i}M_{*}^{i}}}$والضفيرة، وهي مجموعة مختارة عشوائيًا من المرافقات والمعكوسات المختارة من معلمات مجموعة المفاتيح (أ لأليس و ب لبوب، حيث (لأليس)${\displaystyle \mathrm {B} _{a}=\prod _{i=1}^{k}A_{i}^{\pm 1}}$).

من بيانات مفتاحهم الخاص، يقوم كل من أليس وبوب بحساب مفتاحهما العام${\displaystyle (Pub_{A},\sigma _{a})}$و${\displaystyle (Pub_{B},\sigma _{b})}$أين، على سبيل المثال،${\displaystyle (Pub_{A},\sigma _{a})=(m_{A},id)*b_{a}}$، أي نتيجة الضرب E للمصفوفة الخاصة والتبديل المتطابق مع الجديلة الخاصة.

يجب على كل طرف معرفة المفتاح العام للطرف الآخر قبل تنفيذ البروتوكول.

لحساب السر المشترك، تقوم أليس بحساب${\displaystyle (S_{ab},\sigma _{ab})=(m_{A}Pub_{B},\sigma _{b})*\mathrm {B} _{a}}$ويقوم بوب بالحساب${\displaystyle (S_{ba},\sigma _{ba})=(m_{B}Pub_{A},\sigma _{a})*\mathrm {B} _{b}}$السر المشترك هو زوج المصفوفة/التبديل${\displaystyle (S_{ab},\sigma _{ab})}$، وهو ما يساوي${\displaystyle (S_{ba},\sigma _{ba})}$الأسرار المشتركة متساوية لأن المجموعات المترافقة${\displaystyle A}$و${\displaystyle B}$يتم اختيارهم للتنقل، ويستخدم كل من أليس وبوب نفس مصفوفة البذور${\displaystyle M_{*}}$وقيم T${\displaystyle \mathrm {T} }$.

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

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

يعتمد أمان التشفير التلقائي (AE) على مسألة البحث المتزامن المعمم عن الاقتران (GSCSP) ^{[ 4 ]} ضمن مجموعة الجدائل . تُعد هذه المسألة صعبة ومختلفة تمامًا عن مسألة البحث عن الاقتران (CSP)، التي كانت تُمثل المسألة الصعبة المركزية فيما يُعرف بتشفير مجموعة الجدائل . ^{[ 5 ]} حتى لو تم كسر مسألة البحث عن الاقتران (CSP) بشكل موحد (وهو ما لم يحدث حتى الآن)، فإنه من غير المعروف كيف سيُسهل ذلك كسر مسألة البحث المتزامن المعمم عن الاقتران (GSCSP).

يُظهر الهجوم الأول الذي شنه كل من كالكا وتيشر وتسابان فئة من المفاتيح الضعيفة عندما${\displaystyle M_{*}}$أو${\displaystyle m_{A}}$يتم اختيارها عشوائيًا. ^{[ 6 ]} تابع مؤلفو برنامج Algebraic Eraser بنشر نسخة أولية حول كيفية اختيار المعلمات غير المعرضة للهجوم. ^{[ 7 ]} قام بن-زفي وبلاكبيرن وتسابان بتحسين الهجوم الأول إلى هجوم يدعي المؤلفون أنه قادر على اختراق معلمات الأمان المعلنة (التي يُزعم أنها توفر أمانًا من نوع 128 بت) باستخدام أقل من 8 ساعات من وحدة المعالجة المركزية، وأقل من 64 ميجابايت من الذاكرة. ^{[ 8 ]} رد أنشيل وأتكينز وغولدفيلد على هذا الهجوم في يناير 2016. ^{[ 9 ]}

أظهر هجوم ثانٍ من قِبل مياسنيكوف وأوشاكوف، نُشر كنسخة أولية، أن المترافقات المختارة بضفيرة مترافقة قصيرة جدًا يمكن فصلها، مما يؤدي إلى كسر النظام. ^{[ 10 ]} وقد دحض غانيلز هذا الهجوم، مُبينًا أن ضفائر المترافقة ذات الحجم المناسب لا يمكن فصلها. ^{[ 4 ]}

في عام 2016، نشر سيمون ر. بلاكبيرن وماثيو جيه بي روبشو مجموعة من الهجمات العملية على مسودة بروتوكول ISO/IEC 29167–20 للاتصالات اللاسلكية الصادرة في يناير 2016، بما في ذلك انتحال هوية علامة الهدف في وقت وذاكرة ضئيلين، واستعادة المفتاح الخاص بالكامل التي تتطلب 2.49 من ^الوقت و ^2.48 من الذاكرة. ^{[ 11 ]} ردّ أتكينز وغولدفيلد بأن إضافة رمز تجزئة أو رمز مصادقة الرسائل إلى مسودة البروتوكول يُحبط هذه الهجمات. ^{[ 12 ]}

• تبادل مفاتيح أنشيل-أنشيل-غولدفيلد
• التشفير القائم على المجموعات
• التشفير غير التبادلي

• الصفحة الرئيسية لـ SecureRF