"Alicjo, czy to naprawdę Ty?" , albo o podpisach cyfrowych.

29.11.2009 - Agata Murawska
TrudnośćTrudność

Jak to poprawić?

Funkcja hashująca to funkcja, która napisowi dowolnej długości przyporządkowuje pewną krótką wartość, zwaną często hashem lub skrótem. Chcemy przy tym, żeby podobne napisy miały bardzo różniące się hashe, oraz żeby na podstawie skrótu nie dało się odtworzyć napisu, który ten skrót wygenerował.
Ta ostatnia własność to właśnie jednokierunkowość funkcji hashującej.
Okazuje się, że można poprawić pomysł podpisywania kluczem prywatnym tak, żeby podpis był krótszy, niż wiadomość, ale nadal miał wymagane przez nas własności. Pomocą służą jednokierunkowe funkcje hashujące. Nazwa może się wydawać magiczna, ale kryje za sobą dość prostą ideę.

Zamiast szyfrować kluczem prywatnym całą wiadomość, Alicja może teraz użyć ustalonej funkcji hashującej, tworząc skrót wiadomości, a następnie go podpisać.

hash

Bob wie, jakiej funkcji skrótu używała Alicja (na przykład cała szkoła używa tej samej funkcji z rodziny SHA-2), może więc stworzyć skrót otrzymanej wiadomości M, odszyfrować (krótki!) podpis przy użyciu klucza publicznego Alicji i porównać te dwa ciągi.

Wyeliminowaliśmy wady poprzedniego rozwiązania, pozostaje więc zastanowić się, jakim kosztem się to odbyło. Czy używanie hashy niesie ze sobą dodatkowe zagrożenia lub niedogodności?

Dlaczego tego typu atak nazywany jest "atakiem urodzinowym"?
Jego idea jest podobna do pewnego zadania z rachunku prawdopodobieństwa:
Ile minimalnie osób należy wybrać, żeby prawdopodobieństwo, że dwie z nich urodziły się tego samego dnia, było większe, niż 50%?

Okazuje się, że wynik jest mały w porównaniu z naszym pierwszym wyobrażeniem - wystarczą bowiem 23 osoby.

W naszym przykładzie datą urodzenia jest funkcja skrótu, zaś różne wersje umów to osoby.
Niestety tak, przynajmniej, jeśli nasza funkcja skrótu nie była dość długa. Można wtedy zastosować tak zwany "atak urodzinowy".

Wyobraźmy sobie, że Anna i Bill negocjują treść umowy. W jej ostatecznej wersji ustalili, że Anna zapłaci Billowi 1000 zł. Bill przygotowuje dwie wersje umowy - prawdziwą i korzystniejszą dla niego (na przykład mówiącą, że dostanie on 100000 zł), po czym modyfikuje nieznacznie obie wersje w wielu miejscach na różne sposoby, dla każdej pary umów obliczając funkcję hashującą.
Jego celem jest oczywiście znalezienie takich wersji umów, które mają ten sam skrót.
Jeśli mu się uda - przedstawia Annie wynegocjowaną umowę, którą ona podpisuje. Uzyskuje tym samym podpis dla pewnego skrótu tej umowy - podpis zależy tylko od wartości skrótu, zatem jest taki sam dla obu umów.
Anna nie jest w stanie udowodnić, że nie podpisała niekorzystnej umowy.

Na szczęście, jeśli używana przez nas funkcja jest długa, to znaczy skróty mają ponad 160 bitów, taki atak jest trudny do przeprowadzenia ze względu na ilość kombinacji.

4
Twoja ocena: Brak Ocena: 4 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com