When you visit my site, you agree to download and run a Flash/ActiveX control that downloads all your cookies to slashdot.org, and then sends them to me, so that I can now present false credentials to slashdot.org to make it think that I have auto-login privledges.
Awesome design flaw there, but I highly doubt anyone is THAT stupid to put THAT big of a security flaw into a system.
Well, in the situation of SHA-1 the digest length is 180 bits, and the brute force attack complexity was said in TFA to be 2^80
So, I'm running with TFA that the complexity would be 2^(n/2) which would still be 2^O(n). Given this even the decrease of only halving the n, you still end up with a complexity of 2^O(n)
So, anyways, the complexity of the brute force attack is still 2^O(n) and it's not at this time considered weak. Well, unless you're so steeped in paranoia that you post lengthy comments about the complexity of a simple 160-bit message digest breaking algorithm......................
So, yeah. Just by nature of the assumption the break strength would have to be 2^O(n^alpha) where 0 alpha 1, but not where alpha = 1. Hopefully, we don't have to worry about people solving hashes in 2^O(1) time. That would essentially negate all abilities.
Of course, the other thing is that it is theoretically possible to find hash collisions up to a certain length in O(1) complexity. But the problem is that you would require a hash table indexed to the hash value of the string, and insert the string at that hash bucket.
Once you have enough data there, I'm sure you'd be able to find collisions in O(1) time. Of course, your space requirement would be NP.
I suppose the point of all of this is to prove that, if you play devil's advocate, you're going to be wrong 99% of the time.
No problem, you got me on a couple points also anyways.
I definitely agree that using the multi-hash method is good to bump up security, and for verification of files. After all, it's not that much more computationally expensive to hash the files through a few different algos.
It's definitely a decent idea, and will actually increase security unlike using two substitution ciphers on a piece of text.
I'd just like to say that while I've been bashing the idea, it possibly is the best non-deus ex machina solution available. I'm just playing devil's advocate so that people think about the possible pitfalls, rather than just gloss over them.
Same reason why people break encryption to make better encryption is the reason why people break security policies to make security policies better.
I've come to the notion that this is at least in part true for traffic laws. Somehow, the legislators think that just by passing a traffic law, that it will effect people's behaviours, and they'll drive better.
Or the law is written to improve safety so long as the existing laws are being followed.
But such is not a guarentee. People are bending or breaking the laws already. So, things might be a little different or drastically different than that world that they are passing their laws for.
Like Las Vegas, where you run a red light if you were waiting at the last one. It's generally ok, it's your right, and everyone is expecting it.
Yeah, like my problems that I had with my DSL line once.
I figured out a lot of my symptoms and such completely on my own. (Most oddly, despite having my firewall blocking ping requests, I was getting a pong from my IP) When I finally called tech support (because the problem was not something that I had done,) I ended up getting a guy who was at least some what competent, and we changed my IP, and we were still getting pings from my old IP.
We determined that I was sharing my IP with someone else, and they needed to merely change my static IP.
Now, let me give the response that those same tech people tried to give me at first when I said I could visit some webpages but not others: "Try flushing your browsers cache, cookies, etc."
At least the guy who helped me fix the problem was smart enough to understand what was going on when I told him "I'm telnetting directly to port 80 on the machines, and it won't open a connection. It is *not* a browser issue."
I see the point of having multiple hash algorithms to prevent the hash-length being brought down due to attacks.
But any single good hash should beat out any number of worse hashes.
While it's a good "bolt-on" fix to add a layer of security, really and functionally, it's not that much better than extending digest length production.
Really, you can essentially guarentee that, eventually, finding a hash collision will be come computationally feasible.
Let's take two hash algos, A, and B. Let's say they have the same brute force computational complexity: 2^n. Now, let's say that hash A is eventually found to have a flaw in it that allows that complexity to be brought down to 2^(n/2), while B has a more serious flaw that brings its complexity down to 2^(n/4).
Now, if one were to be using the two hashes together for security, then the hash complexity to find a collision in both should be about 2^(n/2) * 2^(n/4) or simplifying 2^(n/2 + n/4) = 2^(3n/4) Which is closer to the complexity of a brute force attack than to constant time complexity.
But, now let's say that instead you could have hashed the values with a digest of double the length for hash algo A. This means that the brute force complexity goes from 2^n to 2^(2n). But since we now have an attack that halves the n in the complexity, we end up with a time to attack even with the flaw to be 2^n. This is the original complexity of the simple hash algo A brute force.
Now, granted this is a deus ex machina choice to pick the strongest hash algo, so it is impossible to replicate in real life except after the fact (just like the perfect scheduling program).
But the whole idea of hash algos is to make the complexity sufficiently difficult that finding a collision would be computationally infeasible for anyone attempting to alter it. If you're shooting for a long-term goal of keeping the hash good for a long time, then you need to ensure that the computational complexity to solve it is ridiculously large.
Either way, it's all about staving off people from being able to produce a collision to your hash.
Personally I'd take SHA-8092 over using 4 128-bit digest hash programs, no matter what their implementation. Unless you can show me an attack that will reduce the complexity to below the others individually.
It uses the RDTSC assembly command on the x86. While this is good and nice if you don't have a speedstep technology computer, if you do, then the clockspeed of the CPU actually varies, and the RDTSC is defined to increment every clock-edge of the CPU.
This means that if you have the SpeedStep technology in your computer, then RDTSC is not a reliable time source.
This should be noted as a particular caveat on anything relying on RDTSC as a reliable timer.
While the individual strength of an algorithm is constant, tuning it to produce larger digest length produces a more difficult result. So, even if it takes 2^63 hash operations to find a hash collision for SHA-1, if you tune the algorithm to produce a digest of 1 bit more, then it would take 2^64 hash operations to find a hash collision.
And your argument that algorithms are not tunable for larger digest production is wrong. MD5 as defined and specified cannot produce longer digests, but it would be a relatively "simple" matter to rework it to use larger blocks. (Say, instead of per-byte, it works per-2-byte)
It's always possible to take a hash algorithm and extend it to produce a larger digest. It just won't be backwards compatible, so in all cases but the academic it's mostly just a useless point.
But if you're going to make a hash out of MD5 concat SHA-1, then that hash won't be backwards compatible, and you'll need to write and validate code that would process it anyways.
The point is that computing the collision for a hash in two spaces is essentially equivalent to search for a collision in any single one hash with twice as much digest length.
Instead of having to find a digest that matches 160 bits of the SHA-1, now instead you have to match 256 bits.
Two seperate and mostly equivalent algorithms together is not better than a single similar algorithm with twice the digest length.
This is no better than increasing the hash key size. In fact, it's worse than increasing the hash key by the same.
If you take hash algo A at 32 bits, and algo B at 32 bits, but B is weaker than A, then hash collision calculation would be less than the complexity of A squared. (Since B is weaker than A)
If instead you double the hash size of A to 64 bits, then your collision calculation would be the square of the complexity of A at 32.
So, combining MD5 with SHA-1 could cause some problems, with both of them having weaknesses, neither is going to provide you much protection, even if you use them together.
If you built a safe out of paper and cardboard. Sure such a safe would, yes, be better than one made of just paper, or just cardboard, but it's still not better than a safe built out of two cardboard sheets.
Ideally, you don't want to build a safe out of either.
TFA says that it holds implications for IPsec, and a number of other algorithms that depend on SHA-1.
Now, this SHA-1 attack is 2^63 complexity, but this is orders of magnitude less than the 2^80 brute force.
Now, what makes you think that there isn't a faster MD5 attack than just the plain brute force 2^64? Assuming a relative number of orders of magnitude, we're talking around 2^50 or so complexity for an MD5 hash attack.
it's impossible to "create a profile that could only match that file" since such a hash would be at least as large as the file itself.
You forgot about lossy compression. In a way, you could view gzip, and bzip2 as hashing algorithms that take a larger file and reduce it to a smaller size.
This "hash" would only match one file per "hash", and the "hash" would be smaller than the file itself.
Actually, I work in the department that builds these patches. I know about them, and can install them before you all can. I also got pinged with a critical email telling us to install the patches immediately.
Regardless of that point, my fact still remains that when I clicked on the link to download the Windows XP SP2 version of the PnP patch, that it came up with a 404 error.
There's a race-condition in there, and you're not going to convince me otherwise, because I hit a 404 page trying to get the patch.
That was people at Microsoft relying on undefined behavior.
And I'll take the opportunity to slap on an insurance bet, and say that not everything gets completely tested out of the box. That's just not possible. (Reference: Halting Problem)
But Microsoft does test stuff pretty well before it goes out the door. No better, or worse than Linux.
Speaking of which. If Microsoft were to put out a patch that caused reproducable Filesystem corruption for a number of it's users, then immediately puts out a patch to correct the problem; everyone would pound on Microsoft and say that it's because of lack of testing, and just shows that Microsoft can't be trusted.
But when Linus and the Linux crew releases 2.4.11, then 2.4.12 the next day (or two) then the OSS community just says, "Well, no guarentees" and "can't test it all".
While I still enjoy Linux a lot more than Windows, and I like OSX a lot more than I llike Linux; my time at Microsoft has shown me that they're just like all the other programmers out there. No worse, no better.
But it does take some time for the files to be made available. As, they weren't there at the time that I went to install them. And I've never had the need to download said patches because I've never had to WGA verify an illegal copy of Windows.
Slashdot Mirror
Not to mention a security flaw.
When you visit my site, you agree to download and run a Flash/ActiveX control that downloads all your cookies to slashdot.org, and then sends them to me, so that I can now present false credentials to slashdot.org to make it think that I have auto-login privledges.
Awesome design flaw there, but I highly doubt anyone is THAT stupid to put THAT big of a security flaw into a system.
Well, in the situation of SHA-1 the digest length is 180 bits, and the brute force attack complexity was said in TFA to be 2^80
So, I'm running with TFA that the complexity would be 2^(n/2) which would still be 2^O(n). Given this even the decrease of only halving the n, you still end up with a complexity of 2^O(n)
So, anyways, the complexity of the brute force attack is still 2^O(n) and it's not at this time considered weak. Well, unless you're so steeped in paranoia that you post lengthy comments about the complexity of a simple 160-bit message digest breaking algorithm......................
So, yeah. Just by nature of the assumption the break strength would have to be 2^O(n^alpha) where 0 alpha 1, but not where alpha = 1. Hopefully, we don't have to worry about people solving hashes in 2^O(1) time. That would essentially negate all abilities.
Of course, the other thing is that it is theoretically possible to find hash collisions up to a certain length in O(1) complexity. But the problem is that you would require a hash table indexed to the hash value of the string, and insert the string at that hash bucket.
Once you have enough data there, I'm sure you'd be able to find collisions in O(1) time. Of course, your space requirement would be NP.
I suppose the point of all of this is to prove that, if you play devil's advocate, you're going to be wrong 99% of the time.
Yeah, I don't know if he gets that there are ways to do things on the web that don't rely on Internet Explorer using an ActiveX control.
No problem, you got me on a couple points also anyways.
I definitely agree that using the multi-hash method is good to bump up security, and for verification of files. After all, it's not that much more computationally expensive to hash the files through a few different algos.
It's definitely a decent idea, and will actually increase security unlike using two substitution ciphers on a piece of text.
I'd just like to say that while I've been bashing the idea, it possibly is the best non-deus ex machina solution available. I'm just playing devil's advocate so that people think about the possible pitfalls, rather than just gloss over them.
Same reason why people break encryption to make better encryption is the reason why people break security policies to make security policies better.
I've come to the notion that this is at least in part true for traffic laws. Somehow, the legislators think that just by passing a traffic law, that it will effect people's behaviours, and they'll drive better.
Or the law is written to improve safety so long as the existing laws are being followed.
But such is not a guarentee. People are bending or breaking the laws already. So, things might be a little different or drastically different than that world that they are passing their laws for.
Like Las Vegas, where you run a red light if you were waiting at the last one. It's generally ok, it's your right, and everyone is expecting it.
Yeah, like my problems that I had with my DSL line once.
I figured out a lot of my symptoms and such completely on my own. (Most oddly, despite having my firewall blocking ping requests, I was getting a pong from my IP) When I finally called tech support (because the problem was not something that I had done,) I ended up getting a guy who was at least some what competent, and we changed my IP, and we were still getting pings from my old IP.
We determined that I was sharing my IP with someone else, and they needed to merely change my static IP.
Now, let me give the response that those same tech people tried to give me at first when I said I could visit some webpages but not others: "Try flushing your browsers cache, cookies, etc."
At least the guy who helped me fix the problem was smart enough to understand what was going on when I told him "I'm telnetting directly to port 80 on the machines, and it won't open a connection. It is *not* a browser issue."
I see the point of having multiple hash algorithms to prevent the hash-length being brought down due to attacks.
But any single good hash should beat out any number of worse hashes.
While it's a good "bolt-on" fix to add a layer of security, really and functionally, it's not that much better than extending digest length production.
Really, you can essentially guarentee that, eventually, finding a hash collision will be come computationally feasible.
Let's take two hash algos, A, and B. Let's say they have the same brute force computational complexity: 2^n. Now, let's say that hash A is eventually found to have a flaw in it that allows that complexity to be brought down to 2^(n/2), while B has a more serious flaw that brings its complexity down to 2^(n/4).
Now, if one were to be using the two hashes together for security, then the hash complexity to find a collision in both should be about 2^(n/2) * 2^(n/4) or simplifying 2^(n/2 + n/4) = 2^(3n/4) Which is closer to the complexity of a brute force attack than to constant time complexity.
But, now let's say that instead you could have hashed the values with a digest of double the length for hash algo A. This means that the brute force complexity goes from 2^n to 2^(2n). But since we now have an attack that halves the n in the complexity, we end up with a time to attack even with the flaw to be 2^n. This is the original complexity of the simple hash algo A brute force.
Now, granted this is a deus ex machina choice to pick the strongest hash algo, so it is impossible to replicate in real life except after the fact (just like the perfect scheduling program).
But the whole idea of hash algos is to make the complexity sufficiently difficult that finding a collision would be computationally infeasible for anyone attempting to alter it. If you're shooting for a long-term goal of keeping the hash good for a long time, then you need to ensure that the computational complexity to solve it is ridiculously large.
Either way, it's all about staving off people from being able to produce a collision to your hash.
Personally I'd take SHA-8092 over using 4 128-bit digest hash programs, no matter what their implementation. Unless you can show me an attack that will reduce the complexity to below the others individually.
It uses the RDTSC assembly command on the x86. While this is good and nice if you don't have a speedstep technology computer, if you do, then the clockspeed of the CPU actually varies, and the RDTSC is defined to increment every clock-edge of the CPU.
This means that if you have the SpeedStep technology in your computer, then RDTSC is not a reliable time source.
This should be noted as a particular caveat on anything relying on RDTSC as a reliable timer.
While the individual strength of an algorithm is constant, tuning it to produce larger digest length produces a more difficult result. So, even if it takes 2^63 hash operations to find a hash collision for SHA-1, if you tune the algorithm to produce a digest of 1 bit more, then it would take 2^64 hash operations to find a hash collision.
And your argument that algorithms are not tunable for larger digest production is wrong. MD5 as defined and specified cannot produce longer digests, but it would be a relatively "simple" matter to rework it to use larger blocks. (Say, instead of per-byte, it works per-2-byte)
It's always possible to take a hash algorithm and extend it to produce a larger digest. It just won't be backwards compatible, so in all cases but the academic it's mostly just a useless point.
But if you're going to make a hash out of MD5 concat SHA-1, then that hash won't be backwards compatible, and you'll need to write and validate code that would process it anyways.
The point is that computing the collision for a hash in two spaces is essentially equivalent to search for a collision in any single one hash with twice as much digest length.
Instead of having to find a digest that matches 160 bits of the SHA-1, now instead you have to match 256 bits.
Two seperate and mostly equivalent algorithms together is not better than a single similar algorithm with twice the digest length.
DOH!
This is no better than increasing the hash key size. In fact, it's worse than increasing the hash key by the same.
If you take hash algo A at 32 bits, and algo B at 32 bits, but B is weaker than A, then hash collision calculation would be less than the complexity of A squared. (Since B is weaker than A)
If instead you double the hash size of A to 64 bits, then your collision calculation would be the square of the complexity of A at 32.
So, combining MD5 with SHA-1 could cause some problems, with both of them having weaknesses, neither is going to provide you much protection, even if you use them together.
If you built a safe out of paper and cardboard. Sure such a safe would, yes, be better than one made of just paper, or just cardboard, but it's still not better than a safe built out of two cardboard sheets.
Ideally, you don't want to build a safe out of either.
TFA says that it holds implications for IPsec, and a number of other algorithms that depend on SHA-1.
Now, this SHA-1 attack is 2^63 complexity, but this is orders of magnitude less than the 2^80 brute force.
Now, what makes you think that there isn't a faster MD5 attack than just the plain brute force 2^64? Assuming a relative number of orders of magnitude, we're talking around 2^50 or so complexity for an MD5 hash attack.
it's impossible to "create a profile that could only match that file" since such a hash would be at least as large as the file itself.
You forgot about lossy compression. In a way, you could view gzip, and bzip2 as hashing algorithms that take a larger file and reduce it to a smaller size.
This "hash" would only match one file per "hash", and the "hash" would be smaller than the file itself.
Correcting myself... it's "catamount" Thank you Wikipedia
Also because their most recent attack is 2^63 complexity, which is under the 2^64 complexity that people have already run.
Well, the method for "DNA-printing" a file would have to allow for the complete recreation of the file from the DNA-printing.
This has been actually done for a long time, it's called "file compression".
You lost me at "All the did was..."
Brings back memories, only mine was with a mountain lion, not a cougar.
Cougars and mountain lions are regional names for the same animal, Felix concolor. Also, "panther".
Also Cantamount. My high school mascot was the Cougar, so I ended up learning all this stuff.
poorly written PHP code.
Seriously, you should be respecting the Adverb and using it properly.
Actually, I work in the department that builds these patches. I know about them, and can install them before you all can. I also got pinged with a critical email telling us to install the patches immediately.
Regardless of that point, my fact still remains that when I clicked on the link to download the Windows XP SP2 version of the PnP patch, that it came up with a 404 error.
There's a race-condition in there, and you're not going to convince me otherwise, because I hit a 404 page trying to get the patch.
That was people at Microsoft relying on undefined behavior.
And I'll take the opportunity to slap on an insurance bet, and say that not everything gets completely tested out of the box. That's just not possible. (Reference: Halting Problem)
But Microsoft does test stuff pretty well before it goes out the door. No better, or worse than Linux.
Speaking of which. If Microsoft were to put out a patch that caused reproducable Filesystem corruption for a number of it's users, then immediately puts out a patch to correct the problem; everyone would pound on Microsoft and say that it's because of lack of testing, and just shows that Microsoft can't be trusted.
But when Linus and the Linux crew releases 2.4.11, then 2.4.12 the next day (or two) then the OSS community just says, "Well, no guarentees" and "can't test it all".
While I still enjoy Linux a lot more than Windows, and I like OSX a lot more than I llike Linux; my time at Microsoft has shown me that they're just like all the other programmers out there. No worse, no better.
Opinions expressed are my own
Alright I'll give this to you.
But it does take some time for the files to be made available. As, they weren't there at the time that I went to install them. And I've never had the need to download said patches because I've never had to WGA verify an illegal copy of Windows.
No, I'm not.
The product validation explicitly told me that my copy of Windows was not activated and that I could not install the update until I did so.
Product Validation requires Product Activation.
Get Your Official Olympically Sponsored Calendar here!