ВИКОРИСТАННЯ ГІБРИДУ CPU/GPU У КРИПТОГРАФІЧНИХ ВИСОКОПРОДУКТИВНИХ ОБЧИСЛЕННЯХ



В даному докладі розглянуто кластерні системи CPU/GPU, їх переваги і недоліки, їх використання у системах криптографічного злому. Демонструється один з зломщиків, що використовує таку структуру.

Ключові слова: CPU, GPU, паралельні обчислення, хмарні обчислення

СPU/GPU HYBRID CLUSTER USAGE IN CRYPTOGRAPHY HPC

RIPNEVSKY O.O. NTUU “KPI” student, Ukraine, Kyiv

This article describes CPU/GPU cluster systems, their advantages and disadvantages, usability in cryptography crack systems. Example of such system demonstrated further.

Keywords: CPU, GPU, parallel computing, cloud computing

1. Вступ

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

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

2.Кластери

Актуальним є використання гібридних кластерів, тобто тихщо складаються з декількох CPU, які працюють разом з декількома GPU. GPU дозволяють виконувати паралельні обчислювання, тому що більшість операцій підтримуються на рівні ядер. Це дозволяє отримувати максимальну обчислювальну потужність, через відсутність обробників команд, та більш практичне використання комп’ютерних ресурсів. Сьогодні використання таких технологій, як OpenGL або CUDA, дозволяє програмам працювати значно швидше, ніж на мультиядерних,чи навіть мультипроцесорних, системах.

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

Ці технології є дуже практичними у розв’язанні складних обчислювальних задач, що можуть бути поділені на багато незалежних частин. Конкретно ця особливість дозволяє подолати парадигму SPMD (одна і та сама програма, що має працювати з декількома одиницями даних).

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

3.Відновлення паролів

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

Деякі алгоритми хешування, такі як MD5, демонструють слабкі колізії: можна створити два повідомлення, які будуть мати однаковий хеш. Це, як правило, більш проста проблема, ніж так звана атака "знаходження прообразу" , де вхідне значення обчислюється на основі хешів до даного параметру.

Пароль можна розглядати як n символів (з можливим повторенням) з "набору символів" с., тому існує nc можливих паролів. В середньому потрібна буде лише їхня половина [3]. Збільшення або n або c підніме число комбінацій в геометричній прогресії, як показано нижче:

Табл. 1 Залежність кількості комбінацій від n та c

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

Швидкість перебору в 40 мільйонів хешів в секунду– цілком можливий результат для MD5 шифрування на помірно швидкій багатоядерній системі, проте використання перебору на важкому паролі займе дуже багато часу. Для звичайного пароля з 8 символів, вибраних зсимволів A-Za-Z0-9, ми маємо с = 62 іn = 8. Це займе в середньому 2,729,251 секунд, або трохи більше місяця, щоб відновити один хеш. Деякі системи, такі як MD5crypt або GPG шифрування файлів ОС Linux / FreeBSD, виконують кілька ітерацій хеш-функції (зазвичай>1000), щоб подолати можливість перебору - потенційно збільшуючи час відновлення для гіпотетичного паролю до 83 років [3].

Цю проблему можна розподілити шляхом розбиття простору пошуку між декількома системами. У теорії, лінійне масштабування може бути реалізоване через повну відсутність залежностей між блоками простору пошуку: 31 еквівалентний комп'ютер зможуть відновити MD5-хеш за один день, і шляхом додавання додаткових систем (або використання прискорення GPU), час відновлення потенційно може бути зменшено до декількох годин [4].

4. Оптимізація алгоритму длявикористання з GPU

4.1.Інструкція

Зниження загальної кількості інструкційу процедурі обробки завжди призводить до більш високої продуктивності. AMD GPU забезпечує деякі інструкції, що можуть бути використані для прискорення SHA1 реалізації.

Одним з них є інструкція BFI_INT. Тримакро-функції в блоці коду нижче генерують один і той же результат. F1 єосновним , виразом, що займає 4 інструкції.F2 також вираз, яке зменшує кількість інструкцій на 1. F3 використовує біт вибору функції в OpenCL, яка використовує інструкцію BFI_INT представлену AMD GPU і при цьому займає всього 1 інструкцію.

$#$define F1(b,c,d)((b&c)|(~b)&d)

$#$define F2(b,c,d) (d^(b&(c^d)))

$#$define F3(b,c,d) bitselect(d, c, b)

Ще одна інструкція що може бути використана, є rotate(). Хоча x86 підтримує rol(rotate left) інструкцію, C і багато інших мов програмування високого рівня не підтримують оператор rotate.Тому, як правило, на мові C реалізація rotate left 32-бітового цілого числа може бути виражена як (1) в наступному блоці коду.

$#$define ROTL(x, n)((x>(32-n)))

$#$define ROTL(x, n) rotate(x, n)

    1. Модифікація алгоритму

Так як SHA1 і MD5 мають чотири або п'ять різних нелінійних функцій для використання під час обробки одного блоку, він може очікувати декілька if застосувань для випадку, коли потрібно вибрати іншу не лінійну функції відносно декількох кроків, як показано в наступному прикладі псевдокоду.

//Головний цикл для SHA1

for i from 0 to 79

if 0 ≤ i ≤ 19 then

f = (b and c) or ((not b) and d)

k = 0x5A827999

else if 20 ≤ i ≤ 39

f = b xor c xor d

k = 0x6ED9EBA1

else if 40 ≤ i ≤ 59

f = (b and c) or (b and d) or (c and d)

k = 0x8F1BBCDC

else if 60 ≤ i ≤ 79

f = b xor c xor d

k = 0xCA62C1D6

temp = (a leftrotate 5) + f + e + k +w[i] e = d

d = c

c = b lefrotate 30

b = a

a = temp

end for

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

Іншим, що можна оптимізувати є значення регістру свопу. Як було показано в коді вище,в кожній ітерації значення A, B, C, D, E (SHA1) мінялися місцями. Замість заміни значення регістра, використовуючи п'ять 32-бітних інструкцій прив’язки, простою зміною регістру в коді можна досягти того ж ефекту.

Для SHA1, розгорнута версія є не найкращим варіантом для використання з GPU. Основна проблема полягає в різноманітності слів. Попередньо обчислюваний масив слів, який містить 80 32-розрядних цілі числа, має зберігатися в регістрах для підвищення продуктивності. Проте, регістри є обмеженим ресурсом для GPU. Використання такої кількості регістрів призведе до низької зайнятості і продуктивності. Таким чином, альтернативний метод обчислення SHA-1, запропонований в [5], має використовуватисяв GPU. Замість того щоб використовувати 80 регістрів, слова, що мають від 16 до 79 символів обчислюються під час роботи, щоб зберегти 64 регістри, як показано в наступній дій.

$#$define W(i) \

( \

s = i & 0x0f, \

W[s] = W[(s+13)&0x0f] ^ W[(s+8)&0x0f]^ W[(s+2)&0x0f] ^ W[(s)&0x0f],\

W[s] = rotate(W[s], 1) \

)

5.Висновок

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

Ці системи можуть бути швидко масштабованими і гарно використовують надані ресурси, тому їхній подальший розвиток є дуже важливим.

Література

  1. Karbowski, A. and Niewiadomska-Szynkiewicz,E. Parallel and distributed computing. Warsaw University of Technology Press,2009.– 458 с.

  2. Kunzman, D. M. andKalé, L. V. . Programming hetero-geneous clusters with accelerators usingobject-based programming, Scientific Programming Volume 19 (2011), Issue 1, 2011, с.47-62

  3. Scott Hauck andAndré DeHon. Reconfigurable Computing, 1st Edition,2007,с. 944

  4. Weidong Qiu, ZhengGong, GPU-Based High Performance Password Recovery Technique for HashFunctions,2016

  5. N. I.of Standards and Technology, “Secure hash standard (SHS),” http://csrc.nist.gov/publications/fips/fips180\-4/fips\-180\-4.pdf, 2012.
  • Рецензент: к.т.н., доц. каф. ОТ НТУУ "КПІ" А. М. Волокита
May 23, 2016