Wypełnienie (kryptografia) - Padding (cryptography)

Ten artykuł dotyczy kryptografii. Dla innych zastosowań tego terminu, zobacz Padding (ujednoznacznienie) .

W kryptografii , wyściółka jest jedną z szeregu odrębnych praktyk które obejmują dodawanie danych do początku, w środku lub na końcu wiadomości przed szyfrowaniem. W klasycznej kryptografii dopełnienie może polegać na dodawaniu do wiadomości bezsensownych fraz, aby ukryć fakt, że wiele wiadomości kończy się w przewidywalny sposób, np. z poważaniem .

Kryptografia klasyczna

Oficjalne wiadomości często zaczynają się i kończą w przewidywalny sposób: Mój drogi ambasadorze, Raport pogodowy, Z poważaniem itp. Podstawowym zastosowaniem dopełniania klasycznymi szyframi jest uniemożliwienie kryptoanalitykowi wykorzystania tej przewidywalności w celu znalezienia znanego tekstu jawnego, który pomaga w złamaniu szyfrowania. Dopełnienie losowej długości uniemożliwia także osobie atakującej poznanie dokładnej długości wiadomości w postaci zwykłego tekstu.

Słynnym przykładem klasycznego wypełnienia, które spowodowało wielkie nieporozumienie, jest incydent z „ cudami świata ”, który prawie spowodował stratę aliantów w bitwie II wojny światowej u podnóża Samar , będącej częścią większej bitwy w zatoce Leyte . W tym przykładzie admirał Chester Nimitz , naczelny dowódca amerykańskiej floty na Pacyfiku podczas II wojny światowej, wysłał następującą wiadomość do admirała Bulla Halseya , dowódcy Task Force Thirty Four (głównej floty alianckiej) w bitwie w zatoce Leyte, dnia 25 października 1944:

Gdzie jest, powtarzam, gdzie jest grupa zadaniowa trzydzieści cztery?

Po dodaniu dopełnienia (pogrubienia) i metadanych wiadomość stała się:

TURKEY TROTS TO WATER GG FROM CINCPAC ACTION COM THIRD FLEET INFO COMINCH CTF SEVENTY-SEVEN X WHERE IS RPT WHERE IS TASK FORCE THIRTY FOUR RR THE WORLD WONDERS

Operator radiowy Halsey pomylił część dopełnienia wiadomości, więc admirał Halsey przeczytał następującą wiadomość:

Gdzie jest, powtarzam, gdzie jest grupa zadaniowa trzydzieści cztery? Świat zastanawia się

Admirał Halsey zinterpretował wyściółkę „Cuda świata” jako sarkastyczną naganę, powodując emocjonalny wybuch, a następnie zamknął się w swoim moście i dąsał się na godzinę, zanim przeniósł swoje siły, aby pomóc w bitwie pod Samarem. Radiooperator Halseya powinien był zostać poinformowany o literach RR, że „zastanawia się świat”; wszyscy inni radiooperatorzy, którzy otrzymali wiadomość od admirała Nimitza, poprawnie usunęli obie frazy wypełniające.

Wiele klasycznych szyfrów układa tekst jawny w określone wzorce (np. kwadraty, prostokąty itp.) i jeśli tekst jawny nie pasuje dokładnie, często konieczne jest dodanie dodatkowych liter w celu wypełnienia wzorca. Używanie w tym celu bezsensownych liter ma dodatkową zaletę, ponieważ utrudnia niektóre rodzaje kryptoanalizy.


Kryptografia symetryczna

Funkcje haszujące

Większość nowoczesnych kryptograficznych funkcji skrótu przetwarza wiadomości w blokach o stałej długości; wszystkie oprócz najwcześniejszych funkcji haszujących zawierają jakiś schemat dopełnienia. Kluczowe znaczenie dla funkcji skrótu kryptograficznego ma stosowanie schematów zakańczania, które zapobiegają podatności skrótu na ataki wydłużające .

Wiele schematów dopełniania opiera się na dołączaniu przewidywalnych danych do ostatniego bloku. Na przykład pad może być wyprowadzony z całkowitej długości wiadomości. Ten rodzaj dopełnienia jest powszechnie stosowany do algorytmów mieszających, które używają konstrukcji Merkle-Damgård, takich jak rodzina MD-5 , SHA-1 i SHA-2, taka jak SHA-224, SHA-256, SHA-384, SHA-512 , SHA512/224 i SHA-512/256

Tryb pracy z szyfrem blokowym

Elektroniczna książka kodowa i łańcucha bloków szyfru (tryb CBC) są przykładami trybie szyfr blokowy działania . Tryby szyfrowania blokowego dla algorytmów szyfrowania z kluczem symetrycznym wymagają wprowadzania zwykłego tekstu, który jest wielokrotnością rozmiaru bloku, więc może być konieczne uzupełnienie wiadomości, aby doprowadzić je do tej długości.

Obecnie nastąpiła zmiana na używanie trybu przesyłania strumieniowego zamiast trybu blokowego. Przykładem szyfrowania w trybie strumieniowym jest tryb działania licznika . Tryby działania strumieniowego mogą szyfrować i odszyfrowywać wiadomości o dowolnym rozmiarze i dlatego nie wymagają wypełniania. Bardziej skomplikowane sposoby kończenia wiadomości, takie jak kradzież tekstu zaszyfrowanego lub kończenie pozostałych bloków, pozwalają uniknąć dopełniania.

Wadą dopełniania jest to, że zwykły tekst wiadomości staje się podatny na ataki wyroczni z dopełnieniem . Ataki typu padding oracle pozwalają atakującemu na zdobycie wiedzy o czystym tekście bez atakowania samego prymitywu szyfru blokowego. Ataków dopełniających wyroczni można uniknąć, upewniając się, że atakujący nie może zdobyć wiedzy na temat usuwania bajtów dopełniających. Można to osiągnąć poprzez weryfikację kodu uwierzytelniania wiadomości (MAC) lub podpisu cyfrowego przed usunięciem bajtów dopełniających lub przez przełączenie na tryb działania strumieniowego.

Bit padding

Dopełnienie bitowe można zastosować do wiadomości o dowolnym rozmiarze.

Do komunikatu dodawany jest pojedynczy bit zestawu („1”), a następnie dodawana jest wymagana liczba bitów resetowania („0”) (być może żaden). Liczba dodanych bitów resetowania („0”) będzie zależeć od granicy bloku, do której należy rozszerzyć komunikat. W kategoriach bitowych jest to „1000 ... 0000”.

Ta metoda może być używana do wypełniania wiadomości, które mają dowolną liczbę bitów, niekoniecznie całą liczbę bajtów. Na przykład wiadomość o długości 23 bitów, która jest uzupełniona 9 bitami w celu wypełnienia 32-bitowego bloku: 

... | 1011 1001 1101 0100 0010 0111 0000 0000 |

To dopełnienie jest pierwszym krokiem dwuetapowego schematu dopełniania używanego w wielu funkcjach skrótu, w tym MD5 i SHA . W tym kontekście określa to RFC1321 krok 3.1.

Ten schemat dopełnienia jest zdefiniowany w normie ISO/IEC 9797-1 jako metoda dopełniania 2.

Dopełnienie bajtów

Dopełnienie bajtów można zastosować do wiadomości, które mogą być zakodowane jako całkowita liczba bajtów .

ANSI X9.23

W ANSI X9.23 jako wypełnienie zawsze dodawane jest od 1 do 8 bajtów. Blok jest dopełniany losowymi bajtami (chociaż wiele implementacji używa 00), a ostatni bajt bloku jest ustawiony na liczbę dodanych bajtów.

Przykład: W poniższym przykładzie rozmiar bloku wynosi 8 bajtów, a dopełnienie jest wymagane dla 4 bajtów (w formacie szesnastkowym) 

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |
ISO 10126

ISO 10126 (wycofany, 2007) określa, że ​​dopełnienie powinno być wykonane na końcu ostatniego bloku losowymi bajtami, a granica dopełnienia powinna być określona przez ostatni bajt.

Przykład: W poniższym przykładzie rozmiar bloku wynosi 8 bajtów, a dopełnienie jest wymagane dla 4 bajtów 

... | DD DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 |
PKCS#5 i PKCS#7

PKCS#7 jest opisany w RFC 5652 .

Dopełnienie jest w całych bajtach. Wartość każdego dodanego bajtu to liczba dodanych bajtów, tj. N bajtów, każdy o wartości N jest dodawanych. Liczba dodanych bajtów będzie zależeć od granicy bloku, do której należy rozszerzyć wiadomość.

Wypełnienie będzie jednym z: 

01
02 02
03 03 03
04 04 04 04
05 05 05 05 05
06 06 06 06 06 06
etc.

Ta metoda dopełniania (podobnie jak dwie poprzednie) jest dobrze zdefiniowana wtedy i tylko wtedy, gdy N jest mniejsze niż 256.

Przykład: W poniższym przykładzie rozmiar bloku wynosi 8 bajtów, a dopełnienie jest wymagane dla 4 bajtów 

... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |

Jeśli długość oryginalnych danych jest całkowitą wielokrotnością rozmiaru bloku B , dodawany jest dodatkowy blok bajtów o wartości B. Jest to konieczne, aby algorytm deszyfrowania mógł z całą pewnością określić, czy ostatni bajt ostatniego bloku jest bajtem wypełniającym, wskazującym liczbę dodanych bajtów wypełniających, czy też częścią wiadomości w postaci zwykłego tekstu. Rozważ wiadomość w postaci zwykłego tekstu, która jest całkowitą wielokrotnością B bajtów, przy czym ostatnim bajtem zwykłego tekstu jest 01 . Bez dodatkowych informacji algorytm deszyfrujący nie będzie w stanie określić, czy ostatni bajt jest bajtem zwykłego tekstu, czy bajtem wypełniacza. Jednak dodając B bajtów każdy o wartości B po bajcie tekstu jawnego 01 , algorytm deszyfrujący może zawsze traktować ostatni bajt jako bajt wypełniający i usuwać odpowiednią liczbę bajtów wypełniających z końca zaszyfrowanego tekstu; wspomniana liczba bajtów do usunięcia na podstawie wartości ostatniego bajtu.

Dopełnienie PKCS#5 jest identyczne z dopełnieniem PKCS#7, z wyjątkiem tego, że zostało zdefiniowane tylko dla szyfrów blokowych, które używają 64-bitowego (8-bajtowego) rozmiaru bloku. W praktyce można je stosować zamiennie.

ISO/IEC 7816-4

Norma ISO/IEC 7816 -4:2005 jest identyczna ze schematem dopełniania bitów, stosowanym do zwykłego tekstu o długości N bajtów. W praktyce oznacza to, że pierwszy bajt jest bajtem obowiązkowym o wartości '80' (szesnastkowo), po którym, w razie potrzeby, następuje od 0 do N  -1 bajtów ustawionych na '00', aż do osiągnięcia końca bloku. Sama norma ISO/IEC 7816-4 jest standardem komunikacji dla kart inteligentnych zawierającym system plików i sama w sobie nie zawiera żadnych specyfikacji kryptograficznych.

Przykład: W poniższym przykładzie rozmiar bloku wynosi 8 bajtów, a dopełnienie jest wymagane dla 4 bajtów 

... | DD DD DD DD DD DD DD DD | DD DD DD DD 80 00 00 00 |

Następny przykład pokazuje wypełnienie tylko jednego bajtu 

... | DD DD DD DD DD DD DD DD | DD DD DD DD DD DD DD 80 |

Zerowy dopełnienie

Wszystkie bajty, które muszą zostać uzupełnione, są dopełniane zerem. Schemat zerowego dopełnienia nie został ustandaryzowany pod kątem szyfrowania, chociaż jest określony dla skrótów i MAC jako Metoda dopełniania 1 w normach ISO/IEC 10118-1 i ISO/IEC 9797-1 .

Przykład: W poniższym przykładzie rozmiar bloku wynosi 8 bajtów, a dopełnienie jest wymagane dla 4 bajtów 

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 00 |

Dopełnienie zerami może nie być odwracalne, jeśli oryginalny plik kończy się jednym lub większą liczbą bajtów zerowych, co uniemożliwia rozróżnienie między bajtami danych w postaci zwykłego tekstu a bajtami dopełnienia. Może być używany, gdy długość wiadomości może być wyprowadzona poza pasmem . Jest często stosowany do ciągów zakodowanych binarnie ( ciąg zakończony znakiem null ) , ponieważ znak null można zwykle usunąć jako spację .

Dopełnienie zerowe jest czasami określane również jako „dopełnienie zerowe” lub „dopełnienie zerowe”. Niektóre implementacje mogą dodawać dodatkowy blok zerowych bajtów, jeśli tekst jawny jest już podzielny przez rozmiar bloku.

Kryptografia klucza publicznego

W kryptografii klucza publicznego wypełnienie to proces przygotowywania wiadomości do szyfrowania lub podpisywania przy użyciu specyfikacji lub schematu, takiego jak PKCS#1 v1.5, OAEP , PSS , PSSR, IEEE P1363 EMSA2 i EMSA5. Nowoczesną formą dopełniania asymetrycznych prymitywów jest OAEP stosowany do algorytmu RSA , gdy jest używany do szyfrowania ograniczonej liczby bajtów.

Operacja jest określana jako „dopełnienie”, ponieważ pierwotnie losowy materiał był po prostu dodawany do wiadomości, aby była wystarczająco długa dla prymitywu. Ta forma wypełnienia nie jest bezpieczna i dlatego nie jest już stosowana. Nowoczesny schemat dopełnienia ma na celu zapewnienie, że atakujący nie może manipulować tekstem jawnym w celu wykorzystania matematycznej struktury prymitywu i zwykle towarzyszy mu dowód, często w losowym modelu wyroczni , że złamanie schematu dopełnienia jest tak trudne, jak rozwiązanie trudnego problem leżący u podstaw prymitywu.

Analiza i ochrona ruchu poprzez padding

Nawet jeśli używane są doskonałe procedury kryptograficzne, atakujący może uzyskać wiedzę o ilości wygenerowanego ruchu. Atakujący może nie wiedzieć, co Alicja i Bob zostali mówisz, ale może wiedzieć, że one były rozmowy i jak dużo rozmawiali. W niektórych okolicznościach ten wyciek może być bardzo kompromitujący. Rozważmy na przykład, kiedy wojsko organizuje tajny atak na inny naród: może wystarczyć zaalarmować ten naród, aby wiedział tylko, że odbywa się wiele tajnych działań.

Jako inny przykład, podczas szyfrowania strumieni Voice Over IP, które używają kodowania ze zmienną szybkością transmisji bitów, liczba bitów na jednostkę czasu nie jest zasłonięta, co można wykorzystać do odgadnięcia wypowiadanych fraz. Podobnie, wzorce serii, które są tworzone przez zwykłe kodery wideo, są często wystarczające do jednoznacznego zidentyfikowania strumienia wideo oglądanego przez użytkownika. Nawet całkowity rozmiar samego obiektu, takiego jak strona internetowa, plik, pobrany pakiet oprogramowania lub wideo online, może jednoznacznie zidentyfikować obiekt, jeśli atakujący zna lub może odgadnąć znany zbiór, z którego pochodzi obiekt. Kanał boczny o długości zaszyfrowanej treści został wykorzystany do wyodrębnienia haseł z komunikacji HTTPS w dobrze znanych atakach CRIME i BREACH .

Uzupełnienie zaszyfrowanej wiadomości może utrudnić analizę ruchu , zasłaniając prawdziwą długość jej ładunku. Wybór długości do wypełnienia wiadomości może być dokonany deterministycznie lub losowo; każde podejście ma mocne i słabe strony, które mają zastosowanie w różnych kontekstach.

Randomizowane dopełnienie

Na końcu wiadomości może być dołączona losowa liczba dodatkowych bitów lub bajtów dopełnienia, wraz ze wskazaniem na końcu, ile zostało dodanego wypełnienia. Jeśli wielkość wypełnienia zostanie wybrana jako jednolita liczba losowa między 0 a pewnym maksymalnym M, na przykład podsłuchujący nie będzie w stanie dokładnie określić długości wiadomości w tym zakresie. Jeśli maksymalne wypełnienie M jest małe w porównaniu z całkowitym rozmiarem wiadomości, to wypełnienie to nie spowoduje znacznego obciążenia , ale wypełnienie przesłoni tylko najmniej znaczące bity całkowitej długości obiektu, pozostawiając przybliżoną długość dużych obiektów łatwo obserwowalną i stąd nadal potencjalnie jednoznacznie identyfikowalne na podstawie ich długości. Jeśli maksymalne wypełnienie M jest porównywalne z rozmiarem ładunku, w przeciwieństwie do tego, niepewność podsłuchującego co do rzeczywistego rozmiaru ładunku wiadomości jest znacznie większa, kosztem tego, że wypełnienie może sumować się do 100% narzutu ( 2× powiększenie) do wiadomość.

Ponadto w typowych scenariuszach, w których podsłuchujący ma możliwość zobaczenia wielu kolejnych wiadomości od tego samego nadawcy, a wiadomości te są podobne w sposób, w jaki atakujący wie lub może się domyślić, podsłuchujący może użyć technik statystycznych, aby zmniejszyć, a ostatecznie nawet wyeliminować korzyść z randomizowanego dopełnienia. Załóżmy na przykład, że aplikacja użytkownika regularnie wysyła wiadomości o tej samej długości, a podsłuchujący zna lub może odgadnąć fakty na podstawie na przykład odcisków palców aplikacji użytkownika. Alternatywnie, aktywny atakujący może być w stanie nakłonić punkt końcowy do regularnego wysyłania wiadomości, na przykład w przypadku, gdy ofiarą jest serwer publiczny. W takich przypadkach podsłuchujący może po prostu obliczyć średnią z wielu obserwacji, aby określić długość ładunku zwykłej wiadomości.

Deterministyczne dopełnienie

Deterministyczny schemat wypełniania zawsze wypełnia ładunek wiadomości o określonej długości w celu utworzenia zaszyfrowanego komunikatu o określonej odpowiadającej długości wyjściowej. Gdy wiele długości ładunku mapuje się na tę samą długość wyściełanego wyjścia, podsłuchujący nie może odróżnić ani poznać żadnych informacji o prawdziwej długości ładunku w jednym z tych wiader długości , nawet po wielu obserwacjach przesyłanych komunikatów o tej samej długości. Pod tym względem, deterministyczne schematy wypełniania mają tę zaletę, że nie ujawniają żadnych dodatkowych informacji z każdym kolejnym komunikatem o tym samym rozmiarze ładunku.

Z drugiej strony załóżmy, że podsłuchujący może skorzystać na poznaniu niewielkich różnic w rozmiarze ładunku, takich jak plus lub minus tylko jeden bajt w przypadku ataku polegającego na zgadywaniu hasła. Jeśli nadawca wiadomości ma pecha, aby wysłać wiele wiadomości, których długość ładunku różni się tylko o jeden bajt, a ta długość znajduje się dokładnie na granicy dwóch deterministycznych klas wypełnienia, wówczas te plus-minusy długości ładunku będą konsekwentnie dawały różne również długości wyściełane (na przykład plus-lub-minus jeden blok), przeciekające dokładnie te szczegółowe informacje, których pragnie atakujący. Przeciwko takim zagrożeniom randomizowane dopełnienie może zapewnić większą ochronę poprzez niezależne zasłanianie najmniej znaczących bitów długości wiadomości.

Typowe metody dopełniania deterministycznego obejmują dopełnienie do stałego rozmiaru bloku i dopełnienie do następnej, większej potęgi dwójki. Podobnie jak w przypadku randomizowanego wypełniania z niewielką maksymalną wartością  M , jednak wypełnianie deterministycznie do rozmiaru bloku znacznie mniejszego niż ładunek wiadomości zasłania tylko najmniej znaczące bity prawdziwej długości wiadomości, pozostawiając rzeczywistą przybliżoną długość wiadomości w dużej mierze niezabezpieczoną. Uzupełnianie wiadomości do potęgi dwójki (lub dowolnej innej stałej podstawy) zmniejsza maksymalną ilość informacji, które wiadomość może przeciekać przez jej długość od O (log M ) do O (log log M ) . Dopełnienie do potęgi dwójki zwiększa jednak narzut rozmiaru wiadomości nawet o 100%, a dopełnienie do potęg większych liczb całkowitych dodatkowo zwiększa maksymalny narzut.

Schemat PADMÉ, zaproponowany dla wypełnianych jednolitych losowych blobów lub PURB , deterministycznie wypełnia wiadomości do długości reprezentowanych jako liczba zmiennoprzecinkowa, której mantysa nie jest już (tj. nie zawiera więcej znaczących bitów) niż jej wykładnik. To ograniczenie długości zapewnia, że ​​wiadomość przecieka co najwyżej O (log log M ) bitów informacji poprzez swoją długość, jak dopełnienie do potęgi dwójki, ale wiąże się ze znacznie mniejszym obciążeniem, najwyżej 12% dla małych wiadomości i zmniejsza się stopniowo wraz z rozmiarem wiadomości .

Zobacz też

Bibliografia

Dalsza lektura