November 26th, 2012, 07:47 AM
Home-grown algorithm advice needed
I've devised a home-brew symmetric encryption algorithm, and would like some advice as to how secure/insecure it is.
I know about the dangers of doing this, but the decision was to a large extent forced by the need to have processes performing the encryption/decryption, where those processes are running on completely differing platforms and/or environments and/or languages, and where secure encryption libraries were either not available on all platforms or were incompatible. One of the platforms is a very simple scripting language built into a software terminal emulator, which only has basic integer maths operations and functions, basic string/substring functions and a few basic logic functions like xor... it doesn't even have arrays.
Here are the details of my scheme:-
I have 3 different home-brew PRNGs (lets call them PRNG1, PRNG2 & PRNG3), each of which produces a different stream of 100,000 PRNs before repeating).
I then start three iterations or rounds:-
I produce a random number, R (in the range 0-100,000) from the system random number generator - *not* using my home-brew PRNGs.
I use R as a seed for my PRNG (PRNG1 for round 1, PRNG2 for round 2, PRNG3 for round 3)
Using the chosen PRNG & seed, the plaintext is XOR'd against the stream of PRNs generated to produce the cyphertext.
R is appended to the cyphertext.
Repeat steps 1-4 twice more for rounds 2 & 3, where the cyphertext of one round becomes the cleartext of the next, and each round has its own uinque R value.
The receiving end decrypts the cyphertext, by extracting R from the cyphertext at the beginning of each of 3 decryption rounds, the reversing the xor operations.
The code that implements this is not publicly available, and only cyphertexts are publicly available, i.e. known plaintext attacks are not possible.
The basic idea is.. each of the 3 rounds of encryption has a unique R, each of which produces a unique pseudo-random string of bytes, which when xor'd together produce a one-time pad unique to that combination of three Rs. This is xor'd with the cleartext. Obviously it is only a *one-time* pad, if the combination of three Rs (i.e. pseudo-random string) is never re-used. In my scheme, because each of the three Rs can take the value 0-100000, that means a particular pseudo-random string will only be re-used every 1e15 (100000 times 100000 times 100000) encryption events, and is therefore so rarely re-used it is close to being a one-time pad. I calculate that if encryption events occur at a rate of 1000 per second, then a specific permutation of the three Rs (and hence of the one-time pad), will only get re-used once every 31000 years - good enough for my purposes.
One of the advantages of my scheme is that I do not have to store passwords in the different processes, or perform password updates/synchronisations between them.
I know that the security of this scheme depends on the cryptographic security of the PRNGs, I have done some simple tests on my PRNGs, but cannot claim that the tests are cryptographically thorough. My PRNGs are of the form:
R_new = ((R_old x M) + C)
where M & C are chosen carefully, and R is the generated random number. I understand this is called a Linear Congruential generator.
I don't see a problem with including the R values in the cyphertext, because they alone do not give enough information to predict the PRNs... the values of M & C are also needed.
I welcome suggestions as to how someone might break this scheme, as well as suggestions for improvement, and if any of my reasoning is faulty.
I welcome any suggestions for better PRNGs or encryption algorithms, where source-code is available, and which are easily coded in a very simple programming language that does not have arrays. I would need access to source-code because I am not confident of implementing an algorithm (that I do not understand) securely using only a verbal description.
If you have questions about any details (maybe because I have not explained it clearly), please feel free to ask.
Many thanks for your help & advice.
November 26th, 2012, 12:49 PM
Since posting my original question, I've done some testing, and it seems the above is not correct. In fact, some repetitions of combinations of the three Rs will start to appear much more quickly than I assumed... probably after only about 2e11 encryptions rather than 1e15 as I assumed. This looks like it might be the same as the "birthday paradox". However, my test was looking for a repetition of *any* combination of R's, but several cyphertexts (maybe as many as 5-10?) using the same specific combination of R's would be needed to break it using frequency analysis. So maybe this is still relatively secure?
Originally Posted by ad1mt
Any help most welcome...
November 26th, 2012, 01:11 PM
Who's your adversary?
Bored kid in a bedroom or "Three Letter Agency"?
How far do encrypted messages have to travel, over what kind of interface?
1m down a serial cable from a hand-held terminal to a local machine is a different problem to machines on different continents communicating over the internet.
What is the value of the information. IE, what do you lose if someone breaks the system? $100 / message perhaps? More? Less?
How many messages before you're likely to notice that something is wrong?
November 26th, 2012, 06:00 PM
Your algorithm might work if you're trying to keep something hidden from your kid sister, but I wouldn't chance it against a more skilled attacker.
Why? Because if someone gets hold of your decryption program, your security is in big trouble. The random seed is enclosed as part of the message, so if the person knows your three PRNGs, they can easily decrypt any message of yours. Your whole premise that the code is not publicly available is bad (security through obscurity is never a good idea). Remember, Claude Shannon said that a crypto algorithm should never depend on the algorithm being part of the security, only the key.
Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne
"I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo