Obscurcir un identifiant

Je cherche un moyen de chiffrer / masquer un identifiant 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) correspond à une correspondance univoque (si x! = y, F (x)! = F (y))
  • compte tenu de F (x), il est facile de trouver x – donc F n’est pas une fonction de hachage
  • donné x et F (x) il est difficile / impossible de trouver F (y), quelque chose comme x ^ 0x1234 ne fonctionnera pas

Pour plus de clarté, je ne cherche pas une solution de chiffrement solide, mais seulement un obscurcissement. Imaginez une application web avec des URL 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 les uns après les autres, alors je préfère les cacher derrière quelque chose comme example.com/profile/23423 , example.com/profile/80980234 etc. Bien que les jetons stockés dans une firebase database puissent faire le travail assez facilement, je suis curieux de savoir s’il existe des mathématiques simples pour ce.

Une exigence importante sur laquelle je n’ai pas été clair est que les résultats doivent avoir un aspect “aléatoire”, c’est-à-dire une séquence x,x+1,...,x+n , F(x),F(x+1)...F(x+n) ne devrait pas former une progression quelconque.

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 et bits XOR qui se chevauchent dans chaque sous-ensemble (bits de parité des sous-ensembles)
  • le représenter dans un système numérique de longueur variable et mélanger les chiffres
  • choisir une paire d’entiers impairs x et y qui sont des inverses multiplicatifs les uns des autres (modulo 2 32 ), puis se multiplier par x pour masquer et multiplier par y pour restaurer, toutes les multiplications sont modulo 2 32 (source: inverses “par Eric Lippert )

La méthode du système numérique de longueur variable n’obéit pas à elle seule à votre exigence de «progression». Il produit toujours des progressions arithmétiques courtes. Mais combiné à une autre méthode, il donne de bons résultats.

La même chose est vraie pour la méthode de représentation modulaire.

Voici un exemple de code C ++ pour trois de ces méthodes. Les exemples de bits de lecture aléatoire peuvent utiliser des masques et des distances différents pour être plus imprévisibles. Deux autres exemples sont bons pour les petits nombres (juste pour donner l’idée). Ils doivent être étendus pour masquer 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 

Vous voulez que la transformation soit réversible et pas é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 composée de 64 bits, utilisez DES. Si votre plage est de 128 bits, utilisez AES. Si vous voulez une gamme différente, alors votre meilleur pari est probablement le chiffrement Hasty Pudding , qui est conçu pour gérer différentes tailles de blocs et des plages de nombres qui ne correspondent pas parfaitement à un bloc, par exemple 100 000 à 999 999.

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

Cependant, si vous essayez de contrecarrer le spectateur occasionnel, je vous recommande une combinaison de deux méthodes:

  • Une clé privée que vous combinez avec l’ID en les regroupant
  • Rotation des bits d’un certain montant avant et après l’application de la clé

Voici un exemple (en 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, qu’il devrait être rapide et pas trop facile à démêler.

J’ai trouvé ce code Python / PHP très utile:

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

J’ai écrit un article sur les permutations sécurisées avec des codes de bloc , qui devrait répondre à vos exigences.

Je suggérerais cependant que si vous voulez deviner les identifiants, vous devez simplement les utiliser en premier lieu: générer des UUID et les utiliser en premier lieu pour vos enregistrements – il n’y a pas besoin de pouvoir convertir en et à partir d’un “vrai” identifiant.

Faites n’importe quoi avec les bits de l’ID qui ne les détruiront pas. Par exemple:

  • faire pivoter la valeur
  • utiliser la recherche pour remplacer certaines parties de la valeur
  • xor avec une certaine valeur
  • échanger des bits
  • swap bytes
  • refléter la valeur entière
  • refléter une partie de la valeur
  • … utilise ton imagination

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

Créez un programme qui “chiffrera” des valeurs intéressantes pour vous et les placera dans un tableau que vous pourrez examiner. Ayez le même programme TESTEZ votre routine de chiffrement / déchiffrement AVEC tous les ensembles de valeurs que vous voulez avoir dans votre système.

Ajouter des choses à la liste ci-dessus dans les routines jusqu’à ce que vos numéros semblent correctement mutilés à vous.

Pour toute autre chose, obtenez une copie du livre .

Vous ne savez pas exactement comment vous avez besoin d’être, à quelle vitesse ou quelle quantité de mémoire utiliser. Si vous n’avez pas de contraintes de mémoire, vous pouvez faire une liste de tous les entiers, les mélanger et utiliser cette liste en tant que mappage. Cependant, même pour un entier de 4 octets, vous auriez besoin de beaucoup de mémoire.

Cependant, cela pourrait être réduit, donc au lieu de mapper tous les entiers, vous ne mapperiez que 2 octets (ou le pire des 1) octets et les appliqueriez à chaque groupe de l’entier. Donc, en utilisant 2 octets, un entier serait (groupe1) (groupe2), vous mapperiez chaque groupe à travers la carte aléatoire. Mais cela signifie que si vous modifiez uniquement le groupe 2, le mappage du groupe 1 restra le même. Cela pourrait “réparer” en mappant différents bits à chaque groupe.

Donc, * (group2) pourrait être (bit 14,12,10,8,6,4,2,0) donc, l’ajout de 1 changerait à la fois group1 et group2 .

Cependant, il ne s’agit que de la sécurité par l’obscurité, quiconque pouvant alimenter des chiffres dans votre fonction (même si vous gardez le secret de la fonction) pourrait facilement le comprendre.

Générez une clé symésortingque privée à utiliser dans votre application et chiffrez-la avec votre entier. Cela répondra aux trois exigences, y compris la plus difficile # 3: il faudrait deviner votre clé pour briser votre régime.

Ce que vous décrivez ici semble être le contraire d’une fonction à sens unique: il est facile à inverser mais super difficile à appliquer. Une option consisterait à utiliser un algorithme standard de chiffrement par clé publique standard, dans lequel vous fixez une clé publique (secrète, choisie au hasard) que vous conservez secrète et une clé privée que vous partagez avec le monde. De cette façon, votre fonction F (x) serait le cryptage de x en utilisant la clé publique. Vous pouvez ensuite déchiffrer facilement F (x) à x en utilisant la clé de déchiffrement privée. Notez que les rôles de la clé publique et de la clé privée sont inversés ici – vous donnez la clé privée à tout le monde afin qu’ils puissent décrypter la fonction, mais gardez la clé publique secrète sur votre serveur. De cette façon:

  1. La fonction est une bijection, elle est donc inversible.
  2. Étant donné que F (x), x est efficacement calculable.
  3. Étant donné x et F (x), il est extrêmement difficile de calculer F (y) à partir de y, car sans la clé publique (en supposant que vous utilisez un schéma de chiffrement cryptographiquement fort), il est impossible de chiffrer les données, même si la clé de déchiffrement est connue.

Cela a de nombreux avantages. Tout d’abord, vous pouvez être assuré que le système cryptographique est sûr, car si vous utilisez un algorithme bien établi comme RSA, vous n’avez pas à vous soucier de l’insécurité accidentelle. Deuxièmement, il existe déjà des bibliothèques pour cela, vous n’avez donc pas besoin de coder beaucoup et vous pouvez être immunisé contre les attaques par canal secondaire. Enfin, vous pouvez rendre possible d’inverser F (x) sans que quiconque puisse réellement calculer F (x).

Un détail – vous ne devriez pas utiliser le type int standard ici. Même avec des nombres entiers de 64 bits, il y a tellement peu de combinaisons possibles qu’un attaquant pourrait simplement forcer tout à inversion jusqu’à ce qu’ils trouvent le cryptage F (y) pour certains y même s’ils ne possèdent pas la clé. Je suggère d’utiliser quelque chose comme une valeur de 512 bits, puisque même une attaque de science-fiction ne pourrait pas forcer cela.

J’espère que cela t’aides!

Si xor est acceptable pour tout sauf inférer F(y) donné x et F(x) alors je pense que vous pouvez le faire avec un sel . Choisissez d’abord une fonction à sens unique secrète. Par exemple S(s) = MD5(secret ^ s) . Alors F(x) = (s, S(s) ^ x)s est choisi au hasard. J’ai écrit cela comme un tuple mais vous pouvez combiner les deux parties en un entier, par exemple F(x) = 10000 * s + S(s) ^ x . Le décryptage extrait à nouveau le sel et utilise F'(F(x)) = S(extract s) ^ (extract S(s)^x) . Étant donné x et F(x) vous pouvez voir s (même s’il est légèrement obscurci) et vous pouvez déduire S(s) mais pour un autre utilisateur y avec un sel aléatoire différent t sachant que F(x) ne peut pas trouver S(t) .