Кіріспе
Криптоаналитикалық шабуыл түрі
Криптографияда интерполяциялық шабуыл – блок шифрларына қарсы криптоаналитикалық шабуыл түрі. Блок шифрларында дифференциалдық криптоанализ және сызықтық криптоанализ ұсынылғаннан кейін, дифференциалдық және сызықтық шабуылдарға қарсы қауіпсіз екендігі дәлелденген бірнеше жаңа блок шифрлары енгізілді. Олардың ішінде KN шифры және SHARK шифры сияқты қайталама блок шифрлары бар еді. Алайда, Томас Якобсен мен Ларс Кнудсен 1990 жылдардың соңында интерполяциялық шабуыл деп аталатын жаңа шабуылды енгізе отырып, бұл шифрларды бұзу оңай екенін көрсетті. Шабуыл кезінде S-қорапты көрсету үшін алгебралық функция қолданылады. Бұл Галуа өрісіндегі қарапайым квадраттық, полиномиалдық немесе рационалдық функция болуы мүмкін. Оның коэффициенттерін стандартты Лагранж интерполяциясы әдістерімен белгілі жай мәтіндерді деректер нүктелері ретінде пайдаланып анықтауға болады. Сонымен қатар, теңдеулерді жеңілдету және шабуылды оңтайландыру үшін таңдалған жай мәтіндерді қолдануға болады. Ең қарапайым түрінде интерполяциялық шабуыл шифрланған мәтінді жай мәтіннің полином түрінде көрсетеді. Егер полиномда белгісіз коэффициенттердің саны салыстырмалы түрде аз болса, онда жай мәтін/шифрланған мәтін (жай/шифр) жұптарының жиынтығымен полиномды қайта құруға болады. Полином қайта құрылғаннан кейін шабуылшы құпия кілтті нақты білмей, шифрлауды көрсете алады. Интерполяциялық шабуыл құпия кілтті қалпына келтіру үшін де қолданылуы мүмкін. Әдісті мысалмен түсіндіру оңай.
In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers. After the two attacks, differential cryptanalysis and linear cryptanalysis, were presented on block ciphers, some new block ciphers were introduced, which were proven secure against differential and linear attacks. Among these there were some iterated block ciphers such as the KN Cipher and the SHARK cipher. However, Thomas Jakobsen and Lars Knudsen showed in the late 1990s that these ciphers were easy to break by introducing a new attack called the interpolation attack. In the attack, an algebraic function is used to represent an S box. This may be a simple quadratic, or a polynomial or rational function over a Galois field. Its coefficients can be determined by standard Lagrange interpolation techniques, using known plaintexts as data points. Alternatively, chosen plaintexts can be used to simplify the equations and optimize the attack. In its simplest version an interpolation attack expresses the ciphertext as a polynomial of the plaintext. If the polynomial has a relative low number of unknown coefficients, then with a collection of plaintext/ciphertext (p/c) pairs, the polynomial can be reconstructed. With the polynomial reconstructed the attacker then has a representation of the encryption, without exact knowledge of the secret key. The interpolation attack can also be used to recover the secret key. It is easiest to describe the method with an example.
Тіршілік ету
Біттік блок шифрін қарастыра отырып, онда мүмкін жай мәтіндер саны бар, демек, ерекше жұптар бар. Егер полиномда белгісіз коэффициенттер болса, онда бізге полиномдағы белгісіз коэффициенттер санына тең немесе одан көп жұптар қажет. Сондықтан интерполяциялық шабуыл тек қана егер .
Уақыт күрделілігі
Қажетті қарапайым мәтінді шифрлау уақытына қарағанда, жұптарды қолданып полиномды құру уақыты шамалы деп есептейік. Егер белгісіз коэффициенттер болса, онда бұл шабуылдың уақыттық күрделілігі , үшін белгілі әртүрлі жұптар қажет болады.
Уақыт күрделілігі
Егер функцияны коэффициенттер арқылы, ал функцияны коэффициенттер арқылы өрнектеуге болады десек, теңдеуді матрицалық теңдеу түрінде құру үшін белгілі бір ерекше жұптар қажет болады. Дегенмен, бұл матрицалық теңдеу көбейту мен қосуға дейін шешіледі. Сондықтан, бірегей және нөлдік емес шешім алу үшін жоғарғы дәрежеге сәйкес келетін коэффициентті бірге, ал тұрақты мүшені нөлге теңейміз. Осылайша, белгілі бір ерекше жұптар талап етіледі. Осы шабуылдың уақыттық күрделілігі , белгілі бір ерекше жұптарды қажет етеді. "Ортада кездесу" (Meet In The Middle) тәсілімен коэффициенттердің жалпы саны әдетте стандартты тәсілге қарағанда аз болады. Бұл тәсілді тиімдірек етеді, себебі аз жұптар қажет.
Кілтті қалпына келтіру
Сонымен қатар, құпия кілтті қалпына келтіру үшін интерполяциялық шабуылды қолдануға болады. Егер блок ұзындығы бар итерациялық шифрдың соңғы раундысын алып тастасақ, шифрдың нәтижесі болады. Бұл шифрды қысқартылған шифр деп атаймыз. Идеясы – соңғы раунд кілтін болжау, сонда біз бір раундты шифрлап, қысқартылған шифрдың нәтижесін ала аламыз. Содан кейін болжамды тексеру үшін, қысқартылған шифрға интерполяциялық шабуылды қалыпты әдіспен немесе Ортада Кездесу әдісімен қолданамыз. Бұл қалай жасалады. Қалыпты әдіспен қысқартылған шифрдың нәтижесін ашық мәтіннің полиномы ретінде көрсетеміз. Полиномды деп атаймыз. Егер біз оны коэффициенттерімен көрсете алсақ, онда белгілі бір ерекше жұптарды пайдаланып полиномды құрастыра аламыз. Соңғы раунд кілтінің болжамын тексеру үшін, егер осы шарт орындалса, бір қосымша жұппен тексеру қажет:
If we remove the last round of an round iterated cipher with block length , the output of the cipher becomes Call the cipher the reduced cipher. The idea is to make a guess on the last round key , such that we can decrypt one round to obtain the output of the reduced cipher. Then to verify the guess we use the interpolation attack on the reduced cipher either by the normal method or by the Meet In The Middle method. Here is how it is done. By the normal method we express the output of the reduced cipher as a polynomial of the plaintext Call the polynomial Then if we can express with coefficients, then using known distinct pairs, we can construct the polynomial. To verify the guess of the last round key, then check with one extra pair if it holds that
Егер осылай болса, соңғы раунд кілтінің болжамы дұрыс болуының жоғары ықтималдығы бар. Егер жоқ болса, кілтті тағы бір болжаңыз. Ортада Кездесу әдісі бойынша, раундтан шығысты ашық мәтіннің полиномы ретінде және қысқартылған шифрдың нәтижесінің полиномы ретінде көрсетеміз. Полиномдарды және деп атаймыз, ал оларды тиісінше және коэффициенттерімен көрсетейік. Содан кейін белгілі бір ерекше жұптармен коэффициенттерді таба аламыз. Соңғы раунд кілтінің болжамын тексеру үшін, егер осы шарт орындалса, бір қосымша жұппен тексеру қажет:
Егер осылай болса, соңғы раунд кілтінің болжамы дұрыс болуының жоғары ықтималдығы бар. Егер жоқ болса, кілтті тағы бір болжаңыз. Соңғы раунд кілтін тапқаннан кейін, қалған раунд кілттерімен де осылай жалғастыра аласыз.
Уақыт күрделілігі
Ұзындығы бар құпия дөңгелек кілтпен, содан кейін әртүрлі кілт болады. Кездейсоқ таңдалған жағдайда, олардың әрқайсысының дұрыс болу ықтималдығы бар. Сондықтан, дұрыс кілтті табу үшін орташа есеппен жасауға тура келеді. Осылайша, қалыпты әдістің орташа уақыт күрделілігі болады, ол белгілі бір ерекше жұпты қажет етеді, ал Meet In The Middle әдісінің орташа уақыт күрделілігі болады, ол белгілі бір ерекше жұпты қажет етеді.
Нақты әлемдегі қолдану
Meet in the middle шабуылы S қораптарына шабуыл жасау үшін кері функциясын пайдаланатын түрінде қолданылуы мүмкін, себебі биттік S қорабы болғанда, онда SHARK блок шифры SP желісін S қорабымен қолданады. Шифр аз раундтан кейін дифференциалдық және сызықтық криптоанализге төзімді. Дегенмен, 1996 жылы Томас Якобсен мен Ларс Кнудсен оны интерполяциялық шабуыл арқылы бұзды. SHARK арқылы блок өлшемі биттерін, параллель биттік S қораптарын раундтарда пайдалану арқылы SHARK нұсқасын белгілейміз. Якобсен мен Кнудсен SHARK (64 биттік блок шифры) үшін таңдалған жазық мәтіндерді пайдалана отырып интерполяциялық шабуылдың бар екенін, сондай-ақ SHARK (128 биттік блок шифры) үшін таңдалған жазық мәтіндерді пайдалана отырып интерполяциялық шабуылдың бар екенін анықтады. Сондай-ақ Томас Якобсен Рид-Соломон кодтарының жақсартылған кодтамасы үшін Мадху Судан алгоритмін қолдана отырып, интерполяциялық шабуылдың ықтималдық нұсқасын ұсынды. Бұл шабуыл тіпті жазық мәтін мен шифрлы мәтін арасындағы алгебралық байланыс тек мәндердің бір бөлігіне ғана қатысты болғанда да жұмыс істей алады.
The block cipher SHARK uses SP network with S box The cipher is resistant against differential and linear cryptanalysis after
a small number of rounds. However it was broken in 1996 by Thomas Jakobsen and Lars Knudsen, using interpolation attack. Denote by SHARK a version of SHARK with block size bits using parallel bit S boxes in rounds. Jakobsen and Knudsen found that there exist an interpolation attack on SHARK (64 bit block cipher) using about chosen plaintexts, and an interpolation attack on SHARK (128 bit block cipher) using about chosen plaintexts. Also Thomas Jakobsen introduced a probabilistic version of the interpolation attack using Madhu Sudan's algorithm for improved decoding of Reed Solomon codes. This attack can work even when an algebraic relationship between plaintexts and ciphertexts holds for only a fraction of values.