Приветствую жителей Хабра!

Итак, новые «криптографические игрища» пришли по мою душу. Поэтому сегодня поговорим о занудном упражнении, ориентированном на полный перебор паролей, реализации тривиального многопоточного брутера силами C++ и OpenMP, а также кратко об использовании криптобиблиотеки CryptoPP и стороннего модуля fastpbkdf2 (для Си и Плюсов) в своих проектах.

Го под кат, печеньки out there!


ДИСКЛЕЙМЕР. Перебирать чужие пароли нельзя, читать тексты, адресованные не вам, нельзя, создавать и распространять вредоносное ПО с целью неправомерного доступа к компьютерной информации нельзя. Наказуемо согласно УК РФ. Dixi.

Разбор условия

Вещественная обёртка задачи представляет из себя небольшую карточку со следующим текстом:

SGFzaGVkU2FsdCg4Ynl0ZXNJblVURjE2TEUpQ291bnRlckNpcGhlcnRleHRB
RVMyNTZFQ0J8MWE0MDhhYTVhZjkzMDkxOGRkYjkyNzQ3NDBhMDJjMmJkM2Vl
N2NkNjU3MDQwMDAwMDQxN2E2Nzc4Yzc3YzYwZjcxMGJlNTNiNmViODQ0ZDg0
MmUwZWEwZGYwNDA2NTU4NWEzMzIzYTUwZjc2OGY1N3xQb3NzaWJsZVBhc3N3
b3JkUGF0dGVybnN8RERMTExMTEx8RExMTExMTER8TExMRERMTEx8TExMTExM
REQ=

Зачем в Base64? Преподавателем на это было отвечено: «Чтобы варианты условий не повадно выбирать было». Не очень-то и хотелось. Также на словах была передана информация об используемом алгоритме преобразования пароля в ключ (PBKDF2_HMAC_SHA1) и сформулированы простые условия игры: «Подобрать пароль для восстановления сообщения, зашифрованного блочным шифром. Пароль не словарный, может состоять из цифр и маленьких букв латинского алфавита, соль — только из маленьких букв». Давайте посмотрим, что скрывает кодировка:

HashedSalt(8bytesInUTF16LE)CounterCiphertextAES256ECB|1a408a
a5af930918ddb9274740a02c2bd3ee7cd6570400000417a6778c77c60f71
0be53b6eb844d842e0ea0df04065585a3323a50f768f57|PossiblePassw
ordPatterns|DDLLLLLL|DLLLLLLD|LLLDDLLL|LLLLLLDD

Что мы видим? Первая часть сообщения (до первого вертикального слэша), вероятно, представляет из себя порядок следования данных, непосредственно указанных во второй части: хеш значение соли (с информацией о кодировке в скобках), счетчик итераций для PBKDF2, используемый блочный шифр и режим шифрования. AES добрался до меня и здесь, кто бы мог подумать... Третья часть и до конца — потенциальные маски нужного пароля, где L — буква (letter), D — цифра (digit). Также определено, что пароль состоит из 8-ми символов. Вроде звучит логично, теперь было бы неплохо структурировать полученную информацию.

Проанализируем второй блок сообщения. В задании нет информации об используемой функции хеширования соли, поэтому сделаем предположение, что это SHA1, т. к. это единственная широко используемая криптографическая хеш-функция с длиной выхода 20 байт (только этот размер идеально ложится под остальное разбиение). Также, очевидно, что счетчик представлен в little endian, по крайней мере очень хочется так думать, ибо 0x57040000 = 1459879936 итераций PBKDF2 — не самая лучшая перспектива для перебора… И, наконец, остается два блока AES по 16 байт каждый. Следовательно, имеем такую картину:

1A408AA5AF930918DDB9274740A02C2BD3EE7CD6 — хеш соли (20 байт);
0x00000457 = 1111 — счетчик итераций PBKDF2;
0417a6778c77c60f710be53b6eb844d8 — первый блок шифртекста (16 байт);
42e0ea0df04065585a3323a50f768f57 — второй блок шифртекста (16 байт).

Восстановление соли

Окей, для начала напишем быдлобыстро-скрипт для восстановления соли. Благо, 4 символа (aka 8 байт в UTF16) переберутся за секунды, поэтому воспользуемся пайтоном, не мудрствуя лукаво:

# Run: python3 crack_salt_hash.py

from hashlib import sha1
from itertools import product

ALPH = 'abcdefghijklmnopqrstuvwxyz'
SIZE = 4
TOTAL = len(ALPH)**SIZE

def crack_hash(func, output, enc):
  progress = 0
  for salt in product( *([ALPH]*SIZE) ):
    if func(''.join(salt).encode(encoding=enc)).hexdigest() == output:
      print(progress+1, 'of', TOTAL)
      return ''.join(salt)
    progress += 1
    if progress % 10000 == 0:
      print(progress, 'of', TOTAL)
  return None

if __name__ == '__main__':
  print(crack_hash(sha1, '1a408aa5af930918ddb9274740a02c2bd3ee7cd6', 'UTF-16LE'))

По прошествии 3-х секунд, имеем результат: "dukg". С учетом 2-байтовой кодировки конечная форма соли (пригодная для ввода в PBKDF2) будет иметь вид "d\x00u\x00k\x00g\x00".

Криптографические нужды

Теперь предстоит выбрать инструменты для работы с криптографией. По порядку: сперва подумаем о получении ключа из пароля, затем о расшифровании сообщения. Для решения обоих вопросов сразу на ум приходят два возможных варианта: OpenSSL либо Crypto++ (он же CryptoPP). Оба пакета широко известны и с ними нетрудно работать на C++ (выбор языка пришел сам собой исходя необходимости высокой скорость перебора).

Генерация ключей

Забегая немного вперед, стоит сказать, что стандартная функция PKCS5_PBKDF2_HMAC_SHA1 из OpenSSL при заданном счетчике в 1111 итераций показала среднюю скорость в 1000 ключей/с при параллельной работе на 4-ядерном Intel Core i5 2.60GHz. Не самый лучший результат, посему было решено поискать альтернативное «прокаченное» решения для генерации ключей. Таким решением стала библиотека fastpbkdf2 от стороннего разработчика. Библиотека основана на том же OpenSSL (реализации самих хеш-функций оттуда), однако использует «различные оптимизации во внутреннем цикле for» при высчитывании PBKDF2. Такое описание меня вполне устраивает, к тому же производительность возросла примерно в 3,45 раза: теперь перебор идет со скоростью в 3450 паролей/с.

Модуль написан на Си и требует компилятор, поддерживающий C99, поэтому для встраивания его (модуля) в проект на Плюсах, скомпилируем из исходников и создадим динамическую библиотеку как:

$ gcc fastpbkdf2.c -fPIC -std=c99 -O3 -c -g -Wall -Werror -o fastpbkdf2.o
$ gcc -shared -lcrypto -o libfastpbkdf2.so fastpbkdf2.o

И теперь для запуска конечного брутера (который мы пока не написали, но уже придумали для него оригинальное название — "bruter.cxx"), нужно будет скормить ему сию библиотеку, написав:

$ g++ bruter.cxx -o bruter -L"/path/to/libfastpbkdf2.so" -Wl,-rpath="/path/to/libfastpbkdf2.so" -lfastpbkdf2

В конце добавим Makefile для автоматизации. Прикинем теперь, как будет происходить проверка валидности пароля:

bool checkPassword(uint8_t* password, const uint8_t* ciphertext, uint8_t* decrypted, int& decryptedLength) {
  uint8_t key[KEY_LENGTH];
  fastpbkdf2_hmac_sha1(password, PASSWORD_LENGTH, salt, SALT_LENGTH, iterations, key, KEY_LENGTH);

  decryptedLength = CryptoPP_Decrypt_AES_256_ECB(ciphertext, (uint8_t*) key, decrypted);

  if (isPrintable(decrypted, decryptedLength))
    return true;

  return false;
}

где CryptoPP_Decrypt_AES_256_ECB — не написанная еще функция расшифрования. Возвращаемое значение — истина/ложь, в зависимости от исхода проверки критерия. Критерий же верного декрипта — печатаемость всех символов открытого текста, оценка критерия лежит на функции isPrintable (см. полный листинг в Заключении).

Расшифрование сообщения

Для расшифрования сообщения обратимся за помощью к библиотеки Crypto++.

Следуя порядку работы с блочными шифрами в рамках данного пакета, выполним следующие действия: создадим функциональный объект для расшифрования AES в режиме ECB (decryptor), инициализируем его ключом (размер ключа определяет версию AES — в нашем случае AES-256), назначим выходной буфер и выполним операцию преобразования шифртекста в открытый текст по алгоритму, который содержит decryptor. Также мы предполагаем, что добивание блока (PADDING) не использовалось вовсе, ибо условие умалчивает о формате добивания. Следовательно, длина исходного сообщение должна быть кратной длине одного блока AES.

int CryptoPP_Decrypt_AES_256_ECB(const uint8_t* ciphertext, uint8_t* key, uint8_t* plaintext) {
  ECB_Mode<AES>::Decryption decryptor;
  decryptor.SetKey(key, AES::MAX_KEYLENGTH);
  ArraySink ps(&plaintext[0], PLAINTEXT_LENGTH);

  ArraySource(ciphertext,
              CIPHERTEXT_LENGTH,
              true,
              new StreamTransformationFilter(decryptor,
                                             new Redirector(ps),
                                             StreamTransformationFilter::NO_PADDING));
	
  return ps.TotalPutLength();
}

Возвращать функция будет длину дешифрованного сообщения.

Новая информация

Пока в течении дня возился с подготовительными работами, описанными выше, на почту прилетело письмо от автора, в котором сообщалось, что «всплыла новая информация, касательно структуры пароля». В общих словах сообщалось, что при создании пароля пользователь по ошибке зажал Shift при вводе единицы и буквы "q". Перефразируя сообщение, получим символ "!" (на месте цифры) и букву "Q" (на месте буквы), как гарантированные составляющие пароля. Для пользователя новость не самая лучшая, но для нас просто замечательная: это подразумевает существенное сужение области перебора. Численную оценку преимущества, которое так удачно было получено, проведем чуть позже, когда будем оценивать время, необходимое на полный перебор.

Параллельный брутер

Дело за малым: остается написать управляющую функцию и ввести элемент многопоточности. Для распараллеливания вычислений будем использовать прагмы OpenMP. Общее количество паролей для перебора — известная величина. Для примера рассмотрим одну из четырех моделей паролей (с учетом того, что одна из цифр — на самом деле "!", а одна из букв — «Q»):

$$

$$

Первые две скобки — количество размещений с повторениями из 26 по 5 и из 10 по 1 соответственно (5 букв и 1 цифра), множители в третьих скобках — перестановка "!" (может стоять на двух позициях) и перестановка «Q» (может стоять на шести позициях). Полную область перебора определим, домножив результат на 4, получая $$ или 5,7 млрд.

Так как границы области определены, для выработки паролей воспользуемся вложенными циклами for и прагмой omp parallel for с параметром collapse() для «схлопывания» множественных петель в одну большую. Нужно помнить, что для того, чтобы пользоваться collapse(), необходимо поддерживать «идеальную вложенность» циклов. Это означает, что каждый следующий цикл (кроме последнего, разумеется) содержит в себе только очередную инструкцию for, а все операции выполняются в последнем по вложенности цикле.

Также, перед тем, как приступать к написанию кода, обратим внимание на интересную особенность: каждая следующая модель пароля является циклическим сдвигом на 1 или 3 позиции другой модели. Приняв это к сведению, мы сможем проще организовать перебор паролей из каждой модели за одну итерацию цикла:

void Parallel_TotalBruteForce(uint8_t* goodPassword, uint8_t* goodDecrypted, int& goodDecryptedLength) {

  uint8_t alp[27] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z', '\0' };
  uint8_t num[11] = { '0','1','2','3','4','5','6','7','8','9', '\0' };

#ifdef WITH_OPENMP
  omp_set_num_threads(myOMP_THREADS);
#endif

  uint64_t progress = 0;
  bool notFinished = true;

  #pragma omp parallel for shared(progress, notFinished) collapse(8)
  for (int a = 0; a  < 2; a++)
  for (int b = 2; b  < 8; b++)
  for (int c = 0; c < 26; c++)
  for (int d = 0; d < 26; d++)
  for (int e = 0; e < 26; e++)
  for (int f = 0; f < 26; f++)
  for (int g = 0; g < 26; g++)
  for (int h = 0; h < 10; h++) {
    if (notFinished) {
      uint8_t password[9]; password[PASSWORD_LENGTH] = '\0';
      uint8_t indeces[6] = { 2,3,4,5,6,7 };
      memmove(indeces+b, indeces+b+1, 5-b);
      uint8_t decrypted[100]; int decryptedLength;

      password[         a] =    '!';  // 0-1
      password[        !a] = num[h];  // 0-1
      password[         b] =    'Q';  // 2-7
      password[indeces[0]] = alp[c];  // 2-7
      password[indeces[1]] = alp[d];  // 2-7
      password[indeces[2]] = alp[e];  // 2-7
      password[indeces[3]] = alp[f];  // 2-7
      password[indeces[4]] = alp[g];  // 2-7

      if (
      // DDLLLLLL
      checkPassword(password, ciphertext, decrypted, decryptedLength) ||
      // DLLLLLLD      
      checkPassword(rotateLeftOneChar(password), ciphertext, decrypted, decryptedLength) ||
      // LLLLLLDD
      checkPassword(rotateLeftOneChar(password), ciphertext, decrypted, decryptedLength) ||
      // LLLDDLLL
      checkPassword(rotateLeftThreeChars(password), ciphertext, decrypted, decryptedLength)
    ) {
        #pragma omp critical
        {
          memcpy(goodPassword, password, 9);
          memcpy(goodDecrypted, decrypted, decryptedLength);
          goodDecryptedLength = decryptedLength;
          notFinished = false;
        }
      }

      if (progress % PROGRESS_SEP == 0)
        cout << progress << " of " << TOTAL << endl;
      progress += STEP;
    }
  }
}

Флаг notFinished используется для выхода из for. Такой подход более свойственен для работы с pthread напрямую, в OpenMP для этого есть #pragma omp cancel, однако меня компилятор засыпал предупреждениями, природа которых мне не до конца ясна, поэтому было решено использовать флаг.

Теперь посмотрим на производительность полученной системы и оценим время, необходимое на полный перебор.

Оценка производительности и поиск бо?льших мощностей

Как уже говорилось выше, при параллельной работе на 4-ядерном Intel Core i5 2.60GHz была достигнута скорость, примерно равная 3450 паролей/с. Всего 5,7 млрд. паролей, отсюда нехитрые вычисления дают оценку в 19 дней работы машины при условии, что нужный нам пароль окажется последним из всего множества. Не лучшая перспектива.

Самое время для маленького читерства. Воспользуемся небезызвестным сервисом облачных вычислений Amazon EC2. Выберем инстанс для вычислений с ЦПУ-преимуществом (характеристики приведены на скриншоте ниже) и посмотрим производительность.



Подняв количество потоков с 4 до 36 (+ более шустрые серверные процы), получили прирост в скорости аж в 10 раз даже несмотря на замедление работы сервиса из-за недавнего наката анти-Meltdown патчей. Подняв два инстанса таких виртуалок по спотовой цене в $0,37/ч получим возможность перебрать все множество за 24 часа, выложив при этом $17,76 (или около 1 тыс. руб. по текущему состоянию курса). Недешевое удовольствие для учебной задачки, но спортивный интерес все же победил, поэтому готов поделиться результатами.

Но прежде посмотрим ради интереса, сколько бы времени потребовалось, если бы «неожиданно не всплыла» дополнительная информация об ошибках пользователя при вводе. В этом случае мощность общего множества паролей записывалась бы как:

$$

Следовательно, для полного перебора на скорости 3450 п/с ушло бы больше года при использовании ЭВМ на процессоре, указанном в начале раздела [из цикла «Ужасы нашего Городка»].

Результаты

Восстановленный пароль: "ldQ9!nwd".
Открытый текст: 2E2B2A602A2B2C20594F552044495341524D4544204D4521202C2B2A602A2B2E.
Сообщение: ".+*`*+, YOU DISARMED ME! ,+*`*+.".

Декрипт был получен чуть больше чем за 1/2 суток. При используемом подходе со сдвигами одной модели пароля относительно других получилась такая картина: успешной оказалась та итерация, когда первой сгенерировалась комбинация "9!nwdldQ" (из модели $$), и после трех циклических сдвигов влево на проверку ушел нужный пароль.

Заключение, исходные коды

Новый год ознаменовался достаточно необычным для меня опытом, благодарность автору за сбалансированную игру ;)

Полный код брутера под спойлером:


Код мейкфайла, как обещано, под вторым спойлером:


Спасибо за внимание, всем добра!