Zbr's days.

Zbr's days.

←July→
Sun Mon Tue Wed Thu Fri Sat

1 2 3 4 5

6 7 8 9 10 11 12

13 14 15 16 17 18 19

20 21 22 23 24 25 26

27 28 29 30 31

←2008→
Months

Jan Feb Mar

Apr May Jun

Jul Aug Sep

Oct Nov Dec

/(1549)

devel(867)

acrypto(35)

hifn(12)

arm(1)

captcha(9)

dst(87)

eventfs(3)

flat(59)

fs(162)

kevent(110)

aio(7)

math(13)

bezier(3)

codes(5)

hash(5)

networking(177)

nta(27)

unetstack(3)

zcs(7)

other(158)

sh(17)

sky(2)

threading(25)

life(296)

other(93)

About TODO Blog RSS Old blog Projects Gallery Notes

Tue, 07 Aug 2007

I as bloody wrong.

It is impossible to create an input from fully completed workspace, so my crack is no more than a simple case, which does not allow to form an input for given digest.
Instead new equation must be included into the set, which holds the connection between input and workspace bits.
Back to drawing board.

/devel/math/hash :: Link / Comments (0)

Mon, 06 Aug 2007

Breaking Enigma code or cracking SHA1 hash for fun.

Do you recall my intention to crack this hash. Well, it is first 20 rounds of the most widely used cryptographic digest called SHA1. SHA1 contains 80 rounds.

I found a simple way to form a workspace, which, after being processed, results in the given hash value, i.e. algorithm takes needed hash value as parameter and creates something used as input, hash of which is exactly the same as requested.

This is not a complete crack of the reduced SHA1 algorithm yet, since workspace (80 bytes for the first 20 rounds) must be turned into 64 bytes of input, but it is not that complex task.
I do not know if this algorithm will work with full sized SHA1 (80 rounds instead of 20), but right now I do not see any problems with it.

Here is an example workspace data:

Input data:
5e ca 9b e6 38 cf cd 33 41 cf 61 b3 fb cd 39 df 65 87 61 b8 2c 1e 56 ac 69 d7 d0 18 7f 9b 0f a3 
9c 13 99 4c c0 08 c2 de 2d ed c2 d5 99 f8 94 57 d7 a1 e2 35 93 73 0c 11 5a 80 5e 80 ff a8 54 fe

digest: 136be2b1 e949ef99 b85caa61 c97e39cc 7c53ccc5

Cracked data:

workspace (substitute W in sha_transform() with this data):
a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 a57d8667 96ccb97c 
a1900adc c7d34989 3c218123 b2380816

digest: 136be2b1 e949ef99 b85caa61 c97e39cc 7c53ccc5

So, the last task in breaking reduced SHA1 is to find input 64 bytes, which after processed by this method:

W[i] = rol32(W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16], 1);

results in found above workspace.

I do not know, if this can be considered as SHA1 crack, my goal was to complete it upto exactly this point, i.e. break reduced to 20 rounds SHA1 algo.
Although I will ask Bruce Schneier tomorrow if it is.

Stay tuned, but I will go climbing now.

/devel/math/hash :: Link / Comments (0)

Wed, 01 Aug 2007

A hash.

You might now this one:

#define f1(x,y,z)   (z ^ (x & (y ^ z)))

__u32 W[80];
__u32 digest[5];
__u8 in[64];

for (i = 0; i < 20; i++) {
	t = f1(b, c, d) + K1 + rol32(a, 5) + e + W[i];
	e = d; d = c; c = rol32(b, 30); b = a; a = t;
}

I've started to think about how to solve this problem.
I expect similar results to my one round Jenkins hash analysis or complete fail.
You know where to find results - stay tuned.

/devel/math/hash :: Link / Comments (0)

Sun, 01 Apr 2007

Hashes.

#define f1(x,y,z)   (z ^ (x & (y ^ z)))		/* x ? y : z */

#define K1  0x5A827999L			/* Rounds  0-19: sqrt(2) * 2^30 */]

	for (i = 0; i < 20; i++) {
		t = f1(b, c, d) + K1 + rol32(a, 5) + e + W[i];
		e = d; d = c; c = rol32(b, 30); b = a; a = t;
	}

Where $a, $b, $c, $d and $e are parts of the digest, W[i] is i'th word of the input. Does it look similar to this one:

{ \
	a -= b; a -= c; a ^= (c>>13); \
	b -= c; b -= a; b ^= (a<<8); \
	c -= a; c -= b; c ^= (b>>13); \
	a -= b; a -= c; a ^= (c>>12);  \
	b -= c; b -= a; b ^= (a<<16); \
	c -= a; c -= b; c ^= (b>>5); \
	a -= b; a -= c; a ^= (c>>3);  \
	b -= c; b -= a; b ^= (a<<10); \
	c -= a; c -= b; c ^= (b>>15); \
}

For me it does - it is roughly the same GF(2) and GF(2^32) transformations, but with different arguments and operations, but the ground is the same.
So, I have quite ambitious goal to write a similar to this code for new type of the hash. But I'm not sure if I will have a time, but at least it is interesting. Quoted above code snipet is part of the well-known hash, other 3 parts are essentially the same with different f?() function.

/devel/math/hash :: Link / Comments (0)

Wed, 28 Mar 2007

Breaking Enigma code.

Or cracking Jenkins hash for fun and profit...

One man. Six days. One bottle of wine. One bottle of beer. Enourmous amount of tea cups. Eighteen sheets of paper. Two rounds of Jenkins hash.

As a gain:

library for polynomial arifmetic calculations in different Galua fields
refreshed knowledge of polynomial algebra
refreshed knowledge about Galua fields (CRC, Rid-Solomon codes)
new knowledge on boolean algebra transformations
some knowledge on differential crypto analysis

History.
Day one - cracking first round of Jenkins hash.
That was pretty easy from calculation point of view (i.e. how to select i'th bit based on knowledge of (i-1)'th or (i+1)'th bit), but it was not a main goal.
I wanted to solve the problem from algorithmistic point of view, i.e. not to find a single solution, but a generation law. I started from simpler task - to solve following equation:

(A + X) XOR X = B

Day two - theory.
There are two possible ways of solving above equation - either to present logical (bitwise) operation in Galua field of 2^1 (GF(2^1)) - XOR - in ariphmetical field (GF(2^32)) or present sum operation in GF(2^32) as a bitwise operation in GF(2^1).
There are different ways to do it.

Day three - sum as a bitwise operation.
It can be presented using quite simple form:

Ai + Bi = Ai xor Bi xor K(i-1), where
Ki = 0, i = 0,
Ki = (Ai and Bi) or (Ai and K(i-1)) or (Bi and K(i-1))

Xi means i'th bit of X

I got recursive formula for simple sum, which was not what I wanted, so I started to solve above logical equation using different models.
First one - polynomial algebra - sum and bitwise operations are quite simple in polynomial algebra, but there is a serious problem - bitwise operations must be applied only to normalized polynomial form, since it looses information when drops overflow of the order. This limitation is nothing for comupter program, since it is possible to normalize polynomial form before doing bitwise operation, but it does not allow to move on in algorithm solvation.
So, next step - transform bitwise operations into GF(2^32) operations.

Day four - boolean polynoms.
Boolean polynom is a polynom which result and arguments can only be either 0, or 1.
For example XOR operation can be presented as following polynomial form:

A XOR B = X*(3-X)/2, where X = 2*a + b

Looks exactly what I wanted - to present all operations in polynomial form, but there is small problem.
After I expressed all logical operations in the simple equation above ((A+X) xor X = B, where each operation (sum in GF(2^32) and XOR) is transformed into boolean polynoms) in polynomial form, I got system of equations of 27 order - it is not what I expected to solve for simple equation, so this step was dropped too.

Day five - give up?
Not so fast, if I can not solve that problem in algorithm form, let's find at least one sulution for all given inputs.
Here I created a library for polynomial sum, subtraction and normalization (which allows to work with numbers of essentually any order as a bonus, i.e. it is a sum and substraction in Galua field of any order), and started with first round of Jenkins hash cracking.
I ended up with code which gets as input two 32 bit values and hash result, and returns third 32 bit value which if being hashed in first round of Jenkins hash produce required hash value.
That was simple, but then I started second round. (Jenkins hash has 9 rounds).
I made the main mistake here - I started to calculate second round value based on initial inputs (two of them are under attacker's control), but for correct solvation I needed to make a trick.

Day six - break second round of Jenkins hash.
Main trick in Jenkins hash is that it uses value calculated on previous round as input parameter for current round, so after some mathematical transformation it is possible to change variables in the hash equation to work not with initial values, but with some initial values and result of the previous round.
Since each round's result only depends on its input values (some of them can be initial ones, others can be calculated on previous rounds), it can be done.
This idea was in my brain from the beginning, but I could not formulate it into something which can be used, and today sitting in the bus, which moved from home to Moscow to my paid work office I finally drew it (the latest sheet of paper).

Now I have a program which calculates two inputs for given input and required hash output for two-round Jenkins hash.
It is quite simple, but the whole process was very interesting itself.

Further cracking is not impossible task, but complexity increasees with each round (although not exponentially).
I absolutely do not regret about time I spent solving this problem - that was fun.

Interested reader can find a set of photos of brainstorming of this problem in gallery.
And a solution:

Two rounds of Jenkins hash crack solution

Two rounds of Jenkins hash crack solution

Example:

old a: 15e28f3a, b: 1cb4ed1c, c: 7edcd3a0, h1: 70bc78e4
new a: 15e28f3a, b: 434c39d0, c: d28fc0ec, h1: 70bc78e4

As you can see, $a parameter is the same, $b and $c are under attacker's control, all three produce the same hash value $h1 of reduced to two rounds Jenkins hash. $b and $c were calculated based on $a and $h1 knowledge (or actually $h1 can be selected randomly and $b and $c can be selected to produce it again and again, salting with random value will not change the picture).

/devel/math/hash :: Link / Comments (0)