скорость crypt md5

tokuchu

Вот такая программа без претензий на идеальность:


#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#include <signal.h>

#include <string.h>



char s[7] = "aaaaaa";

long long count = 0;

long long count0 = 0;

long secs = 0;

int delay = 30;

long long total = 52 * (long long)52 * 52 * (long long)52 * 52 * (long long)52;



void sigalrm(int sig)

{

  secs += delay;

  alarm(delay);

  fprintf(stderr,

          "total: %lld, "

          "%.4lf%%, "

          "+%lld pass, "

          "%.2lf pass/sec, "

          "current: %s\n",

          count,

          (double)count * 100.0 / (double)total,

          count - count0,

          (doublecount - count0) / (double)delay,

          s);

  count0 = count;

}



const char *hash = "bZEkVZPajtHcTOLt.H2Q..";

const char *salt = "$1$PQW8jl.5";



void p(void)

{

  if (strcmp(hash, (const char *)crypt(s, salt) + 12) == 0)

  {

    printf("Here it is: %s\n", s);

    exit(0);

  }

}



void f1(void);

void f2(void);

void f3(void);

void f4(void);

void f5(void);



void f0(void)

{

  for (s[0] = 'a'; s[0] <= 'z'; ++s[0]) f1;

  for (s[0] = 'A'; s[0] <= 'Z'; ++s[0]) f1;

}



void f1(void)

{

  for (s[1] = 'a'; s[1] <= 'z'; ++s[1]) f2;

  for (s[1] = 'A'; s[1] <= 'Z'; ++s[1]) f2;

}



void f2(void)

{

  for (s[2] = 'a'; s[2] <= 'z'; ++s[2]) f3;

  for (s[2] = 'A'; s[2] <= 'Z'; ++s[2]) f3;

}



void f3(void)

{

  for (s[3] = 'a'; s[3] <= 'z'; ++s[3]) f4;

  for (s[3] = 'A'; s[3] <= 'Z'; ++s[3]) f4;

}



void f4(void)

{

  for (s[4] = 'a'; s[4] <= 'z'; ++s[4]) f5;

  for (s[4] = 'A'; s[4] <= 'Z'; ++s[4]) f5;

}



void f5(void)

{

  for (s[5] = 'a'; s[5] <= 'z'; ++s[5]) { p; ++count; }

  for (s[5] = 'A'; s[5] <= 'Z'; ++s[5]) { p; ++count; }

}



int main(void)

{

  signal(SIGALRM, sigalrm);

  alarm(delay);

  f0;

  fprintf(stderr, "End of generation\n");

  return 0;

}

Перебирает пароли "[a-zA-Z]{6}" и сравнивает хеш с известным. Наблюдаются странная скорость её работы на разных платформах (в паролях в секунду):
Athlon XP 1700+, Gentoo, linux 2.6, gcc-4.1 - 1620
Xeon 2.4, Gentoo, linux 2.6, gcc-3.4 - 1620
Xeon 2.4, RedHat 9, linux 2.4.31, gcc-3.2 - 1620
CeleronM 1.3, Gentoo, linux 2.6, gcc-4.1 - 1349
PentiumM 1.6, FreeBSD 6.0 - 892
Celeron Coppermine 800, Gentoo, linux 2.6, gcc-4.1 - 856
P3 Coppermine 800, Slackware, linux 2.6 - 669
P4 2.0, FreeBSD 6.1 - 540
P4 ?, FreeBSD 5.4 - 490
Athlon 1000, FreeBSD 5.4 - 452
P4 2.4, Gentoo, linux 2.6, gcc-4.1 - 380
PentiumM 600, FreeBSD 6.0 - 333
P3 500, FreeBSD 4.11 - 280
Вот так вот

vall

потрясающе. надо это на LOR запостить. вот флуда то будет.
очевидно что основной тормоз это вычисление самой MD5.
лучше не брать её из библиотеки, а скомпилировать статически и с оптимизациями,
тогда есть шанс что p4 перестанет настолько тормозить.

tokuchu

очевидно что основной тормоз это вычисление самой MD5.
лучше не брать её из библиотеки, а скомпилировать статически и с оптимизациями,
Ну да, понятно, что самый затык на crypt и вызовы оттуда md5 приходится.
Но прикол в том, что там есть 2 системы на Xeon - железо почти одинаковое, но одна система Gentoo с оптимизацией под P4, а другая RedHat 9, которой хрен знает сколько лет. И результат - одинаковый.
Кто-нибудь на других процах/системах может потестить?

vall

хз как там этот RH собран, может они что-то и придумали.
просто на p4 оптимизация очень много дает, NetBurst слишком уж отличается от i686.
K8 Sempron 2GHz/Linux 2.6/Ubuntu x86_64 - 2342

tokuchu

Кстати, я на P4 2.4 когда по 10 секунд отмерял, то у меня на первые 10 секунд было больше 600 паролей в секунду, а потом не больше 380.

Chupa

J-t-R 1.7.0.2, AthlonXP 2500+
скорость около 3600

tokuchu

J-t-R 1.7.0.2
Это что такое?
"bbbbbb"
Ну это я так - для прикола.

tokuchu

А ещё непонятны сливания в одном классе - CeleronM 1.3 vs PentiumM 1.6, Celeron 800 vs Pentium 800. Там что оптимизация сказалась? Тогда как же Gentoo vs RedHat 9?

Chupa

john the ripper
оптимизирован специально под перебор, поэтому работает быстрее, чем crypt в цикле

procenkotanya

Celeron M 1.3 / Ubuntu Linux / Linux 2.6 / GCC 4.2 1415
Со статически слинкованной скомпиленной с оптимизацией crypt 1600

Dasar

функция crypt что делает?
hash считает от password + salt?

Dasar

имхо, дело не в md5, потому что винда md5-хэши считает со скоростью 100тыс. в секунду

procenkotanya

Кстати да, скорость должна быть такой низкой?
Вот что показывает профилирование варианта с заинлайненным crypt:


CPU: PIII, speed 1300 MHz (estimated)

Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit mask of 0x00 (No unit mask) count 100000

samples  %        linenr info                 image name               app name                 symbol name

51514    51.1808  pwhack.c:79                 pwhack                   pwhack                   md5_process_block

22517    22.3714  (no location information)   libc-2.3.6.so            libc-2.3.6.so            (no symbols)

13375    13.2885  pwhack.c:236                pwhack                   pwhack                   __md5_process_bytes

9733      9.6700  pwhack.c:355                pwhack                   pwhack                   __md5_crypt_r

1191      1.1833  (no location information)   pwhack                   pwhack                   .plt

553       0.5494  (no location information)   oprofiled                oprofiled                (no symbols)

tokuchu

Да, crypt считает хеш от password и salt.
имхо, дело не в md5, потому что винда md5-хэши считает со скоростью 100тыс. в секунду
Ну, я думаю, это ещё от размера данных зависеть должно.
Потом в crypt хешем не просто md5 является... там оно лишь часть процедуры.
Кстати, прогу виндовую поставил для подбора - на Athlon XP 1700 она тоже 1500 паролей в секунду выдаёт, что с результатом у Linux на таком же проце схоже.

Dasar

> Да, crypt считает хеш от password и salt.
каким образом?
> Потом в crypt хешем не просто md5 является... там оно лишь часть процедуры
так вот как раз у меня подозрение, что как раз crypt херней и страдает, и что если md5-hash считать напрямую, то работать будет на несколько порядков быстрее

procenkotanya

Оно считает md5 много раз.
Вот кусок кода. Коммент жжот


  /* Now comes another weirdness.  In fear of password crackers here

     comes a quite long loop which just processes the output of the

     previous round again.  We cannot ignore this here.  */

  for (cnt = 0; cnt < 1000; ++cnt)

    {

      /* New context.  */

      __md5_init_ctx (&ctx);



      /* Add key or last result.  */

      if cnt & 1) != 0)

        __md5_process_bytes (key, key_len, &ctx);

      else

        __md5_process_bytes (alt_result, 16, &ctx);



      /* Add salt for numbers not divisible by 3.  */

      if (cnt % 3 != 0)

        __md5_process_bytes (salt, salt_len, &ctx);



      /* Add key for numbers not divisible by 7.  */

      if (cnt % 7 != 0)

        __md5_process_bytes (key, key_len, &ctx);



      /* Add key or last result.  */

      if cnt & 1) != 0)

        __md5_process_bytes (alt_result, 16, &ctx);

      else

        __md5_process_bytes (key, key_len, &ctx);



      /* Create intermediate result.  */

      __md5_finish_ctx (&ctx, alt_result);

    }

tokuchu

так вот как раз у меня подозрение, что как раз crypt херней и страдает, и что если md5-hash считать напрямую, то работать будет на несколько порядков быстрее
Так вопрос не в скорости подсчёта md5, и даже не совсем о скорости crypt, а про сравнительную производительность разных архитектур при подсчёте crypt.

vall

фиговый эксперимент. не надо использовать системную crypt для этого.

tokuchu

не надо использовать системную crypt для этого.
А чем она плоха? В системных библиотеках не нужны оптимизации, разве?
И это не эксперимент. Просто мне непонятна очень низкая производительность на некоторых системах. Т.е. я сначала запустил на одной (Athlox XP 1700 а потом на другой (P4 2.4) с почти одинаковой ОС и очень удивился увидев огромную разницу в скорости.

vall

просто в этом случае нужна жёсткая оптимизация.
md5 плохо работает на p4 в силу своей структуры - короткий цикл в котором модифицируются одни и те-же данные.

tokuchu

просто в этом случае нужна жёсткая оптимизация.
А разве она с таким же успехом не нужна в системной библиотеке?

Ivan8209

Всё зависит от системы.
Если система "дружественная", то библиотечная функция будет проверять входные данные,
что, соответственно, требует времени.
---
...Я работаю антинаучным аферистом...

vall

А разве она с таким же успехом не нужна в системной библиотеке?
ну не обязана функция crypt в системной библиотеке быть оптимизированной на перебор паролей =)
со своей задачей она справляется по-любому.

shlyumper

Еще кстати, на тему быстродействия этой конкретной программы: запускал ее интереса ради на ноутбуке. На нем включен CPU Frequency scaling. Так вот, от этой программы проц "разгоняться" с 600Mhz холостого хода до 1.7GHz не захотел. Соответственно, результаты между запуском программы "просто так", и запуском программы с предварительным переводом проца на 1.7GHz - различается примерно в 3 раза, как и должно быть. Удивительно то, что вообще, при запуске процессорноемких программ процессор обычно всегда "разгоняется" сам, а от этой программы разгоняться не захотел.

tokuchu

ну не обязана функция crypt в системной библиотеке быть оптимизированной на перебор паролей
Если не под вычисление хеша - то подо что она тогда должна быть оптимизирована?
Даже если она там и не сильно оптимизирована, то не считая FreeBSD, сравнивались glibc-реализации на разных процах фактически. И слив P4 по-моему просто ужасен.

tokuchu

По поводу ноута странно... прога вроде весь свободный проц спокойно выжирает.

vall

реализация вроде везде одна используется. просто её структура нетипична - компиляторы отстраивают не на таком коде, хотя возможно md5 и входит в тестовый набор gcc.
P4 сливает т.к. для него нужно писать какую-то свою реализацию этой функции, обычная на нём сосёт. (как и он сам собственно )

tokuchu

P4 сливает т.к. для него нужно писать какую-то свою реализацию этой функции, обычная на нём сосёт. (как и он сам собственно )
Ну да, вот это то и отстойно. Я всегда знал , что он сосёт, но что настолько может...

banderon

Intel(R) Pentium(R) 4 CPU 3.20GHz
Ubuntu Linux 2.6.15
gcc 4.0.3
2400 pass/sec
опции при компилировании: -O4 -lcrypt

vlfdimir58

AMD Athlon(tm) 64 Processor 3500+
Fedora Core 4 x86_64 (2.6.13)
gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)
~2350 pass/sec
-------------------
AMD Opteron(tm) Processor 248
Fedora Core 5 x86_64 (2.6.15)
gcc version 4.1.1 20060525 (Red Hat 4.1.1-1)
2768.50 pass/sec

sergey_m

Удивительно то, что вообще, при запуске процессорноемких программ процессор обычно всегда "разгоняется" сам, а от этой программы разгоняться не захотел.
AFAIK, процессор не разгоняется сам, его разгоняет операционная система.

shlyumper

Бля, ну давай пофелософствуем, все равно ж ты мысль понял.
AFAIK, процессор не разгоняется сам, его разгоняет операционная система.
AFAIK, процессор не разгоняется сам, его разгоняет материнская плата, получившая пинок от операционной системы.

sergey_m

Это я к тому, что процессор и материнская плата не виноваты в том, что ты наблюдал.
Оставить комментарий
Имя или ник:
Комментарий: