Comp128

COMP128

Rodzaj algorytmu	szyfr symetryczny
Długość klucza	64 bity
Data złamania	kwiecień 1998
Złamany przez	Ian Golberg, David Wagner
Skuteczne ataki	atak partycyjny (maj 2002)

COMP128 – algorytm implementowany w kartach SIM, realizujący w jednym kroku operacje wykonywane przez algorytmy A3 oraz A8. Pierwszy z nich (A3) odpowiedzialny jest za uwierzytelnianie (autoryzację) użytkownika w sieci GSM, drugi (A8) – za wybór klucza sesyjnego Kc pozwalającego szyfrować dane. Ponieważ algorytmy te posiadają te same parametry wejścia, ale dwa różne parametry wyjścia mogły w praktyce zostać zastąpione jednym algorytmem posiadającym dwa wyjścia (SRES, Kc), jakim jest właśnie COMP128.

Poniżej zamieszczony został scenariusz uwierzytelniania wykorzystujący algorytmy A3 i A8 składające się na algorytm COMP128.

              Autoryzacja użytkownika w sieci oraz wyliczanie klucza sesyjnego Kc:
                           UŻYTKOWNIK:                            SIEĆ:
   wysłanie numeru IMSI (International -------128bit IMSI------ → po odebraniu numeru IMSI
           Mobile Subscriber Identity)                            odesłanie do użytkownika
              zapisanego na karcie SIM ← -----128bit RAND-------- losowej liczby RAND
        wyliczenie na podstawie klucza -------32bit SRES ------ → porównanie wyliczonej przez sieć liczby
       długoterminowego Ki oraz liczby                            SRES z liczbą otrzymaną od użytkownika
     RAND (otrzymanej od sieci) liczby ------- 64bit Kc ------- → i odesłanie (w razie zgodności obu liczb)
    SRES (za pomocą algorytmu A3) oraz                            numeru TMSI (z ang. Temporary Mobile
                   klucza sesyjnego Kc                            Subscriber Identity) używanego podczas
              (za pomocą algorytmu A8) ← ------  TMSI   --------- dalszej współpracy z siecią, szyfrowanego
             i przesłanie ich do sieci                            kluczem sesyjnym Kc

W celu zachowania pełnego bezpieczeństwa sieci GSM algorytm COMP128 miał być w 100% tajny. W 1997 roku opublikowano jednak znaleziony tekst „dziurawego” dokumentu zawierającego notatki jednego z inżynierów pracującego nad tym algorytmem. W kwietniu 1998 Ian Golberg i David Wagner z Uniwersytetu Kalifornijskiego w Berkeley odtworzyli kod algorytmu w języku C oraz zrekonstruowali parę zaginionych linii tekstu i przeprowadzili pierwszy udany atak na COMP128.

Pseudo-kod opisujący pracę algorytmu:

VOID A3A8 (wejście RAND[16], Ki[16],
           wyjście SIMoutput[12])-operują na bajtach
{
         x[32]-bufor wewnętrzny-operuje na bajtach, bit[128]-bufor roboczy;
         T[5][]-bloki podstawieniowe zapisane w tablicy (512, 256, 128, 64, 32 bajtów);
         pozostałe zmienne i, j, k, l, m, n, y, z, następny_bit;

         zapisanie RAND na ostatnich 16 bajtach bufora (x[16...31])
         for i=16 to 31{
             x[i]=RAND[i]
         }
         wykonanie pętli 8 razy
         for i=1 to 8{
             zapisanie Ki na pierwszych 16 bajtach bufora (x[0...15])
             for j=0 to 15{
             x[j]=Ki[j]
             }
             kompresja (tzw. kompresja motyla, czyli jedna z głównych słabości algorytmu COMP128)
             for j=0 to 4{
                 for k=0 to (2^j)-1{
                     for l=0 to 2(^4-j)-1{
                         m=1+k2^(5-j)
                         n=m+2^(4-j)
                         y=(x[m]+2x[n])mod 2^(9-j);
                         z=(2x[m]+x[n])mod 2^(9-j);
                         x[m]=T[j][y];
                         x[n]=T[j][z];
                    }
                 }
              }
             "Form bits From bytes" czyli przestawienie bitów w buforze
              for j=0 to 31{
                  for k=0 to 3{
                      bit[4j+k]=(x[j]>>(3-k))&1
                  }
              }
              permutacja z pominięciem ostatniej pętli
              if i<8{
                 for j=0 to 15{
                     for k=0 to 7{
                         następny_bit=17(8j+k)mod 128
                         k-ty bit x[j+16]=bit[następny_bit]
                     }
                  }
               }
            }
            kompresja 16 bajtów wynikowych do 12 bajtów oraz zapisanie
            ich w SIMoutput[] (x[0...3]-SRES; x[4...11]-Kc);
            wyzerowanie ostatnich 10 bitów klucza Kc
            for i=0 to 3
                SIMoutput[i]=(x[2i]<<4)|x[2i+1]
            for i=0 to 5
                SIMoutput[4+i]=(x[2i+18]<<6|(x[2i+18+1]<<2)|(x[2i+18+2]>>2)
            SIMoutput[4+6]=(x[26+18]<<6)|(x[26+18+1]<<2)
            SIMoutput[4+7]=0
         }

Goldberg i Wagner odkryli, że klucz sesyjny Kc, który jest na jednym z wyjść algorytmu COMP128 zawiera jedynie 54 bity użyteczne, a ostatnie 10 bitów jest zawsze zerowanych. Taki sposób szyfrowania danych zmniejsza bezpieczeństwo sieci ponad 1000-krotnie w stosunku do tego, co pozwala uzyskać specyfikacja GSM. Pozwoliło to jednak przeprowadzić Goldbergowi i Wagnerowi atak na COMP128 zawierający 2¹⁹ zapytań do karty SIM i trwający mniej niż 8 godzin. Ich atak i złamanie algorytmu COMP128 pozwoliło na poznanie klucza długoterminowego Ki przechowywanego na karcie SIM, a tym samym na klonowanie kart SIM (choć nadal aby móc korzystać z karty potrzebny jest jej kod PIN).

W maju 2002 roku Josyula R. Rao, Pankaj Rohatgi, Helmut Scherzer (wszyscy z firmy IBM) oraz Stephanie Tinguely (ze Szwajcarskiego Głównego Instytutu Technologii) przeprowadzili tzw. atak partycyjny, czyli atak na SIM bocznymi kanałami, pozwalający złamać algorytm COMP128 w mniej niż minutę. Swoją pracę opisali w artykule pt. „Partitioning Attacks: Or How to Rapidly Clone Some GSM Cards”^[1] i zamieścili w internecie.

Do tej pory udało się złamać jedynie algorytm COMP128-V1, czyli jego pierwszą wersję. Obecnie trwają prace nad udoskonaleniem COMP128, a operatorzy migrują na nowsze wersje tego algorytmu:

• COMP128-V2 – likwiduje jedynie niektóre luki pierwszej wersji algorytmu
• COMP128-V3 – stworzony do generowania 64-bitowego klucza sesyjnego Kc
• COMP128-V4 – bazuje na algorytmie 3GPP, który używa AES; prace nad tą wersją wciąż trwają.