GCM (tryb Galois / Counter), w szczególności w połączeniu z AES, był de facto złotym standardem od lat. Szyfruj i uwierzytelniaj w jednym kroku, to po prostu zbyt niesamowite, a terminy takie jak AEAD działają dobrze, jeśli chodzi o zaimponowanie dziewczynie, więc to byłoby korzystne dla obu stron. Ale żartuj na bok …
zawsze się zastanawiałem, co sprawia, że jest tak wyjątkowy, a im dłużej o tym myślę, tym mniej rozumiem. Jeśli na to spojrzysz, to ogólna magia nie jest wcale taka niesamowita. A może jestem po prostu zbyt głupi, żeby to zrozumieć (stąd moje pytanie).
Moje przemyślenia:
Przede wszystkim GCM jest formą trybu licznika . Co oznacza, że w przeciwieństwie do np. łańcuch bloków szyfrowania, wyjście jednego bloku zależy od dokładnie jednego bloku wejściowego. Co gorsza: możesz zmodyfikować pojedynczy bit, a odszyfrowany wynik będzie się różnił dokładnie tym bitem. Bo jeśli jesteś uczciwy, szyfr blokowy w trybie licznika nie jest w ogóle ” szyfrem blokowym „, ale (z kluczem) PRNG po którym następuje operacja XOR. Zasadniczo ” blokowy ” szyfr strumieniowy. Nie trzeba wiele wyobrazić sobie scenariusza, w którym ktoś mógłby nadużyć tego, aby zmienić wiadomości w szkodliwy sposób (np. Zmienić ” transakcję: +5 000 \ $ ” do ” transakcji: -5 000 \ $ „). Szyfry blokowe mają zwykle wrodzoną właściwość przekształcania się w kompletny bełkot gdy przerzucasz jeden bit (plus, z łańcuchem, całą pozostałą część wiadomości). To właściwie całkiem fajna, pożądana właściwość, którą po prostu wyrzuciliśmy za burtę bez dobrego powodu.
Jasne, z uwierzytelniaczem , powyższy atak jest trudny do osiągnięcia, ponieważ naruszenie zostanie wykryte. Ale w zasadzie, uwierzytelniacz rozwiązuje tylko problem, który wprowadził wybór trybu działania .
GHASH to MAC, który obsługuje dodatkowe uwierzytelnione dane. Z tego, co wiem, jest to zwykłe kłamstwo. Lub nazwij to ” optymistyczną przesadą „, jeśli wolisz. To po prostu funkcja kompresji z nieintuicyjną matematyką (dla nie-matematyków) w tyle, ale na końcu robi tylko zwykłe mnożenie i odrzucanie połowy bitów wejściowych odpowiednikiem ” przepełnienie „. I właśnie to, z bardziej przyziemną matematyką, można zrobić w dwóch wierszach kodu w języku C na blok w ciągu kilkunastu cykli (lub jeśli nie przeszkadza ci używanie 32-bitowych mnożeń zamiast 64, można to zrobić równolegle, np. Z AVX2 ” s vpmulld na dwa pełne bloki w ~ 4 cyklach).
Ci, którzy nadal pamiętają IDEA, przypomną sobie, że używali mod dodawania 2 16 i mod mnożenia 2 16 + 1 jako S-boxy, które miały tę fajną właściwość, że były odwracalne (trochę to konieczne, jeśli chcesz odszyfrować). Niestety, nie można tego rozszerzyć do 32-bitowych, ponieważ 2 32 +1 nie jest liczba pierwsza, więc nie gwarantujemy, że wszystkie dane wejściowe będą względnie pierwsze, a zatem masz problem z odwróceniem operacji. Ale… to w naszym przypadku w porządku, nie chcemy nasza funkcja kompresji ma być odwracalna! Więc naprawdę, ” prosta „, zwykłe mnożenie też powinno załatwić sprawę?
A więc ta prosta, bez specjalnego, bez magii kompresja funkcja jest zainicjowana za pomocą klucza i IV, co przypadkowo sprawia, że ostateczne dane wyjściowe zależą od klucza w taki czy inny sposób, więc ta zwykła funkcja skutecznie staje się MAC. Jeśli masz ” dodatkowe dane „, po prostu umieszczasz je w hashu przed zaszyfrowaniem danych i gotowe. Ponownie, to nie jest coś super specjalnego.
Ogólnie rzecz biorąc, nie ma nic, czego nie można by osiągnąć za pomocą prawie każdej innej funkcji skrótu .
Teraz Galois / counter zakłada, że będzie używany tryb licznika. Tryb licznika (i jego pochodne), a także GHASH mają tę zaletę, że można szyfrować / odszyfrowywać bloki równolegle. Ponadto GHASH jest trywialnie równoległy.
Tak, wydajność ! Ale bądźmy szczerzy, czy to naprawdę zaleta, czy raczej ogromna wada ?
Czy ma znaczenie, ile czasu zajmie odszyfrowanie pliku o rozmiarze gigabajta lub terabajta wiadomość i jak dobrze można zrównoleglenie tej pracy? Lub aplikacje, w których absolutnie chcesz mieć możliwość ” wyszukiwania ” w losowych pozycjach? Cóż, na pewno są aplikacje, w których może to mieć znaczenie. Przychodzi mi na myśl pełne szyfrowanie dysku. Ale w takim przypadku nie chcesz używać GCM, ponieważ chcesz, aby rozmiar wejściowy i wyjściowy były identyczne.
W przypadku zajętego serwera (lub sieci VPN) będzie to miało znaczenie, a przynajmniej tak się wydaje , ale i tak mogą przetwarzać wszystko równolegle, ponieważ mają wiele równoczesnych połączeń.Zatem to, czy możesz zrównoleglać jeden strumień, ogólnie nie ma znaczenia. A co z aplikacjami, w których jest tylko kilka połączeń? Cóż, normalnie nie przesyłasz terabajtów danych przez terminal logowania, a jeśli to zrobisz, Twoje połączenie internetowe i tak nadal jest prawdopodobnie czynnikiem ograniczającym, ponieważ wydajność pojedynczego rdzenia z łatwością przewyższa przepustowość GbE nawet na 7-8-letnich procesorach do komputerów stacjonarnych .
W porządku, być może będziesz musiał poczekać 2-3 sekundy dłużej podczas rozpakowywania zaszyfrowanego pliku 2TB 7z na dysku twardym (jeśli tworzenie tysięcy wpisów katalogu nie jest naprawdę wąskim gardłem, do którego skłaniam się uwierzysz). Jak często robiłeś to w ciągu ostatniego roku? Ja: zero razy.
Jedynymi, dla których to naprawdę robi różnicę, są ” złoczyńcy „, czyli dokładnie ci, którym nie chcesz mieć łatwego życia. Oczywiście, jeśli możesz trywialnie zrównoleglać, ataki staną się znacznie łatwiejsze. Rzuć pokój pełen dedykowanego sprzętu (GPU, FPGA, cokolwiek) do rozwiązania problemu i pozwól mu się rozwikłać. Brak konieczności komunikacji między węzłami? Cóż, idealnie, nie może być lepiej.
Czy to naprawdę zaleta? Nie wiem, dla mnie wygląda to na ogromną wadę. Jeśli już, chciałbym uczynić tworzenie równoległych tak trudnymi, jak to tylko możliwe, a nie tak łatwymi, jak to tylko możliwe.
A więc … dość zastanawiania się i do pytania:
brakuje mi podstawowej rzeczy w GCM, która czyni go tak niesamowitym, że absolutnie powinieneś go używać?
Komentarze
- Ale kim są ” złoczyńców ” jest niemożliwe do zdefiniowania. Ma to OGROMNY wpływ na zalecenia rządowe i odpowiedzi na tym forum.
Odpowiedź
TL; DR: GCM zapewnia doskonałą wydajność z najlepszymi właściwościami bezpieczeństwa, jakich oczekujemy od szyfrów (AEAD).
GCM używa CTR do tworzenia szyfru strumieniowego. Jest to dobrze zbadana metoda, która ma tylko jedną wadę: absolutnie wymaga uwierzytelnienia, aby zapobiec przerzucaniu bitów. Przed GCM rozwiązaniem był CTR-then-MAC. Jedną z głównych zalet szyfrów strumieniowych jest brak ataków dopełniających (ponieważ nie ma potrzeby wypełniania). Kolejną zaletą jest to, że AES-CTR może skorzystać z instrukcji AES-NI.
GCM to CTR-then-MAC z lepszą wydajnością . Jednym z kluczowych ulepszeń w stosunku do CRT-then-MAC jest możliwość nakładania się szyfrowania i uwierzytelniania. Co więcej, udowodniono, że jest bezpieczny w konkretnym modelu bezpieczeństwa i nie jest obciążony patentami, więc jego użycie jest łatwe.
Ma pewne wady: nie jest wydajny w sprzęcie wbudowanym i jest to trudne do wydajnej implementacji. Ostatni punkt jest kontrowany przez użycie bibliotek napisanych przez innych. To są jednak powody, dla których xchacha20-poly1305 stał się popularny w porównaniu z GCM.
Komentarze
- Innym powodem, dla którego ChaCha20 zyskał popularność, jest to, że nie AES. Nie ' nie zrozum mnie źle, AES to świetny algorytm, ale umieszczenie dosłownie wszystkich naszych jajek w jednym koszyku może nie jest najmądrzejszym ze wszystkich pomysłów. Posiadanie jeszcze jednego dobrze przetestowanego algorytmu oprócz AES jest bardzo cenne.
- @ MechMK1 Zgadzam się z Tobą , ale nie napisałem, że to wszystkie przyczyny popularności ChaCha20 ', ponieważ ' To nie jest pytanie zadane tutaj. Chodziło mi o t kapelusz GCM nie jest uważany za ” niesamowity „, jak myśli OP.
- Absolutnie prawda. To ' nie jest złotą gęsią, ale nikt nigdy nie został zwolniony za używanie AES-GCM, że tak powiem.
- I to ' nie są obciążone patentami.
- @StephenTouset Dzięki, zredagowałem swój post, aby dołączyć Twój komentarz.
Odpowiedź
Przede wszystkim GCM jest formą trybu licznika. Co oznacza, że w przeciwieństwie do np. łańcuch bloków szyfrowania, wyjście jednego bloku zależy od dokładnie jednego bloku wejściowego. Co gorsza: możesz zmodyfikować pojedynczy bit, a odszyfrowany wynik będzie się różnił dokładnie tym bitem. Ponieważ, jeśli jesteś uczciwy, szyfr blokowy w trybie licznika wcale nie jest „szyfrem blokowym”, ale (z kluczem) PRNG, po którym następuje operacja XOR. Zasadniczo „blokowy” szyfr strumieniowy. Nie trzeba dużo wyobrazić sobie scenariusza, w którym ktoś mógłby nadużyć tego, aby zmienić wiadomości w szkodliwy sposób (np. Zmienić „transakcję: +5 000 \ $” na „transakcję: -5 000 \ $”).
Uwierzytelnianie wiadomości, które GCM nakłada na CTR, sprawia, że jego plastyczność jest nieistotna.
Szyfry blokowe zwykle mają wrodzoną właściwość przekształcania się w kompletny bełkot, gdy przerzucasz jeden bit (plus, przy łączeniu, cała pozostała część wiadomości) . To całkiem niezła, pożądana właściwość, którą po prostu wyrzuciliśmy za burtę bez powodu.
To bardzo, bardzo źle. Po pierwsze , Tryb CBC również cierpi z powodu pewnego rodzaju słabości plastyczności; jeśli odwrócisz jeden bit zaszyfrowanego tekstu, zaszyfrujesz tylko jeden blok i odwróć odpowiedni bit bloku sieci. Są też inne ataki plastyczności przeciwko CBC; zobacz na przykład atak EFail .
Mówiąc bardziej ogólnie, twój nieformalny pomysł, że wiadomości „zamieniają się w kompletny bełkot” nie jest wystarczająco dobry. Absolutnie potrzebujemy komputerów do mechanicznego wykrywania, z wyraźną odpowiedzią „tak / nie”, kiedy zaszyfrowana wiadomość została sfałszowana. Ufanie, że człowiek znajdzie się w pętli na tyle wcześnie, by dostrzec „bełkot”, nie jest wystarczające.
GHASH to MAC obsługujący dodatkowe uwierzytelnione dane. Z tego, co wiem, to jawne kłamstwo. Lub nazwij to „optymistyczną przesadą”, jeśli chcesz. Jest to po prostu funkcja kompresji z nieintuicyjną matematyką (dla nie-matematyków) w tyle, ale w końcu robi nic poza prostym mnożeniem i wyrzucaniem połowy bitów wejściowych odpowiednikiem „przepełnienia”.
MAC nie działa, ponieważ użytkownicy nie rozumieją matematyki. To tak, jakby powiedzieć, że ludzie nie mogą oglądać telewizji satelitarnej, ponieważ nie Nie znam rachunku różniczkowego. MAC z polami skończonymi są standardową konstrukcją, znaną od dziesięcioleci.
To właśnie, przy bardziej przyziemnej matematyce, można zrobić w dwóch wierszach C kod na blok w ciągu kilkunastu cykli (lub jeśli nie przeszkadza ci używanie 32-bitowych mnożeń zamiast 64, można to zrobić równolegle, np. z vpmulld AVX2 dla dwóch pełnych bloków w ~ 4 cyklach).
Trwa debata na temat tego, czy MAC oparte na polach Galois, takich jak GHASH, czy MAC oparte na polach głównych, takich jak Poly1305, są bardziej praktycznym wyborem. Wiele z nich zależy od kompromisów między projektowaniem MAC w celu podkreślenia implementacji oprogramowania i sprzętu; np. mnożenie pól Galois jest koszmarem w oprogramowaniu, ale znacznie prostsze niż mnożenie arytmetyczne w sprzęcie. Duża część kompromisów zależy również od podatności na ataki typu side-channel, np. analiza mocy .
Ale nie ma debaty, czy pola Galois lub pola pierwsze są zasadniczo nieistniejące nd. Matematyka sprawdza się na obu.
Hej, wydajność! Ale bądźmy szczerzy, czy to naprawdę zaleta, czy raczej ogromna wada?
Powiedz to niekończącym się paradom inżynierów przez dziesięciolecia, którzy oparli się dodaniu szyfrowania do produktów ze względu na wydajność. I nie myśl tylko o potężnych komputerach; myśl o urządzeniach wbudowanych i bardzo bój się Internetu rzeczy.
To znaczy, to wcale nie jest martwy problem. W ciągu ostatnich kilku lat toczyła się ożywiona debata i opracowanie nowej konstrukcji kryptograficznej do obsługi szyfrowania całego dysku na słabszych urządzeniach z Androidem, które zostały ocenione niewystarczająco wydajne dla algorytmów opartych na AES, które Android oferował wcześniej.
Jedynymi, dla których [wydajność] naprawdę robi różnicę, są „źli faceci”, tj. dokładnie ci, których nie chcesz mieć łatwe życie. Oczywiście, jeśli możesz trywialnie zrównoleglać, ataki staną się znacznie łatwiejsze. Zaplanuj problem pełen dedykowanego sprzętu (GPU, FPGA, cokolwiek) i pozwól mu się rozwikłać.
Szyfry rozwiązują ten problem, używając wystarczająco dużych rozmiarów kluczy, a nie spowolnienia szyfrów. Problem, który poruszasz, pojawia się w kryptografii opartej na hasłach , gdzie nie „Nie mają dostatecznie entropijnych tajnych kluczy. 256-bitowe klucze symetryczne będą zawsze więcej niż wystarczająco duże, aby pokonać każdy atak brutalnej siły w naszym wszechświecie.
Co to jest podstawowa rzecz, której mi brakuje w GCM, która czyni go tak niesamowitym, że absolutnie powinieneś go używać?
Absolutnie nie musisz używać GCM . Jest to jednocześnie:
- Fundamentall y dźwięk i bardzo szeroko obsługiwane w sprzęcie;
- Obarczony wieloma wadami, których nie poruszyłeś, takimi jak słaba wydajność oprogramowania i katastrofalny błąd autentyczności przy jednorazowym użyciu, które często dyskwalifikują go w niektórych praktycznych kontekstach .
Jeśli masz sprzęt, który ma natywną obsługę AES-GCM i dobrze sprawdzone oprogramowanie, które ją wykorzystuje, nierozsądnie byłoby nie mieć go wśród najlepszych kandydatów.