Random Bullshit

Epic math fail

30-12-2010 19:11:37 CET Postato in: gente di un certo livello, nerdate | Commenta

Prendiamo l'esempio canonico di una firma ECDSA:

$$ \begin{aligned} r &= (k G)_x&\pmod n \\ s &= k^{-1}(z + r d_A)&\pmod n \end{aligned} $$

Un avversario conosce tutti i parametri, ad eccezione della chiave privata \( d_A \) e del parametro random \( k \).

In teoria, ogni firma è un sistema di due equazioni con due incognite, ma la prima equazione non è per niente facile da risolvere, quindi il sistema è sicuro - a patto che il parametro random non sia prevedibile o derivabile in alcun modo.

Mettiamo ora il caso di avere davanti due firme ECDSA \( (r_1, s_1) \) e \( (r_2, s_2) \) generate con la stessa chiave privata (a noi ignota) tali che \( r_1 = r_2 \). Questo significa che:

$$ \begin{aligned} (k_1 G)_x &\equiv (k_2 G)_x &\pod n \\ k_1 &\equiv k_2 &\pod n \end{aligned} $$

Ouch: il parametro random non è né random né imprevedibile, bensì è identico per entrambe le firme. Non sappiamo ancora il suo valore, ma possiamo tranquillamente calcolarlo attaccando \( s_1 \) e \( s_2 \) (ricordate: la parte computazionalmente ardua del problema è invertire la moltiplicazione scalare tra il parametro random e il punto generatore!):

$$ \begin{aligned} s_1 - s_2 &= k^{-1}(z_1 + r d_A) - k^{-1}(z_2 + r d_A) &\pmod n \\ s_1 - s_2 &= k^{-1}(z_1 - z_2) &\pmod n \\ k &= (s_1 - s_2)^{-1}(z_1 - z_2) &\pmod n \end{aligned} $$

Uh-oh... improvvisamente l'incognita è una sola: \( d_A \), ovvero la chiave privata usata per generare la firma.

A questo punto, non ci resta che inserire il valore appena calcolato in una delle due equazioni relative a \( s \) e risolvendola rispetto a \( d_A \):

$$ \begin{aligned} s_i &= k^{-1}(z_i + r d_A) &\pmod n \\ s_i k &= z_i + r d_A &\pmod n \\ s_i k - z_i &= r d_A &\pmod n \\ d_A &= r^{-1}(s_i k - z_i) &\pmod n \\ d_A &= (r(s_1 - s_2))^{-1}(z_1 s_2 - z_2 s_1) &\pmod n \end{aligned} $$

Lo so, state pensando: "belle seghe mentali, nessuno è così stupido da usare due volte lo stesso parametro random".

In effetti è vero, nessuno l'ha usato solo due volte, ma c'è chi l'ha usato per ogni singola firma generata: $REDACTED

EDIT: ho rimosso il nome e il link di chi ha fatto la pirlata in questione visto che tira aria di citazioni in giudizio. E' stato presentato al 27C3 e riguarda una console, Google è vostro amico.