شيفرة التدفقA5/1

A5/1 هو شفيرة تدفق تُستخدم لتوفير خصوصية الاتصالات عبر الهواء في معيار الهاتف الخلوي GSM . إنه أحد التطبيقات العديدة لبروتوكول الأمان A5. تم الاحتفاظ بالأمر سراً في البداية، لكنه أصبح معروفاً للعامة من خلال التسريبات والهندسة العكسية . وقد تم تحديد عدد من نقاط الضعف الخطيرة في الشفرة.

 التاريخ والاستخدام 
يُستخدم A5/1 في أوروبا والولايات المتحدة. أما A5/2 فكان إضعافًا متعمدًا للخوارزمية من أجل بعض مناطق التصدير.  تم تطوير A5/1 في عام 1987، عندما لم يكن من المتوقع استخدام GSM خارج أوروبا، وتم تطوير A5/2 في عام 1989. وعلى الرغم من أن كليهما كان سريًا في البداية، تم تسريب التصميم العام في عام 1994، وتمت هندسة الخوارزميات عكسيُا بالكامل في عام 1999 بواسطة مارك بريسينو من هاتف GSM. في عام 2000، كان حوالي 130 مليون عميل GSM يعتمدون على A5/1 لحماية سرية اتصالاتهم الصوتية.[ بحاجة لمصدر ]

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

 وصف 
يسار|تصغير|350x350بك| تستخدم شفرة التدفق A5/1 ثلاثة LFSRs . يتم تسجيل السجل إذا كان بت التسجيل الخاص به (البرتقالي) يتفق مع بت التسجيل الخاص بأحد السجلين الآخرين أو كليهما.
يتم تنظيم إرسال GSM كسلاسل من الانفجارات . في قناة نموذجية وفي اتجاه واحد، يتم إرسال دفعة واحدة كل 4.615 ميلي ثانية وتحتوي على 114 بت متاحة للمعلومات. تُستخدم A5/1 لإنتاج سلسلة من شيفرة المفتاح بطول 114 بت من تدفق المفاتيح لكل انفجار ويتم إجراء عملية XOR بينها وبين 114 بت قبل التضمين. يتم تهيئة A5/1 التي تستخدم مفتاح بطول 64 بت مع رقم إطار معروف علنًا بطول 22 بت. كانت تطبيقات GSM الميدانية القديمة التي تستخدم Comp128v1 لتوليد المفاتيح، تحتوي على 10من بتات المفتاح مثبتة على الصفر، مما أدى إلى طول مفتاح فعّال يبلغ 54 بت. تم تصحيح هذا الضعف مع إدخال Comp128v3 الذي ينتج مفاتيح صحيحة بطول 64 بت. عند العمل في وضع GPRS / EDGE، تتيح التضمينات الراديوية ذات نطاق الترددي العالي إطارات أكبر بطول 348 بت، ويتم بعد ذلك استخدام A5/3 في وضع تشفير التدفق للحفاظ على السرية.

يعتمد A5/1 على مزيج من ثلاث مسجلات إزاحة ذات تغذية راجعة خطية (LFSRs) مع توقيت غير منتظم. يتم تحديد مسجلات الإزاحة الثلاثة كما يلي :
LFSR رقم الطول في أجزاء تعليق متعدد الحدود تسجيل الوقت قليل تم النقر عليه أجزاء 1 19  8 13، 16، 17، 18 2 22  10 20، 21 3 23  10 7، 20، 21، 22
لم تُختار هَذِه الدرجات عشوائيًا: نظرًا لأن درجات المسجلات الثلاثة أولية نسبيًا، فإن فترة هذا المولد هي حاصل ضرب فترات المسجلات الثلاثة. وبالتالي فإن فترة A5/1 (قبل التكرار) هي 2^64 بت (اثنان مرفوع للقوة 64).

يَتم فهرسة البتات مع البت ذو أقل أهمية (LSB) على أنه 0.

تُدار المسجلات بطريقة التوقف/الانطلاق باستخدام قاعدة الأغلبية. لكل مسجل يوجد بت توقيت مرتبط به. في كل دورة، يتم فحص بت التوقيت لكل المسجلات الثلاثة وتحديد البت الأغلبية. يتم تدوير المسجل إذا كان بت التسجيل يتفق مع البت الأغلبية. ومن ثم، في كل خطوة يتم تسجيل سجلين أو ثلاثة على الأقل، ويتحرك كل سجل باحتمال 3/4.

في البداية، تُضبط المسجلات على الصفر. ثم على مدار 64 دورة، يتم دمج المفتاح السري K المكون من 64 بت وفقًا للمخطط التالي: في الدورة  ، يتم إضافة بت i من المفتاح إلى أقل بت مهم في كل مسجل باستخدام عملية XOR —



يتم بعد ذلك تسجيل كل سجل.

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

 حماية 
يسار|تصغير|250x250بك| الرسالة التي تظهر على شاشة الهاتف المحمول مع التحذير من عدم التشفير
تم نشر عدد من الهجمات على A5/1، وتمكنت وكالة الأمن القومي الأمريكية من فك تشفير رسائل A5/1 بشكل روتيني وفقًا لوثائق داخلية تم إصدارها.

تتطلب بَعض الهجمات مَرحلة مُعالجة مُسبقة مُكلفة يمكن بعدها كسر الشفرة في دقائق أو ثوانٍ. فِي الأصل، كانت نِقاط الضعف عِبارة عن هجمات سلبية تستخدم افتراض النص العادي المعروف . في عام 2003، تم تحديد نقاط ضعف أكثر خطورة يمكن استغلالها في سيناريو النص المشفر فقط ، أو من قبل مهاجم نشط. في عام 2006، أظهر إيلاد باركان وإيلي بيهام وناثان كيلر هجمات ضد A5/1، و A5/3 ، أو حتى GPRS تسمح للمهاجمين بالتنصت على مكالمات هواتف GSM وفك تشفيرها إما في الوقت الحقيقي، أو في أي وقت لاحق.

وفقًا للبروفيسور جان أريلد أودستاد، في عملية المعيارية التي بدأت في عام 1982، تم اقتراح A5/1 بطول مفتاح 128 بت. في ذلك الوقت، كان من المتوقع أن يكون 128 بت آمنًا لمدة 15 عامًا على الأقل. يُعتقد الآن أن 128 بت سيكون آمنًا حتى ظهور الحوسبة الكمومية . يقول أودستاد، وبيتر فان دير أريند، وتوماس هاوج إن البريطانيين أصروا على تشفير أضعف، حيث قال هاوغ إنه من قبل المندوب البريطاني بالتنصت بسهولة أكبر. اقترح البريطانيون طول مفتاح يبلغ 48 بت، في حين أراد الألمان الغربيون تشفيرًا أقوى للحماية من التجسس الألماني الشرقي، لذا أصبح الحل الوسط هو طول مفتاح يبلغ 54 بت. 

 هجمات النص العادي المعروف 
تم اقتراح هجوم على A5/1 بواسطة روس أندرسون في عام 1994. كانت الفكرة الأساسية لأندرسون هي تخمين المحتوى الكامل للسجلات R1 وR2 وحوالي نصف السجل R3. بهذه الطريقة يتم تحديد توقيت جميع السجلات الثلاثة ويمكن حساب النصف الثاني من R3. Ross Anderson (17 June 1994). "A5 (Was: HACKING DIGITAL PHONES)". Newsgroup: uk.telecom. Usenet: 2ts9a0$95r@lyra.csx.cam.ac.uk.

في عام 1997، قدم جوليك هجومًا يعتمد على حل مجموعات من المعادلات الخطية، ويبلغ التعقيد زمني له 2 × 40.16 (الوحدات تُقاس بعدد الحلول لنظام المعادلات الخطية المطلوبة).

في عام 2000، أظهر أليكس بيريوكوف ، وأدي شامير ، وديفيد فاغنر أنه يمكن تحليل شفرة A5/1 يمكن تحليله في الوقت الحقيقي باستخدام هجوم يعتمد على الموازنة بين الوقت والذاكرة،  استنادًا إلى عمل سابق لجوفان جوليك.  تسمح إحدى طرق الموازنة للمهاجم بإعادة بناء المفتاح في ثانية واحدة من دقيقتين من النص المعروف أو في عدة دقائق من ثانيتين من النص المعروف، ولكن يجب عليه أولاً إكمال مرحلة معالجة مسبقة مُكلفة تتطلب 248 خطوة لحساب حوالي 300 جيجابايت من البيانات. هناك العديد من الموازنات الممكنة بين المعالجة المسبقة ومتطلبات البيانات ووقت الهجوم وتعقيد الذاكرة.

في نفس العام، نشر إيلي بيهام وأور دونكلمان أيضًا هجومًا على A5/1 بتعقيد إجمالي في العمل يبلغ 2 39.91 من دورات A5/1 مع توفر 2 20.8 بت من نص معروف . يتطلب الهجوم 32 جيجابايت من تخزين البيانات بعد مرحلة معالجة مسبقة تبلغ 2 38. 

نَشَرَ إيكدال وجوهانسون هُجومًا على إجِراء التهيئة الأولية والذي يكسر A5/1 في غضون بضع دقائق باستخدام من دقيقتين إلى خمس دقائق من نص المحادثة المعروف.  لا يتطلب هذا الهجوم مرحلة معالجة مُسبقة. في عام 2004، حسّن ماكسيموف وآخرون هذه النتيجة إلى هجوم يتطلب "أقل من دقيقة من الحسابات، وبضع ثوانٍ من المحادثة المعروفة". تم تحسين الهجوم بشكل أكبر من قبل إيلاد باركان وإيلي بيهام في عام 2005. 

 الهجمات على A5/1 كما هو مستخدم في GSM 
في عام 2003، نشر باركان وآخرون عدة هجمات على تشفير GSM.  الأولى هو الهجوم نشط. يمكن إقناع هواتف GSM باستخدام الشيفرة الأضعف بكثير A5/2 لفترة قصيرة. يمكن كسر A5/2 بسهولة، وتستخدم الهواتف نفس المفتاح المستخدم في الخوارزمية الأقوى A5/1 . كما تم عرض هجوم ثانٍ على A5/1، وهو هجوم يعتمد على تبادل الوقت والذاكرة باستخدام النص المشفر فقط والذي يتطلب قدرًا كبيرًا من الحساب المسبق.

في عام 2006، نشر إلاد باركان وإيلي بيهام وناثان كيلر النسخة الكاملة من ورقتهم البحثية لعام 2003، والتي تحتوي على هجمات ضد شيفرات A5/X ويدعي المؤلفون : 

في عام 2007، بدأت جامعتا بوخوم وكيل مشروعًا بحثيًا لإنشاء مسّرع تشفي يعتمد على FPGA بالتوازي الكثيف يُعرف باسم COPACOBANA. كان COPACOBANA أول حل المتاح تجاريًا  يستخدم تقنيات الموازنة السريعة بين الزمن والذاكرة والتي يمكن استخدامها لمهاجمة خوارزميات A5/1 وA5/2 الشائعة، المستخدمة في تشفير صوت GSM، بالإضافة إلى معيار تشفير البيانات (DES). كما أنه يتيح شن هجمات القوة الغاشمة ضد GSM مما يلغي الحاجة إلى جداول بحث كبيرة محسوبة مسبقًا.

فِي عام 2008، أطلقت مَجموعة The Hackers Choice مشروعًا لتطوير هجوم عملي على A5/1. يتطلب الهُجوم إنشاء جدول بحث كبير بحجم 3 تيرابايت تقريبًا. وبالاقتران مع قدرات المسح التي تم تطويرها كجزء من المشروع الشقيق، توقعت المجموعة أن تكون قادرة على تسجيل أي مكالمة GSM أو رسالة نصية قصيرة مشفرة باستخدام A5/1، وفي غضون حوالي 3 إلى 5 دقائق استخرج مفتاح التشفير ومن ثم الاستماع إلى المكالمة وقراءة الرسالة بصيغة واضحة. لكن الجداول لم يتم إصدارها. 

جهد مشابه، مشروع فك تشفير A5/1، تم الإعلان عنه مؤتمر Black Hat للأمن لعام 2009 من قبل خبراء التشفير كارستن نول وساشا كريسلر. قام المشروع بإنشاء جداول البحث باستخدام وحدات معالجة الرسومات العامة من Nvidia عبر بنية حوسبة موزعة بنظام نظير إلى نظير . بدءًا من منتصف سبتمبر 2009، عمل المشروع بما يعادل 12 بطاقة رسومات Nvidia GeForce GTX 260. وفقًا للمؤلفين، يمكن استخدام هذه الطريقة على أي تشفير بحجم مفتاح يصل إلى 64 بت.  Subverting the security base of GSM. Karsten Nohl and Sascha Krißler

في ديسمبر 2009، أعلن كريس باجيت وكارستن نول عن جداول هجوم مشروع فك تشفير A5/1 لشيفرة A5/1. تستخدم الجداول مزيجًا من تقنيات الضغط، بما في ذلك جداول قوس قزح وسلاسل النقاط المميزة. كانت هذه الجداول جزءًا فقط من الجدول المكتمل الذي يبلغ حجمه 1.7 تيرابايت وتم حسابها خلال ثلاثة أشهر باستخدام 40 عقدة CUDA مُوزعة ثم نُشرت عبر BitTorrent . Nohl, Karsten; Chris Paget (27 December 2009). GSM: SRSLY?. 26th Chaos Communication Congress (26C3). Archived from the original on 6 January 2010. Retrieved 30 December 2009. "Archived copy" (PDF). Archived from the original  (PDF) on 26 July 2011. Retrieved 29 December 2009.{{cite web}}: CS1 maint: archived copy as title (link)
Subverting the security base of GSM. Karsten Nohl and Sascha Krißler   مؤخرًا، أعلن المشروع عن الانتقال إلى كود ATI Evergreen الأسرع، إلى جانب تغيير في صيغة الجداول، وأعلن Frank A. Stevenson عن اختراقات لشيفرة A5/1 باستخدام الجداول المُنشأة بواسطة ATI. 

وثائق سربها إدوارد سنودن في عام 2013 إلى أن وكالة الأمن القومي "تستطيع معالجة بيانات A5/1 المشفرة". 

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

قد يظن البعض أن استخدام A5/1 كمولد زائف للتتابع العشوائي مع بذرة تهيئة بحجم 64 بت (حجم المفتاح)، لكنه ليس موثوقًا به. يفقد عشوائيته بعد 8 ميجا بايت فقط (وهو ما يمثل فترة أكبر السجلات الثلاثة). 

 انظر أيضًا 

 أ5/2
 كاسومي ، المعروف أيضًا باسم A5/3
 خوارزمية تشفير الرسائل الخلوية

 المراجع 

 ملحوظات 




 روابط خارجية 








تصنيف:معيار النظام العالمي لاتصالات الهواتف المحمولة
تصنيف:معايير مشروع شراكة الجيل الثالث
تصنيف:معايير اتصالات الأجهزة المحمولة
تصنيف:معميات تدفق استخرج معماها
تصنيف:معميات تدفق