Проверка NIST тестом.

[j123123]

Здравствуйте, хочу сообщить о своих провеках хэш функции t1ha2.

Код:

#include <stdio.h>
#include "t1ha.h"

int main(void)
{
  uint64_t seed = 1234;
  /*
  FILE *fp;
  fp = fopen("/dev/urandom", "r");
  fread((void *)&seed, 1, 8, fp);
  fclose(fp);
  */
  
  for (uint64_t i = 0; i < 100000; i++)
  {
     uint64_t out_hash = t1ha2_atonce((void *)&i, 8, seed);
     fwrite((void *)&out_hash, 8, 1, stdout);
  }
  return 0;
}

Вывод программы сохраняется в файл my_test > randdata. Компилировалось и запускалось на x86-64 архитектуре, если это важно.
Таким образом я делаю ГПСЧ из хеш-функции. Так вот, такой ГПСЧ проваливает тест NIST. Я взял https://github.com/dj-on-github/sp800_22_tests и запустил это таким образом:
/sp800_22_tests-master/sp800_22_tests.py -t random_excursion_variant_test rand_data_test
Результат:

Tests of Distinguishability from Random
TEST: random_excursion_variant_test
J= 217
x = -9	 count=178	p = 0.321056 
x = -8	 count=201	p = 0.140221 
x = -7	 count=217	p = 0.000000  Not Random
x = -6	 count=224	p = 0.071638 
x = -5	 count=196	p = 0.237595 
x = -4	 count=180	p = 0.474671 
x = -3	 count=172	p = 0.683074 
x = -2	 count=184	p = 0.646686 
x = -1	 count=204	p = 0.441249 
x = 1	 count=217	p = 0.000000  Not Random
x = 2	 count=200	p = 0.333141 
x = 3	 count=192	p = 0.379485 
x = 4	 count=186	p = 0.397697 
x = 5	 count=183	p = 0.384678 
x = 6	 count=215	p = 0.020468 
x = 7	 count=247	p = 0.282416 
x = 8	 count=252	p = 0.306734 
x = 9	 count=246	p = 0.238734 
J too small (J=217 < 500) for result to be reliable
FAIL
P=0.321055625331
P=0.14022146188
P=0.0
P=0.0716377331396
P=0.237595481656
P=0.474671155356
P=0.683073833309
P=0.646685986377
P=0.441248751646
P=0.0
P=0.33314126571
P=0.379485462949
P=0.397697454488
P=0.384678398871
P=0.0204679237542
P=0.282416272064
P=0.306734447862
P=0.238733670118

Тест провален. Может быть эти требования не стоит предьявлять к данной хеш функции, но я просто собщаю.

[erthink]

Я не склонен воспринимать эти результаты всерьез по двум причинам:

• Нет уверенности что реализация теста корректна. Не являются редкостью технические ошибки, которые выявляются на новых версиях компиляторов и т.п. (в данном случае python и/или используемых библиотек).
• Тест вроде-бы сам сообщает что при неком использованном параметре J=217 результатам нельзя верить.

[j123123]

Нет уверенности что реализация теста корректна. Не являются редкостью технические ошибки, которые выявляются на новых версиях компиляторов и т.п. (в данном случае python и/или используемых библиотек).

Реализация тестов NIST есть и на Си, в т.ч. официальная, доступная по ссылке https://csrc.nist.gov/projects/random-bit-generation/documentation-and-software - можно проверить на ней. Есть еще какие-то сторонние реализации, например https://github.com/stamfest/randomtests https://github.com/terrillmoore/NIST-Statistical-Test-Suite

Еще можно почитать описание самого теста "Random Excursions Variant Test", и что конкретно проверяется им, вот ссылка на соответствующую статью: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf - можно написать свою реализацию данного теста, если есть какие-то сомнения.

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

Не совсем. Малый параметр J говорит о том, что результаты теста могут быть необъективны, но этот параметр J выводоится на основе содержимого анализируемого файла (хотя тут конечно и размер играет роль). J это количество переходов через 0 если битовую последовательность представить как последовательность -1, 1 и просуммировать это.

Вот простейшая программа, которая принимает поток байтов в stdin и считает только лишь параметр J для него:

#include <stdio.h>

const char pos_neg[2] = {-1, +1};

int main(void)
{
  int acc = 0;
  unsigned zero_cross = 0;
  int c;
  while((c = getchar()) != EOF)
  {
    for(int i = 7; i != -1; --i)
    {
      acc += pos_neg[ ((unsigned char)c >> i) & 1 ];
      if (acc == 0)
      {
        zero_cross++;
      }
    }
  }
  printf("J = %u\n", zero_cross+1);
  return 0;
}

Для последовательности, полученной с сидом 1234, это самое значение J не меняется очень длительный период времени. Попробуйте в оригинальной программе заменить условие цикла for (uint64_t i = 0; i < 100000; i++) на i < 2500000 например. Это несколько странно

[j123123]

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

[erthink]

Тогда я понял о чем вы.

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

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

Соответственно, если предлагаемое "дешевое" (с точки быстродействия) качество не подходит, то нужно подбирать другую хеш-функцию (или другой ГПСЧ).
Но каких-либо четких критериев тут нет.

---

Если говорить о недостатках t1ha, то сейчас я считаю что мне не следовало использовать MUL-XOR (aka MUM) миксер (умножение 64x64=>128 с последующим XOR-ом старшей и младшей частей). Этот миксер, кроме очевидной не-инъективности, сложен для анализа и поэтому привнес еще несколько недочетов (см #36).