{"id":33517,"date":"2019-10-31T21:53:04","date_gmt":"2019-10-31T18:53:04","guid":{"rendered":"https:\/\/prohoster.info\/blog\/predstavlen-bolee-effektivnyj-metod-opredeleniya-prefiksov-kollizij-dlya-sha-1\/"},"modified":"2019-10-31T21:53:04","modified_gmt":"2019-10-31T18:53:04","slug":"predstavlen-bolee-effektivnyj-metod-opredeleniya-prefiksov-kollizij-dlya-sha-1","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sk\/blog\/news\/predstavlen-bolee-effektivnyj-metod-opredeleniya-prefiksov-kollizij-dlya-sha-1","title":{"rendered":"Bol predstaven\u00fd \u00fa\u010dinnej\u0161\u00ed sp\u00f4sob ur\u010dovania kol\u00edznych prefixov pre SHA-1","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

V\u00fdskumn\u00edci z franc\u00fazskeho \u0161t\u00e1tneho in\u0161tit\u00fatu pre v\u00fdskum v informatike a automatiz\u00e1cii (INRIA) a Nanyang Technological University (Singapur) vyvinuli<\/a><\/noindex> vylep\u0161en\u00fd met\u00f3da<\/a><\/noindex> \u00fatoky<\/a><\/noindex> algoritmus SHA-1, ktor\u00fd podstatne zjednodu\u0161uje vytv\u00e1ranie dvoch r\u00f4znych dokumentov s rovnak\u00fdmi hashmi SHA-1. Podstata met\u00f3dy spo\u010d\u00edva v zn\u00ed\u017een\u00ed oper\u00e1cie \u00fapln\u00e9ho h\u013eadania kol\u00edz\u00ed v SHA-1 na kol\u00edznu \u00fatok s ur\u010den\u00fdm prefixom<\/a><\/noindex>, pri ktorej kol\u00edzia nast\u00e1va pri pr\u00edtomnosti ur\u010dit\u00fdch prefixov, nez\u00e1visle od ostatn\u00fdch \u00fadajov v s\u00fabore. In\u00fdmi slovami, je mo\u017en\u00e9 vypo\u010d\u00edta\u0165 dva preddefinovan\u00e9 prefixy a ak jeden pripoj\u00edme k jedn\u00e9mu dokumentu, a druh\u00fd k druh\u00e9mu \u2014 v\u00fdsledn\u00e9 SHA-1 hash pre tieto s\u00fabory bud\u00fa rovnak\u00e9.<\/p>\n

Tento typ \u00fatoku st\u00e1le vy\u017eaduje obrovsk\u00e9 v\u00fdpo\u010dty a h\u013eadanie prefixov zost\u00e1va zlo\u017eitej\u0161ie ako be\u017en\u00e9 h\u013eadanie kol\u00edzi\u00ed, ale praktick\u00e1 \u00fa\u010dinnos\u0165 v\u00fdsledku je podstatne vy\u0161\u0161ia. Ak doteraz najr\u00fdchlej\u0161\u00ed sp\u00f4sob vyh\u013ead\u00e1vania prefixov kol\u00edzi\u00ed v SHA-1 vy\u017eadoval vykonanie 277,1 oper\u00e1ci\u00ed, nov\u00fd pr\u00edstup zni\u017euje po\u010det v\u00fdpo\u010dtov na rozsah od 266,9 do 269,4. Pri takejto \u00farovni v\u00fdpo\u010dtov sa odhadovan\u00e9 n\u00e1klady \u00fatoku pohybuj\u00fa pod sto tis\u00edc dol\u00e1rov, \u010do je celkom realista pre spravodajsk\u00e9 slu\u017eby a ve\u013ek\u00e9 korpor\u00e1cie. Pre porovnanie, na h\u013eadanie be\u017enej kol\u00edzie je potrebn\u00e9 vykona\u0165 pribli\u017ene 264,7 oper\u00e1ci\u00ed.<\/p>\n

V minul\u00fdch<\/a><\/noindex> demon\u0161tr\u00e1ci\u00ed<\/a><\/noindex> Google pri mo\u017enosti generovania r\u00f4znych PDF s\u00faborov s rovnak\u00fdm hashom SHA-1 bola pou\u017eit\u00e1<\/a><\/noindex> trik s kombinovan\u00edm dvoch dokumentov do jedn\u00e9ho s\u00faboru, prep\u00ednan\u00edm vidite\u013enej vrstvy a pos\u00favan\u00edm v\u00fdberu vrstvy na oblas\u0165 vzniku kol\u00edzie. Pri podobn\u00fdch n\u00e1kladoch na zdroje (na h\u013eadanie prvej kol\u00edzie SHA-1 Google str\u00e1vil rok v\u00fdpo\u010dtov na klastri z 110 GPU) nov\u00fd pr\u00edstup umo\u017e\u0148uje dosiahnu\u0165 zhodu SHA-1 pre dva \u013eubovo\u013en\u00e9 s\u00fabory \u00fadajov. Z praktick\u00e9ho h\u013eadiska je mo\u017en\u00e9 pripravi\u0165 TLS certifik\u00e1ty, v ktor\u00fdch sa uv\u00e1dzaj\u00fa r\u00f4zne dom\u00e9ny, ale zhoduj\u00fa sa hashe SHA-1. Tak\u00e1to mo\u017enos\u0165 umo\u017e\u0148uje nekal\u00e9mu certifika\u010dn\u00e9mu \u00faradu vytvori\u0165 certifik\u00e1t pre digit\u00e1lny podpis, ktor\u00fd m\u00f4\u017ee by\u0165 pou\u017eit\u00fd na autoriz\u00e1ciu falo\u0161n\u00fdch certifik\u00e1tov pre \u013eubovo\u013en\u00e9 dom\u00e9ny. Probl\u00e9m sa d\u00e1 takisto vyu\u017ei\u0165 na kompromit\u00e1ciu protokolov, ktor\u00e9 sa spoliehaj\u00fa na absenciu kol\u00edzi\u00ed, ako s\u00fa TLS, SSH a IPsec.<\/p>\n

Navrhnut\u00e1 strat\u00e9gia vyh\u013ead\u00e1vania prefixov pre kol\u00edzie predpoklad\u00e1 rozdelenie v\u00fdpo\u010dtov na dva kroky. V prvom kroku sa vykon\u00e1va vyh\u013ead\u00e1vanie blokov, ktor\u00e9 s\u00fa na pokraji kol\u00edzie, prostredn\u00edctvom vkladania n\u00e1hodn\u00fdch premenn\u00fdch re\u0165azcov do preddefinovanej cie\u013eovej sady rozdielov. V druhom kroku sa na \u00farovni jednotliv\u00fdch blokov z\u00edskan\u00e9 re\u0165azce rozdielov porovn\u00e1vaj\u00fa s kol\u00edznymi p\u00e1rmi stavov, pri\u010dom sa pou\u017e\u00edvaj\u00fa met\u00f3dy tradi\u010dn\u00fdch \u00fatokov zameran\u00fdch na vyh\u013ead\u00e1vanie kol\u00edzi\u00ed. <\/p>\n

Napriek tomu, \u017ee teoretick\u00e1 mo\u017enos\u0165 \u00fatoku na SHA-1 bola preuk\u00e1zan\u00e1 u\u017e v roku 2005, a v praxi bola prv\u00e1 kol\u00edzia n\u00e1jden\u00e1<\/a><\/noindex> v roku 2017, SHA-1 st\u00e1le ost\u00e1va v obehu a je zahrnut\u00fd v niektor\u00fdch \u0161tandardoch a technol\u00f3gi\u00e1ch (TLS 1.2, Git at\u010f.). Hlavn\u00fdm cie\u013eom vykonanej pr\u00e1ce bolo poskytn\u00fa\u0165 \u010fal\u0161\u00ed presved\u010div\u00fd argument na okam\u017eit\u00e9 ukon\u010denie pou\u017e\u00edvania SHA-1, najm\u00e4 v certifik\u00e1toch a digit\u00e1lnych podpisoch.<\/p>\n

Navy\u0161e m\u00f4\u017eeme spomen\u00fa\u0165 publik\u00e1ciu<\/a><\/noindex> v\u00fdsledkov<\/noindex> kryptoanal\u00fdzy blokov\u00fdch \u0161ifrov SIMON-32\/64<\/a><\/noindex>, vyvinut\u00fdch NSA USA a v roku 2018 schv\u00e1len\u00fdch ako \u0161tandard ISO\/IEC 29167-21:2018<\/a><\/noindex>.
\nVedcom sa podarilo vyvin\u00fa\u0165 met\u00f3du obnovy tajn\u00e9ho k\u013e\u00fa\u010da na z\u00e1klade dvoch zn\u00e1mych p\u00e1rov otvoren\u00e9ho textu a \u0161ifrov\u00e9ho textu. Pri obmedzen\u00fdch v\u00fdpo\u010dtov\u00fdch zdrojoch na obnovenie k\u013e\u00fa\u010da sa vy\u017eaduje nieko\u013eko hod\u00edn a\u017e nieko\u013eko dn\u00ed. Teoretick\u00fd \u00faspe\u0161n\u00fd koeficient \u00fatoku je odhadovan\u00fd na 0.25, zatia\u013e \u010do praktick\u00fd pre existuj\u00faci prototyp \u2014 0.025.<\/p>\n

<\/a><\/noindex><\/p>\n

Zdroj: opennet.ru<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u0438\u0437 \u0444\u0440\u0430\u043d\u0446\u0443\u0437\u0441\u043a\u043e\u0433\u043e \u0433\u043e\u0441\u0443\u0434\u0430\u0440\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u0438\u043d\u0441\u0442\u0438\u0442\u0443\u0442\u0430 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439 \u0432 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435 \u0438 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u043a\u0435 (INRIA) \u0438 \u041d\u0430\u043d\u044c\u044f\u043d\u0441\u043a\u043e\u0433\u043e \u0442\u0435\u0445\u043d\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 (\u0421\u0438\u043d\u0433\u0430\u043f\u0443\u0440) \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 \u0443\u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u0430\u0442\u0430\u043a\u0438 \u043d\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c SHA-1, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0443\u043f\u0440\u043e\u0449\u0430\u044e\u0449\u0438\u0439 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0434\u0432\u0443\u0445 \u0440\u0430\u0437\u043d\u044b\u0445 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438 \u0445\u044d\u0448\u0430\u043c\u0438 SHA-1. \u0421\u0443\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u0430 \u0432 \u0441\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u043b\u043d\u043e\u0446\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0434\u0431\u043e\u0440\u0430 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438 \u0432 SHA-1 \u043a \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u043e\u043d\u043d\u043e\u0439 \u0430\u0442\u0430\u043a\u0435 \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043e\u043c, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-33517","post","type-post","status-publish","format-standard","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Predstaven\u00e1 efekt\u00edvnej\u0161ia met\u00f3da ur\u010dovania prefixov kol\u00edzi\u00ed pre SHA-1 | ProHoster","description":"V\u00fdskumn\u00edci z franc\u00fazskeho \u0161t\u00e1tneho in\u0161tit\u00fatu pre v\u00fdskum v informatike a automatiz\u00e1cii (INRIA) a Nanyang Technological University (Singapur)","canonical_url":"https:\/\/prohoster.info\/sk\/blog\/news\/predstavlen-bolee-effektivnyj-metod-opredeleniya-prefiksov-kollizij-dlya-sha-1","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sk_SK","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043e\u0432 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439 \u0434\u043b\u044f SHA-1 | ProHoster","og:description":"\u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u0438\u0437 \u0444\u0440\u0430\u043d\u0446\u0443\u0437\u0441\u043a\u043e\u0433\u043e \u0433\u043e\u0441\u0443\u0434\u0430\u0440\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u0438\u043d\u0441\u0442\u0438\u0442\u0443\u0442\u0430 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439 \u0432 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435 \u0438 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u043a\u0435 (INRIA) \u0438 \u041d\u0430\u043d\u044c\u044f\u043d\u0441\u043a\u043e\u0433\u043e \u0442\u0435\u0445\u043d\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 (\u0421\u0438\u043d\u0433\u0430\u043f\u0443\u0440)","og:url":"https:\/\/prohoster.info\/sk\/blog\/news\/predstavlen-bolee-effektivnyj-metod-opredeleniya-prefiksov-kollizij-dlya-sha-1","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:53:04+00:00","article:modified_time":"2019-10-31T18:53:04+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"33517","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 15:37:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:39:23","updated":"2026-01-21 15:37:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/33517","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/comments?post=33517"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/33517\/revisions"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media?parent=33517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/categories?post=33517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/tags?post=33517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}