5 ms·

Downloading the PDFs [1] and comparing their sizes takes less than a minute. They're the exact same size. Yet here we have Linus making one bet after another th

by Strom 10y ago

Downloading the PDFs [1] and comparing their sizes takes less than a minute. They're the exact same size. Yet here we have Linus making one bet after another that size has to be different for this attack. Now to be fair, he also keeps repeating that he hasn't seen the attack yet. Which leads me to question why is this post interesting to HN? Is it to show how Linus aimlessly speculates and gets his guesses wrong? -- [1] http://shattered.it/ http://shattered.it/

cldellow 10y ago
I think you're violently agreeing with Linus here. He says: > pdf's don't have that issue, they have a fixed header and you can fairly arbitrarily add silent data to the middle that just doesn't get shown. In other words, he expects the PDFs to have the same size because silent data has been arbitrarily added to the middle that doesn't get shown.
- euyyn 10y ago
  Padding a code commit with extra whitespace, in indentation, between operators and operands, and trailing the lines, isn't rocket science. As another commenter said, you then helpfully fix the style in the following commit.
  - kalenx 10y ago
    Let's assume that you can use spaces, tabs, newlines and linefeeds. It's still only 4 bytes amongst 128 possibilities (using ASCII)... Good luck with that. Or, in other words : good luck to conceal pseudo-random _bits_ in _text_ files...
  - vidarh 10y ago
    "git diff" highlights, in bright red if you have color enabled, trailing whitespace. The changes you'd be able to make without making it suspicious would be highly limited. Maybe it's possible, but it doesn't seem very likely for source. You'd be more likely to succeed if someone stores binary files in git where people don't have an easy way to audit what's causing the difference. But in that case it would seem you likely have simpler attack vectors.
sverige 10y ago
>> Which leads me to question why is this post interesting to HN? Is it to show how Linus aimlessly speculates and gets his guesses wrong? I think it's interesting because it is another example of his basic attitude toward security, and a lot of people who should know better use Linux believing it is secure because "it hasn't been broken yet."
kalenx 10y ago
That's not it's claim. He specifically goes down on saying how PDF are different than source files, and why while it is trivial to produce two forged PDF with the same size, it is not with source files. That being said, his motto is more like "don't freak out", and in the specific git context, I can only agree.
ibejoeb 10y ago
>Is it to show how Linus aimlessly speculates and gets his guesses wrong? I wasn't thinking of it like that, but now that you mention it, yeah. There's definitely something to learn from the way people make assumptions and are subsequently led by them.
more_original 10y ago
The PDFs have the same size, but they do not have a header in the file that states their overall size. If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. From what I understand, the attack works by inserting garbage data after a fixed file prefix and before a fixed file suffix (anyone please correct me if I'm wrong).
- AgentME 10y ago
  Why would that make the attack harder? Both PDFs are the same length.
- acqq 10y ago
  > If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. No. It doesn't change anything if the size is in the PDF header. The size of both PDFs are the same, the header of both PDF files is the same on the both "shattered" files now. What Linus says is that if you tried to put these two PDF files in git, it would not see them as the same, as git calculates the sha1 differently. But Google would be able to produce two PDF files that would, as git sees them, appear to be same just as easy as these that were produced. P.S. (answer to your answer to this message) Note, You wrote one level above > If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. And I argued that it isn't harder, but irrelevant. From your answer: > But to generate a collision with a different prefix q one would have to do the expensive computation all over again Yes. Now read what your claim was again. It's not harder. Exactly as easy as the first time.
  - more_original 10y ago
    > But Google would be able to produce two PDF files that would, as git sees them, appear to be same just as easy as these that were produced. Right, but they would have to re-do their enormous calculation. ("This attack required over 9,223,372,036,854,775,808 SHA1 computations.") Google started with a common prefix p (the PDF header), then computed blocks M11, M12, M21 and M22, such that (p || M11 || M21 || S) and (p || M12 || M22 || S) collide for any suffix S. Given p, M11, M12, M21 and M22, anyone can make colliding PDFs that show different contents quickly. But to generate a collision with a different prefix q, e.g. one including the file size, one would have to do the expensive computation all over again, I think. Note: I'm not trying to argue that SHA-1 can be made secure with padding. I was just trying to say that the statement "The PDFs have the same size" misses the point.
AgentME 10y ago
I often see the suggestion that storing the length of the file too helps secure against hash collisions because it adds the additional requirement that both files be the same length, but every single MD5 and SHA1 collision I've seen are between values of the same length anyway! Where does this myth come from?
- hvidgaard 10y ago
  It's not a myth. It is obvious that you can find collisions with this constraint. When you make a collision attack such as this, you start with 2 inputs and have a target size, i.e. with a specific size of the padded data, then you simply iterate over paddings (of the same size), and when you find a collision, it will be of the correct size. But it does add an extra constraint, and it prevent attacks that rely on random length filler data. This is not much of an improvement, but an improvement non the less.
  - AgentME 10y ago
    I can agree it strictly limits the type of attacks that can be done, but it doesn't appear to be any practical increase in security. It's like arguing for adding another step in the manufacturing process of bulletproof armor to add a few extra atoms to the armor's thickness. Sure it theoretically adds some protection against some 0.000...1% of bullets that would have just barely had enough force to get through, but it wouldn't have made a difference to any single previously observed successful attack of a similar nature. The fact that someone would argue that this increase in defense is good enough to obviate the need of switching to a different type of stronger defense seems to imply a misunderstanding of hashing.
alexeiz 10y ago
> Downloading the PDFs [1] and comparing their sizes takes less than a minute. shattered-1.pdf and shattered-2.pdf have the same size and sha-1 hash, but git is still able to recognize that those are two different files and creates two different commit hashes for them. So clearly just having the same size and sha-1 hash is not enough to fool git.
- Strom 10y ago
  Git calculates sha1(prefix+file), while the Google example was meant for sha1(file). However there is no difference in the attack. You could just as easily construct two files that have different sha1(file) but matching sha1(prefix+file).

by Strom 10y ago

cldellow 10y ago

I think you're violently agreeing with Linus here. He says: > pdf's don't have that issue, they have a fixed header and you can fairly arbitrarily add silent data to the middle that just doesn't get shown. In other words, he expects the PDFs to have the same size because silent data has been arbitrarily added to the middle that doesn't get shown.

euyyn 10y ago
Padding a code commit with extra whitespace, in indentation, between operators and operands, and trailing the lines, isn't rocket science. As another commenter said, you then helpfully fix the style in the following commit.
- kalenx 10y ago
  Let's assume that you can use spaces, tabs, newlines and linefeeds. It's still only 4 bytes amongst 128 possibilities (using ASCII)... Good luck with that. Or, in other words : good luck to conceal pseudo-random _bits_ in _text_ files...
- vidarh 10y ago
  "git diff" highlights, in bright red if you have color enabled, trailing whitespace. The changes you'd be able to make without making it suspicious would be highly limited. Maybe it's possible, but it doesn't seem very likely for source. You'd be more likely to succeed if someone stores binary files in git where people don't have an easy way to audit what's causing the difference. But in that case it would seem you likely have simpler attack vectors.

sverige 10y ago

>> Which leads me to question why is this post interesting to HN? Is it to show how Linus aimlessly speculates and gets his guesses wrong? I think it's interesting because it is another example of his basic attitude toward security, and a lot of people who should know better use Linux believing it is secure because "it hasn't been broken yet."

kalenx 10y ago

That's not it's claim. He specifically goes down on saying how PDF are different than source files, and why while it is trivial to produce two forged PDF with the same size, it is not with source files. That being said, his motto is more like "don't freak out", and in the specific git context, I can only agree.

ibejoeb 10y ago

>Is it to show how Linus aimlessly speculates and gets his guesses wrong? I wasn't thinking of it like that, but now that you mention it, yeah. There's definitely something to learn from the way people make assumptions and are subsequently led by them.

more_original 10y ago

The PDFs have the same size, but they do not have a header in the file that states their overall size. If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. From what I understand, the attack works by inserting garbage data after a fixed file prefix and before a fixed file suffix (anyone please correct me if I'm wrong).

AgentME 10y ago
Why would that make the attack harder? Both PDFs are the same length.
acqq 10y ago
> If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. No. It doesn't change anything if the size is in the PDF header. The size of both PDFs are the same, the header of both PDF files is the same on the both "shattered" files now. What Linus says is that if you tried to put these two PDF files in git, it would not see them as the same, as git calculates the sha1 differently. But Google would be able to produce two PDF files that would, as git sees them, appear to be same just as easy as these that were produced. P.S. (answer to your answer to this message) Note, You wrote one level above > If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. And I argued that it isn't harder, but irrelevant. From your answer: > But to generate a collision with a different prefix q one would have to do the expensive computation all over again Yes. Now read what your claim was again. It's not harder. Exactly as easy as the first time.
- more_original 10y ago
  > But Google would be able to produce two PDF files that would, as git sees them, appear to be same just as easy as these that were produced. Right, but they would have to re-do their enormous calculation. ("This attack required over 9,223,372,036,854,775,808 SHA1 computations.") Google started with a common prefix p (the PDF header), then computed blocks M11, M12, M21 and M22, such that (p || M11 || M21 || S) and (p || M12 || M22 || S) collide for any suffix S. Given p, M11, M12, M21 and M22, anyone can make colliding PDFs that show different contents quickly. But to generate a collision with a different prefix q, e.g. one including the file size, one would have to do the expensive computation all over again, I think. Note: I'm not trying to argue that SHA-1 can be made secure with padding. I was just trying to say that the statement "The PDFs have the same size" misses the point.

AgentME 10y ago

I often see the suggestion that storing the length of the file too helps secure against hash collisions because it adds the additional requirement that both files be the same length, but every single MD5 and SHA1 collision I've seen are between values of the same length anyway! Where does this myth come from?

hvidgaard 10y ago
It's not a myth. It is obvious that you can find collisions with this constraint. When you make a collision attack such as this, you start with 2 inputs and have a target size, i.e. with a specific size of the padded data, then you simply iterate over paddings (of the same size), and when you find a collision, it will be of the correct size. But it does add an extra constraint, and it prevent attacks that rely on random length filler data. This is not much of an improvement, but an improvement non the less.
- AgentME 10y ago
  I can agree it strictly limits the type of attacks that can be done, but it doesn't appear to be any practical increase in security. It's like arguing for adding another step in the manufacturing process of bulletproof armor to add a few extra atoms to the armor's thickness. Sure it theoretically adds some protection against some 0.000...1% of bullets that would have just barely had enough force to get through, but it wouldn't have made a difference to any single previously observed successful attack of a similar nature. The fact that someone would argue that this increase in defense is good enough to obviate the need of switching to a different type of stronger defense seems to imply a misunderstanding of hashing.

alexeiz 10y ago

> Downloading the PDFs [1] and comparing their sizes takes less than a minute. shattered-1.pdf and shattered-2.pdf have the same size and sha-1 hash, but git is still able to recognize that those are two different files and creates two different commit hashes for them. So clearly just having the same size and sha-1 hash is not enough to fool git.

Strom 10y ago
Git calculates sha1(prefix+file), while the Google example was meant for sha1(file). However there is no difference in the attack. You could just as easily construct two files that have different sha1(file) but matching sha1(prefix+file).