Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
pride.crypto.rng; a random number generator + stream cipher
Topic Started: Apr 21 2016, 12:51 AM (271 Views)
E. Rose
Member
[ *  * ]
I have been researching/developing a psuedo random number generator. The basic concept behind the generator is simple:

Let Z256 indicate the set of integers 0...256
Let Z256? indicate a random permutation of Z256
Let seed denote the internal 2048 bit/256 byte array
Let state_8 denote an internal 8 bit/1 byte state
Let ^ denote bitwise XOR
Let [] indicate indexing


  • The set of 256 integers (Z256) is shuffled according to state_8
    - Uses Fisher-Yates shuffle
    - Shuffling Z256 with random data produces a random permutation of Z256 (Z256?)
  • The seed is updated
    - Seed is randomized via XOR with 2 bytes from Z256! and index
    - seed[index] ^= data[index] ^ data[random index] ^ index
    - Selecting a random index from Z256! outputs a random byte
  • State_8 is updated
    - state_8 ^= seed[index] ^ seed[random_index]
  • Output is squeezed from the state
    - output[index] = seed[Z256?[index]]
    - State is output in one of 256! possible orders


A code sample can also be found on github: https://github.com/erose1337/pride/blob/master/crypto/rng.py . Note the algorithm is not finalized. I would have posted it here, but code tags do not respect white space for some reason. If there are any discrepancies between the description given here and the python implementation provided for reference, assume the description given here is wrong and not the implementation.

Looking forward to seeing some attacks!
Attached to this post:
Attachments: rng.py (6.94 KB)
Edited by E. Rose, Apr 21 2016, 12:56 AM.
Offline Profile Quote Post Goto Top
 
E. Rose
Member
[ *  * ]
I'm investigating the security of this construction against timing attacks. Since there's a bunch of data dependent access of the array, I am concerned it may be vulnerable. I have asked here http://crypto.stackexchange.com/questions/34753/is-accessing-elements-of-an-array-in-secret-order-vulnerable-to-timing-attack to hopefully receive some advice on the matter.
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
I must confess that I have so difficulties to understand how the algorithm works.

E. Rose
 
  • The set of 256 integers (Z256) is shuffled according to state_8
    - Uses Fisher-Yates shuffle
    - Shuffling Z256 with random data produces a random permutation of Z256 (Z256?)
Does random data describe a permutation 0..255 or a selection of 256 randomly chosen byte in the range 0..255?

E. Rose
 
  • The seed is updated
    - Seed is randomized via XOR with 2 bytes from Z256! and index
    - seed[index] ^= data[index] ^ data[random index] ^ index
    - Selecting a random index from Z256! outputs a random byte
As you described and if I understand it correctly, the value of the internal state element at seed[index] will now hold a new calculated value. If I don't err than the internal state, which might has been a permutation, may now contain double values because you don't swap the internal state values, but instead calculate new once, based on the values of other internal state elements?

E. Rose
 
  • State_8 is updated
    - state_8 ^= seed[index] ^ seed[random_index]
Am I right in saying that state_8 denotes some kind of random element selector? And if yes, where in the algorithm is it used again? What' it's purpose? And how does it calculate random_index?

E. Rose
 
  • Output is squeezed from the state
    - output[index] = seed[Z256?[index]]
    - State is output in one of 256! possible orders
How is index calculated?
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
E. Rose
 
I'm investigating the security of this construction against timing attacks. Since there's a bunch of data dependent access of the array, I am concerned it may be vulnerable.
Timing attacks on a PRNG may be a thread if the attacker can run some hidden routines on the machine which is doing the encryption. To my knowledge the attacker needs access to the RAM as well a first and second level cache. I came across a very interesting paper[1] when I designed my first usable and considerably secure stream cipher, because it's based on internal state arrays and index pointers, somewhat similar to your algorithm.

In the mentioned paper a very interesting cache timing attack on RC4 is described. Important to notice from my point of view, that the attack only need a small amount of keystreams to be successfully mounted. The major point here is, that even regarding the fact that the internal state of RC4 changes quite fast, it does not change fast enough in order to avoid the precise differentiation of data that has changed and those that don't. This minor information leak can be exploited by the algorithm described in the paper.

This lead me to the conclusion that my own stream cipher need a bigger internal state and more index pointers, that changes more frequently.

Perhaps you might consider reading the paper and draw your own conclusion regarding your algorithm


[1] Cache Timing Analysis of RC4
By Thomas Chardin, Pierre-alain Fouque and Delphine Leresteux

http://www.di.ens.fr/~fouque/pub/acns11.pdf
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
E. Rose
Member
[ *  * ]
If you aren't completely adverse to reading code you might just read the python script; The entire rng takes maybe 20 lines of code. Let me attempt to clarify.

Quote:
 
"Does random data describe a permutation 0..255 or a selection of 256 randomly chosen byte in the range 0..255?"

It describes a selection of 256 randomly chosen bytes in the range 0..255

Quote:
 
"As you described and if I understand it correctly, the value of the internal state element at seed[index] will now hold a new calculated value. If I don't err than the internal state, which might has been a permutation, may now contain double values because you don't swap the internal state values, but instead calculate new once, based on the values of other internal state elements?"


There are two internal 2048 bit states. One is, and always remains, a permutation of the set of integers 0..255. This is shuffled using the second "seed" state as the source of random data required to shuffle the array. The second "seed" state is modified based on two bytes selected from from the Z256? state. These two steps are inlined, so that during the shuffle, as the index decrements from the end of Z256? to the beginning, the byte at seed[index] is modified based on the values at Z256?[index] and Z256?[randomly_swapped_index].

Here's the code for the shuffle:
Code:
 

def[space]shuffle_extract(data,[space]key,[space]state):[space][space][space][space]
[space][space][space][space]"""[space]State[space]update[space]and[space]round[space]key[space]extraction[space]function.[space]"""
[space][space][space][space]for[space]i[space]in[space]reversed(range(1,[space]256)):
[space][space][space][space][space][space][space][space]#[space]Fisher-Yates[space]shuffle
[space][space][space][space][space][space][space][space]j[space]=[space]state[space]&[space](i[space]-[space]1)[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]
[space][space][space][space][space][space][space][space]data[i],[space]data[j][space]=[space]data[j],[space]data[i][space][space][space][space][space][space][space][space][space][space][space]

[space][space][space][space][space][space][space][space]key[i][space]^=[space]data[j][space]^[space]data[i][space]^[space]i[space]#[space]randomize[space]key[space]value[space][space][space]
[space][space][space][space][space][space][space][space]state[space]^=[space]key[i][space]^[space]key[j][space]#[space]randomize[space]value[space]with[space]output[space]feedback
[space][space][space][space][space][space][space][space]
[space][space][space][space]key[0][space]^=[space]data[j][space]^[space]data[i][space]
[space][space][space][space]state[space]^=[space]key[0][space]^[space]key[j]
[space][space][space][space]return[space]state


Quote:
 
Am I right in saying that state_8 denotes some kind of random element selector? And if yes, where in the algorithm is it used again? What' it's purpose? And how does it calculate random_index?


Yes, state_8 is used as the random element selector. It is first initialized to the first byte of the key. It is supplied as an argument to the shuffle_extract routine. Every call to shuffle_extract randomizes it with key material and returns it. The random_index value is calculated using the standard method in the Fisher-Yates shuffle. state_8 is used as the source of random data, and is masked to be constrained to the appropriate range (one less then the current index).

I'm not sure if this technique is used in other crypto primitives. I doubt it's novel, but I couldn't point you to another primitive that uses it. Basically, the state_8 variable influences avalanche and diffusion. Each key byte influences the variable; If this were not done, changing bytes of the key would cause output changes to propagate slower. It also acts as a randomizing element, as even if the same Z256? and same seed are supplied to shuffle_extract, they will only have 1/256 the chance of producing the same output. It acts like an internal "tweak", and is never exposed.

The "index" variable is simply the counter that results from enumerating the bytes (0...255), albeit in reverse due to how the Fisher-Yates shuffle operates. Math commonly uses the symbol 'i' for this meaning, but I prefer explicit terminology to opaque/arcane symbols.
Offline Profile Quote Post Goto Top
 
E. Rose
Member
[ *  * ]
Karl-Uwe Frank
Apr 24 2016, 11:25 AM
E. Rose
 
I'm investigating the security of this construction against timing attacks. Since there's a bunch of data dependent access of the array, I am concerned it may be vulnerable.
Timing attacks on a PRNG may be a thread if the attacker can run some hidden routines on the machine which is doing the encryption. To my knowledge the attacker needs access to the RAM as well a first and second level cache. I came across a very interesting paper[1] when I designed my first usable and considerably secure stream cipher, because it's based on internal state arrays and index pointers, somewhat similar to your algorithm.

In the mentioned paper a very interesting cache timing attack on RC4 is described. Important to notice from my point of view, that the attack only need a small amount of keystreams to be successfully mounted. The major point here is, that even regarding the fact that the internal state of RC4 changes quite fast, it does not change fast enough in order to avoid the precise differentiation of data that has changed and those that don't. This minor information leak can be exploited by the algorithm described in the paper.

This lead me to the conclusion that my own stream cipher need a bigger internal state and more index pointers, that changes more frequently.

Perhaps you might consider reading the paper and draw your own conclusion regarding your algorithm


[1] Cache Timing Analysis of RC4
By Thomas Chardin, Pierre-alain Fouque and Delphine Leresteux

http://www.di.ens.fr/~fouque/pub/acns11.pdf
Thank you for the link to the paper, this is what I was hoping to find.

Quote:
 
This lead me to the conclusion that my own stream cipher need a bigger internal state and more index pointers, that changes more frequently.


Could I ask you to summarize those conclusions for me? Like what did you have originally and what did you conclude you needed? Or if it's a secret/NDA/whathaveyou, that's ok too I guess. I'll figure it out eventually.
Offline Profile Quote Post Goto Top
 
E. Rose
Member
[ *  * ]
I had never actually investigated RC4 this closely before. I had heard of it, but I definitely see the similarity between it and the rng here. That's actually really useful because it means I can really make use of papers like the one you shared.
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
E. Rose
 
If you aren't completely adverse to reading code you might just read the python script; The entire rng takes maybe 20 lines of code.
Surely I can read code, but as every programmer has it's own style it's sometimes a time consuming task fiddling through a listing in order to find out how a specific algorithm works.

What I have learned so far since I started with cryptography is, that if I wan't others having a closer look at my algorithm, I need to present it in a very simplistic readable form. And here first of all only the core algorithm itself, preferable in combination with a formal description in a natural language. Later on there might follow some example implementations for easing running tests by the peer reviewers, so they don't need to program it themselves.

And when I speak of a simplistic readable form, it should be written in such a manner that a comparison between different programming languages is quite easy. That's why I tend to offer an algorithm mostly written in a pseudo code, in ANSI-C, Java and Python, sometimes even in Basic. Just compare these two different implementations and you may understand what I mean

http://www.freecx.co.uk/zx8/ANSI-C/zx8_ps_algorithm.c
http://www.freecx.co.uk/zx8/Python/zx8_ps_algorithm.py


E. Rose
 
Could I ask you to summarize those conclusions for me? Like what did you have originally and what did you conclude you needed? Or if it's a secret/NDA/whathaveyou, that's ok too I guess. I'll figure it out eventually.
When I saw the source code of RC4 it really fascinated me. So few lines of code are able to produce one of the strongest and long time unbroken cipher. For me it's a masterpiece of cryptography, mainly because it extends the very old principle of a polyalphabetic substitution cipher into the computer age. And moreover it gives this ancient cryptographic principle the long needed feature of a self modifying substitution alphabet.

But over time it becomes more and more under pressure of being unable to cope with the immensely growing need for encryption of huge amount of data. For a very long time it was unbroken, but meanwhile it has revealed certain weaknesses. On was discovered early, the bias in the first output byte of the keystream, the other that is has problems encrypting vast amount of data like > 2GB.

There were several approaches to mitigate that problem by modifying RC4, but all it's derivates, like RC4A and VMPC suffer on the same problem.

That's why I thought about another way of building a stream cipher that still honours the concept of a self modifying polyalphabetic substitution cipher.

For me it is evident that there must be two instead of one permutation from which the final output byte should be drawn. But the two internal state array should never interfere. Each of them has to stay as a permutation, never introduce any kind of output feedback, and keep their inner state distant form each other. Additionally the inner state should be updated twice on every byte output. This of course implies that there are 4 swaps on every output cycle involved, which slow down the encryption process in comparison to RC4 heavily. Furthermore I needed some index pointer that are updated in a sequential way, in order to guarantee that every cell of the internal state would be reached at least once and a second index pointer which is updated in a pseudo-randomly fashion. Then there are the column index pointers which are used to indicate which internal cell elements should be swapped. Finally I decided that the output byte should be masked and never reveal any information of the internal state element position directly, like RC4 does. All in all there is a bunch of constantly changing elements that obfuscate the two internal states and should prevent a cache timing attack. But all this massive calculation means there's a price to pay and that's trading speed for security.

But still I believe the algorithm is simple, clean and easy to understand, following one of my favourite quotes

"Simplicity is the ultimate sophistication."
- Leonardo Da Vinci

If your'e interested you can find some details, a step-by-step explanation how the algorithm works and test routines and results over here
http://www.freecx.co.uk/zx8/Docs/
http://www.freecx.co.uk/zx8/

The whole thing is, that I like to convince you separating the core algorithm from the test routines and test the output very thoroughly, which means not only running your own test functions, diehard or ent against the keystream but some fare more valuable random test suites like TestU01[1], just to mention one. And not only on several tens or hundreds of megabyte but on a very very large scale of output, like 2, 4, 8, 16 ... Gigabyte! ... and this using several hundred different random keys in order to make sure that your algorithm at least is not running into a bias.


[1] http://simul.iro.umontreal.ca/testu01/tu01.html
Edited by Karl-Uwe Frank, Apr 25 2016, 11:23 AM.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
E. Rose
Member
[ *  * ]
Quote:
 
Surely I can read code, but as every programmer has it's own style it's sometimes a time consuming task fiddling through a listing in order to find out how a specific algorithm works.

What I have learned so far since I started with cryptography is, that if I wan't others having a closer look at my algorithm, I need to present it in a very simplistic readable form. And here first of all only the core algorithm itself, preferable in combination with a formal description in a natural language. Later on there might follow some example implementations for easing running tests by the peer reviewers, so they don't need to program it themselves.

And when I speak of a simplistic readable form, it should be written in such a manner that a comparison between different programming languages is quite easy. That's why I tend to offer an algorithm mostly written in a pseudo code, in ANSI-C, Java and Python, sometimes even in Basic. Just compare these two different implementations and you may understand what I mean


I understand the need for an appropriate formal description of the algorithm. The above was my first attempt and was destined to need revision and clarification. I haven't finalized the algorithm either, so I'll be probably be updating the description with time. The primitives I work on are subject to change at any time, or might be abandoned altogether, if I find a new or better idea. I have significantly more "hands on" experience, tinkering with code and algorithm design, then any kind of experience sharing them, even in an informal setting with non crypto code. You're basically the first person (other then myself) that's looked at/used any of it.

Thank you for your insights from the development of your algorithm! My first design for this rng actually used two separate Z256 states, which always remained permutations and never mixed. Output was squeezed via shuffling both arrays, seeding output[index] with state[index] ^ state2[index], then pulling bytes from seed via seed[state[index]]. I was concerned my algorithm was getting greedy for space, and modified it to attempt to use less. I'll probably write it again and test some stats later.

Did you ever consider utilizing a capacity, similar to a sponge? The algorithm right now supports a configurable rate. Basically, state - rate = capacity; each time output is squeezed, only rate bytes are output, leaving capacity bytes a secret. I wasn't sure if this would add strength to a place that needs it. I think RC4 ended up evolving in this direction.

Quote:
 
The whole thing is, that I like to convince you separating the core algorithm from the test routines and test the output very thoroughly, which means not only running your own test functions, diehard or ent against the keystream but some fare more valuable random test suites like TestU01[1], just to mention one. And not only on several tens or hundreds of megabyte but on a very very large scale of output, like 2, 4, 8, 16 ... Gigabyte! ... and this using several hundred different random keys in order to make sure that your algorithm at least is not running into a bias.


I appreciate being directed to another test suite. I'm interested in such things and finding them isn't the easiest thing in the world. And I agree that statistical tests need to be extensive in order to have any value. As soon as I have an algorithm worth testing that vigorously, I'll burn some CPU and generate lots of data. My naive C implementation of the rng produces takes about .035 on my laptop to generate 1 MB. So testing large volumes of data from that shouldn't be too much of a pain.
Edited by E. Rose, Apr 25 2016, 07:20 PM.
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
E. Rose
 
I understand the need for an appropriate formal description of the algorithm.
I think it's necessary to mention that the paper which I have published on zx8 is still formalised in a amateurish manner in comparison to those highly mathematical papers of any widely used cipher algorithm. Apart from the very basic and quite different notation in describing the algorithm they lack a formal mathematical proof of the security of the zx8 algorithm. Therefore unfortunately I believe that no professional cryptographer will consider them worth reading. This is something you should keep in mind when publishing your own formal description using a different notation as the one commonly used by mathematicians.

E. Rose
 
Thank you for your insights from the development of your algorithm!
Your'e welcome!

E. Rose
 
My first design for this rng actually used two separate Z256 states, which always remained permutations and never mixed.
In my opinion you should stick with that and use it as a solid basis.

E. Rose
 
... I'll probably write it again ...
Please allow me to add some further remarks.

When designing a stream cipher you should clearly not only concentrate on the Pseudo-Random-Generation Algorithm (PRGA) but also keep an intense interest in designing a proper secure Key Schedule Algorithm (KSA). When I published one of my first stream cipher algorithms a few years ago I didn't even think about having a proper KSA. Luckily I receive a devastating comment from Greg Rose (nice coincidence with your last name though :) ) which reads somehow "Without a KSA you have nothing." This made me think for a long time, because Greg Rose is quite a name in history of cryptography, and if he given such a comment, it was worth thinking twice.

And furthermore a lot of reading of papers about how RC4 is getting to attacked revealed me, that most of the time an adversary will try to break the KSA but rarely the PRGA. In case of RC4 the KSA really has some certain weaknesses [1]. So I thought there has to be a way to get rid of this weak point of design. This finally lead to the development of zx8 with it's really heavy armoured KSA.

But even worst, if an attacker can recover the internal state of RC4 at any time, he will be able reverse calculate the secret key [2]. Of course the described technique has not brought any practical attack forth so far. But even the possibility of reverse calculating the PRGA and the KSA getting back to the secret key should not be possible in my opinion. Therefore I tried to design zx8 somehow more complex in order to prevent such an event, but still trying to follow the advice from Albert Einstein: "Everything should be made as simple as possible, but not simpler."

And therefor within the KSA of zx8 the PRGA is called 256 times on every key byte which is incorporated into the two internal state arrays. In addition with those 5 index lookup pointers, which are constantly updated in a pseudo-random fashion, and the masking of the output byte, there is little if no valuable information for any attacker. The only known value is that of the sequential index pointer b.

Now there is still something to consider regarding cache timing attacks. The KSA should do as much work as possible, and under the aspect of usability acceptable, to update and change the level one and level two cache of the CPU. No trace to the internal state should be found after the KSA has finished. Therefor it might also be useful dropping at least one complete internal state after the KSA has finished - as an advice for a secure usage of RC4 nonetheless. Furthermore the secret key has to be removed immediately after running the KSA and before dropping the complete internal state, so no trace of the secret key may remain in RAM or L1, L2 cache.

So in my opinion, if you start to re-write your algorithm please consider

1) A proper and secure KSA which does prevent any bias and any correlation between key and internal state after the KSA

2) A relatively huge internal state with independent permutations

3) Several index lookup pointers and some output byte masking in order to never reveal any byte of the internal state directly

4) A well balanced update of the internal state arrays in order to prevent any bias in the keystream even on a very large scale

5) A fast and broad update of the internal state arrays in addition to several index lookup pointers to prevent cache timing attacks

6) A fixed and constant output of the keystream completely independent from the plaintext in order to prevent cache timing attacks

7) Give some test vectors so that anyone implementing your algorithm can verify that he has done it properly


E. Rose
 
Did you ever consider utilizing a capacity, similar to a sponge? The algorithm right now supports a configurable rate. Basically, state - rate = capacity; each time output is squeezed, only rate bytes are output, leaving capacity bytes a secret. I wasn't sure if this would add strength to a place that needs it. I think RC4 ended up evolving in this direction.
No, I have not considered any sponge ability in my algorithms currently, because I can't see the advantage such a reservoir. And yes, the successor of RC4, named Spritz, uses sponge techniques as far as I understand. But in my opinion it has lost it's simplicity - and so far not sure what it has gained.

In fact, if I look at SBox8, my recent stream cipher algorithm, it occur to me that it is squeezing its output already from a "sponge", which is literally the internal state. There are four additional internal state variables a,b,c,d which are updated in a pseudo-randomly fashion on every output cycle apart from the byte swap and their content is than "squeezed" into the output byte <= (a + b) ^ (c + d). I'm not sure if any reservoir would add any level of security here, but I believe it will surely slow down the whole process. And as SBox8 is designed with just one internal state array, having tiny 8bit microprocessor platforms like Arduino in mind, there is not enough RAM where a reservoir might fit in.


E. Rose
 
I appreciate being directed to another test suite. I'm interested in such things and finding them isn't the easiest thing in the world.
In my opinion TestU01 it the ultimate and most comprehensive test battery for PRNG's available yet. It's state of the art and believe me, if there is any weakness in a PRNG it will find it - in clear contrast to diehard. There is also another quite promising new test suite around for some years called "PractRand"[3], but despite all my effort I couldn't get it to work.

Finally there is the so called "book stack test"[4][5][6] which revealed the massive bias in RC4 with the keystream being > 2GB and also "cracked" the ZK-Crypt cipher. From my point of view you should definitively check your stream ciphers agains it.

I hope these information will help you designing a proper usefull stream cipher, because I think that there is need for a great variety of such available to the public.


[1] Lecture Notes on Stream Ciphers and RC4 - Rick Wash
http://rickwash.com/papers/stream.pdf

[2] RC4 State Information at Any Stage Reveals the Secret Key - Goutam Paul, Subhamoy Maitra
https://eprint.iacr.org/2007/208.pdf

[3] PractRand
http://pracrand.sourceforge.net/

[4] - On ZK-Crypt, Book Stack, and Statistical Tests -
Doroshenko, Fionov, Lubki, Monarev, Ryabko
http://eprint.iacr.org/2006/196

[5] - The experimental distinguishing attack on RC4 -
Doroshenko, S. and Ryabko, B. (2006)
http://eprint.iacr.org/2006/070

[6] - The distinguishing attack on ZK-Crypt cipher -
by Alexey Lubkin and Boris Ryabko
http://www.ecrypt.eu.org/stream/papersdir/076.pdf
Edited by Karl-Uwe Frank, Apr 26 2016, 09:36 AM.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
E. Rose
Member
[ *  * ]
Firstly, I appreciate all the links. I'm a fan of open source style intelligence, which means references for everything is really important.

Quote:
 
...no professional cryptographer will consider them worth reading. This is something you should keep in mind when publishing your own formal description using a different notation as the one commonly used by mathematicians.


For a little background, I have never been to college and have no professional work history. I accepted a while ago that even if I put in the time and effort to attempt to assemble a proper white paper on crypto research, that basically nobody would read it, even if the language of the paper used formal math and contained valid proofs. I have no "qualifications" and nobody to vouch for me. Considering how heavily academia is intertwined with crypto, I'm pretty sure I'm destined to be an outsider. I'm ok with this, as I'm not seeking to be employed as a professional cryptographer. I do these things because they are fun to me.

This is the reason I am grateful for the forum here. Places like this are likely the only place I can try to have a conversation about crypto/algorithm design; everywhere else is going to more or less have the above challenges: people will expect formal mathematical descriptions, and I'd undoubtedly be met with cries of "don't roll your own", and "leave it to the smart people". So far the only other place I have found is crypto.stackexchange, which is useful to read old questions about general crypto stuff, but pretty much pointless for insights regarding my own questions on internal algorithm design. In my experience, people there are all too happy to say "no" or disprove an idea, but don't appear to be nearly so inclined to offer suggestions/constructive criticism as to how to improve the idea in question.

Quote:
 
...When designing a stream cipher you should clearly not only concentrate on the Pseudo-Random-Generation Algorithm (PRGA) but also keep an intense interest in designing a proper secure Key Schedule Algorithm (KSA).


Mine has a key schedule inlined into the shuffle function. It updates the key based on internal state values. "seed" and "key" are basically synonymous in this rng; The key is the original "seed".

I might try to update the key based off of information that's not from the state, based off of what you've mentioned here about keeping things separate and clean.

I agree that a key schedule is a very important part of a cipher. I have a block cipher I've put much more work into (but didn't consider the current iteration worth sharing yet), so I have studied key schedules a bit. I actually wrote the answer on crypto.stackexchange regarding the requirements of a key schedule[1]. I attempt to design key schedules that fit the classification of "2B"[2]


Quote:
 
Therefor it might also be useful dropping at least one complete internal state after the KSA has finished - as an advice for a secure usage of RC4 nonetheless

I saw that countermeasure when I was reading about RC4. Using a rate/capacity will drop some of the state with each squeeze; I wonder if that's why spritz ended up evolving in that direction. Do you know if that countermeasure (dropping the first state) is still used with newer variants of RC4? Basically I think I might look at all the evolutionary variants of RC4 and see how they attempted to fix the problems/how they succeed/how they fail.

Using a rate/capacity is definitely a time/security trade off. This is the reason the default rate on my rng is 256; I'm not sure how much capacity would be required to thwart what kind of attack (if any, at all), so decided to leave it configurable. That assumes using a capacity would improve security in the first place, which can't really be gauged without looking at attacks on the specific rng (which don't exist yet).


Quote:
 
In my opinion TestU01 it the ultimate and most comprehensive test battery for PRNG's available yet. It's state of the art and believe me, if there is any weakness in a PRNG it will find it - in clear contrast to diehard. There is also another quite promising new test suite around for some years called "PractRand"[3], but despite all my effort I couldn't get it to work.

Finally there is the so called "book stack test"[4][5][6] which revealed the massive bias in RC4 with the keystream being > 2GB and also "cracked" the ZK-Crypt cipher. From my point of view you should definitively check your stream ciphers agains it.

I hope these information will help you designing a proper usefull stream cipher, because I think that there is need for a great variety of such available to the public.


Then I'm extra grateful for you sharing it! I will make sure to incorporate the book stack test.

[1] What are the requirements of a key schedule?
http://crypto.stackexchange.com/questions/33975/what-are-the-requirements-of-a-key-schedule

[2] Key Schedule Classification of the AES Candidates
http://csrc.nist.gov/archive/aes/round1/conf2/papers/carter.pdf
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · Challenges · Next Topic »
Add Reply