Обфускание идентификатора

Ответ 1

Обфускацию его с помощью некоторой комбинации из 2 или 3 простых методов:

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

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

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

Вот пример кода С++ для 3 из этих методов. Пример случайных бит может использовать несколько разных масок и расстояний, чтобы быть более непредсказуемыми. Другие 2 примера хороши для небольших чисел (просто чтобы дать идею). Они должны быть расширены, чтобы должным образом запутать все целочисленные значения.

// *** 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 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

Ответ 2

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

Ответ 3

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

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

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

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

  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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

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

Для чего-нибудь еще получите копию The Book.

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

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

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

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

Ответ 9

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

Ответ 10

Если 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).

Ответ 11

Я написал код 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; Вы должны установить это на то, что вы думаете, ваш самый высокий ID будет.

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

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

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