کاسومی
کاسومی یک رمزگذاری قطعهای است که در سامانه جهانی مخابرات سیار، جیاسام، سرویس بسته امواج رادیویی تلفن همراه استفاده میشود. در سامانه جهانی مخابرات سیار، کاسومی به عنوان الگوریتمهای رازداری و یکپارچگی دادهها به ترتیب به نامهای (به انگلیسی: UEA1) و (به انگلیسی: UIA1) به کار رفتهاست. در جیاسام، کاسومی در تولیدکنندهٔ جریانکلید برای A5/3 به کار رفتهاست. در سرویس بسته امواج رادیویی، کاسومی در تولیدکنندهٔ جریانکلید برای GEA3 به کار رفتهاست.
عمومی | |
---|---|
طراحان | میتسوبیشی الکتریک |
مشتقشده از | MISTY1 |
کاسومی برای پروژه مشارکتی نسل سوم شبکه تلفن همراه (به انگلیسی: 3GPP) طراحی شده بود تا به وسیلهٔ گروهی از متخصصان الگوریتمهای امنیتی (به انگلیسی: SAGE) (بخشی از سازمان استانداردهای اروپایی به نام نهاد استانداردهای مخابراتی اروپا) در سامانه امنیتی سامانه جهانی مخابرات سیار به کار رود.
به خاطر برنامهٔ فشرده برای استانداردسازی 3GPP، گروه SAGE پیشنهاد گروه فنی مخصوص 3GPP (به انگلیسی: TSG) را در مورد بخش امنیتی 3G (به انگلیسی: SA3) قبول کرد. پیشنهاد به این صورت بود که برای بخش امنیتی، به جای توسعه یک الگوریتم رمزگذاری جدید، از یک الگوریتم موجود که مورد ارزیابی قرار گرفته بود، استفاده شود. آنها برای این کار، الگوریتم (به انگلیسی: MISTY1) را که توسعهیافته بود و توسط میتسوبیشی الکتریک، ثبتشده بود را انتخاب کردند. اصل الگوریتم برای پیادهسازی راحتتر توسط سختافزار و فراهمکردن دیگر مجموعه نیازمندیهای لازم برای امنیت ارتباطی تلفنهای همراه 3G، مقداری تغییر کرد.
اسم کوسامی که بعد از نام اصلی الگوریتم (به انگلیسی: MISTY1) به علت معادل ژاپنی برای (به انگلیسی: mist) انتخاب شد. (به هیراگانا معادل かすみ و به روماجی معادل kasumi است)
در ژانویه ۲۰۱۰، اوردانکلمن (به انگلیسی: Orr Dunkelman)، ناتانکلر (به انگلیسی: Nathan Keller) و ادی شامیر یک مقالهای را منتشر نمودند که در آن نشانداده شده بود که میتوان الگوریتم کوسامی را با یک حمله کلیدهای مرتبط (به انگلیسی: Related-key attack) و منابع محاسباتی خیلی مدرن، شکست. البته این حمله در برابر MYSTY1 بیاثر بود.
توضیحات
کاسومی یک الگوریتم است که به صورت خاص در تکنولوژیهای 3GPP تعریفشدهاست. کاسومی یک رمزگذاری قطعهای با کلیدی به طول ۱۲۸ بیت، ورودی و خروجی ۶۴ بیتی است. هستهٔ اصلی کاسومی یک شبکهٔ فایستل با ۸ دور میباشد. توابع هر دور شبکهٔ فایستل، تبدیلات شبکهای برگشت هستند. در هر دور، تابع مربوط به دور از یک زیرکلید ۱۶ بیتی که از طریق کلید ۱۲۸ بیتی اصلی الگوریتم و توسط یک زمانبند کلید ثابت تولیدشده است، استفاده میکند.
زمانبند کلید
کلید اصلی ۱۲۸ بیتی به اسم
همچنین در کنار کلید اصلی، یک کلید تغییریافته به اسم
این زیرکلیدهای هر دور، به وسیلهٔ چرخش بیتی به سمت چپ با مقداری مشخص یا از طریق کلیدهای تغییریافته (بدون تغییر) محاسبه میشوند.
کلیدهای ۸ دو به صورت زیر هستند:
زیراندیسهای به کار رفته در فرمولهای بالا به صورت گردشی است، یعنی اگر یک زیراندیس به صورت
الگوریتم
الگوریتم کاسومی یک کلید ۶۴ بیتی را به صورت ۲ بخش ۳۲ بیتی در قالب بخش چپ (
در هر دور، بخش سمت راست (
تابع دور (به انگلیسی: round function) برای دورهای زوج و فرد متفاوت میباشد. با این حال، در هر دور، تابع دور یک تابع از دو بخش
و برای دورهای زوج، تابع دور به صورت زیر است:
خروجی الگوریتم، الحاق بخشهای خروجی دور آخر میباشد.
هر دو تابع
تابع
ورودی ۳۲ بیتی (
بخش سمت چپ ورودی (
سپس خروجی قبلی (
در نهایت خروجی، الحاق دو بخش سمت چپ و راست میباشد:
تابع
ورودی ۳۲ بیتی (
سپس در درون ۳ دور از شبکهٔ فایستل عبور میکند.
در هر یک از سه دور شبکهٔ فایستل (دارای اندیسهای ۱ و ۲ و ۳) سمت چپ تغییر میکند تا سمت راست دور بعدی را بسازد و سمت راست، به عنوان سمپ چپ دور بعدی استفاده میشود.
در نهایت خروجی تابع به صورت روبرو خواهد بود:
تابع
تابع
ورودی ۱۶ بیتی (
طول بخش
بیتهای موجود در بخش چپ (
بیتهای موجود در بخش راست (
در اینجا کلمهٔ میانی
بیتهای موجود در بخش راست (
بیتهای موجود در بخش چپ (
در نهایت خروجی تابع از الحاق دو بخش نهایی چپ و راست تولید میشود:
جعبههای جایگزینی
جعبههای جایگزنی به نامهای S7 و S9 هر دو توسط عملیات عطف منطقی و یای انحصاری و جدولها تعریف میشوند. عملیاتی منطقی برای پیادهسازی سختافزاری استفاده میشوند ولی امروزه اکثراً برای نمایش آن از جدولها استفاده میشوند. (به انگلیسی: look-up table)
جدول جایگزینی S7 به صورت زیر تعریفشدهاست:
int 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 به صورت زیر تعریفشدهاست:
int 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,254,378, 58,143,220, 81,400,
95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,
165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,
501,407,249,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
};
رمزشناسی
در سال ۲۰۰۱، یک حلمه دیفرانسیلی غیرممکن (به انگلیسی: impossible differential attack) برای ۶ دور کاسومی توسط Kühn معرفی شد.
در سال ۲۰۰۳، الادبارکن (به انگلیسی: Elad Barkan)، الیبیهام (به انگلیسی: Eli Biham) و ناتانکلر (به انگلیسی: Nathan Keller) یک حملهٔ مرد میانی را در برابر پروتکل جیاسام معرفی کردند که مانع از رمزگذاری A5/3 شده و سبب شکستن پروتکل شد. اما این روش به رمزگذاری A5/3 حمله نکرد. نسخهٔ کامل این مقاله بعدها رد سال ۲۰۰۶ منتشر شد.
در سال ۲۰۰۵، الیبیهام (به انگلیسی: Eli Biham)، یک محقق اسرائیلی، اردانکلمن (به انگلیسی: Orr Dunkelman) و ناتنکلر (به انگلیسی: Nathan Keller) یک مقاله در مورد حمله بومرنگ (به انگلیسی: Boomerang attack) برای کاسومی منتشر نمود که میتواند خیلی سریعتر از حمله جستجوی فراگیر ۸ دور کاسومی را بشکند. این حمله به 2 متن آشکار که هر کدام توسط ۴ کلید مرتبط به هم، رمز شدهاند نیاز دارد و دارای پیچیدگی زمانی برابر با 2 عمل رمزگذاری کاسومی است. اگر چه این یک حمله کاربردی نیست، اما اعتبار برخی از اثباتها را در مورد امنیت رمزگذاری پروتکل 3GPP را که بر اساس امنیت از پیش تعیینشدهٔ کاسومی بود، بیارزش کرد.
در سال ۲۰۱۰، دانلکمن (به انگلیسی: Dunkelman) و کلر (به انگلیسی: Keller) و شمیر (به انگلیسی: Shamir) یک حملهٔ جدید را منتشر نمودند که یک شنونده اجازه میداد تا بتواند کلید کامل A5/3 را توسط حملهٔ کلیدهای مرتبط (به انگلیسی: related-key attack) بدست آورد. مدت زمان و پیچیدگی فضای حمله آن قدر کم بود که حتی نویسندگان معتقد بودند که با یک کامپیوتر اینتل کور ۲ و حتی استفاده از پیادهسازیهای غیر بهینهٔ کاسومی، آن را میتوان در ۲ ساعت شکست. نویسندگان اشاره کرده بودند که شاید حمله برای روش A5/3 که در سامانههای 3G استفاده شدهاست، قابل استفاده نباشد. دلیل اصلی آنها این بود که 3GPP تضمین کرده بود که تغییرات آنها در الگوریتم MISTY، به صورت جدی امنیت الگوریتم را تحت تأثیر قرار ندادهاست.
برای مطالعهٔ بیشتر
منابع
- ↑ "Draft Report of SA3 #38" (PDF). 3GPP. 2005.
- ↑ "General Report on the Design, Speification and Evaluation of 3GPP Standard Confidentiality and Integrity Algorithms" (PDF). 3GPP. 2009.
- ↑ Matsui, Mitsuru; Tokita, Toshio (Dec 2000). "MISTY, KASUMI and Camellia Cipher Algorithm Development" (PDF). Mitsibishi Electric Advance. Mitsibishi Electric corp. 100: 2–8. ISSN 1345-3041. Archived from the original (PDF) on 2008-07-24. Retrieved 2010-01-06.
- ↑ US 7096369, Matsui, Mitsuru & Toshio Tokita, "Data Transformation Apparatus and Data Transformation Method", published Sep. 19, 2002, issued Aug. 22, 2006
- ↑ Orr Dunkelman; Nathan Keller; Adi Shamir (2010-01-10). "A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony".
- ↑ "3GPP TS 35.202: Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification". 3GPP. 2009.
- ↑ Kühn, Ulrich. Cryptanalysis of Reduced Round MISTY. EUROCRYPT 2001. CiteSeerX 10.1.1.59.7609.
- ↑ Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (PDF). CRYPTO 2003. pp. 600–616.
- ↑ Elad Barkan, Eli Biham, Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)" (PDF).
- ↑ Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. ASIACRYPT 2005. pp. 443–461. Archived from the original (ps) on 2013-10-11.