DES шифрі және оның эволюциясы: қауіпсіздік пен алмасу

Кіріспе

Ертедегі жіктелмеген симметриялық кілттік блок шифрлау жүйесі DES салыстырмалы түрде қысқа 56 биттік кілт өлшеміне байланысты қауіпсіз емес. 1999 жылдың қаңтарында distributed.net және Electronic Frontier Foundation бірлесіп DES кілтін 22 сағат 15 минутта бұзды (қараңыз). Шифрдың теориялық әлсіздіктерін көрсететін талдау нәтижелері де бар, бірақ олар тәжірибеде қолданылмайды. Алгоритм Үш еселенген DES (Triple DES) түрінде іс жүзінде қауіпсіз деп саналады, дегенмен теориялық шабуылдар бар. Бұл шифр Advanced Encryption Standard (AES) стандартымен алмастырылды. DES стандарты Ұлттық Стандарттар және Технология Институты (National Institute of Standards and Technology) тарапынан стандарт ретінде алынып тасталды. Осы уақытта инженер Мохамед Атала 1972 жылы Atalla Corporation құрды және 1973 жылы коммерцияланған "Atalla Box" деп аталатын алғашқы аппараттық қауіпсіздік модулін (HSM) жасады. Ол желіден тыс құрылғыларды құпия PIN-кодты жасайтын кілтпен қорғады және коммерциялық сәттілікке жетті. Банктер мен кредиттік карта компаниялары Атала нарыққа үстемдік етеді деп қорқып, халықаралық шифрлау стандартын әзірлеуге түрткі болды. Атала банктік нарықта IBM-ге ерте бәсекелес болды және DES стандартында жұмыс істеген IBM қызметкерлерінің ықпалы ретінде айтылды. IBM 3624 кейіннен бұрынғы Atalla жүйесіне ұқсас PIN-кодты тексеру жүйесін қабылдады. 1973 жылдың 15 мамырында NSA-мен кеңескеннен кейін NBS қатаң жобалау талаптарына сай келетін шифр үшін ұсыныстар сұрады. Ешбір ұсыныс қанағаттандырмады. 1974 жылдың 27 тамызында екінші сұраныс жіберілді. Бұл жолы IBM 1973-1974 жылдар аралығында дамытылған, Horst Feistel-дің Lucifer шифрына негізделген шифрды ұсынды, ол қабылдауға лайық деп танылды. Шифрды жобалау және талдаумен айналысқан IBM командасына Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith және Bryant Tuckerman кірді.

Стандартты алгоритм

Сын-пикирлерге қарамастан, DES 1976 жылдың қарашасында федералды стандарт ретінде бекітілді және 1977 жылдың 15 қаңтарында FIPS PUB 46 ретінде жарияланды, барлық құпия емес деректерде қолдануға рұқсат етілді. Кейіннен ол 1983, 1988 (FIPS 46 1 ретінде қайта жаңартылды), 1993 (FIPS 46 2), және 1999 (FIPS 46 3) жылдары стандарт ретінде қайта бекітілді, соңғысы "Қос ДЭС" (төменде қараңыз) талаптарын белгіледі. 2002 жылдың 26 мамырында DES ашық бәйгеден кейін Advanced Encryption Standard (AES) стандартымен алмастырылды. 2005 жылдың 19 мамырында FIPS 46 3 ресми түрде алынып тасталды, бірақ NIST 2030 жылға дейін сезімтал үкіметтік ақпарат үшін Үш еселенген DES-ті мақұлдады. Алгоритм сондай-ақ ANSI X3.92 (қазіргі X3 INCITS деп аталады, ал ANSI X3.92 – ANSI INCITS 92) және NIST SP 800 67 (TDEA құрамында) стандарттарында да көрсетілген. 1994 жылы тағы бір теориялық шабуыл – сызықтық криптоанализ жарияланды, бірақ 1998 жылы Electronic Frontier Foundation ұйымының DES крекері DES-ке нақты шабуыл жасауға болатынын көрсетті және жаңа алгоритмді қажет ететінін айқындады. Осы және басқа криптоанализ әдістері осы мақалада егжей-тегжейлі қарастырылады. DES-тің енгізілуі криптографияны, әсіресе блок шифрларын бұзу әдістерін академиялық тұрғыдан зерттеуге ықпал еткен катализатор болды деп есептеледі. DES туралы NIST-тің ретроспективтік сараптамасына сәйкес, DES шифрлау алгоритмдерін әскери емес зерттеу және дамытуды "серпіліс берді" деуге болады. 1970-ші жылдарда әскери немесе барлау ұйымдарында қызмет ететін криптографтардың саны өте аз болды, ал криптографияны академиялық түрде зерттеу де аз болған. Қазір белсенді академиялық криптологтар көп, криптография бойынша күшті бағдарламалары бар математика кафедралары, сондай-ақ коммерциялық ақпараттық қауіпсіздік компаниялары мен кеңесшілер жетерлік. Криптоанализшілердің бір буыны DES алгоритмін талдау (яғни, "жарып тастауға" тырысу) арқылы тәжірибе жинады. Криптограф Брюс Шнайердің сөздерімен айтқанда, "DES криптоанализ саласын ең көп ынталандырды. Енді зерттеуге арналған алгоритм пайда болды". 1970-80 жылдардағы криптографиядағы ашық әдебиеттің үлкен бөлігі DES-ке арналған, ал DES – барлық симметриялық кілт алгоритмдерінің салыстырылатын стандарты болып табылады.

Despite the criticisms, DES was approved as a federal standard in November 1976, and published on 15 January 1977 as FIPS PUB 46, authorized for use on all unclassified data. It was subsequently reaffirmed as the standard in 1983, 1988 (revised as FIPS 46 1), 1993 (FIPS 46 2), and again in 1999 (FIPS 46 3), the latter prescribing "Triple DES" (see below). On 26 May 2002, DES was finally superseded by the Advanced Encryption Standard (AES), following a public competition. On 19 May 2005, FIPS 46 3 was officially withdrawn, but NIST has approved Triple DES through the year 2030 for sensitive government information. The algorithm is also specified in ANSI X3.92 (Today X3 is known as INCITS and ANSI X3.92 as ANSI INCITS 92), NIST SP 800 67 (as a component of TDEA). Another theoretical attack, linear cryptanalysis, was published in 1994, but it was the Electronic Frontier Foundation's DES cracker in 1998 that demonstrated that DES could be attacked very practically, and highlighted the need for a replacement algorithm. These and other methods of cryptanalysis are discussed in more detail later in this article. The introduction of DES is considered to have been a catalyst for the academic study of cryptography, particularly of methods to crack block ciphers. According to a NIST retrospective about DES,
The DES can be said to have "jump started" the nonmilitary study and development of encryption algorithms. In the 1970s there were very few cryptographers, except for those in military or intelligence organizations, and little academic study of cryptography. There are now many active academic cryptologists, mathematics departments with strong programs in cryptography, and commercial information security companies and consultants. A generation of cryptanalysts has cut its teeth analyzing (that is, trying to "crack") the DES algorithm. In the words of cryptographer Bruce Schneier, "DES did more to galvanize the field of cryptanalysis than anything else. Now there was an algorithm to study." An astonishing share of the open literature in cryptography in the 1970s and 1980s dealt with the DES, and the DES is the standard against which every symmetric key algorithm since has been compared.

Хронологиясы

Күн Жыл Іс-шара 15 мамыр 1973 NBS стандартты шифрлау алгоритміне алғашқы сұранысты жариялайды 27 тамыз 1974 NBS стандартты шифрлау алгоритміне екінші сұранысты жариялайды 17 наурыз 1975 DES федералдық тіркелімде пікір алу үшін жарияланады 1976 тамыз DES бойынша алғашқы семинар 1976 қыркүйек DES-тің математикалық негізін талқылайтын екінші семинар 1976 қараша DES стандарт ретінде бекітіледі 15 қаңтар 1977 DES FIPS стандарты ретінде жарияланады FIPS PUB 46 маусым 1977 Диффи мен Хеллман DES шифрын күшпен бұзуға болатынын айтады. 19 мамыр 2005 NIST FIPS 46 3-ті алып тастады (Федералдық тіркелімнің 70 томы, 96 нөмірін қараңыз) 2006 сәуір Бохум және Киль университеттерінің FPGA-ға негізделген параллель машинасы COPACOBANA DES-ті 9 күнде 10 000 долларлық аппараттық шығындармен бұзады. Бір жыл ішінде бағдарламалық қамтамасыз етуді жетілдіру орташа уақытты 6,4 күнге дейін қысқартты. 2008 ж. қараша COPACOBANA-ның ізбасары RIVYERA машинасы орташа уақытты бір күннен де аз уақытқа қысқартты. 2016 жылдың тамызы Ашық кодты құпия сөзді бұзу бағдарламасы hashcat DES-ке жалпы мақсаттағы GPU-да күшпен іздеуді қосты. Тестілеу нәтижесінде Nvidia GeForce GTX 1080 Ti GPU, құны 1000 АҚШ доллары, кілтті орташа есеппен 15 күнде қалпына келтіретіні (толық іздеу 30 күнге созылады) көрсетілді. Сегіз GTX 1080 Ti GPU-мен құрылған жүйелер кілтті орташа есеппен 2 күннің ішінде қалпына келтіре алады. 2017 жылдың шілдесі Таңдалған ашық мәтіндік шабуыл, радуга кестесін пайдаланып, 25 секунд ішінде 1122334455667788 таңдалған ашық мәтіннің DES кілтін қалпына келтіре алады. Әр мәтін үшін жаңа радуга кестесін есептеу қажет. Радуга кестелерінің шектеулі жиынтығы жүктеуге қолжетімді.

Сипаттама

DES – бұл архетиптік блок шифрі – белгілі бір ұзындықтағы ашық мәтін биттерінің тізбегін қабылдап, оны күрделі операциялар сериясы арқылы сол ұзындықтағы шифрланған мәтін биттерінің тізбегіне түрлендіретін алгоритм. DES үшін блок мөлшері 64 бит. DES сондай-ақ трансформацияны бейімдеу үшін кілтті пайдаланады, сондықтан шифрлау үшін қолданылған нақты кілтті білгендер ғана шифрды аша алады. Кілт номиналды түрде 64 биттен тұрады, бірақ алгоритмде олардың тек 56-сы ғана қолданылады. Сегіз бит тек парлықты тексеру үшін пайдаланылады және кейін жойылады. Сондықтан кілттің тиімді ұзындығы 56 бит. Кілт 8 байт түрінде сақталады немесе жіберіледі, олардың әрқайсысы тақ парлықпен. ANSI X3.92 1981 (қазір ANSI INCITS 92–1981 деп белгілі) стандартының 3.5-тармағында былай делінген:

Кілтті жасау, тарату және сақтау кезінде қателерді анықтау үшін кілттің әрбір 8 биттік байтындағы бір бит пайдаланылуы мүмкін. 8, 16, 64 биттер әр байттың тақ парлыққа ие болуын қамтамасыз ету үшін арналған. Басқа блок шифрлары сияқты, DES өзі жеке шифрлаудың қауіпсіз құралы емес, оның орнына жұмыс режимінде қолданылуы керек. FIPS 81 DES-пен пайдалану үшін бірнеше режимдерді анықтайды. DES-ті пайдалану туралы қосымша ақпарат FIPS 74 құжатында келтірілген. Шифрды ашу шифрлаумен бірдей құрылымды пайдаланады, бірақ кілттер кері ретпен қолданылады. (Бұл екі бағытта да бірдей аппараттық немесе бағдарламалық қамтамасыз етуді пайдалану мүмкіндігін береді.)

Жалпы құрылым

Алгоритмнің жалпы құрылымы 1-суретте көрсетілген: өңдеудің 16 бірдей кезеңі бар, олар раундтар деп аталады. Сонымен қатар, бастапқы және соңғы пермутация бар, олар IP және FP деп аталады, олар бір-біріне кері (IP FP әрекетін "кері қайтарады" және керісінше). IP және FP криптографиялық маңызы жоқ, бірақ 1970-ші жылдардың ортасындағы 8-биттік аппараттық базаға блоктарды жүктеуді жеңілдету үшін қосылған. Негізгі раундтар алдында блок екі 32 биттік жартыға бөлінеді және кезекпен өңделеді; бұл өзара алмасу Феистель схемасы деп аталады. Феистель құрылымы шифрлау мен дешифрлеудің өте ұқсас процестер екенін қамтамасыз етеді – жалғыз айырмашылық дешифрлеу кезінде кіші кілттер кері ретпен қолданылады. Алгоритмнің қалған бөлігі толықтай бірдей. Бұл, әсіресе аппараттық құралдарда жүзеге асыруды жеңілдетеді, өйткені жеке шифрлау және дешифрлеу алгоритмдері қажет емес. ⊕ символы эксклюзивті НИМ (XOR) операциясын білдіреді. F функциясы жарты блокты кілттің бір бөлігімен араластырады. F функциясының нәтижесі блоктың екінші жартысымен біріктіріледі, ал жартылары келесі раундқа дейін ауыстырылады. Соңғы раундтан кейін жартылары ауыстырылады; бұл Феистель құрылымының ерекшелігі, ол шифрлау мен дешифрлеуді ұқсас процестерге айналдырады.

Негізгі кесте

3-сурет шифрлау кілт кестесін көрсетеді – кіші кілттерді жасайтын алгоритм. Алдымен, бастапқы 64 биттен 56 биті Пермутацияланған таңдау 1 (PC 1) арқылы таңдалып алынады, ал қалған сегіз биті жойылады немесе паритет тексеру біттері ретінде қолданылады. Содан кейін 56 бит екі 28 биттік бөлікке бөлінеді; әр бөлік одан әрі жеке қарастырылады. Кезекті турларда екі бөлік те бір немесе екі битқа солға қарай жылдырылады (әр тур үшін көрсетіледі), содан кейін 48 кіші кілт биті Пермутацияланған таңдау 2 (PC 2) арқылы таңдалады – сол бөліктен 24 бит және оң бөліктен 24 бит. Айналымдар (суретте «<<<» символымен белгіленген) әр кіші кілтте әртүрлі биттер жиынтығы қолданылатынын білдіреді; әр бит 16 кіші кілттің шамамен 14-інде қолданылады. Дешифрлеу кілт кестесі ұқсас – кіші кілттер шифрлеуге қарағанда кері ретпен орналасқан. Бұл өзгерістен басқа, процесс шифрлеумен бірдей. Барлық айналымдық блоктарға бірдей 28 бит жіберіледі.

Псевкод

DES алгоритмінің псевдокоды төменде келтірілген.

Қауіпсіздік және криптоанализ

DES криптоанализі туралы басқа блок-шифрларға қарағанда көбірек ақпарат жарияланғанмен, қазіргі күнге дейін ең тиімді шабуыл – күш қолдану әдісі болып табылады. Әртүрлі шағын криптоаналитикалық қасиеттер белгілі, сондай-ақ үш теориялық шабуыл мүмкін. Олардың теориялық қиындығы күш қолдану шабуылынан кем болғанымен, оларды жүзеге асыру үшін өте көп мөлшерде белгілі немесе таңдалған қара мәтін қажет, сондықтан олар іс жүзінде маңызды емес.

Қатаң шабуыл

Кез келген шифр үшін шабуылдың ең негізгі әдісі – барлық мүмкін кілттерді кезекпен сынап көру. Кілттің ұзындығы мүмкін кілттердің санын, демек, осы тәсілдің мүмкіндігін анықтайды. DES үшін кілт өлшемі стандарт ретінде қабылданғанға дейін оның жеткіліктілігі туралы сұрақтар туындады, және теориялық криптоанализ емес, кішкентай кілт өлшемі алмастыру алгоритміне қажеттілікті талап етті. Сыртқы консультанттармен, соның ішінде ҰҚК-мен жүргізілген талқылау нәтижесінде кілт мөлшері 256 биттен 56 битке дейін қысқартылды. Академияда DES-ті бұзу машинасына қатысты түрлі ұсыныстар жасалды. 1977 жылы Диффи мен Хеллман бір күнде DES кілтін табуға болатын, шамамен 20 миллион АҚШ долларына тұратын машина ұсынды. 1993 жылы Винер 7 сағат ішінде кілтті табуға болатын 1 миллион АҚШ долларына тұратын кілт іздеу машинасы ұсынды. Алайда, бұл алғашқы ұсыныстардың ешқайсысы жүзеге асырылмады, немесе кем дегенде, жүзеге асырылғаны туралы жария түрде хабарланбады. DES-тің осалдығы 1990 жылдардың соңында тәжірибеде дәлелденді. 1997 жылы RSA Security бірнеше бәйге ұйымдастырып, DES-пен шифрланған хабарды бұзған алғашқы командаға 10 000 АҚШ доллары сыйлық ұсынды. Бұл бәйгеде Рок Версер, Мэтт Кертин және Джастин Долске басшылық еткен DESCHALL жобасы жеңіске жетті, олар Интернеттегі мыңдаған компьютерлердің бос уақытын пайдаланды. DES-ті жылдам бұзудың мүмкіндігі 1998 жылы электрондық шекаралар қоры (EFF), киберкеңістіктегі азаматтық құқықтарды қорғау тобы, шамамен 250 000 АҚШ долларына арнайы DES бұзушысын құрған кезде көрсетілді (EFF DES бұзушысын қараңыз). Олардың мақсаты DES-ті теорияда да, тәжірибеде де бұзуға болатынын көрсету болды: «Өз көзімен көрмейінше, шындыққа сенбейтін адамдар көп. Оларға DES-ті бірнеше күнде бұза алатын физикалық машинаны көрсету – кейбір адамдарды DES-ке өздерінің қауіпсіздігін сендірудің жалғыз жолы». Машина кілтті екі күннен астам іздеу барысында бұзып алды. Келесі расталған DES бұзушысы 2006 жылы Германиядағы Бохум және Киль университеттерінің командалары жасаған COPACOBANA машинасы болды. EFF машинасынан айырмашылығы, COPACOBANA коммерциялық түрде қол жетімді, қайта конфигурацияланатын интегралдық схемалардан тұрады. XILINX Spartan 3 1000 типіндегі 120 өрістегі бағдарламаланатын қақпалар массиві (FPGA) қатар жұмыс істейді. Олар әрқайсысы 6 FPGA құрайтын 20 DIMM модуліне топтастырылған. Қайта конфигурацияланатын аппаратты пайдалану машинаны басқа кодты бұзу тапсырмаларына да қолдануға мүмкіндік береді. COPACOBANA-ның ең қызықты жақтарының бірі – оның құны. Бір машинаны шамамен 10 000 долларға құрастыруға болады. EFF машинасына қарағанда құнның шамамен 25 есеге төмендеуі – цифрлық аппаратты үздіксіз жетілдірудің мысалы. Инфляцияны ескергенде, 8 жыл ішінде жақсарту шамамен 30 есеге жетеді. 2007 жылдан бастап SciEngines GmbH, COPACOBANA-ның екі жобалық серіктесінің еншілес компаниясы, COPACOBANA-ның ұрпақтарын жетілдіріп, дамытты. 2008 жылы COPACOBANA RIVYERA 128 Spartan 3 5000-ды пайдалану арқылы DES-ті бұзу уақытын бір күннен аз уақытқа қысқартты. SciEngines RIVYERA 128 Spartan 3 5000 FPGA-ны пайдаланып, DES-ті бұзған кездегі рекордты ұстады. Олардың 256 Spartan 6 LX150 моделі бұл көрсеткішті одан да төмендетті. 2012 жылы Дэвид Хултон мен Мокси Марлинспайк 48 Xilinx Virtex 6 LX240T FPGA-дан тұратын жүйе туралы хабарлады, әр FPGA-да 400 МГц жылдамдықпен жұмыс істейтін 40 толық құбырлы DES ядросы бар, жалпы сыйымдылығы 768 гигакей/сек. Жүйе шамамен 26 сағат ішінде DES-тің барлық 56 биттік кілт кеңістігін толық іздестіре алады және бұл қызмет онлайн төлем арқылы ұсынылады.

For any cipher, the most basic method of attack is brute force—trying every possible key in turn. The length of the key determines the number of possible keys, and hence the feasibility of this approach. For DES, questions were raised about the adequacy of its key size early on, even before it was adopted as a standard, and it was the small key size, rather than theoretical cryptanalysis, which dictated a need for a replacement algorithm. As a result of discussions involving external consultants including the NSA, the key size was reduced from 256 bits to 56 bits to fit on a single chip. In academia, various proposals for a DES cracking machine were advanced. In 1977, Diffie and Hellman proposed a machine costing an estimated US$20 million which could find a DES key in a single day. By 1993, Wiener had proposed a key search machine costing US$1 million which would find a key within 7 hours. However, none of these early proposals were ever implemented—or, at least, no implementations were publicly acknowledged. The vulnerability of DES was practically demonstrated in the late 1990s. In 1997, RSA Security sponsored a series of contests, offering a $10,000 prize to the first team that broke a message encrypted with DES for the contest. That contest was won by the DESCHALL Project, led by Rocke Verser, Matt Curtin, and Justin Dolske, using idle cycles of thousands of computers across the Internet. The feasibility of cracking DES quickly was demonstrated in 1998 when a custom DES cracker was built by the Electronic Frontier Foundation (EFF), a cyberspace civil rights group, at the cost of approximately US$250,000 (see EFF DES cracker). Their motivation was to show that DES was breakable in practice as well as in theory: "There are many people who will not believe a truth until they can see it with their own eyes. Showing them a physical machine that can crack DES in a few days is the only way to convince some people that they really cannot trust their security to DES." The machine brute forced a key in a little more than 2 days' worth of searching. The next confirmed DES cracker was the COPACOBANA machine built in 2006 by teams of the Universities of Bochum and Kiel, both in Germany. Unlike the EFF machine, COPACOBANA consists of commercially available, reconfigurable integrated circuits. 120 of these field programmable gate arrays (FPGAs) of type XILINX Spartan 3 1000 run in parallel. They are grouped in 20 DIMM modules, each containing 6 FPGAs. The use of reconfigurable hardware makes the machine applicable to other code breaking tasks as well. One of the more interesting aspects of COPACOBANA is its cost factor. One machine can be built for approximately $10,000. The cost decrease by roughly a factor of 25 over the EFF machine is an example of the continuous improvement of digital hardware—see Moore's law. Adjusting for inflation over 8 years yields an even higher improvement of about 30x. Since 2007, SciEngines GmbH, a spin off company of the two project partners of COPACOBANA has enhanced and developed successors of COPACOBANA. In 2008 their COPACOBANA RIVYERA reduced the time to break DES to less than one day, using 128 Spartan 3 5000's. SciEngines RIVYERA held the record in brute force breaking DES, having utilized 128 Spartan 3 5000 FPGAs. Their 256 Spartan 6 LX150 model has further lowered this time. In 2012, David Hulton and Moxie Marlinspike announced a system with 48 Xilinx Virtex 6 LX240T FPGAs, each FPGA containing 40 fully pipelined DES cores running at 400 MHz, for a total capacity of 768 gigakeys/sec. The system can exhaustively search the entire 56 bit DES key space in about 26 hours and this service is offered for a fee online.

Жәндіктерден жылдам шабуылдау

DES-тің толық 16 раундын бұзуға қабілетті үш шабуыл бар: дифференциалдық криптоанализ (DC), осы шабуыл түрлері кейде сертификациялық әлсіздіктер деп аталады. Дифференциалдық криптоанализ 1980-ші жылдардың соңында Эли Бихам мен Ади Шамир қайта ашты; бұл әдіс бұрын IBM және NSA-ға белгілі болған, бірақ құпия сақталған. Толық 16 раундты бұзу үшін дифференциалдық криптоанализге 247 таңдалған ашық мәтін қажет. DES DC-ге қарсы тұру үшін жасалған. Сызықтық криптоанализді Мицуру Мацуи ашқан, оған 243 белгілі ашық мәтін қажет (Мацуи, 1993); әдіс іске асырылды (Мацуи, 1994) және DES-тің алғашқы тәжірибелік криптоанализі ретінде жарияланды. DES-тің осы типтегі шабуылға қарсы тұру үшін жасалғандығын көрсететін ешқандай дәлел жоқ. Сызықтық криптоанализдің (LC) жалпыланған түрі 1994 жылы (Калиски және Робшоу) ұсынылды және Бірюков және басқалармен одан әрі жетілдірілді (2004); олардың талдауы шабуылға қажетті дерек көлемін кем дегенде 4 есеге азайтуға болатынын көрсетеді, яғни 243 орнына 241. Сызықтық криптоанализдің таңдалған ашық мәтін нұсқасында да дерек көлемін азайтуға болады (Knudsen және Mathiassen, 2000). Junod (2001) сызықтық криптоанализдің нақты уақыт күрделілігін анықтау үшін бірнеше тәжірибелер жүргізді және оның күтілгеннен асып түскенін, 239–241 DES есептеуіне тең уақыт қажет екенін хабарлады. Жақсартылған Дэвис шабуылы: сызықтық және дифференциалдық криптоанализ – жалпы әдістер, оларды көптеген схемаларға қолдануға болады, ал Дэвис шабуылы – DES үшін арнайы әдіс, оны алғаш 1980-ші жылдары Дональд Дэвис ұсынды, ал Бихам мен Бирюков (1997) оны жақсартты. Шабуылдың ең күшті түрі 250 белгілі ашық мәтін қажет етеді, есептеу күрделілігі 250 және 51% сәттілік деңгейіне ие. Шифрдың раундтары кем қысқартылған нұсқаларына, яғни 16 раундтан кем нұсқаларына қарсы шабуылдар да ұсынылды. Мұндай талдау қауіпсіздік үшін қанша раунд қажет екенін және толық нұсқа қанша "қауіпсіздік маржасын" сақтайтынын көрсетеді. Дифференциалдық-сызықтық криптоанализді Лэнгфорд пен Хеллман 1994 жылы ұсынды, ол дифференциалдық және сызықтық криптоанализді бір шабуылға біріктіреді. Шабуылдың жетілдірілген нұсқасы 215,8 таңдалған ашық мәтінмен 9 раундтық DES-ті бұзуға қабілетті және 229,2 уақыт күрделілігіне ие (Biham және басқалар, 2002).

There are three attacks known that can break the full 16 rounds of DES with less complexity than a brute force search: differential cryptanalysis (DC), these types of attack are sometimes termed certificational weaknesses. Differential cryptanalysis was rediscovered in the late 1980s by Eli Biham and Adi Shamir; it was known earlier to both IBM and the NSA and kept secret. To break the full 16 rounds, differential cryptanalysis requires 247 chosen plaintexts. DES was designed to be resistant to DC. Linear cryptanalysis was discovered by Mitsuru Matsui, and needs 243 known plaintexts (Matsui, 1993); the method was implemented (Matsui, 1994), and was the first experimental cryptanalysis of DES to be reported. There is no evidence that DES was tailored to be resistant to this type of attack. A generalization of LC—multiple linear cryptanalysis—was suggested in 1994 (Kaliski and Robshaw), and was further refined by Biryukov and others. (2004); their analysis suggests that multiple linear approximations could be used to reduce the data requirements of the attack by at least a factor of 4 (that is, 241 instead of 243). A similar reduction in data complexity can be obtained in a chosen plaintext variant of linear cryptanalysis (Knudsen and Mathiassen, 2000). Junod (2001) performed several experiments to determine the actual time complexity of linear cryptanalysis, and reported that it was somewhat faster than predicted, requiring time equivalent to 239–241 DES evaluations. Improved Davies' attack: while linear and differential cryptanalysis are general techniques and can be applied to a number of schemes, Davies' attack is a specialized technique for DES, first suggested by Donald Davies in the eighties, and improved by Biham and Biryukov (1997). The most powerful form of the attack requires 250 known plaintexts, has a computational complexity of 250, and has a 51% success rate. There have also been attacks proposed against reduced round versions of the cipher, that is, versions of DES with fewer than 16 rounds. Such analysis gives an insight into how many rounds are needed for safety, and how much of a "security margin" the full version retains. Differential linear cryptanalysis was proposed by Langford and Hellman in 1994, and combines differential and linear cryptanalysis into a single attack. An enhanced version of the attack can break 9 round DES with 215.8 chosen plaintexts and has a 229.2 time complexity (Biham and others, 2002).

Жайдастырылған DES

Жайлатылған DES (SDES) қазіргі заманғы криптоаналитикалық техникаларды оқуға көмектесу үшін білім беру мақсатында ғана жасалған. SDES құрылымы мен қасиеттері DES-ке ұқсас, бірақ шифрлау және шифрды ашуды қолмен, қарындаш пен қағазбен орындауды жеңілдету үшін оңайлатылған. Кейбір адамдар SDES-ті оқу DES және басқа блок шифрларын, сондай-ақ оларға қарсы түрлі криптоаналитикалық шабуылдарды түсінуге көмектеседі деп есептейді.

Ауыстыру алгоритмдері

Қауіпсіздік туралы алаңдаушылық және бағдарламалық жасақтамада DES-тің салыстырмалы түрде баяу жұмыс істеуі зерттеушілерді 1980-ші жылдардың аяғы мен 1990-шы жылдардың басында пайда бола бастаған әртүрлі баламалы блок шифрын ұсынуға итермеледі: мысалдарға RC5, Blowfish, IDEA, NewDES, SAFER, CAST5 және FEAL кіреді. Бұл жобалардың көпшілігі DES-тің 64 биттік блок өлшемін сақтады және олар әдетте 64 бит немесе 128 бит кілтті қолданғанымен, "түсіру" орнына қолданылуы мүмкін еді. Кеңес Одағында 64 биттік блок көлемі мен 256 биттік кілті бар GOST 28147-89 алгоритмі енгізілді, ол кейін Ресейде де қолданылды. DES-тің өзі қауіпсіз схемада бейімделіп, қайта пайдаланылуы мүмкін. Көптеген бұрынғы DES пайдаланушылары қазір Үш есе DES (TDES) қолданады, ол DES-тің патент иелерінің бірі сипаттаған және талдаған (FIPS Pub 46-3 қараңыз); бұл DES-ті екі (2TDES) немесе үш (3TDES) түрлі кілттермен үш рет қолдануды қамтиды. TDES жеткілікті қауіпсіз деп саналады, бірақ ол өте баяу. Есептеу шығындары аз DES X, DES алдында және кейін қосымша кілт материалдарын XOR операциясы арқылы қосу арқылы кілт өлшемін ұлғайтады. GDES – шифрлауды жылдамдату тәсілі ретінде ұсынылған DES нұсқасы, бірақ ол дифференциалдық криптоанализге осал екені дәлелденді. 1997 жылдың 2 қаңтарында NIST DES-тің орнын алмастырушыны таңдауға ниетті екенін мәлімдеді. 2001 жылы халықаралық бәйгеден кейін NIST жаңа шифрлау стандартын таңдады, ол – Advanced Encryption Standard (AES) болды. AES ретінде таңдалған алгоритмді оның жасаушылары Rijndael деген атпен ұсынды. NIST AES бәйгесінің басқа финалистері RC6, Serpent, MARS және Twofish болды.