Тема немного веселая, по этому не в алгоритмы.

Подробности: https://habrahabr.ru/post/324772/

Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе. Конкуренты могут делать фейковые записи с целью получить n ID-ов, идущих подряд.

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

Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?

Здравствуйте, ·, Вы писали:

S>>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
O>>последовательные номера + сильное шифрование, не?
·>По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт.
Нет, не нужно. Старый добрый RC5 прекрасно работает с блоками по 32 бита — его защищённость зависит от длины ключа, которая для RC5 может быть от 64 бит до 128 бит.

То есть, мы можем взять обычный int32 и получить зашифрованный int32. Причём шифрование будет невзламываемым разумными мерами. Есть некоторые related-text атаки из-за малого размера шифртекста, но они будут требовать знать достаточно большой кусок ключевого пространства и не дадут сильного выигрыша.

Далее останется только сузить int32 до 676 миллионов. Самый простой подход — https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_cycle_walking

# x - чистое значение счётчика, 0<X<676000000
CycleWalkingFPE(x)
{
   if encrypt(x) < 676000000
     return encrypt(x)
   else 
     return CycleWalkingFPE(encrypt(x))
}

Тот же самый код и для расшифровки.

Ну и генерация нового ID сводится к взятию следующего значения. Я недавно переключил пару систем в Амазоне на такой подход

Здравствуйте, Shmj, Вы писали:

C>>Более интересное решение — использовать "Format Preserving Encryption". Стандартов на него пока нет, но вручную достаточно легко реализуется "cycle-walking". Делаем счётчик в 32 бита, затем берём RC5 с размером блока в 32 бита, шифруем значение и делаем cycle-walking пока оно не поместится в 676 миллионов (в среднем 8 шагов, ерунда).
S>А как вам мой алгоритм: http://rsdn.org/forum/etude/6740933.1

Автор: Shmj
Дата: 29.03.17

S>?
Поздравляю, вы изобрели сеть Фейстеля с HMAC в качестве раундовой функции

Это вполне разумный подход: https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_a_Feistel_network

Насчёт стойкости, двух раундов может быть недостаточно, так что я тупо добавил бы ещё несколько раундов туда (просто повторять процесс несколько раз). Ну и 22 бита — это немного не по условию задачи, так как не покрывает всего ключевого пространства (29 бит — наиболее близкое значение).

AG>XX000000
AG>26*26*1000000 = 676000000 ключей
AG>676000000 / 8 = 84 500 000 байт битмапка заюзаных.
Ну битмапка с моей колокольни — частный случай БД.

AG>а с шифрованием бы не связывался, потому что что будешь делать, если ключ утёк.
Ну вероятность утекания ключа в данном случае я бы оценил примерно так же как вероятность утекания сведений, которые с его помощью можно спереть — то есть количество клиентов. Так что это не релевантная проблема.

AG>вот у нас счётчик заюзаных, хороший рандом, чтобы выход в диапазоне [0..счётчик-1], и один линейный проход по битмапке, который из выхода рандома получает реальный новый ключ.
А по поводу защиты от мегахакеров, которым прям так хочется знать сколько у вас клиентов и все на этом, думаю что стойкость данной системы при использовании любого рандома упрется в криптостойкость этого самого рандома.

Здравствуйте, ononim, Вы писали:

O>последовательные номера + сильное шифрование, не?

Надо ещё проверить, что не совпало ни с одним из предыдущих. А если совпало — перегенерить и снова проверять. Если почти все логины заняты — это может быть долго. Чуть быстрее — хранить в массиве все уже розданные логины в упорядоченном виде, после шифрования брать остаток от деления на количество свободных логинов, бинарным поиском находить, в какой из промежутков новый логин попал, и вычислять, чему он теперь равен. После этого нужно его вставить в этот упорядоченный массив, но это стоит столько же, сколько стоит один раз проверить на совпадение перебором. Если O(m) недопустимо, то хранить розданные логины в бинарном сбалансированном дереве с порядковой статистикой (количество узлов со значениями меньше текущего), тогда всё обойдётся в O(log(m)), с константой порядка шести 32-битных элементов на запись. Надо быть готовым, что конкуренты забьют почти все номера, то есть держать файл на примерно 16 гигов. Опять же, если они сразу забьют все номера кроме последнего, то они будут точно знать, чему равен этот последний
Вот только какой смысл? Тогда не получится написать в резюме, что работал с BigData.

Здравствуйте, Shmj, Вы писали:

S>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?

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

Здравствуйте, ononim, Вы писали:

O>Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.

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

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

Внимательно статью читать лень.

S>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
последовательные номера + сильное шифрование, не?

O>>последовательные номера + сильное шифрование, не?
C>Надо ещё проверить, что не совпало ни с одним из предыдущих. А если совпало — перегенерить и снова проверять.
Шифрование != хэширование. Проверять ничего не нужно. Достаточно последовательного инкремента исходных данных. Это конечно если считать что никогда не наступит переполнения и изымания/реюзания предыдущих ид-шников, в таком случае придется таки скатиться к БД.

Здравствуйте, ononim, Вы писали:

O>>>последовательные номера + сильное шифрование, не?
C>>Надо ещё проверить, что не совпало ни с одним из предыдущих. А если совпало — перегенерить и снова проверять.
O>Шифрование != хэширование. Проверять ничего не нужно. Достаточно последовательного инкремента исходных данных. Это конечно если считать что никогда не наступит переполнения и изымания/реюзания предыдущих ид-шников, в таком случае придется таки скатиться к БД.

Ну зачем БД.

XX000000

26*26*1000000 = 676000000 ключей

676000000 / 8 = 84 500 000 байт битмапка заюзаных.

вот у нас счётчик заюзаных, хороший рандом, чтобы выход в диапазоне [0..счётчик-1], и один линейный проход по битмапке, который из выхода рандома получает реальный новый ключ.

а с шифрованием бы не связывался, потому что что будешь делать, если ключ утёк.

Здравствуйте, ononim, Вы писали:

S>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
O>последовательные номера + сильное шифрование, не?
По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт. Т.е. по нескольким последовательным значениям будет реально взломать ключ и угадывать следующие.
Самый жизнеспособный вариант — выбирать случайно, проверять на дупликат (выбор по хеш-таблице) — и повторять, если уже использован.
В случае когда количество занятых логинов будет велико, т.е. выберется почти всё пространство — количество повторов может сильно возрасти — проще всего увеличить количество значений. Если это невозможно расширить — создать и перемешать табличку оставшихся логинов, она будет небольшой на том этапе, по крайней мере значительно меньше, чем остальная база пользователей.
Можно держать пул (можно даже распределённый) свободных логинов, если требуется переживать пиковые нагрузки.

Alexander G, Вы писали:

AG>676000000 / 8 = 84 500 000 байт битмапка заюзаных.
Это просто "повезло" с требованием. А завтра понадобится формат XXX0000000X для номеров заказов и битмапка ВНЕЗАПНО станет терабайтной.

S>>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
O>>последовательные номера + сильное шифрование, не?
·>По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт. Т.е. по нескольким последовательным значениям будет реально взломать ключ и угадывать следующие.
Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.

Здравствуйте, ononim, Вы писали:

S>>>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
O>>>последовательные номера + сильное шифрование, не?
O>·>По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт. Т.е. по нескольким последовательным значениям будет реально взломать ключ и угадывать следующие.
O>Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.
Да, ты прав. Возможно.
Но я бы в данном случае всё равно бы такое не использовал, т.к. есть три проблемы — придётся обеспечивать хранение секрета, невозможно этот секрет менять позже, невозможно расширять пространство значений при необходимости.

Здравствуйте, Shmj, Вы писали:

S>Тема немного веселая, по этому не в алгоритмы.

S>Подробности: https://habrahabr.ru/post/324772/



а вообще, как эта задача решается? почему нельзя просто генерить эту последовательно на лету, при регистрации пользователя?

Здравствуйте, Shmj, Вы писали:

Взять GIUD (если кому мало — два), зашифровать случайным ключом (третьим GIUD-ом), взять средние n байт, преобразовать в нужный формат, проверить на дубли. Всё.

Здравствуйте, ononim, Вы писали:

O>Шифрование != хэширование. Проверять ничего не нужно. Достаточно последовательного инкремента исходных данных. Это конечно если считать что никогда не наступит переполнения и изымания/реюзания предыдущих ид-шников, в таком случае придется таки скатиться к БД.

Не совсем. К примеру, у нас есть шифр с 64-битными блоками. Ну, например, DES. Если кормить его счетчиком, получим псевдослучайную последовательность чисел в диапазоне от 0 до 18446744073709551615 без повторов. А нам, к примеру, надо от 0 до 9999999. Следовательно, DES не очень-то подходит, слишком много неподходящих ответов он будет выдавать.

Заметим, что если отрезать от DES'а лишние биты, то последовательность остается псевдослучайной, но теряется гарантия неповторяемости.

Я бы взял шифр с длинной блока N такой, что 2^N-1 не меньше верхней границы диапазона, в который надо попасть, а 2^(N-1) — 1 уже меньше. Кормил бы его счетчиком и отбрасывал неподходящие значения — их не больше половины, потому что мы так выбрали размер блока.

Вопрос в том, где взять шифр с нужной (произвольной) длинной блока. Я думаю, этот вопрос имеет ответ, но этим пришлось бы заниматься.

Здравствуйте, wildwind, Вы писали:

W>Взять GIUD (если кому мало — два), зашифровать случайным ключом (третьим GIUD-ом), взять средние n байт, преобразовать в нужный формат, проверить на дубли. Всё.

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

Во-вторых, проверка на дубли может оказаться дорогим удовольствием.

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

Здравствуйте, Shmj, Вы писали:

S>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
Эээ, а с каких пор жалкие 700 миллионов стало бигдатой? Я думал, что детская бигдата начинается с 700 миллиардов, объемы данных — петабайты, и это еще хорошо и оптимально упакованные данные.

А тут, если особо не заморачиваться. Тупо рандом из диапазона и складывание результата в массив булевых переменных не прокатит? Под массив из 700 миллионов булевых нужно 87 мегабайт, объем детский. Если n раз рандом (допустим N = 100) не получился плюс инкрементом от рандома (пусть еще n раз) всегда попадаем на уже сгенерированный номер, значит мы диапазон довольно неплохо забили. Это случится наверно лет через 100 . Через 100 лет, если вдруг понадобится далее, пробегаем по всему массиву линейно и там, где остались пустые — перекладываем индексы уже в массив от целых индексов в первом массиве. Линейно прогон этих жалких 87 мегабайт будет занимать доли секунды, и это 1 раз только нужно будет делать. Далее массив на 97 мегабайт освобождаем, он уже не нужен, и просто последовательно выбираем элементы из оставшегося массива.

Здравствуйте, Pzz, Вы писали:

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

У нас не стоит задача получить все возможные варианты.

Pzz>Во-вторых, проверка на дубли может оказаться дорогим удовольствием.

С чего бы?

Pzz>В-третьих, когда большая часть значений уже использована, каждое следущее с очень большой вероятностью будет дублем, и найти следущее уникальное значение будет все сложнее и сложнее.

Если проект доживет до этой стадии, длину ID можно расширить. Можно заранее.

Здравствуйте, ononim, Вы писали:

O>Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.

Ну а если попытаться без экзотических алгоритмов, по простому.

Предлагаю такой алгоритм.

Имеем:

1. Секретный ключ для HMAC SHA1 (без разницы, можно и MD5).
2. Номера пользователей в базе по порядку, наверх отдаем криптопреобразование.

Делаем:
1. Номер пользователя представляем в виде 16+6=22 бит. Это с запасом.
2. Условно делим 22 бита на 2 группы по 11 бит.

Для шифрования:
1. Делаем HMAC правой части (от правых 11 бит) с секретным ключом. Получаем ХЕШ 1. Хеш 1 пользователь получить не сможет, так как у него нет секретного ключа.
2. Накладываем XOR-ом получившийся ХЕШ 1 на левые 11 бит.
3. Делаем HMAC левых 11 бит (которые уже XOR-нутые) с секретным ключом. Получаем ХЕШ 2. Т.к. у пользователя нет секретного ключа, то он не может сделать обратное преобразование.
4. Накладываем XOR-ом ХЕШ 2 на правые 11 бит.

Обратная бадяга:

1. Делаем ХЕШ 2 из левых 11 бит (HMAC с ключом).
2. Опять XOR-ом накладываем на правую часть.
3. Делаем HMAC правой части, это хеш 1.
4. Накладываем XOR-ом на левую часть.

Есть вероятность что после XOR-а число будет чуть больше чем требуется (но менее чем на 1 бит). С этим можно что-то сделать (типа по модулю значение взять), но хотелось бы улышать другое:

Где я прокололся?

Здравствуйте, Shmj, Вы писали:

S>Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе. Конкуренты могут делать фейковые записи с целью получить n ID-ов, идущих подряд.
Самое тупое — взять список всех ID, перемешать их и сохранить в файл. Это будет порядка пары гигабайт (всего 676 миллионов вариантов).

Более интересное решение — использовать "Format Preserving Encryption". Стандартов на него пока нет, но вручную достаточно легко реализуется "cycle-walking". Делаем счётчик в 32 бита, затем берём RC5 с размером блока в 32 бита, шифруем значение и делаем cycle-walking пока оно не поместится в 676 миллионов (в среднем 8 шагов, ерунда).

Телемаркет.

В качестве бонуса, алгоритм реверсируемый — можно взять зашифрованный ID и получить исходное значение счётчика.

S>Где я прокололся?
Честно говоря разбираться лень, но знаю точно что если вы не математик с уклоном в криптографию то лучше свои криптоалгоритмы не сочинять, а использовать то что сочинили математики.

Здравствуйте, Shmj, Вы писали:

S> Где я прокололся?
Не понял как ты гарантируешь, что сгенерённые таким образом значения будут уникальны. Использование хеша однозначно говорит о том, что могут быть коллизии.

S>>Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе. Конкуренты могут делать фейковые записи с целью получить n ID-ов, идущих подряд.
C>Самое тупое — взять список всех ID, перемешать их и сохранить в файл. Это будет порядка пары гигабайт (всего 676 миллионов вариантов).
Если что это тоже по сути шифрование, такая себе разновидность "одноразового блокнота".

Здравствуйте, ononim, Вы писали:

S>>Где я прокололся?
O>Честно говоря разбираться лень, но знаю точно что если вы не математик с уклоном в криптографию то лучше свои криптоалгоритмы не сочинять, а использовать то что сочинили математики.

Нет уж, в этюдах давайте разберемся

Здравствуйте, ·, Вы писали:

S>> Где я прокололся?
·>Не понял как ты гарантируешь, что сгенерённые таким образом значения будут уникальны. Использование хеша однозначно говорит о том, что могут быть коллизии.

Уникальность хеша не требуется -- он используется только как ключ для операции XOR.

Здравствуйте, Cyberax, Вы писали:

C>Более интересное решение — использовать "Format Preserving Encryption". Стандартов на него пока нет, но вручную достаточно легко реализуется "cycle-walking". Делаем счётчик в 32 бита, затем берём RC5 с размером блока в 32 бита, шифруем значение и делаем cycle-walking пока оно не поместится в 676 миллионов (в среднем 8 шагов, ерунда).

А как вам мой алгоритм: http://rsdn.org/forum/etude/6740933.1

Автор: Shmj
Дата: 29.03.17

?

S>>>Где я прокололся?
O>>Честно говоря разбираться лень, но знаю точно что если вы не математик с уклоном в криптографию то лучше свои криптоалгоритмы не сочинять, а использовать то что сочинили математики.
S>Нет уж, в этюдах давайте разберемся
Ну поскольку добрые люди ваш метод идентифицировали

Автор: Cyberax
Дата: 30.03.17

, то вот вам новое чтиво, на предмет known plain text атак на него

Здравствуйте, Cyberax, Вы писали:

C>Ну и 22 бита — это немного не по условию задачи, так как не покрывает всего ключевого пространства (29 бит — наиболее близкое значение).

Ага, 29.

100000 * 26 * 26 = 101000 01001010 11110001 00000000

Но идея та же...

Здравствуйте, Pzz, Вы писали:

Pzz>В-третьих, когда большая часть значений уже использована, каждое следущее с очень большой вероятностью будет дублем, и найти следущее уникальное значение будет все сложнее и сложнее.

Когда мы используем более половины возможных кодов, мы сразу можем заменить базу использованных на базу ещё не использованных...

S>Ага, 29.

понимаю как они считали. На земле ~10 миллиардов людей, log₂ (10⁹) ≈ 29

хотя log₂ (100000 * 26 * 26) ≈ 26

Здравствуйте, Shmj, Вы писали:

S>Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе.

Запихать время в ИД?

Здравствуйте, Shmj, Вы писали:

S>Где я прокололся?

Очень похоже на

Т.е. делим шифруемые данные пополам (l, r), (l ^ f(r), r) и переставляем местами: (r, l ^ f(r))
f — криптографическая функция, не обязательно обратимая.
Для стойкой функции f достаточно трех итераций. Работает и для битовых данных, и для десятичных данных.
В качестве f можно взять HMAC и обрезать результат до нужного размера.