Obfuscating an ID

Question

Je cherche un moyen de crypter/obfusquer un ID entier dans un autre entier. Plus précisément, j'ai besoin d'une fonction int F(int x) de sorte que

• x<->F(x) est une correspondance biunivoque (si x != y, F(x) != F(y))
• Étant donné F(x), il est facile de trouver x - donc F n'est pas une fonction de hachage.
• étant donné x et F(x) il est difficile/impossible de trouver F(y), quelque chose comme x ^ 0x1234 ne fonctionne pas

Pour que les choses soient claires, je ne cherche pas une solution de cryptage fort, mais seulement de l'obscurcissement. Imaginez une application web avec des urls comme example.com/profile/1 , example.com/profile/2 etc. Les profils eux-mêmes ne sont pas secrets, mais je voudrais empêcher les voyeurs occasionnels de voir/récupérer tous les profils l'un après l'autre, donc je préférerais les cacher derrière quelque chose du genre example.com/profile/23423 , example.com/profile/80980234 etc. Bien que les jetons stockés dans la base de données puissent faire le travail assez facilement, je suis curieux de savoir s'il existe des mathématiques simples pour cela.

Une exigence importante que je n'avais pas clairement définie est que les résultats doivent avoir l'air "aléatoires", c'est-à-dire qu'étant donné une séquence x,x+1,...,x+n , F(x),F(x+1)...F(x+n) ne devraient pas former une progression de quelque sorte que ce soit.

Answer 1

Obfusquez-le avec une combinaison de 2 ou 3 méthodes simples :

• XOR
• mélanger les bits individuels
• convertir en représentation modulaire (D.Knuth, Vol. 2, Chapitre 4.3.2)
• choisir 32 (ou 64) sous-ensembles de bits qui se chevauchent et faire un XOR des bits dans chaque sous-ensemble (bits de parité des sous-ensembles)
• le représenter dans un système numérique à longueur variable et mélanger les chiffres
• choisissez une paire d'entiers impairs x y y qui sont des inverses multiplicatifs l'un de l'autre (modulo 2 32 ), puis multiplier par x pour obscurcir et multiplier par y à rétablir, toutes les multiplications sont modulo 2 32 (source : "Une utilisation pratique des inverses multiplicatifs" par Eric Lippert )

La méthode du système numérique à longueur variable n'obéit pas d'elle-même à votre exigence de "progression". Elle produit toujours des progressions arithmétiques courtes. Mais lorsqu'elle est combinée à une autre méthode, elle donne de bons résultats.

Il en va de même pour la méthode de représentation modulaire.

Voici un exemple de code C++ pour 3 de ces méthodes. L'exemple "Shuffle bits" peut utiliser des masques et des distances différents pour être plus imprévisible. Les 2 autres exemples sont bons pour les petits nombres (juste pour donner une idée). Ils devraient être étendus pour obfusquer correctement toutes les valeurs entières.

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

Answer 2

Vous voulez que la transformation soit réversible, et non évidente. Cela ressemble à un cryptage qui prend un nombre dans une plage donnée et produit un nombre différent dans la même plage. Si votre plage est de 64 bits, alors utilisez DES. Si vous voulez des nombres de 128 bits, utilisez AES. Si vous souhaitez une plage différente, votre meilleur choix est probablement le suivant Chiffre Hasty Pudding Ce système est conçu pour s'adapter à différentes tailles de blocs et à des plages de nombres qui ne rentrent pas parfaitement dans un bloc, comme 100 000 à 999 999.

Answer 3

L'obscurcissement n'est pas vraiment suffisant en termes de sécurité.

Toutefois, si vous essayez de déjouer le regard du spectateur occasionnel, je vous recommande de combiner deux méthodes :

• Une clé privée que vous combinez avec l'identifiant en les xorant ensemble.
• Faire tourner les pannetons d'une certaine quantité avant et après la clé. a été appliquée

Voici un exemple (utilisant un pseudo-code) :

  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

Je ne l'ai pas testé, mais je pense que c'est réversible, que cela devrait être rapide et qu'il n'est pas trop facile d'extraire la méthode.

Answer 4

Faites ce que vous voulez avec les morceaux de l'ID sans les détruire. Par exemple :

• faire tourner la valeur
• utiliser le lookup pour remplacer certaines parties de la valeur
• xor avec une certaine valeur
• bits d'échange
• octets d'échange
• refléter la valeur totale
• miroir une partie de la valeur
• ... utilisez votre imagination

Pour le décryptage, faites tout cela dans l'ordre inverse.

Créez un programme qui "crypte" certaines valeurs intéressantes pour vous et les place dans un tableau que vous pouvez examiner. Demandez au même programme de TESTER votre routine de cryptage/décryptage AVEC tous les ensembles de valeurs que vous souhaitez avoir dans votre système.

Ajoutez des éléments à la liste ci-dessus dans les routines jusqu'à ce que vos chiffres vous paraissent correctement manipulés.

Pour tout le reste, procurez-vous un exemplaire de Le livre .

Answer 5

J'ai écrit un article sur permutations sécurisées avec chiffrement par blocs qui devrait répondre à vos besoins.

Je dirais cependant que si vous voulez des identifiants difficiles à deviner, vous devriez simplement les utiliser dès le départ : générez des UUID et utilisez-les comme clé primaire pour vos enregistrements dès le départ - il n'est pas nécessaire de pouvoir convertir un "vrai" ID.