Генерация случайной последовательности

Чем обычный рандом не подходит?

Ты чем-то обдолбадся...

Ну так-то впердоливай новый рэндомный ключ 🔑 с проверкой что нет похожего старого. И всё. Только смысл непонятен.

Ему нужен рандом, но с выкашиванием того, что он считает не-рандомным.

бери несколько рандомных байт и заенкодь их в base32 или base36, я хз что там у тебя... вот повтыкай http://www.gootar.com/folder/base.html

Изи же, с тебя миллион рублей

dron@gnu:~$ cat random.c 
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <assert.h>

#define KEY_QUANTITY 55000000
#define KEY_FILE "keys.txt"
#define RF rand() % 25 + 65

int main(int argc, char *argv[])
{
    FILE * pkey_file = fopen(KEY_FILE,"w");
    assert(pkey_file);

    srand(time(NULL));
    for (uintmax_t i = 0; i < KEY_QUANTITY; ++i)
    {
        fprintf(pkey_file,"%c%c%c%c-%c%c%c%c\n",RF,RF,RF,RF,RF,RF,RF,RF);
    }
    fclose(pkey_file);

    return 0;
}
dron@gnu:~$ gcc random.c
dron@gnu:~$ time ./a.out 

real	0m17,894s
user	0m17,004s
sys	0m0,524s
dron@gnu:~$ du -h ./keys.txt 
525M	./keys.txt
dron@gnu:~$ head -n 10 ./keys.txt 
DMDL-DWXK
JVFX-CXFX
ETOS-DAMY
LXFY-TJRI
BWDB-RQXF
ERBE-IDWI
RQDJ-JJUQ
NHMI-VNCU
PQEE-PHYM
NOSW-IXVD
dron@gnu:~$ 

Допиши проверку на коллизии и всё.

А и цифарки добавь в диапазон, я забыл про них

*printf лишний здесь.

23456789ABCDEFGHJKLMNPRSTUVWXYZ

Читаете криптографически хорошие случайные байты (не rand(), а из /dev/urandom, например). Каждые 5 бит из этого потока берёте и проверяете: если == 31, то выкидываете, иначе используете число как смещение в массиве допустимых символов (%31 можно делать только в том случае, если каждый бит действительно распределён независимо от других; не у всех rand() это гарантируется). Повторяете, пока не наберётся 8 символов. Всё это повторяете 55000000 раз.

Типичные карточки для пополнения, промо-коды, и т.д.

«невозможность» угадать другой код

31^8/55000000 = 15507.109

пожалуй и правда угадать будет «невозможно»

Ты не учёл исключение некоторых символов, в задаче не полный алфавит. Исключены неоднозначные символы 1, I, 0, O, Q.

И rand() здесь опасно использовать. Слишком предсказуемые псевдо-случайные числа.

Читаешь из /dev/urandom и кодируешь в base64 с кастомным алфавитом

А у тебя маленький алфавит. Ну тогда читаешь из /dev/urandom и маской вырезаешь ненужные биты чтобы получить число 0-31, потом достаешь символ по индексу из массива.

Генерация случайной последовательности

Например, совершенно недопустимы коды следующего вида:
- A123-B456
- A123-B457

Не вижу причин считать эту последовательность неслучайной.

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

Во, точно. Я почему то считал это дистанцией Левинштейна, но там со словами.

Вначале напишу предположения исходя из описания проблемы.

Список предположений:

• Коды проверяются сервером онлайн.
• Коды не нужно проверять оффлайн на устройстве пользователя.
• Нет нужды иметь алгоритм, чтобы генерация кодов подвергалась конкретным закономерностям, чтобы с помощью обратного алгоритма можно было проверить его правильность. Если проще, то мы просто можем на сервере создать табличку со всеми 55 млн. кодами и проверять правильность и доступность кода обычным поиском в БД.
• Коды вводит уже существующий пользователь и у каждого есть только 10 попыток, то есть, не стоит проблемы брутфорса с помощью кучи ботов. Идеальный пример — провайдер, где создание пользователя требует ручной активации персоналом, т.е., злоумышленник в принципе не может насоздавать кучу действующих фейковых аккаунтов.

Возможные проблемы:

• При несложной автоматической регистрации пользователей таки возможен сценарий брутфорса. Примерно 1.5 тыс. ботов теоретически должны угадать как минимум один код.

Советы:

1. Не использовать определённый алгоритм генерации кодов, только совершенно случайные данные. Здесь советовали /dev/urandom, но на самом деле я бы советовал только /dev/random или аппаратный ГСЧ. Если с аппаратным ГСЧ должно быть всё понятно, то вот на счёт софтварных ГСПЧ есть нюансы. 55 млн. 8-байтных кодов - это 419 Мб, получение такого объема из /dev/random может быть очень долгим, но это надёжный источник случайных данных на типичном не специализированном оборудовании.

   /dev/urandom же вначале тоже дает очень хорошую энтропию, потому что он неявно использует доступный пул данных из /dev/random. Как только этот пул заканчивается, то /dev/urandom продолжает генерировать уже псевдослучайные числа.

2. Можно использовать разные алгоритмы нахождения похожих строк:

   Ratcliff/Obershelp https://xlinux.nist.gov/dads/HTML/ratcliffObershelp.html
   Levenshtein distance https://en.wikipedia.org/wiki/Levenshtein_distance
   Больше здесь: https://en.wikipedia.org/wiki/String_metric
   https://stackoverflow.com/questions/17388213/find-the-similarity-percent-betw...
   https://stackoverflow.com/questions/6690739/fuzzy-string-comparison-in-python...
   

3. Про расстояние Хэмминга уже написали в треде.
4. Вероятность угадывания кода с одной попытки: ≈0.007% (писали выше). Вероятность угадать с десяти попыток - ≈0.07%. Если это не устраивает, то следует увеличить длину кода.
5. Поиск похожей подстроки не поможет в случае пары кодов вида 5999-5999 и 6000-6000, поэтому в дополнение к поиску похожих кодов можно добавить следующую проверку. Каждый блок кода можно представить как число, записанное в системе счисления с основанием 31 (т.к. у тебя используется 31 символ). Допустим, есть пары 1099-ABCE и 1100-ABCD. Вычисляем разницу между парой первых блоков и вторых, и складываем модули.

   1099 - 1100 = -1
   ABCE - ABCD = 1
   |-1| + |1|= 2
   

   Таким образом можно отфильтровать простейшие математические закономерности, если у пары кодов результат этих вычислений меньше определённого числа, например, меньше десяти.
6. В целом слишком небольшой размер генерируемого кода значительно увеличивает появление пар кодов, между которыми прослеживаются различные закономерности.
7. Даже если мы будем исключать много «похожих» пар кодов, шансы злоумышленника угадать почти не увеличиваются. Например, пусть на каждый подходящий код мы гарантированно исключаем тысячу «похожих» кодов, и злоумышленнику стало известно n уже использованных кодов, и он знает нашу методику отсеивания похожих кодов. Всего возможных кодов 31⁸. Он может отсеять n*1001 кодов. Т.е., если в интернет слили 100 использованных кодов, то количество вариантов для угадывания уменьшается на ≈100000, т.е., на 0.00001%. Если у него будет 54999999 известных использованных кодов, то шанс угадать последний правильный код с одной попытки будет 100/(31⁸-54999999*1000) ≈ 0.0000000001%.

Надеюсь, я не ошибся в расчётах.

Это решается псевдослучайной выборкой, необязательно брать последовательно, расстояния между значениями и исключение заведомо нежелательных решается обычным if, да и в принципе количество кодов конечно, можно нагенерировать миллиард псевдослучайных значений, а затем из них псевдослучайно сделать выборку 55миллионов необходимых попутно удаляя из основной массы то что уже взяли что бы уменьшить шанс коллизий, попутно всё же проверяя каждое новое значение на дистанцию пар и триплетов по отношению ко всем что уже выбрали и исключая заведомо нежелательное. Вот если бы петабайт надо было заранее регенерировать, вот тут да тут уже проверка коллизий не такая тривиальная задача стала бы.

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

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

При несложной автоматической регистрации пользователей таки возможен сценарий брутфорса. Примерно 1.5 тыс. ботов теоретически должны угадать как минимум один код.

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

Согласен. ТС не уточнил, как он будет их распространять. Если ему нужно заранее распечатать в виде карт пополнения, то всё равно или придётся хранить их в полном объеме, или проверять по алгоритму, что опаснее, IMHO, особенно при таком маленьком коде, который слабее, чем 40-битный ключ.

# Bash
echo "scale=2; l(31^8)/l(2)" | bc -l
39.81

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

Я думаю нужно смотреть в сторону корректирующих кодов с детекцией одной ошибки. Они гарантированно будут отличаться минимум двумя символами.

Обычно такие штуки упираются в неизвестность алгоритма. Если он известен злоумышлинникам считай фсе пропало.

Я КО?

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

Кстати, не так уж и долго. Нужно все уже сгенерированные коды положить в словарь, а для каждого нового проверять находящиеся на от него на расстоянии 1. Для каждой буквы пробегаем по алфавиту. Получается <число позиций в коде> * <число символов в алфавите> проверок.

f('ABCD', k, n) = 'WXYZ'

f() - чоткая криптография

k - секретный ключ

n [1..60] - вариант (для размерности)

'ABCD' - вхлоп

'WXYZ' - выхлоп

1) нигде 55млн ключей хранить и рыться в них не надо

2) т.к. криптография чоткая, коллизий нету

Для валидации берешь первую часть ключа, суешь в f() и, меняя n от 1 до 60, смотришь что вышло. Если совпадает со второй частью, ключ валидный

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

чоткая криптография

т.к. криптография чоткая, коллизий нету

дай URL на эту тему, plz

Держи: https://ru.wikipedia.org/wiki/Коллизия_хеш-функции

Кстати код:

#include <stdio.h>
#include <openssl/sha.h>

#define ALPHABET_SIZE   31
#define MESSAGE_SIZE    32
#define KEY_SIZE        4
#define VAR_SIZE        2

#define KEY_OFFSET      MESSAGE_SIZE - KEY_SIZE - VAR_SIZE
#define VAR_OFFSET      MESSAGE_SIZE - VAR_SIZE

#define VAR_NUM         60

unsigned char alphabet[] = "23456789ABCDEFGHJKLMNPRSTUVWXYZ";
unsigned char message[] = "secretsecretsecretsecretse______";

void main(void) {
    unsigned char hash[SHA256_DIGEST_LENGTH];
    unsigned char key[] = "haha\0";
    SHA256_CTX context;

    for (int i = 0; i < ALPHABET_SIZE; i++)
        for (int j = 0; j < ALPHABET_SIZE; j++)
            for (int k = 0; k < ALPHABET_SIZE; k++)
                for (int l = 0; l < ALPHABET_SIZE; l++)
                    for (int m = 0; m < VAR_NUM; m++) {
                        key[0] = message[KEY_OFFSET    ] = alphabet[i];
                        key[1] = message[KEY_OFFSET + 1] = alphabet[j];
                        key[2] = message[KEY_OFFSET + 2] = alphabet[k];
                        key[3] = message[KEY_OFFSET + 3] = alphabet[l];

                        printf("%s-", key);

                        sprintf(message + VAR_OFFSET, "%02d", m);
                    
                        SHA256_Init(&context);
                        SHA256_Update(&context, message, MESSAGE_SIZE);
                        SHA256_Final(hash, &context);

                        for (int n = 0; n < KEY_SIZE; n++)
                            key[n] = alphabet[hash[n] % ALPHABET_SIZE];
  
                        printf("%s\n", key);

                    }
}

Посчитать коллизии?