KASUMI - KASUMI - Wikipedia

KASUMI bir blok şifreleme kullanılan UMTS, GSM, ve GPRS mobil iletişim UMTS'de KASUMI, gizlilik (f8) ve bütünlük algoritmalar (f9) sırasıyla UEA1 ve UIA1 adlarıyla.^[1]GSM'de KASUMI, A5 / 3 anahtar akışı oluşturucu ve GPRS'de GEA3 anahtar akış üreteci.

KASUMI için tasarlandı 3GPP UMTS güvenlik sisteminde kullanılmak üzere Güvenlik Algoritmaları Uzmanlar Grubu (SAGE), Avrupa standartları kuruluşunun bir parçası ETSI.^[2]3GPP standardizasyonundaki zamanlama baskıları nedeniyle, yeni bir şifre geliştirmek yerine, SAGE, geliştirmeyi halihazırda bazı değerlendirmelerden geçmiş mevcut bir algoritmaya dayandırmak için 3G güvenliğinin (SA3) sistem yönleri için 3GPP teknik özellik grubu (TSG) ile anlaştı.^[2]Şifreleme algoritmasını seçtiler MISTY1 gelişmiş^[3]ve patentli^[4]tarafından Mitsubishi Electric Corporation Orijinal algoritma, daha kolay donanım uygulaması ve 3G mobil iletişim güvenliği için belirlenen diğer gereksinimleri karşılamak için biraz değiştirildi.

KASUMI, orijinal algoritmanın adını almıştır MISTY1 — 霞 み (Hiragana か す み, romaji Kasumi ) Japonca "sis" için kelime.

Ocak 2010'da, Orr Dunkelman, Nathan Keller ve Adi Shamir Kasumi'yi bozabileceklerini gösteren bir makale yayınladı. ilgili anahtar saldırısı ve çok mütevazı hesaplama kaynakları; bu saldırıya karşı etkisiz MISTY1.^[5]

Açıklama

KASUMI algoritması bir 3GPP teknik şartnamesinde belirtilmiştir.^[6]KASUMI, 128-bit anahtar ve 64-bit giriş ve çıkışa sahip bir blok şifreleyicidir. KASUMI'nin çekirdeği sekiz turlu Feistel ağı. Ana Feistel ağındaki yuvarlak işlevler, geri döndürülemez Feistel benzeri ağ dönüşümleridir. Her turda, yuvarlak işlevi, sabit bir anahtar çizelgesi kullanılarak orijinal 128 bit anahtardan türetilen sekiz adet 16 bitlik alt anahtardan oluşan yuvarlak bir anahtar kullanır.

Anahtar program

128 bit anahtar K sekiz 16 bit alt anahtara bölünmüştür K_ben:

${ displaystyle K = K_ {1} | K_ {2} | K_ {3} | K_ {4} | K_ {5} | K_ {6} | K_ {7} | K_ {8 } ,}$

Ek olarak değiştirilmiş bir anahtar K 'benzer şekilde 16 bit alt anahtarlara bölünmüştür K '_ben, kullanıldı. Değiştirilen anahtar, 0x123456789ABCDEFFEDCBA9876543210 ile XORing tarafından orijinal anahtardan türetilmiştir ( "kolumda hiçbir şey yok" numarası ).

Yuvarlak tuşlar ya alt anahtarlardan belirli bir miktarda sola bitsel dönüş ile ve değiştirilmiş alt anahtarlardan (değişmemiş) türetilir.

Yuvarlak tuşlar aşağıdaki gibidir:

${ displaystyle { begin {array} {lcl} KL_ {i, 1} & = & { rm {ROL}} (K_ {i}, 1) KL_ {i, 2} & = & K '_ { i + 2} KO_ {i, 1} & = & { rm {ROL}} (K_ {i + 1}, 5) KO_ {i, 2} & = & { rm {ROL}} (K_ {i + 5}, 8) KO_ {i, 3} & = & { rm {ROL}} (K_ {i + 6}, 13) KI_ {i, 1} & = & K ' _ {i + 4} KI_ {i, 2} & = & K '_ {i + 3} KI_ {i, 3} & = & K' _ {i + 7} end {dizi}}}$

Alt anahtar dizini eklemeleri döngüseldir, böylece i + j 8'den büyük olan birinin gerçek alt anahtar indeksini elde etmek için sonuçtan 8 çıkarması gerekir.

Algoritma

KASUMI algoritması 64 bit kelimeyi iki 32 bitlik yarıda, solda (${ displaystyle L_ {i}}$)ve doğru (${ displaystyle R_ {i}}$Giriş sözcüğü, ilk turun sol ve sağ yarısının birleştirilmesidir:

${ displaystyle { rm {input}} = R_ {0} | L_ {0} ,}$.

Her rauntta, sağ yarı, yarıların değiştirildiği round işlevinin çıktısı ile XOR'lanır:

${ displaystyle { begin {array} {rcl} L_ {i} & = & F_ {i} (KL_ {i}, KO_ {i}, KI_ {i}, L_ {i-1}) oplus R_ {i -1} R_ {i} & = & L_ {i-1} end {dizi}}}$

nerede KL_ben, KO_ben, KI_ben yuvarlak anahtarlardır ben^inci yuvarlak.

Çift ve tek raundlar için yuvarlak işlevler biraz farklıdır. Her durumda, yuvarlak işlevi iki işlevin bir bileşimidir FL_ben ve FO_benGarip bir tur için

${ displaystyle F_ {i} (K_ {i}, L_ {i-1}) = FO (KO_ {i}, KI_ {i}, FL (KL_ {i}, L_ {i-1})) , }$

ve eşit bir tur için

${ displaystyle F_ {i} (K_ {i}, L_ {i-1}) = FL (KL_ {i}, FO (KO_ {i}, KI_ {i}, L_ {i-1})) , }$.

Çıktı, son turun çıktılarının birleştirilmesidir.

${ displaystyle { rm {çıktı}} = R_ {8} | L_ {8} ,}$.

Her ikisi de FL ve FO işlevler, 32 bitlik giriş verilerini iki 16 bitlik yarıya böler. FL işlev, geri döndürülemez bir bit işlemidir. FO işlev, geri döndürülemez üç yuvarlak Feistel benzeri bir ağdır.

FL işlevi

32 bitlik giriş x nın-nin ${ displaystyle FL (KL_ {i}, x)}$ 16 bitlik iki yarıya bölünmüştür ${ displaystyle x = l | r}$Girişin ilk sol yarısı ${ displaystyle l}$ yuvarlak anahtar ile bitsel olarak AND'lidir ${ displaystyle KL_ {i, 1}}$ ve bir bit sola döndürüldü. Bunun sonucu, girişin sağ yarısına XOR'lanır ${ displaystyle r}$ çıktının hakkını elde etmek için ${ displaystyle r '}$.

${ displaystyle r '= { rm {ROL}} (l kama KL_ {i, 1}, 1) oplus r}$

Sonra çıktının sağ yarısı ${ displaystyle r '}$ yuvarlak anahtar ile bitler halinde ORed ${ displaystyle KL_ {i, 2}}$ ve bir bit sola döndürüldü. Bunun sonucu, girişin sol yarısına XOR'lanır ${ displaystyle l}$ çıktının ölümcülünü elde etmek için ${ displaystyle l '}$.

${ displaystyle l '= { rm {ROL}} (r' vee KL_ {i, 2}, 1) oplus l}$

Fonksiyonun çıktısı, sol ve sağ yarıların birleştirilmesidir ${ displaystyle x '= l' | r '}$.

FO işlevi

32 bit giriş x nın-nin ${ displaystyle FO (KO_ {i}, KI_ {i}, x)}$ 16 bitlik iki yarıya bölünmüştür ${ displaystyle x = l_ {0} | r_ {0}}$ve bir Feistel ağının üç turundan geçti.

Üç turun her birinde (indekslenen j 1, 2 ve 3 değerlerini alır) yeni sağ yarıyı almak için sol yarı değiştirilir ve bir sonraki turun sol yarısı yapılır.

${ displaystyle { begin {dizi} {lcl} r_ {j} & = & FI (KI_ {i, j}, l_ {j-1} oplus KO_ {i, j}) oplus r_ {j-1} l_ {j} & = & r_ {j-1} end {dizi}}}$

Fonksiyonun çıktısı ${ displaystyle x '= l_ {3} | r_ {3}}$.

İşlev FI

İşlev FI düzensiz Feistel benzeri bir ağdır.

16 bitlik giriş ${ displaystyle x}$ fonksiyonun ${ displaystyle FI (Ki, x)}$ ikiye bölünmüştür ${ displaystyle x = l_ {0} | r_ {0}}$olan ${ displaystyle l_ {0}}$ 9 bit genişliğinde ve ${ displaystyle r_ {0}}$ 7 bit genişliğindedir.

Sol yarıdaki bitler ${ displaystyle l_ {0}}$ önce 9-bit ile karıştırılır ikame kutusu (S-kutusu) S9 ve sonuç sıfır uzatılmış sağ yarı ile XOR'lanır ${ displaystyle r_ {0}}$ yeni 9 bitlik sağ yarıyı elde etmek için ${ displaystyle r_ {1}}$.

${ displaystyle r_ {1} = S9 (l_ {0}) oplus (00 | r_ {0}) ,}$

Sağ yarının bitleri ${ displaystyle r_ {0}}$ 7 bitlik S-box ile karıştırılır S7 ve sonuç, en az önemli yedi bitle (LS7) yeni sağ yarının ${ displaystyle r_ {1}}$ yeni 7 bitlik sol yarıyı almak için ${ displaystyle l_ {1}}$.

${ displaystyle l_ {1} = S7 (r_ {0}) oplus LS7 (r_ {1}) ,}$

Ara kelime ${ displaystyle x_ {1} = l_ {1} | r_ {1}}$ yuvarlak anahtar KI ile ÖZELLEŞTİRİLMİŞTİR ${ displaystyle x_ {2} = l_ {2} | r_ {2}}$olan ${ displaystyle l_ {2}}$ 7 bit genişliğinde ve ${ displaystyle r_ {2}}$ 9 bit genişliğindedir.

${ displaystyle x_ {2} = KI oplus x_ {1}}$

Sağ yarıdaki bitler ${ displaystyle r_ {2}}$ daha sonra 9 bitlik S-box ile karıştırılır S9 ve sonuç sıfır uzatılmış sol yarı ile XOR'lanır ${ displaystyle l_ {2}}$ çıktının yeni 9 bitlik sağ yarısını almak için ${ displaystyle r_ {3}}$.

${ displaystyle r_ {3} = S9 (r_ {2}) oplus (00 | l_ {2}) ,}$

Sonunda sol yarının parçaları ${ displaystyle l_ {2}}$ 7 bitlik S-box ile karıştırılır S7 ve sonuç, en az önemli yedi bitle (LS7) çıktının sağ yarısının ${ displaystyle r_ {3}}$ 7-bitlik öldürücü almak için ${ displaystyle l_ {3}}$ çıktının.

${ displaystyle l_ {3} = S7 (l_ {2}) oplus LS7 (r_ {3}) ,}$

Çıktı, son sol ve sağ yarıların birleştirilmesidir ${ displaystyle x '= l_ {3} | r_ {3}}$.

İkame kutuları

ikame kutuları (S kutuları) S7 ve S9, spesifikasyondaki hem bit bazlı AND-XOR ifadeleri hem de arama tabloları ile tanımlanır. Bit bazlı ifadeler donanım uygulaması için tasarlanmıştır, ancak günümüzde arama tablolarını kullanmak gelenekseldir. HW tasarımında.

S7 aşağıdaki diziyle tanımlanır:

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 aşağıdaki diziyle tanımlanır:

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};

Kriptanaliz

2001 yılında imkansız diferansiyel saldırı KASUMI'nin altı raundunda Kühn (2001) tarafından sunuldu.^[7]

2003 yılında Elad Barkan, Eli Biham ve Nathan Keller gösterdi ortadaki adam saldırıları karşı GSM A5 / 3 şifresini önleyen ve böylece protokolü bozan protokol. Ancak bu yaklaşım A5 / 3 şifresine saldırmaz.^[8] Makalelerinin tam versiyonu daha sonra 2006'da yayınlandı.^[9]

2005 yılında İsrailli araştırmacılar Eli Biham, Orr Dunkelman ve Nathan Keller bir ilişkili anahtar dikdörtgen (bumerang) saldırısı 8 raundun tamamını kapsamlı aramadan daha hızlı kırabilen KASUMI'de.^[10]Saldırı 2 gerektirir^54.6 her biri birbiriyle ilişkili dört anahtardan biri altında şifrelenmiş ve 2'ye eşdeğer bir zaman karmaşıklığına sahip olan seçilmiş düz metinler^76.1 KASUMI şifrelemeleri. Açıkça bu pratik bir saldırı olmasa da, KASUMI'nin varsayılan gücüne dayanan 3GPP protokollerinin güvenliği hakkında bazı kanıtları geçersiz kılar.

2010'da Dunkelman, Keller ve Shamir, bir rakibin tam bir A5 / 3 anahtarını kurtarmasına izin veren yeni bir saldırı yayınladı. ilgili anahtar saldırısı.^[5] Saldırının zaman ve mekan karmaşıklığı, yazarların saldırıyı iki saat içinde tek seferde gerçekleştirmesine yetecek kadar düşüktür. Intel Core 2 Duo hatta optimize edilmemiş referans KASUMI uygulamasını kullanan masaüstü bilgisayar. Yazarlar, bu saldırının A5 / 3'ün 3G sistemlerinde kullanıldığı şekilde uygulanamayabileceğini belirtmektedir; ana amaçları, 3GPP'nin MISTY'deki değişikliklerinin algoritmanın güvenliğini önemli ölçüde etkilemeyeceğine dair güvencelerini gözden düşürmekti.

Ayrıca bakınız

• A5 / 1 ve A5 / 2
• MISTY1
• KAR

Referanslar

Dış bağlantılar

• Nathan Keller'in ana sayfası