NIST ogłosił listę czternastu algorytmów funkcji skrótu, które zostały zakwalifikowane do drugiej rundy konkursu SHA-3. Są to algorytmy BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD i Skein.

http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

W opublikowanej niedawno pracy zespół w składzie Cameron McDonald, Philip Hawkes i Józef Pieprzyk poinformował o opracowaniu metody znajdowania kolizji dla funkcji skrótu SHA-1 o złożoności 2^52.

W udostępnionej prezentacji nie ma szczegółów technicznych (zapowiedziano rychłą publikację na Eprincie). Dotychczas najlepsza znana metoda umożliwiała znajdowanie kolizji przy złożoności 2^63, jest to więc znaczący postęp w kierunku osłabienia funkcji SHA-1.

Należy pamiętać, że możliwość znalezienia kolizji funkcji SHA-1 nie oznacza jeszcze zagrożenia np. dla podpisu elektronicznego, w którego przypadku konieczny jest skuteczny atak typu pre-image.

http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf

http://ipsec.pl/kryptografia/2009/aktualny-poziom-bezpieczenstwa-kryptog…

Opublikowany w ubiegłym miesiącu dokument NIST SP 800-107 zawiera, poza głównym tematem jakim jest randomizowany skrót na potrzeby podpisu cyfrowego, także interesującą analizę aktualnego stanu bezpieczeństwa kryptograficznych funkcji skrótu.

Pod uwage brana jest funkcja SHA1 oraz funkcje z serii SHA-2 czyli SHA-224, SHA-256, SHA-384 i SHA-512. Ich praktyczna odporność na ataki dotykające funkcji haszujących jest przedstawiona w poniższe tabeli zaczerpniętej z SP 800-107. Wszystkie odporności są mierzone w bitach:

Dla SHA-1 podana jest wartość <80 czyli “mniej niż 80″. Jest to o tyle istotne, że wartość 80 bitów to dolna granica złożoności obliczeniowej (odporności), jaką posługuje się NIST w stosunku do podstawowych algorytmów kryptograficznych. Aktualny szacunek dla SHA-1 według SP 800-107 to 60 bitów, czyli grubo poniżej granicy 80 bitów.

Podane wartości mają istotne znaczenie dla wyboru funkcji skrótu w różnych zastosowaniach. Na przykład większość dostępnych w Internecie serwerów SSL (banków, sklepów internetowych) negocjuje domyślnie SSL z funkcją skrótu MD5 i nie wywołuje to specjalnej sensacji, ze względu na krótkotrwały charakter tych połączeń.

Drugie zastosowanie funkcji skrótu w protokole SSL czyli ochrona autentyczności stron za pomocą certyfikatów X.509 wymaga długotrwałej odporności na wymienione ataki - i tutaj obecność MD5 w certyfikatach znanego CA wywołała niedawno umożliwiła ich podrobienie.

Zgodnie z zaleceniami NIST opisanymi we wspomnianej publikacji SP 800-107 oraz - szerzej - w 800-57 funkcja MD5 nie powinna być używana w zastosowaniach związanych z podpisem cyfrowym już od 1999 roku.

W stosunku do SHA-1 taką rekomendację wyznaczono na rok 2010. A ściślej, wyznaczono ją dla wszystkich algorytmów posługując się kryterium zapewnianej odporności mierzonej w bitach. I tak:

• do 2010 roku powinny być używane algorytmy zapewniające minimum 80 bitów - nie powinny być stosowane klucze RSA i DSA krótsze niż 1024 bity,
• w latach 2011-2030 powiny być używane algorytmy zapewniające min. 112 bitów - wycofany powinien zostać 3DES z dwoma kluczami (2TDEA), minimalna długość kluczy RSA i DSA to 2048 bitów,
• po roku 2030 powinny być używane algorytmy zapewniające min. 128 bitów - wycofany powinien być każdy warian 3DES, minimalne długości kluczy RSA i DSA to 3072 bity

Zgodnie z zaleceniami SP 800-57 po aktualizacji w 2008 roku SHA-1 jako zapewniające odporność mniejszą niż 80 bitów nie powinno być stosowane w noywych implementacjach.

• NIST Special Publication 800-107: Recommendation for Applications Using Approved Hash Algorithms, February 2009
• NIST Special Publication 800-57: Recommendation for Key Management - Part 3: Application Specific Key-Management Guide, August 2008 (DRAFT)
• NIST Special Publication 800-57: Recommendation for Key Management – Part 1: General (Revised), March 2007

Zespół Aleksandra Sotirowa z politechniki w Eindhoven zademonstrował podrobiony certyfikat jednego z publicznych centrów certyfikacji. Fałszerstwo było możliwe dzięki wygenerowaniu kolizji w funkcji skrótu MD5, której używało zaatakowane centrum certyfikacji.

Badacze pobrali oryginalny certyfikat centrum certyfikacji, które jako jedno z niewielu nadal stosuje funkcje MD5. Następnie wygenerowali takie wartości fałszywego certyfikatu, które dawały identyczny skrót MD5 jak w certyfikacie podrabianym. Ponieważ podrabiany certyfikat był certyfikatem pośredniego, więc następnie skopiowali podpis roota do fałszywego certyfikatu. Dzięki zgodności skrótów przeglądarki weryfikowały go poprawnie.

Przeprowadzony atak jest wyłącznie atakiem na przestarzałą funkcję skrótu nadal stosowaną przez jedno z centrów certyfikacji (RapidSSL, własność VeriSign) pomimo, że od dawna wiadomo o jej słabościach. Do wygenerowania kolizji użyty został klaster dwustu komputerów Playstation 3S.

Niemal wszystkie centra certyfikacji stosują obecnie funkcję SHA1, która co najmniej przez kilka kolejnych lat powinna być odporna na kolizje typu preimage. W nadchodzących latach należy oczekiwać stopniowego przechodzenia na funkcje z rodziny SHA2, a następnie SHA3.

Z kryptograficznego punktu widzenia badacze przeprowadzili skuteczny atak preimage, generując kolizję dla już istniejącej wiadomości (certyfikaty). W 2005 roku zespół Arjena Lenstry z tej samej uczelni zaprezentował fałszywe certyfikaty stworzone dzięki znalezieniu zwykłej kolizji MD5.

• Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger “MD5 considered harmful today”, 2008
• Steve M. Bellovin “Companies, Courts, and Computer Security”, 2008
• Kevin Poulsen “Researchers Use PlayStation Cluster to Forge a Web Skeleton Key”, Wired 2008
• Arjen Lenstra, Xiaoyun Wang, Benne de Weger “Colliding X.509 Certificates based on MD5-collisions”, 2006
• RFC 4270 “Attacks on Cryptographic Hashes in Internet Protocols”, 2005

W piątek 31 października upłynął termin zgłaszania kandydatów do ogłoszonego przez NIST konkursu na nowy standard funkcji skrótu o roboczej nazwie SHA-3. Do konkusu spłynęło ponoć prawie 30 propozycji od zespołów z całego świata.

Konkurs SHA-3 ma być podobny do procesu, w jakim wyłoniono standard AES - tam zwycięzcą został holenderski Rijndael. Celem konkursu SHA-3 jest wyłonienie funkcji skrótu na najbliższe dekady. Jego główną motywacją są potencjalne ataki kryptoanalityczne na dotychczasowy standard SHA-1. W odpowiedzi na nie NIST stworzył rodzinę skrótów SHA-2, których architektura jest jednak bardzo podobna do SHA-1.

Według NIST nie ma podstaw do twierdzenia, że funkcje SHA-2 mogą być w nadchodzących latach podatne na ataki, ale fakt że od bezpieczeństwa funkcji skrótu zależy długoterminowe bezpieczeństwo np. podpisu elektronicznego jest wystarczającym powodem by w perspektywie kilku lat zastąpić SHA-2 nowym standardem wyłonionym na drodze publicznego konkursu.

• Więcej informacji o konkursie na stronie NIST - Cryptographic Hash Algorithm Competition

Nazwy większości zgłoszonych algorytmów można znaleźć na stronie SHA-3 Zoo. W miarę publikacji zgłoszonych algorytmów przez NIST lub przez autorów wyniki testów wydajnościowych będą prezentowane w serwisie eBATS. Obecnie na stronie SHA-3 Zoo wymienione są następujące algorytmy:

1. BLAKE - autorzy Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
2. Blue Midnight Wish - autorzy Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes
3. Boole - autor Greg Rose
4. CubeHash - autor Dan Bernstein
5. Edon-R - autorzy Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal
6. EnRUPT - autorzy Sean O’Neil, Karsten Nohl, Luca Henzen
7. ESSENCE - autor Jason Worth Martin
8. Groestl - autorzy Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
9. Kecak - autorzy Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche
10. Maraca - autor Robert J. Jenkins Jr.
11. MCSSHA-3 - autor Mikhail Maslennikov
12. MD6 - autorzy Ron Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Drew Sutherland, Eran Tromer, Yiqun Lisa Yin
13. NaSHA - autorzy Smile Markovski, Aleksandra Mileva
14. NKS2D - autor Geoffrey Park
15. Ponic - autor Peter Schmidt-Nielsen
16. Sgàil - autor Peter Maxwell
17. Skein - autorzy Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
18. WaMM - autor John Washburn

Amerykański instytut standardów (NIST) otworzył projekt nowej rodziny funkcji haszujących SHA-3.

czytaj dalej