التشفير التطبيقي. كيف استعدنا عملات البيتكوين مقابل 300 ألف دولار

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

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

أتذكر بشكل خاص مشروعين. الأول كان Microsoft Word 97. قبل ظهوره ، تم تشفير الملفات باستخدام XOR بايت من نص واضح وسلسلة 16 بايت تم إخراجها من كلمة المرور. عادةً ما تكون البايت الأكثر شيوعًا في ملف Word هي 0x00 أو 0xFF أو 0x20 (مسافة) ، لذلك اخترنا للتو الحرف الأكثر شيوعًا في كل عمود وتحققنا من 3 إلى ¹⁶ خيارًا. عادةً ما يحدث الاسترداد الرئيسي على الفور ، ولكن حتى لا يظن الناس أنهم أهدروا المال ، أدخلنا رسمًا متحركًا صغيرًا مشابهًا لمشهد القراصنة في هوليوود مع الكثير من الشخصيات العشوائية ، والتي تظهر منها كلمة المرور الصحيحة تدريجيًا.

قام Microsoft Word 97 بتغيير كل شيء. ربما كشفت MSDN أيضًا عن تنسيق التشفير ، ولكن لم تتمكن شركتنا الصغيرة من تحمل اشتراك. وليس حقيقة أنه سيسمح لنا بكتابة برنامج للقرصنة بعد تلقي المعلومات. لفهم ، في SoftICE ، قمت بتعيين نقطة توقف فورًا بعد إدخال كلمة المرور ، ثم حركت المكدس ببطء حتى عثرت على خوارزمية. كان هذا قبل إصدار IDA Pro ، لذلك كان لدي عشرات الصفحات من المطبوعات مع رمز مجمع مخطوط بعلامة حمراء على جداري. كنت سعيدًا جدًا عندما اكتشفت الأمر أخيرًا. في ذلك الوقت ، تم السماح لـ Microsoft بتصدير تشفير 40 بت فقط ، لذا قامت الشركة بتطبيق التشفير المسموح به بشكل صارم: لقد قاموا مرارًا بتجزئة كلمة المرور في MD5 باستخدام "الملح" (يتم اختيار وحدات البايت بشكل عشوائي من الملف) ،للحصول على مفتاح 40 بت ، ثم يضاف إليه الملح ويتم تجزئته مرة أخرى. استغرق فحص كلمة المرور على أجهزة الكمبيوتر في ذلك الوقت حوالي نصف ثانية. كان علينا استخدام هجوم القاموس لأنه كان من المستحيل تقريبًا اختراق كلمة مرور باستخدام القوة الغاشمة. نتيجة لذلك ، قمنا بكتابة كلمة مرور للشركات الكبيرة والوكالات. نفّذ البرنامج قسوة مساحة مفتاح 40 بت باستخدام تعليمات MMX Pentium الفاخرة. سمعت أنها بمجرد أن عملت لمدة تسعة أشهر قبل أن ألتقط كلمة المرور.نفّذ البرنامج قسوة مساحة مفتاح 40 بت باستخدام تعليمات MMX Pentium الفاخرة. سمعت أنها بمجرد أن عملت لمدة تسعة أشهر قبل أن ألتقط كلمة المرور.نفّذ البرنامج قسوة مساحة مفتاح 40 بت باستخدام تعليمات MMX Pentium الفاخرة. سمعت أنها بمجرد أن عملت لمدة تسعة أشهر قبل أن ألتقط كلمة المرور.

مشروع آخر ممتع حقًا هو أرشيف مضغوط. اتخذ Phil Katz ، منشئ PKZIP ، قرارًا غير معتاد في ذلك الوقت لتوثيق تنسيق ملفه وتضمين هذه الوثائق في حزمة البرامج ، مما جعل ZIP تنسيقًا مفضلًا للمطورين. قام روجر شلافلي بتطوير تشفير دفق لتشفير الأرشيفات. سرعان ما أصبح معيار zip هو الأكثر شيوعًا ضمن Windows ، والعديد من التنسيقات الأخرى ، مثل ملفات jar java ومستندات OpenOffice ، كانت في الواقع ملفات مضغوطة ذات بنية دليل محددة بداخلها. كانت النسخة المفتوحة من البرنامج تسمى InfoZIP ، وكانت أساسًا تقريبًا لجميع أرشفة الملفات المضغوطة الملكية ، مثل WinZip. عندما بدأت في اختراق WinZip ، احتلت 95 ٪ من السوق.

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

يحتوي التشفير المضغوط على 96 بتًا من الحالة الداخلية ، مقسمة إلى ثلاث كتل 32 بت تسمى key0، key1وkey2. الأول والثالث هما الحالة الداخلية لنسختين من CRC32 ، سجل التحول الخطي مع الملاحظات (نموذج رياضي بسيط يسمح لك بإنشاء تسلسلات عشوائية). باختصار ، لتحديث الحالة ببايت جديد من البيانات ، تقوم بتحويل كل شيء لأسفل بمقدار بايت واحد (تجاهل البايت السفلي) ، ثم قم بعمل XOR مع ثابت من جدول التحويل المفهرس بواسطة بايت البيانات بعد XOR مع البايت السفلي. key1هي الحالة الداخلية لمولد متناسق خطي مبتور (TLCG). لتحديث حالتها الداخلية ، نضيف بايت من البيانات ، مضروبًا في ثابت ، والذي سوف نسميهc، وأضف واحدة. يعمل التشفير على النحو التالي: أدخل بايت البيانات في CRC32 الأول ، ثم خذ البايت السفلي وأدخله في TLCG ، ثم خذ البايت العلوي من هناك وأدخله في CRC32 الثاني ، ثم خذ الحالة والمربع (تقريبًا) ، ثم أصدر البايت الثاني ينتج عنها دفق بايت. لتهيئة 96 بت من الحالة الداخلية ، تبدأ بحالة معروفة وتشفير كلمة المرور ، ثم تشفير عشرة بايتات ملح.

يحصل PKZIP على وحدات بايت الملح الخاصة به ، ويخصص ذاكرة دون أن يقوم بتهيئتها ، لذا فهو يحتوي على أجزاء من المواد من برامج أو صور أو مستندات أخرى قيد التشغيل ، أيا كان. كان هذا يعمل بشكل جيد على Windows ، ولكن في العديد من أنظمة Unix ، تتم تهيئة الذاكرة تلقائيًا عند تخصيصها. يحدد InfoZIP بايتات الملح باستخدام الوظيفةrandلغة سي. قام بتهيئة حالة مولد الأرقام العشوائية عن طريق عمل طابع زمني XOR على معرف العملية ، ثم قام بإنشاء عشرة بايتات لكل ملف. في هذه الحالة ، بمعرفة الطابع الزمني ومعرف العملية ، كان من الممكن ، نظريًا ، استعادة وحدات بايت الرأس ، والتي ، بدورها ، جعلت من الممكن مهاجمة Beham و Kocher. يبدو أن مؤلفي InfoZIP كانوا على علم بهذا الهجوم لأنهم ذهبوا خطوة أبعد - وقاموا بتشفير الرأس باستخدام كلمة مرور. وهكذا ، لم يكن لدى المهاجم سوى نص عادي مشفر ، ولم يكن الهجوم سيعمل.

لقد لاحظت ذلك ، نظرًا لأن كلمة المرور هي نفسها في كلتا المرورين ، فإن البايت الأول من الدفق هو نفسه في كل منهما. بنفس الطريقة عند تبديل مفتاح الضوء مرتين ، يبقى في مكانه في البداية ، عندما يتكرر البايت XOR مع نفس تدفق البايت ، يبقى كما هو. سمح لي هذا بتطوير هجوم قوي جدًا على نص التشفير فقط : بعد تلقي خمسة ملفات مشفرة في الأرشيف ، يمكنني إخراج الحالة الداخلية للوظيفةrandدون الحاجة إلى النظر إلى الطابع الزمني أو معرفة معرف العملية. ثم يمكنني إنشاء الرؤوس الأصلية غير المشفرة. نظرًا لأن عددًا قليلاً من البتات في كل جزء من التشفير يؤثر على الجزء التالي ، يمكنني أيضًا تخمين بعض البتات من الحالة والتحقق مما إذا كان فك تشفير وحدات البايت التالية مرتين يعطي الإجابة التي توقعتها. كلما تقدمت ، كان علي تخمين قطع أقل وأقل من المفتاح. يسمح كل ملف إضافي أيضًا باستبعاد المزيد من المواد الرئيسية المحتملة ؛ في ذلك الوقت ، استغرق الأمر عدة ساعات على سطح مكتب واحد. لقد نشرت مقالًا حول هذا الأمر وحصلت على فرصة لعرضه في اليابان في مؤتمر Fast Software Encryption 2001.

سرعان ما غادرت AccessData ، وعملت في شركة ناشئة على الشبكات العصبية لمدة عام ، وقضيت ثلاث سنوات في الدراسة للحصول على درجة الماجستير في علوم الكمبيوتر في جامعة أوكلاند مع كريس كالود ، وبدأت دراسات الدكتوراه مع الفيزيائي الرياضي جون بايز في جامعة كاليفورنيا ريفرسايد ، وعملت لمدة ست سنوات كجزء من فريق الأمن التطبيقي في Google ، أكمل شهادة الدكتوراه ، وبعد ذلك بسنوات أصبح المدير الفني للشركة الناشئة الجديدة.

منذ حوالي نصف عام ، تلقيت بشكل غير متوقع رسالة على LinkedIn من شاب روسي. قرأ المقال الذي كتبته قبل 19 عامًا وأردت معرفة ما إذا كان الهجوم سيعمل على أرشيف يحتوي على ملفين فقط. أظهر تحليل سريع أنه يتطلب كمية هائلة من قوة الحوسبة والمال. نظرًا لوجود ملفين فقط ، يوجد في كل مرحلة من التحديد نتائج إيجابية خاطئة أكثر بكثير. والنتيجة هي ²⁷⁷³ مفتاحًا ممكنًا للاختبار ، ما يقرب من 10 سكستليون. حسبت أن مجموعة كبيرة على GPU ستعمل لمدة عام ، وستكون تكلفتها حوالي 100 ألف دولار. ضربني قائلاً إنه وافق على إنفاق الكثير من المال لاستعادة المفتاح.

والحقيقة هي أنه في يناير 2016 ، اشترى عملات بيتكوين مقابل حوالي 10-15 ألف دولار ووضع المفاتيح في ملف مضغوط مشفر. الآن تكلفوا أكثر من 300 ألف دولار ، ولم يستطع تذكر كلمة المرور. لحسن الحظ ، كان لا يزال لديه الكمبيوتر المحمول الأصلي ، وكان يعرف وقت التشفير بالضبط. نظرًا لأن InfoZip ينتج الإنتروبيا استنادًا إلى الطابع الزمني ، فقد وعد هذا بتقليل عدد الخيارات الرئيسية المحتملة "إلى" 10 كوينتيليون فقط - وجعل الهجوم ممكنًا في غضون شهرين في مزرعة GPU متوسطة. وقعنا على عقد وبدأت العمل.

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

في هجومي الأصلي ، خمنت البايتات العالية للمفاتيح key1 · c و key1 · c ² و key1 · c ³ و key1 · c ⁴ . في الوقت الذي خمنت فيه هذه البايت الرابع ، كنت أعرف الحالة الكاملة لبقية الشفرة ؛ أنا فقط بحاجة لتحويل هذه البايت الأربعة إلى المفتاح الأصلي 1 ، وهذا كل شيء. سأذهب فوق مساحة الحالة 32 بت للمفتاح 1 وتحقق من كل واحد لمعرفة ما إذا كان يعطي وحدات البايت العالية الصحيحة. ومع ذلك ، سيتعين عليك هنا التحقق من مفاتيح كوينتيليون ؛ إذا كنت بحاجة إلى إجراء 2 ³² اختبارًا لكل منها ، فسوف يستغرق الأمر عدة مئات الآلاف من السنين.

تذكرت بشكل غامض أن بعض الأعمال قد تم إجراؤها على التحليل المشفر لـ TLCG من خلال تقليل الأساس الشبكي ، لذلك قمت بتفحص المقالة الأصلية. لذا كان كذلك! كان من الضروري فقط تحديد الشبكة ذات النواقل الأساسية المعطاة بواسطة 2 ³² ودرجة الثبات من TLCG ، ثم قم بتقليل أساس الشبكة. على أساس مخفض ، يمكنني استعادة الحالة الأصلية من وحدات البايت العالية بضرب المصفوفات ببساطة.

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

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

فكرت في الهجمات المشفرة الأخرى التي أعرفها. أحدهم كان هجوم "اللقاء في المنتصف". بدت مرشحة واعدة. يتم تطبيق الهجوم على تشفير كتلة عندما يستخدم جزءًا واحدًا من المادة الرئيسية لأداء النصف الأول من التشفير ، والجزء الآخر للجزء الثاني. ينطبق هذا على التشفير المضغوط ، لكن المادة الرئيسية تفوق عدد البتات في المنتصف. ثم حدث لي ، ماذا لو استخدمنا الخط الخطي لـ CRC32: إذا قمنا بإجراء عملية XOR على ناتجين من CRC32 الأخير ، فستكون النتيجة مستقلة عن key2! بدلاً من حساب الحالة الوسيطة للشفرة وتخزينها في جدول ، أود حساب XOR للحالتين الوسيطتين وتخزينها بدلاً من ذلك.

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

استمر الهجوم عشرة أيام وانتهى بالفشل.

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

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

أنا الآن أبحث عن عمل. إذا كانت لديك مشاكل مثيرة للاهتمام في التحليل الفني أو التحسين ، فأخبرني بذلك.

---