Обфускация ID

Я ищу способ зашифровать / запутать целочисленный идентификатор в другое целое число. Точнее мне нужна функция int F(int x), чтобы

• x <-> F (x) взаимно однозначное соответствие (если x! = y, F (x)! = F (y))
• учитывая F (x), легко определить x, поэтому F не является хеш-функцией
• учитывая x и F (x) трудно / невозможно узнать F (y), что-то вроде x ^ 0x1234не сработает

Для ясности, я не ищу надежного решения для шифрования, это всего лишь обфускация. Представьте себе веб-приложение с URL-адресами вроде example.com/profile/1и example.com/profile/2т. Д. Сами профили не являются секретными, но я бы хотел, чтобы случайные вуайеристы не просматривали / извлекали все профили один за другим, поэтому я бы предпочел спрятать их за чем-то вроде example.com/profile/23423и example.com/profile/80980234т. токены, хранящиеся в базе данных, могут выполнять эту работу довольно легко, мне любопытно, есть ли для этого какая-то простая математика.

Одно важное требование, которое я не понял, - это то, что результаты должны выглядеть «случайными», то есть, учитывая последовательность x,x+1,...,x+n, F(x),F(x+1)...F(x+n)не должны образовывать прогрессию какого-либо вида.

Затемните его комбинацией двух или трех простых методов:

• XOR
• перемешать отдельные биты
• преобразовать в модульное представление (Д. Кнут, том 2, глава 4.3.2)
• выбрать 32 (или 64) перекрывающихся подмножества битов и битов XOR в каждом подмножестве (биты четности подмножеств)
• представить его в числовой системе переменной длины и перемешать цифры
• выбрать пару нечетных чисел , xи yкоторые являются мультипликативными обратен друг к другу ( по модулю- ³² ), затем умножить на xзапутать и умножить на yвосстановление, все умножения по модулю- ³² (источник: «Практическое применение мультипликативных обратных» Эрик Липперт )

Метод числовой системы переменной длины сам по себе не подчиняется вашему требованию "прогрессии". Он всегда производит короткие арифметические прогрессии. Но в сочетании с каким-либо другим методом дает хорошие результаты.

То же верно и для метода модульного представления.

Вот пример кода C ++ для 3 из этих методов. В примере перестановки битов могут использоваться разные маски и расстояния, чтобы быть более непредсказуемым. Два других примера хороши для небольших чисел (просто для того, чтобы дать представление). Их следует расширить, чтобы правильно скрыть все целочисленные значения.

// *** Numberic system base: (4, 3, 5) -> (5, 3, 4)
// In real life all the bases multiplied should be near 2^32
unsigned y = x/15 + ((x/5)%3)*4 + (x%5)*12; // obfuscate
unsigned z = y/12 + ((y/4)%3)*5 + (y%4)*15; // restore

// *** Shuffle bits (method used here is described in D.Knuth's vol.4a chapter 7.1.3)
const unsigned mask1 = 0x00550055; const unsigned d1 = 7;
const unsigned mask2 = 0x0000cccc; const unsigned d2 = 14;

// Obfuscate
unsigned t = (x ^ (x >> d1)) & mask1;
unsigned u = x ^ t ^ (t << d1);
t = (u ^ (u  >> d2)) & mask2;
y = u ^ t ^ (t << d2);

// Restore
t = (y ^ (y >> d2)) & mask2;
u = y ^ t ^ (t << d2);
t = (u ^ (u >> d1)) & mask1;
z = u ^ t ^ (t << d1);

// *** Subset parity
t = (x ^ (x >> 1)) & 0x44444444;
u = (x ^ (x << 2)) & 0xcccccccc;
y = ((x & 0x88888888) >> 3) | (t >> 1) | u; // obfuscate

t = ((y & 0x11111111) << 3) | (((y & 0x11111111) << 2) ^ ((y & 0x22222222) << 1));
z = t | ((t >> 2) ^ ((y >> 2) & 0x33333333)); // restore

Вы хотите, чтобы преобразование было обратимым, а не очевидным. Похоже на шифрование, которое берет число из заданного диапазона и производит другое число в том же диапазоне. Если ваш диапазон - 64-битные числа, используйте DES. Если ваш диапазон составляет 128-битные числа, используйте AES. Если вам нужен другой диапазон, то лучшим выбором, вероятно, будет шифр Hasty Pudding , который предназначен для работы с блоками разных размеров и с диапазонами чисел, которые не вписываются в блок, например от 100000 до 999999.

Обфускации недостаточно с точки зрения безопасности.

Однако, если вы пытаетесь помешать случайному наблюдателю, я бы порекомендовал комбинацию двух методов:

• Закрытый ключ, который вы объединяете с идентификатором, объединяя их вместе
• Поворот битов на определенную величину как до, так и после применения ключа

Вот пример (с использованием псевдокода):

  def F(x)
    x = x XOR 31415927       # XOR x with a secret key
    x = rotl(x, 5)           # rotate the bits left 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    x = rotr(x, 5)           # rotate the bits right 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    return x                 # return the value
  end

Я не тестировал его, но думаю, что это обратимо, должно быть быстро и не так просто, чтобы выявить метод.

Я нашел этот конкретный фрагмент кода Python / PHP очень полезным:

https://github.com/marekweb/opaque-id

Я написал код JS, используя некоторые идеи из этой ветки:

const BITS = 32n;
const MAX = 4294967295n;
const COPRIME = 65521n;
const INVERSE = 2166657316n;
const ROT = 6n;
const XOR1 = 10296065n; 
const XOR2 = 2426476569n;


function rotRight(n, bits, size) {
    const mask = (1n << bits) - 1n;
    // console.log('mask',mask.toString(2).padStart(Number(size),'0'));
    const left = n & mask;
    const right = n >> bits;
    return (left << (size - bits)) | right;
}

const pipe = fns => fns.reduce((f, g) => (...args) => g(f(...args)));

function build(...fns) {
    const enc = fns.map(f => Array.isArray(f) ? f[0] : f);
    const dec = fns.map(f => Array.isArray(f) ? f[1] : f).reverse();

    return [
        pipe(enc),
        pipe(dec),
    ]
}

[exports.encode, exports.decode] = build(
    [BigInt, Number],
    [i => (i * COPRIME) % MAX, i => (i * INVERSE) % MAX],
    x => x ^ XOR1,
    [x => rotRight(x, ROT, BITS), x => rotRight(x, BITS-ROT, BITS)],
    x => x ^ XOR2,
);

Это дает хорошие результаты, например:

1 1352888202n 1 'mdh37u'
2 480471946n 2 '7y26iy'
3 3634587530n 3 '1o3xtoq'
4 2225300362n 4 '10svwqy'
5 1084456843n 5 'hxno97'
6 212040587n 6 '3i8rkb'
7 3366156171n 7 '1jo4eq3'
8 3030610827n 8 '1e4cia3'
9 1889750920n 9 'v93x54'
10 1017334664n 10 'gtp0g8'
11 4171450248n 11 '1wzknm0'
12 2762163080n 12 '19oiqo8'
13 1621319561n 13 'qtai6h'
14 748903305n 14 'cdvlhl'
15 3903018889n 15 '1sjr8nd'
16 3567473545n 16 '1mzzc7d'
17 2426613641n 17 '144qr2h'
18 1554197390n 18 'ppbudq'
19 413345678n 19 '6u3fke'
20 3299025806n 20 '1ik5klq'
21 2158182286n 21 'zoxc3y'
22 1285766031n 22 'l9iff3'
23 144914319n 23 '2ea0lr'
24 4104336271n 24 '1vvm64v'
25 2963476367n 25 '1d0dkzz'
26 2091060108n 26 'ykyob0'
27 950208396n 27 'fpq9ho'
28 3835888524n 28 '1rfsej0'
29 2695045004n 29 '18kk618'
30 1822628749n 30 'u559cd'
31 681777037n 31 'b9wuj1'
32 346231693n 32 '5q4y31'

Тестирование с помощью:

  const {encode,decode} = require('./obfuscate')

  for(let i = 1; i <= 1000; ++i) {
        const j = encode(i);
        const k = decode(j);
        console.log(i, j, k, j.toString(36));
   }

XOR1и XOR2представляют собой просто случайные числа от 0 до MAX. MAXесть 2**32-1; вы должны установить это значение, которое, по вашему мнению, будет вашим наивысшим идентификатором.

COPRIME- число, взаимно простое с / MAX. Я считаю, что простые числа взаимно просты со всеми остальными числами (кроме кратных самих себя).

INVERSEэто сложно понять. Эти сообщения в блоге не дают прямого ответа, но WolframAlpha может понять это за вас . По сути, просто решите уравнение (COPRIME * x) % MAX = 1для x.

buildФункция что - то я создал , чтобы сделать его проще для создания этих кодирования / декодирования трубопроводов. Вы можете скормить ему столько операций, сколько захотите, [encode, decode]попарно. Эти функции должны быть равными и противоположными. Эти XORфункции сами по себе дополняют друг друга, поэтому вам не нужна пара.

Вот еще одна забавная инволюция :

function mixHalves(n) {
    const mask = 2n**12n-1n;
    const right = n & mask;
    const left = n >> 12n;
    const mix = left ^ right;
    return (mix << 12n) | right;
}

(предполагает 24-битные целые числа - просто измените числа на любой другой размер)

Сделайте что-нибудь с битами идентификатора, чтобы их не уничтожить. Например:

• повернуть значение
• используйте поиск для замены определенных частей значения
• xor с некоторым значением
• обменять биты
• поменять местами байты
• отражать всю ценность
• отразить часть стоимости
• ... использовать ваше воображение

Для расшифровки проделайте все в обратном порядке.

Создайте программу, которая «зашифрует» для вас некоторые интересные значения и поместит их в таблицу, которую вы сможете изучить. Используйте ту же программу. ПРОВЕРЬТЕ свою процедуру шифрования / дешифрования со всем набором значений, которые вы хотите иметь в своей системе.

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

Для чего-нибудь еще возьмите копию Книги .

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

Я бы посоветовал, однако, что если вы хотите, чтобы идентификаторы трудно угадывать, вы должны просто использовать их в первую очередь: сгенерировать UUID и использовать их в качестве первичного ключа для ваших записей - нет необходимости иметь возможность для преобразования в «настоящий» идентификатор и обратно.

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

Однако это можно сделать меньше, поэтому вместо отображения всех целых чисел вы должны отобразить только 2 (или в худшем случае 1) байт и применить это к каждой группе в целом числе. Итак, используя 2 байта, целое число будет (группа1) (группа2) вы сопоставите каждую группу через случайную карту. Но это означает, что если вы измените только group2, то сопоставление для group1 останется прежним. Это можно «исправить», назначив разные биты каждой группе.

Итак, * (group2) может быть (бит 14,12,10,8,6,4,2,0), поэтому добавление 1 изменит как group1, так и group2 .

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

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

То, что вы здесь описываете, кажется противоположностью односторонней функции: ее легко инвертировать, но очень сложно применить. Один из вариантов - использовать стандартный готовый алгоритм шифрования с открытым ключом, в котором вы фиксируете (секретный, случайно выбранный) открытый ключ, который вы храните в секрете, и закрытый ключ, которым вы делитесь со всем миром. Таким образом, ваша функция F (x) будет шифрованием x с использованием открытого ключа. Затем вы можете легко расшифровать F (x) обратно до x, используя закрытый ключ дешифрования. Обратите внимание, что роли открытого и закрытого ключей здесь поменялись местами - вы выдаете закрытый ключ всем, чтобы они могли расшифровать функцию, но держите открытый ключ в секрете на своем сервере. Сюда:

1. Функция является биекцией, поэтому она обратима.
2. Учитывая F (x), x эффективно вычислим.
3. Учитывая x и F (x), чрезвычайно сложно вычислить F (y) из y, поскольку без открытого ключа (при условии, что вы используете криптографически стойкую схему шифрования) невозможно зашифровать данные, даже если частные ключ дешифрования известен.

Это дает много преимуществ. Во-первых, вы можете быть уверены, что криптосистема безопасна, поскольку, если вы используете хорошо зарекомендовавший себя алгоритм, такой как RSA, вам не нужно беспокоиться о случайной небезопасности. Во-вторых, для этого уже существуют библиотеки, поэтому вам не нужно много писать код и вы можете быть защищены от атак по побочным каналам. Наконец, вы можете дать возможность любому пойти и инвертировать F (x), при этом никто не сможет вычислить F (x).

Одна деталь - вам определенно не следует использовать здесь только стандартный тип int. Даже с 64-битными целыми числами существует так мало возможных комбинаций, что злоумышленник может просто перебрать все, пока не найдет шифрование F (y) для некоторого y, даже если у них нет ключа. Я бы посоветовал использовать что-то вроде 512-битного значения, поскольку даже научно-фантастическая атака не сможет перебрать это.

Надеюсь это поможет!

Если xorприемлемо для всего, кроме вывода F(y)данного, xи F(x)тогда я думаю, что вы можете сделать это с солью . Сначала выберите секретную одностороннюю функцию. Например S(s) = MD5(secret ^ s). Тогда F(x) = (s, S(s) ^ x)где sвыбирается случайным образом. Я написал это как кортеж, но вы можете объединить две части в целое число, например F(x) = 10000 * s + S(s) ^ x. Расшифровка sснова извлекает соль и использует F'(F(x)) = S(extract s) ^ (extract S(s)^x). Учитывая, xи F(x)вы можете видеть s(хотя он немного запутан), и вы можете сделать вывод, S(s)но для другого пользователя yс другой случайной солью tпользователь, зная, F(x)не может найти S(t).