KASUMI - KASUMI

KASUMI , UMTS , GSM ve GPRS mobil iletişim sistemlerinde kullanılan bir blok şifredir . UMTS'de KASUMI, sırasıyla UEA1 ve UIA1 adlarıyla gizlilik ( f8 ) ve bütünlük algoritmalarında ( f9 ) kullanılır. GSM'de KASUMI, A5 / 3 anahtar akış üretecinde ve GPRS'de GEA3 anahtar akış üretecinde kullanılır.

KASUMI, Avrupa standartlar kuruluşu ETSI'nin bir parçası olan Security Algorithms Group of Experts (SAGE) tarafından 3GPP'nin UMTS güvenlik sisteminde kullanılması için tasarlanmıştır . 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ı. Mitsubishi Electric Corporation tarafından geliştirilen ve patenti alınan MISTY1 şifreleme algoritmasını seçtiler . 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, adını orijinal algoritma olan MISTY1'den alır - 霞 み (hiragana か す み , romaji kasumi ) Japonca "sis" anlamına gelen kelimedir.

Ocak 2010'da Orr Dunkelman , Nathan Keller ve Adi Shamir , Kasumi'yi ilgili anahtar saldırısı ve çok mütevazı hesaplama kaynakları ile kırabileceklerini gösteren bir makale yayınladı ; bu saldırı MISTY1'e karşı etkisizdir .

Açıklama

KASUMI algoritması bir 3GPP teknik şartnamesinde belirtilmiştir. KASUMI, 128-bit anahtar ve 64-bit giriş ve çıkışa sahip bir blok şifreleyicidir. KASUMI'nin çekirdeği sekiz aşamalı bir Feistel ağıdır . 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 bitlik anahtardan türetilen sekiz 16 bitlik alt anahtardan oluşan yuvarlak bir anahtar kullanır.

Anahtar program

128 bitlik anahtar K , sekiz adet 16 bitlik alt anahtar K _i'ye bölünmüştür :

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

Ayrıca modifiye edilmiş bir anahtar K 'benzer şekilde 16-bit alt anahtarları bölünmüştür K' _i kullanılır. Değiştirilen anahtar, 0x123456789ABCDEFFEDCBA9876543210 ile XORing ile orijinal anahtardan türetilmiştir ( " kolumda hiçbir şey yok" numarası olarak seçilir ).

Yuvarlak anahtarlar 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ükse, gerçek alt anahtar dizinini elde etmek için sonuçtan 8 çıkarılması gerekir.

Algoritma

KASUMI algoritması 64-bit kelimeyi iki 32-bit yarıya, left ( ) ve right ( ) olarak işler . Giriş kelimesi, ilk turun sol ve sağ yarısının birleştirilmesidir: ${\ displaystyle L_ {i}}$${\ displaystyle R_ {i}}$

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

Her rauntta, sağ yarı, round işlevinin çıktısı ile XOR'lanır ve ardından yarılar değiştirilir:

${\ 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}}}$

burada KL _i , KO _i , KI _i i ^inci tur için yuvarlak anahtarlardır .

Çift ve tek raundlar için yuvarlak işlevler biraz farklıdır. Her durumda, yuvarlak fonksiyon FL _i ve FO _{i olmak} üzere iki fonksiyondan oluşan bir bileşimdir . Garip 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} \,}$ .

Hem FL hem de FO işlevleri, 32 bitlik giriş verilerini iki 16 bitlik yarıya böler. FL ise fonksiyon geri dönüşü olmayan bir bit manipülasyon FO fonksiyonu geri dönüşü olmayan bir üç yuvarlak Feistel benzeri ağdır.

FL işlevi

32 bitlik giriş x / iki 16 bitlik yarıya bölünmüştür . Önce girdinin sol yarısı yuvarlak anahtarla bitsel olarak ANDlanır ve bir bit sola döndürülür. Bunun sonucu girişinin sağ yarısına XOR'ed edilir çıkışının sağ yarısını almak için . ${\ displaystyle FL (KL_ {i}, x)}$${\ displaystyle x = l \ | r}$${\ displaystyle l}$${\ displaystyle KL_ {i, 1}}$${\ displaystyle r}$${\ displaystyle r '}$

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

Daha sonra çıktının sağ yarısı yuvarlak anahtarla bitler halinde ORed ve sola bir bit döndürülür. Bunun sonucu girişinin sol yarısına XOR'ed edilir çıkışının sol yarısını almaya . ${\ displaystyle r '}$${\ displaystyle KL_ {i, 2}}$${\ displaystyle l}$${\ 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-bitlik giriş x arasında iki 16 bitlik parçaya bölünür ve Feistel ağının üç tur geçirilir. ${\ displaystyle FO (KO_ {i}, KI_ {i}, x)}$${\ displaystyle x = l_ {0} \ | r_ {0}}$

Üç turun her birinde ( 1, 2 ve 3 değerlerini alan j ile indekslenmiş ) sol yarı, yeni sağ yarıyı elde etmek için değiştirilir ve sağ yarı, bir sonraki raundun 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}}}$

İşlevin çıktısı . ${\ displaystyle x '= l_ {3} \ | r_ {3}}$

İşlev FI

FI işlevi düzensiz Feistel benzeri bir ağdır.

16-bit girdi fonksiyonu olarak ikiye bölünmüştür olan 9 bit genişliğinde ve 7 bit genişliğinde. ${\ displaystyle x}$${\ displaystyle FI (Ki, x)}$${\ displaystyle x = l_ {0} \ | r_ {0}}$${\ displaystyle l_ {0}}$${\ displaystyle r_ {0}}$

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

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

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

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

Ara kelime almak için yuvarlak anahtar Kİ ile XORed olan 7 bit genişliğinde ve 9 bit genişliğinde. ${\ displaystyle x_ {1} = l_ {1} \ | r_ {1}}$${\ displaystyle x_ {2} = l_ {2} \ | r_ {2}}$${\ displaystyle l_ {2}}$${\ displaystyle r_ {2}}$

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

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

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

Son olarak, sol yarının bitleri 7 bitlik S-kutusu S7 tarafından karıştırılır ve sonuç, çıktının 7 bitlik sol yarısını elde etmek için çıktının sağ yarısının en az önemli yedi biti ( LS7 ) ile XOR'lanır . çıktı. ${\ displaystyle l_ {2}}$${\ displaystyle r_ {3}}$${\ displaystyle l_ {3}}$

${\ 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ı

İkame kutuları (S-kutular) S7 ve S9 bit temelinde ve-XOR ifadeler ve tarifnamede arama tablolarında her ikisi ile tanımlanır. Bit bazlı ifadeler donanım uygulamasına yöneliktir ancak günümüzde HW tasarımında bile arama tablolarının kullanılması gelenekseldir.

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'de Kühn (2001) tarafından altı tur KASUMI'ye imkansız bir diferansiyel saldırı sunuldu.

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

2005 yılında İsrailli araştırmacılar Eli Biham , Orr Dunkelman ve Nathan Keller , 8 turun tamamını kapsamlı aramadan daha hızlı kırabilen ilgili anahtar dikdörtgen (bumerang) saldırısını KASUMI'ye yayınladı . Saldırı , her biri dört ilgili anahtardan biri altında şifrelenmiş ve 2 ^76,1 KASUMI şifrelemesine eşdeğer bir zaman karmaşıklığına sahip 2 ^54,6 seçilmiş düz metin gerektirir . Bu açıkça 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 ilgili anahtar saldırısıyla tam bir A5 / 3 anahtarını kurtarmasına olanak tanıyan yeni bir saldırı yayınladı . Saldırının zaman ve mekan karmaşıklığı, yazarların saldırıyı , optimize edilmemiş referans KASUMI uygulamasını kullanarak bile bir Intel Core 2 Duo masaüstü bilgisayarında iki saat içinde gerçekleştirmesine yetecek kadar düşüktür . 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ı