Beroenden

Framskridande

Det går framåt. Idag har läst ganska mycket kring metoderna som används. Börjar klarna, det är intressant men samtidigt går det upp för mig hur svårt problem det verkar vara.

Sökning sker top down brute force, men skall vi testa allt tar det tid. Lite för lång tid, eftersom vi har 2^160 möjliga bitkombinationer. Vi måste därför begränsa vårt universum, genom att bara titta på en viss typ av bitkombinationer som uppfyller vissa krav (de kallas ofta generalized characteristics). Väljer vi våra krav rätt, dvs lyckas vi ringa in många meddelande med samma hashvärde och exkludera de som är irrelevanta för sammanhanget, så har vi något ut utgå ifrån.

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...