К примеру, в системе moodle, которая использовалась у нас в универе для тестирования студентов, ID ответов были инкрементными и сквозными на всю базу. Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса. В общем, проблем с тестами у нас не было. Потом они перешли на GUID, но я к тому моменту уже выпустился, хехе.
Давайте рассмотрим несколько способов генерации таких ограниченных по длине последовательностей от самых простых до криптографически стойких.
Кольцо вычетов
Точнее, мультипликативная группа кольца вычетов. На деле проще, чем звучит. Поясню картинкой:
Видите, степени тройки тут идут по порядку.
1, 2, 3, 4, 5, 6, а результат остатка от деления — нет
3, 2, 6, 4, 5, 1. Но всё равно в итоге все числа от 1 до 6 присутствуют.
7 называется модулем, а 3 — первообразным корнем (генератором). Чтобы это работало, модуль должен быть вида:
где p — простое число больше двух. Модули для нас — максимальные значения ID, которые мы можем сгенерить с их помощью.
Чем не подход для генерации псевдослучайных айдишек? Берем ID по порядку, возводим генератор в степень этой ID и берем остаток по модулю. Для достаточно больших модулей получится вполне себе.
Это, кстати, почти что Диффи Хэллман, только в масштабах поменьше. Кстати, те кто генерил ручками параметры DH для веб серверов, знают, что процесс это небыстрый. Именно потому, что искать первообразный корень для больших чисел непросто.
Линейный конгруэнтный метод
Популярная штука в качестве дефолтных генераторов случайных чисел во многих языках программирования, но абсолютно не криптостойкая. Вот её формула:
При правильно подобранных параметрах обеспечивает период равный m.
А если в качестве m выбрать простое число, то даже c можно выкинуть при определенных условиях, период будет максимальным или близким к нему.
Недостатки очевидны — нужно искать спец числа, да и не факт что они будут кратны размеру байта. Ну и предсказать следующий член последовательности, зная предыдущие, можно, это доказали математики.
Линейные регистры сдвига с обратной связью
Абсолютно замечательные конструкции, которые позволяют генерировать псевдослучайные последовательности путём перексоривания всего нескольких бит. Какие биты ксорить определяет многочлен, лежащий в основе LFSR. Если он примитивный, то последовательность получится максимальной.
Эти примитивные многочлены не так-то просто генерить, примерно как искать простые числа. Но нашлась таки отличная программка primpoly, которая умеет находить примитивные многочлены заданной степени. Даже может выводить списком все возможные примитивные многочлены если передать параметр -a, например, Primpoly.exe -a 2 64.
Если нам нужна ID размером в 8 байт, примерно как на Youtube, то вот самый минимальный полином x ^ 64 + x ^ 4 + x ^ 3 + x + 1.
Как им пользоваться:
У нас есть любое 64битное число кроме нуля. Мы ксорим между собой биты 64, 4, 3 и 1. Единица в полиноме означает, что число сдвигается вправо на 1 бит, а результат ксора помещается в старший бит.
Пример реализации на C:
bit = ((lfsr >> 0) ^ (lfsr >> 60) ^ (lfsr >> 61) ^ (lfsr >> 63) ) & 1;
lfsr = (lfsr >> 1) | (bit << 63);
Сдвиг на 0 дает нам бит 64, сдвиг на 1 бит 63 и т. д. Если этот код выполнять в бесконечном цикле, то мы в итоге придем к тому значению, с которого начинали.
А если прогнать число через несколько регистров с разными полиномами, то предсказать такую последовательность будет довольно сложно даже математически подкованным товарищам. Кстати, на принципе комбинации LFSR построены алгоритмы шифрования GSM трафика A5/1 и A5/2, правда их уже поломали, но тем не менее.
Минус такого подхода в том, что мы можем получать ID только последовательно, не зная заранее, какая будет «через одну». Поэтому переходим к следующему способу.
Обратимые функции
Или еще назовем их изоморфные. Вот тут вообще бесконечное количество вариантов, всё ограничивается вашей фантазией и желанием накрутить сложность процесса, результатом которого является ваша айдишечка.
К примеру, возьмем функции ?0 и ?1 из SHA-256, которые одному 32битному числу сопоставляют другое 32битное (f1 и f2 они называются в описании потокового шифра HC-128).
>>> это циклический сдвиг, >> это просто сдвиг вправо.
Вот цитата от товарищей, которые исследовали эти функции:
The ?0 and ?1 GF(2)- linear mappings are one to one (in order to check this property, we computed the 32x32 GF(2) matrices representing ?0 and ?1, and checked that the kernel of this matrix was restricted to the null vector).
Из неё понятно, что они изоморфны (one to one), можно самим не проверять. Мы даже можем обратную функцию не строить, просто все числа в цикле прогоняем через одну или другую, или обе, или пару раз одну, потом пару раз другую, ну вы поняли. И получаем все ID в диапазоне 32 бит в псевдослучайном порядке, о котором знаем только мы.
Таких функций напридумывать, как вы понимаете, можно базилион и комбинировать как угодно. Но пока что, это тоже не криптостойкий способ. Да и получить обратно, если нужно, оригинальную ID по-простому не получится.
Криптостойкая генерация последовательностей ID любого размера
Вы не поверите, но всё уже придумано за нас, я даже статью про это писал.
Только тут у нас не номера кредиток, а числа размером сколько нам нужно. От 16 до 192 бит с шагом в 1 бит для одного раунда алгоритма BPS. Мы берем основание системы такое какое нам нужно, не обязательно кратное 8. В алгоритме лимит на максимальное основание 65536, но ничто не мешает сделать больше, технически там в одну половинку сети фейстеля помещается 96 бит. Или вообще не извращаться, сделать основание 256 и просто шифровать столько байт сколько их в вашей айдишке.
Итак, настраиваем BPS на это основание, ключ для AES, IV(Tweak) и прогоняем все оригинальные ID от 1 до «основание системы — 1» через этот BPS. Потом то, что получилось оборачиваем в какой-нибудь base58 и вот вам готовая красивая айдишечка.
Нам даже хранить её не надо, мы можем её расшифровать и сопоставить оригинальной нормальной айдишке, бекенд вообще может не знать о том, что мы с ID извращаемся.
True random
Самый тру подход в плане криптостойкости (даже теоретически ничего не предсказать), но неудобен в хозяйстве. Каждую ID мы генерим абсолютно случайно какой-нибудь железкой и проверяем в базе, что такой еще нет и тогда пишем. Но это надо лезть в базу каждый раз, чтобы проверить, со временем генерация будет всё медленней и прочие проблемы.
Такие дела.
Комментарии (39)
VlastV
10.10.2016 12:40+1Для реализации псевдосоучайных идентификаторов можно использовать http://hashids.org реализованную на большинстве языков. Но она не совместима со словом «security» о чем честно написано в README
VlastV
10.10.2016 13:43В частности эта библиотека использовалась для передачи идентификатора пользователя для выбора шардирования, и идентификатора сущности.
yegreS
10.10.2016 13:08+1А чем не устроило использование GUID?
Scratch
10.10.2016 13:10+4Длинный же, хочется покороче. Гуиды обычно напоказ не выставляют, не красиво
Athari
11.10.2016 00:35+1Гуиды можно в алфавите побольше кодировать, например, с base-64 получится "80XQyRzi0EaXHbkuvCq4PA". Тоже длинно, но чуть менее ужасно, чем "c9d045f3-e21c-46d0-971d-b92ebc2ab83c". :)
PsyHaSTe
18.10.2016 12:07+1Из гуида лишнее можно просто вырезать. Учитывая что распределение бит равномерное и независимое, это никак не ослабляет его свойств.
MMik
10.10.2016 13:12+2True random надо предгенерировать на свободных машинах заранее, тогда клиенту не надо будет ждать лишний раз.
Scratch
10.10.2016 13:17Ради айдишек городить такую инфраструктуру, мне кажется, никто не будет, проще заюзать BPS. К тому же, у него есть один интересный побочный эффект — смена ключа мгновенно меняет все видимые ID на другие. Не уверен, что это прям крутое преимущество, но где-то может пригодиться, например чтоб кеши какие то сбросить
Nostr
10.10.2016 13:36+2Есть еще замечательные алгоритмы, наподобие Blum Blum Shub.
Он просто красив в своем исполнении. Доказано его сведение к Quadratic residuosity problem, что позволяет считать его криптографически стойким. + обладает возможностью получения произвольного элемента последовательности по номеру без вычисления предыдущих.
Скорость только не радует, но все-равно он шикарен.Scratch
10.10.2016 13:41Разве получится с его помощью генерить криптостойкие 32 или 64битные последовательности? Если будем брать не все биты, то не сможем восстановить оригинальный номер, а если брать маленькие простые числа, то их факторизовать можно чуть ли не на бумажке
Nostr
10.10.2016 14:18Числа нужно брать большие, чтобы получить криптостойкий результат. Почему мы не сможем восстановить оригинальный номер? В данном алгоритме последовательность получается из одного или нескольких наименее значащих бит каждого из чисел.
Scratch
10.10.2016 14:28+2Если я правильно прочитал вики, алгоритм позволяет узнать любой член последовательности из изначального состояния, но не наоборот. Т.е. условно, получив из ID = 5 её представление 2348203948, которое мы показываем пользователю, мы обратно сделать не сможем, придется где-то хранить это представление в дополнение к оригинальной ID.
vlreshet
10.10.2016 14:02Возможно меня заплюют, но чем плох банальный XOR sha-1 от текущего времени с точностью до миллисекунды, и sha-1 большого рандомного числа? Размером такого id? Просто насколько я понимаю — вероятность того что у двух юзеров в одну и ту же миллисекунду выпадут одинаковые рандомные числа — насколько ничтожна, что можно ей пренебречь.
Neuyazvimy1
11.10.2016 16:59Этот вариант очень хорош, мы в одном проекте который уже в продакшене используем такой метод.
string = userId + getLongTime + SecureRandom.(«seed»);
secureStr = encodeBase64(string)
На выходе получаем что-то типа этого "[B@43a53fe7" и коротко и очень быстро генерит (мы так генерим токены авторизации)
bluetooth
10.10.2016 14:47+3Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса
Объясните логику пожалуйста.Scratch
10.10.2016 14:49+1Ленивые преподы сначала заводили в админке правильный ответ, а потом неправильные, у правильного ID была наименьшей. Потом в исходнике страницы просто смотрели какой из вариантов ответа наименьший, он чаще всего и был правильным
DistortNeo
10.10.2016 20:51+1Я так тест на уроке истории в школе взломал, причём в докомпьютерную эпоху. Просто обратил внимание, что значения правльных ответов (годы событий) идут в строго возрастающем порядке, что сильно сократило количество возможных вариантов ответов для вопросов.
dom1n1k
10.10.2016 16:15Мне вот еще интересно, как генерировать такие строковые id, если наложены дополнительные ограничения для человекочитаемости — например, отсутствие в итоговой строке буквы «l», поскольку она похожа на единицу. Тупо проверять и перегенерировать, если что?
Scratch
10.10.2016 16:28+2Должно быть просто, если использовать подход с алгоритмом BPS из предыдущей статьи.
Если делать всё честно, то:
1) Определяете свой алфавит, его размер будет основанием системы счисления, base
2) Определяете сколько символов у вас будет в айдишке Назовем длину len. Если 10, то максимальная айдишка это base^10 -1.
3) Заводите массив интов, размером с len, но в котором значения могут быть лишь в диапазоне 0..base-1
Всё, основа готова. Зашифрованный массив получится такой же длины, а значения в нём будут индексами букв из вашего алфавита.
Чтобы получить следующее значение, вам нужно инкрементнуть массив, это делается буквально двумя строчками кода
func increment(counter []byte, base int) { for i := len(counter) - 1; i >= 0; i-- { counter[i] = (counter[i] + 1) % base if counter[i] != 0 { break } } }
Но вообще, вся эта свистопляска с основаниями нужна по сути только в части вывода при шифровани и ввода при зашифровывании. Внутри там всё равно используется bigInt, если немного подковырять, можно работать напрямую с ним, минуя ненужные преобразования.
И если всё сделать правильно, получится преобразование ID -> ваш алфавит и обратно безо всяких лишних проверок
sheknitrtch
10.10.2016 16:53+1К стати, можно воспользоваться библиотекой humanhash и сконвертировать полученные страшные хеши в последовательности английских слов для лучшего запоминания.
DistortNeo
10.10.2016 20:47Эх, криптографы…
Проблема криптостойкости генераторов случайных чисел уже обсуждалась и не раз. Почитайте, например, вот эту публикацию и не изобретайте велосипеды:
https://habrahabr.ru/company/mailru/blog/273147/
Естественно, никаких маппингов из коротких последовательных ID в длинные быть не должно — они заведомо ненадёжны. Только True Random.
Каждую ID мы генерим абсолютно случайно какой-нибудь железкой и проверяем в базе, что такой еще нет и тогда пишем. Но это надо лезть в базу каждый раз, чтобы проверить, со временем генерация будет всё медленней и прочие проблемы.
Я бы не назвал это проблемой. Потому что вероятность коллизии (повторения значения 64-битного счётчика) будет крайне мала. Не получилось вставить строку в базу из-за уже существующего ключа — не вопрос, сгенерировали новый, на производительности это не скажется ну вообще никак.
Либо другой вариант генерации ID: просто прибавлять к текущему значению счётчика случайное значение в достаточно большом диапазоне. Тогда проверять на совпадение ID не нужно будет.Scratch
10.10.2016 20:58При чем тут криптостойкость ГПСЧ? ГПСЧ абсолютно не обязательно генерируют неповторяющиеся последовательности, а статья как раз про них.
Цель статьи показать, что генерировать неповторяющиеся числа не по порядку можно разными способами и абсолютно не обязательно далать это криптостойко. Но можно и упороться, про это как раз два последних способа.DistortNeo
10.10.2016 21:20-1Цель статьи показать, что генерировать неповторяющиеся числа не по порядку можно разными способами и абсолютно не обязательно далать это криптостойко.
При том, что вы несколько раз в статье указывали на важность невозможности последовательного перебора значений ID.Scratch
10.10.2016 21:28я писал в заголовке
предотвратить или хотя бы затруднить возможность прямого перебора значений
Все описанные в статье способы как минимум затрудняют прямой перебор значений просто потому что идут не по порядку, как максимум делают это криптостойкими способами. Что не так то?DistortNeo
11.10.2016 01:04-1Все описанные в статье способы как минимум затрудняют прямой перебор значений просто потому что идут не по порядку
Про «security through obscurity» уже писали. Для школьных тестов сойдёт, для банковских операций — увы, нет.
Что не так то?
Что криптостойкий и простой в реализации метод почему-то не оказывается предпочтительным.Scratch
11.10.2016 01:13+4Я ни один из методов не рекомендую, я просто о них рассказал, а какой из них предпочтительней решать разработчикам. Разве где-то написано «генерим ID для банковских транзакций»? Я еще раз напоминаю, статья о том, что есть много абсолюто разных способов решать одну и ту же задачу — генерировать числа не по порядку без повторений.
Aquahawk
Надеюсь вы понимаете, что:
Полностью убивает идею
Это называется security through obscurity и не является защитой вообще. Либо алгоритма генерации нет вообще(с допуском на качество рандом генератора) и вы храните в своей базе, либо это можно перебирать, только способ перебора сходу не очевиден. Насколько важно на самом деле защитить от перебора? Если не важно совсем то можно открытый id показывать, если хоть сколько то важно, то надо защищать нормально.
EDIT:
Мать моя женщина, это секьюрити компания написала.
Scratch
При чем тут security through obscurity? Я могу в открытую опубликовать алгоритм шифрования ID, но ключ останется у меня. И это никак не ослабит защиту от прямого перебора. Хочется перебирать все возможные варианты — никто не запрещает, но по порядку это сделать не получится, придется шерстить весь диапазон.
Aquahawk
Да, с BPS будет нормально, согласен. Из предложенных методов безопасен первый и последний. Возможно стоит в статье сделать какой-то доп акцент на это.
Scratch
А там написано «от самых простых до криптографически стойких». Чтобы больше не было путаницы, перенес random в конец
mayorovp
Там все способы безопасны при достаточном размере диапазона и случайных параметрах. Просто варианты с шифрованием и истинным радномом достаточно защищены "от дурака".
ittakir
Статья хорошая, применение — хотя бы даже генерировать номера скрэтч-карт для оплаты чего-либо.