Differentialvägar i MD5

differentialvägar (differential paths). Idag har jag tittat på dessa i MD5, och då framfört allt de som användes av Wang et. al.  För att finna en kollision i hashvärdet för ett, på när som två block, godtyckligt meddelandepar M gör man som följer: 

Låt 

M = M_1,...,B_0,B_1,...,M_m

M_j är godtyckliga meddelandeblock. B_0 och B_1 är två block vi inte bestämt ännu. Definera

M' = M_1,...,B_0',B_1',...,M_m

Hashvärdet är då

MD5Compress(M) = IVH_0(M_1) + ... + IVH_k(B_0) + IVH_{k+1}(B_1) + ... + IVH(M_m)

MD5Compress(M') = IVH_0(M_1) + ... + IVH_k(B_0') + IVH_{k+1}(B_1') + ... + IVH(M_m)

B_0' = B_0 + d och B_1' = B_1 + c

Poängen är att vi kan välja c och d så att

IVH_k(B_0 + d) - IVH_k(B_0) = -(IVH_{k+1}(B_1 + c) - IVH_{k+1}(B_1'))

vilket innebär att skillnaden uppstår i B_0 och försvinner efter B_1.  c och d är de differentialvägar som Wang et al. introducerade. Dock gäller inte detta för alla B-block, så vi måste söka efter dessa. Wang använder lite olika sökheuristiker för att finna block som uppfyller dessa krav. Men det blir imorgon...