Авторские статьи Разделение диапазона перебора паролей

Discussion in 'Статьи' started by ZaCo, 3 Oct 2007.

  1. ZaCo

    ZaCo Banned

    Joined:
    20 Jun 2005
    Messages:
    737
    Likes Received:
    336
    Reputations:
    215
    Распределенный перебор паролей
    Захаров Александр aka ZaCo
    --
    В продолжение статьи <Циклический инкремент паролей> хотелось бы затронуть тему
    распределения диапазонов паролей из заданного множества символов. Во время развития распределения
    мощностей между различными машинами задача является наиболее актуальной, например, описанный ниже
    метод уже был применен в системе распределенного перебора BruteNet. Применяемый язык C++.
    Назовем заданное множество символов, на котором ведется перебор, charset. На уровне
    программы это будет обычный массив байт (будем считать для ясности, что любой символ можно
    представить в одном байте), таким образом, если перебор ведется на множестве 'abc', то:
    Code:
    	charset[]='abc';
    
    На момент описания внутреннего представления каждой строки мы можем абстрагироваться от ее
    непосредственного представления, храня каждую строку как набор позиций, начиная с единицы, текущего
    символа в массиве charset. Такое представление действительно является удобным: строка 'bab',
    хранимая в виде '\x02\x01\x02' дает возможность перейти к следующей допустимой строке 'bac' простой
    инкрементацией последнего байта. Примем очевидным факт того, что начиная со строки 'a' и переходя
    подобным образом к следующей строке мы обойдем последовательно все участвующее в переборе строки.
    Такое поведение наталкивает на мысль о <численно-подобном> поведении строк. Действительно,
    прибавление единицы почти в точности выполняется по правилам сложения столбиком, однако при переходе
    за предел длины charset мы ставим текущий символ не в ноль, а в единицу, делая перенос на разряд
    влево. Таким образом, следующая строка после 'bac' будет 'bba'. Если бы мы научились выполнять
    арифметические операции на такими <числами> нам бы, очевидно, не составило бы и труда выполнить
    изначальную задачу деления диапазона. Но это и не представляется проблемой, ведь тема длинной
    целочисленной арифметики в пределах нашей задачи не является трудоемкой. Итак, установив связь
    между строками и числами нам остается только понять как их хранить в виде непосредственно чисел;
    параллельно возникает и обратная задача - преобразование числа в строку.

    Длинная арифметика и деление диапазона

    Заметим, что отображение каждой строки на множество целых чисел больше нуля является
    взаимно-однозначным, более того будем считать значением строки abc...def длинной n число равное:

    f+e*power+d*power^2+...+c*power^(n-3)+b*power^(n-2)+a*power^(n-1)

    Причем очевидно, что каждый символ строки принимает значение из диапазона [1..power],
    где power - количество символов в charset. Будем считать power степенью системы
    исчисления нашей арифметики. Для того чтобы строка была корректной для привычных операций столбиком,
    необходимо, ее изменить так, чтобы соответствующее ей число не поменяло значения и каждый символ
    находился в промежутке от [0..power-1]. Для этого достаточно пройтись по строке в цикле с
    младшего разряда к большему и, если, текущее значение больше либо равно power вычесть power и
    прибавить единицу к следующему разряду.

    Затроним момент реализации. Для простоты будем считать, что количество символов лежит в
    константе PASS_SIZE:
    Code:
       BYTE power;
       BYTE word[PASS_SIZE];
    
    Массив word будет хранить в себе число с которым мы и будем проводить все
    арифметические операции. В итоге функция преобразующая строку в необходимый нам вид будет выглядить
    так:
    Code:
     
    ariphmetic ariphmetic::operator=(char * rhs)
    {   memset(word,0,PASS_SIZE);
        memcpy(&word[PASS_SIZE-strlen(rhs)],rhs,strlen(rhs));
    
        for(i=PASS_SIZE-1;word[i]>0;i--)
         if(word[i]>=power)
          {
           word[i]-=power;
           word[i-1]++;
          }
    }
    
    где rhs - наша строка. Обратная операция - вывод числа из нашей арифметики в строку:
    Code:
     int ariphmetic::ToWord(char * result)
    {   int i,v;
        char buff[PASS_SIZE];
        memcpy(buff,word,PASS_SIZE);
        for(j=0;( (j<PASS_SIZE) && (buff[j]==0));j++);
        if(j==PASS_SIZE) return 0;
        v=0;
        for(i=PASS_SIZE-1;i>j;i--)
         {
          int c=buff[i]+v;
          buff[i]=c;
          if(c<=0)
           {
            buff[i]+=power;
            v=-1;
           }
          else
           {
            v=0;
           }
         }
        buff[i]+=v;
        if(buff[i]==0)
         {
          j++;
         }
        memcpy(result,&buff[j],(PASS_SIZE-j));
    }
    
    Сначала мы определяем с какой позиции в массиве начинается слово и заносим это значение в
    переменную j. Далее проделываем в цикле операцию обратную той, что использовалось в предыдущей
    функции: если текущая элемент меньше или равен нулю, прибавляем к нему power и вычитаем единицу из
    следующего разряда.
    Предположим нам нужно узнать какая строка будет, к примеру, через 5 000 000 инкрементаций.
    Благодаря настоящим выкладкам это можно сделать естественнее и быстрее чем циклом и сложением с
    единицей на каждом итерационном шаге. Ответ на задачу о представлении целого числа в нашей
    арифметике поможет в дальнейшем в разделении диапазона перебора на равное количество частей. Здесь
    все очень просто:
    Code:
     void ariphmetic::Dec2Word(unsigned int rhs)
     {   memset(&word[0],0,PASS_SIZE);
        int i=PASS_SIZE-1;
        do
         {
          if(i==0) break;
          word[i--]=rhs%power;
          rhs=rhs/power;
         }
        while(rhs>0);
    }
    
    Нет смысла приводить в данном контексте алгоритм деления или умножения двух чисел, потому
    как это скорее тема длинной арифметики, я приведу лишь пример сложения двух таких чисел:
    Code:
    void ariphmetic::Add(const ariphmetic & rhs)
     {
        int i;
        int sum,v=0;
    
        for(i=PASS_SIZE-1;i>0;i--)
         {
          sum=word[i]+rhs.word[i]+v;
          if(sum<power)
           {
            word[i]=sum;
            v=0;
           }
          else
           {
            word[i]=sum-power;
            v=1;
           }
         }
       }
     }
    
    После реализации всех необходимых арифметических операций, код распределения диапазона на N
    частей будет выглядить так:
    Code:
      void ReDistribute(const ariphmetic & first, const ariphmetic & last)
     {
      int i;
      ariphmetic temp;
      temp=(last-first)/(N);
      for(i=0;i<N-1;i++)
       {
        cl[i]->first=temp*i+first;
        cl[i]->last=cl[i]->first+temp-1;
       }
      cl[i]->first=temp*i+first;
      cl[i]->last=last;
     };
    
    где, cl - массив частей, last, first - соответственно нижняя и верхнии
    границы диапазона. Перед вызовом необходимо указать границы:
    Code:
    	first='\x01';
    	last='\x03\x03\x03';
    
    Заключение

    Хотелось бы отметить действительную привлекательность предложенного метода, который,
    при должной реализации, является не сколько быстрым и удобным, сколько универсальным. Затронутая и
    применяемая тема длинной арифметики описана мной в заметке
    <Длинная и быстрая арифметика>.
    Полноценную же библиотеку для языка C++, входящую в состав проекта BruteNet,
    можно скачать с моего сайта. Все мысли, идеи и пожелания можете отправить на zaco@yandex.ru или
    http://zaco.itdefence.ru.
     
    #1 ZaCo, 3 Oct 2007
    Last edited: 3 Oct 2007
    2 people like this.
  2. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,858
    Likes Received:
    1,962
    Reputations:
    594
    На мой взгляд вся задача распределения диапазонов паролей из заданного множества символов сводится к:

    1. Приведение строки в вид b-ричной позиционной системы счисления.
    2. Перевод в любую удобную систему для вычислений (операции -,+,/) например десятичная, шестнадцатиричная.
    3. Собственно проведение операций деления полного диапазона на подмножества.
    4. Обратное преобразование в строку в момент подбора (запись в виде b-ричной позиционной системы - это и есть пароль)

    Вот например имеем пасс из трёх символов 'aZ/' в charsete[]=mixalpha-numeric-all-space, тогда основание b-ричной системы равно 95 (число возможных символов чарсета)
    Тогда:
    a(95)=0(10)
    b(95) = 1(10)
    c(95) = 2(10)
    -------------------
    --пропущено--
    -------------------
    _(95) = 94(10) "_" - обозначил пробел, так как он последний в чарсете. (для удобства отображения можно пробел поставить в начало чарсета и сделать, чтоб он, а не 'a' соответствовал '0' в десятичной системе, но оставим пока как есть).
    Наш пароль: aZ/(95)=0*95^2+31*95^1+93*95^0=3038(10)

    Итак, например у нас диапазон [aaa-___], чарсет mixalpha-numeric-all-space т.е. фактически 95-ричная позиционная система исчисления.
    charset[]=mixalpha-numeric-all-space = [abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/ ]

    Переводим его в десятичную систему:
    aaa(95)=0(10)
    ___(95)=94*95^2+94*95^1+94*95^0=94*9025+8930+94=848350+8930+94=857374 - самое наибольшее число в дясятичной системе, соответствующее пассу из 3-х пробелов. Проверим, что нам говорит Winrtgen-> он говорит, что всего возможно 866495 ключей (паролей). Кто из нас ошибся? Похоже, что я, так как отсутствие какого либо символа в пароле это тоже результат имеющий значение, т. е. множестово одно и двух символьных паролей тоже учитывается в Winrtgen, тогда и мы исправим ошибку:
    ___(95)=95*95^2+95*95^1+95*95^0=866495 и получим результат, который сообщает Winrtgen.

    И так мы получили: полное множество [пусто-___] -> [0-866495] и [aaa-'три пробела'] -> [0-857374] - теперь можно дробить на поддиапазоны, например разбить на два второй диапазон: 857374/2=428687 Затем остаётся перевести обратно в 95-ричную систему и можно использовать для подбора паролей.

    ЗЫ Написал почти тоже самое ,что и Zaco, только щас заметил, заисключением того, что как я понял, все арифметические операции Zaco предлагает проводить в b-ричной системе счисления, вообщем смысл ясен...
     
    #2 -=lebed=-, 3 Oct 2007
    Last edited: 4 Oct 2007
  3. ZaCo

    ZaCo Banned

    Joined:
    20 Jun 2005
    Messages:
    737
    Likes Received:
    336
    Reputations:
    215
    >>все арифметические операции Zaco предлагает проводить в b-ричной системе счисления, вообщем смысл ясен...
    в 10-ой системе проводить операции крайне бессмысленно и что более важно расточительно в плане памяти и скорости.
     
  4. Talisman

    Talisman Elder - Старейшина

    Joined:
    22 Apr 2006
    Messages:
    401
    Likes Received:
    153
    Reputations:
    80
    прально. нех из системы в систему переводить... сам когдато на олимпиаде решал похожую проблемку. я двоичным делением к-ричной системы делал. приближение хорошее выходит, главное быстро.
     
Loading...
Similar Threads - Разделение диапазона перебора
  1. Tyc00n

    Авторские статьи Перебор файлов в sqlmap

    Replies:
    6
    Views:
    10,810
  2. lukmus
    Replies:
    5
    Views:
    4,559
  3. Slon
    Replies:
    17
    Views:
    4,318