About TODO Blog RSS Old blog Projects Gallery Notes

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 (0)

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 (0)

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 1

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

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 0

1 0 0 1 0 1 0 1

0 0 0 0

1 1 0 1 0 1 0 1

1 0 0 1 0 1 0 1

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

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

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

/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;
}

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

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.

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

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 (0)

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 (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;
	}

{ \
	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); \
}

/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

(A + X) XOR X = B

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

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

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

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