Zbr's days.
←March→
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
←2007→
Months
Jan Feb Mar
Apr May Jun
Jul Aug Sep
Oct Nov Dec

About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

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

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)

Please solve this captcha to be allowed to post (need to reload in a minute): 11 * 90

Comments are closed for this story.