Szyfrowanie zachowujące format

W kryptografii szyfrowanie z zachowaniem formatu ( FPE ) odnosi się do szyfrowania w taki sposób, że dane wyjściowe (tekst zaszyfrowany ) mają ten sam format co dane wejściowe (tekst jawny ) . Znaczenie „formatu” jest różne. Zwykle używane są tylko skończone zestawy znaków; numeryczne, alfabetyczne lub alfanumeryczne. Na przykład:

Szyfrowanie 16-cyfrowego numeru karty kredytowej, tak aby tekst zaszyfrowany był kolejnym 16-cyfrowym numerem.
Szyfrowanie angielskiego słowa, tak aby tekst zaszyfrowany był innym angielskim słowem.
Szyfrowanie n -bitowej liczby tak, aby tekst zaszyfrowany był kolejną n -bitową liczbą (jest to definicja n -bitowego szyfru blokowego).

Dla takich skończonych domen i dla celów poniższej dyskusji szyfr jest równoważny permutacji N liczb całkowitych ${0, ..., N -1$ }, gdzie N jest rozmiarem domeny.

Motywacja

Ograniczone długości lub formaty pól

Jedną z motywacji do korzystania z FPE są problemy związane z integracją szyfrowania z istniejącymi aplikacjami z dobrze zdefiniowanymi modelami danych. Typowym przykładem może być numer karty kredytowej , na przykład 1234567812345670 (16 bajtów, tylko cyfry).

Dodanie szyfrowania do takich aplikacji może być trudne, jeśli modele danych mają zostać zmienione, ponieważ zwykle wiąże się to ze zmianą limitów długości pól lub typów danych. Na przykład wyjście z typowego szyfru blokowego zamieniłoby numer karty kredytowej na wartość szesnastkową (np. 0x96a45cbcf9c2a9425cde9e274948cb67 , 34 bajty, cyfry szesnastkowe) lub wartość Base64 (np. lqRcvPnCqUJc3p4nSUjLZw== , 24 bajty, znaki alfanumeryczne i specjalne), co złamie wszelkie istniejący aplikacji oczekujących, że numer karty kredytowej będzie liczbą 16-cyfrową.

Oprócz prostych problemów z formatowaniem, przy użyciu AES-128-CBC, ten numer karty kredytowej może zostać zaszyfrowany do wartości szesnastkowej 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02 . Oprócz problemów spowodowanych tworzeniem nieprawidłowych znaków i zwiększaniem rozmiaru danych, dane zaszyfrowane przy użyciu trybu CBC algorytmu szyfrowania zmieniają również swoją wartość, gdy są odszyfrowywane i ponownie szyfrowane. Dzieje się tak, ponieważ losowa wartość początkowa który jest używany do inicjowania algorytmu szyfrowania i jest uwzględniany jako część zaszyfrowanej wartości, jest inny dla każdej operacji szyfrowania. Z tego powodu nie jest możliwe użycie danych zaszyfrowanych w trybie CBC jako unikalnego klucza do identyfikacji wiersza w bazie danych.

FPE próbuje uprościć proces przejścia, zachowując formatowanie i długość oryginalnych danych, umożliwiając zastąpienie wartości w postaci zwykłego tekstu ich zaszyfrowanymi tekstami w starszych aplikacjach.

Porównanie z prawdziwie losowymi permutacjami

Chociaż prawdziwie losowa permutacja jest idealnym szyfrem FPE, w przypadku dużych domen niewykonalne jest wstępne wygenerowanie i zapamiętanie prawdziwie losowej permutacji. Tak więc problem FPE polega na wygenerowaniu pseudolosowej permutacji z tajnego klucza w taki sposób, aby czas obliczeń dla pojedynczej wartości był mały (idealnie stały, ale przede wszystkim mniejszy niż O(N) ) .

Porównanie z szyframi blokowymi

n - bitowy szyfr blokowy jest FPE na zbiorze ${0, ..., 2 n -1$ }. Jeśli potrzebny jest FPE w jednym z tych zestawów o standardowym rozmiarze (na przykład n = 64 dla DES i n = 128 dla AES), można użyć szyfru blokowego o odpowiednim rozmiarze.

Jednak w typowym użyciu szyfr blokowy jest używany w trybie działania , który pozwala na szyfrowanie dowolnie długich wiadomości oraz z wektorem inicjującym , jak omówiono powyżej. W tym trybie szyfr blokowy nie jest FPE.

Definicja bezpieczeństwa

W literaturze kryptograficznej (patrz większość odniesień poniżej) miarą „dobrego” FPE jest to, czy atakujący może odróżnić FPE od prawdziwie losowej permutacji. Postuluje się różne typy atakujących, w zależności od tego, czy mają dostęp do wyroczni lub znanych par szyfrogram/tekst jawny.

Algorytmy

W większości wymienionych tutaj podejść dobrze rozumiany szyfr blokowy (taki jak AES ) jest używany jako prymityw zastępujący idealną funkcję losową. Ma to tę zaletę, że włączenie tajnego klucza do algorytmu jest łatwe. Tam, gdzie w poniższej dyskusji wspomniano o AES, zadziałałby również każdy inny dobry szyfr blokowy.

Konstrukcje FPE firmy Black i Rogaway

Wdrożenie FPE z bezpieczeństwem, które można udowodnić, z bezpieczeństwem podstawowego szyfru blokowego, zostało po raz pierwszy podjęte w artykule kryptografów Johna Blacka i Phillipa Rogawaya , w którym opisano trzy sposoby, aby to zrobić. Udowodnili, że każda z tych technik jest tak samo bezpieczna jak szyfr blokowy użyty do jej skonstruowania. Oznacza to, że jeśli algorytm AES jest używany do tworzenia algorytmu FPE, to wynikowy algorytm FPE jest tak samo bezpieczny jak AES, ponieważ przeciwnik zdolny do pokonania algorytmu FPE może również pokonać algorytm AES. Dlatego jeśli AES jest bezpieczny, to zbudowane na jego podstawie algorytmy FPE również są bezpieczne. We wszystkich poniższych E oznacza operację szyfrowania AES, która jest używana do konstruowania algorytmu FPE, a F oznacza operację szyfrowania FPE.

FPE z szyfru prefiksowego

Prostym sposobem na utworzenie algorytmu FPE na ${0, ..., N -1}$ jest przypisanie każdej liczby całkowitej pseudolosowej wagi, a następnie posortowanie według wagi. Wagi są definiowane przez zastosowanie istniejącego szyfru blokowego do każdej liczby całkowitej. Black i Rogaway nazywają tę technikę „szyfrem przedrostkowym” i wykazali, że jest ona prawdopodobnie tak dobra, jak zastosowany szyfr blokowy.

Zatem, aby utworzyć FPE w domenie {0,1,2,3}, mając dany klucz K , zastosuj AES( K ) do każdej liczby całkowitej, dając na przykład

 waga  (0) = 0x56c644080098fc5570f2b329323dbf62  waga  (1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7  waga  (2) = 0x47d2e1bf72264fa01fb274465e56ba20  waga  (3) = 0 x077de40941c93774857961a8a772650d

Sortowanie [0,1,2,3] według wagi daje [3,1,2,0], więc szyfr to

 fa  (0) = 3  fa  (1) = 1  fa  (2) = 2  fa  (3) = 0

Ta metoda jest użyteczna tylko dla małych wartości N . W przypadku większych wartości rozmiar tabeli przeglądowej i wymagana liczba szyfrowań do zainicjowania tabeli stają się zbyt duże, aby było to praktyczne.

FPE z chodzenia na rowerze

Jeśli istnieje zestaw M dozwolonych wartości w dziedzinie pseudolosowej permutacji P (na przykład P może być szyfrem blokowym, takim jak AES), algorytm FPE można utworzyć z szyfru blokowego, wielokrotnie stosując szyfr blokowy, aż wynik jest jedna z dozwolonych wartości (w obrębie M ).

  
         
         CycleWalkingFPE(x) {  jeśli  P  (x) jest elementem  M  to  zwróć  P  (x)  w przeciwnym razie  zwróć  CycleWalkingFPE(  P  (x)) }

Rekurencja ma gwarancję zakończenia. (Ponieważ P jest jeden do jednego, a dziedzina jest skończona, wielokrotne stosowanie P tworzy cykl, więc zaczynając od punktu w M , cykl ostatecznie zakończy się w M .)

Ma to tę zaletę, że elementy M nie muszą być odwzorowywane na kolejne sekwencje {0,..., N -1} liczb całkowitych. Ma tę wadę, że gdy M jest znacznie mniejsze niż domena P , to może być wymaganych zbyt wiele iteracji dla każdej operacji. Jeśli P jest szyfrem blokowym o stałym rozmiarze, takim jak AES, jest to poważne ograniczenie rozmiarów M , dla których ta metoda jest skuteczna.

Na przykład aplikacja może chcieć zaszyfrować wartości 100-bitowe za pomocą AES w sposób, który tworzy kolejną wartość 100-bitową. Dzięki tej technice szyfrowanie AES-128-ECB może być stosowane do momentu osiągnięcia wartości, przy której wszystkie 28 najwyższych bitów ma wartość 0, co wymaga średnio 228 ^iteracji .

FPE z sieci Feistel

Możliwe jest również wykonanie algorytmu FPE z wykorzystaniem sieci Feistela . Sieć Feistela potrzebuje źródła pseudolosowych wartości dla podkluczy dla każdej rundy, a dane wyjściowe algorytmu AES mogą być użyte jako te pseudolosowe wartości. Kiedy to zostanie zrobione, wynikowa konstrukcja Feistela jest dobra, jeśli użyto wystarczającej liczby rund.

Jednym ze sposobów implementacji algorytmu FPE przy użyciu AES i sieci Feistela jest użycie tylu bitów danych wyjściowych AES, ile jest potrzebnych do zrównania długości lewej lub prawej połowy sieci Feistela. Jeśli na przykład potrzebna jest wartość 24-bitowa jako klucz podrzędny, możliwe jest użycie najniższych 24 bitów danych wyjściowych AES dla tej wartości.

Może to nie spowodować, że dane wyjściowe sieci Feistela zachowają format danych wejściowych, ale możliwe jest iterowanie sieci Feistela w taki sam sposób, jak robi to technika chodzenia po rowerze, aby zapewnić zachowanie formatu. Ponieważ możliwe jest dostosowanie rozmiaru wejść do sieci Feistela, możliwe jest bardzo prawdopodobne, że ta iteracja zakończy się średnio bardzo szybko. Na przykład w przypadku numerów kart kredytowych jest 10 ¹⁵ możliwych 16-cyfrowych numerów kart kredytowych (uwzględniając nadmiarową cyfrę kontrolną ), a ponieważ 10 ¹⁵ ≈ 2 ^49,8 , użycie 50-bitowej sieci Feistela wraz z chodzeniem rowerowym stworzy algorytm FPE, który szyfruje średnio dość szybko.

Tasowanie Thorpa

Tasowanie Thorpa jest jak wyidealizowane tasowanie kart lub równoważnie maksymalnie niezrównoważony szyfr Feistela, w którym jedna strona to pojedynczy bit. Łatwiej jest udowodnić bezpieczeństwo niezrównoważonych szyfrów Feistela niż zrównoważonych.

tryb VIL

W przypadku rozmiarów domen, które są potęgą dwójki, i istniejącego szyfru blokowego o mniejszym rozmiarze bloku, można utworzyć nowy szyfr przy użyciu trybu VIL, jak opisał Bellare, Rogaway.

Pospieszny szyfr budyniowy

Szyfr Hasty Pudding wykorzystuje niestandardowe konstrukcje (niezależne od istniejących szyfrów blokowych jako prymitywów) do szyfrowania dowolnych skończonych małych domen.

Tryb FFSEM/FFX AES

Tryb FFSEM AES (specyfikacja), który został zaakceptowany do rozpatrzenia przez NIST, wykorzystuje opisaną powyżej konstrukcję sieciową Feistela Blacka i Rogawaya, z AES dla funkcji okrągłej, z jedną niewielką modyfikacją: używany jest pojedynczy klucz, który jest nieco zmodyfikowany dla każda runda.

Od lutego 2010 FFSEM został zastąpiony przez tryb FFX napisany przez Mihira Bellare , Phillipa Rogawaya i Terence'a Spiesa. (specyfikacja, NIST Block Cipher Modes Development , 2010 ).

FPE dla szyfrowania JPEG 2000

W standardzie JPEG 2000 kody znaczników (z zakresu od 0xFF90 do 0xFFFF) nie powinny pojawiać się w tekście jawnym i zaszyfrowanym. Prosta technika modular-0xFF90 nie może być zastosowana do rozwiązania problemu szyfrowania JPEG 2000. Na przykład słowa zaszyfrowanego tekstu 0x23FF i 0x9832 są prawidłowe, ale ich kombinacja 0x23FF9832 staje się nieważna, ponieważ wprowadza kod znacznika 0xFF98. Podobnie, prostej techniki chodzenia po rowerze nie można zastosować do rozwiązania problemu szyfrowania JPEG2000, ponieważ dwa prawidłowe bloki tekstu zaszyfrowanego mogą dać nieprawidłowy tekst zaszyfrowany, gdy zostaną połączone. Na przykład, jeśli pierwszy blok tekstu zaszyfrowanego kończy się bajtami „...30FF”, a drugi blok tekstu zaszyfrowanego zaczyna się bajtami „9832…”, wówczas w tekście zaszyfrowanym pojawi się kod znacznika „0xFF98”.

Dwa mechanizmy szyfrowania JPEG 2000 z zachowaniem formatu zostały podane w artykule „Efficient and Secure Encryption Schemes for JPEG2000” autorstwa Hongjuna Wu i Di Ma. Aby wykonać szyfrowanie JPEG 2000 z zachowaniem formatu, technika polega na wykluczeniu bajtu „0xFF” w szyfrowaniu i deszyfrowaniu. Następnie mechanizm szyfrowania JPEG 2000 wykonuje dodanie modulo-n za pomocą szyfru strumieniowego; inny mechanizm szyfrowania JPEG 2000 wykonuje technikę chodzenia po rowerze z szyfrem blokowym.

Inne konstrukcje FPE

Kilka konstrukcji FPE opiera się na dodawaniu danych wyjściowych standardowego szyfru modulo n do danych, które mają być zaszyfrowane, z różnymi metodami nieobciążającymi wyniku. Dodatek modulo-n, wspólny dla wielu konstruktów, jest natychmiast oczywistym rozwiązaniem problemu FPE (stąd jego użycie w wielu przypadkach), przy czym główne różnice to zastosowane mechanizmy bezstronności.

Sekcja 8 FIPS 74 , Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard , opisuje sposób użycia algorytmu szyfrowania DES w sposób, który zachowuje format danych poprzez dodanie modulo-n, po którym następuje bezstronna operacja. Norma ta została wycofana 19 maja 2005 r., więc technikę tę należy uznać za przestarzałą pod względem formalnym.

Innym wczesnym mechanizmem szyfrowania z zachowaniem formatu było „Szyfrowanie danych z ograniczonym zakresem wartości” Petera Gutmanna, które ponownie wykonuje dodawanie modulo-n na dowolnym szyfrze z pewnymi poprawkami, aby wynik był jednolity, a wynikowe szyfrowanie było tak silne, jak podstawowy algorytm szyfrowania, na którym jest oparty.

Artykuł „Using Datatype-Preserving Encryption to Enhance Data Warehouse Security” autorstwa Michaela Brightwella i Harry'ego Smitha opisuje sposób wykorzystania algorytmu szyfrowania DES w sposób, który zachowuje format zwykłego tekstu. Wydaje się, że ta technika nie stosuje bezstronnego kroku, podobnie jak inne techniki modulo-n, o których mowa tutaj.

Artykuł „Szyfrowanie z zachowaniem formatu” autorstwa Mihira Bellare'a i Thomasa Ristenparta opisuje wykorzystanie „prawie zrównoważonych” sieci Feistela do tworzenia bezpiecznych algorytmów FPE.

Artykuł „Format Controlling Encryption using Datatype Preserving Encryption” Ulfa Mattssona opisuje inne sposoby tworzenia algorytmów FPE.

Przykładem algorytmu FPE jest FNR (ang. Flexible Naor and Reingold ).

Akceptacja algorytmów FPE przez organy normalizacyjne

Specjalna publikacja NIST 800-38G, „Zalecenia dotyczące trybów działania szyfru blokowego: metody szyfrowania z zachowaniem formatu” określa dwie metody: FF1 i FF3. Szczegóły dotyczące propozycji złożonych dla każdego z nich można znaleźć na stronie NIST Block Cipher Modes Development, w tym informacje o patentach i wektorach testowych. Przykładowe wartości są dostępne zarówno dla FF1, jak i FF3.

FF1 to FFX [Radix] „Tryb szyfrowania oparty na Feistelu z zachowaniem formatu”, który jest również w procesach standardów zgodnych z ANSI X9 jako X9.119 i X9.124. Został przesłany do NIST przez Mihira Bellare'a z Uniwersytetu Kalifornijskiego w San Diego, Phillipa Rogawaya z Uniwersytetu Kalifornijskiego w Davis i Terence'a Spiesa z firmy Voltage Security Inc. Dostarczono wektory testowe, a ich części opatentowano. (DRAFT SP 800-38G Rev 1) wymaga, aby minimalny rozmiar domeny szyfrowanych danych wynosił 1 milion (wcześniej 100).

FF3 to BPS nazwany na cześć autorów. Został przesłany do NIST przez Erica Briera, Thomasa Peyrina i Jacquesa Sterna z Ingenico we Francji. Autorzy oświadczyli NIST, że ich algorytm nie jest opatentowany. Produkt CyberRes Voltage , choć twierdzi, że posiada własne patenty również na tryb BPS. W dniu 12 kwietnia 2017 r. NIST stwierdził, że FF3 „nie nadaje się już jako metoda FPE ogólnego przeznaczenia”, ponieważ naukowcy odkryli lukę.
FF3-1 (DRAFT SP 800-38G Rev 1) zastępuje FF3 i wymaga minimalnego rozmiaru domeny szyfrowanych danych na 1 milion (wcześniej 100).

Inny tryb został uwzględniony w projekcie wytycznych NIST, ale został usunięty przed ostateczną publikacją.

FF2 to schemat VAES3 dla FFX: dodatek do „Trybu działania FFX w celu zachowania szyfrowania”: zbiór parametrów dla ciągów szyfrujących o dowolnej podstawie z operacją podklucza w celu wydłużenia żywotności klucza szyfrującego. Został przesłany do NIST przez Joachima Vance'a z VeriFone Systems Inc. Wektory testowe nie są dostarczane oddzielnie od FF1, a ich części są opatentowane. Autorzy przesłali zmodyfikowany algorytm jako DFF, który jest aktywnie rozważany przez NIST.

Korea opracowała również standard FPE, FEA-1 i FEA-2.

Implementacje

Implementacje Open Source FF1 i FF3 są publicznie dostępne w językach C , Go , Java , Node.js , Python , C#/.Net i Rust