Counter-Strike: Threshold Attack

Napigilan ang potensyal na pag-atake sa threshold ECDSA, panalo ang mga kontra-terorista!

Pagtanggi

Ang code na tinalakay sa tala na ito ay isang isinasagawa sa oras ng pagsulat at hindi pa nai-audit. Mangyaring laging mag-ingat kapag gumagamit ng hindi na-edit na code.

Panimula

Ang mga threshold wallet ay gumagamit ng threshold signature schemes (TSS) upang ipamahagi ang mga karapatan sa pag-sign sa maraming partido kapag naglalabas ng mga transaksyon sa blockchain. Kadalasang nakikita sila bilang isang paraan upang matanggal ang pandaraya ng tagaloob at pagbutihin ang mga garantiya sa seguridad sa isang desentralisadong setting.

Bagaman hindi bago ang konsepto ng TSS, ito ang kauna-unahang pagkakataon na malawakan itong ginagamit sa pagsasanay ng Binance, Thorchain, RenVM, at iba pa.

Ang nasabing pagiging popular na boom ay nag-uudyok sa akademya na mag-imbento ng mas mahusay na TSS, kaya’t hindi dapat sorpresa na maraming pananaliksik ang nagaganap sa larangan kamakailan: tingnan ang Lin17, GG18, CCLST19, GG20. Ang huli ay itinuturing na pinakamahusay na multi-party na ECDSA TSS dahil sa threshold- at round-optimality na ito, pati na rin ang pagkakaroon ng mga makikilalang abort.

Sa teorya, ang lahat ng nasa itaas ng TSS ay ligtas sa ilalim ng praktikal na mga pagpapalagay, tulad ng napatunayan sa mga kaukulang papel. Gayunpaman, sa pagsasagawa, ang mga tukoy na pagpapatupad ay maaaring magdusa mula sa mga kahinaan na ipinakilala ng software ng TSS.

Ang pinakatanyag na kilalang pagpapatupad ng Rust ng GG20 ay ang mga pinuno ng industriya na ZenGo-X. Sa katunayan, napakahusay na ginamit namin ito bilang isang panimulang punto para sa aming solusyon na nakabatay sa TSS. Gayunpaman, pagkatapos basahin ang papel na ito, na iminungkahi sa amin ni Omer Shlomovits, nakakita kami ng isang banayad na isyu sa kanilang code. Inaakay kami nito sa isang kritikal na atake na inilarawan sa tala na ito.

Bilang tunay na desentralisadong mahilig sa seguridad, mabilis kaming nakipag-ugnay sa ZenGo at naayos ang natuklasan na paglabag sa seguridad sa isang kahilingan sa paghila. Hindi nagtagal ay naaprubahan ito at isinama sa kanilang aklatan ng TSS. Ang mananaliksik na nakakita ng pag-atake ay binigyan ng isang kapagbigayan ng bug, ang pinakamalaki sa kasaysayan ng ZenGo.

Background

Sa natitirang tala na ito, gagamit kami ng notasyon mula sa GG18. Nagpapahiwatig din kami ng isang cyclic subgroup na nabuo ng isang elemento g bilang ⟨g⟩, at ang pagkakasunud-sunod nito bilang |g|.

Una, sa panahon ng ipinamahaging pangunahing henerasyon, ang bawat partido ay bumubuo ng mga halagang h₁, h₂, N, at nagpapatunay sa zero-knowledge na

magkakahiwalay na mga log ng h₁ at h₂ na may paggalang sa bawat isa modulo N na umiiral (ibig sabihin, ang h₁ at h₂ ay bumubuo ng parehong subgroup: ⟨h₁⟩ = ⟨h₂⟩).

Ang mga halagang ito ay ginamit din ng ibang mga partido sa panahon ng pag-sign upang makalkula ang z = h₁ᵏ h₂ʳ (mod N), kung saan ang k ang kanilang lihim na halaga, at ang r ay isang random na halagang ginamit upang “itago” k.

Tandaan na ang k ay direktang naka-link sa bahagi ng lihim na key sk, nangangahulugang maaari naming ibalik ang sk kung alam namin ang k at mayroong isang kaukulang pirma.

Ang Pag-atake

Kung ang h₁ at h₂ ay bumubuo ng parehong subgroup ng isang malaking order, pagkatapos ay wala kaming nakukuhang espesyal na impormasyon tungkol sa kanilang kapangyarihan h₁ᵏ at h₂ʳ na maaari naming magamit upang malaman ang isang bagay tungkol sa k. Pormal, ang pag-aaring ito ay tinatawag na statistic zero-knowledge.

Gayunpaman, sa panahon ng pangunahing yugto ng henerasyon, ang pagpapatupad ng ZenGoonly ay nagpatunay na ang isang discrete log ng h₂ hinggil sa h₁ ay mayroon, ibig sabihin ang ⟨h₂⟩ ay isang subgroup ng ⟨h₁⟩ (at hindi kabaligtaran). Sa partikular, hindi ito nagpapataw ng mga hadlang sa |h₂| at kung paano ito nauugnay sa |h₁|.

Ang pangunahing ideya sa likod ng pag-atake ay nais namin ang sumusunod na tatlong mga pag-aari na magkakasabay na hawakan:

-|h₂| dapat ay sapat na maliit upang maaari tayong mabagsik-puwersa sa lahat ng mga posibleng halagang h₂ʳ;

-|h₁| dapat malaki para sa ⟨h₁⟩ upang maglaman ng sapat na mga elemento upang natatanging mapa mula sa h₁ᵏ hanggang k;

-ang pagmamapa mula sa h₁ᵏ hanggang k ay dapat na mahusay na makalkula, ibig sabihin dapat nating mabilis na makahanap ng discrete logarithms modulo N.

Maliit | h₂ |

Ang isang madaling paraan upang makamit ang unang pag-aari nang walang kawalan ng pangalawang patunay ng dlog ay upang itakda ang h₂ = 1, pagkatapos h₂ʳ = 1 anuman ang pagpipilian ng r, at z = h₁ᵏ (mod N).

Ang isang natural na reaksyon ay tahasang ipinagbabawal ang h₂ = 1, ngunit hindi ito masyadong makakatulong. Ang isang mas sopistikadong (ngunit ganap na praktikal) na diskarte para sa isang kalaban ay pumili ng h bilang isang random na ugat ng pagkakaisa ng maliit na kaayusan. Ang nasabing h₂ ay maaaring mabuo nang mabisa sapagkat alam natin ang pag-factor ng N.

Mahusay na mga dlog

Mayroong maraming mga paraan upang piliin ang N sa isang paraan na nagpapahintulot sa amin na mahusay na kumuha ng mga dlog. Ang isang posibleng pagpipilian ay itakda ang N = ²²⁵⁶> q, at gumamit ng isang bit-by-bit na algorithm na inilarawan dito.

Ang isa pang praktikal na pagpipilian ay piliin ang N bilang isang malaking makinis na numero. Pagkatapos ay maaari naming gamitin ang general Pohlig — Hellman algorithm.

Pagsasamantala

Ang kawalan ng pangalawang patunay ng dlog (h₁ w.r.t. h₂) ay napakadali para sa isang nakakahamak na partido upang masiyahan ang lahat ng tatlong mga katangian na inilarawan sa itaas.

Maaari nilang malaman ang lihim na pagbabahagi ng bawat partido at madaling ibalik ang nakabahaging lihim. Bilang isang resulta, nakakuha sila ng kapangyarihan na mag-isa na mag-sign ng mga transaksyon. Pinapayagan silang i-laman ang wallet ng samahan sa pamamagitan ng paglilipat ng lahat ng mga assets sa kanilang sarili.

Upang makita ang pag-atake sa aksyon hanggang sa punto ng pagkakalantad ng mga pribadong key, tingnan ang aming imbakan.

Napapansin na ang mga praktikal na solusyon na nakabatay sa TSS ay karaniwang may maraming antas ng pagtatanggol, at ang mga nasabing pagsasamantala ay maaaring tumigil sa kalsada.

Sa parehong oras, ito ay hindi sa anumang paraan ang nais na sitwasyon. Sa katunayan, ang nakabahaging lihim ay maaaring hindi isang susi sa wallet, ngunit sa halip, ilang sensitibong impormasyon, na nais ng aming mga gumagamit na ligtas na maiimbak sa blockchain — isang kaso ng paggamit na susuportahan ng aming pagpapatupad ng TSS sa paglabas nito.

Isang Tala ng Pagsara

Sa totoo lang, nangangailangan ang GG20 ng isang pangatlong partido— na ang N ay isang produkto ng dalawang ligtas na kalakasan at wala rin ito sa silid-aklatan ng ZenGo. Ngunit kung ang h₁ at h₂ ay bumubuo ng parehong pangkat, ang kawalan ng patunay na ito ay hindi maaaring humantong sa anumang impormasyon na tumagas — ang protokol ay statistical zero-knowledge anuman ang N.

Ang orihinal na pangangatuwiran sa likod ng pag-akalang N ay hindi namin nais na ang ibang mga partido ay mabilis na makapagpahiwatig sa bilang na ito. Gayunpaman, tulad ng ipinaliwanag ni Rivest at Silverman sa kanilang artikulo noong 1999, ang mga alalahanin na nauugnay sa pag-iingat ay hindi na nauugnay sa ngayon, dahil ang kasalukuyang kalagayan ng mga pamamaraan sa pag-iingat ng sining ay gumagana laban sa ligtas na mga kalakasan din.