The fifth Free and Open source Software Developers' European Meeting is a 2 days event, organized by volunteers, to promote the widespread use of Free and Open Source software. Taking place in the beautiful city of Brussels, Belgium, FOSDEM meetings are recognised as the best Free and Open Source events in Europe.
This fifth edition will take place at the same location (in the ULB) on the Feb 26 & 27 Feb 2005.
I might be misreading it, or misremembering, but it resembles tiger tree hash, only with MD5. With the right block size, this might catch the doppelganger blocks.
Hm. The doppelganger blocks were 64 bytes long. That would require even tinier blocks to catch. Storing or passing along the complete tree could take more room than the original.
they only hash parts of the file to save timefreaking stupid...
The older Kazaa only did the first part of the file. Looking at the docs in the parent post, the newer one does the whole file. It looks a little like what I remember of the tiger tree hash idea.
If you and I are remembering the same thing, that was under a different attack. IIRC, that wasn't even an attack on the hash, but just on the way that fingerprints were generated.
I think you're right. I was trying to work out where you were coming from.
Yes, although many legacy keys are still around-- mostly because people kept using PGP 2.6.2 for so long. My keyring is 10% legacy keys.
Oh. That's not good. I should have known that people would still be using old versions, and/or overriding the suggested expiration dates...
So. The key signing mechanism for RSA keys uses the MD5 hash. And RSA got included with GnuPG 1.0.3.
Looking around, there's someone who still recommends PGP 2.6 because the source code is smaller, so easier to audit.
You know that GPG keys are identified and signed by their MD5 hashes?
I vaguely remember that the short key ID used a flimsy hash, but to avoid that you only had to verify the key length. Looking around, MD5 looked dubious in 1997, and alternatives - like SHA1 and RIPEMD-160 - got incorporated to PGP. So. I don't buy this. PGP.com knows about it.
The intuitive short-term solution, at least to me, is to use N different MD5sums for each file, taken at N different offsets within the file (each unique mod block size).
It won't do the offset thing, but tiger tree hashing uses blocks, and combines them into another checksum. If the blocks were small enough, they'd catch this. I'm not sure about the block size involved in either, though; I suppose with a bit more CPU, you could get arbitrarily small blocks.
Somebody could use these fake files to "poison" popular torrents, making it very unlikely that anybody on them will get uncorrupted files.
This would worry me, except that BT uses SHA1, not MD5, so this is irrelevant. MD5 has seemed suspect for years, & Bram's the sort to pay attention to that sort of thing.
I checked; Edonkey is based on MD4. Gnutella variants might use MD5.
How can I help get the signatures for that crap added into an anti-spyware program? (That's partially about the guy who went to one site & got hit by much spyware. It might be nice to follow his lead, then be able to help others who have done that without realizing what would happen.)
When an attempt to reinstall Windows overwrote a Linux partition, I made a script to compare the fsck-recovered files & directories to a Tripwire database.
Nothing irreplaceable was lost, & only a few files - 5% or so? - lost information.
That's where you represent primality or lack of it by setting and clearing bits of an integer. Working out the mask for those bit operations can take enough time to cancel out the space benefits. I think you could optimize the different masks & their steppings.
... there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes. I tried this, but I don't know where that program is now. I used 0 as an escape code, allowing me to either note the next delta in hex, or else the current number, to detect errors. I only did this for output, though.
I could see that being effective for the trial factor prime number table, too.
Oh, and the nfsnet thing that's your homepage is cool.
There's a primes program in (uh, on Debian) the bsdgames package; if memory serves, it does the wheel thing suggested.
A suggestion for the article: If the trial factor prime number table gets big enough to swap (either out of cache, or out to disk), just segment the trial factors too.
This is something I've given a lot of thought to; I've been interested in prime numbers since I was a kid. I've thought about making CDs or DVDs full of primes.
The largest primes known are Mersenne primes. There are primality tests for Mersennes that are far faster than any tests for other numbers. There are still far more other primes at that size - the most recently found Mersenne prime is over seven million digits long.
Another improvement would be to make the program cache-friendly. He sort of did this, down one level of the memory hierarchy, by paging the data to disk -- now he only needed to realize that, just as memory is much faster than disk, cache memory is faster than main memory.
Some of the programs sieved into smaller pages, which could fit into caches. He noted that page sizes of a million worked well for him, but he thought it might have to do with directory access with a large number of files.
I wouldn't trust HavenCo. They're not taking on new customers, they're not putting effort into supporting the customers they have, and the Sealand rulers, despite rulings that they are a sovereign nation, still have made noises about not leaving well enough alone about privacy.
This probably won't be noticed so late in the thread -
I asked Stephenson at a signing after _Quicksilver_ if he had hidden messages in the text. He said he hadn't. (I could ask him again when he passes through the Bay Area next week, though.)
I wondered this because of Eliza and her letters; it turns out that one crypto system she used was dependent on handwriting quirks that weren't reproduced.
I'd check the line numbers of the typos next, by the way.
I just returned _Invisible Cities_ - I second your recommendation, but I'd describe it differently. It's a travelogue of fictional & fantastic cities. I'd recommend it for people who like Neil Gaiman.
I'm surprised; I expected references to All Your Base & Sealab 2021 in this thread, not Calvino.
I tried xdelta3 on a large text file; it was much slower & produced a much larger patch than xdelta1. That may be a pathologically bad example. Also, that's the first public release of xdelta3; the author's written that there's lots of tuning to be done. The article link for "binary diff" talks about a utility offering 50%-80% reduction from the equivalent xdelta1. If the point is saving space, I would compare the patch size first. The overhead of tracking deltas with the versions involved seems like enough to make me think about rsync instead. I think that's currently relatively CPU intensive on the server, though.
Slashdot Mirror
From the site:
The fifth Free and Open source Software Developers' European Meeting is a 2 days event, organized by volunteers, to promote the widespread use of Free and Open Source software. Taking place in the beautiful city of Brussels, Belgium, FOSDEM meetings are recognised as the best Free and Open Source events in Europe.
This fifth edition will take place at the same location (in the ULB) on the Feb 26 & 27 Feb 2005.
I might be misreading it, or misremembering, but it resembles tiger tree hash, only with MD5. With the right block size, this might catch the doppelganger blocks.
Hm. The doppelganger blocks were 64 bytes long. That would require even tinier blocks to catch. Storing or passing along the complete tree could take more room than the original.
Thanks. I thought that tiger tree hashing could catch this with the right block size. Do you know the hash tree block size for Gnutella & Bitzi?
they only hash parts of the file to save timefreaking stupid ...
The older Kazaa only did the first part of the file. Looking at the docs in the parent post, the newer one does the whole file. It looks a little like what I remember of the tiger tree hash idea.
If you and I are remembering the same thing, that was under a different attack. IIRC, that wasn't even an attack on the hash, but just on the way that fingerprints were generated.
I think you're right. I was trying to work out where you were coming from.
Yes, although many legacy keys are still around-- mostly because people kept using PGP 2.6.2 for so long. My keyring is 10% legacy keys.
Oh. That's not good. I should have known that people would still be using old versions, and/or overriding the suggested expiration dates...
So. The key signing mechanism for RSA keys uses the MD5 hash. And RSA got included with GnuPG 1.0.3.
Looking around, there's someone who still recommends PGP 2.6 because the source code is smaller, so easier to audit.
This is kind of depressing, isn't it?
You know that GPG keys are identified and signed by their MD5 hashes?
I vaguely remember that the short key ID used a flimsy hash, but to avoid that you only had to verify the key length.
Looking around, MD5 looked dubious in 1997, and alternatives - like SHA1 and RIPEMD-160 - got incorporated to PGP.
So. I don't buy this. PGP.com knows about it.
The intuitive short-term solution, at least to me, is to use N different MD5sums for each file, taken at N different offsets within the file (each unique mod block size).
It won't do the offset thing, but tiger tree hashing uses blocks, and combines them into another checksum. If the blocks were small enough, they'd catch this. I'm not sure about the block size involved in either, though; I suppose with a bit more CPU, you could get arbitrarily small blocks.
Somebody could use these fake files to "poison" popular torrents, making it very unlikely that anybody on them will get uncorrupted files.
This would worry me, except that BT uses SHA1, not MD5, so this is irrelevant. MD5 has seemed suspect for years, & Bram's the sort to pay attention to that sort of thing.
I checked; Edonkey is based on MD4. Gnutella variants might use MD5.
It's nice to know I wasn't the only one who thought of the other Flash. Although I thought of All Your Base, Yatta, and How to Kill a Mockingbird first. :)
I know, very March 2001...
How can I help get the signatures for that crap added into an anti-spyware program?
(That's partially about the guy who went to one site & got hit by much spyware. It might be nice to follow his lead, then be able to help others who have done that without realizing what would happen.)
When an attempt to reinstall Windows overwrote a Linux partition, I made a script to compare the fsck-recovered files & directories to a Tripwire database.
Nothing irreplaceable was lost, & only a few files - 5% or so? - lost information.
That's where you represent primality or lack of it by setting and clearing bits of an integer.
... there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes.
Working out the mask for those bit operations can take enough time to cancel out the space benefits. I think you could optimize the different masks & their steppings.
I tried this, but I don't know where that program is now. I used 0 as an escape code, allowing me to either note the next delta in hex, or else the current number, to detect errors. I only did this for output, though.
I could see that being effective for the trial factor prime number table, too.
Oh, and the nfsnet thing that's your homepage is cool.
There's a primes program in (uh, on Debian) the bsdgames package; if memory serves, it does the wheel thing suggested.
A suggestion for the article:
If the trial factor prime number table gets big enough to swap (either out of cache, or out to disk), just segment the trial factors too.
This is something I've given a lot of thought to; I've been interested in prime numbers since I was a kid. I've thought about making CDs or DVDs full of primes.
The largest primes known are Mersenne primes. There are primality tests for Mersennes that are far faster than any tests for other numbers. There are still far more other primes at that size - the most recently found Mersenne prime is over seven million digits long.
Another improvement would be to make the program cache-friendly. He sort of did this, down one level of the memory hierarchy, by paging the data to disk -- now he only needed to realize that, just as memory is much faster than disk, cache memory is faster than main memory.
Some of the programs sieved into smaller pages, which could fit into caches. He noted that page sizes of a million worked well for him, but he thought it might have to do with directory access with a large number of files.
On my computer, generating primes from 2 to 2^32 takes a third of the time to unbzip2 the same list.
What are you talking about? This? Or this? They suggested changing passwords, instead of deleting accounts.
I wouldn't trust HavenCo. They're not taking on new customers, they're not putting effort into supporting the customers they have, and the Sealand rulers, despite rulings that they are a sovereign nation, still have made noises about not leaving well enough alone about privacy.
Dude. Check his ID. You just got trolled by "Pan T. Hose."
Technically, Akamai has more bandwidth than Jesus.
Really? What does Jesus have?
I want to see Jerry Springer: The Opera.
This probably won't be noticed so late in the thread -
I asked Stephenson at a signing after _Quicksilver_ if he had hidden messages in the text. He said he hadn't. (I could ask him again when he passes through the Bay Area next week, though.)
I wondered this because of Eliza and her letters; it turns out that one crypto system she used was dependent on handwriting quirks that weren't reproduced.
I'd check the line numbers of the typos next, by the way.
I just returned _Invisible Cities_ - I second your recommendation, but I'd describe it differently. It's a travelogue of fictional & fantastic cities. I'd recommend it for people who like Neil Gaiman.
I'm surprised; I expected references to All Your Base & Sealab 2021 in this thread, not Calvino.
I tried xdelta3 on a large text file; it was much slower & produced a much larger patch than xdelta1. That may be a pathologically bad example. Also, that's the first public release of xdelta3; the author's written that there's lots of tuning to be done.
The article link for "binary diff" talks about a utility offering 50%-80% reduction from the equivalent xdelta1. If the point is saving space, I would compare the patch size first.
The overhead of tracking deltas with the versions involved seems like enough to make me think about rsync instead. I think that's currently relatively CPU intensive on the server, though.
Let's imagine some icon takes 64x64 pixels and is crunched to 4KB compressed.
This would be a "compression" of a byte per pixel: 64x64=4096=4K. Compressing with JPEG or PNG would make it a fraction of that size.
Masamune Shirow's mouse came to mind first. Although apparently getting it to work on a non-Japanese computer might be tricky.