Re: Potential DoS on Bittorrent
Skybuck Flying
"What would happen if a bad client connects with as many other clients as
possible and uploads bad pieces as slowly as possible" ?
Will the other clients discard the slow client (or piece) and get the same
piece from a faster source or will the other clients wait almost forever ?
;)
See if you have the alt.internet.p2p newsgroup.. it seems more appropriate
to post it there... I have included it as well ;)
Bye,
Skybuck.
"Mack" <macckone@a_nospamjunk123_ol.com> wrote in message
news:7i8351hvrmemiu1tu...@4ax.com...
> A potential trouble spot in the bittorrent protocol is that it allows
> any potential uploader to upload pieces of a file if they are willing.
> If a malicious client decides they want to prevent a particular client
> from finishing a file, they can start uploading erroneous pieces of
> the file. When the section is completed and the SHA1 hash doesn't
> match, the client discards the whole block and starts over. As long
> as the malicious client can get the victim client to receive the
> erroneous pieces, the victim can not complete the file transfer.
>
> A solution to this problem would be to include a mechanism where the
> victim can get verification checksums on sub-pieces of a file. This
> solution uses computational power but very little bandwidth.
>
> A different solution is to record the source of particular data and
> verify it against an another source. If different pieces are
> downloaded then one is most likely the correct piece and the other the
> erroneous piece. This solution allows a mix and match strategy on
> any sub-pieces that differ. With the usual 256k pieces composed of
> 16k sub-pieces this is a 2^16 problem maximum assuming all sub-pieces
> differ. This is readily solvable.
>
> In the general case all of the sub-pieces will come from a particular
> client. The strategy in this case is simply to select a different
> client when asking for the sub-pieces a second time. In the end-game
> mode more than one client may be providing sub-pieces. This requires
> tracking where the pieces came from and asking for them from a
> different source.
>
> Combining these two strategies allows effectively spotting erroneous
> sub-pieces and prohibiting a malicious client from providing pieces.
> Leslie 'Mack' McBride
> remove text between _ marks to respond via e-mail
none
anything from anyone that has more than 2 hash fails..... turns out that
hash fails are more a function of bad networks than anything else.
Greg
Mack
>I use bittorrent... What happens is ppl set it up to *not* dwnld
>anything from anyone that has more than 2 hash fails..... turns out that
> hash fails are more a function of bad networks than anything else.
That corresponds to the strategy disscussed below, currently not all
clients support this. However in end-game mode which client do you
charge with the hash fail? Remember multiple clients are providing
sub-pieces and only one sub-piece is needed to cause a fail. If
sub-pieces also had hashes in end-game mode this would not be a
problem but they don't. That would be the first strategy I discussed
below.
To greg:
Slow clients are discarded in favor of fast clients once the end-game
mode is reached.
Skybuck Flying
> On Tue, 05 Apr 2005 16:14:52 +1200, none <""bob\"@(none)"> wrote:
>
> >I use bittorrent... What happens is ppl set it up to *not* dwnld
> >anything from anyone that has more than 2 hash fails..... turns out that
> > hash fails are more a function of bad networks than anything else.
>
> That corresponds to the strategy disscussed below, currently not all
> clients support this. However in end-game mode which client do you
> charge with the hash fail? Remember multiple clients are providing
> sub-pieces and only one sub-piece is needed to cause a fail. If
> sub-pieces also had hashes in end-game mode this would not be a
> problem but they don't. That would be the first strategy I discussed
> below.
Good point.
Question:
Why are sub pieces downloaded from multiple clients ? Why not simply one
client ?
That would solve it.
>
> To greg:
>
> Slow clients are discarded in favor of fast clients once the end-game
> mode is reached.
Doesn't this mean bittorrent has another DoS ?
The slow connection DoS ? ;)
Bye,
Skybuck.
Andrew Swallow
[snip]
>
> Good point.
>
> Question:
>
> Why are sub pieces downloaded from multiple clients ? Why not simply one
> client ?
>
> That would solve it.
>
general public can receive download much faster than they can send.
Several clients are needed to receive at top speed.
I am surprised that the sub pieces do not have their own hash/CRC. A
method of ensuring that the entire message arrives is needed, possibly
by asking for missing pieces from the originating installation. The
identity of this installation will therefore have to be known.
Organisations like the BBC and the Hollywood studios will simply have to
keep their products online.
When used for business purposes a way of confirming delivery and viewing
will also be needed.
Andrew Swallow
Skybuck Flying
"Andrew Swallow" <am.sw...@btopenworld.com> wrote in message
news:d30dsp$8kn$1...@titan.btinternet.com...
> Skybuck Flying wrote:
> [snip]
> >
> > Good point.
> >
> > Question:
> >
> > Why are sub pieces downloaded from multiple clients ? Why not simply one
> > client ?
> >
> > That would solve it.
> >
> ISP supply users with different transmission and reception speeds. The
> general public can receive download much faster than they can send.
> Several clients are needed to receive at top speed.
Clients can download multiple pieces at the same time this should be enough
to receive at top speed so why split the pieces further into sub pieces ?
I think in the end splitting it into sub pieces is probably inefficient:
1. more protocol overhead for sub piece information/negotiation ?
2. tcp needs some time to get at top speed... having to restart all the time
doesnt seem that wise ;)
What are benefits for sub pieces ?
1. Maybe faster switching to different clients etc. Not necessarly faster
sharing since a complete piece has to be received first to check if the
piece was received correctly... unless one doesnt care about that and simply
uploads possible corrupted sub pieces etc ;)
Bye,
Skybuck.
none
> Skybuck Flying wrote:
> [snip]
> I am surprised that the sub pieces do not have their own hash/CRC.
I believe that they do. Thats what i meant by a hash fail. A torrent can
have multiple files as well. The total size of a torrent can be as small
as a few megs but usually are 100's of megs and most are 1 gig or more.
I normally have between 2-8 clients that i download from and about 2
that i'm uploading too (Sometimes thay can be clients i'm also
downloading from). These clients are *very* dynamic in every sense.
Bit torrent was never designed for any kind of security unfortunately. I
would expect that there would quite a large number of potential DoS
attacks. But i don't that the one mentioned here is "practical" one.
Greg
Mack
>Andrew Swallow wrote:
>> Skybuck Flying wrote:
>> [snip]
>
>> I am surprised that the sub pieces do not have their own hash/CRC.
>I believe that they do. Thats what i meant by a hash fail. A torrent can
>have multiple files as well. The total size of a torrent can be as small
>as a few megs but usually are 100's of megs and most are 1 gig or more.
Pieces have hashes, sub-pieces do not, at least according to the specs
I am reading. However sub-pieces are generally only used in end-game
mode when the number of potential senders exceeds the number of pieces
(which is generally about 2-8 as you stated). Different clients
handle this differently, but should all have some version since it is
compliant.
>
>I normally have between 2-8 clients that i download from and about 2
>that i'm uploading too (Sometimes thay can be clients i'm also
>downloading from). These clients are *very* dynamic in every sense.
>
>Bit torrent was never designed for any kind of security unfortunately. I
>would expect that there would quite a large number of potential DoS
>attacks. But i don't that the one mentioned here is "practical" one.
Until all clients start banning hash failed senders, the attack is
somewhat practical. But even in the case where 2 failed hashes
result in a ban, the end-game mode still does not cope well.
>
>Greg
Stephen Sprunk
> Pieces have hashes, sub-pieces do not, at least according to
> the specs I am reading.
Same for the one I'm reading, at least in the .torrent file. Perhaps once a
piece is started, the sender directly transmits hashes of the subpieces to
the receiver? See below on why I think this may happen.
In any case, pieces should be small enough that retrying the entire piece is
acceptable.
> However sub-pieces are generally only used in end-game mode
Not correct. Sub-pieces are always used to break up a piece into smaller
chunks for transmission. It's much easier (and more reliable) to ask for
16kB chunks than 256kB+ chunks even from one peer. Watching the graphs in
my clients, many sub-pieces are missed (for whatever reason) the first time
through, and the client goes back and requests them again. Since sub-pieces
are defined to be requested in order, needing retries for random ones
implies either protocol errors or hash/checksum failures.
> when the number of potential senders exceeds the number of
> pieces (which is generally about 2-8 as you stated). Different
> clients handle this differently, but should all have some version
> since it is compliant.
What is 2-8? One of the files I'm downloading right now has 9 seeds, 23
peers, 1413 pieces (of 512kB each), and 32 sub-pieces per piece.
I've never actually observed end-game mode in action, since it's such a tiny
fraction of the download time.
> > I normally have between 2-8 clients that i download from and
> > about 2 that i'm uploading too (Sometimes thay can be clients
> > i'm also downloading from). These clients are *very* dynamic in
> > every sense.
> >
> > Bit torrent was never designed for any kind of security
> > unfortunately. I would expect that there would quite a large
> > number of potential DoS attacks. But i don't that the one
> > mentioned here is "practical" one.
>
> Until all clients start banning hash failed senders, the attack is
> somewhat practical. But even in the case where 2 failed hashes
> result in a ban, the end-game mode still does not cope well.
True. I'm not aware of any client that doesn't ban peers sending bad data,
though. Already this morning, mine has banned one and it's been up less
than an hour.
Frankly, downloading the same 512kB piece a few times to eliminate the
random DoSer that may be present is nothing compared to the whole 5GB
download. Now, if there were many bad senders, this might be a real
problem, but you'd have to increase download times by a lot more than 0.01%
before anyone will care; the variation due to uneven download speeds is
orders of magnitude greater.
One extension to mitigate this might be clients informing the tracker of
peers they've banned; if several clients ban the same sender, the tracker
could remove it from circulation.
S
--
Stephen Sprunk "Those people who think they know everything
CCIE #3723 are a great annoyance to those of us who do."
K5SSS --Isaac Asimov
Twisted One
> Same for the one I'm reading, at least in the .torrent file. Perhaps once a
> piece is started, the sender directly transmits hashes of the subpieces to
> the receiver? See below on why I think this may happen.
This would suck. If we assume the sender of subpieces is untrusted, then
the hash they send is untrusted. It will match the data, even if the
data is bogus and the big piece will hash-fail, just so they can't be
fingered as the bad node, and so the downloader has to get the whole
piece again and not just the bad subpiece.
--
http://www.gnu.org/philosophy/right-to-read.html
Palladium? Trusted Computing? DRM? Microsoft? Sauron.
"One ring to rule them all, one ring to find them
One ring to bring them all, and in the darkness bind them."
none
> Stephen Sprunk wrote:
>
>> Same for the one I'm reading, at least in the .torrent file. Perhaps
>> once a
>> piece is started, the sender directly transmits hashes of the
>> subpieces to
>> the receiver? See below on why I think this may happen.
>
>
> This would suck. If we assume the sender of subpieces is untrusted, then
> the hash they send is untrusted. It will match the data, even if the
> data is bogus and the big piece will hash-fail, just so they can't be
> fingered as the bad node, and so the downloader has to get the whole
> piece again and not just the bad subpiece.
>
You get hash information from the "trusted" tracker... I think
Greg
Twisted One
Piece hashes, apparently, but apparently not subpiece hashes. From the
post I was replying to:
"Perhaps once a piece is started, the sender directly transmits hashes
of the subpieces to the receiver?"
--
Mack
<ste...@sprunk.org> wrote:
>"Mack" <macckone@a_nospamjunk123_ol.com> wrote in message
>news:p78951ha1111ghgjs...@4ax.com...
>> Pieces have hashes, sub-pieces do not, at least according to
>> the specs I am reading.
>
>Same for the one I'm reading, at least in the .torrent file. Perhaps once a
>piece is started, the sender directly transmits hashes of the subpieces to
>the receiver? See below on why I think this may happen.
>
>In any case, pieces should be small enough that retrying the entire piece is
>acceptable.
>
>> However sub-pieces are generally only used in end-game mode
>
>Not correct. Sub-pieces are always used to break up a piece into smaller
>chunks for transmission. It's much easier (and more reliable) to ask for
>16kB chunks than 256kB+ chunks even from one peer. Watching the graphs in
>my clients, many sub-pieces are missed (for whatever reason) the first time
>through, and the client goes back and requests them again. Since sub-pieces
>are defined to be requested in order, needing retries for random ones
>implies either protocol errors or hash/checksum failures.
Some clients use end-game mode all the way through, which sounds like
what yours is doing. In end-game mode each sub-piece is requested
from a different client (if possible). Some clients will respond with
a sub-piece some won't. If all are transmitted correctly (true in the
general case) then the piece succeeds once all pieces are transmitted.
A variation on this is requesting all pieces at the same time from the
same client. Although the specs say they should be requested in order
I think most clients use some kind of simultaneous requesting of more
than one sub-piece.
I am unaware of an extensions to provide hashes between clients.
Although such an extension would be a good one.
>
>> when the number of potential senders exceeds the number of
>> pieces (which is generally about 2-8 as you stated). Different
>> clients handle this differently, but should all have some version
>> since it is compliant.
>
>What is 2-8? One of the files I'm downloading right now has 9 seeds, 23
>peers, 1413 pieces (of 512kB each), and 32 sub-pieces per piece.
>
>I've never actually observed end-game mode in action, since it's such a tiny
>fraction of the download time.
>
When I say potential senders, I am talking about clients that don't
have you choked.
>> > I normally have between 2-8 clients that i download from and
>> > about 2 that i'm uploading too (Sometimes thay can be clients
>> > i'm also downloading from). These clients are *very* dynamic in
>> > every sense.
>> >
>> > Bit torrent was never designed for any kind of security
>> > unfortunately. I would expect that there would quite a large
>> > number of potential DoS attacks. But i don't that the one
>> > mentioned here is "practical" one.
>>
>> Until all clients start banning hash failed senders, the attack is
>> somewhat practical. But even in the case where 2 failed hashes
>> result in a ban, the end-game mode still does not cope well.
>
>True. I'm not aware of any client that doesn't ban peers sending bad data,
>though. Already this morning, mine has banned one and it's been up less
>than an hour.
>
The client I routinely use doesn't but I have very rarely seen bad
data either, of course it is a very old client. A drawback to banning
in an unhealthy torrent, someone with a bad connection may also be the
only person with "interesting" pieces.
>Frankly, downloading the same 512kB piece a few times to eliminate the
>random DoSer that may be present is nothing compared to the whole 5GB
>download. Now, if there were many bad senders, this might be a real
>problem, but you'd have to increase download times by a lot more than 0.01%
>before anyone will care; the variation due to uneven download speeds is
>orders of magnitude greater.
In a healthy torrent with many seeders and downloaders a DoS is out of
luck. In a torrent with only a few seeders it may succeed for some
length of time.
>
>One extension to mitigate this might be clients informing the tracker of
>peers they've banned; if several clients ban the same sender, the tracker
>could remove it from circulation.
>
>S
Leslie 'Mack' McBride
Stephen Sprunk
> On Thu, 7 Apr 2005 10:02:37 -0500, "Stephen Sprunk"
> <ste...@sprunk.org> wrote:
> > Not correct. Sub-pieces are always used to break up a piece
> > into smaller chunks for transmission. It's much easier (and
> > more reliable) to ask for 16kB chunks than 256kB+ chunks
> > even from one peer. Watching the graphs in my clients, many
> > sub-pieces are missed (for whatever reason) the first time
> > through, and the client goes back and requests them again.
> > Since sub-pieces are defined to be requested in order,
> > needing retries for random ones implies either protocol errors
> > or hash/checksum failures.
>
> Some clients use end-game mode all the way through, which
> sounds like what yours is doing. In end-game mode each sub-
> piece is requested from a different client (if possible). Some
> clients will respond with a sub-piece some won't. If all are
> transmitted correctly (true in the general case) then the piece
> succeeds once all pieces are transmitted.
I would expect the subpieces to come in nearly simultaneously or in random
order if this were what my client were doing...
> A variation on this is requesting all pieces at the same time from
> the same client. Although the specs say they should be
> requested in order I think most clients use some kind of
> simultaneous requesting of more than one sub-piece.
I think this is what my client does. Generally the 32 sub-pieces come
through in order, though it's rare that all 32 come through in the first
pass. Once one is missed, the receive rate drops way down, the remainder
(usually) of the subpieces come in, and it goes back to fetch the one or two
it missed. Often it takes several minutes to fetch the 32nd sub-piece --
longer than it took to grab the other 31.
According to the paper, clients are supposed to request the sub-pieces in
order from the same peer with 5 requests or so pipelined to keep TCP busy.
There are a few reasons why one subpiece might be missed in the middle even
if the client does use this model. TCP checksums aren't perfect, and
gigabytes of data are bound to have transient errors. Or a bug at the other
end might drop a request but process ones after it.
> I am unaware of an extensions to provide hashes between clients.
> Although such an extension would be a good one.
Though, going back to the original post, it wouldn't prevent a peer from
deliberately sending bad hashes. The only secure protection against
corruption at the subpiece level reduces to setting the piece size to the
minimum and have only one subpiece per piece.
> When I say potential senders, I am talking about clients that don't
> have you choked.
Ah, okay. That part of the paper hasn't really sunk in, so I don't know how
to predict how many of the peers/seeds I'm connected to will actually send
me pieces.
> The client I routinely use doesn't but I have very rarely seen bad
> data either, of course it is a very old client. A drawback to
> banning in an unhealthy torrent, someone with a bad connection
> may also be the only person with "interesting" pieces.
It's in the paper on the protocol, so I assumed all clients implement
banning. Mine, at least, has an option to turn it on or off, and it resets
the ban list when the client is restarted.
If banned folks are the only ones with "interesting" pieces, then the
protocol has failed. Every client should be attempting to get the rarest
pieces first, and presumably some will succeed before banning the only peers
that have them. If nobody can get the pieces even in that mode, the banned
peer is effectively not part of the network because their connection is
unusable.
> In a healthy torrent with many seeders and downloaders a DoS
> is out of luck. In a torrent with only a few seeders it may
> succeed for some length of time.
One could say that even in the absence of DoS, an unhealthy torrent is out
of luck.
Michael Amling
> Often it takes several minutes to fetch the 32nd sub-piece --
> longer than it took to grab the other 31.
Are you sure it's actually taking that long to fetch? Or has the 32nd
sub-piece been fetched and it's taking that long to check the piece's hash?
--Mike Amling
Mack
<ste...@sprunk.org> wrote:
err .. since the sub-pieces are sent over a TCP connection an error
would prevent any more arriving until the error is corrected. TCP
passes data up to the application in a strictly sequential order. The
only time a loss of order would happen is if the requests are actually
sent over a different TCP connection, ie. to a different host.
>
>> I am unaware of an extensions to provide hashes between clients.
>> Although such an extension would be a good one.
>
>Though, going back to the original post, it wouldn't prevent a peer from
>deliberately sending bad hashes. The only secure protection against
>corruption at the subpiece level reduces to setting the piece size to the
>minimum and have only one subpiece per piece.
>
If all of the sub-piece hashes matched and the piece didn't hash to
the torrent value then it is safe to assume the client is deliberately
sending bad hashes.
>> When I say potential senders, I am talking about clients that don't
>> have you choked.
>
>Ah, okay. That part of the paper hasn't really sunk in, so I don't know how
>to predict how many of the peers/seeds I'm connected to will actually send
>me pieces.
>
>> The client I routinely use doesn't but I have very rarely seen bad
>> data either, of course it is a very old client. A drawback to
>> banning in an unhealthy torrent, someone with a bad connection
>> may also be the only person with "interesting" pieces.
>
>It's in the paper on the protocol, so I assumed all clients implement
>banning. Mine, at least, has an option to turn it on or off, and it resets
>the ban list when the client is restarted.
>
>If banned folks are the only ones with "interesting" pieces, then the
>protocol has failed. Every client should be attempting to get the rarest
>pieces first, and presumably some will succeed before banning the only peers
>that have them. If nobody can get the pieces even in that mode, the banned
>peer is effectively not part of the network because their connection is
>unusable.
>
>> In a healthy torrent with many seeders and downloaders a DoS
>> is out of luck. In a torrent with only a few seeders it may
>> succeed for some length of time.
>
>One could say that even in the absence of DoS, an unhealthy torrent is out
>of luck.
A unhealthy torrent isn't quite dead yet. All it takes is one seeder
to keep it alive, but that isn't healthy. Remember all torrents start
out unhealthy. Even torrents without seeders can theoretically
recover if all of the pieces are shared by the remaining clients.
Stephen Sprunk
> On Thu, 7 Apr 2005 21:33:26 -0500, "Stephen Sprunk"
> <ste...@sprunk.org> wrote:
> > According to the paper, clients are supposed to request the sub-
> > pieces in order from the same peer with 5 requests or so
> > pipelined to keep TCP busy. There are a few reasons why one
> > subpiece might be missed in the middle even if the client does
> > use this model. TCP checksums aren't perfect, andgigabytes
> > of data are bound to have transient errors. Or a bug at the other
> > end might drop a request but process ones after it.
>
> err .. since the sub-pieces are sent over a TCP connection an error
> would prevent any more arriving until the error is corrected. TCP
> passes data up to the application in a strictly sequential order. The
> only time a loss of order would happen is if the requests are actually
> sent over a different TCP connection, ie. to a different host.
TCP's checksum is much weaker than a cryptographic hash. When transferring
multi-GB files over TCP, undetected errors are _expected_, which is why BT
uses strong hashes on each piece.
> > Though, going back to the original post, it wouldn't prevent a
> > peer from deliberately sending bad hashes. The only secure
> > protection against corruption at the subpiece level reduces to
> > setting the piece size to the minimum and have only one
> > subpiece per piece.
>
> If all of the sub-piece hashes matched and the piece didn't hash to
> the torrent value then it is safe to assume the client is deliberately
> sending bad hashes.
Is there any way to determine the set of sub-piece hashes do not match the
full piece hash without downloading an entire bad piece?
Vernon Schryver
Stephen Sprunk <ste...@sprunk.org> wrote:
>TCP's checksum is much weaker than a cryptographic hash. When transferring
>multi-GB files over TCP, undetected errors are _expected_, which is why BT
>uses strong hashes on each piece.
I am having trouble making sense of that paragraph.
- That the TCP checksumis is not a cryptographic hash is irrelevant
as far the integrity of TCP data with the usual distribution
errors. Cryptographic checksyms have very different design goals
compared to the goals for simple data communications.
- When transfering files far larger than 10^9 bytes, you do not
expect enough undetect errors to talk aobut. This has been well
known in practice by decades by people who've been pushing GBytes
throught TCP connections. (True, not with WINTEL PCs.)
- The primary defenses against TCP (and UDP) data errors are the
lower level checksums such as the Ethernet CRC. The TCP checksum
exists only to detect the rare errors not detected by those lower
level errors. This fact is why many people over the years have
argued that the TCP checksum should be turned off. The rest of
us have argued otherwise since the late 1980's when host CPUs got
fast enough to make the TCP (and UDP) checksum worth its keep to
detect bad RAM in a router or other rare problems.
- You can get a feeling for the number of undetected TCP checksum
errors on any busy host that has a reasonable version of the
`netstat` command. Look for counts from `netstat -s` or similar
about bad checksums to see how bad packets were detected. If you
assume the errors uniformly distributed, then that the undetected
error rate should be about 0.0015% of the detected error rate.
Vernon Schryver v...@rhyolite.com
Mack
(Vernon Schryver) wrote:
>In article <1113092660.2ebaeb2be10e21d8faf629daa659ad4c@teranews>,
>Stephen Sprunk <ste...@sprunk.org> wrote:
>
>
>>TCP's checksum is much weaker than a cryptographic hash. When transferring
>>multi-GB files over TCP, undetected errors are _expected_, which is why BT
>>uses strong hashes on each piece.
>
>I am having trouble making sense of that paragraph.
>
> - That the TCP checksumis is not a cryptographic hash is irrelevant
> as far the integrity of TCP data with the usual distribution
> errors. Cryptographic checksyms have very different design goals
> compared to the goals for simple data communications.
>
> - When transfering files far larger than 10^9 bytes, you do not
> expect enough undetect errors to talk aobut. This has been well
> known in practice by decades by people who've been pushing GBytes
> throught TCP connections. (True, not with WINTEL PCs.)
>
> - The primary defenses against TCP (and UDP) data errors are the
> lower level checksums such as the Ethernet CRC. The TCP checksum
> exists only to detect the rare errors not detected by those lower
> level errors. This fact is why many people over the years have
> argued that the TCP checksum should be turned off. The rest of
> us have argued otherwise since the late 1980's when host CPUs got
> fast enough to make the TCP (and UDP) checksum worth its keep to
> detect bad RAM in a router or other rare problems.
IPv6 has removed the IP header checksum in favor of the underlying
transmission media providing that service, after all IP is
'unreliable'. TCP is supposed to be more reliable, and does offer an
extension mechanism for the basic checksum. The basic checksum also
detects different errors from the underlying CRC which is very
important.
>
> - You can get a feeling for the number of undetected TCP checksum
> errors on any busy host that has a reasonable version of the
> `netstat` command. Look for counts from `netstat -s` or similar
> about bad checksums to see how bad packets were detected. If you
> assume the errors uniformly distributed, then that the undetected
> error rate should be about 0.0015% of the detected error rate.
>
I would expect a greater number of lost/damaged packets to occur
on a DSL/Cable connection like most of us have. My DSL for example
detected 7 bad packets (using error correction code) over the last 24
hours. On bad days (rain/thunderstorms) this can be up to 10000.
Obviously I have a great DSL connection today and DSL uses better
error detection/correction than the CRC used by ethernet.
All host on my ethernet network show zero ethernet packet errors and
zero tcp errors. On a really busy ethernet host connected to the
backbone the number of errors per day between similar hosts is
neglible. Considering the higher quality of ethernet cabling and
backbone equipment, the error rate is going to be predominated by the
user connections.
The only times I have ever seen bad TCP packets are
1) from 'hostile' probing
2) when one of my switches flaked out (and every host told me about
it) ... flashing network connection lost on windows and beeping from
linux (with a host of messages).
3) traffic from a wireless host on the network (collisions and static
happen).
I used to see TCP errors and ethernet errors when using 'bus'
technology (hubs, 10base2, 10base5). Errors on most modern
ethernet networks are neglible.
Even DSL is good at catching errors. Cable and Wireless lag
behind in this respect since they use shared technology which depends
on errors to detect collisions.
>
>Vernon Schryver v...@rhyolite.com
Twisted One
> Even DSL is good at catching errors. Cable and Wireless lag
> behind in this respect since they use shared technology which depends
> on errors to detect collisions.
Netstat -s on my cable-connected system shows no errors (save address
errors) after hours of heavy p2p usage.
Vernon Schryver
Mack <macckone@a_nospamjunk123_ol.com> wrote:
>IPv6 has removed the IP header checksum in favor of the underlying
>transmission media providing that service, after all IP is
>'unreliable'.
I fear I might disagree with that if it were expanded.
> TCP is supposed to be more reliable, and does offer an
>extension mechanism for the basic checksum.
I don't understand that.
> The basic checksum also
>detects different errors from the underlying CRC which is very
>important.
I mostly agree with that.
>I used to see TCP errors and ethernet errors when using 'bus'
>technology (hubs, 10base2, 10base5).
That speaks more to the poor quality of a lot of 802.3 hardware
and worse installation than anything about "buses."
> Errors on most modern
>ethernet networks are neglible.
That has always been true with quality hardware. The defacto maximum
1500 byte MTU size doesn't push typical 32-bit CRCs, FCS, etc. It's
probably just as well that jumbo 802 frames seem to be dead and that
the 4K FDDI, 8K TR, and other large MTUs are variously dead or used
only in fairly restricted circumstances.
>Even DSL is good at catching errors.
There are many things covered by "DSL." Even a single DSL link often
involves more than one lower layer scheme between routers.
> Cable and Wireless lag
>behind in this respect since they use shared technology which depends
>on errors to detect collisions.
That's nonsense technically. "Collsions" are bad only in the ears
of people with limited technical knowledge and the mavens who write
the inter-ad filler in the trade rags. The nonsense and even lies
(e.g. from IBM Token Ring and 100VG-AnyLAN salescritters) about the
non-existent evils of collisions have been a pet peeve of mine since
the 1980's. (Yes, I know about the Ethernet Capture Effect and
realize it is related to the CSMA/CD exponential backoff algorithm.)
Those who care about the technical stuff instead of sales blather care
only about achieved bit and packet error rates. As long as the numbers
are right, wehther the network relies on wet string is irrelevant.
If your TCP/IP links have a worse than 50% probabilty of one wrong bit
in a GByte or 10,000,000,000 bits, then you are using very bad hardware
and probably worse software.
Vernon Schryver v...@rhyolite.com
Stephen Sprunk
news:d39ukg$9l1$1...@calcite.rhyolite.com...
Hi Vernon; good to see a familiar name in a different forum...
> In article <1113092660.2ebaeb2be10e21d8faf629daa659ad4c@teranews>,
> Stephen Sprunk <ste...@sprunk.org> wrote:
> > TCP's checksum is much weaker than a cryptographic hash.
> > When transferring multi-GB files over TCP, undetected errors
> > are _expected_, which is why BT uses strong hashes on each
> > piece.
>
> I am having trouble making sense of that paragraph.
>
> - That the TCP checksumis is not a cryptographic hash is irrelevant
> as far the integrity of TCP data with the usual distribution
> errors. Cryptographic checksyms have very different design goals
> compared to the goals for simple data communications.
They do have different design goals: TCP was designed to be cheap in
software in the 70s, and cryptographic hashes are designed to be strong
against a wide variety of factors. Sure, cryptographic protection is
overkill, but AFAIK nobody has developed a non-cryptographic hash that
protects against the common cases that a checksum (or even CRC) misses.
> - When transfering files far larger than 10^9 bytes, you do not
> expect enough undetect errors to talk aobut. This has been
> well known in practice by decades by people who've been
> pushing GBytes throught TCP connections. (True, not
> with WINTEL PCs.)
In the last week, I've downloaded about 15GB of data with BT. There were
about 20 hash fails on individual 512kB pieces.
While there are many possible places the data could have been corrupted, the
weakest link in the chain is TCP's checksum.
> - The primary defenses against TCP (and UDP) data errors are
> the lower level checksums such as the Ethernet CRC.
That's fine if you assume all errors will be on CRC-protected links and
detectable. They occur in other places too, and in ways that even CRCs
won't detect (with low but still nonzero probability).
> The TCP checksum exists only to detect the rare errors not
> detected by those lower level errors. This fact is why many
> people over the years have argued that the TCP checksum
> should be turned off. The rest of us have argued otherwise
> since the late 1980's when host CPUs got fast enough to
> make the TCP (and UDP) checksum worth its keep to
> detect bad RAM in a router or other rare problems.
I worked for a router vendor for years, and we had a constant stream of bugs
related to routers and switches mangling packets in ways that a simple
checksum could not detect. And then, of course, there's always "alpha
particle" corruption in fast RAM, which has led the same vendor to switch to
ECC; several bit errors _per minute_ are detected and corrected, which makes
me wonder what the real error rates are in non-ECC products.
While the odds of random bit flips in non-ECC memory resulting in something
a checksum wouldn't catch is low, it's still undeniably higher than the odds
of not being caught by a CRC or hash.
> - You can get a feeling for the number of undetected TCP
> checksum errors on any busy host that has a reasonable
> version of the `netstat` command. Look for counts from
> `netstat -s` or similar about bad checksums to see how
> bad packets were detected. If you assume the errors
> uniformly distributed, then that the undetected error rate
> should be about 0.0015% of the detected error rate.
Unfortunately, my host (WinXP x64 Edition) does not show the detected error
rate.
0.0015% is a lot when you're talking about GBs of data. If the detected
error rate is 0.01%, that still means there will be 6 undetected errors in a
4GB file (one DVD). Unacceptable.
There's a reason tools like SFV and PAR exist, as well as why BT and other
p2p protocols include cryptographic hashes. Even one wrong bit is one too
many, and TCP isn't getting the job done.
Stephen Sprunk
> In article <es6i51p7v6147lhmm...@4ax.com>,
> Mack <macckone@a_nospamjunk123_ol.com> wrote:
> >IPv6 has removed the IP header checksum in favor of the underlying
> >transmission media providing that service, after all IP is
> >'unreliable'.
>
> I fear I might disagree with that if it were expanded.
Ditto. IIRC, the IP header checksum was removed in v6, but the TCP checksum
was changed to cover the IPv6 header as well. No point in having two weak
checksums when one will catch nearly as many errors and cost much less
processing time in intermediate nodes.
> > TCP is supposed to be more reliable, and does offer an
> >extension mechanism for the basic checksum.
>
> I don't understand that.
Nor do I.
> > The basic checksum also detects different errors from the
> > underlying CRC which is very important.
>
> I mostly agree with that.
It's always useful to have different algorithms to cross-check, but having
the stronger one on the bottom layer means a weaker one on the upper layers
is mostly useless. The TCP checksum only comes into play during periods
where there is no lower-level mechanism.
> > Errors on most modern ethernet networks are neglible.
>
> That has always been true with quality hardware.
And quality cabling and software. However, a large part of the Internet
comprises hardware, software, and cabling of questionable quality.
> The defacto maximum 1500 byte MTU size doesn't push typical
> 32-bit CRCs, FCS, etc. It's probably just as well that jumbo 802
> frames seem to be dead and that the 4K FDDI, 8K TR, and
> other large MTUs are variously dead or used only in fairly
> restricted circumstances.
To me, that's a shame. I've used 9kB MTU in clusters and it makes the
difference between needing TCP offload and not. Being able to send 4kB or
8kB pages at a time (instead of 1460 bytes) is very attractive for shared
memory and remote filesystem access.
> > Cable and Wireless lag behind in this respect since they use
> > shared technology which depends on errors to detect collisions.
>
> That's nonsense technically. "Collsions" are bad only in the ears
> of people with limited technical knowledge and the mavens who write
> the inter-ad filler in the trade rags.
Totally agreed. Collisions are fine, though an excessive number do hurt
performance. I'm unaware of any case where even extreme levels of
collisions cause undetected data errors.
> If your TCP/IP links have a worse than 50% probabilty of one
> wrong bit in a GByte or 10,000,000,000 bits, then you are using
> very bad hardware and probably worse software.
Unfortunately, I'm seeing higher undetected error rates than that (see other
post). While it's difficult to completely rule out bad HW or SW in my home,
Murphy's Law says it'll be somewhere I can't control -- the hundreds of
other users I interact with or the various ISPs between us.
Mack
<ste...@sprunk.org> wrote:
>"Mack" <macckone@a_nospamjunk123_ol.com> wrote in message
>news:f1ld51h6es2a52cpe...@4ax.com...
>> On Thu, 7 Apr 2005 21:33:26 -0500, "Stephen Sprunk"
>> <ste...@sprunk.org> wrote:
>> > According to the paper, clients are supposed to request the sub-
>> > pieces in order from the same peer with 5 requests or so
>> > pipelined to keep TCP busy. There are a few reasons why one
>> > subpiece might be missed in the middle even if the client does
>> > use this model. TCP checksums aren't perfect, andgigabytes
>> > of data are bound to have transient errors. Or a bug at the other
>> > end might drop a request but process ones after it.
>>
>> err .. since the sub-pieces are sent over a TCP connection an error
>> would prevent any more arriving until the error is corrected. TCP
>> passes data up to the application in a strictly sequential order. The
>> only time a loss of order would happen is if the requests are actually
>> sent over a different TCP connection, ie. to a different host.
>
>TCP's checksum is much weaker than a cryptographic hash. When transferring
>multi-GB files over TCP, undetected errors are _expected_, which is why BT
>uses strong hashes on each piece.
>
A much more likely source of errors is data corruption by a bad piece
of equipment. Random errors may happen and even be undetected but
they are by far the least common source of repetitive errors. See my
other response to this thread for the discussion of actual errors
occuring in a production evironment. The 160 bit Hash code is much
stronger than the 32 bit CRC. More importantly is that it prevents
malicious data alteration, which is a very large concern in a P2P
network. A 160 bit CRC would offer more refined random error
detection but would not verify integrity against malicious attack.
The protocol paper indicates that pieces can arrive out of order as a
result of chocking. This has nothing to do with TCP errors. TCP is
ordered delivery. It does have to do with multiple pending requests.
The protocol allows for unorder delivery. A much more likely cause is
requests to different hosts.
>> > Though, going back to the original post, it wouldn't prevent a
>> > peer from deliberately sending bad hashes. The only secure
>> > protection against corruption at the subpiece level reduces to
>> > setting the piece size to the minimum and have only one
>> > subpiece per piece.
>>
>> If all of the sub-piece hashes matched and the piece didn't hash to
>> the torrent value then it is safe to assume the client is deliberately
>> sending bad hashes.
>
>Is there any way to determine the set of sub-piece hashes do not match the
>full piece hash without downloading an entire bad piece?
Not with SHA, hashes that are mathematically based (ie. on factoring
or DL) could solve this problem but I haven't kept up with the
literature in that regard.
Mack
<twist...@gmail.invalid> wrote:
>Mack wrote:
>> Even DSL is good at catching errors. Cable and Wireless lag
>> behind in this respect since they use shared technology which depends
>> on errors to detect collisions.
>
>Netstat -s on my cable-connected system shows no errors (save address
>errors) after hours of heavy p2p usage.
Point acknowledged, but at this point I think we are talking a very
low number of errors. Can you tell how many errors you cable modem
has caught? Or is it capable of providing such information?
Twisted One
> Point acknowledged, but at this point I think we are talking a very
> low number of errors. Can you tell how many errors you cable modem
> has caught? Or is it capable of providing such information?
What, the *modem itself*? It's a box with blinking lights on the floor
by my desk. I don't have access to its internals. It just looks like an
ethernet socket to the computer, and presumably looks like my computer
to the Internet. :)
Mack
(Vernon Schryver) wrote:
>In article <es6i51p7v6147lhmm...@4ax.com>,
>Mack <macckone@a_nospamjunk123_ol.com> wrote:
>
>>IPv6 has removed the IP header checksum in favor of the underlying
>>transmission media providing that service, after all IP is
>>'unreliable'.
>
>I fear I might disagree with that if it were expanded.
>
>> TCP is supposed to be more reliable, and does offer an
>>extension mechanism for the basic checksum.
>
>I don't understand that.
TCP is reliable, ordered delivery of data. As opposed to IP or UDP
which are 'unreliable' and 'unordered'. In RFC 1071 there is an
extension mechanism for the TCP checksum.
>
>> The basic checksum also
>>detects different errors from the underlying CRC which is very
>>important.
>
>I mostly agree with that.
>
>
>>I used to see TCP errors and ethernet errors when using 'bus'
>>technology (hubs, 10base2, 10base5).
>
>That speaks more to the poor quality of a lot of 802.3 hardware
>and worse installation than anything about "buses."
>
>> Errors on most modern
>>ethernet networks are neglible.
>
>That has always been true with quality hardware. The defacto maximum
>1500 byte MTU size doesn't push typical 32-bit CRCs, FCS, etc. It's
>probably just as well that jumbo 802 frames seem to be dead and that
>the 4K FDDI, 8K TR, and other large MTUs are variously dead or used
>only in fairly restricted circumstances.
>
Err ... all of the gigabit equipment we use where I work is capable of
jumbo frames. Some of the newer 100Mbit equipment also handle them,
including some of the NICs. The standard CRC-32 has about the same
error correction capability at 1500 bytes as 9000 bytes, IIRC it
doesn't start degrading till about 11000 bytes or so. There is a
paper on jumbo frames that uses that figure.
>
>>Even DSL is good at catching errors.
>
>There are many things covered by "DSL." Even a single DSL link often
>involves more than one lower layer scheme between routers.
>
When I say DSL I mean the link between the DSLAM and the modem.
They all use FEC based on RS as does cable and wireless. They also
use randomization and interleaving to spread out burst errors.
>> Cable and Wireless lag
>>behind in this respect since they use shared technology which depends
>>on errors to detect collisions.
>
>That's nonsense technically. "Collsions" are bad only in the ears
>of people with limited technical knowledge and the mavens who write
>the inter-ad filler in the trade rags. The nonsense and even lies
>(e.g. from IBM Token Ring and 100VG-AnyLAN salescritters) about the
>non-existent evils of collisions have been a pet peeve of mine since
>the 1980's. (Yes, I know about the Ethernet Capture Effect and
>realize it is related to the CSMA/CD exponential backoff algorithm.)
>
>Those who care about the technical stuff instead of sales blather care
>only about achieved bit and packet error rates. As long as the numbers
>are right, wehther the network relies on wet string is irrelevant.
>
Collisions are not evil in the sense that they are 'bad' in and of
themselves. We are talking decimal points here, at least for cable.
Now wireless is another story, but that isn't just collisions there is
also bad software and interference. With the appropriate level of
error correction, undetected errors should be quite rare.
If the same ECC is used on a CSMA/CD system as a point to point
system, the point to point system will always win assuming everything
else being equal. Since the same ECC chips are used in both cable and
DSL modems, which do you think will have more undetected errors?
One example is given in this very long link.
http://www.xilinx.com/xlnx/xebiz/designResources/ip_product_details.jsp?iLanguageID=1&key=DO-DI-RSD&com.broadvision.session.new=Yes&BV_SessionID=@@@@1678162367.1113179704@@@@&BV_EngineID=cccdaddeflehdhdcflgcefldfhndfmo.0
>If your TCP/IP links have a worse than 50% probabilty of one wrong bit
>in a GByte or 10,000,000,000 bits, then you are using very bad hardware
>and probably worse software.
Cable shoots for about 1e-6 for digital video, so assume they are
shooting for 1e-9 for data (not sure on the data figure), after FEC.
DSL seems to be going for a lower error rate. Obviously this will
depend on line noise, but my experience has been that DSL does better.
Mack
<twist...@gmail.invalid> wrote:
>Mack wrote:
>> Point acknowledged, but at this point I think we are talking a very
>> low number of errors. Can you tell how many errors you cable modem
>> has caught? Or is it capable of providing such information?
>
>What, the *modem itself*? It's a box with blinking lights on the floor
>by my desk. I don't have access to its internals. It just looks like an
>ethernet socket to the computer, and presumably looks like my computer
>to the Internet. :)
Some such devices provide a tool or web interface to examine and/or
set some internal state. Some also provide firewall ability and other
capabilities.
Twisted One
> Some such devices provide a tool or web interface to examine and/or
> set some internal state. Some also provide firewall ability and other
> capabilities.
I take it those come with drivers, or something is detected and
plug'n'prayed automagically? Mine otoh seems to be a fairly dumb
connector between a coaxial cable on one side and an ethernet cable on
the other. Fortunately I have firewalling and other such stuff from
other equipment.
Mack
<twist...@gmail.invalid> wrote:
>Mack wrote:
>> Some such devices provide a tool or web interface to examine and/or
>> set some internal state. Some also provide firewall ability and other
>> capabilities.
>
>I take it those come with drivers, or something is detected and
>plug'n'prayed automagically? Mine otoh seems to be a fairly dumb
>connector between a coaxial cable on one side and an ethernet cable on
>the other. Fortunately I have firewalling and other such stuff from
>other equipment.
My first DSL modem was about like yours but found a tool that could
query the internal state (the phone company had one so I knew it
existed). My second DSL modem had a tool that you could use to
query/set the internal state, and appearently had better error
detection/correction and better reliability. My current one provides a
nifty web interface (kinda cool), firewall (works great once I got it
to allow PPTP, IPSEC/L2TP seem out of the question), IDS/IPS (rather
basic), nat (more flexible than windows 2003), dhcp (one range), WPA
wireless (doesn't play well with others), and the ability to adjust
all of the above settings via the web interface or a provided tool
(windows only).
Vernon Schryver
Stephen Sprunk <ste...@sprunk.org> wrote:
>They do have different design goals: TCP was designed to be cheap in
>software in the 70s, and cryptographic hashes are designed to be strong
>against a wide variety of factors. Sure, cryptographic protection is
>overkill, but AFAIK nobody has developed a non-cryptographic hash that
>protects against the common cases that a checksum (or even CRC) misses.
The data of the TCP design is irrelevant. Cryptographic hashes in
this case are not overkill, but wrong. Cryptographic hashes have very
different design goals from communications checksums. Communications
checksums are designed to do things like swapped bytes, stuck bits,
or bursts of stuck or random bits. Cryptographic hashes are designed
to detect what might be called intentional fiddling.
There are sound reasons why no (reasonable, common) communcations
protocols have ever used cryptographic hashes instead of the various
data error detecting or correcting schemes.
>In the last week, I've downloaded about 15GB of data with BT. There were
>about 20 hash fails on individual 512kB pieces.
20 bad TCP checksums in 15 GBytes of data seems high.
Still, the odds of an undetected error are 1000:1.
>While there are many possible places the data could have been corrupted, the
>weakest link in the chain is TCP's checksum.
Repeating a misunderstanding does not make it right. I'm sorry, but
that is simply wrong.
>> - The primary defenses against TCP (and UDP) data errors are
>> the lower level checksums such as the Ethernet CRC.
>
>That's fine if you assume all errors will be on CRC-protected links and
>detectable. They occur in other places too, and in ways that even CRCs
>won't detect (with low but still nonzero probability).
You say that as if it contradicted my statement. It doesn't. The TCP
checksum is intended to detect errors not detected by the lower level
CRCs, FCSs, and so forth.
>I worked for a router vendor for years, and we had a constant stream of bugs
>related to routers and switches mangling packets in ways that a simple
>checksum could not detect.
I worked for a UNIX vendor for a dozen years and received a constant
stream of reports about data TCP/IP and UDP/IP corruption due to design
and other errors in hardward and software, including my own code. In
none of those cases that I can recall would a stronger transport
checksum have done the least good. A major reason is that most of the
errors happened in parts of the path not protected by the TCP checksum
(and not only because my efforts to move the TCP and UDP checksum
computations out of the main CPUs).
> And then, of course, there's always "alpha
>particle" corruption in fast RAM, which has led the same vendor to switch to
>ECC; several bit errors _per minute_ are detected and corrected, which makes
>me wonder what the real error rates are in non-ECC products.
I wonder why ECC RAM is rare in PCs, but that's all irrelevant.
>While the odds of random bit flips in non-ECC memory resulting in something
>a checksum wouldn't catch is low, it's still undeniably higher than the odds
>of not being caught by a CRC or hash.
I don't understand that sentence, but I doubt that it is relevant.
>Unfortunately, my host (WinXP x64 Edition) does not show the detected error
>rate.
Using such software on the hardware you are probably using makes talk
about a better TCP checksum sound...well...I can't think of a polite
way to say "foolish."
>0.0015% is a lot when you're talking about GBs of data. If the detected
>error rate is 0.01%, that still means there will be 6 undetected errors in a
>4GB file (one DVD). Unacceptable.
>
>There's a reason tools like SFV and PAR exist, as well as why BT and other
>p2p protocols include cryptographic hashes. Even one wrong bit is one too
>many, and TCP isn't getting the job done.
If BT is using cryptographic hashes for ordinary data integrity despite
ordinary noise, bugs, and bit rot, then whoever made that choice should
not have had that job. Cyrptographic hashes are entirely wrong for
detecting ordinary data corruption. You might want a long CRC or
similar instead of the simple TCP checksum. You'd probably want some
kind of error correction scheme to combat bit rot. Merely detecting
bit rot and giving up is like the personal computer RAM with parity
instead of ECC. If the probability of bit rot is high enough to worry
about, then you shouldn't crash the system on a RAM parity error or
retransmit your 0.5 GByte BT block on a checksum error. You should
instead arrange to have enough redundancy in the bit stream to fix
sufficiently likely errors.
However, given the non-technical environment of a lot of Bit Torrent
uses, there are obvious reasons to for BT to use cryptographic hashes.
Many BT users have human adversaries who would love to corrupt the data.
On those grounds alone, a crypto hash is the right choice.
Vernon Schryver v...@rhyolite.com
Vernon Schryver
Mack <macckone@a_nospamjunk123_ol.com> wrote:
>occuring in a production evironment. The 160 bit Hash code is much
>stronger than the 32 bit CRC. More importantly is that it prevents
>malicious data alteration, which is a very large concern in a P2P
>network. A 160 bit CRC would offer more refined random error
>detection but would not verify integrity against malicious attack.
Exactly! Many BT users have human adversaries and a cryptographic
hash is the appropriate choice as a defense against their data
corruption.
Against simple bit rot in RAM, wires, fiber, CPUs, buses, other
hardware, software, and so forth, there are far better choices than
any cryptogrpahic hash.
Vernon Schryver v...@rhyolite.com
Vernon Schryver
Stephen Sprunk <ste...@sprunk.org> wrote:
>> The defacto maximum 1500 byte MTU size doesn't push typical
>> 32-bit CRCs, FCS, etc. It's probably just as well that jumbo 802
>> frames seem to be dead and that the 4K FDDI, 8K TR, and
>> other large MTUs are variously dead or used only in fairly
>> restricted circumstances.
>
>To me, that's a shame. I've used 9kB MTU in clusters and it makes the
>difference between needing TCP offload and not.
Only if your hardware and software is lame or ancient.
There was a time when 4KBytes was a magic number for packet sizes.
Years before, the magic number was 512, and hence the BSD "trailer
protocol." Today the magic numbers are larger than any reasonable
frame size.
> Being able to send 4kB or
>8kB pages at a time (instead of 1460 bytes) is very attractive for shared
>memory and remote filesystem access.
Again, that's true only if your hardware or software are lame or
ancient. Note that I say that as the guy who made TCP/IP/FDDI and
UDP/IP/FDDI go faster than anybody else for a while thanks to page
flipping. Modern page sizes are (or should be) larger than 8KBytes if
only to limit the sizes sizes of page tables. It is as silly today
to have 32 GByte of RAM divided into 8KByte pages as it was 15 years
ago to have have 512 Byte or 1 KByte pages...well, at least for
data if not for code.
>Unfortunately, I'm seeing higher undetected error rates than that (see other
>post). While it's difficult to completely rule out bad HW or SW in my home,
>Murphy's Law says it'll be somewhere I can't control -- the hundreds of
>other users I interact with or the various ISPs between us.
In that case, you don't need cryptographic hashes, but some usable
redundancy in the bit stream. Besides the familiar ECC polynomials,
over the years people have done things like making the stream naively
stutter and repeat itself. Look at Digital Fountain.
Would you really recommand to NASA that a 160 bit crypto hash would
be a better way to get data from Saturn or Mars?
Vernon Schryver v...@rhyolite.com
David Wagner
>If BT is using cryptographic hashes for ordinary data integrity despite
>ordinary noise, bugs, and bit rot, then whoever made that choice should
>not have had that job. Cyrptographic hashes are entirely wrong for
>detecting ordinary data corruption.
I don't understand why you would say that. There is nothing wrong with
using a cryptographic hash for ordinary data integrity.
Crypto hashes may be overkill for this purpose, but what is wrong with
overkill? Personally, if it was my data, I'd rather have an engineer
who errs on the side of robustness and overkill, rather than erring on
the side of undetected data corruption.
David Wagner
>Against simple bit rot in RAM, wires, fiber, CPUs, buses, other
>hardware, software, and so forth, there are far better choices than
>any cryptogrpahic hash.
Can you name one that is better, in any way other than performance?
(Did you know that one some platforms, MD4 is faster than a CRC hash?)
D. J. Bernstein
> Cyrptographic hashes are entirely wrong for
> detecting ordinary data corruption.
No, they aren't.
It's true that traditional error correction shouldn't be _eliminated_ by
strong cryptographic authenticators. There are many transmission errors,
and traditional error correction eliminates most of those errors much
more efficiently than a strong cryptographic authenticator.
Traditional error correction should, however, be _reduced_ in the
presence of strong cryptographic authenticators. The most efficient
strategy is to use a small error-correction code to bring the error rate
down to, say, one in a thousand packets. That would be a completely
unacceptable error rate without the authenticators, but we can rely on
the authenticators to catch the remaining errors, and we can rely on a
higher-level retransmission protocol to fix the remaining errors.
Yes, it's a waste of time to be constantly retransmitting and
reauthenticating bad packets. But it's also a waste of time to reduce
the random-error rate to, say, one in 10^12 packets. There's an optimum
amount of error correction---and, at that optimum, cryptography _does_
catch some random errors that slip past the error-correcting codes.
---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago
Vernon Schryver
David Wagner <daw-u...@taverner.cs.berkeley.edu> wrote:
Beware of the hammer maker's syndrome that sees all of the world as a nail.
When it comes to error recovery, you are spending bits of redundancy
and CPU cycles to reduce the probability of uncorrected errors. You
are not really interested in knowing that your adversary is trying to
interfer. You also value getting the data through the channel. So
let's say you want to spend some redundancy and cycles on reducing the
error rate in a channel. Which is likely be a better expenditure for
those redundant btis and CPU cycles, a cryptographic hash or something
else?
You surely have a pretty good idea of the kinds of errors you want to
detect and correct (perhaps with retransmissions). Are any of the
crypto hashes going to do well at detecting every burst of N bad bits,
X% uniformly distributed individual bad bits, swapped bytes, bytes
appended to packets or whatever kind of error you care about?
Are you going to inform me that any of the currently known crypto hashes
are so characterized in such terms? I thought that they are all
designed to make computing inverses difficult. Ease incomputing
inverses is often one the primary design goals of many non-crypto error
detection schemes.
Vernon Schryver v...@rhyolite.com
Vernon Schryver
David Wagner <daw-u...@taverner.cs.berkeley.edu> wrote:
>>Against simple bit rot in RAM, wires, fiber, CPUs, buses, other
>>hardware, software, and so forth, there are far better choices than
>>any cryptogrpahic hash.
>
>Can you name one that is better, in any way other than performance?
I think so, but first tell me what kind of errors you care about so I
can take a stab finding someone who knows about the stuff to ask.
>(Did you know that one some platforms, MD4 is faster than a CRC hash?)
Anyone says that is either talking about a long CRC or is ignorant of
the fast ways to compute short CRCs. There's also some question about
whether the speaker is a software jock (I am) who wants to get laughed
out of hardware designers' offices. What makes sense in software is
often nonsense when you're talking about gates, and vice versa.
Say you care about detecting absoluty every burst of 256 bad bits in
any packet of 1460 bytes that otherwise has no errors? What about two
bad cache lines. What about detecting any 1460 byte packet that has
at most 5 randomly distributed toggled bits? Has MD4 or any crypto
hash been characterized in such terms?
Worrying about corrupted strings of bits of is important in many
real cases, from multi-process cache coherence bugs to the canonical
communications line "drop out."
I'll agree that if you have no idea about the errors you want to catch
and know nothing about fire codes and so forth, then a crypto hash is
probably a better choice than something like a 160-add-with-rotate.
If the design target is merely the usual vacuous Usenet jabbering
instead of serious designing, then I'll shut up.
Vernon Schryver v...@rhyolite.com
David Wagner
>When it comes to error recovery, you are spending bits of redundancy
>Which is likely be a better expenditure for
>those redundant btis and CPU cycles, a cryptographic hash or something
>else?
Not clear. A cryptographic hash may well do better against some kinds
of errors; a CRC may do better against others.
But if you have CPU cycles and bits to spare, then a hash function seems
eminently reasonable. For instance, if we are defining a file format for
some large archive to be stored on disk, a cryptographic hash seems like
a reasonable choice. Disk is cheap, and you can hash faster than you can
read data from disk.
>You surely have a pretty good idea of the kinds of errors you want to
>detect and correct (perhaps with retransmissions).
Not necessarily.
>Are any of the
>crypto hashes going to do well at detecting every burst of N bad bits,
>X% uniformly distributed individual bad bits, swapped bytes, bytes
>appended to packets or whatever kind of error you care about?
They are going to do just fine, as long as the hash output has enough
bits. That is the great thing about crypto hashes -- I know that they
will defend *against* all crazy error models.
In comparison, one cannot say the same about simpler hashes, like
Fletcher checksums or CRCs.
David Wagner
>Say you care about detecting absoluty every burst of 256 bad bits in
>any packet of 1460 bytes that otherwise has no errors? What about two
>bad cache lines. What about detecting any 1460 byte packet that has
>at most 5 randomly distributed toggled bits? Has MD4 or any crypto
>hash been characterized in such terms?
Yup, a crypto hash will detect all of these.
If any of these errors gets past your crypto hash, then you have
found a collision. Claim your fame.
I can't understand why anyone would spend time worrying about the
possibility that nature might happen, by chance, to come up with a
collision for a crypto hash function.
Look at it this way. If you use a CRC, the most likely failure
mode is that some error mode occurs that you didn't anticipate (and
in that case, the CRC checksum can fail spectacularly, even though the
crypto hash would have worked fine). That failure mode is *vastly* more
likely than the chance that nature stumbles across a collision in SHA1.
Andrew Swallow
> Vernon Schryver wrote:
[snip]
>>You surely have a pretty good idea of the kinds of errors you want to
>>detect and correct (perhaps with retransmissions).
>
>
> Not necessarily.
The errors that got past the CRC check.
Andrew Swallow
Vernon Schryver
David Wagner <daw-u...@taverner.cs.berkeley.edu> wrote:
>>You surely have a pretty good idea of the kinds of errors you want to
>>detect and correct (perhaps with retransmissions).
>
>Not necessarily.
Yes, necessarily unless one is just doing Usenet hand waving, which
is a step below academic (in the pejorative sense) of that word.
>>Are any of the
>>crypto hashes going to do well at detecting every burst of N bad bits,
>>X% uniformly distributed individual bad bits, swapped bytes, bytes
>>appended to packets or whatever kind of error you care about?
>
>They are going to do just fine, as long as the hash output has enough
>bits. That is the great thing about crypto hashes -- I know that they
>will defend *against* all crazy error models.
>
>In comparison, one cannot say the same about simpler hashes, like
>Fletcher checksums or CRCs.
What are you talking about? CRCs are known to detect N bit errors
in a block of M bits, where N depends on the CRC polynomial.
Which crypto hash is known to detect all N bit errors in in a block
of M bits, for any N>1, and M>8000?
Vernon Schryver v...@rhyolite.com
Vernon Schryver
David Wagner <daw-u...@taverner.cs.berkeley.edu> wrote:
>>Say you care about detecting absoluty every burst of 256 bad bits in
>>any packet of 1460 bytes that otherwise has no errors? What about two
>>bad cache lines. What about detecting any 1460 byte packet that has
>>at most 5 randomly distributed toggled bits? Has MD4 or any crypto
>>hash been characterized in such terms?
>
>Yup, a crypto hash will detect all of these.
I don't keep up on the literature, so feel free to point out a paper
that proves any of those properties for any crypto hash. Which crypto
hash has been proven to handle even the simpliest case of detect all
single bit changes in a fixed size block? Actually I wouldn't be
surprised at that very simple result, although I would be impressed.
What about N-bit bursts that are the meat and potatoes of CRCs, FCS,
and so forth?
>If any of these errors gets past your crypto hash, then you have
>found a collision. Claim your fame.
That statement is not worthy of you. For one thing, if you can detect
that an error has gotten past whatever integrity check you use, then
you should be using whatever you use to do the detecting instead of
the integrity check.
>I can't understand why anyone would spend time worrying about the
>possibility that nature might happen, by chance, to come up with a
>collision for a crypto hash function.
>
>Look at it this way. If you use a CRC, the most likely failure
>mode is that some error mode occurs that you didn't anticipate (and
>in that case, the CRC checksum can fail spectacularly, even though the
>crypto hash would have worked fine). That failure mode is *vastly* more
>likely than the chance that nature stumbles across a collision in SHA1.
Are you the David Wagner of Berkeley? If so, what happened to you
to cause you to say such things?
Yes, as I agreed, if you're certified clue free, then a crypto hash
is not a bad choice. But if you already have an N-bit CRC and you
want to spend another M bits of redundancy, and you are designing
instead of netnews blathering, how do you spend those N bits? Why
would 160 bits of crypto hash added to the TCP 16-bit sum and 32-bit
link layer CRC be a better choice than a CRC-128?
You are essentially claiming that because it is hard to find A and B
such that H(A)=H(B), therefore H is a good error detector. Or perhaps
you are claiming that magic crypto pixie dust causes one mapping from
a set 2**11680 things to a set of 2**160 (or 128 or 256 or whatever)
to have fewer collisions than other mappings.
By your apparent reasoning, any mapping is as good as any other for
communications error detection, so there's no reason to prefer anything
to a simple 160-bit sum. Don't talk claiming fame. Say why I should
believe that any particular hash is better at detecting N-bit errors
than another. (I trust know you enough of finite fields to know why
it is trivial to say such things about CRCs.)
Vernon Schryver v...@rhyolite.com
David Wagner
>Yes, necessarily unless one is just doing Usenet hand waving, which
>is a step below academic (in the pejorative sense) of that word.
I disagree. I think it many cases (particularly ones where data
integrity has a high importance) it may be useful to protect against
failure modes that we may not have anticipated. Isn't this part of
what robustness is all about?
I continue to believe that choosing a more-robust primitive instead
of a less-robust primitive is not a firing offense. I continue to object
to the suggestion that anyone who chooses a crypto hash for data integrity
should lose their job.
>>They are going to do just fine, as long as the hash output has enough
>>bits. That is the great thing about crypto hashes -- I know that they
>>will defend *against* all crazy error models.
>>
>>In comparison, one cannot say the same about simpler hashes, like
>>Fletcher checksums or CRCs.
>
>What are you talking about?
Let me explain what I am talking about.
For crypto hash, I can say this (with high degree of confidence):
"The crypto hash will protect against all kinds of naturally-occurring
errors, including error models that I haven't anticipated, even very
crazy error models that I would never have imagined."
I cannot say the same thing if you replace "crypto hash" by CRC.
CRCs are great if the error model occurred in deployment is exactly
the same as what was expected at design time. But if those two diverge,
CRCs can fail in arbitrarily horrible ways.
In comparison, crypto hashes exhibit more graceful degradation in case
the actual error model deviates from what was expected. In some contexts,
this may well be a useful property.
I still say that the use of crypto hashes for data integrity is
defensible in some circumstances. I say that context matters. And
I say that it is unreasonable to make blanket claims that any engineer
who uses a crypto hash for data integrity should lose her job.
David Wagner
>But if you already have an N-bit CRC and you
>want to spend another M bits of redundancy, and you are designing
>instead of netnews blathering, how do you spend those N bits?
As I pointed out in some of my earlier
``netnews blathering'', in some contexts bits are cheap.
In those contexts, crypto hashes may well be a perfectly fine
choice.
Example: A file format for high-value 1MB records on disk.
Disk space is nearly free; the cost of a 128-bit checksum is negligible.
Note carefully: I am not suggesting that a crypto hash is the right
answer in all contexts. I am saying that there exist some contexts
where use of a crypto hash is defensible.
Regarding your technical questions:
>You are essentially claiming that because it is hard to find A and B
>such that H(A)=H(B), therefore H is a good error detector.
Yes, that is correct.
>By your apparent reasoning, any mapping is as good as any other for
>communications error detection, so there's no reason to prefer anything
>to a simple 160-bit sum.
No, that does not follow.
(For instance, if checksum bits are precious, then a map with short
outputs may be a better choice than a map with long outputs, all else
being equal. It all depends on context.)
Vernon Schryver
David Wagner <daw-u...@taverner.cs.berkeley.edu> wrote:
>>Yes, necessarily unless one is just doing Usenet hand waving, which
>>is a step below academic (in the pejorative sense) of that word.
>
>I disagree. I think it many cases (particularly ones where data
>integrity has a high importance) it may be useful to protect against
>failure modes that we may not have anticipated. Isn't this part of
>what robustness is all about?
>
>I continue to believe that choosing a more-robust primitive instead
>of a less-robust primitive is not a firing offense. I continue to object
>to the suggestion that anyone who chooses a crypto hash for data integrity
>should lose their job.
It depends on the job. Choosing the best possible hammer when the
task calls for a screwdriver should be a career limiting move.
perhaps the problem is that you are talking about spending fewer than
500 bits of redundancy on a message of GBytes to detect unspecified,
even unspecifiable errors, while I'm talking well characterized errors
in messages of 1 or 2 KBytes.
I agree that in the first case, a total message checksum ought to be
as different as possible from the seperate CRCs etc. done on each of
the millions of separate segments that comprise the message. Since
the only somewhat well studied, plausibly uniform family of hashes
other than CRCs and so forth are crypto hashes, I agree that a crypto
hash is good choice for a total message integrity check. At 160 bits
per extra out of 10^10 bits, why not use several (modulo CPU cycle
costs)?
>>>They are going to do just fine, as long as the hash output has enough
>>>bits. That is the great thing about crypto hashes -- I know that they
>>>will defend *against* all crazy error models.
>>>
>>>In comparison, one cannot say the same about simpler hashes, like
>>>Fletcher checksums or CRCs.
>>
>>What are you talking about?
>
>Let me explain what I am talking about.
>
>For crypto hash, I can say this (with high degree of confidence):
> "The crypto hash will protect against all kinds of naturally-occurring
> errors, including error models that I haven't anticipated, even very
> crazy error models that I would never have imagined."
>I cannot say the same thing if you replace "crypto hash" by CRC.
That is not a worthy statement unless you can formalize "high degree
of confidence." Not knowing how to invert MD5 with fewer than X
operations does not qualify. Ignorance of how to do things can a good
thing when you're dealing with people, as in cryptography. It's
otherwise elsewhere.
>CRCs are great if the error model occurred in deployment is exactly
>the same as what was expected at design time. But if those two diverge,
>CRCs can fail in arbitrarily horrible ways.
>
>In comparison, crypto hashes exhibit more graceful degradation in case
>the actual error model deviates from what was expected.
I suspect that statement is true, but I cannot see how to start to
prove it. That no one knows despite plenty of trying that a crypto
hash doesn't have a stupid vulnerablity comparable to the holes in
hash functions defined by taking the remainder modulo a composite does
not make it so. I might bet something I really care about on the
Riemann Hypothesis; not so that SHA-whatever can't be broken.
Your position reminds me of state of the art in psuedo-random number
generators 30 or 40 years ago before Knuth and friends. That current
crypto hash functions seem to be good does not make them so, any more
than the arbitrary mixtures of sundry machine code operations made the
old PRNGs good.
> In some contexts,
> this may well be a useful property.
Yes, but only to the extent you know it is true.
> I still say that the use of crypto hashes for data integrity is
> defensible in some circumstances. I say that context matters. And
> I say that it is unreasonable to make blanket claims that any engineer
> who uses a crypto hash for data integrity should lose her job.
Ok, how about this: Anyone who propose using a crypto hash function
instead of the TCP checksum or a link layer FCS, CRC, etc. should be
re-assigned on grounds of ignorance of and disinterest in the design
constraints and of the strengths and weaknesses of crypto and other
hash functions.
I remain shocked and horrified by what can only be described as
superstitious awe for crypto hashes from people who should know better.
That a function has the property that it is hard, given A to find B
such that H(A)=H(B), has less than nothing to do with detecting errors
that are in some sense uniform. It is less than nothing because the
opposite feature of easy inversion is the foundation of forward error
correction. Imagine an error correcting scheme where given the hash
value and the bad bits, you can't guess the right bits before the heat
death of the universe. Hard-to-invert is a valuable property, but it
is not the only way to evaluate hash functions.
Vernon Schryver v...@rhyolite.com
Joe Peschel
news:d3fb64$1pv6$1...@calcite.rhyolite.com:
> Yes, necessarily unless one is just doing Usenet hand waving, which
> is a step below academic (in the pejorative sense) of that word.
>
What do you think is the pejorative sense of that word?
J
--
__________________________________________
When will Bush be tried for war crimes?
"Our enemies are innovative and resourceful, and so are we. They
never stop thinking about new ways to harm our country and our
people, and neither do we." --G. W. B.
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
David Wagner
>It depends on the job. Choosing the best possible hammer when the
>task calls for a screwdriver should be a career limiting move.
Bingo! I agree with the highlighted statement above.
And for some jobs, a crypto hash is a reasonable choice of tool.
>>For crypto hash, I can say this (with high degree of confidence):
>
>That is not a worthy statement unless you can formalize "high degree
>of confidence."
I can partially formalize it in the following way: the degree of
confidence is at least as high as one's degree of confidence that SHA1 is
collision-resistant. Now, I certainly do not have a mathematical proof
that SHA1 is collision-resistant. However, mathematical proofs are not
the only way to get a high degree of confidence. Sure, I would much
rather have a mathematical proof, given the option -- but it is also
true that there are other forms of evidence.
If the unproven aspect is problematic, one option might be to concatenate
N bits of CRC hash and M bits of crypto hash.
But I also think there are many contexts where the unproven aspect is
not a showstopper. When we talk about error models -- e.g., bursts of
256 erroneous bits -- no one ever proves mathematically that those error
models are a faithful model of reality, or that those kinds of errors
are the only kinds of errors possible. Why should we accept unproven
error models, but categorically reject unproven hashes? Wouldn't that
be a double standard? I think the issue is not as cut-and-dried as that.
>That a function has the property that it is hard, given A to find B
>such that H(A)=H(B), has less than nothing to do with detecting errors
>that are in some sense uniform.
If a function is collision-resistant, then resists collisions
due to uniform-random errors (as well as many other kinds of errors).
"Less than nothing" is an overstatement.
I agree that collision-resistance is not sufficient for 'error correction'.
But for 'error detection'? Collision-resistance certainly seems relevant
to error detection.
D. J. Bernstein
> Actually I wouldn't be surprised at that very simple result, although
> I would be impressed.
Prepare to be impressed: One of the standard ways to build a strong
cryptographic authenticator is as an AES-encrypted 128-bit CRC using a
secret polynomial. This has all the guarantees of a CRC---including the
minimum-distance guarantees, if you put the appropriate restrictions on
the choice of polynomial---_plus_ protection against clever forgeries.
(CRC-AES authenticators aren't the state of the art: high-characteristic
authenticators with similar properties are much faster. In particular,
Poly1305-AES produces a cryptographically strong 128-bit authenticator
in just a few cycles per byte. See http://cr.yp.to/mac.html.)
Evidently you thought that there was some much larger gap between the
cryptographically strong solution and the non-cryptographic solution.
There isn't. The cryptographic solution has a size requirement (128
bits), and is encrypted; those are the only differences.
As I said before, non-cryptographic error-correcting codes still have a
place: they're the best way to reduce the error rate down to, say, 1
packet in 1000. But one can, and should, rely on strong cryptographic
authenticators to catch the remaining errors. The authenticators are
needed anyway, and letting them handle an occasional error is more
efficient than using a larger non-cryptographic error-correcting code.
Vernon Schryver
D. J. Bernstein <d...@cr.yp.to> wrote:
>Prepare to be impressed: One of the standard ways to build a strong
>cryptographic authenticator is as an AES-encrypted 128-bit CRC using a
>secret polynomial. This has all the guarantees of a CRC---including the
>minimum-distance guarantees, if you put the appropriate restrictions on
>the choice of polynomial---_plus_ protection against clever forgeries.
>
>(CRC-AES authenticators aren't the state of the art: high-characteristic
>authenticators with similar properties are much faster. In particular,
>Poly1305-AES produces a cryptographically strong 128-bit authenticator
>in just a few cycles per byte. See http://cr.yp.to/mac.html.)
>
>Evidently you thought that there was some much larger gap between the
>cryptographically strong solution and the non-cryptographic solution.
>There isn't. The cryptographic solution has a size requirement (128
>bits), and is encrypted; those are the only differences.
>
>As I said before, non-cryptographic error-correcting codes still have a
>place: they're the best way to reduce the error rate down to, say, 1
>packet in 1000. But one can, and should, rely on strong cryptographic
>authenticators to catch the remaining errors. The authenticators are
>needed anyway, and letting them handle an occasional error is more
>efficient than using a larger non-cryptographic error-correcting code.
Ok, I'm convinced.
Vernon Schryver v...@rhyolite.com
Michael Amling
>
> Prepare to be impressed: One of the standard ways to build a strong
> cryptographic authenticator is as an AES-encrypted 128-bit CRC using a
> secret polynomial.
From whom does this polynomial need to remain secret? In the
application under discussion, I presume at least the originator of the
.torrent file would need to know it. Don't all the peers need to know
the secret polynomial in order to verify received pieces?
And who has to know the AES key?
> This has all the guarantees of a CRC---including the
> minimum-distance guarantees, if you put the appropriate restrictions on
> the choice of polynomial---_plus_ protection against clever forgeries.
--Mike Amling
D. J. Bernstein
> Don't all the peers need to know
> the secret polynomial in order to verify received pieces?
Yes, that's how cryptographic message authentication works. The secret
is efficiently shared through, e.g., elliptic-curve Diffie-Hellman.
Mack
<d...@cr.yp.to> wrote:
>Michael Amling wrote:
>> Don't all the peers need to know
>> the secret polynomial in order to verify received pieces?
>
>Yes, that's how cryptographic message authentication works. The secret
>is efficiently shared through, e.g., elliptic-curve Diffie-Hellman.
If all of the peers know the secret allowing them to produce and/or
verify the pieces. How does this defend against a malicious peer?
We are talking P2P here. Everyone has to be able to verify and
produce.
>
>---D. J. Bernstein, Associate Professor, Department of Mathematics,
>Statistics, and Computer Science, University of Illinois at Chicago
Leslie 'Mack' McBride
Michael Amling
> Michael Amling wrote:
>
>>Don't all the peers need to know
>>the secret polynomial in order to verify received pieces?
>
>
> Yes, that's how cryptographic message authentication works. The secret
> is efficiently shared through, e.g., elliptic-curve Diffie-Hellman.
That makes it more like a MAC than a hash. While the thread has
characteristically drifted away from the original topic, the OP's threat
model included a malicious peer. Replacing the SHA-1 hashes of the
current BT protocol with AES-encrypted 128-bit CRC's would make the
legit peers vulnerable to malicious peers who, knowing the polynomial,
would be able to send fake pieces whose MACs would match the expected
MACs because they differ from the true pieces by a multiple of the CRC
polynomial, a worse outcome than the DoS the original poster was worried
about.
I think the OP's posited DoS attack can be defended against without
changing the protocol only by using smaller pieces. The current trusted
.torrent file format does not include information that would allow
validating sub-pieces. I presume the OP is looking for a space-efficient
cryptographically strong method for validating the sub-pieces, for
incorporation in a future version of the protocol.
--Mike Amling
D. J. Bernstein
> the OP's threat model included a malicious peer
The great thing about attackers is that there are so many to choose from!
You should be using
* a small non-cryptographic error-correcting code between the peers
as the most efficient way to reduce the random error rate to, say,
one in a thousand packets;
* a strong cryptographic authenticator as the most efficient way to
eliminate forgeries by anyone on the network between the peers (and
to clean up the remaining random errors); and
* a signature from the original source of the data as the only way to
catch forgeries by the middlemen.
I was commenting solely on the balance between the first two stages; I
didn't mean to suggest that they were the only stages.
Hans Fleischmann
> On Tue, 12 Apr 2005 17:56:54 +0000 (UTC), "D. J. Bernstein"
><d...@cr.yp.to> wrote:
>
>>Michael Amling wrote:
>>> Don't all the peers need to know
>>> the secret polynomial in order to verify received pieces?
>>
>>Yes, that's how cryptographic message authentication works. The secret
>>is efficiently shared through, e.g., elliptic-curve Diffie-Hellman.
>
> If all of the peers know the secret allowing them to produce and/or
> verify the pieces. How does this defend against a malicious peer?
> We are talking P2P here. Everyone has to be able to verify and
> produce.
Assuming Bittorrent: You get the hash from the (trusted) .torrent, not
from the peer.
Hans
anthonyberet
> "Andrew Swallow" <am.sw...@btopenworld.com> wrote in message
> news:d30dsp$8kn$1...@titan.btinternet.com...
>
>>Skybuck Flying wrote:
>>[snip]
>>
>>>Good point.
>>>
>>>Question:
>>>
>>>Why are sub pieces downloaded from multiple clients ? Why not simply one
>>>client ?
>>>
>>>That would solve it.
>>>
>>
>>ISP supply users with different transmission and reception speeds. The
>>general public can receive download much faster than they can send.
>>Several clients are needed to receive at top speed.
>
>
> Clients can download multiple pieces at the same time this should be enough
> to receive at top speed so why split the pieces further into sub pieces ?
>
> I think in the end splitting it into sub pieces is probably inefficient:
>
> 1. more protocol overhead for sub piece information/negotiation ?
> 2. tcp needs some time to get at top speed... having to restart all the time
> doesnt seem that wise ;)
>
> What are benefits for sub pieces ?
>
> 1. Maybe faster switching to different clients etc. Not necessarly faster
> sharing since a complete piece has to be received first to check if the
> piece was received correctly... unless one doesnt care about that and simply
> uploads possible corrupted sub pieces etc ;)
>
Don't forget the size of the pieces in a torrent can be defined when
generating the .torrent file.
anthonyberet
> Stephen Sprunk wrote:
>
>> Same for the one I'm reading, at least in the .torrent file. Perhaps
>> once a
>> piece is started, the sender directly transmits hashes of the
>> subpieces to
>> the receiver? See below on why I think this may happen.
>
>
> This would suck. If we assume the sender of subpieces is untrusted, then
> the hash they send is untrusted. It will match the data, even if the
> data is bogus and the big piece will hash-fail, just so they can't be
> fingered as the bad node, and so the downloader has to get the whole
> piece again and not just the bad subpiece.
>
Tut! - the HASH is in the .torrent file, which are usually to be trusted.
Joseph Ashwood
isn't on topic either.
"anthonyberet" <nos...@me.invalid> wrote in message
news:3nddn1...@individual.net...
>>>>Why are sub pieces downloaded from multiple clients ? Why not simply one
>>>>client ?
Sub pieces are there under the assumption that disk reads are expensive and
more small disk reads will actually be more efficient in the highly
distributed setting than fewer large disk reads. Whether or not this is true
at typical bittirrent sizes is debatable is open to debate, but
asymptotically it will be true. The other occassion where the sub pieces
come into play is in the end game, where when only a certain small number of
pieces is left the ability to request from multiple sources diminishes very
quickly. As the sub pieces are available the distributed nature can be
accelerated to much closer to the file complete state. This in effect
reduces the end game overhead which can become very high. For example in
large swarms it is not necessarily bad form to request the last piece from
16 different peers, in a monolilthic sub piece form this is 16*piece size,
since pieces are generally on the order of 256KBytes this represents a
download of 4MB for the last 256KB, not exactly efficient, and with growing
swarms we are beginning to see where it could be considered acceptable from
a download perspective to download from in the neighborhood of 100 different
peers. By creating the sub piece it becomes possible to shrink the example
from 4MB to 1/4MB. The downside, as noted by others I'm certain, is that the
protocol does have some extra overhead. Since I actually have a client
running right now I can tell you that the current overhead it is receiving
is 0.9%, assuming a CD sized average download (640MB for simplicity), and a
256KB piece size eliminating the sub pieces would save 5.4MB worth of
download, while in a large swarm it would save >10MB in the end game, making
the overhead a multi-megabyte benefit on each download, multiple the benefit
by the large swarm size and the swarm has saved GBs worth of transfer.
>>>>That would solve it.
In fact during the meaty times of the download that is very typical, because
BitTorrent uses HTTP to perform the actual transfers you will see a number
of optimizations in the requests.
>> 1. more protocol overhead for sub piece information/negotiation ?
Sub piece information is not distributed. This is due to the fact that sub
pieces are not hashed and verified, and there is a very specific provision
against uploading a piece that has not been verified.
>> 2. tcp needs some time to get at top speed... having to restart all the
>> time
>> doesnt seem that wise ;)
It's actually not restarted, the connection remains open and a series of
HTTP requests are sent over it.
>> 1. Maybe faster switching to different clients etc. Not necessarly faster
>> sharing since a complete piece has to be received first to check if the
>> piece was received correctly... unless one doesnt care about that and
>> simply
>> uploads possible corrupted sub pieces etc ;)
> Don't forget the size of the pieces in a torrent can be defined when
> generating the .torrent file.
That they can, but the shift from a 256KB piece to the requisite 16KB piece
would create a 16x increase in the size of the torrent file itself which
begins to move the burden out of the swarm and back onto the assumedly HTTP
server that is used for the torrent file. In fact there is a movement within
the BitTorrent community to move to an embedded Merkle tree reducing the
torrent file down to the size of a URL, and there is a notable amount of
evidence that this can substantially improve performance.
Now, why was sci.crypt added to this? Was it just so you could get me to
reply? If you had asked the same question on the BitTorrent discussion list
you would've gotten answers that are equally qualified.
Joe
Andrew Swallow
[snip]
>
> Now, why was sci.crypt added to this? Was it just so you could get me to
> reply? If you had asked the same question on the BitTorrent discussion list
> you would've gotten answers that are equally qualified.
As a guess, sci.crypt was added because if large
organisations like the BBC and the Hollywood studios
use Bittorrent to download programmes then they will
want to encrypt the file. They can then charge you
for the key variable needed by your player to
decrypt the file. The key variable can be
personalised by encrypting it using the subscribers
public key.
Andrew Swallow
Joseph Ashwood
Actually we had a discussion about this on sci.crypt a while ago. Basically,
as they stand now no p2p architectures can support secure DRM (although some
group DRM designs might work, haven't looked to closely). To support good
DRM that doesn't require only the leaking of a single key requires an
architecture change. The methods that came to mind before and still come to
mind now are transferring the first block in a client-server architecture so
the first block can be modified in any number of different ways, and having
k*n blocks where only n blocks are needed, this allows different blocks to
have different keys and gives a lot of room to roam to find something
secure. I can cover either of them in more detail, but I doubt the inner
workings would be all that interesting to most of the people reading.
Joe