# AW: Possibly new result on truncating hashes

```
John Kelsey wrote:

> Unfortunately, we can't make this argument, because this
> postulated collision algorithm can't be used to find a
> collision in the whole SHA256 more efficiently than brute force.
>
> Let's do the counting argument:  Each time we call the
> 160-bit collision algorithm, we get a new pair which has the
> same first 160 bits of SHA256 output, and random unrelated
> last 96 bits of SHA256 output.  Each pair has a probability
> of 2^{-96} of colliding in the remaining bits.  So, to get a
> collision on the whole SHA256 using this 160-bit collision
> algorithm, we expect to have to try about 2^{96} collision
> pairs, each found at a cost of 2^{64}.  The resulting work is
> 2^{64} * 2^{96} = 2^{160}, more than a straight brute-force
> collision search on SHA256.
> ```
```
Hmm, wouldn't you expect a lot of partial collisions among all those 2^96
collision pairs? That is, after
2^80 runs of the algorithm you would obtain your first partial collision in
collision pairs, don't you?
For 2^96 that's roughly 2^32 such pairs of pairs. Those might help you to speed