Генерируем псевдослучайные ID а-ля Youtube

    Привет, %username%! Бывает необходимо генерировать ID не подряд, причем чтобы они гарантированно не повторялись. На youtube это используется для того, чтобы вы не могли брутфорсом получить все новые и старые видосики, так же это не редкость на разных файлообменниках и вообще везде где нужно предотвратить или хотя бы затруднить возможность прямого перебора значений.


    К примеру, в системе moodle, которая использовалась у нас в универе для тестирования студентов, ID ответов были инкрементными и сквозными на всю базу. Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса. В общем, проблем с тестами у нас не было. Потом они перешли на GUID, но я к тому моменту уже выпустился, хехе.

    Давайте рассмотрим несколько способов генерации таких ограниченных по длине последовательностей от самых простых до криптографически стойких.

    Кольцо вычетов


    Точнее, мультипликативная группа кольца вычетов. На деле проще, чем звучит. Поясню картинкой:

    image

    Видите, степени тройки тут идут по порядку.
    1, 2, 3, 4, 5, 6, а результат остатка от деления — нет
    3, 2, 6, 4, 5, 1. Но всё равно в итоге все числа от 1 до 6 присутствуют.

    7 называется модулем, а 3 — первообразным корнем (генератором). Чтобы это работало, модуль должен быть вида:
    image

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

    Чем не подход для генерации псевдослучайных айдишек? Берем ID по порядку, возводим генератор в степень этой ID и берем остаток по модулю. Для достаточно больших модулей получится вполне себе.

    Это, кстати, почти что Диффи Хэллман, только в масштабах поменьше. Кстати, те кто генерил ручками параметры DH для веб серверов, знают, что процесс это небыстрый. Именно потому, что искать первообразный корень для больших чисел непросто.

    Линейный конгруэнтный метод


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

    image

    При правильно подобранных параметрах обеспечивает период равный 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).

    image
    image

    >>> это циклический сдвиг, >> это просто сдвиг вправо.

    Вот цитата от товарищей, которые исследовали эти функции:
    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 мы генерим абсолютно случайно какой-нибудь железкой и проверяем в базе, что такой еще нет и тогда пишем. Но это надо лезть в базу каждый раз, чтобы проверить, со временем генерация будет всё медленней и прочие проблемы.

    Такие дела.
    Virgil Security, Inc.
    Мы превращаем программистов в криптографов.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 41

      0
      Надеюсь вы понимаете, что:
      Нам даже хранить её не надо, мы можем её расшифровать и сопоставить оригинальной нормальной айдишке, бекенд вообще может не знать о том, что мы с ID извращаемся.

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

      Это называется security through obscurity и не является защитой вообще. Либо алгоритма генерации нет вообще(с допуском на качество рандом генератора) и вы храните в своей базе, либо это можно перебирать, только способ перебора сходу не очевиден. Насколько важно на самом деле защитить от перебора? Если не важно совсем то можно открытый id показывать, если хоть сколько то важно, то надо защищать нормально.

      EDIT:
      Мать моя женщина, это секьюрити компания написала.
        +6
        При чем тут security through obscurity? Я могу в открытую опубликовать алгоритм шифрования ID, но ключ останется у меня. И это никак не ослабит защиту от прямого перебора. Хочется перебирать все возможные варианты — никто не запрещает, но по порядку это сделать не получится, придется шерстить весь диапазон.
          0
          Да, с BPS будет нормально, согласен. Из предложенных методов безопасен первый и последний. Возможно стоит в статье сделать какой-то доп акцент на это.
            0
            А там написано «от самых простых до криптографически стойких». Чтобы больше не было путаницы, перенес random в конец
              0

              Там все способы безопасны при достаточном размере диапазона и случайных параметрах. Просто варианты с шифрованием и истинным радномом достаточно защищены "от дурака".

            +2
            Статья хорошая, применение — хотя бы даже генерировать номера скрэтч-карт для оплаты чего-либо.
            +1
            Для реализации псевдосоучайных идентификаторов можно использовать http://hashids.org реализованную на большинстве языков. Но она не совместима со словом «security» о чем честно написано в README
              0
              В частности эта библиотека использовалась для передачи идентификатора пользователя для выбора шардирования, и идентификатора сущности.
              +1
              А чем не устроило использование GUID?
                +4
                Длинный же, хочется покороче. Гуиды обычно напоказ не выставляют, не красиво
                  +1

                  Гуиды можно в алфавите побольше кодировать, например, с base-64 получится "80XQyRzi0EaXHbkuvCq4PA". Тоже длинно, но чуть менее ужасно, чем "c9d045f3-e21c-46d0-971d-b92ebc2ab83c". :)

                    +1
                    Из гуида лишнее можно просто вырезать. Учитывая что распределение бит равномерное и независимое, это никак не ослабляет его свойств.
                +2
                True random надо предгенерировать на свободных машинах заранее, тогда клиенту не надо будет ждать лишний раз.
                  0
                  Ради айдишек городить такую инфраструктуру, мне кажется, никто не будет, проще заюзать BPS. К тому же, у него есть один интересный побочный эффект — смена ключа мгновенно меняет все видимые ID на другие. Не уверен, что это прям крутое преимущество, но где-то может пригодиться, например чтоб кеши какие то сбросить
                    0

                    Не надо ничего ждать. Псевдослучайного CRNG достаточно.

                    +2
                    Есть еще замечательные алгоритмы, наподобие Blum Blum Shub.
                    Он просто красив в своем исполнении. Доказано его сведение к Quadratic residuosity problem, что позволяет считать его криптографически стойким. + обладает возможностью получения произвольного элемента последовательности по номеру без вычисления предыдущих.
                    Скорость только не радует, но все-равно он шикарен.
                      0
                      Разве получится с его помощью генерить криптостойкие 32 или 64битные последовательности? Если будем брать не все биты, то не сможем восстановить оригинальный номер, а если брать маленькие простые числа, то их факторизовать можно чуть ли не на бумажке
                        0
                        Числа нужно брать большие, чтобы получить криптостойкий результат. Почему мы не сможем восстановить оригинальный номер? В данном алгоритме последовательность получается из одного или нескольких наименее значащих бит каждого из чисел.
                          +2
                          Если я правильно прочитал вики, алгоритм позволяет узнать любой член последовательности из изначального состояния, но не наоборот. Т.е. условно, получив из ID = 5 её представление 2348203948, которое мы показываем пользователю, мы обратно сделать не сможем, придется где-то хранить это представление в дополнение к оригинальной ID.
                            0
                            А, вот вы о чем. Я понял. Да, хранить придется видимо…
                              0
                              а еще, я так понимаю, не факт, что они не повторятся, еще и на повторы надо смотреть
                      0
                      Возможно меня заплюют, но чем плох банальный XOR sha-1 от текущего времени с точностью до миллисекунды, и sha-1 большого рандомного числа? Размером такого id? Просто насколько я понимаю — вероятность того что у двух юзеров в одну и ту же миллисекунду выпадут одинаковые рандомные числа — насколько ничтожна, что можно ей пренебречь.
                        0
                        Размерчик, да. Желательно, чтобы ID поместилась хотя бы в int64
                          0
                          Ну свернуть криптостойким хешом то можно до любого размера, в любом случае вероятность пересечения будет зависеть от размера id.
                            +1
                            т. е. все равно надо будет смотреть, не пересекается ли. А это уже можно свести к последнему варианту
                          0
                          Этот вариант очень хорош, мы в одном проекте который уже в продакшене используем такой метод.
                          string = userId + getLongTime + SecureRandom.(«seed»);
                          secureStr = encodeBase64(string)
                          На выходе получаем что-то типа этого "[B@43a53fe7" и коротко и очень быстро генерит (мы так генерим токены авторизации)
                            –1
                            SecureRandom=42 или меняется для каждого нового токена?
                          +3
                          Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса

                          Объясните логику пожалуйста.
                            +1
                            Ленивые преподы сначала заводили в админке правильный ответ, а потом неправильные, у правильного ID была наименьшей. Потом в исходнике страницы просто смотрели какой из вариантов ответа наименьший, он чаще всего и был правильным
                              +1
                              Я так тест на уроке истории в школе взломал, причём в докомпьютерную эпоху. Просто обратил внимание, что значения правльных ответов (годы событий) идут в строго возрастающем порядке, что сильно сократило количество возможных вариантов ответов для вопросов.
                                +3

                            0
                            Мне вот еще интересно, как генерировать такие строковые id, если наложены дополнительные ограничения для человекочитаемости — например, отсутствие в итоговой строке буквы «l», поскольку она похожа на единицу. Тупо проверять и перегенерировать, если что?
                              +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 -> ваш алфавит и обратно безо всяких лишних проверок
                              +1
                              К стати, можно воспользоваться библиотекой humanhash и сконвертировать полученные страшные хеши в последовательности английских слов для лучшего запоминания.
                                0
                                Только надо помнить, что если «страшные хеши» сконвертировать библиотекой humanhash, то разным «страшным хешам» могут соответствовать _одинаковые_ последовательности английских слов, т.к. humanhash — это хеширование, в котором байты бьются на блоки и каждый блок ужимается до одного байта операцией xor, а потом эти байты по таблицам заменяются на слова.
                                0
                                Эх, криптографы…

                                Проблема криптостойкости генераторов случайных чисел уже обсуждалась и не раз. Почитайте, например, вот эту публикацию и не изобретайте велосипеды:
                                https://habrahabr.ru/company/mailru/blog/273147/

                                Естественно, никаких маппингов из коротких последовательных ID в длинные быть не должно — они заведомо ненадёжны. Только True Random.

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

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

                                Либо другой вариант генерации ID: просто прибавлять к текущему значению счётчика случайное значение в достаточно большом диапазоне. Тогда проверять на совпадение ID не нужно будет.
                                  0
                                  При чем тут криптостойкость ГПСЧ? ГПСЧ абсолютно не обязательно генерируют неповторяющиеся последовательности, а статья как раз про них.
                                  Цель статьи показать, что генерировать неповторяющиеся числа не по порядку можно разными способами и абсолютно не обязательно далать это криптостойко. Но можно и упороться, про это как раз два последних способа.
                                    –1
                                    Цель статьи показать, что генерировать неповторяющиеся числа не по порядку можно разными способами и абсолютно не обязательно далать это криптостойко.

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


                                      Все описанные в статье способы как минимум затрудняют прямой перебор значений просто потому что идут не по порядку, как максимум делают это криптостойкими способами. Что не так то?
                                        –1
                                        Все описанные в статье способы как минимум затрудняют прямой перебор значений просто потому что идут не по порядку

                                        Про «security through obscurity» уже писали. Для школьных тестов сойдёт, для банковских операций — увы, нет.

                                        Что не так то?

                                        Что криптостойкий и простой в реализации метод почему-то не оказывается предпочтительным.
                                          +4
                                          Я ни один из методов не рекомендую, я просто о них рассказал, а какой из них предпочтительней решать разработчикам. Разве где-то написано «генерим ID для банковских транзакций»? Я еще раз напоминаю, статья о том, что есть много абсолюто разных способов решать одну и ту же задачу — генерировать числа не по порядку без повторений.

                                Only users with full accounts can post comments. Log in, please.