Ктн, доцент Василенко В.С.

Національний авіаційний університет (НАУ) України

Геш-функції та цілісність інформаційних об’єктів

Високі надійність, ефективність й технологічність телекомунікаційних мереж (ТКМ) є можливими тільки за умови надійного та ефективного захисту конфіденційності, цілісності та доступності інформаційних об’єктів телекомунікаційних мереж. Залежно від умов застосування, складності та класу ТКМ, а також характеристик можливих загроз, вага цих функціональних властивостей може змінюватись, але проблеми забезпечення цілісності інформації є одними з основних при розробці й впровадженні будь-яких захищених ТКМ. З цією метою або виключається доступ до первинної, відкритої інформації (задачі управління доступом) на усіх етапах її циркуляції в ТКМ, або використовуються обчислені і включені до складу інформаційних об’єктів геш-функції, так звані ознаки цілісності.

Контроль, а можливо і поновлення цілісності інформації в умовах впливу як природних, так і штучних (найчастіше цілеспрямованих) спотворень забезпечується шляхом порівняння початкових ознак цілісності (геш-функцій), що відповідають цим об’єктам, і ознак цілісності, сформованих для інформаційних об’єктів, цілісність яких контролюється наразі (вторинних ознак цілісності). При цьому вторинні ознаки цілісності інформаційних об’єктів, цілісність яких контролюється, обчислюються за тими ж механізмами, що і початкові. У разі їх збігу робиться висновок про відсутність порушень цілісності [1−4].

Нехай передаванню чи збереженню підлягає деякий інформаційний об’єкт А, інформаційна довжина якого не перевищує m розрядів. Необхідно забезпечити його цілісність. Із цією метою із використанням механізмів хешування здійснюється розрахунок потрібних надлишкових символів, наприклад, ознаки цілісності (геш-функції) − h(А) цього об’єкту. Інформаційний об’єкт та його ознака цілісності зберігаються чи передаються єдиним блоком у вигляді конкатенації (у цьому виразі позначка означає конкатенацію А та ).

Якщо потенційний порушник має намір порушити цілісність таких об’єктів, то для приховування порушення цілісності (модифікації) інформаційних об’єктів він має або сформувати нову ознаку цілісності (геш-функцію), яка відповідає модифікованій інформації, або здійснювати таку модифікацію, при якій ознака цілісності збігається з початковою (використати колізії геш-функцій).

Для запобігання підробки порушниками вторинних ознак цілісності необхідно або виключити доступ неавторизованих користувачів до інформації (задачі управління доступом, розгляд яких виходить за межі роботи), або авторизованим користувачам сформувати із використанням секретних ключів геш-функції, що мають мінімальну кількість (а краще – зовсім не мають) колізій. Для порушення цілісності порушник може використати колізії відповідних геш-функцій чи визначити ключі перетворення. Розгляд способів протистояння використанню колізій і є задачею цієї роботи.

Нагадаємо [1 − 4], що для розрахунку геш-функцій застосовується операція визначення лишку від ділення вихідного інформаційного об’єкту А (що розглядається як деяке число) на ключ p – застосування операцій визначення лишку числа А по модулю (ключу) p:

h(А) = , (1)

де позначка (див. рис. 1а та 1б) означає обчислення цілої частини від розподілу А на p.

Рис. 1. Геш-функції та їх колізії

Колізією геш-функцій h(х) і h(у) називається ситуація, коли два різних вхідних блоки даних х і у мають однакові геш-функції, тобто h(х) = h(у):

h(х) = ; h(у) = .

Наприклад, при , , … (рис. 1в, 1г). Неважко зрозуміти, що колізії геш-функцій виду (1) існують, коли вхідні блоки х і у пов’язані співвідношенням:

, (2)

де k = 0, 1, 2, …, оскільки у цьому випадку:

h(у) = .

Тоді, виходячи із викладеного, слід зробити висновок, що в разі, коли будь-який вхідний блок даних А характеризується геш-функцією h(х), то числове значення цього блоку може бути визначеним як:

.

У цьому виразі − кількість колізій геш-функцій блоку даних А, при обраному значенні модуля − . Якщо ж такий блок даних представляється в деякому діапазоні , а колізії геш-функцій для такого блоку пов’язані співвідношенням (2), то максимальна кількість колізій цього блоку даних (рис. 1д) дорівнює .

Із викладеного неважко зробити висновок, що досвідчений порушник в разі необхідності порушити цілісність інформаційного об’єкту х може здійснити таку його модифікацію, яка залишиться непоміченою. З цією метою йому слід скористатися перетворенням х®у із використанням виразу (2). Кількість таких модифікацій ‒ уже визначена та дорівнює кількості можливих колізій . Отже для протистояння можливим порушенням цілісності інформаційних об’єктів кількість колізій слід зменшувати.

Зрозуміло, що для цього слід зменшувати величину , мінімальне значення якої досягається при . Дійсно, у цьому випадку співвідношення , а отже, . У цьому випадку, тобто при геш-функція виду (1) набуває значення:

h(А) = ,

результуючий об’єкт для зберігання чи передавання набуває вигляду:

,

тобто здійснюється дублювання первинного інформаційного блоку.

Таке дублювання іноді може мати сенс, але вкрай обмежено, по-перше, через велику надлишковість, що часто є неприпустимим. По-друге, такий спосіб при такому значення лише одного ключа перетворення ніякої конфіденційності навіть самої геш-функції не забезпечує. Це свідчить про те, що у цих умовах обчислення геш-функції, як в задачах контролю цілісності, так і, особливо, в задачах криптографічних перетворень, значною мірою втрачає сенс.

Таким чином, задача має протиріччя, яке полягає в тому, що для зменшення кількості колізій величину ключа (модуля за яким обчислюється геш-функція) слід обирати якомога більшою (аж до ), а отже, ключ слід мати один, а для забезпечення властивостей із криптографічної стійкості результатів гешування слід мати множину ключів.

Розв’язання цього протиріччя забезпечується шляхом утворення єдиного ключа перетворення у вигляді добутку його складових [7]:

.

Такий підхід є еквівалентним застосуванню до інформаційного об’єкта А декількох (n) перетворень (1). Але, на відміну від (1), відповідна сукупність ключів розглядається як один складний модуль (основа), який дорівнює добутку із набору n часткових основ . У наслідок цього одержується кількість лишків , яка є відповідною кількості основ , та зменшеною, відповідно, кількістю колізій: при та кількість колізій дорівнює нулю.

Тоді результуючий інформаційний блок може буди записаним у вигляді:

. (3)

При цьому згаданого дублювання первинного інформаційного блоку не відбувається, а оскільки в цьому випадку , то кількість колізій дорівнює нулю . Отже, такий підхід забезпечує надійний контроль цілісності інформаційних об’єктів.

Висновок. Запропонованій підхід за рахунок відсутності колізій забезпечує виконання вимог щодо надійного контролю цілісності інформаційних об’єктів.

Василенко В.С. Геш-функції та криптографічні перетворення. / Василенко В.С. // ISBN 978-966-8736-05-6, Матеріали Х міжнародної Науково – практичної конференції “Праці академічних наук − 2014” 30 серпня − 7 вересня 2014 р.” – Йоркшир, Англія: “Sсience and Education LTD”, 2014. –С. 26–29.