SHA-0 Kollision hittad

Running time: ca 6,000 minuter

SHI-3-kolliderare

Project Euler 59

Äntligen lite kryptoknäckning!

ciphertext = open( "cipher1.txt", "r" ).readline().split(',')

frequencies = [[0]*255,[0]*255,[0]*255] 

for char in range(0,len(ciphertext)):

   frequencies[char%3][int(ciphertext[char])] += 1

print sum(int(ciphertext[char]) ^ 32 ^ frequencies[char%3].index(max(frequencies[char%3])) for char in range(0, len(ciphertext)))

Sudo funkar när allt annat brister

Project Euler 26

SHI-3-kolliderare under körning

Väntar på att SHI-3 skall kollidera.

Project Euler 148

to A <3

def f(x):

   if x <= 6:

      return (x)*(x+1)/2

   else:

      k = 1

      r = 1

      while (7*k <= x):

         k *= 7

         r *= 28

return f(x/k)*r + (x/k+1)*f(x-k*int(x/k))

Använde identiteten att x^{7} + y^{7} = (x+y)^{7} (mod 7). Det är vetvärt att lösningen är alla ickenoll rutor i en Sierpinskitriangel.

Kollision hittad

Ur mitt exjobb:

Project Euler 202

Ja, det är ju inte världens vackraste kod och den tar dessutom ganska lång tid att exekvera (~10min på en MacBook), på grund av en dålig skriver GCD-algoritm. Det går helt klart att göra mer effektivt... 

Lösningen jag kom fram till var att istället för att spegla laserstrålen, så speglar vi rummet. Speglingen sker iterativt och blir ett rutnät med trianglar. När det är gjort drar vi en RAK linje genom hela rutnätet till en viss nivå i iterationen och finna ett hörn som är ingångpunkten. Dock måste vi se till att vi inte passerar några andra hörn på vägen, och det är just det vi använder GCD till!

int main() { 

unsigned long long m = 12017639147ull;

unsigned long long s, j, k, x ,y ,g;

if (m % 3 == 2) s = 2;

if (m % 3 == 1) s = 0;

if (m % 3 == 0) s = 1;

j = (m-1)/2 + 3;

unsigned long long count = 0;

k = s + 1;

while(1) {

x = j-k;

y = k-1;

while (x > 0){

g = x;

x = y % x;

y = g;

}

if (g == 1)

count += 1;

k += 3;

if (k > ((j-s)/2))

break;

if(count % 1000000 ==0)

printf("%d\n",count);

}

printf("%d", count*2);

}

SHI-2 vill inte kollidera

Sitter och går igenom kod för attack mot SHI-2. SHI-2 är SHI-1, men med icke-linjära funktioner. Med viss sannolikhet beter sig f_i(B,C,D) som XOR(B,C,D). Med en slump-algoritm gör jag försök för att hitta en felvektor som uppfyller XOR-beteende, men än så länge har jag inte påträffat någon kollision. Koden verkar korrekt...

Satt och roade mig med att lösa det här problemet som omväxling. Väldigt kul och givande, även om det slukade några timmar av min skoltid för att lösas!

Kod för att lösa en algebraisk ekvation över GF(2), den så kallade SHI-1.

%% Program for solving the linear equations of SHI1

basis = []

for n = 1:11

% Bit n must be 1

A = [zeros(1,80)];

b = [ zeros(75,1)];

A(1,n) = 1;

b(1,1) = 1;

% Must be an expansion of m

for i = 12:80

u = zeros(1,80);

u(i) = 1; u(i-3) = 1; u(i-8) = 1;

if (i - 14) > 0

u(i-14) = 1;

end

if (i - 16) > 0

u(i-16) = 1;

end

A = [A ; u];

end

% Last five bits must be zero

A = [A; zeros(5,75) eye(5)];

basis = [basis gflineq(A,b)];

end

% independent basis

gfrank(basis')

% check if match

for i = 17:80

if not (basis(i,1) == mod(basis(i-3,1) + basis(i-8,1) + basis(i-14,1) + basis(i-16,1), 2))

echo 'No match'

i

%break

end

end

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