[Техпоп] Обфускация инкрементальных идентификаторов с помощью модульного умножения

Сегодня будем обфусцировать! Это продолжение моего прошлого поста про инкрементальные идентификаторы. Здесь я расскажу, как можно преобразовать обычные инкрементальные последовательности целых чисел в псевдослучайные последовательности с помощью модульного умножения и как преобразовать их обратно с помощью модульной мультипликативной инверсии.

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

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

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

Обфускация

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

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

Модульное умножение

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

Это умножение:

x * y

По английски умножение — это multiplication, поэтому явления, связанные с умножением, часто называются мультипликативными.

Это вычисление остатка от деления:

x % y

По английски это называется modulo, поэтому явления, связанные с этой операцией, называются модульными.

Это определение мультипликативной инверсии:

Мультипликативная инверсия числа x - это такое число y, что x * y = 1

Например, 5 * 0.2 = 1. 0.2 — это мультипликативная инверсия для 5.

Теперь переходим от школьной математики к не школьной.

Это модульное умножение (modular multiplication):

(x * y) % m

Оно как обычное умножение, только потом берем остаток от деления на m.

Это определение модульной мультипликативной инверсии (modular multiplicative inverse, MMI):

Модульная мультипликативная инверсия для чисел x и m - это такое число y, что (x * y) % m = 1

И тут уже не все так просто.

Во-первых, не для любых x и m можно найти такое число y. Чтобы модульная мультипликативная инверсия гарантировано существовала, x и m должны быть больше нуля и взаимно простыми, т.е. их наибольший общий делитель (НОД) должен быть равен 1. Например, числа 10 и 15 не взаимно простые — оба делятся на 5. А числа 5 и 16 — да.

Во-вторых, таких инверсий может быть несколько (или даже бесконечное число). Так как мы имеем дело с остатком от деления, у нас по сути циклический результат. 5%10=5, 15%10=5, 25%10=5… Например, для чисел 5 и 16 модульная мультипликативная инверсия — это 13, 29, 45 и так далее.

Подробнее об этой инверсии можно почитать тут (на английском).

А использовать это как?

Нахрена нам вообще сдались эти модульное умножение и модульная мультипликативная инверсия? У модульного умножения есть одно важное и очень полезное свойство: если x и m взаимно простые (а нас только такие случаи и интересуют), то для любого числа y от 1 до m-1 модульное умножение даст нам уникальный результат, который меньше m. Возьмем, например, все те же 5 и 16. Тогда выражение для модульного умножения будет таким:

(5 * y) % 16

Если мы будем перебирать y от 1 до m-1, то получим такую последовательность:

5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11

Самое важное — это то, что здесь нет повторов. Т.е. мы преобразовали последовательность от 1 до 15 в последовательность из тех же чисел, но в другом порядке и без повторов. Другими словами, мы обфусцировали инкрементальный идентификатор!

Модульная мультипликативная инверсия нужна, чтобы деобфусцировать идентификаторы, т.е. вернуть как было. Для 5 и 16 инверсия равна 13. Получаем такое выражение:

(x * 13) % 16

Если на место x подставим числа из обфусцированной последовательности (5, 10, 15, 4, 9…), то получим это:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

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

Делаем полноценный обфускатор идентификаторов

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

  • Выбрать m такое, чтобы оно было больше всех используемых идентификаторов. Например, если тип для идентификаторов — это 32-битный int, и мы хотим покрыть все возможные варианты, то в качестве m можно взять максимально возможное значение для этого типа и прибавить 1: 2147483647 + 1 = 2147483648.
  • Выбрать x взаимно простое с m. Для простоты можно просто взять большое простое число и проверить, что m на него не делится. Например, 617467373. Есть куча онлайн-генераторов для простых чисел, например вот этот.
  • Находим модульную мультипликативную инверсию для выбранных x и m. Можно использовать любой онлайн-калькулятор (например), можно использовать математические библиотеки в языках программирования. Для моих чисел получается 2133891045.
  • Чтобы повысить устойчивость к перебору, можно выполнить «исключающее ИЛИ» (XOR) между получившимся результатом и еще одним случайным числом z. Тогда для взлома нужно будет найти x, m и z, что увеличивает сложность перебора. Можно просто сгенерировать еще одно большое простое число. У меня получилось такое: 423012077. Полное выражение будет выглядеть так:
Прямое преобразование: (x * ID1) % m ^ z = ID2 Обратное преобразование: (ID2 ^ z * y) % m = ID1
  • ?
  • profit

Подробнее об этом можно почитать тут и тут (на английском).

Обфусцируем мой ID на DTF (который равен 354):

(617467373 * 354) % 4294967295 ^ 423012077 = 2107664215

Проверим, что деобфускация работает:

(2107664215 ^ 423012077 * 3697274552) % 4294967295 = 354

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

Если говорить математическим языком, то:

Мы получили функциональное отображение подмножества натуральных чисел [1, m-1] на самого себя, причем оно является биекцией, т.е. оно одновременно сюръективно и инъективно

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

[Техпоп] Обфускация инкрементальных идентификаторов с помощью модульного умножения

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

#техпоп #математика #приходько_техпоп

2525
2 комментария

Ничего не понял, но очень интересно

3
Ответить

Комментарий недоступен

1
Ответить