I think if they were announcing a way to generate a file to order matching a certain hash key, they would have chosen the key 'aa bb cc...' or the hash value of some string like 'hello there'. This seems like a way to generate two files, with no particular content, which have the same hash value. It took eighty thousand hours to find this pair - unless further speedups are discovered it would take inordinately long to find a pair of messages that have meaningful content (for some definition of meaningful) and the same hash value.
According to Tanenbaum's book 'Computer Networks' the Internet is an example of an internet. An internet is a network linking together two smaller networks.
Nobody has 'shown that it's possible to create a new file with the same hash key as some other file'. That has been known all along and it's true for any hashing function where the length of the hash is shorter than the length of the original file. For example, if your hash function produces a result 100 bits long then there are 2 ** 100 possible hashes. Obviously there are more files than this so it is _always_ the case that there are two different files with the same hash value. Usually I'd expect an infinite number of files with any given hash value!
So I don't know what the news item is here, except as a curiosity ('look we found it' - like finding the next Mersenne prime) or some technique has been found for making hash collisions which is better than brute force. If all they did was brute-force hash lots of files until finding two with the same MD5sum or whatever, it's obvious they were going to find a collision eventually.
Are these web applications really free? For example if the site you currently use stops offering the service can anyone take the source code and run the same application from a different site? Or are they locked-in proprietary apps where the site owner can turn off the service at any time and you just have to live with it?
However, Java bytecode is very close to Java source code. Apart from variable names and comments, you can usually reconstruct almost the exact same source code from the.class file. The interesting part is in the bytecode to native code translation and that does occur at the execution site.
But Big Brother is your friend in many cases... given the choice between Big Brother and Uncle Osama which would you support?
More seriously, few people dispute that CCTV in public places (for example) has helped in solving some crimes and deterring some others. Being afraid to go out at night, or use a mobile phone in public, is a much greater curtailment of liberty than almost anything the government might dream up. I don't see why we shouldn't trade one form of liberty for another.
No, if you use an rpm-based distribution you type 'apt-get install foo' or 'yum install foo' or 'urpmi install foo'. Of course this requires that someone has taken the time to package foo and upload it to the repository, but that's true for Portage too.
Mozilla is not a GNOME application and neither is OpenOffice. Neither of them use GTK; OpenOffice doesn't use the GNOME dialogue boxes for file opening etc. and IIRC Mozilla doesn't either. They're fine applications, but don't count them as part of some GNOME vs KDE mindshare contest.
There are some things the client can do to improve compression and caching. First, install wwwoffle, a caching http server which has an 'offline' mode so you can browse cached pages when not connected. If like me you really hate waiting for previously-viewed pages to download a second time, tweak the config file so it always uses cached copies when available. Then the Back button and viewing familiar sites will be lightning fast, but you'll need to hit Reload to get the latest version.
I've also found it useful to run a proxy server on a remote host with a fast connection and then tunnel the http proxy port (usually 3128 or 8080) over ssh. Then there is just a single ssh connection between your machine and the proxy, with everything over that being compressed and no overhead of setting up new TCP connections, DNS lookups and so on. This is really fast, but I have found that the ssh tunnelling tended to freeze and the connection needed to be killed and restarted. (That was a few years ago, the bug may now be fixed.) You could try RabbIT as the upstream proxy, compressing images and such before sending them down.
You can certainly combine all three - local wwwoffle, talking over a compressed ssh tunnel to RabbIT at a faster host...
Lossy compression is a liability for things like screenshots and line drawings.
This is a matter of opinion and I think there are others besides me who want lossy compression for these images. A lot of screenshots on the web are in JPEG format even though JPEG is not really suited to them (unless they contain a lot of graded colours like some of the more garish desktop environments). At the moment JPEG is the best you have if you want to get the file size down and are prepared to lose pixel-perfect accuracy. A lossy compression for screenshots only has to do better than JPEG, which is hopefully not hard (although I admit I haven't convincingly got there yet). OTOH, perhaps all these JPEG screenshots are just made by people who don't know what they are doing, and that may be true.
Lossy compression doesn't make sense for cases like this, except maybe for some screen shots where you don't care about preserving things like text.
Interesting you should mention text. Have a look at the 'Dartmoor' sample images. The text in the bottom right is preserved and doesn't suffer smudging or blurring even at the tight compression settings. This is because of the way the matching works, comparing the sum of squared differences between pixels - text with a reasonably high contrast between foreground and background will get a high badness for any pixel mismatch. The background 'watermark' text is broken up at higher compression levels, because it doesn't have much foreground/background contrast. The Dilbert text at threshold 10000 is speckled a bit but still entirely readable (in Dilbert, everything is high contrast so it's harder to get good compression while preserving text).
If you want to implement security in the database then stored procedures are often the only way to do it. With many SQL systems you can either have insert permission on a table or lack it. Clearly, you may want to allow a user to insert rows related to his own department (for example), but not grant blanket insert permission for anything. Some DBMSes like Oracle have fine-grained access control which may be able to handle this, otherwise, you must use stored procedures or perhaps triggers (which are usually written in the stored procedure language).
BTW, if you want to implement security and business logic in a vendor-indepedent way then you cannot rely on features of some particular middleware platform, since this is just as vendor-dependent as the database - usually more so. If you want to allow multiple front ends then security and logic can't be in the front end without duplication. It's certainly possible to write clean code using only published standards all the way through and so become (mostly) independent of some particular vendor, but it's easy to fall into the trap of making the code database-independent in theory, but deeply tied in to some proprietary middleware platform or toolkit. If you have to be tied into something, make sure it's something good. Oracle is a pretty capable system and so are Postgres, Sybase, even MSSQL.
Indeed the lossy-zlib code with a user-specified matching function is a kind of pre-filtering before doing the zlib compression. The only twist is that there is feedback from zlib to the application about what it's trying to do, so that the app need not lose detail in places where that wouldn't get a smaller output file.
Trying to produce a smaller PNG by first saving as low-quality JPEG and then making a PNG from that does not work, at least not for the kind of images you'd typically use PNG for. For example a screenshot took 198kbyte as a PNG; I saved it as a JPEG at 50% quality (which took 141kbyte) and then remade that into a PNG. The final PNG took 712kbyte. The lossiness used by JPEG works well for images (esp. photographs) saved as JPEG but it isn't the kind of lossiness that will improve Lempel-Ziv string matching.
Thanks for the info. I didn't realize that only some of the chunks were zlib-compressed. If the IDAT chunk is just a raw stream of pixels, with no header information at the start of each row or magic bytes giving palette, image size etc., then compressing it lossily will be easy. (Ignoring the problem of ZTXT for now.)
I agree the image quality is pretty poor... but this was just the simplest possible thing I could hack up to show that the concept could work. Essentially, with the lossy zlib you have a measure of 'badness' of a string match, and for images a string is a list of pixels (or RGB triplets). I took badness as the sum of squared differences between corresponding pixel positions, and then just picked the longest string with badness less than a certain threshold. There is no attempt to do a more sophisticated trade-off of badness against match length, or to do any real image analysis to see if the strings of pixels would look the same to the eye.
The nice thing about the technique is indeed its sheer bone-headedness. All you need to do is write a C function to take two byte strings of the same length and return a number saying how well they match. The ordinary zlib behaviour would be to return the length of the strings if they match exactly, and zero otherwise. You can write any function doing anything you want and plug it in to see its effect on the image. A sensible way to start might be to do edge detection on the string of pixels ('there is a border at offsets 5, 7 and 15') and check that these points match between the two strings within +-1 pixel. I'm sure you can think of better ideas.
I don't intend to use PNG to compress photorealistic images but screenshots, line drawings and other things PNG is traditionally good at. I would like to find a way to do good lossy compression on the Dilbert cartoon shown, where the mottled background is tricky to deal with. I could put an ad hoc check in the compressor to see if two strings of pixels both look like 'background' and always treat them as a good match if they are. Who knows, it might even work. The good thing is that you can do whatever bizarre hacks you want in the compression code and the reader of the file doesn't have to know about any of it.
I did start hacking on something to do lossy PNG compression but didn't finish it. The hard part is integrating the code with libpng so that it lossily compresses the image data but not the headers.
Obviously, if the firewall rather than the PC becomes the main point allowing or denying access to the network then attackers will concentrate on the firewall instead. Lots of consumer-level firewalls are likely to have 'easy-to-use' features which can be exploited. Probably even a firewall control panel accessed from Windows, so all you need to do is crack the PC and wait for the user to enter the firewall password once.
Arguing that we should use reverse firewalls to stop exploited PCs sending out traffic to the network is an admission that expecting security on the PC itself is doomed and we should rely on something, anything else - that doesn't run Windows. I think it would be better to attack the real problem and try to make the typical PC as hard to crack as the typical consumer firewall. For those stuck with insecure systems (or systems which make it very hard for a naive user to keep his PC secure) a reverse firewall might be a useful sticking plaster.
The social engineering is possible only because of whoever designed a system where opening an attachment to read it is able to run a program with full administrative privileges on the machine. Trying to teach users that some things are safe to open and others not is really the wrong approach. The system needs to make a much stronger distinction between safe operations and those which are really very dangerous (such as running a program sent to you). And the set of safe operations needs to be enough that most users can do their work without straying outside it.
In general, directories ending in '.d' are magic - a program looks at every file in the directory, rather than expecting a certain fixed set of filenames. For example under init.d for the various runlevels every file is run in sequence.
The '.d' on the directory name tells you not to put random extra files in there. Apart from those directories, you can follow the rule that extra files won't break anything.
Sounds like it would make sense to abolish corporate taxation altogether so all the accountants employed creating shell companies and so on can be put to more useful work.
I agree, using ssh is a much better bet than some half-baked authentication built into distcc (cf CVS's pserver). If you are really paranoid like Sourceforge you'd want to limit user accounts so the distcc client is the only program they can run.
gcc will never be secure against untrusted input, it's just far too complex. Even trying would be an enormous waste of time.
But in this case as in so much else, a security hole is just a bug. A segmentation fault in the compiler needs to be fixed anyway, the fact that it may also lead to a distcc exploit is just an additional reason. A full audit of the gcc code to make sure the memory access is safe would be impossible, but if you do find known bugs you should fix them.
Worryingly the article does not mention *at all* the obvious security questions. If you run a distcc service on a host then who is authorized to connect to it and compile programs? How do they authenticate? What about protection against man-in-the-middle attacks (you may not be paranoid enough to worry about people fiddling with the object code before it is sent back, but at least you ought to know if it's possible). I hope it's not another case of 'ignore security in the service, but it's okay, we'll just put it behind a firewall'.
FWIW, distributed compliation programs like distcc are a good reason to check for buffer overruns and other memory trampling in the compiler. If you've ever managed to segfault gcc by feeding it a bad piece of code, there is a potential exploit via distcc if you can craft a C program that makes the compiler misbehave in the way you want.
Slashdot Mirror
I think if they were announcing a way to generate a file to order matching a certain hash key, they would have chosen the key 'aa bb cc ...' or the hash value of some string like 'hello there'. This seems like a way to generate two files, with no particular content, which have the same hash value. It took eighty thousand hours to find this pair - unless further speedups are discovered it would take inordinately long to find a pair of messages that have meaningful content (for some definition of meaningful) and the same hash value.
According to Tanenbaum's book 'Computer Networks' the Internet is an example of an internet. An internet is a network linking together two smaller networks.
Nobody has 'shown that it's possible to create a new file with the same hash key as some other file'. That has been known all along and it's true for any hashing function where the length of the hash is shorter than the length of the original file. For example, if your hash function produces a result 100 bits long then there are 2 ** 100 possible hashes. Obviously there are more files than this so it is _always_ the case that there are two different files with the same hash value. Usually I'd expect an infinite number of files with any given hash value!
So I don't know what the news item is here, except as a curiosity ('look we found it' - like finding the next Mersenne prime) or some technique has been found for making hash collisions which is better than brute force. If all they did was brute-force hash lots of files until finding two with the same MD5sum or whatever, it's obvious they were going to find a collision eventually.
Are these web applications really free? For example if the site you currently use stops offering the service can anyone take the source code and run the same application from a different site? Or are they locked-in proprietary apps where the site owner can turn off the service at any time and you just have to live with it?
However, Java bytecode is very close to Java source code. Apart from variable names and comments, you can usually reconstruct almost the exact same source code from the .class file. The interesting part is in the bytecode to native code translation and that does occur at the execution site.
But Big Brother is your friend in many cases... given the choice between Big Brother and Uncle Osama which would you support?
More seriously, few people dispute that CCTV in public places (for example) has helped in solving some crimes and deterring some others. Being afraid to go out at night, or use a mobile phone in public, is a much greater curtailment of liberty than almost anything the government might dream up. I don't see why we shouldn't trade one form of liberty for another.
No, if you use an rpm-based distribution you type 'apt-get install foo' or 'yum install foo' or 'urpmi install foo'. Of course this requires that someone has taken the time to package foo and upload it to the repository, but that's true for Portage too.
Correction - I think Mozilla does use GTK underneath but it has its own widget set layered on that, it doesn't use GTK in the normal way.
Mozilla is not a GNOME application and neither is OpenOffice. Neither of them use GTK; OpenOffice doesn't use the GNOME dialogue boxes for file opening etc. and IIRC Mozilla doesn't either. They're fine applications, but don't count them as part of some GNOME vs KDE mindshare contest.
There are some things the client can do to improve compression and caching. First, install wwwoffle, a caching http server which has an 'offline' mode so you can browse cached pages when not connected. If like me you really hate waiting for previously-viewed pages to download a second time, tweak the config file so it always uses cached copies when available. Then the Back button and viewing familiar sites will be lightning fast, but you'll need to hit Reload to get the latest version.
I've also found it useful to run a proxy server on a remote host with a fast connection and then tunnel the http proxy port (usually 3128 or 8080) over ssh. Then there is just a single ssh connection between your machine and the proxy, with everything over that being compressed and no overhead of setting up new TCP connections, DNS lookups and so on. This is really fast, but I have found that the ssh tunnelling tended to freeze and the connection needed to be killed and restarted. (That was a few years ago, the bug may now be fixed.) You could try RabbIT as the upstream proxy, compressing images and such before sending them down.
You can certainly combine all three - local wwwoffle, talking over a compressed ssh tunnel to RabbIT at a faster host...
Interesting you should mention text. Have a look at the 'Dartmoor' sample images. The text in the bottom right is preserved and doesn't suffer smudging or blurring even at the tight compression settings. This is because of the way the matching works, comparing the sum of squared differences between pixels - text with a reasonably high contrast between foreground and background will get a high badness for any pixel mismatch. The background 'watermark' text is broken up at higher compression levels, because it doesn't have much foreground/background contrast. The Dilbert text at threshold 10000 is speckled a bit but still entirely readable (in Dilbert, everything is high contrast so it's harder to get good compression while preserving text).
If you want to implement security in the database then stored procedures are often the only way to do it. With many SQL systems you can either have insert permission on a table or lack it. Clearly, you may want to allow a user to insert rows related to his own department (for example), but not grant blanket insert permission for anything. Some DBMSes like Oracle have fine-grained access control which may be able to handle this, otherwise, you must use stored procedures or perhaps triggers (which are usually written in the stored procedure language).
BTW, if you want to implement security and business logic in a vendor-indepedent way then you cannot rely on features of some particular middleware platform, since this is just as vendor-dependent as the database - usually more so. If you want to allow multiple front ends then security and logic can't be in the front end without duplication. It's certainly possible to write clean code using only published standards all the way through and so become (mostly) independent of some particular vendor, but it's easy to fall into the trap of making the code database-independent in theory, but deeply tied in to some proprietary middleware platform or toolkit. If you have to be tied into something, make sure it's something good. Oracle is a pretty capable system and so are Postgres, Sybase, even MSSQL.
Indeed the lossy-zlib code with a user-specified matching function is a kind of pre-filtering before doing the zlib compression. The only twist is that there is feedback from zlib to the application about what it's trying to do, so that the app need not lose detail in places where that wouldn't get a smaller output file.
Trying to produce a smaller PNG by first saving as low-quality JPEG and then making a PNG from that does not work, at least not for the kind of images you'd typically use PNG for. For example a screenshot took 198kbyte as a PNG; I saved it as a JPEG at 50% quality (which took 141kbyte) and then remade that into a PNG. The final PNG took 712kbyte. The lossiness used by JPEG works well for images (esp. photographs) saved as JPEG but it isn't the kind of lossiness that will improve Lempel-Ziv string matching.
Wouldn't it be more honest to say 'Solution: None'?
FWIW, it looks like Photoshop already supports lossy compression for GIFs and PNGs. I wonder if the Gimp will get it one day.
Thanks for the info. I didn't realize that only some of the chunks were zlib-compressed. If the IDAT chunk is just a raw stream of pixels, with no header information at the start of each row or magic bytes giving palette, image size etc., then compressing it lossily will be easy. (Ignoring the problem of ZTXT for now.)
I agree the image quality is pretty poor... but this was just the simplest possible thing I could hack up to show that the concept could work. Essentially, with the lossy zlib you have a measure of 'badness' of a string match, and for images a string is a list of pixels (or RGB triplets). I took badness as the sum of squared differences between corresponding pixel positions, and then just picked the longest string with badness less than a certain threshold. There is no attempt to do a more sophisticated trade-off of badness against match length, or to do any real image analysis to see if the strings of pixels would look the same to the eye.
The nice thing about the technique is indeed its sheer bone-headedness. All you need to do is write a C function to take two byte strings of the same length and return a number saying how well they match. The ordinary zlib behaviour would be to return the length of the strings if they match exactly, and zero otherwise. You can write any function doing anything you want and plug it in to see its effect on the image. A sensible way to start might be to do edge detection on the string of pixels ('there is a border at offsets 5, 7 and 15') and check that these points match between the two strings within +-1 pixel. I'm sure you can think of better ideas.
I don't intend to use PNG to compress photorealistic images but screenshots, line drawings and other things PNG is traditionally good at. I would like to find a way to do good lossy compression on the Dilbert cartoon shown, where the mottled background is tricky to deal with. I could put an ad hoc check in the compressor to see if two strings of pixels both look like 'background' and always treat them as a good match if they are. Who knows, it might even work. The good thing is that you can do whatever bizarre hacks you want in the compression code and the reader of the file doesn't have to know about any of it.
I did start hacking on something to do lossy PNG compression but didn't finish it. The hard part is integrating the code with libpng so that it lossily compresses the image data but not the headers.
Obviously, if the firewall rather than the PC becomes the main point allowing or denying access to the network then attackers will concentrate on the firewall instead. Lots of consumer-level firewalls are likely to have 'easy-to-use' features which can be exploited. Probably even a firewall control panel accessed from Windows, so all you need to do is crack the PC and wait for the user to enter the firewall password once.
Arguing that we should use reverse firewalls to stop exploited PCs sending out traffic to the network is an admission that expecting security on the PC itself is doomed and we should rely on something, anything else - that doesn't run Windows. I think it would be better to attack the real problem and try to make the typical PC as hard to crack as the typical consumer firewall. For those stuck with insecure systems (or systems which make it very hard for a naive user to keep his PC secure) a reverse firewall might be a useful sticking plaster.
The social engineering is possible only because of whoever designed a system where opening an attachment to read it is able to run a program with full administrative privileges on the machine. Trying to teach users that some things are safe to open and others not is really the wrong approach. The system needs to make a much stronger distinction between safe operations and those which are really very dangerous (such as running a program sent to you). And the set of safe operations needs to be enough that most users can do their work without straying outside it.
In general, directories ending in '.d' are magic - a program looks at every file in the directory, rather than expecting a certain fixed set of filenames. For example under init.d for the various runlevels every file is run in sequence.
The '.d' on the directory name tells you not to put random extra files in there. Apart from those directories, you can follow the rule that extra files won't break anything.
Does it run on SuSE?
Sounds like it would make sense to abolish corporate taxation altogether so all the accountants employed creating shell companies and so on can be put to more useful work.
But in this case as in so much else, a security hole is just a bug. A segmentation fault in the compiler needs to be fixed anyway, the fact that it may also lead to a distcc exploit is just an additional reason. A full audit of the gcc code to make sure the memory access is safe would be impossible, but if you do find known bugs you should fix them.
Worryingly the article does not mention *at all* the obvious security questions. If you run a distcc service on a host then who is authorized to connect to it and compile programs? How do they authenticate? What about protection against man-in-the-middle attacks (you may not be paranoid enough to worry about people fiddling with the object code before it is sent back, but at least you ought to know if it's possible). I hope it's not another case of 'ignore security in the service, but it's okay, we'll just put it behind a firewall'.
FWIW, distributed compliation programs like distcc are a good reason to check for buffer overruns and other memory trampling in the compiler. If you've ever managed to segfault gcc by feeding it a bad piece of code, there is a potential exploit via distcc if you can craft a C program that makes the compiler misbehave in the way you want.
They're also announcing a monster 5-processor workstation board, to be called the Pentathlon.