Szyfrowanie deterministyczne
Deterministyczny dla schemat szyfrowania (w przeciwieństwie do probabilistycznego schematu szyfrowania) to kryptosystem , który zawsze tworzy ten sam tekst zaszyfrowany danego tekstu jawnego i klucza , nawet przy oddzielnych wykonaniach algorytmu szyfrowania. Przykłady deterministycznych algorytmów szyfrowania obejmują RSA (bez dopełnienia szyfrowania) i wiele szyfrów blokowych , gdy są używane w trybie EBC lub ze stałym wektorem inicjującym .
Przeciek
Szyfrowanie deterministyczne może spowodować wyciek informacji do podsłuchującego, który może rozpoznać znane zaszyfrowane teksty. Na przykład, gdy przeciwnik dowiaduje się, że dany zaszyfrowany tekst odpowiada jakiejś interesującej wiadomości, może się czegoś dowiedzieć za każdym razem, gdy ten zaszyfrowany tekst jest przesyłany. Aby uzyskać informacje o znaczeniu różnych zaszyfrowanych tekstów, przeciwnik może przeprowadzić analizę statystyczną wiadomości przesyłanych zaszyfrowanym kanałem lub spróbować skorelować zaszyfrowane teksty z obserwowanymi działaniami (np. zauważając, że dany zaszyfrowany tekst jest zawsze odbierany bezpośrednio przed nurkowaniem łodzi podwodnej) . Ta obawa jest szczególnie poważna w przypadku kryptografii z kluczem publicznym , gdzie każda ze stron może zaszyfrować wybrane wiadomości przy użyciu publicznego klucza szyfrującego. W takim przypadku przeciwnik może zbudować duży „słownik” użytecznych par tekst jawny/zaszyfrowany, a następnie obserwować zaszyfrowany kanał w celu dopasowania zaszyfrowanych tekstów.
Aplikacje
Chociaż deterministyczne schematy szyfrowania nigdy nie mogą być semantycznie bezpieczne , mają pewne zalety w stosunku do schematów probabilistycznych.
Przeszukiwanie bazy danych zaszyfrowanych danych
Jedną z głównych motywacji stosowania szyfrowania deterministycznego jest wydajne wyszukiwanie zaszyfrowanych danych. Załóżmy, że klient chce zlecić bazę danych potencjalnie niezaufanemu dostawcy usług bazodanowych. Jeśli każdy wpis jest szyfrowany przy użyciu systemu kryptograficznego z kluczem publicznym, każdy może dodawać wpisy do bazy danych i tylko wyróżniający się „odbiorca”, który ma klucz prywatny, może odszyfrować wpisy w bazie danych. Jeśli jednak odbiorca chce wyszukać konkretny rekord w bazie danych, staje się to bardzo trudne. Istnieje kilka schematów szyfrowania klucza publicznego, które umożliwiają wyszukiwanie słów kluczowych, jednak wszystkie te schematy wymagają liniowego czasu wyszukiwania w rozmiarze bazy danych. Gdyby wpisy w bazie danych zostały zaszyfrowane schematem deterministycznym i posortowane, to w czasie logarytmicznym można by pobrać określone pole bazy danych.
Bezpieczeństwo
Zakładając, że zastosowany zostanie deterministyczny schemat szyfrowania, ważne jest, aby zrozumieć, jaki jest maksymalny poziom bezpieczeństwa, który można zagwarantować.
Szereg prac skupiało się na tym właśnie problemie. Pierwsza praca mająca na celu rygorystyczne zdefiniowanie bezpieczeństwa dla schematu deterministycznego miała miejsce w CRYPTO 2007 . Ta praca dostarczyła dość silnych definicji bezpieczeństwa (chociaż słabszych niż bezpieczeństwo semantyczne) i dała konstrukcje w losowym modelu wyroczni . Dwie kolejne prace pojawiły się w następnym roku w CRYPTO 2008, podając równoważności definicyjne i konstrukcje bez przypadkowych wyroczni.
Alternatywy dla szyfrowania deterministycznego
Aby przeciwdziałać temu problemowi, kryptografowie zaproponowali pojęcie szyfrowania „randomizowanego” lub probabilistycznego . W ramach tych schematów dany tekst jawny można zaszyfrować do jednego z bardzo dużego zestawu możliwych tekstów zaszyfrowanych, wybranych losowo podczas procesu szyfrowania. Przy wystarczająco silnych gwarancjach bezpieczeństwa proponowane powyżej ataki stają się niewykonalne, ponieważ przeciwnik nie będzie w stanie skorelować dowolnych dwóch szyfrów tej samej wiadomości ani skorelować wiadomości z jej zaszyfrowanym tekstem, nawet mając dostęp do publicznego klucza szyfrującego. Ta gwarancja jest znana jako bezpieczeństwo semantyczne lub nierozróżnialność tekstu zaszyfrowanego i ma kilka definicji w zależności od zakładanych możliwości atakującego (patrz bezpieczeństwo semantyczne ).
Zobacz też
- Szyfrowanie konwergentne
- Szyfrowanie zachowujące format
- Szyfrowanie symetryczne z możliwością wyszukiwania
- Mihir Bellare i Alexandra Boldyreva i Adam O'Neill, Deterministic and Efficiently Searchable Encryption, CRYPTO 2007 [1] [2]
- Alexandra Boldyreva i Serge Fehr i Adam O'Neill, O pojęciach bezpieczeństwa dla szyfrowania deterministycznego i wydajnych konstrukcjach bez losowych wyroczni, CRYPTO 2008 [3] [4]
- Mihir Bellare i Marc Fischlin oraz Adam O'Neill i Thomas Ristenpart, Deterministyczne szyfrowanie: definicyjne równoważności i konstrukcje bez losowych wyroczni, CRYPTO 2008 [5] [6]