Comp128

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.

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)

Scenariusz uwierzytelniania

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

Problemy z zapewnieniem bezpieczeństwa sesji uwierzytelniania

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” i zamieścili w internecie.

Wersje algorytmu

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ą.