كاسومي
كاسومي هي خوارزمية تشفير كتلية تُستخدم في أنظمة الاتصالات المتنقلة UMTS و GSM و GPRS . في UMTS، تُستخدم كاسومي في خوارزميتي السرية ( f8 ) والنزاهة ( f9 ) تحت اسمي UEA1 وUIA1 على التوالي. [ 1 ] في GSM، تُستخدم كاسومي في مولدات تدفق المفاتيح A5/3 و A5/4 ، وفي GPRS في مولدات تدفق المفاتيح GEA3 و GEA4 .
صُممت خوارزمية KASUMI وفقًا لمعايير 3GPP لاستخدامها في نظام أمان UMTS من قِبل فريق خبراء خوارزميات الأمان (SAGE)، التابع لهيئة المعايير الأوروبية ETSI . [ 2 ] ونظرًا لضيق الوقت في عملية توحيد معايير 3GPP، اتفق فريق SAGE مع فريق المواصفات الفنية (TSG) التابع لـ 3GPP والمعني بجوانب نظام أمان الجيل الثالث (SA3) على تطوير خوارزمية موجودة سبق تقييمها، بدلًا من تطوير خوارزمية جديدة. [ 2 ] وقع اختيارهم على خوارزمية التشفير MISTY1 التي طورتها [ 3 ] شركة Mitsubishi Electric Corporation وحصلت على براءة اختراعها [ 4 ] . أُجريت تعديلات طفيفة على الخوارزمية الأصلية لتسهيل تنفيذها على الأجهزة ولتلبية المتطلبات الأخرى المحددة لأمن اتصالات الجيل الثالث.
تمت تسمية KASUMI على اسم الخوارزمية الأصلية MISTY1 —霞み(hiraganaかすみ, romaji kasumi ) هي الكلمة اليابانية التي تعني "ضباب".
في يناير 2010، نشر أور دانكلمان وناثان كيلر وآدي شامير ورقة بحثية تُظهر أنهم تمكنوا من اختراق كاسومي باستخدام هجوم المفتاح المرتبط وموارد حاسوبية متواضعة للغاية؛ هذا الهجوم غير فعال ضد MISTY1 . [ 5 ]
وصف
تم تحديد خوارزمية كاسومي في المواصفات الفنية الصادرة عن 3GPP. [ 6 ] كاسومي هي خوارزمية تشفير كتلية بمفتاح 128 بت ومدخلات ومخرجات 64 بت. جوهر كاسومي هو شبكة فيستل ذات ثماني جولات . وظائف الجولات في شبكة فيستل الرئيسية هي تحويلات شبكية غير قابلة للعكس تشبه تحويلات فيستل. في كل جولة، تستخدم وظيفة الجولة مفتاح جولة يتكون من ثمانية مفاتيح فرعية 16 بت مشتقة من المفتاح الأصلي 128 بت باستخدام جدول مفاتيح ثابت.
الجدول الزمني الرئيسي
يتم تقسيم المفتاح K ذو 128 بت إلى ثمانية مفاتيح فرعية K i ذات 16 بت :
بالإضافة إلى ذلك، يُستخدم مفتاح مُعدَّل K' ، مُقسَّم بدوره إلى مفاتيح فرعية K'i ، كل منها مكون من 16 بت . يُشتق المفتاح المُعدَّل من المفتاح الأصلي عن طريق عملية XOR مع القيمة 0x123456789ABCDEFFEDCBA9876543210 (التي تم اختيارها كقيمة افتراضية ).
يتم اشتقاق مفاتيح التقريب إما من المفاتيح الفرعية عن طريق التدوير الثنائي إلى اليسار بمقدار معين ومن المفاتيح الفرعية المعدلة (غير المتغيرة).
المفاتيح الدائرية هي كالتالي:
عمليات جمع فهرس المفتاح الفرعي دورية بحيث إذا كان i+j أكبر من 8، فيجب طرح 8 من النتيجة للحصول على فهرس المفتاح الفرعي الفعلي.
الخوارزمية
تقوم خوارزمية KASUMI بمعالجة الكلمة ذات 64 بت في نصفين، كل نصف 32 بت، اليسار () واليمين (). الكلمة المدخلة هي عبارة عن دمج النصفين الأيسر والأيمن من الجولة الأولى:
.
في كل جولة، يتم إجراء عملية XOR بين النصف الأيمن ومخرجات دالة الجولة، وبعد ذلك يتم تبديل النصفين:
حيث KL i و KO i و KI i هي مفاتيح الجولة للجولة رقم i .
تختلف دوال التقريب للأدوار الزوجية والفردية اختلافًا طفيفًا. في كلتا الحالتين، تكون دالة التقريب عبارة عن تركيب لدالتين FL i و FO i . بالنسبة للدورة الفردية
ولجولة متساوية
.
الناتج هو عبارة عن تجميع لمخرجات الجولة الأخيرة.
.
تقوم كل من دالتي FL و FO بتقسيم بيانات الإدخال ذات 32 بت إلى نصفين، كل نصف 16 بت. دالة FL هي عملية معالجة بتات غير قابلة للعكس، بينما دالة FO هي شبكة فيستل ثلاثية الجولات غير قابلة للعكس.
الوظيفة FL
المدخل x ذو 32 بتينقسم إلى نصفين، كل منهما مكون من 16 بتأولاً، النصف الأيسر من المدخلاتيتم إجراء عملية AND منطقية باستخدام مفتاح دائريويتم تدويرها إلى اليسار بمقدار بت واحد. ثم يتم تطبيق عملية XOR على نتيجة ذلك مع النصف الأيمن من المدخلات.للحصول على النصف الأيمن من الناتج.
ثم النصف الأيمن من الناتجيتم إجراء عملية OR ثنائية باستخدام مفتاح التقريبويتم تدويرها إلى اليسار بمقدار بت واحد. ثم يتم تطبيق عملية XOR على نتيجة ذلك مع النصف الأيسر من المدخلات.للحصول على النصف الأيسر من الناتج.
يكون ناتج الدالة عبارة عن دمج النصفين الأيسر والأيمن.
الوظيفة FO
المدخل x ذو 32 بتينقسم إلى نصفين، كل منهما مكون من 16 بتوتمت عبر ثلاث جولات من شبكة فيستل.
في كل جولة من الجولات الثلاث (المفهرسة بواسطة j التي تأخذ القيم 1 و 2 و 3) يتم تعديل النصف الأيسر للحصول على النصف الأيمن الجديد ويتم جعل النصف الأيمن هو النصف الأيسر للجولة التالية.
ناتج الدالة هو.
الوظيفة FI
الدالة FI هي شبكة غير منتظمة تشبه Feistel.
المدخل ذو 16 بتمن الوظيفةينقسم إلى نصفين منهاعرضها 9 بتات وعرضها 7 بتات.
أجزاء في النصف الأيسريتم خلطها أولاً بواسطة صندوق الاستبدال ذي 9 بتات (S-box) S9 ، ثم يتم إجراء عملية XOR بين النتيجة والنصف الأيمن الممتد بالأصفار.للحصول على النصف الصحيح الجديد ذي 9 بت.
أجزاء من النصف الأيمنيتم خلطها بواسطة صندوق الاستبدال S7 ذي 7 بتات ، ثم يتم إجراء عملية XOR بين النتيجة والبتات السبعة الأقل أهمية ( LS7 ) من النصف الأيمن الجديد.للحصول على النصف الأيسر الجديد ذي 7 بت.
الكلمة الوسيطةيتم إجراء عملية XOR مع المفتاح الدائري KI للحصول على منهاعرضها 7 بتات وعرضها 9 بتات.
أجزاء في النصف الأيمنثم يتم خلطها بواسطة صندوق الاستبدال S9 ذي 9 بتات ، ويتم إجراء عملية XOR بين النتيجة والنصف الأيسر الممتد بالأصفار.للحصول على النصف الصحيح من الناتج ذي 9 بتات الجديد.
وأخيرًا أجزاء النصف الأيسريتم خلطها بواسطة صندوق الاستبدال S7 ذي 7 بتات ، ثم يتم إجراء عملية XOR بين النتيجة والبتات السبعة الأقل أهمية ( LS7 ) من النصف الأيمن للمخرج.للحصول على النصف الأيسر ذي 7 بتمن الناتج.
الناتج هو دمج النصفين الأخيرين الأيسر والأيمن.
صناديق الاستبدال
يتم تعريف صندوقي الاستبدال (S-boxes) S7 وS9 في المواصفات باستخدام كلٍ من تعابير AND-XOR الثنائية وجداول البحث. تهدف التعابير الثنائية إلى التنفيذ على مستوى الأجهزة، ولكن من الشائع حاليًا استخدام جداول البحث حتى في تصميم الأجهزة.
يتم تعريف S7 بواسطة المصفوفة التالية:
إنت S7 [ 128 ] = { 54 , 50 , 62 , 56 , 22 , 34 , 94 , 96 , 38 , 6 , 63 , 93 , 2 , 18 , 123 , 33 , 55 , 113 , 39 , 114 , 21 , 67 , 65 , 12 , 47 , 73 , 46 , 27 , 25 , 111 , 124 , 81 , 53 , 9 , 121 , 79 , 52 , 60 , 58 , 48 , 101 , 127 , 40 , 120 ، 104 ، 70 ، 71 ، 43 ، 20 ، 122 ، 72 ، 61 ، 23 ، 109 ، 13 ، 100 ، 77 ، 1 ، 16 ، 7 ، 82 ، 10 ، 105 ، 98 ، 117 ، 116 ، 76 ، 11 ، 89 ، 106 ، 0 ، 125 ، 118 ، 99 ، 86 ، 69 ، 30 ، 57 ، 126 ، 87 ، 112 ، 51 ، 17 ، 5 ، 95 ، 14 ، 90 ، 84 ، 91 ، 8 ، 35 ، 103 ، 32 ، 97 ، 28 ، 66 ، 102 ، 31 ، 26 ،45 ، 75 ، 4 ، 85 ، 92 ، 37 ، 74 ، 80 ، 49 ، 68 ، 29 ، 115 ، 44 ، 64 ، 107 ، 108 ، 24 ، 110 ، 83 ، 36 ، 78 ، 42 ، 19 ، 15 ، 41 ، 88 ، 119 ، 59 ، 3 }؛يتم تعريف S9 بواسطة المصفوفة التالية:
إنت S9 [ 512 ] = { 167 , 239 , 161 , 379 , 391 , 334 , 9 , 338 , 38 , 226 , 48 , 358 , 452 , 385 , 90 , 397 , 183 , 253 , 147 ، 331 ، 415 ، 340 ، 51 ، 362 ، 306 ، 500 ، 262 ، 82 ، 216 ، 159 ، 356 ، 177 ، 175 ، 241 ، 489 ، 37 ، 206 ، 17 ، 0 , 333 , 44 ، ٢٥٤ ، ٣٧٨ ، ٥٨ ، ١٤٣ ، ٢٢٠ ، ٨١ ، ٤٠٠ ، ٩٥ ، ٣ ، ٣١٥ ، ٢٤٥ ، ٥٤ ، ٢٣٥ ، ٢١٨ ، ٤٠٥ ، ٤٧٢ ، ٢٦٤ ، ١٧٢ ، ٤٩٤ ، ٣٧١ ، ٢٩٠ ، ٣٩٩ ، ٧٦ ، ١٦٥ ، ١٩٧ ، ٣٩٥ ، ١٢١ ، ٢٥٧ ، ٤٨٠ ، ٤٢٣ ، ٢١٢ ، ٢٤٠ ، ٢٨ ، ٤٦٢ ، ١٧٦ ، ٤٠٦ ، ٥٠٧ ، ٢٨٨ ، ٢٢٣ ، ٥٠١ ، ٤٠٧ ، ٢٤٩ ، 265 ، 89 ، 186 ، 221 ، 428 ، 164 ، 74 ، 440 ، 196 ، 458 ، 421 ، 350 ، 163 ، 232 ،158 ، 134 ، 354 ، 13 ، 250 ، 491 ، 142 ، 191 ، 69 ، 193 ، 425 ، 152 ، 227 ، 366 ، 135 ، 344 ، 300 ، 276 ، 242 ، 437 ، 320 ، 113 ، 278 ، 11 ، 243 ، 87 ، 317 ، 36 ، 93 ، 496 ، 27 ، 487 ، 446 ، 482 ، 41 ، 68 ، 156 ، 457 ، 131 ، 326 ، 403 ، 339 ، 20 ، 39 ، 115 ، 442 ، 124 ، 475 ، 384 ، 508 ، 53 ، 112 ، 170 ، 479 ، 151 ، 126 ، 169 ، 73 ، 268 ، 279 ، 321 ، 168 ، 364 ، 363 ، 292 ، 46 ، 499 ، 393 ، 327 ، 324 ، 24 ، 456 ، 267 ، 157 ، 460 ، 488 ، 426 ، 309 ، 229 ، 439 ، 506 ، 208 ، 271 ، 349 ، 401 ، 434 ، 236 ، 16 ، 209 ، 359 ، 52 ، 56 ، 120 ، 199 ، 277 ، 465 ، 416 ، 252 ، 287 ، 246 ، 6، 83 ، 305 ، 420 ، 345 ، 153 ، 502 ، 65 ، 61 ، 244 ، 282 ، 173 ، 222 ، 418 ، 67 ، 386 ، 368 ، 261 ، 101 ، 476 ، 291 ، 195 ، 430 ، 49 ، 79 ، 166 ، 330 ، 280 ، 383 ، 373 ، 128 ، 382 ، 408 ، 155 ، 495 ، 367 ، 388 ، 274 ، 107 ، 459 ، 417 ، 62 ، 454 ، 132 ، 225 ، 203 ، 316 ، 234 ، 14 ، 301 ، 91 ، 503 ، 286 ، 424 ، 211 ، 347 ، 307 ، 140 ، 374 ، 35 ، 103 ، 125 ، 427 ، 19 ، 214 ، 453 ، 146 ، 498 ، 314 ، 444 ، 230 ، 256 ، 329 ، 198 ، 285 ، 50 ، 116 ، 78 ، 410 ، 10 ، 205 ، 510 ، 171 ، 231 ، 45 ، 139 ، 467 ، 29 ، 86 ، 505 ، 32 ، 72 ، 26 ، 342 ، 150 ، 313 ، 490 ، 431 ، 238 ، 411 ، 325 ،149 ، 473 ، 40 ، 119 ، 174 ، 355 ، 185 ، 233 ، 389 ، 71 ، 448 ، 273 ، 372 ، 55 ، 110 ، 178 ، 322 ، 12 ، 469 ، 392 ، 369 ، 190 ، 1 ، 109 ، 375 ، 137 ، 181 ، 88 ، 75 ، 308 ، 260 ، 484 ، 98 ، 272 ، 370 ، 275 ، 412 ، 111 ، 336 ، 318 ، 4 ، 504 ، 492 ، 259 ، 304 ، 77 ، 337 ، 435 ، 21 ، 357 ، 303 ، 332 ، 483 ، 18 ، 47 ، 85 ، 25 ، 497 ، 474 ، 289 ، 100 ، 269 ، 296 ، 478 ، 270 ، 106 ، 31 ، 104 ، 433 ، 84 ، 414 ، 486 ، 394 ، 96 ، 99 ، 154 ، 511 ، 148 ، 413 ، 361 ، 409 ، 255 ، 162 ، 215 ، 302 ، 201 ، 266 ، 351 ، 343 ، 144 ، 441 ، 365 ، 108 ، 298 ، 251 ، 34 ، 182 ، 509 ، 138 ، 210 ، 335، 133 ، 311 ، 352 ، 328 ، 141 ، 396 ، 346 ، 123 ، 319 ، 450 ، 281 ، 429 ، 228 ، 443 ، 481 ، 92 ، 404 ، 485 ، 422 ، 248 ، 297 ، 23 ، 213 ، 130 ، 466 ، 22 ، 217 ، 283 ، 70 ، 294 ، 360 ، 419 ، 127 ، 312 ، 377 ، 7 ، 468 ، 194 ، 2 ، 117 ، 295 ، 463 ، 258 ، 224 ، 447 ، 247 ، 187 ، 80 ، 398 ، 284 ، 353 ، 105 ، 390 ، 299 ، 471 ، 470 ، 184 ، 57 ، 200 ، 348 ، 63 ، 204 ، 188 ، 33 ، 451 ، 97 ، 30 ، 310 ، 219 ، 94 ، 160 ، 129 ، 493 ، 64 ، 179 ، 263 ، 102 ، 189 ، 207 ، 114 ، 402 ، 438 ، 477 ، 387 122 ، 192 ، 42 ، 381 ، 5 ، 145 ، 118 ، 180 ، 449 ، 293 ، 323 ، 136 ، 380 ، 43 ، 66 ، 60 ،455 ، 341 ، 445 ، 202 ، 432 ، 8 ، 237 ، 15 ، 376 ، 436 ، 464 ، 59 ، 461 ؛تحليل الشفرات
في عام 2001، قدم كوهن (2001) هجومًا تفاضليًا مستحيلاً على ست جولات من لعبة كاسومي. [ 7 ]
في عام ٢٠٠٣، أثبت إيلاد باركان وإيلي بيهام وناثان كيلر إمكانية تنفيذ هجمات الوسيط ضد بروتوكول GSM ، متجاوزين بذلك تشفير A5/3، وبالتالي تمكنوا من اختراق البروتوكول. مع ذلك، لا تستهدف هذه الطريقة تشفير A5/3. [ ٨ ] نُشرت النسخة الكاملة من بحثهم لاحقًا في عام ٢٠٠٦. [ ٩ ]
في عام 2005، نشر الباحثون الإسرائيليون إيلي بيهام ، وأور دانكلمان ، وناثان كيلر هجومًا على خوارزمية كاسومي باستخدام مفتاح مرتبط (هجوم بوميرانج)، وهو هجوم قادر على اختراق جميع جولات التشفير الثماني أسرع من البحث الشامل. [ 10 ] يتطلب هذا الهجوم 2 ^54.6 نصًا عاديًا مختارًا، كل منها مشفر باستخدام أحد المفاتيح الأربعة المرتبطة، ويبلغ تعقيده الزمني ما يعادل 2^ 76.1 عملية تشفير باستخدام كاسومي. مع أن هذا الهجوم غير عملي، إلا أنه يُبطل بعض البراهين المتعلقة بأمان بروتوكولات 3GPP التي اعتمدت على القوة المفترضة لخوارزمية كاسومي.
في عام 2010، نشر دانكلمان وكيلر وشامير هجومًا جديدًا يسمح للمهاجم باستعادة مفتاح A5/3 كاملًا باستخدام هجوم المفتاح المرتبط . [ 5 ] يتميز هذا الهجوم بانخفاض تعقيداته الزمنية والمكانية، ما مكّن الباحثين من تنفيذه في غضون ساعتين على جهاز كمبيوتر مكتبي بمعالج Intel Core 2 Duo، حتى باستخدام تطبيق KASUMI المرجعي غير المُحسَّن. ويشير الباحثون إلى أن هذا الهجوم قد لا ينطبق على طريقة استخدام A5/3 في أنظمة الجيل الثالث؛ إذ كان هدفهم الرئيسي هو دحض تأكيدات 3GPP بأن تغييراتهم على MISTY لن تؤثر بشكل كبير على أمان الخوارزمية.
انظر أيضاً
مراجع
- ↑ "مسودة تقرير SA3 رقم 38" (ملف PDF) . 3GPP. 2005.
- 1 2 "التقرير العام حول تصميم وتحديد وتقييم خوارزميات السرية والنزاهة القياسية لـ 3GPP" (ملف PDF) . 3GPP. 2009.
- ↑ ماتسوي، ميتسورو؛ توكيتا، توشيو (ديسمبر 2000). "تطوير خوارزميات التشفير MISTY وKASUMI وCamellia" (ملف PDF) . مجلة Mitsubishi Electric Advance . 100. شركة Mitsubishi Electric: 2-8 . ISSN 1345-3041 . مؤرشف من الأصل (ملف PDF) بتاريخ 24 يوليو 2008. تاريخ الاسترجاع: 6 يناير 2010 .
- ↑ براءة الاختراع الأمريكية رقم 7096369 ، ماتسوي، ميتسورو وتوكيتا ، توشيو، "جهاز تحويل البيانات وطريقة تحويل البيانات"، نُشرت في 19 سبتمبر 2002، وصدرت في 22 أغسطس 2006
- 1 2 أور دانكلمان؛ ناثان كيلر؛ آدي شامير (10-01-2010). "هجوم عملي على نظام التشفير A5/3 المستخدم في الجيل الثالث من الاتصالات الهاتفية GSM" .
{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal= - ↑ "3GPP TS 35.202: مواصفات خوارزميات السرية والنزاهة الخاصة بـ 3GPP؛ الوثيقة 2: مواصفات كاسومي" . 3GPP. 2009.
- ↑ كوهن، أولريش. تحليل تشفير MISTY ذي الجولات المخفضة . EUROCRYPT 2001. CiteSeerX 10.1.1.59.7609 .
- ↑ إيلاد باركان، إيلي بيهام ، ناثان كيلر. تحليل فوري لتشفير اتصالات GSM باستخدام النص المشفر فقط (ملف PDF) . مؤتمر CRYPTO 2003. الصفحات 600-616 . مؤرشف من النسخة الأصلية (PDF) بتاريخ 25 يناير 2020. تاريخ الاطلاع: 15 سبتمبر 2019 .
{{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط ) - ↑ إيلاد باركان، إيلي بيهام ، ناثان كيلر. "تحليل فوري لنصوص الاتصالات المشفرة بتقنية GSM باستخدام النص المشفر فقط، من إعداد باركان وبيهام من معهد التخنيون (النسخة الكاملة)" (ملف PDF) . مؤرشف من النسخة الأصلية (PDF) بتاريخ 25 يناير 2020. تم الاطلاع عليه بتاريخ 15 سبتمبر 2019 .
{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط ) - ↑ إيلي بيهام ، أور دانكلمان ، ناثان كيلر. هجوم المستطيل ذي المفتاح المرتبط على خوارزمية كاسومي الكاملة . آسيا كريبت 2005. الصفحات 443-461 . مؤرشف من الأصل (ps) بتاريخ 11-10-2013.
{{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
روابط خارجية
- الصفحة الرئيسية لناثان كيلر
- تشفير الكتل
- شفرات فيستل
- تشفيرات الكتلة المكسورة
- معايير 3GPP
- منتجات وخدمات ومعايير شركة ميتسوبيشي إلكتريك
