Криптографиялық шабуыл: Тұрақты ұрысулар және алдын ала таңдалған префикстер

Кіріспе

Криптографиялық шабуыл

Криптографияда, криптографиялық хэш функциясына қатысты соқтығысу шабуылы бірдей хэш мәнін беретін екі түрлі кіріс табуға бағытталған, яғни хэш соқтығысуына қол жеткізуге тырысады. Бұл, нақты бір мақсатты хэш мәнін анықтауға қатысты преобраз шабуылынан өзгеше. Соқтығысу шабуылдарының шамамен екі түрі бар:
Классикалық соқтығысу шабуылы – hash(m1) = hash(m2) болатындай, екі түрлі хабарды m1 және m2 табу. Көбірек айтқанда:
Таңдалған префикстің соқтығысуы – екі түрлі префикстер p1 және p2 берілген кезде, hash(p1 ∥ s1) = hash(p2 ∥ s2) болатындай, s1 және s2 екі қосымшаны табу, мұнда ∥ біріктіру операциясын білдіреді.

Классикалық соқтығысу шабуыл

Симметриялық кілт шифрлары күшпен бұзуға осал болғандай, әрбір криптографиялық хэш-функция туған күн шабуылы арқылы соқтығысуға қабілетті. Туған күн мәселесіне байланысты, мұндай шабуылдар күшпен бұзуға қарағанда әлдеқайда жылдам жүзеге асырылады. n биттік хэш 2n/2 уақыт қадамында (хэш-функцияның есептелуі) бұзылуы мүмкін. Математикалық тұрғыдан алғанда, соқтығысу шабуылы екі түрлі хабарламаны m1 және m2 табады, олар үшін hash(m1) = hash(m2) болады. Классикалық соқтығысу шабуылында шабуылшы ешбір хабарламаның мазмұнына бақылай алмайды, бірақ олар алгоритммен кездейсоқ таңдалады. Нақты хэш-функцияларды криптоталдау арқылы тиімдірек шабуылдар жасауға болады. Егер соқтығысу шабуылы туған күн шабуылынан жылдамырақ болса, хэш-функция көбінесе «бұзылған» деп жарияланады. NIST хэш-функцияларының бәсекелесі екі кең таралған хэш-функцияларға – MD5 және SHA 1-ге қарсы жарияланған соқтығысу шабуылдарының нәтижесінде туындады. MD5-ке қарсы соқтығысу шабуылдары соншалықты жетілдірілді, 2007 жылдан бастап оны қарапайым компьютерде бірнеше секундта жасауға болады. Осылайша құрылған хэш-соқтығысулар әдетте тұрақты ұзындықта және көбінесе құрылымдалмаған болады, сондықтан кең таралған құжат форматтарына немесе протоколдарға тікелей шабуыл жасау мүмкін емес. Дегенмен, көптеген форматтардағы динамикалық құрылымдарды теріс пайдалану арқылы одан айналып өтуге болады. Осылайша, екі құжат бірдей хэш-мәніне ие болу үшін мүмкіндігінше ұқсас етіп жасалады. Бір құжатқа қол қою үшін оны билік өкілдеріне ұсынады, содан кейін қол екінші файлға көшіріледі. Мұндай қаскөй құжат бір құжатта екі түрлі хабарламаны қамтиды, бірақ файлға енгізілген ұсақ өзгерістер арқылы шартты түрде бірін немесе екіншісін көрсетеді: PostScript немесе Microsoft Word-тегі макростар сияқты кейбір құжат форматтарында шартты конструкциялар бар (егер-онда-әйтпесе), олар файлдағы орналасқан жердің бір немесе басқа мәнін тексеруге және көрсетілетін нәрсені бақылауға мүмкіндік береді. TIFF файлдарында кесілген суреттер болуы мүмкін, бұл суреттің басқа бөлігі хэш-мәніне әсер етпей көрсетіледі. Нақты соқтығысу шабуылы 2008 жылдың желтоқсанында жарияланды, онда қауіпсіздік зерттеушілерінің тобы MD5 хэш-функциясына қарсы префикс соқтығысу шабуылын пайдаланып, сертификат беру органының кейіпкері болуға болатын жалған X.509 қол қою сертификатын жариялады. Бұл шабуылшының кез келген SSL қорғалған веб-сайттың кейіпкерін алмастырып, барлық веб-браузерлерде электрондық коммерцияны қорғау үшін орнатылған сертификатты растауды бұзуға мүмкіндік береді. Жалған сертификатты нақты билік органдары қайтаруға мүмкін болмайды, сонымен қатар, оның қолданылу мерзімі де кездейсоқ түрде жасалма болуы мүмкін. MD5 2004 жылдан бері өте әлсіз екені белгілі болғанмен, 2012 жылдың мамырында кем дегенде бір Microsoft кодты қол қою сертификаты әлі де MD5 қолданды. Flame зиянды бағдарламалық жасақтамасы өз компоненттерінің кодты қол қоюын Microsoft түбірлік сертификатымен бұрмалау үшін таңдалған префикстерде соқтығысу шабуылдарының жаңа нұсқасын сәтті қолданды, ол әлі де бұзылған MD5 алгоритмін қолданды. 2019 жылы зерттеушілер SHA 1-ге қарсы таңдалған префикс соқтығысу шабуылдарын 266.9 және 269.4 арасындағы есептеу күрделілігімен және 100 000 АҚШ долларынан аз құнмен тапты. 2020 жылы зерттеушілер SHA 1-ге қарсы таңдалған префикстер соқтығысуының күрделілігін 263.4-ке дейін төмендетті.

Much like symmetric key ciphers are vulnerable to brute force attacks, every cryptographic hash function is inherently vulnerable to collisions using a birthday attack. Due to the birthday problem, these attacks are much faster than a brute force would be. A hash of n bits can be broken in 2n/2 time steps (evaluations of the hash function). Mathematically stated, a collision attack finds two different messages m1 and m2, such that hash(m1) = hash(m2). In a classical collision attack, the attacker has no control over the content of either message, but they are arbitrarily chosen by the algorithm. More efficient attacks are possible by employing cryptanalysis to specific hash functions. When a collision attack is discovered and is found to be faster than a birthday attack, a hash function is often denounced as "broken". The NIST hash function competition was largely induced by published collision attacks against two very commonly used hash functions, MD5 and SHA 1. The collision attacks against MD5 have improved so much that, as of 2007, it takes just a few seconds on a regular computer. Hash collisions created this way are usually constant length and largely unstructured, so cannot directly be applied to attack widespread document formats or protocols. However, workarounds are possible by abusing dynamic constructs present in many formats. In this way, two documents would be created which are as similar as possible in order to have the same hash value. One document would be shown to an authority to be signed, and then the signature could be copied to the other file. Such a malicious document would contain two different messages in the same document, but conditionally display one or the other through subtle changes to the file:

Some document formats like PostScript, or macros in Microsoft Word, have conditional constructs. (if then else) that allow testing whether a location in the file has one value or another in order to control what is displayed. TIFF files can contain cropped images, with a different part of an image being displayed without affecting the hash value. A real world collision attack was published in December 2008 when a group of security researchers published a forged X.509 signing certificate that could be used to impersonate a certificate authority, taking advantage of a prefix collision attack against the MD5 hash function. This meant that an attacker could impersonate any SSL secured website as a man in the middle, thereby subverting the certificate validation built in every web browser to protect electronic commerce. The rogue certificate may not be revokable by real authorities, and could also have an arbitrary forged expiry time. Even though MD5 was known to be very weak in 2004, and at least one Microsoft code signing certificate was still using MD5 in May 2012. The Flame malware successfully used a new variation of a chosen prefix collision attack to spoof code signing of its components by a Microsoft root certificate that still used the compromised MD5 algorithm. In 2019, researchers found a chosen prefix collision attack against SHA 1 with computing complexity between 266.9 and 269.4 and cost less than 100,000 US dollars. In 2020, researchers reduced the complexity of a chosen prefix collision attack against SHA 1 to 263.4.

Шабуыл сценарийлері

Криптографиялық хэш-функциялардың көптеген қолданыстары соқтығысуға қарсы тұруға тікелей байланысты емес, сондықтан соқтығысу шабуылдары олардың қауіпсіздігіне әсер етпейді. Мысалы, HMAC-тар бұған осал емес. Шабуыл тиімді болуы үшін, шабуылшы хэш-функцияға берілетін мәліметтерді бақылауы керек.

Хаш-тасымалдау

Hash flooding (hashDoS деп те аталады) – хэш-қоғамдасуларды пайдаланып, хэш-кестелерде іздеудің ең нашар жағдайын (сызықтық зондтау) пайдаланатын қызметтен бас тарту шабуылы. Ол алғаш рет 2003 жылы сипатталған. Мұндай шабуылды жүзеге асыру үшін шабуылшы серверге бірдей хэш-мәнді беретін бірнеше дерек бөлігін жібереді, содан кейін серверді баяу іздеулер орындауға мәжбүр етуге тырысады. Хэш-кестелерде қолданылатын хэш-функциялардың басты назары жылдамдық болғандықтан, қауіпсіздік екінші орында тұрды, көптеген негізгі бағдарламалау тілдері әсер етті, және осы сыныптағы жаңа осалдықтар алғашқы таныстырылымнан кейін он жыл өткен соң да пайда болды. (Сырттан басқарылмаса, қолданбаның хэш-кестесіне қатысты "қарапайым" хэштерді пайдалану қауіпсіз болып қалады.) (Ішінара) алдынғы бейне шабуылын пайдаланып, Блум сүзгілерін толтыруға ұқсас шабуыл жасау мүмкін.