Puncte:3

două chei ECDSA la distanță apropiată

drapel yt

Să presupunem că unul folosește două chei private $x_1$ și $x_2$ pentru a genera două chei publice ECDSA $y_1$ și $y_2$ (de exemplu, folosit ca cheie publică pentru adresa Bitcoin). Distanța dintre $x_1$ și $x_2$ este mic (de exemplu, mai puțin de ${2^{20}}$). Ceea ce este rău despre?

Știu că dacă se rupe unul $x_1$, duce cu siguranță la spargerea $x_2$ cu un mic efort de căutare. Dar să presupunem că, cu excepția $|x_1 - x_2|$ este un număr mic toate celelalte practici sunt sigure, de ex. nu reutilizați niciodată non-urile aleatorii în semnare, există alte rezultate proaste (cu excepția faptului că spargerea unei monede este ca și cum ați sparge două)?

kelalaka avatar
drapel in
Principalul atac asupra semnăturii este falsificarea semnăturilor. Există, de asemenea, un eșec total că atacul dezvăluie cheia. Ce altceva dorești?
Sean avatar
drapel yt
Să presupunem că este dată o semnătură existentă care este generată folosind $x_1$. Cum ar putea atacatorul să falsifice altul (cum a fost generat folosind $x_2$) dacă nu cunoaște nonce aleatoriu folosit în prima semnătură?
kelalaka avatar
drapel in
Dacă semnați un mesaj de două ori cu cele două chei folosind non-uri diferite, atunci acest lucru poate oferi informații despre distanța non-urilor.
Sean avatar
drapel yt
Dar dacă semnezi același mesaj folosind aceeași cheie, nu ar fi dezvăluirea și distanța de nonces (și mai rău?) --- Deci, ce se întâmplă dacă nu semnează niciodată același mesaj a doua oară?
Puncte:1
drapel es

Lăsa $d=x_2-x_1$, și lăsați cheile publice să fie pe punctul de bază binecunoscut $G$. Prin urmare, perechile de chei vor fi $(x_1, X_1=x_1G)$ și $(x_2, X_2=x_2G)$.

Valoarea $d$ poate fi forțat brut folosind Pas-Mare-Pas-Mic metoda, care va dura mai puțin de o secundă pe un procesor modern când $n=20$.

Dacă utilizați o semnătură Schnorr pentru a semna un mesaj $m$ folosind $X_1$, ați crea perechea de semnături $(c, r_1)$ prin alegerea unui nonce uniform aleatoriu $k$, și apoi calculând $c=H(kG\mathbin\| m)$ și $r_1=k-cx_1$.

Semnătura se verifică prin verificare $c\overset{?}{=}H(r_1G+cX_1 \mathbin\| m)$.

Atacatorul, care a fost forțat $d$, poate crea apoi o semnătură pe același mesaj, dar care pare să fie semnată de cealaltă cheie privată $x_2$, după cum urmează:

Valorile lui $k$ și $c$ ar rămâne la fel. Apoi calculează $r_2=r_1-cd$. Semnătura falsificată este perechea $(c, r_2)$.

Semnătura va fi verificată prin verificarea acesteia $c\overset{?}{=}H(r_2G+cX_2 \mathbin\| m)$.

Acest lucru va verifica cu succes dacă $kG==r_2G+cX_2$, ceea ce va fi adevărat dacă $k==r_2+cx_2$.

Prin substituire $r_2==r_1-cd$ și $x_2==d+x_1$, putem vedea că acest lucru va fi adevărat datorită alegerii noastre $r_2$.

Acest atac funcționează numai dacă hash-ul sau mesajul nu leagă semnătura de o anumită cheie publică. Dacă protocolul impunea asta $c$ a fost în schimb calculată ca $c=H(kG\mathbin\| X_1\mathbin\| m)$, atacul nu ar funcționa deoarece valoarea de $c$ nu a putut fi reutilizată între semnături (deoarece verificatorul ar verifica semnătura prin concatenare $X_2$ în interiorul hashului în loc de $X_1$).

poncho avatar
drapel my
„Conform întrebării, acest lucru nu va dura mai mult de $2^{21}$ încercări, ceea ce va dura mai puțin de o oră pe un procesor modern.”; de fapt, se poate face cu circa $2^{11}$ încercări (să zicem, folosind Big-Step-Little-Step); este mai degrabă o secundă...
poncho avatar
drapel my
Nu, Big-Step-Little-Step implică doar adăugiri...
knaccc avatar
drapel es
@poncho Mulțumesc, am fost confuz la început, dar acum pot vedea că o perspectivă este că o căutare hashtable este mult mai rapidă decât efectuarea unei adăugiri. Am implementat metoda ta pentru a o testa și funcționează foarte bine.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.