ای۵/۱

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

A۵/۱ یک رمز دنباله‌ای است که در جهت حفظ حریم خصوصی در تلفن‌های همراه استاندارد جی‌اس‌ام به کار رفته است. این سیستم رمزنگاری در ابتدا به شکل محرمانه ارائه شد، امّا بعداً به‌واسطهٔ مهندسی معکوس به شکل عمومی شناخته شد. ضعف‌های جدی و قابل توجّه‌ای در این سیستم رمزنگاری وجود دارد.

تاریخچه و موارد استفاده[ویرایش]

A۵/۱ در اروپا و ایالات متّحدهٔ آمریکا مورد استفاده قرار می‌گرفت. سیستم رمز A۵/۲ یک نسخهٔ عمداً ضعیف‌شدهٔ این الگوریتم بود که برای صادرات به برخی از کشورها مورد استفاده قرار گرفت.[۱] A۵/۱ در سال ۱۹۸۷ و در زمانی که جی‌اس‌ام هنوز در خارج از اروپا مورد استفاده نبود طراحی شد، درصورتی‌که A۵/۲ در سال ۱۹۸۹ طراحی شد. گرچه هر دو الگوریتم پس از طراحی محرمانه باقی‌ماندند، امّا طراحی کلی آنها در سال ۱۹۹۴ لو رفت. همچنین این الگوریتم‌ها در سال ۱۹۹۹ به صورت کامل، از طریق مهندسی معکوس توسط مارک بریکنو لو رفتند. در سال ۲۰۰۰ حدود ۱۳۰ میلیون مشتری از A۵/۱ برای حفظ محرمانگی مکالماتشان استفاده می‌کردند. این عدد در سال ۲۰۱۱ به ۴ میلیارد نفر رسید.

الگوریتم[ویرایش]

هر رجیستر یک بیت دارد که شیفت خوردن آن در هر کلاک از روی آن معلوم می‌شود. اگر بیت متناظر با هر ثبات با بیتی که اکثریت را بین سه بیت زرد رنگ تشکیل می‌دهد برابر باشد، آنگاه آن ثبات شیفت می‌خورد.

در سیستم A۵/۱ در هر ۴٫۶۱۵ هزارم ثانیه، ۱۱۴ بیت ارسال می‌شود. این ۱۱۴ بیت با دنبالهٔ ۱۱۴ بیتی که از یک مولد خارج می‌شود، XOR شده و سپس مدوله شده و ارسال می‌شود. A۵/۱ برای فعال‌سازی به یک کلید ۶۴ بیتی و یک عدد ۲۲ بیتی عمومی به نام شمارهٔ فریم نیاز دارد. پیاده‌سازی‌های قدیمی‌تر جی‌اس‌ام، برای تولید کلید از Comp128v۱ استفاده می‌کردند که ده بیت کلید خروجی آن همواره برابر صفر بود و در واقع طول مؤثّر کلید در آن ۵۴ بیت بود. این ضعف با معرّفی Comp128v۲ بر طرف شد. هنگام کارکردن در مد GPRS/EDGE، پهنای باند بیشتر اجازهٔ استفاده از فریم‌های ۳۴۸ بیتی را نیز فراهم می‌کند. در این شرایط در رمز دنباله‌ای از A۵/۳ استفاده می‌شود. در A۵/۱ از سه ثبات تغییر بازخورد خطی با کلاک نامنظّم استفاده می‌شود که XOR خروجی آنها، به عنوان خروجی مولد مورد استفاده قرار می‌گیرد.

شماره
ثبات
تعداد
بیت‌ها
چندجمله‌ای
فیدبک
بیت
کلاک
بیت‌های
تپ شده
۱ ۱۹ x^{19} + x^{18} + x^{17} + x^{14} + 1 ۸ ۱۳, ۱۶, ۱۷, ۱۸
۲ ۲۲ x^{22} + x^{21} + 1 ۱۰ ۲۰, ۲۱
۳ ۲۳ x^{23} + x^{22} + x^{21} + x^{8} + 1 ۱۰ ۷, ۲۰, ۲۱, ۲۲

اعمال کلاک به هر ثبات در هر کلاک توسط قاعدهٔ اکثریت تعیین می‌شود. هر رجیستر یک بیت دارد که شیفت خوردن آن در هر کلاک از روی آن معلوم می‌شود. (این بیت با رنگ زرد در شکل نمایش داده شده است.) اگر بیت متناظر با هر ثبات با بیتی که اکثریت را بین سه بیت مذکور تشکیل می‌دهد برابر باشد، آنگاه آن ثبات شیفت می‌خورد. بنابرین در هر سیکل، حداقل دو ثبات شیفت خورده و همچنین در هر کلاک هر ثبات به احتمال ۳/۴ شیفت می‌خورد. در ابتدا تمام ثبات‌ها با مقدار اولیّهٔ صفر مقداردهی می‌شوند، سپس طی ۶۴ کلاک، پیش از کلاک iام، کم‌ارزش‌ترین بیت هر رجیستر با بیت iام کلید XOR می‌شود.

R[0] = R[0] \oplus K[i].

به طریق مشابه ۲۲ بیت بعدی هم طی ۲۲ کلاک اضافه می‌شود. سپس ثبات‌ها برای ۱۰۰ کلاک کار می‌کنند. از آن به بعد خروجی آنها برای رمز دنباله‌ای استفاده می‌شود.

امنیت[ویرایش]

پیامی روی صفحهٔ تلفن همرها در رابطه با عدم وجود رمزنگاری

چند حمله به A۵/۱ منتشر شده که برخی از آنها به پیش‌پردازش سنگینی نیاز داشتند که پس از آن، امکان رمزگشایی در چند دقیقه یا چند ثانیه فراهم می‌شد. اکثر این حملات، حمله متن آشکار بودند. در سال ۲۰۰۳، با توجه به یافتن نقاط ضعف جدید، حمله متن رمز شده نیز برای این سیستم یافت شد. در سال ۲۰۰۶، الاد بارکان، الی بایهام و ناتان کلر حملاتی در برابر A۵/۱ و A۵/۳ یافتند که به مهاجمان اجازهٔ شنود مکالمات و رمزگشایی بلادرنگ آنها را می‌داد.

حملات متن آشکار[ویرایش]

اولین حمله به A۵/۱ توسط راس اندرسون در سال ۱۹۹۴ انجام شد. ایدهٔ اصلی این حمله حدس زدن محتویات ثبات یک و دو و نیمی از محتویات ثبات سه بود. بدین ترتیب می‌توان زمان شیفت خوردن ثبات‌ها و در نتیجهٔ آن مقدار نیمهٔ دوم ثبات سوم را هم حدس زد.

در سال ۱۹۹۷ گالیچ حمله‌ای مبتنی بر حل دستگاه معادلات خطی ارائه کرد که با پیچیدگی ۲۴۰٫۱۶ قابل اجرا بود.

در سال ۲۰۰۰، الکس بیریوکف، آدی شمیر و دیوید وگنر با توجه به حملهٔ گالیچ[۲] نشان دادند که A۵/۱ را می‌توان به شکل بلادرنگ و با یک حملهٔ بده بستان زمان-حافظه شکست.[۳] یک بده بستان مهاجم را قادر می‌ساخت تا کلید را طی یک ثانیه از روی دو دقیقه متن آشکار بدست آورد. همچنین می‌توان کلید را طی چند دقیقه از روی دو ثانیه متن رمز شده بدست آورد. اما این حمله نیاز به پیش‌پردازشی با ۲۴۸ بیت روی حدود ۳۰۰GB داشت.

همان سال الی بایهام و ار دانکلمن حمله‌ای با پیچیدگی ۲۳۹٫۹۱ با ۲۲۰٫۸ بیت آشکار متن اصلی ارائه کردند. این حمله ۳۲GB حافظه و پیش‌پردازشی به مقدار ۲۳۸ نیاز داشت.[۴]

پاتریک اکدال و توماس جانسون حمله‌ای مرتبط با مرحلهٔ مقداردهی اوّلیه برای A۵/۱ یافتند که می‌توانست با استفاده از دو تا پنج دقیقه از مکالمهٔ آشکار، رمز را بشکند.[۵] این حمله پیش‌پردازش لازم نداشت. ماکسیمف این حمله را ارتقاء داد تا با چند ثانیه از مکالمهٔ آشکار، در کمتر از یک دقیقه رمز شکسته شود. در سال ۲۰۰۵ الاد بارکان و الی بایهام این حمله را باز هم ارتقاء دادند.[۶]

حمله به A۵/۱ در جی‌اس‌ام[ویرایش]

در سال ۲۰۰۳ الاد بارکان، الی بایهام و ناتان کلر، چند حمله به رمزهای مورد استفاده در جی‌اس‌ام مطرح کردند.[۷] سپس در سال ۲۰۰۶، با تکمیل مقاله‌ای که در سال ۲۰۰۳ ارائه شد، حملاتی به سیستم رمزنگاری A۵/۲ منتشر کردند.

در سال ۲۰۰۷ دانشگاه‌های بوخوم و کیل یک پروژهٔ تحقیقاتی در رابطه با پیاده‌سازی یک حمله کننده موازی و مبتنی بر مدار مجتمع دیجیتال برنامه‌پذیر (FPGA) به نام COPACOBANA را اجرا کردند. این اولّین پیاده‌سازی عملی بود که از حملات بده بستان زمان حافظه برای حمله به A۵/۱ و A۵/۲ استفاده شده بود.[۸]

در سال ۲۰۰۸ گروه The Hackers Choice پروژه‌ای برای پیاده‌سازی یک حمله عملی به A۵/۱ اجرا کردند. این حمله یک Lookup table به اندازهٔ ۳ ترابایت لازم داشت. با این روش این گروه قادر بود تا طی سه تا پنج دقیقه، کلید را بدست آورده و پس از آن مکالمات و پیامک‌ها را رمزگشایی کند. البته این Lookup tableها منتشر نشد.[۹]

در یک تلاش مشابه، پروژه A۵/۱ Cracking در کنفرانس امنیت Black Hat در سال ۲۰۰۹ توسط کارستن ناهل و ساشا کریتلر اعلام شد. در این پروژه Lookup tableها با استفاده از GPGPU ان‌ویدیا و توسط رایانش توزیع‌شده همتا به همتا ساخته شدند.

در دسامبر ۲۰۰۹، Lookup tableها برای حمله به A۵/۱ در پروژه A۵/۱ Cracking توسط کریس پگت و کارستن ناهل منتشر شد. این جدول‌ها از روش‌های فشرده‌سازی مانند جداول رنگین‌کمانی استفاده شده بود. این جداول طی چهار ماه و با استفاده از ۴۰ گره کودا (زبان برنامه‌نویسی) محاسبه شده بود و روی بیت‌تورنت منتشر شد.[۹][۱۰][۱۱][۱۲]

از سال ۲۰۱۲ یک رایانه معمولی با یک پردازنده گرافیکی قوی و چند ترابایت حافظه فلش می‌توانست رمز A۵/۱ را طی چند ثانیه و با احتمال بیش از ۹۰٪ رمزگشائی کند.

منابع[ویرایش]

  1. Quirke, Jeremy (2004-05-01). "Security in the GSM system". AusMobile. Archived from the original on 2004-07-12. 
  2. Golic, Jovan Dj. (1997). "Cryptanalysis of Alleged A5 Stream Cipher". EUROCRYPT 1997: 239–55. 
  3. Biryukov, Alex; Adi Shamir; David Wagner. "Real Time Cryptanalysis of A5/1 on a PC". Fast Software Encryption—FSE 2000: 1–18. 
  4. Biham, Eli; Orr Dunkelman (2000). "Cryptanalysis of the A5/1 GSM Stream Cipher". Indocrypt 2000: 43–51. 
  5. Ekdahl, Patrik; Thomas Johansson (2003). ( "Another attack on A5/1". IEEE Transactions on Information Theory 49 (1): 284–89. doi:10.1109/TIT.2002.806129. 
  6. Barkan, Elad; Eli Biham (2005). "Conditional Estimators: An Effective Attack on A5/1". Selected Areas in Cryptography 2005: 1–19. 
  7. Barkan, Elad; Eli Biham; Nathan Keller (2003). "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication". Crypto 2003: 600–16. Archived from the original on 2005-12-16. 
  8. Gueneysu, Tim; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp (2008). "Cryptanalysis with COPACOBANA". Transactions on Computers Nov. 2008 57: 1498–1513. 
  9. ۹٫۰ ۹٫۱ Nohl, Karsten; Chris Paget (2009-12-27). "GSM: SRSLY?". 26th Chaos Communication Congress (26C3):. Archived from the original on 6 January 2010. Retrieved 2009-12-30. 
  10. https://har2009.org/program/attachments/119_GSM.A51.Cracking.Nohl.pdf Subverting the security base of GSM. Karsten Nohl and Sascha Krißler
  11. O'Brien, Kevin (2009-12-28). "Cellphone Encryption Code Is Divulged". New York Times. Archived from the original on 1 January 2010. Retrieved 2009-12-29. 
  12. McMillan, Robert. "Hackers Show It's Easy to Snoop on a GSM Call". IDG News Service. 

پیوند به بیرون[ویرایش]