В криптографії, одностороння функція стиснення — це така функція, яка перетворює два вхідні аргументи фіксованої довжини, на результат фіксованої довжини. Функція одностороння в тому сенсі, що важко вгадати аргументи значення функції для яких дорівнює заданій величині. Односторонні функції стиснення не пов'язані зі звичними алгоритмами стиснення даних, які натомість можуть бути оберненими точно (стиснення без втрат) або приблизно (стиснення з втратами).
Одностороння функція стиснення використовується, наприклад, в структурі Меркла-Демґардаа всередині криптографічних геш-функцій.
Односторонні функції стиснення часто будуються з блочних шифрів. Для того, щоб перетворити будь-який звичайний блочний шифр в односторонню функцію стиснення, існують методи Девіса-Мейєра, Матіса-Мейера-Осеаса, Міагучі-Пренеля (функції стиснення одноблокової довжини), та MDC-2/Меєра-Шіллінга, MDC-4, Hirose (довжини два блоки). Ці методи докладно описані нижче. ([en] - також назва хеш-функціх запатентованої IBM.)
Стиснення
Функція стиснення змішує два аргументи фіксованої довжини, і повертає один результат фіксованої довжини, розмір якого дорівнює розміру одного з аргументів. На це також можна дивитись як на функцію яка перетворює один великий аргумент фіксованої довжини, на коротший результат фіксованої довжини.
Наприклад, хай аргумент А має довжину в 128 біт, аргумент B теж 128 біт, і вони стискуються в один результат довжини 128 біт. Це те ж саме, якщо б один-єдиний 256-бітовий аргумент стискувався в 128-бітний результат.
Деякі функції стиснення не стискують вдвічі, а з якимось іншим коефіцієнтом. Наприклад, аргумент А може бути 256-бітовим, а аргумент B 128-бітовим, і вони можуть стискатися в 128 біт. Тобто, в цілому 384 вхідних бітів стискаються разом до 128 вихідних бітів.
Змішування виконується таким чином щоб досягти повного лавинового ефекту, коли кожен вихідний біт залежить від кожного вхідного біта.
Односторонність
Одностороння функція - це функція яку легко обчислити, але важко обчислити обернену до неї. Одностороння функція стиснення (яку також називають геш-функцією) повинна мати наступні властивості:
- Легко обчислити: Якщо відомі аргументи, легко отримати результат.
- Стійкість до прообразу: Якщо зловмисник знає лише вихідні дані, для нього буде нереально обчислити вхідні. Іншими словами, для результату функції h, неможливо обчислити m таке що hash(m)=h.
- Стійкість до другого прообразу: Маючи вхідні дані m1 вихідними для яких є h, треба щоб знайти інше значення m2 на виході для якого теж було h тобто hash(m1)=hash(m2).
- [en]: Треба щоб знайти два такі різні аргументи для яких функція дає однаковий результат було важко, тобто зловмисник не повинен могти знайти пару повідомлень m1 ≠ m2 таких що hash(m1) = hash(m2). Через парадокс днів народження (див. також атака «днів народження») існує 50% ймовірність знайти колізію за час приблизно 2n/2 де n кількість біт у виході геш-функції. Таким чином атака на геш-функцію не повинна знаходити колізію за менш ніж 2n/2 спроб.
В ідеалі, під "неможливістю" в стійкості до прообразу і другого прообразу слід розуміти обчислювальну складність приблизно 2n, де n - кількість біт у виході функції. Проте, особливо для випадку стійкості до другого прообразу це досить складна проблема.[]
Будова Меркле — Демґарда
Типовим застосуванням односторонніх функцій стискання є їх використання в будові Меркле-Демґарда всередині криптографічних геш-функцій. Популярні геш-функції, такі наприклад як MD5, SHA-1 і SHA-2 використовують цю будову.
Геш функція повинна бути здатною перетворити повідомлення довільної довжини у результат фіксованої довжини. Цього можна досягти розбиваючи ввід на послідовність блоків однакової довжини, і опрацьовуючи їх послідовно, використовуючи односторонню функцію стискання. Функція стискання повинна бути або сконструйована спеціально для гешування, або побудована з блочного шифру.
Останній блок повинен бути [en].
Коли застосовується доповнення за довжиною (яке також називають MD-посилення (англ. MD-strengthening)), атаки не здатні знайти колізії швидше за час парадоксу днів народження (2n/2, де n розмір блоку в бітах) якщо використана функція f стійка до колізій. Таким чином, Будова Меркла-Демґардаt зводить задачу знаходження правильної геш-функції, до знаходження функції стискання.
Атака знаходження другого прообразу (маючи повідомлення m1 зловмисник знаходить інше повідомлення m2 таке що hash(m1) = hash(m2)) можлива, згідно Келсі та Шнаєром для 2k-блокового повідомлення за час k × 2n/2+1+2n-k+1. Складність більша за 2n/2 але нижча за 2n при довгих повідомленнях, і для коротких повідомлень наближається до 2n.
Побудова з блочних шифрів
Також, односторонні функції стискання будують з блочних шифрів.
Блочні шифри (як і односторонні функції стискання) отримують на вхід дві послідовності фіксованої довжини (ключ і відкритий текст) і повертають одну вихідну послідовність (шифротекст) яка має таку саму довжину як і вхідний відкритий текст.
Проте, сучасні блочні шифри лише частково односторонні. Тобто, маючи відкритий текст і шифротекст нереально знайти ключ що перетворює відкритий текст в шифротекст. Але маючи шифротекст і ключ, знайти відкритий текст можна просто використавши функцію дешифрування блочного шифру. Тому, щоб перетворити блочний шифр в односторонню функцію стискання потрібні деякі додаткові операції.
Деякими методами для перетворення звичайного блочного шифру в односторонню функцію стискання є методи Девіса-Меєра, Матіаса-Меєра-Осеаса, Міягучі-Пренеля (функції стискання одноблокової довжини) та MDC-2, MDC-4, Хіроші (функції стискання двоблокової довжини).
Функції стискання одноблокової довжини виводять скільки ж біт, скільки обробляється використаним блочним шифром. Відповідно, функції стискання двоблокової довжини виводять вдвічі більше біт.
Якщо блочний шифр має [en] наприклад 128 біт, методи одноблокової довжини створюють геш-функцію яка має розмір блоку 128 біт і дає геш розміром 128 біт. Методи стискання двоблокової довжини утворюють геші з розміром вдвічі більшим за розмір блоку блочного шифру. Таким чином 128-бітний шифр може перетворитися в 256-бітну геш-функцію.
Ці методи потім використовуються в будові Меркле — Демґарда і їх детальніше розглядають нижче.
Цей розділ потребує доповнення. (жовтень 2018) |
Структура Девіса-Мейєра
В даній схемі блок повідомлення і попереднє значення геш-функції надходять в якості ключа й блоку відкритого тексту відповідно на вхід блочного шифру . Одержаний в результаті шифрування блок закритого тексту підсумовується (операція XOR) з результатом попередньої ітерації гешування () для отримання наступного значення геш-функції ().
В математичних позначеннях схему Девіса-Мейєра можна записати як:
Якщо блоковий шифр використовує, наприклад, 256-бітний ключ, то кожен блок повідомлень () являє собою 256-бітний фрагмент повідомлення. Якщо ж блоковий шифр використовує розмір блоку в 128 біт, то вхідні й вихідні значення хеш-функції в кожному раунді становлять 128 біт.
Важливою властивістю конструкції Девіса-Мейєра є те, що навіть якщо базовий блок шифрування є повністю безпечним, можна обчислити нерухомі точки для побудови: для будь-якого можна знайти значення таке що : просто нужно установить .
Безпека структури Девіса-Мейєра була вперше доведена Р.Вінтерніцом.
Структура Матіса-Мейєра-Осеаса
Це версія схеми Девіса-Мейєра: блоки повідомлення застосовуються як ключі криптосистеми. Схема може бути використана, якщо блоки даних і ключ шифрування мають один і той же розмір. Наприклад, AES добре підходить для цієї мети.
У даній конструкції блок повідомлення і попереднє значення хеш-функції надходять в якості ключа й блоку відкритого тексту відповідно на вхід блочного шифру . Але вже значення піддається попередній обробці відповідно до розділу через можливі відмінності в розмірах геш-суми й розмірі ключа шифру . Ця функція реалізує відображення n-бітного значення хеш-функції в k-бітний ключ шифру . В результаті застосування операції шифрування, виходить блок закритого тексту, який підсумовується з відповідним йому блоком відкритого тексту ().
Див. також
Література
- Menezes, A. J; Van Oorschot, Paul C; Vanstone, Scott A (2001). Handbook of applied cryptography. Boca Raton, Fla.; London: CRC. ISBN .
- Брюс Шнайер Прикладная криптография, 2006, 2-e изд.
- В. В. Ященко Введение в криптографию, 1999
- С.Баричев, Р.Серов Основы современной криптографии, 2001
- С. В. Дубров Основы современной криптографии
- R. Winternitz A secure one-way hash function built from DES
- УДОСКОНАЛЕНА ФУНКЦІЯ ГЕШУВАННЯ MD4
Наукові стаття
- Авезова Яна Эдуардовна СОВРЕМЕННЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ ХЭШ-ФУНКЦИЙ НА ПРИМЕРЕ ФИНАЛИСТОВ КОНКУРСА SHA-3
- А. В. Антонов РАЗВИТИЕ МЕТОДА ПОСТРОЕНИЯ ХЕШ-ФУНКЦИИ
Примітки
- Menezes, Van Oorschot та Vanstone, 2001, с. 328.
- Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 416–427. Springer, 1989.
- Ralph Merkle. One way hash functions and DES. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 428–446. Springer, 1989.
- John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2n work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.
- Авезова Яна Едуардівна, 2015, с. 61.
- Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing та August 2001, с. 375.
- R. Winternitz. A secure one-way hash function built from DES. In Proceedings of the IEEE Symposium on Information Security and Privacy, 1984, с. 88—90.
- Авезова Яна Едуардівна, 2015, с. 61—62.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V kriptografiyi odnostoronnya funkciya stisnennya ce taka funkciya yaka peretvoryuye dva vhidni argumenti fiksovanoyi dovzhini na rezultat fiksovanoyi dovzhini Funkciya odnostoronnya v tomu sensi sho vazhko vgadati argumenti znachennya funkciyi dlya yakih dorivnyuye zadanij velichini Odnostoronni funkciyi stisnennya ne pov yazani zi zvichnimi algoritmami stisnennya danih yaki natomist mozhut buti obernenimi tochno stisnennya bez vtrat abo priblizno stisnennya z vtratami Odnostoronnya funkciya stisnennya Odnostoronnya funkciya stisnennya vikoristovuyetsya napriklad v strukturi Merkla Demgardaa vseredini kriptografichnih gesh funkcij Odnostoronni funkciyi stisnennya chasto buduyutsya z blochnih shifriv Dlya togo shob peretvoriti bud yakij zvichajnij blochnij shifr v odnostoronnyu funkciyu stisnennya isnuyut metodi Devisa Mejyera Matisa Mejera Oseasa Miaguchi Prenelya funkciyi stisnennya odnoblokovoyi dovzhini ta MDC 2 Meyera Shillinga MDC 4 Hirose dovzhini dva bloki Ci metodi dokladno opisani nizhche en takozh nazva hesh funkcih zapatentovanoyi IBM StisnennyaFunkciya stisnennya zmishuye dva argumenti fiksovanoyi dovzhini i povertaye odin rezultat fiksovanoyi dovzhini rozmir yakogo dorivnyuye rozmiru odnogo z argumentiv Na ce takozh mozhna divitis yak na funkciyu yaka peretvoryuye odin velikij argument fiksovanoyi dovzhini na korotshij rezultat fiksovanoyi dovzhini Napriklad haj argument A maye dovzhinu v 128 bit argument B tezh 128 bit i voni stiskuyutsya v odin rezultat dovzhini 128 bit Ce te zh same yaksho b odin yedinij 256 bitovij argument stiskuvavsya v 128 bitnij rezultat Deyaki funkciyi stisnennya ne stiskuyut vdvichi a z yakimos inshim koeficiyentom Napriklad argument A mozhe buti 256 bitovim a argument B 128 bitovim i voni mozhut stiskatisya v 128 bit Tobto v cilomu 384 vhidnih bitiv stiskayutsya razom do 128 vihidnih bitiv Zmishuvannya vikonuyetsya takim chinom shob dosyagti povnogo lavinovogo efektu koli kozhen vihidnij bit zalezhit vid kozhnogo vhidnogo bita OdnostoronnistDokladnishe Odnostoronnya funkciya Odnostoronnya funkciya ce funkciya yaku legko obchisliti ale vazhko obchisliti obernenu do neyi Odnostoronnya funkciya stisnennya yaku takozh nazivayut gesh funkciyeyu povinna mati nastupni vlastivosti Legko obchisliti Yaksho vidomi argumenti legko otrimati rezultat Stijkist do proobrazu Yaksho zlovmisnik znaye lishe vihidni dani dlya nogo bude nerealno obchisliti vhidni Inshimi slovami dlya rezultatu funkciyi h nemozhlivo obchisliti m take sho hash m h Stijkist do drugogo proobrazu Mayuchi vhidni dani m1 vihidnimi dlya yakih ye h treba shob znajti inshe znachennya m2 na vihodi dlya yakogo tezh bulo h tobto hash m1 hash m2 en Treba shob znajti dva taki rizni argumenti dlya yakih funkciya daye odnakovij rezultat bulo vazhko tobto zlovmisnik ne povinen mogti znajti paru povidomlen m1 m2 takih sho hash m1 hash m2 Cherez paradoks dniv narodzhennya div takozh ataka dniv narodzhennya isnuye 50 jmovirnist znajti koliziyu za chas priblizno 2n 2 de n kilkist bit u vihodi gesh funkciyi Takim chinom ataka na gesh funkciyu ne povinna znahoditi koliziyu za mensh nizh 2n 2 sprob V ideali pid nemozhlivistyu v stijkosti do proobrazu i drugogo proobrazu slid rozumiti obchislyuvalnu skladnist priblizno 2n de n kilkist bit u vihodi funkciyi Prote osoblivo dlya vipadku stijkosti do drugogo proobrazu ce dosit skladna problema dzherelo Budova Merkle DemgardaDokladnishe Budova Merkla Demgarda Budova Merkla Damgarda de IV pochatkove znachennya zgortki fiksovanij vektor f funkciya stiskannya Tipovim zastosuvannyam odnostoronnih funkcij stiskannya ye yih vikoristannya v budovi Merkle Demgarda vseredini kriptografichnih gesh funkcij Populyarni gesh funkciyi taki napriklad yak MD5 SHA 1 i SHA 2 vikoristovuyut cyu budovu Gesh funkciya povinna buti zdatnoyu peretvoriti povidomlennya dovilnoyi dovzhini u rezultat fiksovanoyi dovzhini Cogo mozhna dosyagti rozbivayuchi vvid na poslidovnist blokiv odnakovoyi dovzhini i opracovuyuchi yih poslidovno vikoristovuyuchi odnostoronnyu funkciyu stiskannya Funkciya stiskannya povinna buti abo skonstrujovana specialno dlya geshuvannya abo pobudovana z blochnogo shifru Ostannij blok povinen buti en Koli zastosovuyetsya dopovnennya za dovzhinoyu yake takozh nazivayut MD posilennya angl MD strengthening ataki ne zdatni znajti koliziyi shvidshe za chas paradoksu dniv narodzhennya 2n 2 de n rozmir bloku v bitah yaksho vikoristana funkciya f stijka do kolizij Takim chinom Budova Merkla Demgardat zvodit zadachu znahodzhennya pravilnoyi gesh funkciyi do znahodzhennya funkciyi stiskannya Ataka znahodzhennya drugogo proobrazu mayuchi povidomlennya m1 zlovmisnik znahodit inshe povidomlennya m2 take sho hash m1 hash m2 mozhliva zgidno Kelsi ta Shnayerom dlya 2k blokovogo povidomlennya za chas k 2n 2 1 2n k 1 Skladnist bilsha za 2n 2 ale nizhcha za 2n pri dovgih povidomlennyah i dlya korotkih povidomlen nablizhayetsya do 2n Pobudova z blochnih shifrivTipovij suchasnij blochnij shifr Takozh odnostoronni funkciyi stiskannya buduyut z blochnih shifriv Blochni shifri yak i odnostoronni funkciyi stiskannya otrimuyut na vhid dvi poslidovnosti fiksovanoyi dovzhini klyuch i vidkritij tekst i povertayut odnu vihidnu poslidovnist shifrotekst yaka maye taku samu dovzhinu yak i vhidnij vidkritij tekst Prote suchasni blochni shifri lishe chastkovo odnostoronni Tobto mayuchi vidkritij tekst i shifrotekst nerealno znajti klyuch sho peretvoryuye vidkritij tekst v shifrotekst Ale mayuchi shifrotekst i klyuch znajti vidkritij tekst mozhna prosto vikoristavshi funkciyu deshifruvannya blochnogo shifru Tomu shob peretvoriti blochnij shifr v odnostoronnyu funkciyu stiskannya potribni deyaki dodatkovi operaciyi Deyakimi metodami dlya peretvorennya zvichajnogo blochnogo shifru v odnostoronnyu funkciyu stiskannya ye metodi Devisa Meyera Matiasa Meyera Oseasa Miyaguchi Prenelya funkciyi stiskannya odnoblokovoyi dovzhini ta MDC 2 MDC 4 Hiroshi funkciyi stiskannya dvoblokovoyi dovzhini Funkciyi stiskannya odnoblokovoyi dovzhini vivodyat skilki zh bit skilki obroblyayetsya vikoristanim blochnim shifrom Vidpovidno funkciyi stiskannya dvoblokovoyi dovzhini vivodyat vdvichi bilshe bit Yaksho blochnij shifr maye en napriklad 128 bit metodi odnoblokovoyi dovzhini stvoryuyut gesh funkciyu yaka maye rozmir bloku 128 bit i daye gesh rozmirom 128 bit Metodi stiskannya dvoblokovoyi dovzhini utvoryuyut geshi z rozmirom vdvichi bilshim za rozmir bloku blochnogo shifru Takim chinom 128 bitnij shifr mozhe peretvoritisya v 256 bitnu gesh funkciyu Ci metodi potim vikoristovuyutsya v budovi Merkle Demgarda i yih detalnishe rozglyadayut nizhche Cej rozdil potrebuye dopovnennya zhovten 2018 Struktura Devisa MejyeraShema Devisa Mejyera V danij shemi blok povidomlennya mi displaystyle m i i poperednye znachennya gesh funkciyi Hi 1 displaystyle H i 1 nadhodyat v yakosti klyucha j bloku vidkritogo tekstu vidpovidno na vhid blochnogo shifru E displaystyle E Oderzhanij v rezultati shifruvannya blok zakritogo tekstu pidsumovuyetsya operaciya XOR z rezultatom poperednoyi iteraciyi geshuvannya Hi 1 displaystyle H i 1 dlya otrimannya nastupnogo znachennya gesh funkciyi Hi displaystyle H i V matematichnih poznachennyah shemu Devisa Mejyera mozhna zapisati yak Hi Emi Hi 1 Hi 1 displaystyle H i E m i H i 1 oplus H i 1 Yaksho blokovij shifr vikoristovuye napriklad 256 bitnij klyuch to kozhen blok povidomlen mi displaystyle m i yavlyaye soboyu 256 bitnij fragment povidomlennya Yaksho zh blokovij shifr vikoristovuye rozmir bloku v 128 bit to vhidni j vihidni znachennya hesh funkciyi v kozhnomu raundi stanovlyat 128 bit Vazhlivoyu vlastivistyu konstrukciyi Devisa Mejyera ye te sho navit yaksho bazovij blok shifruvannya ye povnistyu bezpechnim mozhna obchisliti neruhomi tochki dlya pobudovi dlya bud yakogo m displaystyle m mozhna znajti znachennya h displaystyle h take sho Em h h h displaystyle E m h oplus h h prosto nuzhno ustanovit h Em 1 0 displaystyle h E m 1 0 Bezpeka strukturi Devisa Mejyera bula vpershe dovedena R Vinternicom Struktura Matisa Mejyera OseasaShema Matisa Mejyeyera Oseasa Ce versiya shemi Devisa Mejyera bloki povidomlennya zastosovuyutsya yak klyuchi kriptosistemi Shema mozhe buti vikoristana yaksho bloki danih i klyuch shifruvannya mayut odin i toj zhe rozmir Napriklad AES dobre pidhodit dlya ciyeyi meti U danij konstrukciyi blok povidomlennya mi displaystyle m i i poperednye znachennya hesh funkciyi Hi 1 displaystyle H i 1 nadhodyat v yakosti klyucha j bloku vidkritogo tekstu vidpovidno na vhid blochnogo shifru E displaystyle E Ale vzhe znachennya Hi 1 displaystyle H i 1 piddayetsya poperednij obrobci vidpovidno do rozdilu g displaystyle g cherez mozhlivi vidminnosti v rozmirah gesh sumi j rozmiri klyucha shifru E displaystyle E Cya funkciya realizuye vidobrazhennya n bitnogo znachennya hesh funkciyi v k bitnij klyuch shifru E displaystyle E V rezultati zastosuvannya operaciyi shifruvannya vihodit blok zakritogo tekstu yakij pidsumovuyetsya z vidpovidnim jomu blokom vidkritogo tekstu mi displaystyle m i Hi Eg Hi 1 mi Hi 1 mi displaystyle H i E g H i 1 m i oplus H i 1 oplus m i Div takozhWhirlpool kriptografiya Blochnij shifrLiteraturaMenezes A J Van Oorschot Paul C Vanstone Scott A 2001 Handbook of applied cryptography Boca Raton Fla London CRC ISBN 978 0 8493 8523 0 Bryus Shnajer Prikladnaya kriptografiya 2006 2 e izd V V Yashenko Vvedenie v kriptografiyu 1999 S Barichev R Serov Osnovy sovremennoj kriptografii 2001 S V Dubrov Osnovy sovremennoj kriptografii R Winternitz A secure one way hash function built from DES UDOSKONALENA FUNKCIYa GEShUVANNYa MD4Naukovi stattya Avezova Yana Eduardovna SOVREMENNYE PODHODY K POSTROENIYu HESh FUNKCIJ NA PRIMERE FINALISTOV KONKURSA SHA 3 A V Antonov RAZVITIE METODA POSTROENIYa HESh FUNKCIIPrimitkiMenezes Van Oorschot ta Vanstone 2001 s 328 Ivan Damgard A design principle for hash functions In Gilles Brassard editor CRYPTO volume 435 of LNCS pages 416 427 Springer 1989 Ralph Merkle One way hash functions and DES In Gilles Brassard editor CRYPTO volume 435 of LNCS pages 428 446 Springer 1989 John Kelsey and Bruce Schneier Second preimages on n bit hash functions for much less than 2n work In Ronald Cramer editor EUROCRYPT volume 3494 of LNCS pages 474 490 Springer 2005 Avezova Yana Eduardivna 2015 s 61 Handbook of Applied Cryptography by Alfred J Menezes Paul C van Oorschot Scott A Vanstone Fifth Printing ta August 2001 s 375 R Winternitz A secure one way hash function built from DES In Proceedings of the IEEE Symposium on Information Security and Privacy 1984 s 88 90 Avezova Yana Eduardivna 2015 s 61 62