Ofuscando um ID

Estou procurando uma maneira de criptografar / ofuscar um ID de inteiro em outro inteiro. Mais precisamente, preciso de uma função int F(int x), para que

• x <-> F (x) é correspondência um a um (se x! = y, F (x)! = F (y))
• dado F (x), é fácil descobrir x - então F não é uma função hash
• dados x e F (x) é difícil / impossível descobrir F (y), algo como x ^ 0x1234não vai funcionar

Para maior clareza, não estou procurando uma solução de criptografia forte, é apenas ofuscação. Imagine uma aplicação web com URLs como example.com/profile/1, example.com/profile/2etc. Os perfis em si não são segredo, mas eu gostaria de evitar voyeurs casuais para ver / buscar todos os perfis de um após o outro, então eu prefiro escondê-los atrás de algo como example.com/profile/23423, example.com/profile/80980234etc. Embora tokens armazenados em banco de dados podem fazer o trabalho facilmente, estou curioso para saber se há alguma matemática simples disponível para isso.

Um requisito importante sobre o qual não estava claro é que os resultados deveriam parecer "aleatórios", isto é, dada uma sequência x,x+1,...,x+n, F(x),F(x+1)...F(x+n)não deveriam formar uma progressão de nenhum tipo.

Ofusque-o com alguma combinação de 2 ou 3 métodos simples:

• XOR
• embaralhar pedaços individuais
• converter para representação modular (D.Knuth, Vol. 2, Capítulo 4.3.2)
• escolha 32 (ou 64) subconjuntos sobrepostos de bits e bits XOR em cada subconjunto (bits de paridade de subconjuntos)
• representá-lo em sistema numérico de comprimento variável e dígitos aleatórios
• escolha um par de inteiros ímpares xe yque são inversos multiplicativos um do outro (módulo 2 ³² ), depois multiplique por xpara ofuscar e multiplique por ypara restaurar, todas as multiplicações são módulo 2 ³² (fonte: "Um uso prático de inversos multiplicativos" por Eric Lippert )

O método do sistema numérico de comprimento variável não obedece ao seu requisito de "progressão" sozinho. Ele sempre produz progressões aritméticas curtas. Mas quando combinado com algum outro método, dá bons resultados.

O mesmo é verdade para o método de representação modular.

Aqui está um exemplo de código C ++ para 3 desses métodos. O exemplo de bits aleatórios pode usar algumas máscaras e distâncias diferentes para ser mais imprevisível. Outros 2 exemplos são bons para números pequenos (apenas para dar uma ideia). Eles devem ser estendidos para ofuscar todos os valores inteiros corretamente.

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

Você deseja que a transformação seja reversível e não óbvia. Isso soa como uma criptografia que pega um número em um determinado intervalo e produz um número diferente no mesmo intervalo. Se o seu intervalo for de números de 64 bits, use DES. Se o seu intervalo for de números de 128 bits, use AES. Se você deseja um intervalo diferente, sua melhor aposta é provavelmente a cifra Hasty Pudding , que é projetada para lidar com diferentes tamanhos de blocos e com intervalos de números que não se encaixam perfeitamente em um bloco, como 100.000 a 999.999.

A ofuscação não é realmente suficiente em termos de segurança.

No entanto, se você está tentando frustrar o observador casual, recomendo uma combinação de dois métodos:

• Uma chave privada que você combina com o id, juntando-os
• Girar os bits em uma certa quantidade antes e depois de a chave ter sido aplicada

Aqui está um exemplo (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

Não testei, mas acho que é reversível, deve ser rápido e não muito fácil descobrir o método.

Achei esta parte específica do código Python / PHP muito útil:

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

Escrevi alguns códigos JS usando algumas das ideias neste tópico:

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

Produz bons 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'

Testando com:

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

XOR1e XOR2são apenas números aleatórios entre 0 e MAX. MAXé 2**32-1; você deve definir isso para o que você acha que será o seu maior ID.

COPRIMEé um número que é coprime c / MAX. Acho que os próprios números primos são coprimes com todos os outros números (exceto seus múltiplos).

INVERSEé o mais difícil de descobrir. Essas postagens de blog não fornecem uma resposta direta, mas o WolframAlpha pode descobrir por você . Basicamente, basta resolver a equação (COPRIME * x) % MAX = 1para x.

A buildfunção é algo que criei para facilitar a criação desses pipelines de codificação / decodificação. Você pode alimentá-lo com quantas operações quiser como [encode, decode]pares. Essas funções devem ser iguais e opostas. As XORfunções são seus próprios elogios, então você não precisa de um par lá.

Aqui está outra involução 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;
}

(assume inteiros de 24 bits - basta alterar os números para qualquer outro tamanho)

Faça qualquer coisa com os bits do ID que não os destrua. Por exemplo:

• girar o valor
• use lookup para substituir certas partes do valor
• xor com algum valor
• trocar bits
• trocar bytes
• espelhe todo o valor
• espelhe uma parte do valor
• ... use sua imaginação

Para descriptografar, faça tudo isso na ordem inversa.

Crie um programa que irá 'criptografar' alguns valores interessantes para você e colocá-los em uma tabela que você possa examinar. Tenha o mesmo programa TESTE sua rotina de criptografia / descriptografia COM todo o conjunto de valores que você deseja ter em seu sistema.

Acrescente coisas à lista acima nas rotinas até que seus números pareçam devidamente mutilados para você.

Para qualquer outra coisa, obtenha uma cópia do Livro .

Escrevi um artigo sobre permutações seguras com cifras de bloco , que deve atender aos seus requisitos conforme declarado.

Eu sugiro, entretanto, que se você quiser identificadores difíceis de adivinhar, você deve apenas usá-los em primeiro lugar: gerar UUIDs e usá-los como a chave primária para seus registros em primeiro lugar - não há necessidade de ser capaz para converter de e para um ID 'real'.

Não tenho certeza de quão "difícil" você precisa que seja, quão rápido ou quão pouca memória usar. Se você não tem restrições de memória, pode fazer uma lista de todos os inteiros, embaralhá-los e usar essa lista como um mapeamento. No entanto, mesmo para um número inteiro de 4 bytes, você precisaria de muita memória.

No entanto, isso poderia ser menor, então, em vez de mapear todos os inteiros, você mapearia apenas 2 (ou no pior caso 1) byte e aplicaria isso a cada grupo no inteiro. Assim, usando 2 bytes um inteiro seria (grupo1) (grupo2) você mapearia cada grupo através do mapa aleatório. Mas isso significa que se você alterar apenas o grupo2, o mapeamento para o grupo1 permanecerá o mesmo. Isso poderia ser "consertado" mapeando bits diferentes para cada grupo.

Portanto, * (grupo2) poderia ser (bit 14,12,10,8,6,4,2,0), portanto, adicionar 1 mudaria o grupo1 e o grupo2 .

Ainda assim, isso é apenas segurança por obscuridade, qualquer um que possa inserir números em sua função (mesmo que você mantenha a função em segredo) poderia facilmente descobrir isso.

Gere uma chave simétrica privada para usar em seu aplicativo e criptografe seu inteiro com ela. Isso irá satisfazer todos os três requisitos, incluindo o mais difícil # 3: seria necessário adivinhar sua chave para quebrar seu esquema.

O que você está descrevendo aqui parece ser o oposto de uma função unilateral: é fácil de inverter, mas muito difícil de aplicar. Uma opção seria usar um algoritmo de criptografia de chave pública padrão, disponível no mercado, onde você fixa uma chave pública (secreta, escolhida aleatoriamente) que você mantém em segredo e uma chave privada que você compartilha com o mundo. Dessa forma, sua função F (x) seria a criptografia de x usando a chave pública. Você poderia então descriptografar facilmente F (x) de volta para x usando a chave de descriptografia privada. Observe que as funções da chave pública e privada são invertidas aqui - você dá a chave privada a todos para que possam descriptografar a função, mas mantém a chave pública em segredo em seu servidor. Dessa maneira:

1. A função é uma bijeção, portanto, é invertível.
2. Dado F (x), x é eficientemente computável.
3. Dados x e F (x), é extremamente difícil calcular F (y) de y, uma vez que sem a chave pública (supondo que você use um esquema de criptografia criptograficamente forte) não há maneira viável de criptografar os dados, mesmo que o privado a chave de descriptografia é conhecida.

Isso tem muitas vantagens. Em primeiro lugar, você pode ter certeza de que o sistema de criptografia é seguro, pois se você usar um algoritmo bem estabelecido como o RSA, não precisa se preocupar com insegurança acidental. Em segundo lugar, já existem bibliotecas para fazer isso, então você não precisa codificar muito e pode ser imune a ataques de canal lateral. Finalmente, você pode tornar possível que qualquer pessoa inverta F (x) sem que ninguém seja realmente capaz de calcular F (x).

Um detalhe - você definitivamente não deve usar apenas o tipo int padrão aqui. Mesmo com inteiros de 64 bits, há tão poucas combinações possíveis que um invasor poderia simplesmente tentar inverter tudo com a força bruta até encontrar a criptografia F (y) para algum y, mesmo que não tenha a chave. Eu sugeriria usar algo como um valor de 512 bits, já que mesmo um ataque de ficção científica não seria capaz de aplicar força bruta a isso.

Espero que isto ajude!

Se xoré aceitável para tudo, exceto inferir F(y)dado xe F(x)então acho que você pode fazer isso com um sal . Primeiro, escolha uma função secreta de mão única. Por exemplo S(s) = MD5(secret ^ s). Então, F(x) = (s, S(s) ^ x)onde sé escolhido aleatoriamente. Eu escrevi isso como uma tupla, mas você pode combinar as duas partes em um inteiro, por exemplo F(x) = 10000 * s + S(s) ^ x. A descriptografia extrai o sal snovamente e usa F'(F(x)) = S(extract s) ^ (extract S(s)^x). Dado xe F(x)você pode ver s(embora seja um pouco ofuscado) e você pode inferir, S(s)mas para algum outro usuário ycom um sal aleatório diferente que to usuário sabe F(x)não pode encontrar S(t).