LINUX.ORG.RU

Распараллеливание брутфорса с помощью OpenMP

 , ,


0

2

Пытаюсь ускорить процесс подбора ключа, но не понимаю, как правильно применить распараллеливание.

Прошу наставлений и помощи, так как знаний не хватает, а Си я вижу буквально 5-й день в жизни. Код следующий:

int brute ( u8 brute_key[0x10], char *target_dat, char *target_key )
{
  // (TODO) Не хочу читать одн и тот же кусок файла при каждом проходе:
  static u8 buffer_enc_default[0x40];   // Будет хранить оригинальное значение
  memset (buffer_enc_default, 0, 0x40); // Очистка выделенной памяти

  FILE *fp=fopen(target_dat,"rb");
  fseek(fp,0x40,SEEK_SET);
  fread(buffer_enc_default,1,0x40,fp);  // Чтение оригинального значения
  fclose(fp);

  static int i1,i2,i3,i4,i5,i6,i7,i8; // Перебор младших 8 байт (i = индекс)
  i1=i2=i3=i4=i5=i6=i7=i8=0;
  static int flag = TRUE; // Этот флаг позволит прыгнуть на стартовую позицию

  for(i1=0;i1<=0xFF;i1++){
    for(i2=0;i2<=0xFF;i2++){
      for(i3=0;i3<=0xFF;i3++){
        for(i4=0;i4<=0xFF;i4++){
          for(i5=0;i5<=0xFF;i5++){
            for(i6=0;i6<=0xFF;i6++){
              for(i7=0;i7<=0xFF;i7++){
                // #prigmi omp pirillel for // <=== FIXME
                for(i8=0;i8<=0xFF;i8++){

                  if(flag){ // Переход к стартовой позиции:
                    i1 = brute_key[0x08];
                    i2 = brute_key[0x09];
                    i3 = brute_key[0x0A];
                    i4 = brute_key[0x0B];
                    i5 = brute_key[0x0C];
                    i6 = brute_key[0x0D];
                    i7 = brute_key[0x0E];
                    i8 = brute_key[0x0F];
                    flag = FALSE;
                  }

                  // Перенос текущего позиции в brute_key:
                  brute_key[0x08] = (char)i1;
                  brute_key[0x09] = (char)i2;
                  brute_key[0x0A] = (char)i3;
                  brute_key[0x0B] = (char)i4;
                  brute_key[0x0C] = (char)i5;
                  brute_key[0x0D] = (char)i6;
                  brute_key[0x0E] = (char)i7;
                  brute_key[0x0F] = (char)i8;

                  // Объявление переменных:
                  u8 buffer[0x40];
                  u8 zero_iv[0x10];
                  u8 buffer_enc[0x40];
                  u8 buffer_dec[0x40];
                  u8 key[0x10];
                  u8 iv[0x10];

                  // Заполнение переменных нолями:
                  memset (buffer, 0, 0x40);
                  memset (buffer_enc, 0, 0x40);
                  memset (buffer_dec, 0, 0x40);
                  memset (zero_iv, 0, 0x10);

                  // Магия:
                  memcpy (buffer, brute_key, 0x10);
                  vtrm_encrypt (3, buffer, zero_iv);
                  memcpy (key, buffer, 0x10);
                  memcpy (iv, buffer + 0x10, 0x10);
                  memcpy (buffer_enc, buffer_enc_default, 0x40); // <=== TODO
                  aes128cbc (key, iv, buffer_enc, 0x40, buffer_dec);

                  // Проверка результата:
                  if(memcmp(buffer_dec+0x30,zero_iv,0x10)==0){
                    printf("Поздравляю!\n");
                    FILE *fx= fopen(target_key,"wb");
                    fwrite(brute_key,1,0x10,fx);
                    fclose(fx);
                    exit (1) ; //return 0;
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  return -1;
}

★★

prigmi omp pirillel for

У вагіні бімба!

По теме - распараллеливай не распараллеливай, 2^64 ты так не переберёшь

TheAnonymous ★★★★★ ()
Ответ на: комментарий от TheAnonymous

Даже на серверной машине?

с 32-мя ядрами?

Понимаю, что будет дооооолго. Оооооооочень дооооооолго. Но на GPU я писать тем более не умею.

zzdnx ★★ ()
Ответ на: Даже на серверной машине? от zzdnx

Re: Даже на серверной машине?

За время подбора пароля ты получишь диплом, сходишь в армию, женишься, у тебя появятся дети, потом внуки, в глубокой старости ты «нырнешь» в гробик, а твоя прога будет со скрипом все также подбирать пароль. 😉

anonymous ()
Ответ на: Даже на серверной машине? от zzdnx

Даже на серверной машине?

Посчитай, это школьный курс математики. За твою жизнь не переберёт, тебя устраивает такое «дооооооолго»?

А так конечно вместо распараллеливания лучше начать с облегчения внутреннего цикла - всё дерьмо до «магии» там вообще не нужно, и цикл можно сделать один, можно просто по ui64.

Но на GPU я писать тем более не умею

GPU не поможет.

slovazap ★★★★★ ()
Последнее исправление: slovazap (всего исправлений: 1)
Ответ на: комментарий от slovazap

Вспомнилась история о просьбе создателя шахмат о вознаграждении )

int13h ★★★★★ ()

2^64 ты так не переберёшь
тебя устраивает такое «дооооооолго»?

В коде не просто так реализованы применение стартовой позиции и перебор только младших 8 байт.

В стартовую позицию входят все байты ключа. Старшие байты ключа можно вычислить по метаданным с точностью до 5 вариантов.

Этот код предполагается запускать с разной стартовой позицией на многих машинах сразу.

Задача - предельно ускорить выполнение кода, распараллелив, по возможности, на максимально возможное количество потоков.

zzdnx ★★ ()
Ответ на: комментарий от slovazap

вместо распараллеливания лучше начать с облегчения внутреннего цикла - всё дерьмо до «магии» там вообще не нужно

Всё дерьмо до «магии» попало в цикл после того как я начал играться с OpenMP и исправлять косяки связанные с областью видимости переменных.

цикл можно сделать один, можно просто по ui64.

Можно пример?

GPU не поможет.

Майнерам как-то помогает... Возможно, и мне бы помогло.

zzdnx ★★ ()
  for(i1=0;i1<=0xFF;i1++){
    for(i2=0;i2<=0xFF;i2++){
      for(i3=0;i3<=0xFF;i3++){
        for(i4=0;i4<=0xFF;i4++){
          for(i5=0;i5<=0xFF;i5++){
            for(i6=0;i6<=0xFF;i6++){
              for(i7=0;i7<=0xFF;i7++){

У тебя там всё в порядке?

crutch_master ★★★★★ ()
Ответ на: комментарий от zzdnx

Майнерам как-то помогает... Возможно, и мне бы помогло.

Ну да, конца работы программы дождутся не твои внуки, а твои дети.

morse ★★★★★ ()
Ответ на: комментарий от crutch_master

Это слив новой линейки core i* штеуда.

anonymous ()

>У тебя там всё в порядке?

Реанимация. Над телом умирающего, но всё ещё живого, собрался консилиум врачей, громко обсуждающих не приятный цвет и плохой покрой занавесок, а так же кривые стыки обоев.

Я понимаю, глумиться всем мы любим, правда, не всегда это уместно. А по сути вопроса-то есть что ответить?

zzdnx ★★ ()
Ответ на: комментарий от crutch_master

Сделай нормальный цикл

1. Что в твоём понимании означает слово «нормальный»?

2. Чем так не нормальна форма записи применённая мной?

Желательно, с цифрами наглядно демонстрирующими преимущество «нормального» цикла.

zzdnx ★★ ()

#prigmi omp pirillel for

«pragma omp parallel for». Параллелить нужно внешний цикл. Циклы по одному байту — растрата ресурсов. Инициализации внутри горячего цикла — растрата ресурсов.

Время на работу ты оценивал вообще? Сколько времени занимает, скажем, миллион циклов? Сколько времени займёт полный перебор на одной машине в один поток? Сколько времени займёт полный перебор при условии идеального распараллеливания?

i-rinat ★★★★★ ()
Ответ на: комментарий от zzdnx

и исправлять косяки связанные с областью видимости переменных

Куда-то вы их не туда исправляете. static тоже вообще не в кассу.

Можно пример?

uint64_t key = 0;
do {
   // work
   key++;
} while (key != 0);

Майнерам как-то помогает... Возможно, и мне бы помогло.

При знаниях на уровне «как-то» точно нет. AESNI вам бы помог, может он есть в aes128cbc, а может и нет.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

Куда-то вы их не туда исправляете. static тоже вообще не в кассу.

Си вижу буквально первую неделю в жизни урыками по час-два в день. Этого «слегка» недостаточно.

zzdnx ★★ ()
Ответ на: комментарий от zzdnx

Это твои проблемы, я свои знания тебе в голову положить не могу. Выучи C, потом перечитай тред.

slovazap ★★★★★ ()
Ответ на: комментарий от i-rinat

Время на работу ты оценивал вообще?

Для оценки мне нужно знать на чём будет выполняться код. Если на домашнем лаптопе с атомом в один поток - потребуется >500 лет. Если на i5_4460 в один поток - лет 50 и более.

Про растрату ресурсов сам понимаю, но навыков программирования на Си слишком мало, чтобы я с ходу писал правильно работающий код.

zzdnx ★★ ()
Ответ на: комментарий от zzdnx

1. Что в твоём понимании означает слово «нормальный»?

Когда он один а не 8

2. Чем так не нормальна форма записи применённая мной?

Она конченая. А за копипаст надо бить ногами.

Желательно, с цифрами наглядно демонстрирующими преимущество «нормального» цикла.

Просто берешь uint64 и всё. Без вот этого вот дерьма с

i1 = brute_key[0x08];
i2 = brute_key[0x09];
i3 = brute_key[0x0A];
i4 = brute_key[0x0B];
i5 = brute_key[0x0C];
i6 = brute_key[0x0D];
i7 = brute_key[0x0E];
i8 = brute_key[0x0F];
Ты в курсе, что тут просто можно сделать
uint8 *p = (uint8 *)&some_uint64_number;
И получить такой же uint8[]? Или можно гонять счётчик внутри этого твоего brute_key без пердолинга с копированием байтов каждую итерацию?

но навыков программирования на Си слишком мало, чтобы я с ходу писал правильно работающий код

Дело не в навыках си, а в бардаке, что у тебя в голове.

static u8 buffer_enc_default[0x40]; //buffer_enc с говном
...
memset (buffer_enc_default, 0, 0x40); //говно переписываем нолями
...
fread(buffer_enc_default,1,0x40,fp); //ноли переписываем годными данными

...
...
u8 buffer_enc[0x40]; //buffer_enc c говном
...
memset (buffer_enc, 0, 0x40); //переписываем сверху нолями
...
memcpy (buffer_enc, buffer_enc_default, 0x40); // затем годными данными
Зачем ты сперва берешь кусок, сначала его затираешь, потом пишешь данные? Если ты перепишешь его сразу он будет не кошерный и данные которые ты туда запихал нечистыми?
Начни с чего-нибудь по-проще. Покастуй указатели там, поугарай с void*. Сторярова прочитай 2 первых тома по программированию.

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 2)
Ответ на: >У тебя там всё в порядке? от zzdnx

Я понимаю, глумиться всем мы любим,

Тебе повезло, что Царь в тред не заглянул. Так бы ты по-настоящему познал, что такое глумление.

crutch_master ★★★★★ ()
Ответ на: комментарий от crutch_master

Благодарю за терпеливость и объяснения.

Когда он один а не 8

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

Чем не нравится? - Она конченая.

Аргументация уровня «потому что гладиолус». Какое счастье, что меня так НЕ обучали в школе.

Ты в курсе, что тут просто можно сделать...

Если бы я был в курсе - этот пост следовало-бы считать издевательством над участниками форума, однако я обратился за советами и помощью.

Дело не в навыках си, а в бардаке, что у тебя в голове.

Любой порядок отличный от привычного тебе можно называть бардаком, однако сколько порядок бардаком не называй - упорядоченности своей он не потеряет.

Зачем ты сперва берешь кусок, сначала его затираешь, потом пишешь данные?

Наверное, это от того, что я не уверен в неизменности этих участков памяти по время «магии». Я не весь код знаю и понимаю.

Начни с чего-нибудь по-проще.

За учебники спасибо, читать буду, однако сейчас у меня задача стоит в оптимизации кода, а не в самообучении. Я пока ещё отдаю себе отчёт в том, что выполняемая задача, мягко говоря, мне не по зубам.

zzdnx ★★ ()

Наверное, это от того, что я не уверен в неизменности этих участков памяти по время «магии». Я не весь код знаю и понимаю.

Там «магия» только в vtrm_encrypt. buffer_enc точно можно выкинуть. Заполнять нолями - это не очень быстро.

Я искал с Интерент причину такой формы записи и в нескольких источниках натыкался на мнения о том, что такая «лесенка» используется как вариант оптимизации для увеличения скорости итерации длинного (большого) числа.

Всё можно легко проверить просто запустив 2 цикла.

Я пока ещё отдаю себе отчёт в том, что выполняемая задача, мягко говоря, мне не по зубам.

Но как ты её собрался решить, если не собираешься учиться её решать?

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 2)
Ответ на: комментарий от crutch_master

как ты её собрался решить, если не собираешься учиться её решать?

А кто сказал, что не собираюсь? Просто сейчас у меня нет времени на обучение с ноля всем тонкостям ещё неизвестного языка - задачу нужно было решить «ещё вчера».

За советы благодарен, попробую сделать «в лоб». Однако это по прежнему будет однопоточно, что не попадает в текущее ТЗ.

zzdnx ★★ ()
Ответ на: комментарий от zzdnx

За советы благодарен, попробую сделать «в лоб». Однако это по прежнему будет однопоточно, что не попадает в текущее ТЗ.

Вот эта лесенка, кстати не работает

$ cat for32.c
#include <stdint.h>

int main() {
    uint32_t i = 1;
    while (i++);
    return 0;
}
$ gcc for32.c -o for32
$ time ./for32
real	0m5.735s
user	0m5.732s
sys	0m0.000s

$ cat fori.c

#include <stdint.h>

int main() {
    uint16_t i1,i2,i3,i4;
    i1=i2=i3=i4=0;
    uint32_t i = 0;
    for(i1=0;i1<=0xFF;i1++) 
      for(i2=0;i2<=0xFF;i2++) 
        for(i3=0;i3<=0xFF;i3++)
          for(i4=0;i4<=0xFF;i4++) i++;
    return 0;
}
$ gcc fori.c -o fori
$ time ./fori
real	0m7.773s
user	0m7.768s
sys	0m0.000s

Без нагрузки там 0, т.е. пустые циклы сжирает оптимизатор, а если там есть i++ то плюс 2 секунды на работу этих 4-х циклов. Сколько времени он будет просто считать - можно умножить 5.7 сек на 256^4 и получить ~680 лет, но это не точно.

crutch_master ★★★★★ ()
Ответ на: комментарий от zzdnx

Однако это по прежнему будет однопоточно, что не попадает в текущее ТЗ.

Просто берешь и считаешь всё от 0x00000000 до 0x0000FFFF на одном хосте/ядре, от 0x00010000 до 0x0001FFFF на втором хосте и т.д. gnu parallel в помощь.

crutch_master ★★★★★ ()
Ответ на: комментарий от crutch_master

Ты в курсе, что тут просто можно сделать

uint8 *p = (uint8 *)&some_uint64_number;

unspecified behavior в C

и undefined behavior в C++

Не надо так делать, и вообще не нужно пользоваться reinterpret_cast

fsb4000 ★★★★★ ()
Ответ на: комментарий от fsb4000

Не надо так делать, и вообще не нужно пользоваться

Очнулся, через 2 года.

crutch_master ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.