List do grupy dyskusyjnej SHA-3, który napisałem w 2010 roku: Od: Zooko O'Whielacronx Do: hash-forum Data: 2010-10-14 03:46 UTC Ludzie: Jeśli hasz ma 32-bitową odporność na preobraz, to oznacza, że atakujący może wydać około 2³² zasobów, aby znaleźć preobraz. Jeśli hasz ma 64-bitową odporność na preobraz, to oznacza, że atakujący może wydać około 2⁶⁴ zasobów, aby znaleźć preobraz. A co jeśli hasz ma 512-bitową odporność na preobraz? Co to by oznaczało? Że atakujący może wydać około 2⁵¹² zasobów, aby znaleźć preobraz w nim? To jest bezsensowna możliwość do omówienia, ponieważ 2⁵¹² zasobów nigdy nie będzie istniało w życiu tego wszechświata, więc nie może to oznaczać tego, a jeśli to oznacza, to nie ma sensu mówić o "512-bitowej odporności na preobraz". Może to oznacza coś innego? Na analogii, załóżmy, że rozważasz budowę mostu, który wytrzyma 10³ ton ciśnienia. Możesz również rozważyć most, który mógłby wytrzymać 10⁶ ton ciśnienia. Jeśli most miałby być użyty w sytuacji, w której na nim spoczywałoby więcej niż 10³ ton, ale mniej niż 10⁶ ton, to byłoby to bardzo ważne rozróżnienie do zrobienia. Ale co by to oznaczało, aby omówić projekt mostu, który mógłby wytrzymać 10¹⁵⁰ ton ciśnienia? Taka ilość ciśnienia nigdy nie mogłaby być zastosowana do mostu. Czy byłoby jakiekolwiek znaczenie w rozróżnieniu między jednym projektem mostu, który wytrzymałby 10¹⁵⁰ ton ciśnienia, a innym, który wytrzymałby 10³⁰⁰? Nawet jeśli żaden z nich nigdy nie mógłby doświadczyć takiej ilości jak 10¹⁵⁰ ton ciśnienia, być może ten drugi most byłby nadal bezpieczniejszy przed jakimś innym zagrożeniem — błędem ze strony budowniczych lub projektantów lub stresującym wydarzeniem, które nie zostało uwzględnione w modelu, którego użyliśmy do oceny naszych mostów w pierwszej kolejności. A może nie. Może most zaprojektowany do wytrzymania 10³⁰⁰ ton ciśnienia jest w rzeczywistości bardziej narażony na awarię niż ten drugi, gdy zostanie uderzony przez to nieprzewidziane, niemożliwe do modelowania zdarzenie. Kto może to powiedzieć? Jedna rozsądna pozycja, którą można zająć, to że to był błąd ze strony NIST, aby określić, że niektóre z haszy SHA-3 muszą mieć 512-bitową odporność na preobraz. (Jeśli to był błąd, to naprawdę nie mam pojęcia, co z tym zrobić w tej chwili!) Ta pozycja mówi, że istnieje potrzeba funkcji haszującej, która zajmuje znacznie więcej czasu CPU niż SHA-3-256, aby zapewnić znacznie mniejsze prawdopodobieństwo, że atakujący będzie w stanie znaleźć preobraz w niej niż w SHA-3-256, ale że to "znacznie mniejsze prawdopodobieństwo" nie jest w żadnym sensie znacząco skorelowane z ideą posiadania "512-bitowej odporności na preobraz". Inna rozsądna pozycja, którą można zająć, to że funkcja haszująca, która jest znana z maksymalnie 384-bitowej odporności na preobraz, jest bardziej narażona na awarię niż ta, która jest znana z maksymalnie 512-bitowej odporności na preobraz. Tutaj kończy się moje ograniczone zrozumienie analizy kryptograficznej funkcji haszujących. Czy to jest prawdopodobne? Jeśli dam ci dwie takie funkcje haszujące, czy jesteś pewien, że mógłbyś nauczyć się, jak znaleźć preobrazy w pierwszej, zanim znajdziesz preobrazy w drugiej? Jak bardzo jesteś pewien? Czy możliwe, że byłoby odwrotnie — że odkryłbyś metodę znajdowania preobrazów w drugiej, zanim odkryjesz metodę znajdowania preobrazów w pierwszej? Jeśli ktoś, kto ma prawdziwą wiedzę na temat analizy kryptograficznej funkcji haszujących i kto zajmuje stanowisko drugie, mógłby wyjaśnić, co ma na myśli mówiąc "bardziej narażona na awarię", to byłbym zafascynowany, aby to usłyszeć. W każdym razie, jestem prawie pewien, że jako użytkownik funkcji haszujących to, co mnie interesuje, to "bardziej narażona na awarię" (i wydajność), a nie "bity bezpieczeństwa" dla jakiegokolwiek poziomu bitowego większego niż około 128 (w tym uwzględnienie ataków kwantowych, ataków wielotargetowych itp.). Dziękuję za poświęcenie czasu na przeczytanie tego. Pozdrawiam, Zooko Wilcox-O'Hearn