A BitCoin.com-on megjelent figyelmeztető szerint az Android biztonságos véletlengenerátorának hibája miatt elcsenhető a készülékeken generált címekről azok tartalma. A HackerNews kommentelői szerint - és ezt a BitCoin Talk fórumbejegyzései is alátámasztják - a problémát az okozza, hogy a BitCoin tranzakciók aláírására használt ECDSA algoritmushoz az Android készülékek esetenként azonos véletlenszámot generálnak, két azonos véletlent használó tranzakcióból alapján pedig egy támadó új tranzakciót indíthat (a matekot frissítésben leírom).

A problémát tovább súlyosbítja, hogy az ilyen, nem megfelelően hitelesített tranzakciók (így a sérülékeny tárcák) könnyedén megtalálhatók, a BitCoin Talk már a probléma aktív kihasználásáról is beszámolt. 

Hab a tortán, hogy ha tényleg az Android PRNG-jével van a baj, az kriptográfiai alkalmazások sokaságát érintheti. Szerk.: Itt egy viszonylag friss kutatás a különböző SecureRandom implementációk biztonsági problémáiról.

A posztot folyamatosan frissítem.

BitCoin matek

Akkor a lájtos pánik közepén próbáljuk lenyugtatni magunkat némi egyszerű matekkal! Ahogy a BitCoin wiki írja, "az ECDSA az az algoritmus, ami garantálja, hogy a BitCoin-okat csak jogos tulajdonosuk költhesse el" - szóval egy elég fontos algoritmusról van szó :) Az ECDSA a (remélhetőleg) jól ismert DSA algoritmus elliptikus görbékre kiterjesztett változata. Az elliptikus görbék (EC) részleteibe vasárnap éjjel nem szeretnék belemenni, wacher jegyzetei remek összefoglalót adnak a témában, méghozzá magyar nyelven. A jelenlegi probléma megértéséhez a következőkkel kell tisztában lennünk:

1. Az EC kriptorendszerek ún. trapdoor eljárása, ami garantálja az algoritmusok biztonságát az elliptikus görbék felett értelmezett sakláris szorzás, amit *-al fogunk jelölni. Q=n*P esetén (ahol P és Q egy adott görbe ismert pontjai) n skalár megtalálása nehéz feladat.
2. Egy m üzenetre jelentősen leegyszerűsítve az ECDSA aláírás a következő módon áll elő (minden mod n értendő, n egy nagy szám): s=k^-1(H(m)+xr), ahol
   • k egy véletlen szám,
   • H() egy kriptográfiai hash függvény,
   • x az aláíró privát kulcsa,
   • r pedig a k*G pont első koordinátája, mellesleg az aláríás másik nyilvános tagja s mellett. 

Így két üzenetre az aláírások ideális esetben:

s1=k1^-1(H(m1)+xr1)
s2=k2^-1(H(m2)+xr2)

Amennyiben azonban k=k1=k2:

s1=k^-1(H(m1)+xr)
s2=k^-1(H(m2)+xr)

s1-s2=H(m1)/k+xr/k-(H(m2)/k+xr/k)=(H(m1)-H(m2))/k

Innen pedig k sima szorzással/osztással kijön, ahonnan az egyik ismert egyenlőséget átrendezve

x=(ks1-H(m1))/r  //Igen, ez a privát kulcs

(TL;DR) Vagyis a támadó végignézi a tranzakcióidat (ezt a BitCoin hálózat nyilvántartja), és ha talál két azonos k-val generált aláírást, kiszámolja a privát kulcsodat, amivel az összes lóvédat átutalhatja magának. 

Örülnék, ha egy kriptoguru átnézné ezt a részt, ezen kívül miért nincs a blog.hu-n LaTeX?