## Kryptograficzne funkcje skrótu
Funkcja skrótu przyjmuje na wejściu wiadomość, a wynikiem jej działania jest stałej długości skrót, który jest niezależny od długości wiadomości. Oznacza to, iż na pewno istnieją wiadomości, które dadzą w wyniku tę samą wartość funkcji skrótu. Taką sytuację nazywamy *kolizją* i w zastosowaniach kryptograficznych jest ona wysoce niepożądana.
Nie każda funkcja może być kryptograficzną funkcją skrótu. Aby nią zostać, musi spełnić następujące warunki:
- jest problemem trudnym znalezienie dla danej wartości funkcji skrótu takiej wiadomości, która ją wytworzyła (ang. *preimage resistance*),
- jest problemem trudnym znalezienie wiadomości N dla danej M, dla których wartości funkcji skrótu będą takie same (ang. *second preimage resistance*),
- jest problemem trudnym znalezienie dwóch dowolnych wiadomości N i M, dla których wartości funkcji skrótu będą równe (ang. *collision resistance*).
Nie jest zatem funkcją skrótu *funkcja haszująca* używana w strukturach danych. Nie jest też nią *suma kontrolna* taka jak np. *cykliczny kod nadmiarowy* (ang. *cyclic redundancy check*, CRC). Są to funkcje łatwo odwracalne. Oznacza to, iż dla danej wartości funkcji skrótu łatwo znaleźć dowolną wiadomość dającą tę wartość. Łatwym problemem jest też znalezienie dwóch wiadomości, które dadzą ten sam *hasz*, czyli znalezienie kolizji. W kryptografii takie funkcje nie mają żadnego zastosowania. Dla kryptograficznych funkcji skrótu istnieje rozwiązanie powyższych problemów, ale jest ono trudne do znalezienia. *Trudne* to znaczy w praktyce nieużyteczne i niemożliwe przy w tej chwili dostępnych zasobach pamięci i czasu. Mało prawdopodobne jest, aby opłacało się atakującemu znalezienie kolizji po kilkudziesięciu latach.
## Algorytmy
Najbardziej znane funkcje skrótu tworzą dwie rodziny algorytmów: MD (ang. *Message Digest*) oraz SHA (ang. *Secure Hash Algorithm*). Przedstawiciele pierwszej z nich to np. algorytmy MD4 oraz MD5. Nie powinny być już one używane ponieważ znalezienie kolizji dla tych funkcji jest w tej chwili problemem łatwym. Do drugiej rodziny należą algorytmy opracowane przez Narodowy Instytut Standaryzacji i Technologii (ang. *National Institute of Standards and Technology*) zaprezentowane w standardzie [FIPS 180-4](http://dx.doi.org/10.6028/NIST.FIPS.180-4). Aktualnie zalecane jest używanie funkcji skrótu co najmniej SHA-256, która produkuje 256-cio bitową wartość skrótu. Funkcja SHA-1 powinna być wycofywana z użycia w istniejących systemach i nieużywana w nowych.
W Javie funkcje skrótu możemy obliczyć, używając fabryki `MessageDigest`. Nazwa funkcji skrótu przekazywana jest jako ciąg znaków. Znajdziemy je w dokumencie [Standard Algorithm Name Documentation](https://docs.oracle.com/javase/8/docs/technotes/guides/security/StandardNames.html).
Efektem działania poniższego programu będzie obliczenie wartości funkcji skrótu SHA-256 dla przykładowej wiadomości.
```java
import java.security.MessageDigest;
public class DigestTest {
public static void main(String[] args) throws Exception {
byte[] data = "abcdefghijklmnoprstuwxyz1234567890!".getBytes();
MessageDigest md = MessageDigest.getInstance("SHA-256");
byte sha256[] = md.digest(data);
}
}
```
Przygotowanie nowego algorytmu przez NIST trwa wiele lat i związane jest z jego szczegółową analizą. Kiedyś algorytmy opracowywali specjaliści zatrudnieni w NIST. w tej chwili ogłaszane są konkursy, między innymi dlatego by uniknąć podejrzeń o proponowanie takich algorytmów, które być może NIST już potrafi złamać w przeciwieństwie do reszty świata. Taką rywalizację o miano nowej funkcji skrótu ogłoszono w 2007 roku, a standard w postaci dokumentu [FIPS 202](https://dx.doi.org/10.6028/NIST.FIPS.202) przyjęto w sierpniu 2015 roku. Zwyciężył algorytm Keccak, który dołączył do rodziny SHA stając się funkcją SHA-3. Aktualnie w Javie możemy ją obliczyć, używając zewnętrznej biblioteki kryptograficznej np. [Bouncy Castle](https://www.bouncycastle.org/). Zaprezentowane jest to na poniższym przykładzie.
```java
import java.security.Security;
import java.security.MessageDigest;
import org.bouncycastle.jce.provider.BouncyCastleProvider;
public class DigestTest2 {
public static void main(String[] args) throws Exception {
byte[] data = "abcdefghijklmnoprstuwxyz1234567890!".getBytes();
Security.addProvider(new BouncyCastleProvider());
MessageDigest md = MessageDigest.getInstance("SHA3-256");
byte sha3[] = md.digest(data);
}
}
```
## Zastosowania praktyczne
Patrząc na adekwatności funkcji skrótu, można wskazać ich inne interesujące zastosowania poza samą usługą integralności. Odpowiednio użyte doskonale nadają się do bezpiecznego przechowywania haseł użytkowników w bazie danych. Zamiast hasła w jawnej postaci przechowujemy jego wartość funkcji skrótu. Dzięki temu atakujący, który wykradnie taką bazę, nie pozna haseł użytkowników. Pod jednym warunkiem: jeżeli zawczasu przygotuje sobie duży słownik zawierający tysiące haseł i odpowiadające im skróty to może przeprowadzić tzw. *atak słownikowy*, licząc na to, iż znajdzie skrót z wykradzionej bazy w swoim słowniku, a to pozwoli mu poznać hasło. Nie jest to atak pewny, ale często bardzo efektywny, ponieważ użytkownicy często stosują słabe hasła. Ataku tego można uniknąć, stosując *sól* (ang. *salt*), czyli doklejając losowy ciąg znaków do hasła użytkownika przed wyliczeniem skrótu. Sól przechowywana jest wraz ze skrótem hasła w formie jawnej. Dzięki niej przygotowane słowniki stają się bezużyteczne. Po co atakującemu znajomość haseł? Przecież włamał się już do atakowanego serwisu. Liczy jednak na to, iż użytkownicy stosują to samo hasło do innych serwisów, co jest częstą niebezpieczną praktyką. Włamując się w jedno miejsce, uzyska w ten sposób łatwy dostęp do innych.
Za pomocą funkcji skrótu można też zagrać bezpiecznie w rzut monetą przez sieć. Protokół taki nazywamy *protokołem zobowiązania bitowego*. Rzucający monetą musi potraktować swój wynik rzutu funkcją skrótu i przesłać jej wartość do odgadującego. Dzięki tej operacji nie będzie mógł go już zmienić, czyli oszukać odgadującego, ale odgadujący nie ma możliwości stwierdzenia, co zostało wyrzucone. Dopiero po nieudanej próbie odgadnięcia rzucający ujawnia jaka wiadomość wytworzyła przekazany skrót. Ten protokół należy również *właściwie zaimplementować*. W przeciwnym razie zgadujący z łatwością zastosuje atak słownikowy.
## Podsumowanie
Bez zapewnienia *integralności* nie ma sensu budowanie żadnego systemu informatycznego. Jednak ona sama nie ochroni nas przed atakiem polegającym na otrzymaniu *integralnej* informacji z nieznanego źródła. Atakujący może przecież przechwycić dane, zmienić je, przeliczyć wartość funkcji skrótu i wysłać do nas jeżeli przekazujemy te dane kanałami, do których uzyskał dostęp. Wiadomość będzie spójna, ale nie będzie to wiadomość wysłana przez nadawcę, od którego spodziewaliśmy się ją otrzymać. Ta dodatkowa usługa --- sprawdzenie, czy wiadomość pochodzi z oryginalnego źródła --- nie jest jednak celem *integralności*. W kolejnym wpisie ten problem zostanie rozwiązany poprzez dodanie *uwierzytelnienia* realizowanego dzięki kodu uwierzytelniającego wiadomość (ang. *message authentication code*, MAC).
