The first chosen-prefix collision for SHA-1

Re:The first chosen-prefix collision for SHA-1 by runeks on Tuesday January 07, 2020 @10:08AM (#21980575)

The point is that the hashed data must follow a specific data format, and can’t just be arbitrary data. This means that the collision data MUST contain the length at some specific offset in the data, which makes it harder to find a collision.

The more restrictive the serialization format of the hashed data, the harder it is to find a collision that’s valid in the given application context.

[ Parent | on HN ]

Re:The first chosen-prefix collision for SHA-1 by est31 on Tuesday January 07, 2020 @10:25AM (#21980759)

Yeah the data must start with a specific prefix, but can otherwise contain whatever it wants. Anyways, even the shattered attack, which this paper says costs 11k to execute today, had a pdf specific prefix (the shown part is the same in both files):

    $ curl -s https://shattered.io/static/shattered-1.pdf | hexdump -n 512 -C 
    00000000  25 50 44 46 2d 31 2e 33  0a 25 e2 e3 cf d3 0a 0a  |%PDF-1.3.%......|
    00000010  0a 31 20 30 20 6f 62 6a  0a 3c 3c 2f 57 69 64 74  |.1 0 obj.<</Widt|
    00000020  68 20 32 20 30 20 52 2f  48 65 69 67 68 74 20 33  |h 2 0 R/Height 3|
    00000030  20 30 20 52 2f 54 79 70  65 20 34 20 30 20 52 2f  | 0 R/Type 4 0 R/|
    00000040  53 75 62 74 79 70 65 20  35 20 30 20 52 2f 46 69  |Subtype 5 0 R/Fi|
    00000050  6c 74 65 72 20 36 20 30  20 52 2f 43 6f 6c 6f 72  |lter 6 0 R/Color|
    00000060  53 70 61 63 65 20 37 20  30 20 52 2f 4c 65 6e 67  |Space 7 0 R/Leng|
    00000070  74 68 20 38 20 30 20 52  2f 42 69 74 73 50 65 72  |th 8 0 R/BitsPer|
    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!!!!!./.|

The shattered attack was about a so-called "identical prefix" collision, while the shambles paper's collision was a "chosen prefix" one. You can choose it in both cases, but in the "chosen prefix" one both colliding prefixes can be entirely different (and can be as long as you want btw, the attack doesn't cost more if the prefix is 4 KB vs 4 GB), while in the "identical prefix" case it has to be identical.

[ Parent | on HN ]

Re:The first chosen-prefix collision for SHA-1 by toyg on Tuesday January 07, 2020 @10:36AM (#21980907)

> the harder it is to find a collision that’s valid in the given application context

In the double-digit thousands of dollars, an attack that gets 10x or 100x harder is still cheap for state actors.

Assuming the NSA is at least a year or two ahead of the field, git should now accelerate its migration process.

[ Parent | on HN ]