مولّدات الأعداد العشوائية

مولّدات الأعداد العشوائية

توليد الأعداد العشوائيّة مهمٌّ إلى حدٍّ لا يحتمل أن يُترك للصدفة.

   *Robert R. Coveyou*

مقدّمة

تحتاج كثيرٌ من الأنظمة التشفيريّة إلى أعداد عشوائيّة. وقد افترضنا حتى الآن أنّها متاحة. وفي هذا الفصل، سنغوص أكثر في أهمّية الأعداد العشوائيّة وآليّاتها في الأنظمة التشفيريّة.

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

وهناك ثلاث فئات من توليد الأعداد العشوائيّة سنناقش كلًّا منها على حدة:

• مولّدات الأعداد العشوائيّة الحقيقيّة
• المولّدات شبه العشوائيّة الآمنة تشفيريًّا
• المولّدات شبه العشوائيّة

مولّدات الأعداد العشوائيّة الحقيقيّة

بالطبع، فإنّ كلّ من يعتبر الطرق الحسابيّة لتوليد الأرقام العشوائيّة يكون في حالة خطيئة.

   *John von Neumann*

آلَفَ John von Neumann، أبو النموذج الحديثة للحوسبة، ملاحظةً بديهية. فنحن لا ننتظر أن ننتج أعدادًا عشوائيّة بحسابٍ حسابيّ حتميّ قابل للتنبّؤ. فنحن بحاجة إلى مصدر عشوائيّة لا يكون نتيجة قواعد حتميّة.

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

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

• عمليات كمّيّة
• عمليات حراريّة
• انحراف المذبذب
• أحداث توقيتية

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

الاضمحلال الإشعاعي

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

ضجيج اللقطات

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

ضجيج نايكوست

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

$$i = \sqrt{\frac{4 k_B T \Delta_f}{R}}$$ $$v = \sqrt{4 k_B T R \Delta_f }$$

ولعلّ هذه الصيغ تبدو مخيفة قليلًا لمن لم يرَ الفيزياء الكامنة خلفها من قبل، لكنّ لا داعي للقلق كثيرًا: ففهمها ليس ضروريًّا في الحقيقة لمتابعة الحجّة. وهذه الصيغ خاصّة بالجذر التربيعيّ للمربّع. فإذا كنت لم تسمع هذه العبارة من قبل، فيمكنك أن تقارب بينه وبين «المتوسّط». و\Delta f هو عرض النطاق، وT هو حرارة النظام بالكلفن، وk_B هو ثابت بولتزمان.

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

وبتقييم الصيغة، نرى أنّ ضجيج نايكوست ضئيل إلى حدٍّ ما. فعند درجة حرارة الغرفة مع افتراضات معقولة (عرض نطاق 10 kHz ومقاومة 1k\ \Omega)، يكون جهد نايكوست في مرتبة مئات النانوفولت. وحتّى لو قَرَّبنا بحرّية إلى الميكروفولت (ألف نانوفولت)، فإنّ ذلك لا يزال جزءًا من الألف جزء من الألف من الفولت، بل إنّ بطاريّة AA صغيرة تنتج 1.5V.

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

TODO: لم نشرح من قبل كلمة إنتروبيا؛ ويحتاج التعريف الجيّد إلى «المقاومة التي يدركها المهاجم»

TODO: اشرح الشيفرات المتزامنة بوصفها مولّدات عشوائيّة آمنة تشفيريًّا

المولّدات شبه العشوائيّة الآمنة تشفيريًّا

المولّدات شبه العشوائيّة الآمنة تشفيريًّا

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

وبدلًا من ذلك، في الحالات القليلة التي تريد فيها حقًّا أن تختار عددًا عشوائيًّا يدويًّا، ينبغي أن تستعمل دائمًا مولّد الأعداد العشوائيّة الآمن تشفيريًّا الذي يوفّره نظام تشغيلك: /dev/urandom على أنظمة *NIX (Linux وBSD وOS X)، أو CryptGenRandom على Windows. وتوفّر بايثون واجهات مريحة للوصول إلى هذين بوصفهما os.urandom وrandom.SystemRandom.

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

TODO: تحدّث عن التهويم FUD في صفحة man الخاصة بـ urandom في Linux

متقدّم

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

Yarrow

متقدّم

وخوارزمية Yarrow هي مولّد أرقام عشوائيّة شبه عشوائيّ آمن تشفيريًّا.

TODO: اشرح Yarrow فعلًا

وتُستعمل هذه الخوارزمية بوصفها المولّد الآمن تشفيريًّا في FreeBSD، وقد ورثتها Mac OS X. وعلى هذين نظامَي التشغيل معًا، تُستعمل لتنفيذ /dev/random. وخلافًا Linux، فإنّ /dev/urandom ليس سوى اسم بديل لـ /dev/random.

Blum Blum Shub

TODO: اشرح هذا، ولماذا هو جيّد (قابل للإثبات)، لكن لماذا لا نستعمله (بطيء)

Dual_EC_DRBG

Dual_EC_DRBG

متقدّم

Dual_EC_DRBG هو معيار NIST لمولّد بتّات شبه عشوائيّ آمن تشفيريًّا. وقد أثار كمًّا كبيرًا من الجدل: فعلى الرّغم من أنّه طُرح بوصفه معيارًا تشفيريًّا رسميًّا فيدراليًّا، سرعان ما تبيّن أنّه ليس جيّدًا إلى حدٍّ ما.

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

وبعد عدّة سنوات، رشّحت وثائق مسرَّبة وجود باب خلفيّ في معيار مجهول الاسم من NIST صدر في السنة نفسها التي صدر فيها Dual_EC_DRBG، فعمّقت الشكوك أكثر. وأدى هذا إلى توصية رسميّة من الجهة المشرفة على المعايير بوقف استعمال المعيار، وهو أمر لم يسبق له مثيل في مثل هذه الظروف.

الخلفية

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

وآملت NIST معالجة هذه المسألة بإصدار جديد اسمها SP 800-90، تضمّن عدّة مولّدات أرقام عشوائيّة شبه عشوائيّة آمنة تشفيريًّا جديدة. وقد حدّدت هذه الوثيقة عددًا من الخوارزميات المبنيّة على أساسيات تشفيريّة مختلفة:

#. دوالّ التجزئة التشفيريّة #. HMAC #. شيفرات الكتل #. المنحنيات الإهليلجيّة

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

وهناك سبب ثانٍ يجعل المنحنيات الإهليلجيّة تبدو غريبة. فـ HMAC وشيفرات الكتل خوارزميات متماثلة بوضوح. أمّا دوالّ التجزئة فلها استعمالاتها في الخوارزميات غير المتماثلة مثل التوقيعات الرقمية، لكنّها ليست غير متماثلة بحدّ ذاتها. أمّا المنحنيات الإهليلجيّة فتُستعمل حصرًا في الخوارزميات غير المتماثلة: التوقيعات وتبادل المفاتيح والتشفير.

ومع ذلك، لم يكن هذا الاختيار صادرًا عن العدم تمامًا. فالاختيار بين مولّد أرقام عشوائيّة شبه عشوائيّ آمن تشفيريًّا له أساس عدديّ نظريّ قويّ ليس شيئًا غير مألوف: فـ Blum Blum Shub مثال مثاليّ. وهذه المولّدات أبطأ عادةً بكثير من بدائلها. فـ Dual_EC_DRBG مثلًا أبطأ بثلاث رتب مقدارًا من نظائرها المذكورة في المعيار نفسه. والفكرة هي أنّ الثقة الإضافية التي يستلهمها المرء من الضمانات الرياضيّة الأقوى تستحقّ عقوبة الأداء. فمثلًا، نحن واثقون إلى حدٍّ معقول من صعوبة تحليل الأعداد إلى عوامل، لكنّ ثقتنا بدوالّ التجزئة والشيفرات أقلّ كثيرًا. فقد ظهرت RSA سنة 1977 وقد اجتازت اختبار الزمن إلى حدٍّ جيّد منذ ذلك الحين. أمّا DES فظهرت بعد عامين، وتُعدّ اليوم معطوبة تمامًا. أمّا MD4 وMD5 فظهرا بعد أكثر من عقد، وهما معطوبان تمامًا أيضًا.

لكنّ المشكلة أنّ المعيار لم يقدّم في الواقع إثبات الأمن. فالمعيار يحدّد المولّد ثمّ يقتصر على الإشارة إلى أنّ كسره سيكون صعبًا على الأقلّ بقدر حلّ مسألة السجلّ على المنحنيات الإهليلجيّة. أمّا Blum Blum Shub، على النقيض، فإنّ له إثباتًا يُظهر أنّ كسره صعب على الأقلّ بقدر حلّ مسألة تربيعية البواقي. وأفضل خوارزمية لدينا لذلك هي تحليل الأعداد إلى عوامل، ونحن واثقون إلى حدٍّ معقول من صعوبتها إلى حدٍّ كبير.

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

وقام المشفّرون لاحقًا بالواجب الذي كان على NIST تقديمه في المواصفة ecdrbg1 ecdrbg2. وقد أبرزت تلك التحليلات بسرعة بضع مسائل.

لمحة سريعة عن الخوارزمية

وتتألّف الخوارزمية من جزأين:

#. توليد نقاط شبه عشوائيّة على المنحنية الإهليلجيّة، تُحوَّل إلى الحالة الداخليّة للمولّد #. تحويل تلك النقاط إلى بتّات شبه عشوائيّة

وسنوضّح ذلك بيانيًّا، اعتمادًا على رسم مبنيّ على عمل Shumow وFerguson، وهما مشفّران أبرزا بعضًا من المسائل الكبرى في هذه الخوارزمية:

وفي الخوارزمية كلّها، تكون \phi دالة تأخذ نقطةً على المنحنية وتحولها إلى عدد صحيح. وتحتاج الخوارزمية إلى نقطتين معطاتين على المنحنية: P وQ. وهما ثابتتان، ومعرّفتان في المواصفة. وللخوارزمية حالة داخليّة s. وحين تُنتج كتلة جديدة من البتّات، تحوّل الخوارزمية s إلى قيمة مختلفة r باستعمال الدالة \phi وبضرب المنحنى الإهليلجيّة في سُلَّم P:

r = \phi(sP)

تُستعمل القيمة r تلك، من جهة، في إنتاج بتّات الخرج، ومن جهة أخرى في تحديث الحالة الداخليّة للمولّد. ولإنتاج بتّات الخرج، تُستعمل نقطة منحنى إهليلجيّة أخرى، وهي Q. وتُنتَج بتّات الخرج بضرب r في Q، ثمّ تمرير النتيجة عبر تحويل \theta:

o = \theta(\phi(rQ))

ولتنفيذ تحديث الحالة، يُضرب r في P من جديد، ثمّ تُحوَّل النتيجة إلى عدد صحيح. ويُستعمل ذلك العدد بوصفه الحالة الجديدة s.

s = \phi(rP)

المسائل ومواضع الشك

أوّلًا من كلّ شيء، إنّ \phi بسيطة إلى حدٍّ متطرّف: فهي تأخذ مجرّد الإحداثي x لنقطة المنحنى وتطرح الإحداثي y. وهذا يعني أنّه من السهل إلى حدٍّ ما على مهاجم يرى قيمة خرج \phi أن يجد نقاطًا كان من الممكن أن تُنتج تلك القيمة. وذاته، لا يمثّل ذلك مشكلة كبيرة بالضرورة؛ لكنّنا سنرى لاحقًا أنّه أحد العوامل التي تسهم في إمكان وجود باب خلفيّ.

ويُبيَّن عيبٌ آخر في موضع تحويل النقاط إلى بتّات شبه عشوائيّة. فدالة \theta تطرح ببساطة أكثر 16 بتًّا أهميةً. وقد كانت التصاميم السابقة تطرح عددًا أكبر بكثير: فمنحنيات 256 بتًّا مثل هذه، كانت تطرح ما بين 120 و175 بتًّا.

وعدم طرح بتّات كافية منح المولّد انحيازًا صغيرًا. وقد خالفت خاصّية البتّ التالي، فمنح ذلك المهاجم فرصة أفضل من 50% في تخمين البتّ التالي صحيحًا. وصحيح أنّ تلك الفرصة كانت أفضل من 50% بنحو واحد في الألف فقط؛ لكنّ ذلك يبقى غير مقبول فيما ينبغي أن يكون أحدث ما في مولّدات الأعداد العشوائيّة شبه العشوائيّة الآمنة تشفيريًّا.

ولطرح تلك الـ16 بتًّا فقط نتيجة أخرى. فبما أنّه لم يُطرح إلّا 16 بتًّا، لا نحتاج إلّا إلى تخمين 2^{16} احتمالًا لإيجاد القيم الممكنة لـ \phi(rQ) التي أنتجت الخرج. وهذا عدد صغير جدًا: يمكننا ببساطة أن يعدّدها كلّها. وتلك القيم هي مخارج \phi التي رأينا أنّها مجرّد تُعيد الإحداثي x لنقطة. وبما أنّنا نعرف أنّها جاءت من نقطة على المنحنية، فلا بدّ لنا إلّا من التحقّق ممّا إذا كان تخميننا حلًّا لمعادلة المنحنى:

$$y^2 \equiv x^3 + ax + b \pmod p$$

وتحدّد المنحنية الثوابت a, b, p. وقد خمّنا مجرّد قيمة لـ x، فلم يبقَ إلّا مجهول واحد، وهو y. ويمكننا حلّ ذلك بكفاءة معقولة. فنحسب الطرف الأيمن ونرى إن كان مربّعًا تامًّا: y^2 \equiv q \equiv \sqrt{x^3 + ax + b} \pmod p. فإذا كان كذلك، فإنّ A = (x, \sqrt{q}) = (x, y) هي نقطة على المنحنية. وهذا يعطينا عددًا من النقاط الممكنة A، إحداها هي rQ المستعمَلة لإنتاج الخرج.

وهذا ليس أمرًا مهمًّا بحدّ ذاته. فليجد مهاجم حالة الخوارزمية، عليه أن يجد r كي يحسب s. ولا يزال عليه أن يحلّ مسألة السجلّ على المنحنيات الإهليلجيّة ليجد r من rQ، معطى Q. ونحن نفترض أنّ تلك المسألة صعبة.

واحرص على أنّ المنحنيات الإهليلجيّة أساسيات تُستعمل في التشفير غير المتماثل. ومن المتوقّع أن تكون تلك المسألة صعبة الحلّ في العموم، لكن ماذا لو توفّرت لدينا معلومات إضافيّة؟ ماذا لو وُجدت قيمة سرّية e بحيث eQ=P؟

ولنضع أنفسنا في مكان مهاجم يعرف e. فنعيد حساباتنا السابقة. إحدى تلك النقاط A التي وجدناها للتوّ هي rQ التي نبحث عنها. ويمكننا أن نحسب:

$$\phi(eA) \equiv \phi(erQ) \equiv \phi(rP) \pmod p$$

وتُعدّ تلك الخطوة الأخيرة نتيجةً للعلاقة الخاصّة بين e, P, Q. وذلك مثير للاهتمام إلى حدٍّ كبير، لأنّ \phi(rP) هي بالضبط العملية التي تجريها الخوارزمية لحساب s، أي الحالة الجديدة للخوارزمية! ويعني ذلك أنّ مهاجمًا يعرف e يستطيع، بكفاءة معقولة، أن يحسب الحالة الجديدة s من أيّ خرج o، فيتمكّن من التنبّؤ بكلّ القيم المستقبليّة للمولّد!

وهذا يفترض أنّ المهاجم يعرف أيّ A هي A الصحيحة. وبما أنّه لم يُطرح إلّا 16 بتًّا، لم يبقَ إلّا 16 بتًّا لنخمّنها. وهذا يعطينا 2^{16} إحداثي x مرشَّحًا. ونجد تجريبيًّا أنّ نحو نصف إحداثيات x الممكنة تقابل نقاطًا على المنحنية، فتترك لنا 2^{15} نقطة منحنى ممكنة A، إحداها هي rQ. وهذا عدد صغير إلى حدٍّ ما بالنسبة إلى قدرٍ قليل من الحساب الحاسوبيّ: صغير بما يكفي لأن نجرّب كلّ الخيارات. ومن ثمّ يمكننا القول إنّ مهاجمًا يعرف القيمة السرّية e يستطيع قطعًا أن يكسر المولّد.

فقد بيّنا الآن أنّه لو وُجدت e سحرية بحيث eQ=P، واستطعنا اختيار P وQ (وليس علينا أن نشرح من أين أتينا بهما)، فسنستطيع كسر المولّد. فكيف تختار قيمًا من هذا النوع؟

ولإظهار مدى كون ذلك ممكنًا، بدأ الباحثان من قيمتي P وp الخاصّتين بمنحنى NIST، لكنّهما توصّلا إلى Q' خاصّة بهما. وقد فعلا ذلك انطلاقًا من P، واختارا d عشوائيًّا (مع إبقائها سرّية)، وجعلا Q' = dP. والحيلة أنّ هناك خوارزمية كفاءة لحساب e في eQ' = P إذا كنت تعرف d في Q' = dP. وهذه هي e التي نحتاجها لهجومنا السابق. وحين جرّبوا ذلك، اكتشفوا أنّه في كلّ الحالات (أي في حالات d عشوائيّة كثيرة) كانت رؤية 32 بايتًا من الخرج كافية لتحديد الحالة s.

وكلّ هذا، بالطبع، لا يثبت سوى أنّه من الممكن أن تكون قيمتا P وQ المحدَّدتان قيمتين خاصّتين لهما باب خلفيّ سرّي. وهو لا يقدّم أيّ دليل على أنّ القيم الفعليّة تحوي بابًا خلفيًّا. لكنّ المعيار، بما أنّه لم يشرح أصلًا كيف حصلوا على القيمة السحرية لـ Q، لا يستلهم كثيرًا من الثقة. فمعايير التشفير تعتمد عادةً أرقامًا من نوع «لا أعرف من أين جاءت»، مثل قيمة ثابتٍ ما كـ \pi أو قاعدة اللوغاريتم الطبيعي e.

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

وهناك طريقتان يمكن أن يحاول المرء بهما إصلاح هذه الخوارزمية بعينها:

• جعل دالة \theta أعقد في العكس، بدل مجرّد طرح 16 بتًّا. وهذا يجعل إيجاد النقاط المرشَّحة أصعب، وبالتالي يجعل تنفيذ الهجوم أصعب. ومن الطرق البديهية طرح بتّات أكثر. ومن الخيارات الأخرى استعمال دالة تجزئة آمنة تشفيريًّا، أو مزيج من الأمرين.
• توليد Q عشوائيّة في كلّ مرّة تبدأ فيها الخوارزمية، ربما باختيار d عشوائيّة وجعل Q = dP. ويجب بالطبع أن تكون d كبيرة بما يكفي وعشوائيّة حقًّا: فإذا لم تتغيّر \theta ولم يكن أمام d إلّا بضع قيم، أمكن للمهاجم إجراء الهجوم أعلاه على كلّ قيم d.

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

ما بعد ذلك

TODO: تحدّث عن تعليقات صاحب RSA + تسريبات Snowden

Mersenne Twister

وMersenne Twister هو مولّد أرقام عشوائيّة شبه عشوائيّ شائع إلى حدٍّ كبير. ولديه خصائص جيّدة كثيرة، مثل أداءٍ عالٍ، ودورةٍ هائلة ^[1] قدرها 2^{19937} - 1 \approx 4 \cdot 10^{6001}، وهو يجتاز كلّ اختبارات العشوائيّة عدا أكثرها تطلّبًا. ومع كلّ هذه الخصائص الرائعة، فهو ليس آمنًا تشفيريًّا.

نظرة معمّقة على Mersenne Twister

متقدّم

ولإظهار سبب عدم كون Mersenne Twister آمنًا تشفيريًّا، سننظر إلى كيفية عمل الخوارزمية. ولحسن الحظّ، فهي ليست معقّدة إلى حدٍّ كبير.

وتعمل خوارزمية Mersenne Twister القياسيّة على مصفوفة حالة داخليّة S مكوَّنة من 624 عددًا صحيحًا غير سالب بطول 32 بتًّا، وعلى فهرس i يشير إلى العدد الحالي. وهي تتألّف من ثلاث خطوات:

#. دالة تهيئة اختياريّة، تُنتج حالة أوّليّة من قيمة عشوائيّة صغيرة تُسمّى البذرة (seed). #. دالة توليد حالة، تُنتج حالة جديدة من الحالة القديمة. #. دالة استخراج، تُسمّى أيضًا دالة التقويم (tempering)، تُنتج عددًا عشوائيًّا من العنصر الحالي للحالة (العنصر الذي يشير إليه الفهرس i).

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

فإذا رجعنا إلى ما سبق: تُولَّد الحالة من جديد، ثمّ تمرّ دالة الاستخراج على كلّ عناصر الحالة واحدًا واحدًا حتى تنفد. وتتكرّر هذه العمليّة إلى ما لا نهاية.

TODO: ارسم

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

دالة التهيئة

تنشئ دالة التهيئة نسخةً من مصفوفة حالة Mersenne Twister انطلاقًا من عدد عشوائيّ أوّليّ صغير يُسمّى البذرة (seed).

وتبدأ المصفوفة بالبذرة نفسها. ثمّ يُنتَج كلّ عنصر تالٍ من ثابت، والعنصر السابق، وفهرس العنصر الجديد. وتُنتَج العناصر إلى أن يصير عددها 624.

وهذا هو شيفرة بايثون المصدرية:

def uint32(n):
    return 0xFFFFFFFF & n

def initialize_state(seed):
    state = [seed]

    for i in range(1, 624):
        prev = state[-1]
        elem = 0x6c078965 * (prev ^ (prev >> 30)) + i
        state.append(uint32(elem))

    return state

ولمن لم يعمل مع بايثون أو مع معاملاتها البتّيّة:

• >> و<< هما الإزاحة يمينًا والإزاحة يسارًا
• & هو AND ثنائي: 0 \& 0 = 0 \& 1 = 1 \& 0 = 0، و 1 \& 1 = 1.
• ^ هو XOR ثنائي، و^= يُطبّق XOR على الطرفين ويضع النتيجة في الاسم الموجود على اليسار، من نوع x ^= k أي x = x ^ k.

REVIEW: ملحق الحساب البتّيّ؟

دالة إعادة توليد الحالة

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

والشيفرة المصدرية لهذه الدالة في بايثون بسيطة إلى حدٍّ ما. ولاحظ أنّها تعدّل مصفوفة الحالة في مكانها، بدل أن تُعيد مصفوفة جديدة.

def regenerate(s):
    for i in range(624):
        y = s[i] & 0x80000000
        y += s[(i + 1) % 624] & 0x7fffffff

        z = s[(i + 397) % 624]
        s[i] = z ^ (y >> 1)

        if y % 2:
            s[i] ^= 0x9908b0df

والمعامل % في تعبير مثل s[(i + n) % 624] يعني النظر في العنصر التالي من الحالة، مع الالتفاف إلى بداية مصفوفة الحالة إذا لم يوجد عنصر تالٍ.

وللقيمتَي 0x80000000 و0x7fffffff معنًى محدّد عند تفسيرهما متسلسلَتي بتّ بطول 32. فـ 0x80000000 ليس فيها إلّا البتّ الأوّل مضبوطًا؛ بينما 0x7fffffff فيها كلّ البتّات إلّا البتّ الأوّل. ولأنّهما تُدمجان معًا ب AND البتّيّ (&)، فإنّ ذلك يعني بفعالية أنّ y بعد السطرين الأوّلَين في الحلقة يتكوّن من البتّ الأوّل من عنصر الحالة الحالي ومن كلّ البتّات التالية لعنصر الحالة التالي.

دالة التقويم

تُطبَّق دالة التقويم على العنصر الحالي من الحالة قبل إعادته بوصفه العدد العشوائيّ المُنتَج. ومن الأسهل أن نكتفي بعرض الشيفرة بدل شرح كيفية عملها:

_TEMPER_MASK_1 = 0x9d2c5680
_TEMPER_MASK_2 = 0xefc60000

def temper(y):
    y ^= uint32(y >> 11)
    y ^= uint32((y << 7) & _TEMPER_MASK_1)
    y ^= uint32((y << 15) & _TEMPER_MASK_2)
    y ^= uint32(y >> 18)
    return y

قد لا يكون ذلك واضحًا، خاصّة إن لم تكن معتادًا على الحساب الثنائي، لكنّ هذه الدالة متباينة (bijective) أو أحاديّة القيمة (one-to-one): فكلّ دخل من أعداد صحيحة بطول 32 بتًّا يقابله خرج واحد بالضبط، وبالمثل في الاتجاه المعاكس: لكلّ عدد صحيح بطول 32 بتًّا نحصل عليه كخرج، كان هناك بالضبط عدد صحيح واحد بطول 32 بتًّا يمكن أن يكون مصدره. ولأنّها تستعمل الإزاحتين يمينًا ويسارًا، فقد يبدو للوهلة الأولى أنّها تتخلّص من بيانات، ومن ثمّ يستحيل أن تكون قابلة للعكس. وصحيح أنّ تلك الإزاحات تطرح بعض البتّات، لكنّ العملية الحرجة هنا هي XOR المضمَّن (^=): فالإزاحات تُستعمل فقط لحساب أقنعة يُطبَّق XOR على القيمة المراد تقويمها. أمّا عمليات XOR نفسها فقابلة للعكس، ولأنّ كلّ عملية مستقلّة قابلة للعكس، فإنّ تركيبها كذلك قابل للعكس.

ولأنّ دالة التقويم أحاديّة القيمة، فإنّ هناك دالة معاكسة: دالة تعطيك المكافئ غير المُقوَّم لعدد. وقد لا يكون واضحًا لك كيف تبني تلك الدالة ما لم تكن ساحرًا في الحساب البتّيّ، لكنّ ذلك لا بأس به؛ ففي أسوأ الحالات يمكننا أن نلجأ إلى البحث الشامل. فلنفترض أننا نجرّب كلّ عدد صحيح بطول 32 بتًّا، ونتذكّر النتيجة في جدول. ثمّ حين نحصل على نتيجة، نبحث عنها في الجدول، فنجد الأصل. وسيكون على هذا الجدول أن يكون طوله 2^{32} \cdot 32 بتًّا على الأقلّ، أي نحو 17 غيغابايت جيّدة؛ وهو كبير، لكنّه ليس مستحيلًا.

ولحسن الحظّ، هناك طريقة أبسط بكثير لحساب معاكس دالة التقويم. وسنرى لماذا هذا مثير للاهتمام عند تقييم الأمن التشفيريّ لـ Mersenne Twister في القسم التالي. ولمن يهتمّ بالنتيجة، فإنّ دالة إلغاء التقويم تبدو هكذا:

def untemper(y):
    y ^= y >> 18
    y ^= ((y << 15) & _TEMPER_MASK_2)

    y = _undo_shift_2(y)
    y = _undo_shift_1(y)

    return y

def _undo_shift_2(y):
    t = y

    for _ in range(5):
        t <<= 7
        t = y ^ (t & _TEMPER_MASK_1)

    return t

def _undo_shift_1(y):
    t = y

    for _ in range(2):
        t >>= 11
        t ^= y

    return t

الأمن التشفيريّ

تذكّر أنّ الأمن التشفيريّ يشترط استحالة التنبّؤ بالمخارج المستقبليّة أو استرجاع المخارج السابقة انطلاقًا من المخارج الحالية. وMersenne Twister لا تتوفّر فيه هذه الخاصّية.

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

وتذكّر أنّ Mersenne Twister يُنتج عددًا عشوائيًّا بأخذ العنصر الحالي من الحالة، وتطبيق دالة التقويم، وإعادة النتيجة. وقد رأينا أيضًا أنّ لدى دالة التقويم دالة معاكسة. ومن ثمّ، إن استطعت رؤية خرج الخوارزمية وتطبيق معاكس دالة التقويم، فقد استرجعت عنصرًا واحدًا من عناصر الحالة الـ624.

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

ومرّة أخرى، هذا ليس ضعفًا في Mersenne Twister. فهو مصمَّم ليكون سريعًا ولديه خصائص عشوائيّة قويّة. وهو غير مصمَّم ليكون غير متوقّع، وهذه هي الخاصّية المميِّزة لمولّد الأعداد العشوائيّة شبه العشوائيّ الآمن تشفيريًّا.

---

1. دورة مولّد الأعداد العشوائيّة شبه العشوائيّ هي عدد الأعداد العشوائيّة التي يُنتجها قبل أن تتكرّر التسلسلة بأكملها. ↩︎