I've made a small encryption sysytem using a home-made algorithm. Try to find any weakness with the algorithm, so you don't have to brute-force to crack it. To _generate_ keys, you need GNU MP (get it at www.gnu.org), but an ANSI C compiler should be enough to compile the encryption/decryption part.

Source + document describing the algorithm: http://ostling.no-ip.com/files/ypn/tinycrypt.tar.gz

A small key to test with (for all of you who don't have gmp): http://ostling.no-ip.com/files/ypn/key

Now this is perhaps a real contest. I downloaded the code about 4 hours ago. I made certain observations:
(a) It uses very large key sizes, combined with a transposition technique similar in principle to that found in RC4 (RC4 effectively uses a key with 256 scrambled bytes from 0 to 255). Therefore I expect it to be quite difficult to break.
(b) On the other hand, I timed it to be about 1 tenth of the speed of IDEA (1/64 of the speed of RC4) on my Athlon system running Linux.
(c) The documentation is not yet complete: For example, there was no indication of the number of rounds involved in the basic algorithmm; I actually thought I had already broken the algorithm until I saw that the basic process is carried out 16 times.
(d) The system for attacking the algorithm will probably make use of the relative independence of "b1" and "b2" in the basic encryption/decryption round of your algorithm.
(e) Robert is simply too good (cnasica, bozos, game5, etc. and now tinycrypt). I'll have to study the algorithm a little bit more, to see if it can be cryptanalyzed in any way that I know of.

The maximum key size in my algorithm is 8192!, which is about 10^28503. So I guess brute forcing is kind of out of question

My implementation maybe isn't the best, I'm sure it can be improved quite a lot. If I feel motivated enough, I might write a hand-optimized version in assembler to demonstrate. I'm not quite sure, but the speed could possibly depend on the key size. I'll examine that.

In the document, i DO say how many rounds I use.

From the document:
"I use n = 16 in my implementation (if you want to change this, modify
DEFAULT_ITERATIONS in tinycrypt.h."

I also want to ask what you mean with "the relative independence of b1 and b2".

I studied a doc about DES, and my algorithm looks a lot like it. As far as I could see, the basic idea at least was the same.

However, I will try to study this (and a similar, invented by an IRC friend). Maybe I can find out some easier way than plain brute-forcing.

My last post was rather hasty (when I went back to my PC, I noticed the line I missed). By "the relative independence of b1 and b2", I mean the way you divide the basic unit of encryption into two blocks and operate on each half separately (you called it b0 and b1).

One possible weakness lies in the way the plaintext is divided into blocks before encryption. This makes it susceptible to a "known plaintext attack". Suppose you use the system to encrypt this stream of text:
AABBCCDDAABBCCDDAABB, and I know that the text string begins with "AABB". Looking at the equivalent ciphertext for "AABB", I can extract all the occurences of AABB in the input text. The solution? CBC mode.

About my comparison of your algorithm with RC4, I'm referring to the fact that you use an scrambled array of integers from 1 to n. The form of your algorithm is more like DES (a "block cipher"). RC4 has no results for cryptanalysis.

I have a different challenge. I'm new to assembly language, but I'll like to also try to tune your algorithm for speed. My challenge (apart from trying to get weaknesses in your algorithm) is to write an assembly language implementation that is faster than the one you would implement in assembly.

(But for your picture, I still wouldn't believe that you were really 16 ... )

I take that last thing as a compliment

Anyway, I've done some analysing of this algorithm, and here are some thing I have though of:

* One weakness is that all identical clear text blocks in the file are encrypted to the same enchipered blocks. This makes an attack possible where you search for common 4-byte (or whatever block size you use) blocks that occur several times. Then it's probably something very common in the language you've written the encrypted text in, like the string "and " in english. Now you produce a key from the clear text with a list of common 4-charachter strings, and then you check which one of them that produces a sane text when decrypting with it. This is a variant of seunosewa's known plain text attack.

* Another thing worth pointing out is I don't really beleive b0 and b1 are really separated. When I looked closer at the algorithm, the encryption is converted to an XOR with some of the other bits in the clear text block, from both parts. I haven't found out exactly _how_ those XOR series are going to look with different keys. Probably I will never find out either

NB: I'm an amateur. Don't take this analyse too seriously.

Proposed improvements:

* Run the key through an one-way function (maybe the encryption function itself?). This will of course make it slower, but hopefully more secure.

* Let the user choose the number of rounds. This allows him/her to use 4 or 8 rounds to improve speed, possibly at the cost of security.

And last, an analyse of my program's/the algorithm's bottlenecks:

* It's coded in C, using function calls for many simple functions. Not good for speed, only structure

That's kind of all I can think of about bottlenecks.


I will improve the algorithm and then maybe implement it in assembly language. Wait for my next post here

Anyone want to try and write an ASM RSA implementation? I started on a big-number library ages ago, but would need to start again.

This sounds just too cool...looks like I'll have to learn ASM once and finally now [addsig]

One more weakness:
The basic bit-scrambling operation does a good job of scrambling the bits, but it does not change the number of set bits in the scrambled block. Therefore, the output of Tinycrypt for a block consisting of any of the following four patterns:
0000 0000
0000 1111
1111 0000
1111 1111 (using a 4-bit block as an example)
is independent of the key, and if any of the above patterns is seen in the encrypted text, the equivalent plaintext can be easily obtained (I don't have the time to explain it in full). This means I can partially decrypt a large block of encrypted text provided some of the initial text had one of these patterns...

For other cases, I couldn't think of a way to exploit the fact that the number of set bits in a block after scrambling remains unchanged ... this is because of the effect of 'XORing' the two blocks. I'm still thinking on it.

Talking about the assembly version: I don't think I have the time right now ... but I should be able to upload my version in about two weeks.

Yjo: There are many good bignum libraries, such as the GNU MP. Some of then are also specialized on encryption algorithms.

Or do you want to write one in plain asm? For what platform? I'm not so sure an assembly version will get any faster, unless you're _very_ good at algorithm design. You know the golden rule of speed optimization: "First use a better algorithm, then look for other optimizations."

Little note: With an n-bit TinyCrypt key, you will only need 2^2n tries to brute-force it, not n!. A 8192-bit key may still take some time to crack though

Oops! I didn't take any notice of that part. I just took it by 'faith' that its impossible to brute force the algorithm. (What's the difference between impossible and 'more impossible')

The more impossible, the better!

(reply to an earlier post)
The assembly version could be faster. According to gprof, virtually all the work is done in the "encrypt_bits"/"decrypt_bits" function. If that function could be done entirely in assembly taking advantage of the bit set and test instructions of the pentium...

Aren't those avaiable on all 80386+ CPUs?

I suppose so. Its just that I started my amateur assembly language programming on the pentium and I don't intend to go back in time

I think it will be easier to optimize the algorithm if we standardize the block size. For example, using a 2*64-bit block size, the half-block on which the encrypt-bits functions are called can be stored in a single MMX register and manipulated very fast. For 2 * 128-bit block sizes, there are 128-bit registers on the Pentium-4 and Xeon processors to help us out...

Yes, it would. The problem is then that what is good for one platform, is less good for another

Anyway, if my algorithm is flawed enough to encrypt 0 to 0 no matter what the key may be - it HAS to evolve before anyone thinks of optimising the program.

Does that mean this thread is closed for now?