شيفرات الكتل

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

   *David Kahn*

الوصف

شيفرة الكتل (block cipher) هي خوارزمية تشفّر كتلًا ذات طول ثابت. ودالة التشفير E تحوّل كتل النصّ الصريح (plaintext) P إلى كتل نصّ مشفَّر (ciphertext) C باستعمال مفتاح سرّي k:

C = E(k, P)

كتل النصّ الصريح وكتل النصّ المشفَّر هي تسلسلات من البتّات، ويتطابق حجمها دائمًا. وحجم الكتلة (block size) عند شيفرة الكتل هو حجم ثابت. أمّا Keyspace فهو مجموعة كلّ المفاتيح الممكنة.

وبعد ما نحوّل كتل النصّ الصريح إلى كتل نصّ مشفَّر، فإنّ هذه تُفكّ لاحقًا لاستعادة كتلة النصّ الصريح الأصلية. وتُنتَج كتلة النصّ الصريح الأصلية P باستعمال دالة فكّ التشفير D. وهي تأخذ كتلة النصّ المشفَّر C والمفتاح k (وهو المفتاح نفسه المستعمل في تشفير الكتلة) كمدخلين.

P = D(k, C)

أو، بصريًّا، على شكل كتل:

تمثيل بصريّ لشيفرة الكتل

شيفرة الكتل مثال على نظام تشفير بالمفتاح المتماثل (symmetric-key encryption)، المعروف أيضًا بنظام تشفير بالمفتاح السرّي (secret-key encryption). إذ يُستعمل المفتاح السرّي نفسه في التشفير وفي فكّ التشفير معًا. وسنقابل في وقت لاحق من الكتاب بين هذا وبين خوارزميات التشفير بالمفتاح العام (public-key encryption)، التي لها مفتاحان مختلفان: أحدهما للتشفير والآخر لفكّ التشفير.

شيفرة الكتل هي تبديل مُفتَّح بمفتاح (keyed permutation). وهي تبديل (permutation) لأنّ شيفرة الكتل تُسقِط كلّ كتلة ممكنة على كتلة أخرى. وهي أيضًا تبديل مُفتَّح بمفتاح لأنّ المفتاح يحدّد تمامًا أيّ الكتل تُسقَط على أيّها. ومن المهمّ أن تكون شيفرة الكتل تبديلًا، لأنّ على المستقبِل أن يُسقِط الكتل عائدةً إلى كتلها الأصلية.

نوضّح ذلك بالنظر إلى شيفرة كتل ذات حجم كتلة صغير وغير عمليّ، هو 4 بتّات. أي 2^4 = 16 كتلة ممكنة. وبما أنّ كلّ كتلة تُسقَط على رقم ست عشري (hexadecimal digit)، فإنّنا نمثّل الكتل بذلك الرقم. وتوضّح fig-BlockCipherBlocks الكتل التي تعمل عليها الشيفرة.

العقد الست عشرة التي تعمل عليها شيفرة الكتل

العقد الستّة عشرة كلّها التي تعمل عليها شيفرة الكتل. ويُشار إلى كلّ عقدة برقم ست عشري.

وبعد أن نختار مفتاحًا سرّيًا، تستعمله شيفرة الكتل لتحديد تشفير أيّ كتلة بعينها. ونوضّح تلك العلاقة بسهم. فذيل السهم يحمل الكتلة قبل تشفيرها بـE تحت المفتاح k، أمّا رأس السهم فيُسقَط على الكتلة المشفَّرة.

تبديل التشفير تحت مفتاح معيّن

تبديل تشفير تنتجه شيفرة الكتل تحت مفتاح معيّن k.

لاحظ في fig-BlockCipherEncryption أنّ التبديل ليس دورة واحدة كبيرة فحسب، بل يحوي دورة كبيرة من 7 عناصر، وعدّة دورات أصغر من 4 و3 وعنصرين لكلٍّ منها. ومن الممكن تمامًا أن يُشفَّر عنصر إلى نفسه. وهذا هو المتوقَّع عند اختيار تبديلات عشوائية، وهو ما تفعله شيفرة الكتل تقريبًا؛ وهو لا يدلّ على وجود خلل في شيفرة الكتل.

وعنما تفكّ التشفير بدلًا من التشفير، فإنّ شيفرة الكتل تحسب التبديل المعكوس (inverse permutation). وفي fig-BlockCipherDecryption نحصل على الرسم نفسه. والفرق بين الرسمين أنّ رؤوس الأسهم كلّها تشير في الاتجاه المعاكس.

تبديل فكّ التشفير تحت المفتاح نفسه

تبديل فكّ التشفير الذي تنتجه شيفرة الكتل تحت المفتاح نفسه k. وهو معكوس تبديل التشفير، إذ إنّ رؤوس الأسهم كلّها انقلبت.

يحدّد المفتاح أيّ الكتل تُسقَط على أيّ الكتل. ويؤدي مفتاح مختلف إلى مجموعة أسهم مختلفة، كما ترى في fig-BlockCipherEncryptionDifferentKey.

تبديل التشفير تحت مفتاح مختلف

تبديل تشفير تنتجه شيفرة الكتل تحت مفتاح مختلف.

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

معرفة عدد من أزواج (المدخل، المخرج) تحت مفتاح معيّن لا ينبغي أن تمنحك أيّ معلومة عن أيّ أزواج (مدخل، مخرج) أخرى تحت ذلك المفتاح ^[1]. وطالما أننا نتحدّث عن شيفرة كتل مثالية افتراضية، فلا توجد طريقة أسهل لفكّ تشفير كتلة من «تفريغ المفتاح بالقوة الغاشمة» (brute-force): أي أن تُجرّب كلّ مفتاح على حدة حتى تجد المفتاح الصحيح.

شيفرة الكتل التجريبية التي نستخدمها للعرض تحوي كتلًا بطول 4 بتّات، أي 2^4 = 16 احتمالًا. أمّا شيفرات الكتل الحديثة الحقيقية فأحجام كتلها أكبر بكثير، مثل 128 بتًّا، أي 2^{128} (أي أكثر قليلًا من 10^{38.5}) كتلة ممكنة. وتخبرنا الرياضيات بأنّ هناك n! (تُنطق «مضروب n») تبديلًا مختلفًا لمجموعة من n عنصرًا. ويُعرَّف بأنه حاصل ضرب كلّ الأعداد من 1 حتى n ضمنًا:

n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n - 1) \cdot n

تنمو المضروبات بوتيرة مذهلة. فمثلًا، 5! = 120 و10! = 3628800، وتستمرّ النسبة في التزايد. وعدد تبديلات مجموعة كتل شيفرة ذات حجم كتلة 128 بتًّا هو (2^{128})!. و2^{128} وحدها كبيرة أصلًا (تحتاج 39 رقمًا لكتابتها)، لذا فإنّ (2^{128})! عددٌ كبيرٌ يُذهل العقل ولا يمكن استيعابه. وأحجام المفاتيح الشائعة لا تتجاوز المدى من 128 إلى 256 بتًّا، لذا لا تستطيع الشيفرة أن تنفّذ إلّا عددًا من التبديلات يقع بين 2^{128} و2^{256}. وهذا جزء ضئيل جدًّا من جميع التبديلات الممكنة للكتل، لكنّ ذلك مقبول: فذلك الجزء الضئيل ما يزال بعيدًا كلّ البعد عن الصغر بما يكفي ليُجرّبه المهاجم على نحو شامل.

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

AES

أكثر شيفرات الكتل استعمالًا في الوقت الحالي هي AES.

على خلاف سابقتها DES (والذي سننظر إليه بتفصيل أكبر في الفصل التالي)، اختيرت AES عبر مسابقة علنية خضعت لتحكيم الأقران، وذلك بعد دعوة مفتوحة لتقديم المقترحات. وقد تضمّنت هذه المسابقة عدّة جولاتٍ عُرض فيها جميع المتنافسين، بعد إخضاعهم لتحليل تشفيري (cryptanalysis) مطوّل، ثمّ صُوِّت عليها. وحظيت عملية اختيار AES بترحيب واسع من خَبَراء التشفير، وتُعدّ العمليات المشابهة عمومًا الطريقة المفضّلة لاختيار المعايير التشفيرية.

قبل أن تُختار معيار التشفير المتقدّم (Advanced Encryption Standard)، كانت الخوارزمية معروفة باسم Rijndael، وهو اسم مشتقّ من اسمَي العائلة لخبيرَي التشفير البلجيكيَّين اللذين صمّماها: Vincent Rijmen وJoan Daemen. وقد عرّفت خوارزمية Rijndael عائلةً من شيفرات الكتل، تكون أحجام كتلها وأحجام مفاتيحها أيّ مضاعفات لـ32 بتًّا بين 128 بتًّا و256 بتًّا. daemen:aes وعندما صارت Rijndael هي AES عبر عملية توحيد المعايير FIPS، قُيّدت معاملاتها بحجم كتلة قدره 128 بتًّا وأحجام مفاتيح قدرها 128 و192 و256 بتًّا. fips:aes

لا توجد هجمات عملية معروفة على AES. ورغم أنّه قدطرأ بعض التطوّر في السنوات الأخيرة، فإنّ معظمه يتضمّن هجمات على مفاتيح ذات صلة (related-key attacks) cryptoeprint:2009:317، وبعضها فقط على نسخ AES مخفَّضة الجولات (reduced-round) cryptoeprint:2009:374.

تعتمد الخوارزميات المتماثلة عادةً على دالة جولة (round function) تُكرَّر عددًا من المرّات. ويتضمّن كلّ استدعاء عادةً «مفتاح جولة» (round key) مشتقًّا من المفتاح الرئيسي. والنسخة المخفَّضة الجولات أسهل في الهجوم عمدًا. ويمكن أن تمنح هذه الهجمات بصيرةً حول مدى صمود الشيفرة الكاملة.

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

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

نظرة أقرب إلى Rijndael

متقدّم

تتألف AES من عدّة خطوات مستقلّة. فعلى المستوى العامّ، AES هي substitution-permutation network أي شبكة استبدال وتبديل.

جدول المفاتيح '''''''''''

تحتاج AES إلى مفاتيح منفصلة لكلّ جولة في الخطوات التالية. وجدول المفاتيح (key schedule) هو العملية التي تستعملها AES لاستخراج مفاتيح بطول 128 بتًّا لكلّ جولة انطلاقًا من مفتاح رئيسي واحد.

أولًا، يُفصَل المفتاح إلى أربعة أعمدة بايتية. ثمّ يُدار المفتاح ويُمرَّر كلّ بايت على صندوق استبدال (S-box) يحوّله إلى شيء آخر. ثمّ يُجرى XOR لكلّ عمود مع ثابت جولة. أمّا الخطوة الأخيرة فهي إجراء XOR للناتج مع مفتاح الجولة السابقة.

ثمّ يُجرى XOR لبقية الأعمدة مع مفتاح الجولة السابقة لإنتاج الأعمدة المتبقّية.

استبدال البتّات (SubBytes) '''''''''''''''

استبدال البتّات (SubBytes) هو الخطوة التي تطبّق صندوق الاستبدال (S-box) في AES. ويقوم صندوق الاستبدال نفسه باستبدال بايت ببايت آخر، ويُطبَّق هذا الصندوق على كلّ بايت في حالة AES.

ويعمل بأخذ المقلوب الضربيّ (multiplicative inverse) فوق حقل غالوا (Galois field)، ثمّ بتطبيق تحويل تآلُفيّ (affine transformation) بحيث لا توجد قيم x تُحقّق x \xor S(x) = 0 أو x \xor S(x)=\texttt{0xff}. وبعبارة أخرى: لا توجد قيم لـx يحوّلها صندوق الاستبدال إلى x نفسه، أو إلى x مع قلب كلّ بتّاتها. ويجعل هذا الشيفرة مقاومة للتحليل التشفيري الخطّي، بخلاف خوارزمية DES الأسبق، التي سبّبت صندوق استبدالها الخامس مشكلات أمنية خطيرة. خطوة استبدال البتّات (SubBytes)

ولصالح DES، كانت الهجمات الخطّية غير معروفة علنًا وقت تصميمه. إزاحة الصفوف (ShiftRows) '''''''''''''''

بعد تطبيق خطوة استبدال البتّات على البايتات الستّة عشر للكتلة، تُزيح AES الصفوف في المصفوفة 4 \times 4:

خطوة إزاحة الصفوف (ShiftRows)

مزج الأعمدة (MixColumns) '''''''''''''''

تضرب خطوة مزج الأعمدة (MixColumns) كلّ عمود في الحالة في مضروب ثابت.

تمثّل خطوتا إزاحة الصفوف ومزج الأعمدة خصائص الانتشار (diffusion) في AES.

خطوة مزج الأعمدة (MixColumns)

إضافة مفتاح الجولة (AddRoundKey) '''''''''''''''

وكما يوحي الاسم، تضيف خطوة إضافة مفتاح الجولة البايتات من مفتاح الجولة الذي ينتجه جدول المفاتيح إلى حالة الشيفرة.

خطوة إضافة مفتاح الجولة (AddRoundKey)

DES و3DES

DES إحدى أقدم شيفرات الكتل التي لقيت استعمالًا واسعًا. وقد نُشرت بوصفها معيارًا رسميًّا من معايير FIPS سنة 1977. ولم تعد تُعدّ آمنة اليوم، وذلك أساسًا بسبب صغر حجم مفتاحها البالغ 56 بتًّا. (وتقبل خوارزمية DES في الواقع مفتاحًا بطول 64 بتًّا، لكنّ البتّات الثمانية المتبقّية تُستعمل لفحص التكافؤ (parity check) فحسب، وتُطرح فورًا.) ولا ينبغي استعمالها في الأنظمة الجديدة. وعلى العتاد الحديث، يمكن كسر DES بالقوة الغاشمة في أقلّ من يوم. sciengines:breakdes

وبهدف إطالة عمر خوارزمية DES، على نحو يسمح بإعادة استعمال كثير من جهد تطوير العتاد المنفَق، ابتكر الناس نظام 3DES: وهو نظام يُشفَّر فيه الدخل أوّلًا، ثمّ يُفكّ تشفيره، ثمّ يُشفَّر من جديد:

C = E_{DES}(k_1, D_{DES}(k_2, E_{DES}(k_3, p)))

يوفّر هذا النظام تحسينين:

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

يمكن اختيار المفاتيح الثلاثة جميعًا باستقلال تامّ (فتُنتج 168 بتًّا من المفاتيح)، أو k_3 = k_1 (فتُنتج 112 بتًّا من المفاتيح)، أو k_1 = k_2 = k_3، وهو بالطبع DES المجرّد القديمة (بمفتاح 56 بتًّا). وفي خيار المفتاح الأخير، يُلغي فكّ التشفير الأوسط أثر أوّل عملية تشفير، فلا تحصل في الواقع إلّا على أثر عملية التشفير الأخيرة. وهذا مقصود ليكون وضعًا للتوافق الخلفي مع أنظمة DES القائمة. ولو كان تعريف 3DES هو E(k_1, E(k_2, E(k_3, p)))، لاستحال استعمال تطبيقات 3DES في الأنظمة التي تتطلّب التوافق مع DES. وهذا مهمّ بصفة خاصة في تطبيقات العتاد، حيث لا يكون من الممكن دائمًا توفير واجهة ثانوية عادية بـ«DES المفرد» إلى جانب واجهة 3DES الرئيسة.

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

وتوجد بدائل أفضل بكثير، مثل AES. فهي ليست أكثر أمانًا من 3DES فحسب، بل أسرع عادةً بكثير وبكثير. وعلى العتاد نفسه وفي وضع التشغيل (mode of operation) نفسه (سنشرح معناه في الفصل التالي)، تستهلك AES-128 عددًا من دورات المعالج (cycles) لا يتجاوز 12.6 دورة لكلّ بايت، بينما تستهلك 3DES حتى 134.5 دورة لكلّ بايت. cryptopp:bench وبرغم أنّها أسوأ من ناحية الأمان، فإنّها أبطأ حرفيًّا بمقدار رتبة كاملة.

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

وفيما كانت 3DES أسوأ بدرجة واضحة من ناحية الأداء وأسوأ قليلًا من ناحية الأمان، فإنّها لا تزال الأداة الأساسية التي تقوم عليها صناعة التمويل. ولأنّ ثَمّة كمًّا هائلًا من المعايير القائمة مع استمرار إنشاء معايير جديدة، في صناعة شديدة التحفّظ التقني بحيث لا تزال Fortran وCobol تحكمان في الحواسيب المركزية الضخمة، فمن المرجّح أن تستمرّ 3DES في الاستعمال سنوات عديدة قادمة، ما لم تنحدر اختراقات تحليلية تشفيرية كبيرة تهدّد أمنها.

المشكلات المتبقّية

حتى مع شيفرات الكتل، ما تزال هناك بعض المشكلات غير المحلولة.

فمثلًا، لا يمكننا إلّا إرسال رسائل ذات طول محدود جدًّا: وهو طول كتلة شيفرة الكتل. ومن الواضح أنّنا نودّ القدرة على إرسال رسائل أكبر بكثير، أو، والأفضل، تدفّقات ذات حجم غير محدّد. وسنتصدّى لهذه المشكلة بشيفرة تيار stream cipher <stream-ciphers>.

ورغم أنّنا قلّلنا حجم المفتاح بصورة هائلة (من الحجم الإجمالي لكلّ البيانات المُرسَلة في نظام وسادة المرّة الواحدة، في مقابل بضعة بايتات في معظم شيفرات الكتل)، فإنّنا ما زلنا بحاجة إلى معالجة مسألة الاتفاق على بايتات المفتاح تلك القليلة، لا سيّما عبر قناة غير آمنة. وسنتصدّى لهذه المسألة في فصل لاحق عبر key exchange protocol <key-exchange>.

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

السابق الاو الحصري (XOR) التالي شيفرات التيار