Nope na AWS naozaj bezala faktorizacia testovacich klucov. Urobili sme vykonnostny benchmark na adekvatnej velkosti problemu na instancii c4.large. Intel® Xeon® CPU E5-2666 v3 @ 2.90GHz, 2 thread cores. (Faktorizacia inak bezala aj na https://www.metacentrum.cz/en/ (ack v Usenix clanku).
Samozrejme vypoctovy vykon sa da zohnat aj lacnejsie ale AWS sa casto pouziva ako referencny benchmark. Druhotny dovod je aj nas ciel moznost faktorizovat kluc za mesiac, na co nemusi mat kazdy (aj ked lacnejsi) cloud provider dostatok vypocetneho vykonu - napr. forpsi.cz ma celkom vykonne servery za 30 CZK na mesiac. Tam je cena ovela nizsia, ale otazna je udrzatelnost takeho vypoctu.
Vsetky matematicke detaily budu dostupne az po 2.11.2017 ked prebehne nas talk na CCS 2017. Ale v skratke z uz publikovanych informacii:
Matematicky je problem trivialne paralelizovatelny v priestore jedneho parametra. Pre kazdu hodnotu tohoto parametra trva vypocet rovnako dlho co sme aj experimentalne overili na random 512b kluci (komplet faktorizovany). Preto nam na test staci zobrat statisticky vyznamnu cast intervalu a extrapolovat casovy odhad pre cely prehladavany interval.
2k RSA kluc faktorizovany bol, ale vyrobili sme synteticky taky, ktory ma prehladavany parameter “blizko”, teda v ramci kratkeho prehladavaneho intervalu (dlzka vypoctu cca den). To zaruci dobru extrapolaciu. Faktorizacia random 2k kluca je teda mrhanie vypocetnym vykonom. Principialny rozdiel v utoku na 512b a 2048b kluce nie je.
Matematicka spravnost bola potvrdena aj Infineonom a clanok presiel preciznym recenznym konanim na spickovej bezpecnostnej konferencii. Myslim, ze to su dostatocne indikatory na to, ze 2k faktorizacia funguje.
UPDATE:
Prebehol test, kde sa na Infineon karte vygenerovalo 137 000 2k RSA klucov. Kedze sme mali k nim aj privatne kluce mohli sme ich usporiadat podla zlozitosti a realne faktorizovat verejne casti 24 2k RSA klucov, ktore isli priamo z karty za rozumny cas (tyzden). Prehladavane parametre mali blizko. Prebehla teda aj faktorizacia 2k RSA z infineon cipu.
Ako niekto uz spravne poznamenal cena je len odhad. Povazoval by som $40k za hornu hranicu ceny. Ak budem mat stastie na kluc, moze to stat aj $0.1 (ak bude jeho parameter blizko).
Rovnako treba zobrat do uvahy, ze utocnik uz moze mat dostupny hardware a plati povedzme len energiu. Ak by niketo postavil rig z tychto https://ark.intel.com/products/95828/Intel-Xeon-Phi-Processor-7230F-16GB-1_30-GHz-64-core mohol by potom jeden kluc lamat priblizne za $1000 pri cene energii $0.2 za kWh.
Taktiez sa neda vylucit vylepsienie utoku a aj scenar, ked mam klucov viac.
EDIT 2:
Pravdepodobnost, ze nespravne identifikujeme konkretny bezpecny kluc ako nebezpecny (false-positive detection) je nizsia ako 2^{-128}, teda prakticky vylucena - to uz je pravdepodobnejsie, ze uhadneme AES-128 sifrovaci kluc.