Ofuscar una identificación

Estoy buscando una forma de cifrar / ofuscar un ID de entero en otro entero. Más precisamente, necesito una función int F(int x), para que

• x <-> F (x) es una correspondencia uno a uno (si x! = y, F (x)! = F (y))
• dado F (x), es fácil averiguar x, por lo que F no es una función hash
• dado x y F (x) es difícil / imposible averiguar F (y), algo como x ^ 0x1234no funcionará

Para mayor claridad, no estoy buscando una solución de cifrado sólida, es solo una ofuscación. Imagina una aplicación web con URL como example.com/profile/1, example.com/profile/2etc. Los perfiles en sí no son secretos, pero me gustaría evitar que mirones casuales vean / recuperen todos los perfiles uno tras otro, así que prefiero esconderlos detrás de algo como example.com/profile/23423, example.com/profile/80980234etc. Aunque Los tokens almacenados en la base de datos pueden hacer el trabajo con bastante facilidad, tengo curiosidad por saber si hay algunas matemáticas simples disponibles para esto.

Un requisito importante que no tenía claro es que los resultados deben verse "aleatorios", es decir, dada una secuencia x,x+1,...,x+n, F(x),F(x+1)...F(x+n)no deben formar una progresión de ningún tipo.

Ofuscarlo con alguna combinación de 2 o 3 métodos simples:

• XOR
• mezclar bits individuales
• convertir a representación modular (D.Knuth, Vol. 2, Capítulo 4.3.2)
• elija 32 (o 64) subconjuntos superpuestos de bits y bits XOR en cada subconjunto (bits de paridad de subconjuntos)
• representarlo en un sistema numérico de longitud variable y mezclar dígitos
• Elija un par de números enteros impares xy yque sean inversos multiplicativos entre sí (módulo 2 ³² ), luego multiplique por xpara ofuscar y multiplique por ypara restaurar, todas las multiplicaciones son módulo 2 ³² (fuente: "Un uso práctico de inversos multiplicativos" por Eric Lippert )

El método del sistema numérico de longitud variable no obedece a su requisito de "progresión" por sí solo. Siempre produce pequeñas progresiones aritméticas. Pero cuando se combina con algún otro método, da buenos resultados.

Lo mismo ocurre con el método de representación modular.

Aquí hay un ejemplo de código C ++ para 3 de estos métodos. El ejemplo de Shuffle bits puede usar algunas máscaras y distancias diferentes para ser más impredecible. Otros 2 ejemplos son buenos para números pequeños (solo para dar una idea). Deben extenderse para ofuscar correctamente todos los valores enteros.

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

Quiere que la transformación sea reversible y no obvia. Eso suena como un cifrado que toma un número en un rango dado y produce un número diferente en el mismo rango. Si su rango son números de 64 bits, utilice DES. Si su rango es de 128 bits, utilice AES. Si desea un rango diferente, entonces su mejor opción es probablemente el cifrado Hasty Pudding , que está diseñado para hacer frente a diferentes tamaños de bloques y rangos de números que no encajan perfectamente en un bloque, como 100.000 a 999.999.

La ofuscación no es realmente suficiente en términos de seguridad.

Sin embargo, si está tratando de frustrar al espectador casual, le recomendaría una combinación de dos métodos:

• Una clave privada que combinas con el id al xor'inglos juntos
• Rotar los bits en una cierta cantidad antes y después de que se haya aplicado la clave

Aquí hay un ejemplo (usando pseudocódigo):

  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

No lo he probado, pero creo que es reversible, debería ser rápido y no demasiado fácil de descifrar el método.

Encontré esta pieza particular de código Python / PHP muy útil:

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

Escribí un código JS usando algunas de las ideas en este hilo:

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,
);

Produce buenos resultados como:

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'

Prueba con:

  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));
   }

XOR1y XOR2son números aleatorios entre 0 y MAX. MAXes 2**32-1; debe establecer esto en lo que crea que será su ID más alto.

COPRIMEes un número que es coprime w / MAX. Creo que los números primos en sí mismos son coprimos con cualquier otro número (excepto sus múltiplos).

INVERSEes el más complicado de entender. Estas publicaciones de blog no dan una respuesta directa, pero WolframAlpha puede resolverlo por usted . Básicamente, simplemente resolver la ecuación (COPRIME * x) % MAX = 1para x.

La buildfunción es algo que creé para facilitar la creación de estas canalizaciones de codificación / decodificación. Puedes alimentarlo tantas operaciones como quieras por [encode, decode]parejas. Estas funciones tienen que ser iguales y opuestas. Las XORfunciones son sus propios cumplidos, por lo que no necesita un par allí.

Aquí hay otra involución divertida :

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

(asume enteros de 24 bits, simplemente cambie los números por cualquier otro tamaño)

Haga cualquier cosa con los bits de la identificación que no los destruya. Por ejemplo:

• rotar el valor
• usar la búsqueda para reemplazar ciertas partes del valor
• xor con algo de valor
• intercambiar bits
• intercambiar bytes
• reflejar todo el valor
• reflejar una parte del valor
• ... use su imaginación

Para el descifrado, haga todo eso en orden inverso.

Cree un programa que 'cifre' algunos valores interesantes para usted y póngalos en una tabla que pueda examinar. Haga que el mismo programa PRUEBE su rutina de cifrado / descifrado CON todo el conjunto de valores que desea tener en su sistema.

Agregue cosas a la lista anterior en las rutinas hasta que sus números se vean correctamente destrozados.

Para cualquier otra cosa, obtenga una copia de The Book .

Escribí un artículo sobre permutaciones seguras con cifrado en bloque , que debería cumplir con sus requisitos como se indica.

Sin embargo, sugeriría que si desea identificar identificadores difíciles de adivinar, debe usarlos en primer lugar: generar UUID y usarlos como clave principal para sus registros en primer lugar; no es necesario poder para convertir hacia y desde una identificación "real".

No estoy seguro de qué tan "difícil" necesita que sea, qué tan rápido o qué poca memoria usar. Si no tiene restricciones de memoria, puede hacer una lista de todos los enteros, mezclarlos y usar esa lista como un mapeo. Sin embargo, incluso para un entero de 4 bytes, necesitaría mucha memoria.

Sin embargo, esto podría hacerse más pequeño, por lo que en lugar de mapear todos los enteros, mapearía solo 2 (o el peor de los casos, 1) byte y aplicaría esto a cada grupo en el entero. Entonces, usando 2 bytes, un número entero sería (grupo1) (grupo2), mapearía cada grupo a través del mapa aleatorio. Pero eso significa que si solo cambia el grupo2, la asignación para el grupo1 seguirá siendo la misma. Esto podría "arreglarse" mapeando diferentes bits a cada grupo.

Entonces, * (group2) podría ser (bit 14,12,10,8,6,4,2,0), por lo que agregar 1 cambiaría tanto el grupo1 como el grupo2 .

Aún así, esto es solo seguridad por oscuridad, cualquiera que pueda ingresar números en su función (incluso si mantiene la función en secreto) podría resolverlo fácilmente.

Genere una clave simétrica privada para usar en su aplicación y cifre su entero con ella. Esto satisfará los tres requisitos, incluido el número 3 más difícil: uno necesitaría adivinar su clave para romper su esquema.

Lo que está describiendo aquí parece ser lo opuesto a una función unidireccional: es fácil de invertir pero muy difícil de aplicar. Una opción sería utilizar un algoritmo de cifrado de clave pública estándar y listo para usar en el que se fija una clave pública (secreta, elegida al azar) que se mantiene en secreto y una clave privada que se comparte con el mundo. De esa manera, su función F (x) sería el cifrado de x usando la clave pública. A continuación, puede descifrar fácilmente F (x) de nuevo ax utilizando la clave de descifrado privada. Tenga en cuenta que los roles de la clave pública y privada se invierten aquí: les da la clave privada a todos para que puedan descifrar la función, pero mantiene la clave pública en secreto en su servidor. De esa manera:

1. La función es una biyección, por lo que es invertible.
2. Dado F (x), x es eficientemente calculable.
3. Dados x y F (x), es extremadamente difícil calcular F (y) a partir de y, ya que sin la clave pública (suponiendo que use un esquema de cifrado criptográficamente fuerte) no hay forma factible de cifrar los datos, incluso si el privado se conoce la clave de descifrado.

Esto tiene muchas ventajas. Primero, puede estar seguro de que el sistema de cifrado es seguro, ya que si utiliza un algoritmo bien establecido como RSA, no debe preocuparse por la inseguridad accidental. En segundo lugar, ya existen bibliotecas para hacer esto, por lo que no necesita codificar mucho y puede ser inmune a los ataques de canal lateral. Por último, puede hacer posible que cualquiera pueda invertir F (x) sin que nadie pueda calcular F (x).

Un detalle: definitivamente no debería usar el tipo int estándar aquí. Incluso con enteros de 64 bits, hay tan pocas combinaciones posibles que un atacante podría simplemente intentar invertir todo por fuerza bruta hasta que encuentre el cifrado F (y) durante algún y, incluso si no tiene la clave. Sugeriría usar algo como un valor de 512 bits, ya que incluso un ataque de ciencia ficción no podría forzar esto.

¡Espero que esto ayude!

Si xores aceptable para todo menos para inferir F(y)dado xy F(x)entonces creo que puedes hacerlo con una sal . Primero elija una función secreta unidireccional. Por ejemplo S(s) = MD5(secret ^ s). Entonces, F(x) = (s, S(s) ^ x)donde sse elige al azar. Escribí eso como una tupla, pero puedes combinar las dos partes en un número entero, por ejemplo F(x) = 10000 * s + S(s) ^ x. El descifrado extrae la sal snuevamente y la usa F'(F(x)) = S(extract s) ^ (extract S(s)^x). Dado xy F(x)puede ver s(aunque está un poco confuso) y puede inferir, S(s)pero para algún otro usuario ycon una sal aleatoria diferente, tel usuario que sabe F(x)que no puede encontrar S(t).