COMP128

COMP128 je algoritmus implementovaný v SIM kartách realizující jedním postupem algoritmy A3 a A8. Algoritmus A3 slouží pro ověření (autentizaci) uživatele v síti GSM, A8 pro výběr relačního klíče Kc umožňujícího šifrovat data. Protože oba algoritmy mají stejné vstupní parametry, bývají nahrazeny algoritmem COMP128 se dvěma výstupy (SRES, Kc).

Scénář autentizace

Scénář autentizace používající algoritmy A3 a A8 je následující:

              autorizace uživatele do sítě a výpočet relačního klíče Kc:
                             UŽIVATEL:                            SÍŤ:
odeslání čísla IMSI (International      -------128bit IMSI------> po přijetí čísla IMSI je
Mobile Subscriber Identity) zapsaného                             uživateli posláno náhodné
v SIM                                   <-----128bit RAND-------- číslo RAND
výpočet SRES algoritmem A3 aplikovaným
na trvalý klíč Ki a RAND                -------32bit SRES ------> porovnání SRES od mobilu a AuC
výpočet Kc algoritmem A8 aplikovaným
na trvalý klíč Ki a RAND                ------- 64bit Kc -------> další komunikace je šifrována pomocí Kc
                                        <------  TMSI   --------- VLR vygeneruje TMSI a pošle je mobilu;
                                                                  dále se místo IMSI používá TMSI

Problémy se zajištěním bezpečnosti relace autentizace

V zájmu zachování plné bezpečnosti sítě GSM byl algoritmus COMP128 utajován. V roce 1997 však byl publikován nalezený text „uniklého“ dokumentu obsahujícího poznámky jednoho z inženýrů, kteří algoritmus vytvářeli. V dubnu 1998 Ian Golberg a David Wagner z Kalifornské univerzity v Berkeley zrekonstruovali několik chybějících řádků kódu, získali kompletní kód algoritmu v jazyku C a provedli první úspěšný útok na COMP128.

Pseudokód popisující práci algoritmu:

VOID A3A8 (vstupy RAND[16], Ki[16],
           výstup SIMoutput[12])
{
         x[32] - interní buffer - pracuje na bytech, bit[128] - pracovní buffer;
         T[5][]- substituční bloky zapsané v tabulce (512, 256, 128, 64, 32 bytů);
         další proměnné a, j, k, l, m, n, y, z, další_bit;

         uložení RAND do druhých 16 bytů bufferu (x[16...31])
         for a=16 to 31 {
             x[a]=RAND[a]
         }
         8 průchodů smyčkou
         for a=1 to 8 { 
             uložení Ki do prvních 16 bytů bufferu (x[0...15])
             for j=0 to 15 { 
                 x[j]=Ki[j]
             }
             tzv. motýlová komprese, je jednou z hlavních slabin algoritmu COMP128
             for j=0 to 4 { 
                 for k=0 to (2^j)-1 { 
                     for l=0 to 2^(4-j)-1 { 
                         m=l+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];
                    }
                 }
              }
              přeorganizování bitů v bufferu
              for j=0 to 31{
                  for k=0 to 3 {
                      bit[4j+k]=(x[j]>>(3-k))&1
                  }
              }
              provedení permutace; kromě posledního průchodu smyčkou
              if a<8{
                 for j=0 to 15{
                     for k=0 to 7{
                         další_bit=17(8j+k) mod 128
                         k-ty bit x[j+16]=bit[další_bit]
                     }
                  }
               }
            }
            komprese 16 bytů do 12 bytů a jejich uložení
            do SIMoutput[] (x[0...3]-SRES; x[4...11]-Kc);
            for a=0 to 3
                SIMoutput[a]=(x[2i]<<4)|x[2i+1]
            for a=0 to 5
                SIMoutput[4+a]=(x[2i+18]<<6|(x[2i+18+1]<<2)|(x[2i+18+2]>>2)
            vynulování zbylých 10 bitů klíče Kc
            SIMoutput[4+6]=(x[26+18]<<6)|(x[26+18+1]<<2)
            SIMoutput[4+7]=0
         }

Goldberg a Wagner zjistili, že ze 64 bitů relačního klíče Kc, který je jedním z výstupů algoritmu COMP128, je poslední 10 bitů nulových, takže klíč má 54 bitů. To představuje více než tisícinásobné oslabení bezpečnosti oproti tomu, co umožňuje specifikace GSM. Tato znalost umožnila Goldbergovi a Wagnerovi provést útok na COMP128 vyžadující 2¹⁹ dotazů na SIM kartu, které lze provést za méně než 8 hodin. Jejich útok a prolomení algoritmu COMP128 umožnily získat hodnotu trvalého klíče Ki uloženého na kartě SIM, což umožňuje klonování SIM karet (pro využití klonované karty je však potřebné získat její PIN kód).

V květnu 2002 roku Josyula R. Rao, Pankaj Rohatgi, Helmut Scherzer (všichni z firmy IBM) a Stephanie Tinguely (ze švýcarského Hlavního Ústavu Technologii) provedli útok na SIM postranními kanály, tzv. partition attack, umožňující prolomit algoritmus COMP128 za méně než minutu. Svoji práci popsali v článku Partitioning Attacks: Or How to Rapidly Clone Some GSM Cards dostupném na internetu.

Verze algoritmu

Dosud podařilo se prolomit pouze algoritmus COMP128-V1, neboli jeho první verzi. V současné době probíhají práce na zdokonalení COMP128, a operátoři migrují na novější verze algoritmu:

• COMP128-V2 – odstraňuje některé chyby v první verzi algoritmu
• COMP128-V3 – vytvořený pro generování 64bitového relačního klíče Kc
• COMP128-V4 – vychází z algoritmu 3GPP, který používá AES; práce na této verzi stále probíhají.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Comp128 na polské Wikipedii.