About ::
TODO ::
Blog ::
RSS ::
Old blog ::
Projects ::
GIT ::
Gallery ::
Notes
Thu, 04 Sep 2008
Simple exploit for Bernstein/Torek 33 hash.
Example:
$ ./djb_crack 0x12345678 0 0xffffffff 0xabcdef12 07 1a 11 19 01 0c hash: 12345678, calc: 12345678: MATCH 00 hash: 00000000, calc: 00000000: MATCH 03 0a 18 14 1a 09 03 hash: ffffffff, calc: ffffffff: MATCH 02 07 15 11 00 20 03 hash: abcdef12, calc: abcdef12: MATCHExploit takes multiple hash values and searches for data which will produce the same hash value (it prints it to stdout as one can see above).
Since this hash is so simple, it is actually possible to find matching data using brute force, but it is not interesting.
Exploit can not work, if we limit the smallest byte value to something except 1 or 0. Since we do not know actual value of the hash, but only its modulo for 2^32, there is a possibility, that given value can not be represented as sum with fixed multiplicators of the bytes we can operate on (like we can not represent 13 as sum of whatever positive integers, if the smallest one is bigger than 6). But it is always possible to represent any value in the system where the smallest possible byte is zero.
Because of the above limitation for the smallest byte value, every hash can be matched by the array of at most 7 bytes (33^7 is bigger than 2^32).
I want to think some more on the cases, when we we know only modulo (by dividing real result by 2^32 for example) of the result, but we have to find input bytes, so that hash on them would match required one, and input bytes are limited by some set, and the smallest byte is not 1 or 0. This can be tricky task... value
/devel/math/hash :: Link / Comments ()
Wed, 03 Sep 2008
On multiplier selection for the Bernstein/Torek 33 hash.
Hash, as known, uses follofing scheme:
hash = hash * 33 + data[i];where initially hash was set to zero, and data[i] means i'th byte of the input data.
This can also be written as following:
hash = hash + hash << 5 + data[i];Now, let's take a look at hash analysis. As we can see, final hash is a sum of the multiplication of the power of 33 and data bytes. Let's split sum into neighbour pairs, like following (assuming big enough number of input bytes
n):hash = (33^(n-2))*(33*a[0] + a[1]) + ... + (33^(n-k-1))*(33*a[k] + a[k+1]) + ...Now let's check single multiplier using above shift equation for the multiplication:
33*a[k] + a[k+1] = a[k] + a[k] << 5 + a[k+1]Using any other multiplier, which does not result in
a[k] + a[k+1],
will lead to worse distribution, since number of used bits decreases. Particular bad (if not the worst)
multplier is 31, which leads to the following sum:31*a[k] + a[k+1] = a[k] << 5 - a[k] + a[k+1]This hash will have too small active bits, particular only differece between neighbour bytes will play a role in the final hash production.
Now, getting the history of the hash, namely its part, which tells us that hash was first introduced for strings, we can conclude, that above 5 bits shift is used to shift a value to the amount of bits needed to put there new english ASCII character, i.e. shift value could be bigger to work with higher bytes (so that non-zero bits fit the new space).
Now because of the time shift I made for myself because of US embassy interview (awake at 5:30 AM, going to sleep at 1:00 AM), my brain does not allow to work on big projects, so I will try to create an exploit for this hash standing on regular several-cups-of-cofee drug. Stay tuned!
/devel/math/hash :: Link / Comments ()
Mon, 01 Sep 2008
Some recent hash analysis: Bernstein/Torek famous (hash * 33) hash.
Lots of people know about very old hash, which uses simple sum and multiplication
technique (works good not only for strings):
unsigned long hash(const char *s)
{
unsigned long h;
for (h = 0; *s; s++) {
h *= 33;
h += *s;
}
return h;
}
This hash appeared in Bernstein's djbdns server quite long ago (although
Dr. Bernstein now favours version with XOR instead of sum), but it looks like
it appeared in comp.lang.c on behalf of
Chris Torek.I've spent some time on it to determine how it works. One can check clickable picture below to get my thoughts. Short details below.
Bernstein/Torek hash analysis.
In a nutshell, Bernstein/Torek 33 hash is a linear composition of the input bytes.
Each input byte is multiplied by a constant value (namely 33 in a power, which equals to the number of bytes minus position of the input word minus one), and then summed. One can check C source code.
It is simple only because all operations are performed in the same field F(2^32) (namely sum and multiplication, which is effectively the same), if one would add XOR there (like Dr. Bernstein did in the recent version), it shifts the whole approach to the mix of F(2^32) and F(2^1) fields, which is a completely different moster.
In the former case, particulary, it is possible to first multiple/sum lots of elements, and only then apply modulo operation, while in the latter mixed case it is not easily possible (well, I'm searching for group algebra books/articles about operations in mixed fields, so far without much success).
Linear combinations of the input bytes allows very simple way to create an input, which will have the same output hash value as you want. Actually I do not belive in all those attacks, which say, that with our technique we managed to reduce something from X to x. Until there is working realization, which does break appropriate cipher, hash or anything else, it is just words. I do not have a breaking code right now (although belive that it is simple), so nothing was broken and in fact can be completely wrong idea :)
But I will develop it to show myself, that my basic algebra skills are still valid...
/devel/math/hash :: Link / Comments ()
Tue, 19 Aug 2008
Modular arithmetic article needed.
And especially how multiplication and division are performed in finite fields.
So far I run subtraction in a loop to implement modular division in 2^32 field,
which is a bit ugly.
Please drop me a link in comments or send me a
mail, I have a very interesting idea in mind
about some hash analysis. Well, I need to think about something before getting sleep
or while in the transport :)
/devel/math :: Link / Comments ()
Sun, 13 Jul 2008
Hermite interpolation.
This interpolation uses cardinal splines approach, and namely
Catmull-Rom splines. Next task is to test how the Kochanek-Bartels splines (also called TCB-splines)
behave. The latter are used in all popular 3d modelling engines. Since math behind them
is very non-trivial, I will try just to use existing formulas for hermite tangents, which
are quite simple.
Now its time to think, how to use this knowledge and how to apply given approach
to detect and decode letters on the image...
/devel/math/bezier :: Link / Comments ()
Tue, 28 Aug 2007
LDPC iteractive decoding.
This is low-dencity parity check code iteractive decoding algorithm presentation.
Original image was 50x50 bitmap 'transferred' over gaussian (in that degree,
how glibc random number generator (rand()) matches) channel,
where 10% of the noise (swapped bits) were introduced. Rate of the 'transmission'
is 0.5 (i.e. only half of the channel was used to transfer the data, and half for the parity bits).
Code uses hard decoding algorithm, which stops after 4 iterations, since all errors are detected.
Algorithm for matrix generation (takes most of the processing time)
is a bit buggy (can crash, what do you want, I spent 3 hours Sunday night to write it :),
but it does not matter for this presentation.
One can find original presentation by MacKay and Neal (1995)
here,
where authors fully recovered 10000 bits image after 'transmission' over 7.5 % noise channel.
According to my study, LDPC codes and any other similar (let's call them 'probabilistic') codes
can not be used for any reliable transfer, since probability of the error detection is never equal
to one. So, for some matrix some noise can be fixed, but different noise will not. There will be
matrices which will fix at least number of errors, if I understood LDPC correctly, but its generation
is generally very complex (my algorithm tries to automate that a bit though), and I failed
to find a precise description of the error-recovery rate (i.e. how many bits can be 100% recovered
by given matrix (set of weights and word/checksum sizes)). So, for guaranteed transmission some kind
of combined algoritms must be used - LDPC or any other probabilistic code to detect some
errors (as much as possible) and then provide given image to fixed blocksize decoder (like Reed-Solomon),
which guarantees recovery of number of bits, specified during encoding time. Such combined algorithm
will behave better than any of its parts (LDPC and RS separately), since because of probabilistic
nature of the LDPC code, number of errors will be detected, so that error rate becomes small enough
for RS decoder.
One can find source code for LDPC encoder/decoder (code.c),
image to bitmap translator (file2bit.c) and bitmap to picture viewer
(gen_images.c) in archive.
Last two require GTK development library.
I've also created a homepage for this project.
/devel/math/codes :: Link / Comments ()
Mon, 27 Aug 2007
LDPC code presentation.
I'm cooking up a nice LDPC code interactive decoding presentation.
It will be quite small (image is about 50x50 pixels), but I will increase pixel
size on the resulted image.
Presentation (iteractive gif) will show several steps of the image after it was
altered by guassian distribution of the noise.
Stay tuned, it will be ready tomorrow.
/devel/math/codes :: Link / Comments ()
Wed, 22 Aug 2007
LDPC codes.
Ok, I've completed hard-decision decoding algorithm,
with randomly generated matrix (if we are lucky) it can safely decode small
words with multiple bits errors - for example word of 16 bit with
3-bit weight of the random matrix it is possible to decode at leat two bits of
errors even if one of them is in transferred checksum itself.
Unfortunately random matrix generation for larger word sizes
does not work (at all). LDPC generation matrices must obey at least
one rule - it must be invertible. Number of 1's in each column depends on
number of 1's in each row, which is known as weight.
So, to correctly decode damaged message one needs
to have correct matrix, so I need to think about a good algorithm of
creating it. In the regular (simpler) case, matrix has
the same number of 1's in each row and column. The simplest case
is wrapping sequence of bits, like this matrix with weight 3:
1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1And so on, I will check if it works good.
/devel/math/codes :: Link / Comments ()
Mon, 20 Aug 2007
Gallager codes.
Ok, I read number of papers and know kong-fu now - I understood main principles behind LDPC codes.
Main design principle is to send a redundant message over the channel,
which contains a codeword and a checkword(s). The latter is created by multiplying
generator matrix with a source codeword, usually it is very big (thousands of bits),
but matrix is very sparse, so number of operations is not very big.
Generation matrices must obey some rules, main one is that it must be invertible,
otherwise one row can be selected as linear combinations of others, and thus
appropriate information bit will be lost.
Decoding is quite simple - the most powerful algorithm is to use belief propagation -
each check node in generation graph (or generation matrix, which is just a different
representation of the same entity) sends to codeword nodes what they belief a valid bit
with calculated probability, after error probabily that given bit
is zero or one becomes less than requested number (according to Shannon's theorem
code, which allows to reduce error probabily infinitely,
always exist for given rate and communication capacity), codeword calcualtion (decoding) is completed.
There are two mechanisms - hard and soft decision algos, the former is simpler,
but the latter frequently is faster. Let me show an example of the hard decision algorithm
(gotten from "LDPC Codes a brief Tutorial" by Bernhard M.J. Leiner,
although description there is far from being perfect).
Let generation matrix to be this (not very sparse) set:
0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0And source codeword is:
1 0 0 1 0 1 0 1Check word, calculated my multiplication of matrix and codeword is:
0 0 0 0Let's during transmission of the codeword and check word over the channel codeword was changed to this (secod bit changed):
1 1 0 1 0 1 0 1Here is a generation graph (originally proposed by Tanner) of the given matrix:
Here starts decoding algorithm, where each codeword node
C first sends its bit
to each check node F.F0 node will receive 1 1 0 1 bits from C1, C3, C4 and C7 accordingly.
F1 node will receive 1 1 0 1 bits
F2 node will receive 0 1 0 1 bits
F3 node will receive 1 1 0 0 bits
Next step is to calculate the answer for each code node.
Received check word is 0 0 0 0 (calculated above), so set of simple equations starts here.
Each check node F gets three out of four received bits and XORing (summing modulo 2, since this example works in Galois finite field of power of 1 - GF(1)), and sends to the codeword node a bit it expects to be correct to satisfy received check bit.
Here is an example for first check node:
X0 ^ 1 ^ 0 ^ 1 = 0. X0 = 0
1 ^ X1 ^ 0 ^ 1 = 0. X1 = 0
1 ^ 1 ^ X2 ^ 1 = 0. X2 = 1
1 ^ 1 ^ 0 ^ X3 = 0. X3 = 0
Then we send Xi to Ci code bits. After all check nodes are processed, codeword nodes has following set of bits:
C0: 0 from F1, 1 from F3, 1 from originally received codeword.
C1: 0 from F0, 0 from F1, 1 from originally received codeword.
C2: 1 from F1, 0 from F2, 0 from originally received codeword.
C3: 0 from F0, 1 from F3, 1 from originally received codeword.
C4: 1 from F0, 0 from F3, 0 from originally received codeword.
C5: 0 from F1, 1 from F2, 1 from originally received codeword.
C6: 0 from F2, 0 from F3, 0 from originally received codeword.
C7: 1 from F0, 1 from F2, 1 from originally received codeword.
Then using the voting for each bit (i.e. which bit has more 'votes' in above table out of three cases), we get a new codeword:
1 0 0 1 0 1 0 1The same steps then are repeated until cdeword stopped to change. In our case we get it after the first run.
Spft decision algorithm usses essentially the same logic, but it operates with probabilities of the bit to be 1 or 0, each probabilities are recalculated in each run, and after probability is higher than requested value (or error probability is less than requested value), loop stops.
Real world examples use much bigger codewords (up to several thousands of bits), but logic is always the same.
So, I've started initial userspace implementation, if stars are in the right order I will be able to complete it until move to climbing zone, otherwise I hope it to be ready tomorrow.
Stay tuned.
/devel/math/codes :: Link / Comments ()
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 ()
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 7c53ccc5So, 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 ()
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 ()
Tue, 19 Jun 2007
CRC performance depending on the word size.
To select perfect CRC coding technique which will be used for distributed
storage I'm about to start designing, I've ran set of tests to determine how
CRC speed depends on size of the word used in calculation. I use simple XOR
CRC which just performs XOR operation over provided data block several times
and then shows its performance (i.e. number of operations per timeframe).
Here is CRC performance for the same blocksize and number of iterations (i.e.
number of CRC sums performed over the same block):
size: 4096, num: 100000, bits: 64, speed: 459.630646 kop/sec. size: 4096, num: 100000, bits: 32, speed: 348.913483 kop/sec. size: 4096, num: 100000, bits: 16, speed: 176.067184 kop/sec.As expected, CRC speed was improved with increasing size of the word, unfortunately for galois field multiplication speed increase is not enough.
Let's discuss Reed-Solomon coding, which requires galois-field multiplication of checksummed (or raw) data words.
For 16 bit CRC sum galois filed multiplication can be performed using 2^16 table (2 lookups per multiplication or division operation) lookup, but for 32 bit CRC galois field multiplication in GF(2^32) can not be performed using table, since it will be too big. To perform galois field multiplication essentially one needs to solve a system of equations, number of equations is equal to size of the values being multiplied, i.e. 32 in our case. Even the fastest method of solving system of equations will be much much slower than 16 bit CRC plus its 2 lookups. Even using Cauchy matrixes for Reed-Solomon encoding with galois multiplication instead of Vandermonde one results in much slower code than table lookup.
So, for the maximum performance we either need to limit Reed-Solomon system to 16 bit CRC (galois field multiplication is used in RAID coding for example), or to use different coding method.
I'm studing WEAVER codes which are faster by design (and use only XOR operations without complex galois field multiplications), but they have own limits, so I'm trying to understand how distributed system with such erasure coding will suffer from using it.
/devel/math/codes :: Link / Comments ()
Sun, 20 May 2007
First Bezier curve.
Here is a result:
Bezier curve construction is very sensitive to the order of the control points, since
resulted Bezier curve is a weighted sum of Bernstain polynomials, which do not depend
on control points, but each polynomial is multiplied with the single control point,
so mixing them results in completely different picture, while pixel image will still be the same.
As a conclusion, it is not possible to use raw pixel data obtained from
captha
images, instead they must be converted into ordered set of points, which
represents control steps: end points, crosses and rounds.
When this task is solved, it will be quite simple to construct a letter using several Bezier
curves and start working with it.
Back to drawing board...
/devel/math/bezier :: Link / Comments ()
Sat, 19 May 2007
Bezier curves.
For those, who wonders (like me) about vector transformations,
I can recommend to start learning Bezier curves math. It is pretty simple,
but too powerful to believe. For example I always wondered how to approximate
a circle or ellipse, using Bezier curves and derivatives it becomes quite usual task
of approximation.
This is only because of two things, first one is that Bezier curves are parametrized
curves and not functions in usual presentation (but superposition
of basis set of usual functions called Bernstein polynomials), so it can have several results
for the same argument (with different parameter value). Second feature
of this curves is that they are fully defined via its control points,
so scaling and other affine transformations become trivial.
Building a result for given inputs is a bit more complex than with usual functions,
but using de Casteljau's algorithm it is not a big problem too.
I will use b-splines to approximate database letters and then transform
them to match requested image to solve captcha
problems. Probably I will create a math ground for such comparison,
but maybe I will just limit myself with simple 'brute force'.
Even if it will fail, I will create a eye-candy library to create vectorized
images (pretty simple, but that is enough for now).
Stay tuned, maybe tomorrow I will have something to play with, since I devoted the whole
day reading various math theories behind Bezier curves and b-spline approximation,
so I have some (quite small of course, but yet powerful) ground to start with.
/devel/math/bezier :: Link / Comments ()
Sun, 01 Apr 2007
#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 ()
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
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 = BDay 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 XI 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 + bLooks 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:
Example:
old a: 15e28f3a, b: 1cb4ed1c, c: 7edcd3a0, h1: 70bc78e4 new a: 15e28f3a, b: 434c39d0, c: d28fc0ec, h1: 70bc78e4As 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 ()