» » Сказ о тотальном переборе, или Томительное ожидание декрипта

 

Сказ о тотальном переборе, или Томительное ожидание декрипта

Автор: admin от 14-01-2018, 21:50, посмотрело: 170

Сказ о тотальном переборе, или Томительное ожидание декрипта Приветствую жителей Хабра!



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



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

даже не удивляюсь… Третья часть и до конца — потенциальные маски нужного пароля, где 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

alph = 'abcdefghijklmnopqrstuvwxyz'

def crack_hash(function, output, enc):
  progress = 0
  for a in range(26):
    for b in range(26):
      for c in range(26):
        for d in range(26):
          salt = alph[a] + alph[b] + alph[c] + alph[d]
            if function(''.join(salt).encode(encoding=enc)).hexdigest() == output:
              return salt
            progress += 1
            print(progress, 'of', 456976) # 26^4
  return None

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


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



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



Теперь предстоит выбрать инструменты для работы с криптографией. По порядку: сперва подумаем о получении ключа из пароля, затем о расшифровании сообщения. Для решения обоих вопросов сразу на ум приходят два возможных варианта: 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 -c -fPIC fastpbkdf2.c -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) и одну цифру (один раз 10), множители во вторых скобках — перестановка "!" (может стоять на двух позициях) и перестановка «Q» (может стоять на шести позициях). Полную область перебора определим, домножив результат на 4, получая Сказ о тотальном переборе, или Томительное ожидание декрипта или 57 млрд.



Так как границы области определены, для выработки паролей воспользуемся вложенными циклами 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', '' };
  uint8_t num[11] = { '0','1','2','3','4','5','6','7','8','9', '' };

#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] = '';
      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 паролей/с. Всего 57 млрд. паролей, отсюда нехитрые вычисления дают оценку в 19 дней работы машины при условии, что нужный нам пароль окажется последним из всего множества. Не лучшая перспектива.



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



Сказ о тотальном переборе, или Томительное ожидание декрипта




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



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

Сказ о тотальном переборе, или Томительное ожидание декрипта



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



Результаты



Восстановленный пароль: "ldQ9!nwd".

Открытый текст: 2E2B2A602A2B2C20594F552044495341524D4544204D4521202C2B2A602A2B2E.

Сообщение: ".+*`*+, YOU DISARMED ME! ,+*`*+.".



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



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



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



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



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



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

Источник: Хабрахабр

Категория: Программирование, Криптография

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *