Topic: Se tu avessi scoperto un algoritmo ECDLP , che strategia useresti ? (Read 3422 times)

questo interessante paper

http://eprint.iacr.org/2016/003.pdf

congettura la possibile esistenza di un algoritmo di ordine 2^n/3

e' solo una congettura, e nel paper affrontano solo problemi su F2^n   (e non su Fp come Secp256k1)
e inoltre non ECDLP completo  ma una sorta di "riduzione in 2 polinomiali"

pero' un eventuale algoritmo del genere renderebbe il livello di 256 bit di ECDSA a rischio.

2^(n/3) e' ancora arduo ma comincia ad essere trattabile.

Difficile, visto che non esiste...

Magari però uno per l'economia, come venne fatto con Nash.

Giorni fa ci sono stati sviluppi per ECDLP in Fp^n. Per ora non ci sono problemi per Fp.

+1.
Pero' mi e' venuto in mente che potresti diffondere l'algoritmo spacciandoti per Satoshi dopo aver craccato una sua chiave .... non saresti famoso ma forse almeno ancora vivo. Magari beccano poi il vero Satoshi ...

l'altra opzione e' diventare forse famoso ma anche parecchio morto ...
credo che a tutt'oggi  l'affare bitcoin sia una caccola in confronto agli interessi mondiali che girano criptati tramite EC.

In effetti è un caso che non avevo considerato: sarebbe una tentazione molto forte, e con una cifra del genere si potrebbero coprire abbastanza bene le tracce.
Il grosso problema starebbe nell'usare i mixer: non penso che ad oggi ci siano mixer con capacità di coprire simili cifre (bitmixer dichiara una copertura di 2000 bitcoin con fee dello 0,5%), occorrerebbe spezzettare il wallet in decine migliaia di indirizzi di pochi bitcoin per renderli poco tracciabili e poi passarli a vari mixer un po' di volte. Le fee a quel punto diventerebbero importanti (con 40 passaggi si parla di oltre 6 milioni di euro) e i tempi salirebbero a 2-3 mesi per incassare i bitcoin lavati, ma tanto sarebbero di "guadagno" pulito, se così si può dire
Resta poi sempre il problema di spenderli senza farsi arrestare

interessante.

e il caso svuoto UN indirizzo tipo questo :

   79957.11266252  1FeexV6bAHb8ybZjqQMjJrcCrHGW9sb6uF     75 Wed Dec  2 05:26:02 2015       0 Thu Jan  1 00:00:00 1970

il terzo piu ricco ad oggi e mai movimentato in usita, sono circa 32 milioni di euro.

Sicuro che tutti sospetterebbero che e' stato scoperto un ECDLP subesponenziale ? io penso che farebbero tutti milioni di ipotesi prima dell'ECDLP.

e tu hai 32 milioni di euro da mixare diciamo 50 volte, (tanto anche se paghi un milione di commissioni che te frega ?)
e cambiare pian piano lentamente, e senza seminare nessun panico, e senza rischiare quasi niente.... non ti piace come piano ?

Penso che sarebbe molto difficile tener nascosta una simile scoperta, inoltre non porterebbe quasi nessun vantaggio economico temo.
Immaginiamo un po' di scenari possibili:

1. tengo l'algoritmo per me e cerco di svuotare gli address più polposi perchè sono ingordo e per fare in fretta
Appena si scopre che vengono bucati facilmente i wallet si diffonde il panico e il prezzo inizia a crollare.
Mi ritrovo con migliaia di bitcoin rubati, facilmente tracciabili e difficilmente incassabili (in quale exchange in una situazione di incertezza si possono cercare di vendere bitcoin per milioni di dollari in poco tempo?)

2. tengo l'algoritmo per me e prelevo poche migliaia di satoshi da ogni indirizzo (restano comunque parecchie migliaia di bitcoin)
Qui diventa più probabile che la scoperta sia ritardata di qualche tempo, ma occorre che l'algoritmo sia di parecchi ordini di grandezza più rapido rispetto alla situazione attuale.
Ad ogni modo rimangono le difficoltà di incassare somme ingenti, provenienti da indirizzi rubati

3. diffondo l'algoritmo, dopo aver dato modo agli sviluppatori di introdurre delle modifiche ai client (tipo il resto su un nuovo indirizzo obbligatorio)
In questo scenario non guadagno nulla lato bitcoin, ma magari un nobel per la matematica

Io penso sceglierei il n.3

Tipo questo indirizzo....

3Nxwenay9Z8Lc9JBiywExpnEFiLp6Afp8v

Date un occhiata....ha fatto qualche regalino per Natale

qualche info tecnica:

Bitcoin usa i parametri di curva ellittica Secp256k1

il cui ordine e' n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

attualmente gli algoritmi piu' potenti per fare ECDLP  (ecc 2015 http://ecc2015.math.u-bordeaux1.fr/documents/galbraith.pdf)

tipo pollard rho + Montgomey sono attorno al 0.5 * sqrt(ord) (anche qualcosina piu' veloci in media)

Tradotto, siamo a circa 127 bit. Un livello molto piu' basso di quel che ho visto spesso citato in vari post,
ma comunque sempre mostruosamente sicuro.

Sempre che qualcuno non inventi qualcosa di piu' efficace

e se TU avessi inventato questo qualcosa piu' efficace, che strategia useresti ?

sopra ho scritto "stragrande maggioranza", mentre volevo scrivere "buona percentuale". ero un po' addormentato.

i dati corretti sono questi:

---------------------------------------------------------------------------------------------------------------------------------------------------
block#  389112  18/12/2015               num  %noOut   %dead   %of tot %of act  diff prev           value  %noOut  %vdead   %TotVal       diff prev
---------------------------------------------------------------------------------------------------------------------------------------------------
= 0                                105666950   0.00%   0.00%  94.2141%             224395         0.00000   0.00%   0.00%   0.0000%         0.00000
= 1 satoshi (0.00000001 BTC)          424398  36.80%   8.44%   0.3784%   6.54%         -8         0.00424  36.80%   8.44%   0.0000%        -0.00000
> 1 satoshi <= 0.001 BTC  ( ~1$ )    2949720  65.38%   9.13%   2.6300%  45.46%       2535       652.65014  54.57%   2.77%   0.0044%         0.94783
> 0.001 BTC <= 0.1 BTC               2059317  56.17%   3.21%   1.8361%  31.73%       2769     40749.41723  58.64%   5.09%   0.2721%       135.92941
> 0.1 BTC <= 1 BTC                    623416  60.72%   3.26%   0.5558%   9.61%       8792    258538.99755  64.81%   4.60%   1.7265%      3210.05956
> 1 BTC <= 5 BTC                      243877  62.00%   3.35%   0.2174%   3.76%       5329    556227.89543  62.12%   3.78%   3.7144%     10208.69503
> 5 BTC <= 10 BTC                      57418  60.99%   3.90%   0.0512%   0.88%        451    435549.54617  62.48%   4.00%   2.9085%      3045.20245
> 10 BTC <= 25 BTC                     45897  60.84%   4.07%   0.0409%   0.71%        207    745576.94161  61.95%   4.28%   4.9788%      2738.22599
> 25 BTC <= 50 BTC                     56901  85.63%  60.89%   0.0507%   0.88%          3   2508103.19612  88.66%  68.64%  16.7485%      -193.33281
> 50 BTC <= 75 BTC                      8111  71.29%   7.87%   0.0072%   0.12%         16    468281.18524  69.96%   7.40%   3.1271%       890.82924
> 75 BTC <= 100 BTC                     7889  71.43%   4.68%   0.0070%   0.12%         14    747029.26682  72.13%   4.70%   4.9885%      1266.68873
> 100 BTC <= 500 BTC                    8946  61.40%   3.31%   0.0080%   0.14%         -7   1885254.11704  61.41%   2.48%  12.5893%      1084.63957
> 500 btc <= 1000 BTC                   1756  66.51%   0.00%   0.0016%   0.03%         -7   1228403.65966  66.45%   0.00%   8.2030%     -2024.17917
> 1000 BTC                              1549  64.30%   0.00%   0.0014%   0.02%         -6   6100737.52908  61.62%   0.00%  40.7392%    -16138.67862
                  Total Actives      6489195  60.13%   6.78%   5.7859% 100.00%      20088  14975104.40609  67.41%  12.84% 100.0000%      4225.02722
                  Total            112156145   3.48%   0.39% 100.0000%             244483  14975104.40609  67.41%  12.84% 100.0000%      4225.02722

                  Transactions      98653053                                       213847

la colonna noout dice che circa il 60 % degli indirizzi attivi non ha operazioni in output, quindi circa il 40% HA operazioni in output,
ed e' esposta a questo tipo di "remoto pericolo". e non parliamo di indirizzi da qualche spicciolo eh! ci sono anche membri illustri:



un po' di esempi tra gli indirizzi a maggior saldo:

  
  169731.81248748  1NGvjF6XbeoxWybkbtGeYCRJ7C46WSvbQn     16 Thu Dec 10 18:49:21 2015       2 Wed Nov  4 19:51:06 2015
  157997.25058871  1Jz6HEKNJpYjXAYRLn49QUUUrizL5qGxjM  20871 Sat Nov 28 11:10:43 2015       1 Tue Dec 30 17:26:55 2014
   76450.99651004  1JVTyjGMWNmNYwY4kjUagkyNs5nTHCM9By     84 Wed Dec  9 10:17:44 2015      63 Mon Dec 14 00:47:44 2015
   69370.10477328  1HQ3Go3ggs8pFnXuHVHRytPCq5fGG8Hbhx     59 Sat Dec  5 04:00:40 2015       1 Thu Apr 23 14:10:25 2015
   65000.21876778  18vo26nEeDt1Tw17CuWap3F5rKJjBXSMmL  20892 Wed Dec 16 15:29:45 2015      31 Wed Sep 23 17:12:02 2015
   51000.05753797  16cou7Ht6WjTzuFyDBnht9hmvXytg6XdVT     54 Wed Nov 25 00:47:46 2015      10 Sun Aug 31 05:06:42 2014
   40783.02023227  1LJD4nG9LW79pEQ3qMwuyiZ1mAzNDzH7Z6  20879 Wed Dec  2 13:50:14 2015       4 Wed Dec  2 13:50:14 2015
   34488.52941483  1awoNuvVb1WQ5CFkBRK2tJbUZJJkKvtos      5 Wed Oct  7 18:07:05 2015       3 Tue Jun 23 10:19:53 2015
   31506.99783275  1A85rBUFjST7o7MaRBcYdrX8afP4LjTjkV     11 Tue Nov  3 15:16:24 2015       1 Tue Nov  3 15:16:24 2015
   31000.05315620  12ib7dApVFvg82TXKycWBNpN8kFyiAN1dr     40 Wed Dec  2 05:26:02 2015       4 Sat Jul 24 23:35:23 2010
   29624.52786084  1HHTR3u3oCimeDoJwcNntvhQa5QptmQery  20862 Sun Jul 12 12:26:07 2015       2 Thu Jan  8 18:41:45 2015
   29000.00012333  13NNBop1ETfQQ78gC5q7dU8hXRRPVUwiRG      2 Wed Nov 25 00:47:46 2015       0 Fri Oct 27 16:32:49 2028
   29000.00000000  1QKgFeo2srXX5ZZ3nuygfGfkPKX5jF4SrX     30 Tue Nov 17 23:26:03 2015       1 Mon Dec 14 22:40:39 2015
  

Quando avevo tradotto questo articolo sul funzionamento del meccanismo dei resti

http://bitcoinedintorni.blogspot.it/2015/04/cinque-modi-di-perdere-bitcoin-con-gli.html

si faceva riferimento al fatto che alcuni software (tipo Multibit, Mycelium e Blockchain.info) rispedivano il resto all'indirizzo di partenza (non so se questo era/è il loro comportamento di default). A parte alcuni rari casi dove questa impostazione può essere utile (immaginate di importare in uno di questi wallet la chiave privata di un paper wallet, spendere una parte dei btc collegati all'indirizzo del paper wallet e poi eliminare il wallet digitale, dando per scontato che i btc "non spesi" siano rimasti sullo stesso indirizzo, se l'indirizzo del resto fosse diverso dall'indirizzo di partenza avreste irrimediabilmente perso i btc non spesi), nella maggior parte dei casi questa impostazione  riduce sia la sicurezza che l'anonimato.

gia'....
e nonostante questo, ci sono un sacco di indirizzi anche belli pieni di BTC che hanno transazioni in uscita....

È una delle regole base dell'utilizzo del bitcoin: evitare di riutilizzare 2 volte lo stesso indirizzo.
È anche per questo che un client ben impostato ad ogni transazione svuota completamente l'indirizzo di partenza, riversando l'eventuale resto su un terzo indirizzo (indirizzo del resto) diverso dal primo.

Se e' un indirizzo vergine dal quale non sono mai uscite transazioni, hai ragione.

Ma se da quell'indirizzo e' uscita anche una sola transazione, allora hai pubblicato la chiave pubblica vera.

Avevo proprio il timore che questa cosa non fosse cosi' nota....

In che senso? Questo è il modo in cui si ottengono gli indirizzi... non può non esser cosi...

Nella stragrande maggioranza degli indirizzi con saldo >0 NON e' cosi'.

Bhe attimo... Bitcoin parte da una chiave privata e:
1) Crea la pubblica con ECDLP
2) Fa un SHA256
3) Fa un RIPEMD-160
4) Aggiunge 0x00 davanti alla stringa
5) Fa un SHA256
6) Fa un altro SHA256

A questo punto hai la chiave pubblica di un address bitcoin in formato esteso (con un base58 ottieni l'indirizzo che conosciamo tutti).

Ora, anche se tu avessi un indirizzo pubblico conosciuto e pieno di BTC, potresti ottenere l'indirizzo del punto 6) con un decode base58... ma prima di poter utilizzare il tuo "algoritmo" che ti permette da una chiave pubblica ECDLP di passare a quella privata, dovresti comunque risalire anche tutto il resto della catena.

Per questo ho detto che importerebbe "relativamente". Ti manca da bucare almeno altri 2 algoritmi

si


beh per i btc vuol dire accedere a tutti gli address con saldo >0 che hanno almeno una tx firmata in output
(che sono molti ed e' proprio da dove mi e' partita la domanda)

Non ho capito, parli se qualcuno avesse scoperto come passare da una chiave pubblica alle private ellittiche?

Fermo restando che per il BTC questo importerebbe "relativamente", visto che non è l'unica chiave usata... ma la matematica dice che è molto più facile decriptare altri algoritmi che questo, quindi se sei riuscito a decriptare questo, potresti farlo anche su molti altri e sostanzialmente avresti accesso a moltissime informazioni criptate in giro per il mondo