[148856] in cryptography@c2.net mail archive
Re: [Cryptography] BitCoin Question - This may not be the best
daemon@ATHENA.MIT.EDU (Robert Christian)
Tue Dec 31 14:22:08 2013
X-Original-To: cryptography@metzdowd.com
From: Robert Christian <robertjchristian@gmail.com>
In-Reply-To: <D981D4AD-999C-455A-8FD8-1BC82F4B8C3B@gmail.com>
Date: Tue, 31 Dec 2013 10:01:25 -0800
To: Steve Weis <steveweis@gmail.com>
Cc: cryptography <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============3603085917397566564==
Content-Type: multipart/alternative; boundary="Apple-Mail=_6E48C041-F66D-49AB-937F-39EAD5192846"
--Apple-Mail=_6E48C041-F66D-49AB-937F-39EAD5192846
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=windows-1252
On Dec 22, 2013, at 9:44 PM, Robert Christian =
<robertjchristian@gmail.com> wrote:
>=20
> On Dec 22, 2013, at 6:31 PM, Robert Christian =
<robertjchristian@gmail.com> wrote:
>=20
>> Exactly my point. What's the collision resolution strategy and why =
isn't this a scary proposition?
>>=20
>=20
> I did the math on this and it starts to make sense without a collision =
strategy. For ID's, it's 34 characters that can be 0..9, a..z, and =
A..Z. That's 64^34. If you could do 5,000 wallet generations per =
second, it's =3D(64^34)/(5000*60*60*24*365*1E+51) to get 16 percent all =
possible addresses within a year with all systems working full time - =
being a total of =
100,000,000,000,000,016,384,608,344,632,472,552,568,168,984,184,560 =
machines on the task. I think that settles it as a non-efficient means =
of hacking, at least for the next decade or so until quantum computing =
comes into play.
>=20
> Can someone please check my math? And my premise in general? I feel =
like I might be missing something fundamental here=85. and I think at =
this point it=92s established that there is no collision strategy at all =
regardless of the fact it=92s unlikely?
>>
Edit: There are only 58 possible characters. 0OlI are excluded from =
the set to avoid being misread. and there are a few characters within =
the address used for version and checksum.
>=20
>=20
>> On Sunday, December 22, 2013, Steve Weis wrote:
>> On Sun, Dec 22, 2013 at 4:30 PM, Robert Christian
>> <robertjchristian@gmail.com> wrote:
>> > 2) I am pointing out that addresses are finite, and 34 chars =
long... They
>> > can only be upper or lower case, or 0..9. So at the end of the =
day, after
>> > all the fancy stuff, the number of all possible bitcoin addresses =
is
>> > (26*2+10)^34 possible unique ids.
>> >
>> > So the number of possible unique addresses is actually relatively =
smalll.
>> > Right?
>>=20
>> The address has 20-bytes of hash, a network ID byte prefix, and a
>> 4-byte checksum. So, there are 2^160 possible unique addresses. This
>> is converted into a 34 character base-58 string.
>>=20
>> You do bring up one point that many key pairs will collide for a
>> particular address. That's why the hash function must be assumed to =
be
>> collision resistant.
>>=20
>> As for when we might see collisions, with a birthday attack you'd
>> expect there to be a 50% chance of some collision existing when there
>> are roughly 2^80 addresses.
>=20
--Apple-Mail=_6E48C041-F66D-49AB-937F-39EAD5192846
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=windows-1252
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dwindows-1252"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space;"><br><div><div>On Dec 22, 2013, at 9:44 PM, Robert =
Christian <<a =
href=3D"mailto:robertjchristian@gmail.com">robertjchristian@gmail.com</a>&=
gt; wrote:</div><br class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite"><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dwindows-1252"><div style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space;"><br><div><div>On Dec 22, 2013, at 6:31 PM, Robert =
Christian <<a =
href=3D"mailto:robertjchristian@gmail.com">robertjchristian@gmail.com</a>&=
gt; wrote:</div><br class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite">Exactly my point. What's the collision resolution =
strategy and why isn't this a scary =
proposition?<span></span><br><br></blockquote><div><br></div><div>I did =
the math on this and it starts to make sense without a collision =
strategy. For ID's, it's 34 characters that can be 0..9, a..z, and =
A..Z. That's 64^34. If you could do 5,000 wallet generations =
per second, it's =3D(64^34)/(5000*60*60*24*365*1E+51) to get 16 percent =
all possible addresses within a year with all systems working full time =
- being a total of =
100,000,000,000,000,016,384,608,344,632,472,552,568,168,984,184,560 =
machines on the task. I think that settles it as a non-efficient =
means of hacking, at least for the next decade or so until quantum =
computing comes into play.</div><div><br></div><div>Can someone please =
check my math? And my premise in general? I feel like I =
might be missing something fundamental here=85. and I think at this =
point it=92s established that there is no collision strategy at all =
regardless of the fact it=92s =
unlikely?</div></div></div></blockquote><div><br></div>>></div><div>=
<br></div><div>Edit: There are only 58 possible characters. =
0OlI are excluded from the set to avoid being misread. and =
there are a few characters within the address used for version and =
checksum.</div><div><br></div><div><blockquote type=3D"cite"><div =
style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
-webkit-line-break: =
after-white-space;"><div><div><br></div><br><blockquote type=3D"cite">On =
Sunday, December 22, 2013, Steve Weis wrote:<br><blockquote =
class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc =
solid;padding-left:1ex">
On Sun, Dec 22, 2013 at 4:30 PM, Robert Christian<br>
<<a href=3D"javascript:;" onclick=3D"_e(event, 'cvml', =
'robertjchristian@gmail.com')">robertjchristian@gmail.com</a>> =
wrote:<br>
> 2) I am pointing out that addresses are finite, and 34 chars =
long... They<br>
> can only be upper or lower case, or 0..9. So at the end of =
the day, after<br>
> all the fancy stuff, the number of all possible bitcoin addresses =
is<br>
> (26*2+10)^34 possible unique ids.<br>
><br>
> So the number of possible unique addresses is actually relatively =
smalll.<br>
> Right?<br>
<br>
The address has 20-bytes of hash, a network ID byte prefix, and a<br>
4-byte checksum. So, there are 2^160 possible unique addresses. This<br>
is converted into a 34 character base-58 string.<br>
<br>
You do bring up one point that many key pairs will collide for a<br>
particular address. That's why the hash function must be assumed to =
be<br>
collision resistant.<br>
<br>
As for when we might see collisions, with a birthday attack you'd<br>
expect there to be a 50% chance of some collision existing when =
there<br>
are roughly 2^80 addresses.<br>
</blockquote>
</blockquote></div><br></div></blockquote></div><br></body></html>=
--Apple-Mail=_6E48C041-F66D-49AB-937F-39EAD5192846--
--===============3603085917397566564==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============3603085917397566564==--
