Криптографиялық хеш-функциялардың қасиеттері: тұрақтылық, соқтығыстарға қарсы келу. MD5, SHA-1 сынды бұзылған функциялар мен жаңа алгоритмдер туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Криптографиялық хэш-функциялардың қасиеттері
Property of cryptographic hash functions
Криптографияда, соқтығысуға төзімділік – криптографиялық хэш-функциялардың қасиеті: егер бірдей нәтижеге екі түрлі кіріс табу қиын болса, онда H хэш-функциясы соқтығысуға төзімді болып есептеледі; яғни, a ≠ b болатын екі кіріс a және b үшін H(a) = H(b) теңдігі орындалады. Клубшау принципі бойынша, кірістер саны шығыстар санынан көп болған кез келген хэш-функцияда мұндай соқтығысулар болуы міндетті.
In cryptography, collision resistance is a property of cryptographic hash functions: a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b). The pigeonhole principle means that any hash function with more inputs than outputs will necessarily have such collisions;
Криптографиялық хэш-функциялар көбінесе соқтығысуға төзімді болу үшін жасалады. Дегенмен, бұрын соқтығысуға төзімді деп есептелген көптеген хэш-функциялар кейін бұзылды. MD5 және SHA 1 есімді функциялар үшін соқтығысуларды табуға күш қолдану әдісінен тиімдірек техникалар жарияланды. Бірақ, кейбір хэш-функциялар үшін соқтығысуларды табу, бүтін сандарды жіктеу немесе дискретті логарифм сияқты, шешу қиын математикалық есептерді шешумен бірдей қиын екені дәлелденген. Мұндай функциялар «дәлелмен қауіпсіз» деп аталады.
Cryptographic hash functions are usually designed to be collision resistant. However, many hash functions that were once thought to be collision resistant were later broken. MD5 and SHA 1 in particular both have published techniques more efficient than brute force for finding collisions. However, some hash functions have a proof that finding collisions is at least as difficult as some hard mathematical problem (such as integer factorization or discrete logarithm). Those functions are called provably secure.
Көтермеге төзімділігі төмен және күшті
Бәсекеге төзімділіктің екі түрі бар. Хеш функциясының соқтығысуға төзімділігі әлсіз деп есептеледі, егер хеш функциясы H және x берілген болса, H(x) = H(x') болатын басқа x' табылмаса. Басқаша айтқанда, x белгілі болғанда, сол хеш функциясы үшін соқтығысу тудыратын басқа x' табу мүмкін емес. Хеш функциясының соқтығысуға төзімділігі күшті деп есептеледі, егер хеш функциясы H берілген болса, H(x) = H(x') болатын кез келген x және x' табылмаса. Басқаша айтқанда, хеш функциясы үшін соқтығысу тудыратын екі x табу мүмкін емес.
There are two different types of collision resistance. A hash function has weak collision resistance when, given a hashing function H and an x, no other x' can be found such that H(x)=H(x'). In words, when given an x, it is not possible to find another x' such that that hashing function would create a collision. A hash function has strong collision resistance when, given a hashing function H, no arbitrary x and x' can be found where H(x)=H(x'). In words, no two x's can be found where the hashing function would create a collision.
Негізгі себептері
Соқтығысуға төзімділік бірнеше себеппен қажет. Кейбір цифрлық қолтаңба жүйелерінде тарап құжатты растау үшін құжаттың хэшіне ашық кілт қолтаңбасын жариялайды. Егер бірдей хэшпен екі құжат жасау мүмкін болса, шабуылшы бір тарапты біреуге куәландыруға итермелей алады, содан кейін сол тарап екінші құжатқа да куәлік бергенін айта алады. Кейбір таратылған контент жүйелерінде тараптар файлдардың криптографиялық хэштерін салыстырып, олардың бірдей нұсқаға ие екеніне көз жеткізеді. Бірдей хэшпен екі файл жасауға қабілетті шабуылшы пайдаланушыларды олардың шын мәнінде бірдей файл нұсқасына ие екендігіне сендіре алады.
Collision resistance is desirable for several reasons. In some digital signature systems, a party attests to a document by publishing a public key signature on a hash of the document. If it is possible to produce two documents with the same hash, an attacker could get a party to attest to one, and then claim that the party had attested to the other. In some distributed content systems, parties compare cryptographic hashes of files in order to make sure they have the same version. An attacker who could produce two files with the same hash could trick users into believing they had the same version of a file when they in fact did not.