Ukrywanie identyfikatora

Szukam sposobu na zaszyfrowanie / zaciemnienie identyfikatora całkowitego na inną liczbę całkowitą. Dokładniej, potrzebuję funkcji int F(int x), więc to

• x <-> F (x) to korespondencja jeden do jednego (jeśli x! = y, F (x)! = F (y))
• biorąc pod uwagę F (x), łatwo jest znaleźć x - więc F nie jest funkcją haszującą
• biorąc pod uwagę x i F (x), trudno / niemożliwe jest znaleźć F (y), coś takiego jak x ^ 0x1234nie zadziała

Dla jasności nie szukam silnego rozwiązania do szyfrowania, to tylko zaciemnianie. Wyobraźmy sobie aplikację internetową z adresami URL, takich jak example.com/profile/1, example.com/profile/2itp profili sami nie są tajne, ale chciałbym, aby zapobiec przypadkowym podglądaczy do widzenia / pobrać wszystkie profile jeden po drugim, więc wolałbym ukryć je za coś podobnego example.com/profile/23423, example.com/profile/80980234itp Chociaż tokeny przechowywane w bazie danych mogą wykonać to zadanie dość łatwo, jestem ciekawy, czy jest do tego dostępna jakaś prosta matematyka.

Jednym z ważnych wymagań, których nie byłem pewien x,x+1,...,x+n, jest to, że wyniki powinny wyglądać „losowo”, to znaczy biorąc pod uwagę sekwencję , F(x),F(x+1)...F(x+n)nie powinny tworzyć żadnego rodzaju progresji.

Ukryj to za pomocą kombinacji 2 lub 3 prostych metod:

• XOR
• tasuj poszczególne bity
• konwertować na reprezentację modułową (D.Knuth, tom 2, rozdział 4.3.2)
• wybierz 32 (lub 64) nakładające się podzbiory bitów i bitów XOR w każdym podzbiorze (bity parzystości podzbiorów)
• reprezentują go w systemie liczbowym o zmiennej długości i tasują cyfry
• wybrać parę nieparzystych liczb całkowitych xi yże są multiplikatywne odwrotności siebie (modulo 2 ³² ), a następnie pomnożyć przez xukrycie i pomnożyć przez yprzywracanie, wszystkie mnożenia są modulo 2 ³² (źródło: „Praktyczne wykorzystanie multyplikatywnych odwrotności” autorstwa Erica Lippert )

Metoda systemu liczbowego o zmiennej długości sama w sobie nie spełnia wymagań „progresji”. Zawsze tworzy krótkie progresje arytmetyczne. Ale w połączeniu z inną metodą daje dobre rezultaty.

To samo dotyczy metody reprezentacji modułowej.

Oto przykład kodu w C ++ dla 3 z tych metod. Przykład Shuffle bits może wykorzystywać różne maski i odległości, aby być bardziej nieprzewidywalnym. Pozostałe 2 przykłady są dobre dla małych liczb (tylko po to, aby dać pomysł). Powinny zostać rozszerzone, aby poprawnie zaciemnić wszystkie wartości całkowite.

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

Chcesz, aby transformacja była odwracalna, a nie oczywista. To brzmi jak szyfrowanie, które przyjmuje liczbę z danego zakresu i generuje inną liczbę z tego samego zakresu. Jeśli Twój zakres obejmuje liczby 64-bitowe, użyj DES. Jeśli Twój zakres obejmuje liczby 128-bitowe, użyj AES. Jeśli chcesz mieć inny zakres, najlepszym rozwiązaniem jest prawdopodobnie szyfr Hasty Pudding , który jest zaprojektowany do radzenia sobie z różnymi rozmiarami bloków i zakresami liczb, które nie pasują dokładnie do bloku, na przykład od 100 000 do 999 999.

Pod względem bezpieczeństwa zaciemnianie nie jest wystarczające.

Jeśli jednak próbujesz udaremnić przypadkowego widza, polecam połączenie dwóch metod:

• Klucz prywatny, który łączysz z identyfikatorem, łącząc je razem
• Obracanie bitów o określoną wartość zarówno przed, jak i po zastosowaniu klucza

Oto przykład (przy użyciu pseudokodu):

  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

Nie testowałem tego, ale myślę, że jest to odwracalne, powinno być szybkie i niezbyt łatwe do wypróbowania metody.

Uważam, że ten konkretny fragment kodu Python / PHP jest bardzo przydatny:

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

Napisałem trochę kodu JS, korzystając z pomysłów z tego wątku:

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

Daje dobre wyniki, takie jak:

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'

Testowanie z:

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

XOR1i XOR2są po prostu liczbami losowymi od 0 do MAX. MAXjest 2**32-1; Powinieneś ustawić to na cokolwiek myślisz, że będzie twój najwyższy identyfikator.

COPRIMEjest liczbą względnie pierwszą w / MAX. Myślę, że same liczby pierwsze są względnie pierwsze z każdą inną liczbą (z wyjątkiem ich wielokrotności).

INVERSEjest trudna do rozgryzienia. Te posty na blogu nie dają prostej odpowiedzi, ale WolframAlpha może znaleźć to dla Ciebie . Po prostu rozwiąż równanie (COPRIME * x) % MAX = 1dla x.

buildFunkcja jest coś, co stworzone, aby ułatwić tworzenie tych rurociągów kodowania / dekodowania. Możesz podawać mu dowolną liczbę operacji w [encode, decode]parach. Te funkcje muszą być równe i przeciwne. Te XORfunkcje są ich własne komplementy, więc nie trzeba się tam parę.

Oto kolejna zabawna inwolucja :

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

(zakłada 24-bitowe liczby całkowite - po prostu zmień liczby na inny rozmiar)

Zrób wszystko z fragmentami identyfikatora, które ich nie zniszczą. Na przykład:

• obrócić wartość
• użyj wyszukiwania, aby zamienić określone części wartości
• xor z pewną wartością
• zamienić bity
• zamień bajty
• odzwierciedlają całą wartość
• odzwierciedlają część wartości
• ... Użyj swojej wyobraźni

Aby odszyfrować, wykonaj to wszystko w odwrotnej kolejności.

Utwórz program, który „zaszyfruje” kilka interesujących wartości i umieści je w tabeli, którą możesz sprawdzić. Ten sam program PRZETESTUJ procedurę szyfrowania / deszyfrowania ZE wszystkimi zestawami wartości, które chcesz mieć w systemie.

Dodawaj rzeczy do powyższej listy do procedur, aż liczby będą wyglądać na odpowiednio zniekształcone.

W każdym innym przypadku zdobądź egzemplarz książki .

Napisałem artykuł o bezpiecznych permutacjach z szyframi blokowymi , które powinny spełnić twoje wymagania, jak podano.

Sugerowałbym jednak, że jeśli chcesz trudnych do odgadnięcia identyfikatorów, powinieneś po prostu ich używać w pierwszej kolejności: generować UUID i używać ich jako podstawowego klucza do swoich rekordów - nie ma potrzeby, aby móc konwertować na i z „prawdziwego” identyfikatora.

Nie wiem, jak „trudne” to ma być, jak szybko lub jak mało pamięci użyć. Jeśli nie masz ograniczeń pamięci, możesz stworzyć listę wszystkich liczb całkowitych, przetasować je i użyć tej listy jako mapowania. Jednak nawet dla 4-bajtowej liczby całkowitej potrzebowałbyś dużo pamięci.

Jednak można by to zmniejszyć, więc zamiast mapować wszystkie liczby całkowite, zamapowałbyś tylko 2 (lub w najgorszym przypadku 1) bajt i zastosowałbyś to do każdej grupy w liczbie całkowitej. Tak więc, używając 2 bajtów, liczba całkowita byłaby (grupa1) (grupa2) , odwzorowałbyś każdą grupę na losowej mapie. Ale to oznacza, że ​​jeśli zmienisz tylko grupę 2, mapowanie dla grupy 1 pozostanie takie samo. Można to „naprawić”, mapując różne bity do każdej grupy.

Więc * (grupa2) może być (bit 14,12,10,8,6,4,2,0) tak, dodając 1 zmieniłaby zarówno GRUPA1 i Grupa2 .

Mimo to jest to tylko zabezpieczenie przez zaciemnienie, każdy, kto może wprowadzić liczby do twojej funkcji (nawet jeśli utrzymujesz tę funkcję w tajemnicy), może dość łatwo to rozgryźć.

Wygeneruj prywatny klucz symetryczny do użytku w aplikacji i zaszyfruj nim swoją liczbę całkowitą. Spełni to wszystkie trzy wymagania, w tym najtrudniejszy # 3: należałoby odgadnąć klucz, aby złamać schemat.

To, co tu opisujesz, wydaje się być przeciwieństwem funkcji jednokierunkowej: łatwo ją odwrócić, ale bardzo trudno ją zastosować. Jedną z opcji byłoby użycie standardowego, gotowego algorytmu szyfrowania klucza publicznego, w którym ustalasz (tajny, losowo wybrany) klucz publiczny, który utrzymujesz w tajemnicy, oraz klucz prywatny, który udostępniasz światu. W ten sposób twoja funkcja F (x) byłaby szyfrowaniem x przy użyciu klucza publicznego. Następnie możesz łatwo odszyfrować F (x) z powrotem do x, używając prywatnego klucza odszyfrowywania. Zauważ, że role klucza publicznego i prywatnego są tutaj odwrócone - dajesz każdemu klucz prywatny, aby mogli odszyfrować funkcję, ale trzymaj klucz publiczny w tajemnicy na serwerze. W ten sposób:

1. Funkcja jest bijekcją, więc jest odwracalna.
2. Biorąc pod uwagę F (x), x jest wydajnie obliczalne.
3. Biorąc pod uwagę x i F (x), niezwykle trudno jest obliczyć F (y) od y, ponieważ bez klucza publicznego (zakładając, że używasz silnego kryptograficznie schematu szyfrowania), nie ma wykonalnego sposobu szyfrowania danych, nawet jeśli prywatny klucz odszyfrowywania jest znany.

Ma to wiele zalet. Po pierwsze, możesz mieć pewność, że system kryptograficzny jest bezpieczny, ponieważ jeśli używasz ugruntowanego algorytmu, takiego jak RSA, nie musisz się martwić o przypadkową niepewność. Po drugie, istnieją już biblioteki, które to robią, więc nie musisz zbytnio kodować i możesz być odporny na ataki typu side-channel. Wreszcie, możesz umożliwić każdemu przejście i odwrócenie F (x) bez możliwości obliczenia F (x).

Jeden szczegół - zdecydowanie nie powinieneś tutaj używać tylko standardowego typu int. Nawet w przypadku 64-bitowych liczb całkowitych jest tak mało możliwych kombinacji, że osoba atakująca może po prostu spróbować odwrócić wszystko na siłę, aż znajdzie szyfrowanie F (y) dla niektórych y, nawet jeśli nie ma klucza. Sugerowałbym użycie czegoś w rodzaju wartości 512-bitowej, ponieważ nawet atak science fiction nie byłby w stanie tego brutalnie wymusić.

Mam nadzieję że to pomoże!

Jeśli xorjest do zaakceptowania dla wszystkiego, ale wnioskując F(y)podane xi F(x)wtedy myślę, że można zrobić z solą . Najpierw wybierz tajną funkcję jednokierunkową. Na przykład S(s) = MD5(secret ^ s). Wtedy F(x) = (s, S(s) ^ x)gdzie sjest wybierane losowo. Napisałem to jako krotkę, ale można połączyć obie części w liczbę całkowitą, np F(x) = 10000 * s + S(s) ^ x. Odszyfrowanie sponownie wyodrębnia sól i używa F'(F(x)) = S(extract s) ^ (extract S(s)^x). Podane xi F(x)możesz zobaczyć s(choć jest to nieco zaciemnione) i możesz wywnioskować, S(s)ale dla innego użytkownika yz inną losową solą, tktórej użytkownik F(x)nie może znaleźć S(t).