Page 2 - Cryptosystem based on asymmetric numeral systems

I wanted to finally compare standard - block private key ciphers (like DES, AES) and initialized - Asymmetric Numeral Systems.

Writing 'random' for ANS, I mean that the states were distributed uniformly using pseudo-random generator (using the key), with given statistics.
So taking some state, we have probability p_d that it corresponds to symbol 'd', which also determines behavior in this moment.

IDEA:
* block ciphers takes huge blocks and mix them using the key as long as it looks breakable
- ANS uses small blocks, but we have determined by whole history hidden variable - the state, which chooses in random way the number of random behavior of choosing the next state and value/length of block to encode
SAFETYNESS
* output file can be easily divided into blocks
- symbols have random length - the blocks cannot be determined
brute force attacks: after taking another key to check:
* start decoding and analyze the beginning to check if the key is correct
- initialize decoder, which takes time chosen by the user, than start decoding to check if the key is correct.
What if someone has get initialized encoder and want to encode given text?
* wiki says that adaptive type of attacks needs 7-9 rounds to break AES
- we can use random (not using the key) initial state - from given file practically every time he gets completely different encrypted file
KEY LENGTH
* fixed, rather long
- any, short can be safe too
For example if we enforce the initialization to 1s, checking possible 6byte codes would take 9 millions years...
SPEED
* for every block we make a lot of computation - rather slow
- all computations are made while the initialization, encryption/decryption are extremely fast
OUTPUT SIZE
* usually the same
- practically: from well compressed input (if prediction made), up to less than 1% larger than the input
MEMORY NEEDS
* some tables for speedup
- practically: a few kilobytes to a few megabytes for the tables
But can be smaller or much larger if needed.
DATA CORRECTION
* if we mix using a few blocks - impossible, else - we can start decoding the next block
- we can correct single bits and we can start decoding again after some lost fragment

A recent posting on a serious cryptography list had a comment that reminded me of this thread. You will notice that this thread is much more of a monologue than a conversation. Mostly, I think, because the whole idea of inventing a new cipher system is a waste of time. This quote expresses the idea much better than I can.

"The wider point of XZY's writeup -- and of the therapy -- is that developers working on security tools should _know_ they're working in a notoriously, infamously hard field where the odds are _overwhelmingly_ against them if they choose to engineer new solutions.

With such understanding, no competent developer should ever set out to build new cryptosystems unless he can explain, point by point, why his needs cannot be met by existing, vetted systems. That explanation should ideally be made public for dissection by the community."

So far, this thread has not shown why this system is worth discussion.

Why inventing cars if we could walk everywhere?
I know well that it was monologue and I believe that it will finally change...
But what does it mean?
Remember that my main question is: is it safe?
Even because it's already nice alternative for Huffman and arithmetic coding, so I'm pretty sure that it will be widely used as the base of compressors.
Observe that after every post the counter of reads increased by dozens. And it counts only the registered users!
I've mailed informations about this cryptosystem with this link to many experts too and placed it on a few forums...
I know that the lack of constructive criticism in this situation after 1.5 month doesn't prove it's safenesses, but maybe suggest it...?

What for? Just look on the table above...
Standard block ciphers uses simple mixing, and it's natural intuition that maybe it could be demixable ... what can be seen in that there is needed new standard every few years...
ANS uses completely unpredictable, large scale mixing ... if You fell how it works, You will see that breaking it is just ... unimaginable - even in the least safe version (uniform byte) uses just diffusion - we can say it's statistical behavior, but to encode we need the exact position!

For adaptive type attacks it could to be a bit strengthen from the uniform byte version, but even without it there would be needed maaaany millions of rounds to decrypt ... wiki says that for AES we need 7-9 rounds...

The next thing is: what do You think is the best time distribution for ciphers?
I - the initialization has to be as long as the user wants, than the processing is as fast as possible.
ANS completely fulfills this demand - what makes it both much faster than standard ciphers and a few orders of magnitude more resistant to the only always possible attack - brute force.

The next thing is that there is possible compression and data correction by the way ... I know that it could be done separately, but joining them, thinking about it as whole system, makes it much faster, simpler and should be safer and requiring less redundancy than doing everything separately...

The main question to everybody is still: how to break it?

How do you break AES? Got any examples?

Do You think You would know if someone would have breaking method?
We officially know that adaptive attacks needs 7-9 rounds ...
ANS doesn't have this problem - in fact it looks completely resistant to any kind of analysis...

But safenesses using huge keys is rather simple to achieve, so choosing the algorithm we can afford to look on other interests too, like resistance to brute force attacks - that short keys could be safe too, the speed and low complicity of processing, compressing the data by the way, optimized with data correction ... like in ANS

In fact, it's so simple they already do it. 256 bits IS huge even though it "sounds" small.

Brute force attack on 64 bit ANS with initialization chosen to last 1s, would take at average 300 000 000 000 years.
Safe enough?
And we can make initialization only once per key - than encryption itself is just using the table - is much faster then for online computed encryptors.

I feel stupid ... a bit ... :]
Cryptosystems are to be discussed, analyzed in the first stage ... there is no necessity to implement them ... yeah ...
I finally found some time and motivated myself to do it ... and it occurred that there is 'slight' problem ... actually making the version from the first post doesn't work...

The problem was that while encoding, we reduce x and check if we are in the range ... the problem is that some times we can jump over the range.
It won't happen if the initialization is precise, for example while using the formula for the binary version or the precise initialization (with not using randomness for a few last numbers), but the first is much too inprecise.

Here is how to make it right:
Take some symbol (d), than numbers which will be coded into the range ([2^R,2^(R+1)-1]) is some range, say [l_d,u_d].
If (u_d<2*l_d - 1) we could jump over the range, so we should have at least: u_d = 2*l_d - 1
Now [l_d,u_d] has exactly l_d numbers, so summing over d we would get 2^R, but it's exactly #[2^R,2^(r+1)-1] - the number of appearances of each symbol have to be exact - symbol d should appear l_d (=x_d) times.

Here is an example of correct initialization, which by the way should be faster, more precise and unpredictable then the first one:

Selfcorrecting Diffiusion Initialization (SDI):
x_1=Floor(2^R*p_1);x_2=Floor(2^R*p_2);...;x_D=2^R-x_1-...x_{D-1};
sym=(1,1,1,... (x_1 times), 2,2,2, (x_2 times), ... ); i=2^R;
For x=2^R to 2^(R+1)-1
{r=random(key , x , i ); //r - random natural number in [1,i], eg Ceiling(random*i)
d=sym[r]; sym[r]=sym[i]; i--;
dec[x]=(d,x_d); //or cod[d][x_d]=x
x_d++; }

Some practical remarks:
1. (Pseudo)random number generator:
We need that:
- gives good uniform distribution
- complex enough that we cannot start decoding without pratically full initialization (easy to get)
- if while knowing a lot about given random series it would be practically impossible to get the key, then even if somebody get the tables, the key remains safe
- if we can enforce long time of generating - like making many iterations, that cannot be calculated in shorter way, we could additionally enforce artificially longer initialization time.

These conditions should be fully fulfilled with modern generator like Mersenne Twister and similar (WELL) or BBS.
Eventually as fast and good generator we could use output from ANS with practically any sequence (ok - shouldn't has to short period).

For example we could though about scenario, that the key is kept in extremely secure place, we initialize ANS with it using any generator.
To create 'n'-th final ANS table which will be used for the real coding, as the generator we use the output of the first ANS used on some sequence constructed using 'n'.
If somebody would get some of final tables, the key is still safe.

Having random number in [0,1), to get random natural number [0,..,n-1], we could use 'Floor(random*n)', or to omit the multiplication, we could use 'Floor(ShiftLeft(random,k))' where k is smallest that n<2^k and throw away wrong(>k) - the distribution is still uniform and 3/4 of generations are expected to be ok.

ANS can be also used in opposite way - very fast generator to generate symbols with chosen probability distribution.

2. Initialization
We could use precise initialization, but it is slower and could be a bit less secure.

The (wrong) initialization from the first post used diffusion (on x_d) with drift (p). It was precise (x_d are very near x*p_d) on the beginning, and was losing precision with raising x.
The selfcorrecting version (SDI) is made to be precise also on the endpoint of the initialization, what occurred to be necessary...
We could also use this version to make more nodes with large precision - just divide the range and symbols uniformly into subranges and initialize separately - the speed is practically the same.
A few additional nodes should be precise enough even for the best compressors.
Eventually if we don't want many nodes with larger precision, we can instead of distributing to the node, earlier successively move some symbols from the set of all symbols to distribute to the set from which we are randomly choosing - now coding is very precise only on the beginning and the end and can be as precise as we want on the internal points.

3. If our range is [2^R,2^(R+1)-1], decoding table need to remember exactly 2^R pairs (x_d,d) - we can encode such pair in one number on different bits.
In fact coding table needs also 2^R values to be stored - it can be done in one table:
indexes [0,l_1) for d=1, [l_1,l_1+l_2) for d=2 ...
So we would need additional (quick and small - eg in L1 cache) table, eg. instead of 'cod[d][x]' use 'cod[x+move[d]]', where move[d]=l_1+...+l_{d-1}-l_d

4. Bit transfer
Even taking bit by bit it's not slow, but to speedup it additionally, we should transfer a few bits at once, especially for large number of symbols.

While coding specific symbol, we know that the number of bits to transfer can take two values, say bt[d] or bt[d]+1 (small and fast table) - we can transfer bt[d] then eventually one more, or previously check if we are above some value which can be encoded on some bits of bt.
While decoding, if processor hasn't quick bitlength operation, we could:
- use bt table like before or
- encode the necessary number of bits to transfer in decoding table (on some bits) or
- make a binary search, for example using calculated probability distribution of cases (eg. if p(6)=0.3,p(7)=0.3,p(8)=0.4, we should firstly check if the number of bits to transfer is smaller than 8, then eventually if is smaller than 7)

I wanted to add something about the problem to my paper...
Yeah .... I've finally realized how horrible it was written...

I've rewritten the section about ANS (pages 10-16) from the beginning.
http://arxiv.org/PS_cache/arxiv/pdf...0710.3861v3.pdf
I wanted very much to make it finally solidly written, but I would be thankful for any comments...

The demonstration is finally available:
http://demonstrations.wolfram.com/D...NumeralSystems/
It shows that even with tiny tables and simplest statistical initialization it works nice.
I’ve checked correlation tables - the probability distribution of sequences has is asymptotically going to be consistent with central limit theorem for uniform probability distribution - it can be used as random number generator.
I wanted to make it educational - simply written. Remarks how to write it practically are two posts up.


I was thinking about 'uniform byte' version (only to encrypt) - because it didn't look as safe as versions with not uniform probability distribution.
One way was just make prediction process - but we shouldn't use header with probability distribution - it tells about file's content. But predictive methods looks safe.

I think I've found ultimate how to make it fast, safe and without initializing new tables (and without compression) : use intermediate sequence of symbols with fixed, not uniform distribution.
We fix some probability distribution - default or chosen using the key.
Now initialize two tables using the key:
- decoding table - to change input into sequence of symbols with given probability distribution
- coding table - to change above sequence - symbol by symbol as they appear, into new sequence of bits

Surprisingly - these tables can be inverses of each other: because to decode properly we should make it backward - if we do it as above - probability distribution of symbol will be the same, but we would get completely different output.
We are using two separate states - number of behaviors grows to multiplication of these numbers.

Practically we could use one small (to fit into L1 Cache) and one large (for safetyness) table. In fact we are making encryption (with taking random initial state) twice - two small should still be completely enough.
The whole process is a bit slower, but even safer ... and is still much faster than using block ciphers.

I believe that with the demonstration the concept is finally understandable and we can finally start DISCUSSION about its safenesses...

I will focus on possibilities of attack on the simplest version - just going once through a file using one coding table.
All weaknesses I will present can be repaired by adding practically any second layer of encryption.
Please help me expanding this list, discuss and show possible attack strategies...

I)Firstly consider scenario that with the same key, every time we generate new tables - for example
- in compression with prediction or
- we generate succeeding tables - for example with a number which is written in the file, and used with the key for initialization (for example XOR with the key).

In these cases, even if someone would get/rebuild somehow the tables, with good generator (like MT) he cannot tell anything about the key.
To ensure it we can additionally for example using the generator choose initial order of symbols in the table for initialization.

In these situations, the only weakness I can think of is that for the same state and the same symbols, we would get the same output.
The number of states in practical cases is let say 10^4-10^6, and usually we cover the space of states uniformly with x, so above situation should occur extremely rare - I don't see a way to use it practically for finding the table, but:
if in the output file are repeated extremely long sequences of bits - we know that with large probability it should correspond to much longer repeated sequences in the input file.

II) Let's focus now on scenario, that we initialize the table and use it for a longer period of time.
If someone has a lot of plaintext+ciphertotext, could he rebuild the tables? (Even if yes, the key is still safe)

The weakness he could use is:
transfer of bits from symbol with probability q, is saying lg(1/q) youngest bits of the state.
Usually
- there is no possibility to determine which bits are used for given symbol and
- even determining the symbol and bits, he still have possible about (number of occurrences of the symbol) states of random position (the number of occurrences shouldn't be smaller than let say 4)

Tracking the state looks usually impossible, but there is one case it could be practically made:
the hacker knows EXACTLY used probability distributions and the initialization is very precise.
Namely: choose some state and positions in both files.
Now after encoding a symbol he know that if it was chosen correctly:
lg(x)->approximately (lg(x)-lg(q)) modulo width
so using bits from ciphertext he could choose (more or less) the next state.
He chooses one state and continue this procedure until something is wrong, then he can go back and try to change some chosen state on the last way, or change initial state/positions... until finally everything is fine and he recreate whole tables.
It's huge work, but can be much smaller than checking all keys.
To make this scenario realistic, the number of states to choose has to be usually one. If not, the number of possibilities would increase exponentially with size of the range.
So to prevent this kind of attacks, we have to make that he should often use more than one state - we can do it for example it randomly varying used probability distribution using the key, or reducing size of alphabet.