Кіріспе
Тез үйлесімді криптографиялық хэш-функцияларды құру әдісі Криптографияда Меркль-Дамгард құрылымы немесе Меркль-Дамгард хэш-функциясы – тез үйлесімді криптографиялық хэш-функцияларды соқтығысуға төзімді бір жақты қысылу функцияларынан құру әдісі. Бұл құрылыс көптеген танымал хэш алгоритмдерін, мысалы MD5, SHA 1 және SHA 2 жобалауда қолданылды. Меркль-Дамгард құрылысын Ральф Меркль 1979 жылы Ph.D. диссертациясында сипаттады. Ральф Меркль және Иван Дамгард тәуелсіз түрде құрылыстың дұрыс екенін дәлелдеді: яғни, тиісті толтыру схемасы қолданылса және қысылу функциясы соқтығысуға төзімді болса, онда хэш-функция да соқтығысуға төзімді болады. Меркль-Дамгард хэш-функциясы алдымен MD стандартына сәйкес толтыру функциясын қолданады, нәтижесінде кіріс өлшемі белгілі бір санға (мысалы, 512 немесе 1024) еселі болады – себебі қысылу функциялары кез келген өлшемдегі кірістерді өңдей алмайды. Содан кейін хэш-функция нәтижені белгілі өлшемді блоктарға бөліп, оларды компрессиялық функциямен бірінен соң бірі өңдейді, әр жолы кіріс блогын алдыңғы раундтың нәтижесімен біріктіреді. Көп соқтығыстар (бірдей хэшпен көптеген хабарламалар) соқтығыстарды табудан аздап көп жұмыспен ғана табылуы мүмкін. "Шелектік шабуылдар" көп соқтығыстарды табу үшін каскадтық құрылысты (жоғарыда айтылғандай) белгілі бір префикстің соқтығыстарымен (таңдалған префикс соқтығыстары) біріктіреді. Бұл өте нақты соқтығысқан құжаттарды құруға мүмкіндік береді, және бұл соқтығысты табудан көбірек жұмыс талап етеді, бірақ кездейсоқ оракул үшін осыны істеуге қарағанда әлдеқайда аз. Ұзындықты кеңейту: белгісіз кіріс X-тің H(X) хэшін ескере отырып, , мәнін табу оңай, мұнда pad – хэштің толтыру функциясы. Яғни, X белгісіз болса да, X-ке қатысты кіріс хэштерін табуға болады. Ұзындықты кеңейту шабуылдары Flickr сияқты бірқатар коммерциялық веб-хабарламаларды аутентификациялау схемаларына шабуыл жасау үшін қолданылды.
In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision resistant cryptographic hash functions from collision resistant one way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA 1 and SHA 2. The Merkle–Damgård construction was described in Ralph Merkle's Ph. D. thesis in 1979. Ralph Merkle and Ivan Damgård independently proved that the structure is sound: that is, if an appropriate padding scheme is used and the compression function is collision resistant, then the hash function will also be collision resistant. The Merkle–Damgård hash function first applies an MD compliant padding function to create an input whose size is a multiple of a fixed number (e. g. 512 or 1024) — this is because compression functions cannot handle inputs of arbitrary size. The hash function then breaks the result into blocks of fixed size, and processes them one at a time with the compression function, each time combining a block of the input with the output of the previous round. Multicollisions (many messages with the same hash) can be found with only a little more work than collisions. "Herding attacks", which combines the cascaded construction for multicollision finding (similar to the above) with collisions found for a given prefix (chosen prefix collisions). This allows for constructing highly specific colliding documents, and it can be done for more work than finding a collision, but much less than would be expected to do this for a random oracle. Length extension: Given the hash H(X) of an unknown input X, it is easy to find the value of , where pad is the padding function of the hash. That is, it is possible to find hashes of inputs related to X even though X remains unknown. Length extension attacks were actually used to attack a number of commercial web message authentication schemes such as one used by Flickr.
Кең құбырлар құрылысы
Меркль-Дамгард құрылысының бірнеше құрылымдық кемшіліктеріне байланысты, әсіресе ұзындығын кеңейту мәселесі және көптік соқтығыс шабуылдарына байланысты, Стефан Лукс Меркль-Дамгард құрылысының орнына кең құбырлы хэш қолдануды ұсынды. Кең құбырлы хэш Меркль-Дамгард құрылысына өте ұқсас, бірақ ішкі жай-күйінің мөлшері үлкен, яғни ішкі қолданылатын бит ұзындығы шығыс бит ұзындығынан артық. Егер n биттік хэш қажет болса, f қысым функциясы 2n биттік тізбектеу мәнін және хабардың m битін қабылдап, оны 2n биттік шығысқа қысымдайды. Сондықтан, соңғы қадамда екінші қысым функциясы соңғы ішкі хэш мәнін (2n бит) соңғы хэш мәніне (n бит) қысымдайды. Бұл соңғы 2n биттік шығыстың жартысын жою арқылы оңай орындалуы мүмкін. SHA 512/224 және SHA 512/256 осы формада, өйткені олар SHA 512-нің түрінен алынған. SHA 384 және SHA 224 тиісінше SHA 512 және SHA 256-дан алынған, бірақ олардың құбырларының ені 2n-ден әлдеқайда кішкентай.
Тез кең құбырлар құрылысы
Мридул Нанди мен Сурадюти Пол Widepipe хэш-функциясын шамамен екі есе жылдам етуге болатынын көрсетті, егер Widepipe күйін келесідей екіге бөлуге болады: бір жартысы келесі сығымдау функциясына жіберіледі, ал екінші жартысы осы сығымдау функциясының нәтижесімен біріктіріледі. Хаш құрылымының басты идеясы – алдыңғы тізбектеу мәнінің жартысын сығымдау функциясының нәтижесімен XOR операциясы арқылы байланыстыру. Осы арқылы құрылым әр итерацияда бастапқы Widepipe-тан гөрі ұзақ хабар блоктарын қабылдайды. Бұрынғы f функциясын қолдана отырып, n биттік тізбектеу мәндері мен n+m биттік хабарды қабылдайды. Дегенмен, мұның құны – алдын ала жіберу үшін құрылымда қолданылатын қосымша жад.
Параллель алгоритм
MD алгоритмі бастапқыда реттілікпен жұмыс істейді. Соқтығысуға төзімді хеш-функцияны соқтығысуға төзімді қысу функциясынан құратын параллель алгоритм бар. PARSHA 256 хеш-функциясы осы параллель алгоритмді және SHA 256 қысу функциясын пайдаланып жасалған.
Ұзындығы төселген үлгі
Хабарды сығылу функциясына беру үшін соңғы блок тұрақты деректермен (әдетте нөлдермен) толық блокқа дейін толтырылуы керек. Мысалы, хэштелуі керек хабарлама "HashInput" (9 октеттік тізбек, ASCII-де 0x48617368496e707574) және сығымдалу функциясының блок мөлшері 8 байт (64 бит) болсын. Біз екі блок аламыз (толтыру октеттері ашық көк түспен көрсетілген):
Бұл, мазмұны бірдей, бірақ соңында қосымша нөлдермен аяқталатын басқа хабарламалар да сол хэш-мәнді береді дегенді білдіреді. Жоғарыдағы мысалда, тағы бір дерлік бірдей хабарлама (0x48617368496e707574) жоғарыдағы "HashInput" бастапқы хабарламасымен бірдей хэш-мәнді шығарады. Басқаша айтқанда, соңында артық нөлдері бар кез келген хабар, нөлдері жоқ хабардан ажыратылмайды. Бұл жағдайды болдырмау үшін, бірінші толтыру октетінің бірінші биті "1" (0x80) деп өзгертіледі, нәтижесінде:
Дегенмен, көптеген іске асыруларда хабарлама ұзындығы мәнін енгізу үшін соңғы блоктің соңында белгілі бір позицияда белгілі бір биттік мөлшер (көбінесе қазіргі заманғы алгоритмдерде 64 немесе 128 бит) қолданылады (SHA 1 псевдокодын қараңыз). Егер жеткілікті орын болса, ұзындық мәнін соңғы блокқа енгізу арқылы одан әрі жақсартуға болады. Бұл хабарлама ұзындығы үшін қосымша блоктан қашуға мүмкіндік береді. Егер ұзындық мәні 5 байтқа (40 бит) кодталған деп есептесек, хабарлама былай болады:
Ескеріңіз, хабарлама ұзындығын метадеректерде бөлек сақтау немесе хабарламаның басында енгізу ұзындықты кеңейту шабуылына тиімді қарсы шара болып табылады, егер хабарлама ұзындығының және бақылау сомасының жарамсыздығы екеуі де тұтастық тексеруінің сәтсіздігі деп есептелсе.