Cesko.wiki COMP128
Author
Albert FloresCOMP128 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 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
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. +more 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. +more15]) 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>2) vynulování zbylých 10 bitů klíče Kc SIMoutput[4+6]=(x[26+18]19 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. +more 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í.