RC4 шифрі және оның қауіпсіздігі мәселелері

Кіріспе

Ағымдық шифр

криптографияда RC4 (Rivest Cipher 4, сондай-ақ ARC4 немесе ARCFOUR деп те аталады, яғни күмәнді RC4, төменде қараңыз) – ағымдық шифр. Ол бағдарламалық қамтамасыздағы қарапайымдылығымен және жылдамдығымен ерекшеленеді, бірақ RC4-те бірнеше осалдықтар табылды, осылайша ол қауіпсіз емес. Ол шығыс кілттер ағынының басы жойылмағанда немесе кездейсоқ емес немесе байланысты кілттер қолданылғанда әсіресе осал. RC4-тің ерекше проблемалық қолданылуы WEP сияқты өте қауіпсіз емес протоколдарға әкелді. 2015 жылдан бері, кейбір мемлекеттік криптологиялық агенттіктер TLS протоколында қолданылған кезде RC4-ті бұзуға қабілетті болуы мүмкін деген пікірлер бар. RC4-ті күшейту үшін бірнеше әрекеттер жасалды, атап айтқанда Spritz, RC4A, VMPC және RC4+.

Тарих

RC4 1987 жылы RSA Security компаниясының Рон Ривест жобалаған. Ол ресми түрде "Rivest Cipher 4" деп аталса да, RC аббревиатурасы "Ron's Code" дегенді білдіреді (сонымен қатар RC2, RC5 және RC6 қараңыз). RC4 бастапқыда коммерциялық құпия болған, бірақ 1994 жылдың қыркүйегінде оның сипаттамасы Cypherpunks пошта тізіміне анонимді түрде жарияланды. Көп ұзамай ол sci.crypt жаңалықтар тобында жарияланды, онда Боб Дженкинс оны бірнеше күн ішінде бұзды. Содан кейін ол Интернеттегі көптеген сайттарға тарады. Бұрынғы кодтың түпнұсқа екені расталды, өйткені оның нәтижесі лицензиялық RC4 бағдарламалық жасақтамасын пайдаланатын коммерциялық бағдарламалық жасақтамамен сәйкес келді. Алгоритм белгілі болғандықтан, ол енді коммерциялық құпия емес. RC4 атауы сауда белгісі болып табылады, сондықтан сауда белгісіне қатысты мәселелерді болдырмау үшін RC4 көбінесе ARCFOUR немесе ARC4 (демек, күмәнді RC4) деп аталады. RSA Security алгоритмді ресми түрде жарияламады; алайда, Ривест 2008 жылы өзінің курстық материалдарында RC4 туралы ағылшын тіліндегі Wikipedia мақаласына сілтеме жасады және 2014 жылғы мақаласында RC4 тарихын және оның кодын растады. 2014 жылдың мамырында шыққан OpenBSD 5.5 ChaCha20 пайдалану үшін өзгертілді. FreeBSD және NetBSD-дегі arc4random іске асырылымы да ChaCha20-ді қолданады. Linux әдетте glibc-ті пайдаланады, ол 2022 жылға дейін arc4random ұсынбады. Оның орнына, жеке кітапхана libbsd функцияны ұсынады; ол 2016 жылы ChaCha20 қолдану үшін жаңартылды. 2022 жылы glibc ChaCha20 негізіндегі arc4random-ның өзінің нұсқасын қосты. Операциялық жүйемен бірге келген нұсқаулықтарға сәйкес, 2017 жылғы macOS және iOS операциялық жүйелерінің нұсқасында Apple RC4-ті arc4random іске асыруда AES-пен алмастырды. Жаңа кездейсоқ сандар генераторлары көбінесе RC4 кездейсоқ сандар генераторымен салыстырылады. RC4-ке жасалған бірнеше шабуылдар оның нәтижесін кездейсоқ тізбектен ажырата алады. RC4 ағын шифры болғандықтан, ол әдеттегі блок шифрларынан гөрі икемдірек. Егер күшті хабарламаның аутентификациялық кодымен (MAC) бірге қолданылмаса, шифрлау биттерді өзгерту шабуылына ұшырайды. Шифрлау дұрыс іске асырылмаса, ағын шифрына жасалған шабуылдарға да ұшырауы мүмкін. Алайда, RC4 ағын шифры болғандықтан, ол бір кезде TLS 1.0-ға жасалған 2011 жылғы BEAST шабуылына қарсы тұрақты болған жалғыз кең таралған шифр болды. Шабуыл TLS 1.0 қолдайтын барлық басқа шифрлармен бірге қолданылатын шифр блоктарының тізбектеу режимінің белгілі бір әлсіздігін пайдаланады, олардың барлығы блок шифрлары. 2013 жылдың наурызында Изобе, Охигаши, Ватанабе және Мори, сондай-ақ Альфардан, Бернштейн, Патерсон, Поттеринг және Шулдт жаңа шабуыл сценарийлерін ұсынды. Олар RC4 кілт кестесіндегі жаңа статистикалық бұрмалауларды пайдаланып, көптеген TLS шифрлауларында жай мәтінді қалпына келтіруге болады. 2015 жылдың ақпанында жарияланған RFC 7465 RC4-ті TLS-те пайдалануға тыйым салады.

RC4 was designed by Ron Rivest of RSA Security in 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also RC2, RC5 and RC6). RC4 was initially a trade secret, but in September 1994, a description of it was anonymously posted to the Cypherpunks mailing list. It was soon posted on the sci. crypt newsgroup, where it was broken within days by Bob Jenkins. From there, it spread to many sites on the Internet. The leaked code was confirmed to be genuine, as its output was found to match that of proprietary software using licensed RC4. Because the algorithm is known, it is no longer a trade secret. The name RC4 is trademarked, so RC4 is often referred to as ARCFOUR or ARC4 (meaning alleged RC4) to avoid trademark problems. RSA Security has never officially released the algorithm; Rivest has, however, linked to the English Wikipedia article on RC4 in his own course notes in 2008 and confirmed the history of RC4 and its code in a 2014 paper by him. In OpenBSD 5.5, released in May 2014, was modified to use ChaCha20. The implementations of arc4random in FreeBSD, NetBSD also use ChaCha20. Linux typically uses glibc, which did not offer arc4random until 2022. Instead, a separate library, libbsd, offers the function; it was updated to use ChaCha20 in 2016. In 2022, glibc added its own version of arc4random, also based on ChaCha20. According to manual pages shipped with the operating system, in the 2017 release of macOS and iOS operating systems, Apple replaced RC4 with AES in its implementation of arc4random. Proposed new random number generators are often compared to the RC4 random number generator. Several attacks on RC4 are able to distinguish its output from a random sequence. Because RC4 is a stream cipher, it is more malleable than common block ciphers. If not used together with a strong message authentication code (MAC), then encryption is vulnerable to a bit flipping attack. The cipher is also vulnerable to a stream cipher attack if not implemented correctly. It is noteworthy, however, that RC4, being a stream cipher, was for a period of time the only common cipher that was immune to the 2011 BEAST attack on TLS 1.0. The attack exploits a known weakness in the way cipher block chaining mode is used with all of the other ciphers supported by TLS 1.0, which are all block ciphers. In March 2013, there were new attack scenarios proposed by Isobe, Ohigashi, Watanabe and Morii, as well as AlFardan, Bernstein, Paterson, Poettering and Schuldt that use new statistical biases in RC4 key table to recover plaintext with large number of TLS encryptions. The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015.

Роустың бейастар және пермутациядан кілтті қайта құру

1995 жылы Эндрю Рус эксперименттік түрде кілт ағынының бірінші байты кілттің алғашқы үш байтымен байланысты екенін, ал KSA-дан кейінгі пермутацияның алғашқы бірнеше байты кілт байттарының сызықтық комбинациясымен байланысты екенін анықтады. Бұл қиылыстар 2007 жылға дейін түсіндірілмеген күйде қалды, онда Гоутам Пол, Сиддхешвар Рати және Субхамой Майтра кілт ағыны мен кілт арасындағы байланысты дәлелдеді, ал басқа бір жұмыста Гоутам Пол және Субхамой Майтра пермутация мен кілт арасындағы байланысты дәлелдеді. Соңғы жұмыста пермутация-кілт байланыстарын KSA-дан кейінгі соңғы пермутациядан кілтті толыққанды қайта құруға арналған алғашқы алгоритмді жасау үшін де пайдаланылды, кілт немесе бастамалау векторы туралы ешқандай шарт қойылмады. Бұл алгоритмнің табысқа жету ықтималдығы белгілі бір уақыт ішінде тұрақты, ол толық кілтті іздеудің күрделілігінің квадрат түбіріне тең. Содан кейін RC4-тің ішкі күйлерінен кілтті қайта құру бойынша көптеген зерттеулер жүргізілді. Субхамой Майтра мен Гоутам Пол Roos-тың ұқсас қиылыстары ұялы пермутация индекстерін қарастырғанда да сақталады екенін көрсетті, мысалы, немесе. Мұндай қиылыстар кейінірек кілтті қайта құру әдістерінде табыс ықтималдығын арттыру үшін қолданылады.

RC4 ауытқулары

RC4 құрайтын кілттер ағыны белгілі бір тізбектерге қарай әртүрлі дәрежеде бұрмаланған, оны ажырату шабуылдарына осал етеді. Осындай шабуылдың ең тиімдісі Ицик Мантин мен Ади Шамирге тиесілі, олар шифрдың екінші шығыс байты 1/128 (1/256 емес) ықтималдығымен нөлге қарай бұрмаланғанын көрсетті. Бұл себебі, егер бастапқы күйдегі үшінші байт нөлге тең болса және екінші байт 2-ге тең болмаса, екінші шығыс байты әрқашан нөл болады. Мұндай бұрмалануды тек 256 байтты қарап анықтауға болады. COSIC-тің Сурадюти Пол мен Барт Пренел RC4-тің бірінші және екінші байттары да бұрмаланғанын көрсетті. Бұл бұрмалануды анықтау үшін қажетті үлгілер саны 225 байтты құрайды. Скотт Флюрер мен Дэвид МакГрю RC4 кілттер ағынын, бір гигабайттық шығыс дерегі болғанда, кездейсоқ ағыннан ажырататын шабуылдарды көрсетті. RC4 PRGA-ның бір қадамын толық сипаттауды Риддхипратим Басу, Ширшенду Гангули, Субхамой Майтра және Гоутам Пол жасады. Барлық мүмкіндіктерді ескере отырып, олар i және j берілгенде шығыстың таралуы біркелкі емес екенін дәлелдеді, соның салдарынан j туралы ақпарат әрқашан шығысқа таралады.

Флюрер, Мантин және Шамирдің шабуылы

2001 жылы Флюрер, Мантин және Шамир жаңа және күтпеген жаңалық жасады: барлық мүмкін RC4 кілттері бойынша, шығыс кілт ағынының алғашқы бірнеше байтының статистикасы күрт түрде кездейсоқ емес, кілт туралы ақпаратты ашады. Егер nonce және ұзақ мерзімді кілт RC4 кілтін жасау үшін жай ғана біріктірілсе, онда осы кілтпен шифрланған көптеген хабарламаларды талдау арқылы осы ұзақ мерзімді кілтті анықтауға болады. Осы және осымен байланысты әсерлер 802.11 сымсыз желілерінде қолданылатын WEP ("сымдық эквивалентті құпиялылық") шифрлауын бұзу үшін пайдаланылды. Бұл 802.11 нарығында WEP-ті стандартқа негізделген алмастыруға күрес тудырды және IEEE 802.11i және WPA жұмысына әкелді. Протоколдар кілт ағынының бастапқы бөлігін жою арқылы осы шабуылдан қорғануға болады. Мұндай өзгертілген алгоритм дәстүрлі түрде "RC4 drop[n]" деп аталады, мұнда n – бастапқы кілт ағыны байттарының саны. SCAN бойынша әдепкі мән n = 768 байт, бірақ консервативті мән n = 3072 байт болар еді. Флюрер, Мантин және Шамир шабуылы RC4 негізіндегі SSL-ге қатысты емес, себебі SSL RC4 үшін қолданатын шифрлау кілттерін хэш арқылы жасайды, яғни әртүрлі SSL сессияларының кілттері бір-бірімен байланысты емес.

Клейннің шабуылы

2005 жылы Андреас Клейн RC4 ағынды шифрын талдауды ұсынды, RC4 кілт ағыны мен кілт арасындағы байланыстарды көрсетті. Эрик Тьюс, Ральф Филипп Вайнман және Андрей Пичкин бұл талдауды пайдаланып, aircrack ptw құралын жасады, ол 128 битті WEP-де қолданылатын 104 биттік RC4-ті бір минуттан кем уақытта бұза алады. Флюрер, Мантин және Шамир шабуылына шамамен 10 миллион хабарлама қажет болса, aircrack ptw 50% ықтималдықпен 40 000 кадрда немесе 95% ықтималдықпен 85 000 кадрда 104 биттік кілттерді бұза алады.

Комбинаторлық мәселе

RC4 шифрының кіріс және шығыс санымен байланысты комбинаторлық мәселені алғаш рет 2001 жылы Ицик Мантин мен Ади Шамир қойды. Олардың пікірінше, RC4-тің әдеттегі күйіндегі 256 элементтің ішінде тек x элемент (x ≤ 256) ғана белгілі болса (қалған элементтер бос деп есептелінеді), келесі 256 раундта детерминистік түрде алуға болатын элементтердің максималды саны да x-ке тең болады. Бұл болжам 2004 жылы Сурадюти Пол мен Барт Пренелдің берген ресми дәлелімен жоққа шығарылды.

Роял Холлоуэйге шабуыл

2013 жылы Лондон университетінің Роял Холлоуэйдегі Ақпараттық қауіпсіздік тобының қауіпсіздік зерттеушілері шифрланған 234 хабарламаны ғана пайдаланып жүзеге асырыла алатын шабуыл туралы хабарлады. Көптеген жағдайларда бұл әлі практикалық шабуыл болмаса да, нәтиже осыған жеткілікті жақын болғандықтан, кейбір мемлекеттік криптологиялық агенттіктер RC4-ті қауіпсіз ететін жақсырақ шабуылдарға ие болуы мүмкін деген пікір пайда болды. Осыны ескере отырып, TLS трафигінің көп бөлігі шифрлау блоктарын тізбектейтін блок шифрларына жасалатын шабуылдардан сақтану үшін RC4 қолданылады. Егер осындай гипотетикалық жақсы шабуылдар бар болса, онда RC4 комбинациясымен TLS көптеген нақты сценарийлерде осындай шабуылшыларға қарсы қауіпсіз болмайды.

Бар-мицва шабуыл

Black Hat Asia 2015 конференциясында Ицик Мантин RC4 шифрі қолданып, SSL-ге қарсы тағы бір шабуыл жасады.

NOMORE шабуыл

2015 жылы KU Leuven қауіпсіздік зерттеушілері TLS және WPA TKIP протоколдарында RC4-ке қарсы жаңа шабуылдарды ұсынды. Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE) деп аталған бұл шабуыл, тәжірибеде көрсетілген алғашқы шабуыл болып табылады. Олардың TLS-ке қарсы шабуылы 75 сағат ішінде қорғалған HTTP cookie-дің мазмұнын ашуға мүмкіндік береді. WPA TKIP-ке қарсы шабуыл бір сағаттың ішінде аяқталуы мүмкін және шабуылшыға кез келген пакеттерді шифрлап оқуға және өзгертіп жіберуге мүмкіндік береді.

RC4 нұсқалары

Жоғарыда айтылғандай, RC4-тің ең маңызды әлсіздігі жеткіліксіз кілт кестесінен туындайды; шығарылған алғашқы байттар кілт туралы ақпаратты ашады. Бұл мәселені шығыс ағынының бастапқы бөлігін жою арқылы шешуге болады. Бұл RC4 dropN деп аталады, мұнда N әдетте 256-ға еселенген сан, мысалы 768 немесе 1024. RC4-ті күшейту үшін бірнеше әрекеттер жасалды, олардың ішінде Spritz, RC4A, VMPC және RC4+ ерекше аталады.

Шприц

2014 жылы Рональд Ривест Spritz деп аталатын жаңартылған нұсқаулық туралы лекция оқыды және бірлесіп мақала жазды. Spritz-дің аппараттық үдеткіші Secrypt 2016 жылы жарияланды және нәтижелік байттарды жасау үшін қажетті көп деңгейлі шақыруларға байланысты Spritz SHA-3 және RC4-тің ең жақсы белгілі аппараттық іске асырылуымен салыстырғанда өте баяу жұмыс істейтінін көрсетті. Басқа шүмек функциялары сияқты, Spritz криптографиялық хэш-функцияны, детерминистік кездейсоқ бит генераторын (DRBG), қоса берілген деректермен аутентификацияланған шифрлауды қолдайтын шифрлау алгоритмін (AEAD) және т.б. құру үшін қолданылуы мүмкін. 2017 жылы Баник, Изобе және Мории бағдарламалық қамтамасыз етудің өнімділігін едәуір төмендетпей, алғашқы екі кілт ағыны байтындағы айырмашылықты жоятын, тек бір қосымша жадқа қолжеткізуді қажет ететін қарапайым түзету ұсынды.