Blowfish на страже ivi

[slonopotamus]

Не понял в чем проблема сравнить строки без выдачи информации о том, на каком символе случилось различие (и зачем для этого привлекать hmac).

bool streq_secure(char *actual, char *expected) {
  int actual_len = strlen(actual);
  int expected_len = strlen(expected);
  bool result = actual_len == expected_len;

  for (int i = min(actual_len, expected_len); i >= 0; --i) {
    result &= actual[i] == expected[i];
  }

  return result;

Если еще немножко заморочиться, то можно попробовать скрыть и длину ожидаемой строки:

bool streq_secure(char *actual, char *expected) {
  int actual_len = strlen(actual);
  int expected_len = strlen(expected);
  bool result = actual_len == expected_len;

  for (int i = actual_len; i >= 0; --i) {
    result &= actual[i] == (i < expected_len ? expected[i] : '\0');
  }

  return result;

[stargrave2]

Компилятор, например GCC, очень хорошо умеет оптимизировать код по производительности. Учитывая SIMD расширения, кэши: не шибко сильный в ассемблере генерируемом программист не знает что конкретно будет делать процессор. Почти наверняка подобные циклы будут применять и предикаты и переименование регистров (а их везде по-разному), что, в зависимости от длины строк сравниваемых, на время выполнения может повлиять ещё как.

С точки зрения математики, логики, пример ваших циклов само собой будет занимать константное время. На практике оптимизация GCC для intel процессоров не даст желаемого результата (а может и даст иногда). HMAC позволяет где бы то ни было рандомизировать время сравнения. Это частая практика в местах применения криптографии, где никто не хочет тратить приличное количество человекочасов на проверки действительно ли такая-то версия GCC делает нужный по поведению код для заданной модели процессора.

[starius]

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

Можно ли использовать сортированный массив для хранения списка хешей, чтобы избежать накладных расходов, которые вносит дерево?

[stargrave2]

Безусловно можно. В примере из статьи это более миллиона итераций: то есть придётся сделать более миллиона итераций поиска по массиву, читая его элементы последовательно. Это на порядки медленнее чем использование set (в Python) или словарей/хэшей. Да и, если уж нашлось три мегабайта памяти, то наверняка найдётся и чуть-чуть побольше. То есть овчинка выделки не стоит.

[stargrave2]

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

[starius]

Если использовать бинарный поиск, то время поиска в сортированном массиве O(log(N)).

[stargrave2]

Это да. Но у хэша O(1). Безусловно как компромисс между скоростью и экономией памяти можно рассматривать. Чувствую что при одних значениях если данные памяти будут хорошо кэшироваться, то log(N) в быстрой памяти может быть быстрее.

[starius]

Количественная разница становится качественной: либо пользователь мобильных устройств слишком долго ждёт решения PoW, либо трудоёмкость на ПК становится несущественной и посылка трафика будет куда накладнее.

Доступный ресурс, имеющийся на всех платформах, кроме процессора — оперативная память. Задачи процессоров могут быть реализованы аппаратно в виде ASIC- и FPGA-решений с большей производительностью на денежную единицу. А вот разница в производительности памяти на разных доступных пользователям платформах гораздо менее существенна.

Различия машин по памяти не менее велико, чем по процессорной мощи. Память изменяется в 2 000 раз (от примерно 500 мегабайт на мобильниках до примерно 1 терабайта на нодах суперкомпьютеров). Если взять ваш алгоритм, требующий для решения задачи 3 мегабайта, то на большинстве компьютеров памяти бы хватило на одновременное решение тысяч таких задач, что намного превосходит количество задач, которое может одновременно решать процессор этого же компьютера.

[stargrave2]

В данной статье речь про скорость оперативной памяти, а не размерах. Памяти может быть и много: вопрос стимости. Обычный ПК или обычный сервер *уже* (из коробки) имеют разницу в 2-3 порядка относительно обычного смартфона по процессору, а по памяти всего порядок.

Не очень понял про тысячу задач. Если мы возьмём алгоритм по перебору шифра: разница в производительности между процессорами обычного ПК/сервера и смартфона будем считать различается на три порядка. Допустимое максимальное время ожидания решение задачи это 10 секунд (из-за раздражения пользователя). То есть то что на сотовом выполняется 10 сек, на ПК будет выполнятся за 10 мс. Если использовать задачу с памятью, то разница будет в десять раз или меньше. Первую задачу можно распаралллеливать, а вторую можно считать что нет, предполагая что всё упрётся в шину памяти.

В первом случае само по себе PoW бесполезен так как для сервера это несущественные накладные расходы (10мс на одном ядре), а для смартфона слишком большой предел ожидания.

Имея много памяти мы упрёмся в шину и в процессор. Процессор легко докупить. Шину если только распараллеливать на NUMA. Можно, но дорого. Никто не будет тратить столько средства на такое железо так как наши потери от лавины PoW задач не пойдут ни в какое сравнение.

[powerman]

Т.е. Ваш подход в том, чтобы привязать скорость решения задачи к скорости случайного доступа к памяти, вместо привязывания к скорости CPU или к объёму памяти (как делает scrypt)? Из статьи это не совсем понятно, я тоже не въехал как дополнительные 3 Mb памяти решили проблему.

А насколько различается скорость доступа к памяти между разными устройствами?

[stargrave2]

Да, привязка к скорости случайного доступа к памяти. scrypt делает тоже самое: память ему не нужна как таковая: её можно заменить вычислениями на CPU. Либо это будет очень медленно, либо гораздо быстрее при наличии памяти. Она сродни кэшированию промежуточных вычислений. После какого-то порога, связанного с парадоксами дней рождения, у нас будет очень высокая вероятность попадания в кэш хэш-значений: имея этот кэш у нас на каждой итерации большая вероятность найти коллизию и быстро решить задачу (найти необходимое количество коллизий).

Скорость между памятью у нас различалась максимум на порядок.