it-swarm-pt.tech

Ofuscando um ID

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

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

Para maior clareza, não estou procurando uma solução de criptografia forte, é apenas ofuscação. Imagine um aplicativo da Web com URLs como example.com/profile/1, example.com/profile/2 Etc. Os perfis em si não são secretos, mas eu gostaria de impedir que viajantes casuais visualizem/busquem todos os perfis um após o outro, então eu prefiro escondê-los atrás de algo como example.com/profile/23423, example.com/profile/80980234 etc. Embora os tokens armazenados no banco de dados possam fazer o trabalho com bastante facilidade, estou curioso para saber se existe alguma matemática simples disponível para isso.

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

80
georg

Ofuscá-lo com uma combinação de 2 ou 3 métodos simples:

  • XOR
  • embaralhar bits individuais
  • converter em representação modular (D.Knuth, Vol. 2, capítulo 4.3.2)
  • escolha 32 (ou 64) subconjuntos de bits sobrepostos e XOR bits 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 números inteiros ímpares x e y que são inversos multiplicativos um do outro (módulo 232.), multiplique por x para ofuscar e multiplique por y para restaurar, todas as multiplicações são módulo 232. (fonte: "Um uso prático de inversos multiplicativos" por Eric Lippert )

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

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

Aqui está um exemplo de código C++ para três desses métodos. O exemplo de bits aleatórios pode usar 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 idéia). 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
37
Evgeny Kluev

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 128 bits, use o AES. Se você deseja um intervalo diferente, provavelmente sua melhor aposta é codificação Hasty Pudding , que foi projetada para lidar com diferentes tamanhos de bloco e com intervalos de números que não se encaixam perfeitamente em um bloco, como 100.000 a 999.999.

9
rossum

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

No entanto, se você estiver tentando impedir o espectador casual, recomendo uma combinação de dois métodos:

  • Uma chave privada que você combina com o id xor'ing-los juntos
  • Girando os bits em uma certa quantidade antes e depois da aplicação da chave

Aqui está um exemplo (usando pseudo có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

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

6
IAmNaN

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

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

5
miracle2k

Eu escrevi algum código JS usando algumas das idéias 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 alguns 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));
   }

XOR1 e XOR2 são apenas números aleatórios entre 0 e MAX. MAX é 2**32-1; você deve configurá-lo para o que achar que será o seu ID mais alto.

COPRIME é um número coprime com MAX. Eu acho que os números primos são coprimes com todos os outros números (exceto múltiplos de si mesmos).

INVERSE é o mais complicado de se descobrir. Essas postagens no blog não dão uma resposta direta, mas o WolframAlpha pode descobrir isso para você . Basicamente, basta resolver a equação (COPRIME * x) % MAX = 1 para x.

A função build foi criada por mim para facilitar a criação desses pipelines de codificação/decodificação. Você pode alimentá-lo quantas operações quiser, como [encode, decode] pares. Essas funções devem ser iguais e opostas. As funções XOR são seus próprios elogios, assim você não precisa de um par lá.


Aqui está outra divertida involução :

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 números inteiros de 24 bits - basta alterar os números para qualquer outro tamanho)

2
mpen

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

  • gire o valor
  • use a pesquisa para substituir certas partes do valor
  • xor com algum valor
  • trocar bits
  • trocar bytes
  • espelhar todo o valor
  • espelhar uma parte do valor
  • ... use sua imaginação

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

Crie um programa que 'criptografará' alguns valores interessantes para você e os coloque 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 no seu sistema.

Adicione itens à lista acima nas rotinas até que seus números pareçam adequadamente mutilados para você.

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

2
Daniel Mošmondor

Eu escrevi um artigo sobre permutações seguras com cifras de bloco , que deve atender às suas necessidades conforme indicado.

Sugiro, no entanto, que se você quiser adivinhar identificadores, você deve usá-los em primeiro lugar: gerar UUIDs e usá-los como a chave principal de seus registros em primeiro lugar - não há necessidade de poder para converter de e para um ID 'real'.

2
Nick Johnson

Se xor é aceitável para tudo, exceto inferir F(y) dado x e F(x), então acho que você pode fazer isso com um salt. 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. Escrevi isso como uma tupla, mas você pode combinar as duas partes em um número inteiro, por exemplo F(x) = 10000 * s + S(s) ^ x. A descriptografia extrai o salt s novamente e usa F'(F(x)) = S(extract s) ^ (extract S(s)^x). Dado x e F(x) você pode ver s (embora esteja um pouco ofuscado) e pode inferir S(s), mas para algum outro usuário y com um sal aleatório diferente t o usuário que conhece F(x) não consegue encontrar S(t).

1
Ben Jackson

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

No entanto, isso pode ser menor, portanto, em vez de mapear todos os números inteiros, você deve mapear apenas 2 (ou, no pior caso, 1) byte e aplicá-lo a cada grupo no número inteiro. Portanto, usando 2 bytes, um número inteiro seria (group1) (group2) 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 "consertar" mapeando diferentes bits para cada grupo.

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

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

1
Roger Lindsjö

O que você está descrevendo aqui parece ser o oposto de uma função unidirecional: é fácil inverter, mas super difícil de aplicar. Uma opção seria usar um algoritmo padrão de criptografia de chave pública pronto para uso em que você fixa uma chave pública (secreta, escolhida aleatoriamente) para manter um 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 facilmente descriptografar F(x) voltar para x usando a chave de descriptografia privada.Tenha em atenção que as funções das chaves pública e privada são revertidas aqui - você fornece a chave privada a todos, para que eles possam descriptografar a função, mas mantém a chave pública em segredo no servidor.

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

Isso tem muitas vantagens. Primeiro, você pode ter certeza de que o sistema de criptografia é seguro, pois se você usar um algoritmo bem estabelecido como o RSA, não precisará se preocupar com insegurança acidental. Segundo, já existem bibliotecas disponíveis para fazer isso, então você não precisa codificar muito e pode ser imune a ataques de canal lateral. Por fim, você pode permitir que alguém inverta F(x) sem que ninguém consiga calcular F (x)).

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

Espero que isto ajude!

1
templatetypedef

Gere uma chave simétrica privada para uso em seu aplicativo e criptografe seu número inteiro com ele. Isso irá satisfazer todos os três requisitos, incluindo o mais difícil nº 3: seria necessário adivinhar sua chave para interromper seu esquema.

1
dasblinkenlight