Crypto-IT

Kod uwierzytelniania wiadomości (nazywany zwykle MAC, od angielskiego oryginału) to nieduży blok danych, który jest używany w celu uwierzytelnienia przesyłanej wiadomości. Odbiorca może sprawdzić za jego pomocą czy wiadomość nie została zmodyfikowana przez osoby trzecie.

Za pomocą skrótu MAC oznacza się również algorytmy używane w celu tworzenia bloku zawierającego kod uwierzytelnienia oraz jego późniejszego weryfikowania.

Najprostszym sposobem oznaczenia autentyczności wiadomości jest wyliczenie jej sumy kontrolnej, na przykład za pomocą algorytmu CRC, a następnie dołączenie wyniku na końcu przesyłanej wiadomości.

Podstawową wadą tej metody jest brak zabezpieczenia przed celowymi modyfikacjami w treści wiadomości. Napastnik może zmienić zawartość wiadomości, a następnie wyliczyć nową sumę kontrolną i wstawić ją na miejsce oryginalnej. Algorytmy CRC umożliwiają jedynie wykrycie losowych uszkodzeń wiadomości, nie przeprowadzonych celowo przez ewentualnego napastnika.

Kolejne akapity zaprezentują algorytmy MAC, które uniemożliwiają napastnikowi podrobienie kodów uwierzytelniających.

Na bazie kryptograficznie bezpiecznej funkcji pseudolosowej (PRF) można skonstruować kryptograficznie bezpieczny MAC.

Przykładowo, aby zabezpieczyć 16-bajtową wiadomość można użyć algorytmu szyfrującego AES lub dowolnego innego podobnego szyfru symetrycznego operującego na 16-bajtowych blokach danych.

Poniżej zaprezentowano algorytmy MAC, które umożliwiają zabezpieczenie dłuższych wiadomości.

Algorytm CBC MAC jest zbudowany na bazie funkcji pseudolosowej (dla wygody nazwanej F). Jego działanie jest oparte na tej samej idei co szyfrowanie symetryczne przeprowadzane w trybie CBC, z tą różnicą, że nie zwraca się kolejno otrzymywanych pośrednich wartości. Ponadto, po zaszyfrowaniu ostatniego bloku wiadomości wykonywane jest dodatkowe szyfrowanie aktualnego rezultatu przy użyciu drugiego sekretnego klucza.

Końcowe szyfrowanie ma na celu zapewnienie bezpieczeństwa wyliczonego kodu. Cały proces, włącznie z ostatnim dodatkowym krokiem, nosi nazwę ECBC MAC (od ang. encrypted), w odróżnieniu od części algorytmu bez ostatniego szyfrowania nazywanej raw CBC MAC.

W przypadku nie zastosowania ostatniego kroku algorytmu (czyli bez szyfrowania za pomocą drugiego klucza), napastnik mógłby zaatakować zabezpieczenia CBC MAC za pomocą ataku z wybranym tekstem jawnym:

1. Napastnik wybiera wiadomość m o długości jednego bloku.
2. Następnie napastnik uzyskuje od atakowanego systemu wartość kodu uwierzytelniającego dla tej wiadomości: t = F(k, m).
3. Atakujący może w tym momencie określić wartość kodu uwierzytelniającego dla wiadomości m₁ o długości dwóch bloków m₁ = (m, t XOR m):
   rawCBC(k, m₁)  = rawCBC(k, (m, t XOR m))  =  F(k, F(k, m) XOR (t XOR m))  =  F(k, t XOR (t XOR m))  =  t

CBC MAC może zabezpieczać wiadomości o dowolnej długości, od jednego do bardzo wielu bloków. Jego stosowanie jest kryptograficznie bezpieczne, o ile po zaszyfrowaniu pewnej ilości wiadomości zmienia się używany sekretny klucz. Można wykazać, że klucz przestaje być bezpieczny po liczbie wiadomości równej w przybliżeniu pierwiastkowi z liczby wszystkich możliwych wartości bloków danych.

Jeżeli ostatni blok przekazywanej wiadomości nie jest zapełniony całkowicie bitami wiadomości, należy dopełnić go pewnymi znakami, ustalonymi przez komunikujące się strony. Zwykle blok dopełnia się bitami, które jednoznacznie wskazują kiedy kończy się oryginalna wiadomość i uniemożliwiają wykorzystanie ewentualnej niejednoznaczności przez napastnika. Przykładem takiego ciągu może być jedynka, a następnie same zera aż do końca bloku (10000...). Jeśli ostatni blok zapełniony jest w takim stopniu, że nie mieści się w nim jedynka z przynajmniej jednym zerem, należy dołączyć kolejny blok i wypełnić go w całości dopełnianymi znakami.

Dla porównania, użycie samych zer wprowadzałoby niejasność gdzie kończy się transmitowana wiadomość, która może sama posiadać zera jako swoje ostatnie bity danych. Dodatkowo, wiele wiadomości o treściach różniących się jedynie ilością końcowych zer, mogłoby mieć takie same kody uwierzytelniające, co byłoby złamaniem reguł bezpieczeństwa kodowania wiadomości.

CBC MAC jest wykorzystywany w różnych aplikacjach, na przykład w systemach bankowych (standardy ANSI X9.9, X9.19, FIPS 186-3). Często jego sercem jest algorytm szyfrujący AES, którego używa się jako funkcji F.

Algorytm NMAC (od ang. nested) jest podobny do opisanego wcześniej CBC MAC. Wykorzystuje nieco inaczej zbudowaną funkcję pseudolosową F, która w tym przypadku zwraca wartości będące poprawnymi elementami zbioru wszystkich możliwych kluczy, a nie elementami zbioru wszystkich możliwych wartości bloku wiadomości.

Podobnie jak w przypadku CBC MAC, po zaszyfrowaniu ostatniego bloku wiadomości, wykonywane jest dodatkowe szyfrowanie otrzymanego wyniku przy użyciu drugiego sekretnego klucza szyfrującego. Ponieważ wynikiem szyfrowania ostatniego bloku za pomocą funkcji F jest ciąg danych o długości klucza szyfrującego, należy go uzupełnić za pomocą pewnego stałego ciągu (ang. fix pad) do długości bloków wiadomości. NMAC jest zwykle wykorzystywany w systemach, gdzie długość bloku danych jest dużo większa od długości sekretnego klucza szyfrującego.

Ostatnie szyfrowanie ma na celu zapewnienie bezpieczeństwa wyliczonego kodu wiadomości, podobnie jak w przypadku CBC MAC. Proces szyfrowania kolejnych bloków bez ostatniego kroku algorytmu NMAC nosi angielską nawę cascade.

Bez ostatniego kroku algorytmu (czyli bez szyfrowania za pomocą drugiego klucza), napastnik mógłby dołączyć do przechwyconej wiadomości z poprawnie wyliczonym kodem uwierzytelniającym, dowolną liczbę dodatkowych bloków tekstu i samodzielnie wyliczyć nowy kod. Wejściem do pierwszej nowo dodanej funkcji F byłby końcowy kod uwierzytelniający oryginalnej wiadomości.

Stosowanie NMAC jest kryptograficznie bezpieczne, o ile po zaszyfrowaniu pewnej ilości wiadomości zmienia się używany sekretny klucz. Można wykazać, że klucz przestaje być bezpieczny po liczbie wiadomości równej w przybliżeniu pierwiastkowi z liczby wszystkich możliwych wartości kluczy szyfrujących.

Algorytm NMAC obowiązują takie same reguły dotyczące dopełniania ostatnich bloków przekazywanych wiadomości, jakie mają zastosowanie do CBC MAC.

Algorytm CMAC jest odmianą opisanego wcześniej CBC MAC. Wykorzystuje tak samo zbudowaną funkcję pseudolosową F, która zwraca wartości będącymi poprawnymi elementami zbioru wszystkich możliwych bloków danych.

Zamiast ostatniego, dodatkowego szyfrowania za pomocą drugiego klucza, w CMAC wykorzystuje się dwa dodatkowe klucze, które dodaje się do danych wejściowych do ostatniego bloku funkcji F. W zależności od tego czy ostatni blok wiadomości jest w całości zapełniony bitami danych, czy też należy go dopełnić ustalonym ciągiem znaków, używa się odpowiedniego z dwóch dodatkowych kluczy szyfrujących.

Dodanie dodatkowego klucza szyfrującego w ostatnim kroku szyfrowania uniemożliwia ewentualnemu napastnikowi dołączenie dalszych bloków zmodyfikowanej wiadomości i zwalnia z konieczności stosowania dodatkowego kroku kodowania za pomocą funkcji F. Dzięki takiemu rozwiązaniu nie ma również potrzeby dodawać kolejnego bloku, aby zmieścić wcześniej ustalone bajty dopełnienia. Wystarczające będzie użycie właściwego dodatkowego klucza.

CMAC jest uznawany za bezpieczny sposób uwierzytelniania wiadomości. Posiada certyfikaty m. in. amerykańskiego instytutu NIST.

Algorytm PMAC (od ang. parallel) może być wykonywany z użyciem wielu wątków równocześnie, w przeciwieństwie do opisanych wyżej algorytmów sekwencyjnych, w których wszystkie bloki wiadomości musiały być przetwarzane jeden po drugim.

PMAC wykorzystuje w swoim działaniu dwa sekretne klucze szyfrujące. Pierwszy z nich używany jest w funkcji P, która na wejściu przyjmuje dodatkowo jeszcze zwiększające się wartości licznika. Wyjście z funkcji P dodawane jest XOR do bloku danych, a wynik szyfrowany jest przez funkcję pseudolosową F, używającą drugiego sekretnego klucza. Funkcja P jest z założenia nieskomplikowana i działa znacznie szybciej od funkcji F.

Wyjścia ze wszystkich funkcji F oraz dane z ostatniego bloku danych (który wyjątkowo nie jest szyfrowany przez funkcję F) są sumowane XOR, a na końcu szyfrowane również za pomocą algorytmu funkcji F, z drugim sekretnym kluczem szyfrującym.

As usual, it can be proved that PMAC is secure, if the secret key is changed from time to time. A new key should be created after sending the number of messages that is equal roughly to the square of the number of all possible values of data blocks.

PMAC allows to update authentication codes easily and quickly, in a case when one of the message block was replaced by a new one. For example, if a block m[x] is replaced by m'[x], then the following calculations should be performed:
    tag'  =  F(k₂, (F^-1(k₂, tag) XOR F(k₂, m[x] XOR P(k₁, x)) XOR F(k₂, m'[x] XOR P(k₁, x)))

Analogicznie do szyfrowania jednorazowego, można zdefiniować jednorazowy MAC, który zapewnia bezpieczeństwo przeciwko potencjalnym atakom i jest generalnie szybszy od algorytmów uwierzytelniania wiadomości bazujących na funkcjach PFR.

Można wykazać, że dwie wiadomości oznakowane za pomocą tych samych kluczy szyfrujących są nierozróżnialne dla potencjalnego obserwatora.

Działanie Carter-Wegman MAC oparte jest na idei jednorazowego MAC (ang. one-time MAC), rozszerzonego o funkcję pseudolosową w celu umożliwienia wielokrotnego zastosowania tych samych sekretnych kluczy dla kolejnych wiadomości.

HMAC jest popularnym systemem uwierzytelniania wiadomości zbudowanym w podobny sposób do NMAC.

Algorytm HMAC opiera się na wykorzystaniu jednokierunkowych funkcji skrótu (czyli funkcji haszujących).

Wartości ipad oraz opad mogą przyjmować różne wartości. Jest zalecane używanie takich wartości, aby klucz szyfrujący został zmodyfikowany w maksymalnie różny sposób w obu miejscach, w których jest wykorzystywany jako wejście do funkcji haszujących.

Zastosowanie bezpiecznej funkcji haszującej (czyli takiej, której działanie nie powoduje kolizji, to znaczy nie wylicza takich samych wartości dla różnych danych wejściowych) gwarantuje bezpieczeństwo HMAC.

HMAC jest wykorzystywany w wielu systemach, między innymi w popularnych protokołach internetowych (SSL, IPsec, SSH).