Re: [DNSOP] Call for Adoption draft-wouters-sury-dnsop-algorithm-update

[Tony Finch <[e-mail]>]

Roy Arends <[e-mail]> wrote:
>
> This is not true. The shattered.io pdf files contain an embedded jpeg.
> The difference between the files is in the jpeg comment. The size of the
> difference is 128 bytes. These are two consecutive 64 byte inputs. The
> two versions hash to the same output, given the prefix. The prefix is
> 192 bytes, and contains the PDF header and the start of the embedded
> JPEG.

AIUI it is slightly more complicated than that.

Both shattered.io PDFs contain both versions of the content as two JPEGs -
observe that both files contain two JFIF headers, and that the first JFIF
is after the colliding differences which are between octets 0x00c0 and
0x0140.

$ for i in 1 2; do echo $i; hd shattered-$i.pdf | grep -C1 JFI; done
1
00000230  00 00 ff fe 00 fc 00 00  00 00 00 00 00 00 ff e0  |................|
00000240  00 10 4a 46 49 46 00 01  01 01 00 48 00 48 00 00  |..JFIF.....H.H..|
00000250  ff db 00 43 00 01 01 01  01 01 01 01 01 01 01 01  |...C............|
--
0002da90  a8 87 d0 7f cc ba d0 1d  db 8d 23 a7 c3 89 1a 66  |..........#....f|
0002daa0  66 66 7f ff d9 41 4e 47  45 ff e0 00 10 4a 46 49  |ff...ANGE....JFI|
0002dab0  46 00 01 01 00 00 48 00  48 00 00 ff e1 00 40 45  |F.....H.H.....@E|
2
00000230  00 00 ff fe 00 fc 00 00  00 00 00 00 00 00 ff e0  |................|
00000240  00 10 4a 46 49 46 00 01  01 01 00 48 00 48 00 00  |..JFIF.....H.H..|
00000250  ff db 00 43 00 01 01 01  01 01 01 01 01 01 01 01  |...C............|
--
0002da90  a8 87 d0 7f cc ba d0 1d  db 8d 23 a7 c3 89 1a 66  |..........#....f|
0002daa0  66 66 7f ff d9 41 4e 47  45 ff e0 00 10 4a 46 49  |ff...ANGE....JFI|
0002dab0  46 00 01 01 00 00 48 00  48 00 00 ff e1 00 40 45  |F.....H.H.....@E|

The header before the collision is the start of a binary stream object
that contains the SHA-1 collision followed by both JPEGs. The first two
hunks below are the start and end of this stream object, and the third
hunk is in the PDF rubric towards the end of the file.

$ hd shattered-1.pdf | grep -C1 ream
00000080  43 6f 6d 70 6f 6e 65 6e  74 20 38 3e 3e 0a 73 74  |Component 8>>.st|
00000090  72 65 61 6d 0a ff d8 ff  fe 00 24 53 48 41 2d 31  |ream......$SHA-1|
000000a0  20 69 73 20 64 65 61 64  21 21 21 21 21 85 2f ec  | is dead!!!!!./.|
--
00066e90  a0 02 80 0a 00 28 00 a0  02 80 0a 00 ff d9 0a 65  |.....(.........e|
00066ea0  6e 64 73 74 72 65 61 6d  0a 65 6e 64 6f 62 6a 0a  |ndstream.endobj.|
00066eb0  0a 32 20 30 20 6f 62 6a  0a 31 30 32 34 0a 65 6e  |.2 0 obj.1024.en|
--
00067080  0a 0a 31 32 20 30 20 6f  62 6a 0a 3c 3c 2f 4c 65  |..12 0 obj.<</Le|
00067090  6e 67 74 68 20 33 35 3e  3e 0a 73 74 72 65 61 6d  |ngth 35>>.stream|
000670a0  0a 71 0a 20 20 31 30 32  34 20 30 20 30 20 37 34  |.q.  1024 0 0 74|
000670b0  30 20 30 20 30 20 63 6d  0a 20 20 2f 49 6d 30 20  |0 0 0 cm.  /Im0 |
000670c0  44 6f 0a 51 0a 65 6e 64  73 74 72 65 61 6d 0a 65  |Do.Q.endstream.e|
000670d0  6e 64 6f 62 6a 0a 0a 0a  0a 78 72 65 66 0a 30 20  |ndobj....xref.0 |

PDF files use indirect pointers to pull assets out of a binary stream. I
haven't picked out the details, but I believe the shattered.io PDFs
indirect via the SHA-1 collision garbage near the start of the binary
stream in order to select either the first or second embedded JPEG.

Now you might be able to use this existing collision to attack other file
formats which have PDF-style indirection, if you have Ange Albertini
levels of POC||GFTO polyglot construction skills :-) The main restriction
is that the colliding header must appear at the very start, so your target
has to be happy with files starting %PDF.

So I don't think you can use this particular collision to attack DNSSEC,
but if you can spend 6000 CPU-years of work, and if you can get a crafted
key into a DNSKEY record, then you could do some interesting things :-)
But you'll need to spend 6000 CPU-years per targeted attack, because the
RRset starts with the targeted domain name, and each collision depends on
a fixed prefix.

It's worth comparing with MD5 collisions. For SHA-1 they haven't yet got
to the point where they can construct a collision from two different
chosen prefixes, as they can for MD5, and which was necessary for creating
the rogue CA certificate.

https://www.iacr.org/conferences/eurocrypt2007/slides/s01t1.pdf
http://www.phreedom.org/research/rogue-ca/

Tony.
-- 
f.anthony.n.finch  <[e-mail]>  http://dotat.at/  -  I xn--zr8h punycode
Fitzroy, Sole: Southwest becoming cyclonic later 5 to 7, increasing gale 8 for
a time in southeast Fitzroy. Rough or very rough. Rain or thundery showers.
Good, occasionally poor.