Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

First, I'm really not into cryptography, but have some basic knowledge. This was a thought experiment (and later exercise for my programming skills), but even though it was long time ago and I tried to speak about it with some people, I didn't get any feedback that would dismay or confirm strength of this concept. So, dear experts, please can you assess this model as valuable, already invented or shallow. Thank you in advance!

It may look it has similarities with classical PRNG stream chipper, but there is a conceptual difference that makes it (possibly) stronger. Text is encrypted based on index location of first found character in PRNG stream (i.e. letter 'D' is found in a stream after 26 generated numbers for that seed and 26 is written into temporary file, than letter 'e' is found after 12 next generated numbers (or ASCII code equivalent) and so on. Now, we don't stop here because it would be pretty easy to brute-force all seeds and stop when we find few meaningful letters (dict or similar). We repeat the process for temporary file (26,12, ...) with same seed. Part of the passcode is dedicated not for seed but for depth (number of depth levels). In this way brute-force decrypter wouldn't know should it skip any of tested seeds or it should use "decrypted" numbers as base for next level of decryption. 5, 10, even 200 levels would be easy for decryption with known pass (seed), but extreme for brute-force.

As I was advised, I'll try to be much more elaborate, so I'll start with example (the idea itself is really simple):

We have text file with following content we want to encrypt:

"Hello World"

The passcode is 5-123456

Encryption app encrypts in following manner:

  • It uses second part of the pass (123456) as a seed for PRNG and firs part (5) as a depth level (will explain later)
  • Program starts to generate RND from this seed in sequence and checks if first character ('H') ASCII is matched (RND is limited to generate numbers fro 0 to 255).
  • Lets say this is the sequence of numbers generated: 21 4 154 (72) 35 66 (101) 100 72 (108) 22 8 9 23 (108) 55 …..
  • After 4 generated numbers we have a match of character H (72), after 3 more we matched e (101), next 3, ther is l (108), 5 l(108) and so on.
  • We put sequence 4,3,3,5 into temporary file (or array or anything). Here we have encrypted data, but this is piece of cake for brute-force app that finds "Hell" in dict.
  • So we do it again, now with "4,3,3,5,…" as our input data. We are going through PRNG sequence searching for ASCII of 4, 3, 3, 5.
  • Now things are getting really complicated for brute force engine beacuse there is no dict with "4, 3, 3, 5,…" in it. Of course, it could try using positions from all possible seeds in first run and look what chars it returns in second against dict, but we will do it 3 more times as '5' in our passcode means 5th level of depth and that many runs we'll use in encrypting our text.

It is now 2ˆ32 * 2ˆ32 * 2ˆ32 * 2ˆ32 runs it has to go and it doesn't know how to optimize(where to stop) because there is no dict for random numbers sequence.

I hope this is extensive enough to explain the idea, but of course I'm here if there is additional info needed.

Thank you in advance for assessing this idea of mine.

Regards,

Nenad

share|improve this question
1  
Could you please elaborate on the depth levels? –  Tie-fighter Jul 6 '12 at 14:05
    
So, as I said, when you do first pass, you put positions of found letters into temporary file (or array or anything) then you use this file again as input, just this time searching for 1st, 2nd, 3rd,... number from this temporary file and not initial text file, and than repeat. Number of repetitions is depth level and it is not known without the pass. Sorry if I was unclear first time. –  Nenad Mandic Jul 6 '12 at 14:10
    
I might have understood it, but please edit your answer to provide an example with a depth of e.g. 3, so everybody can easily understand. Bonus points for diagrams ^^ –  Tie-fighter Jul 6 '12 at 14:24
    
OK, I will. I'm on my way from office so as soon as I get home. Thank you for advice, I'm new here :-) –  Nenad Mandic Jul 6 '12 at 14:34
    
@Nenad - here we do have crypto questions where the focus is on implementation in a professional environment (eg when you have your crypto application, how do you ensure it works and is controlled as expected). I'll pop this over to Crypto, but agree you will need to flesh it out a lot more to get it accepted. –  Rory Alsop Jul 6 '12 at 15:16
show 1 more comment

migrated from security.stackexchange.com Jul 6 '12 at 15:17

This question came from our site for Information security professionals.

1 Answer

Well, it's a given that a newbie cipher is either insecure or overcomplicated. You, sir, are on the overcomplicated side.

Now, your cipher sounds simple; however, consider what a computer would need to actually encrypt with this cipher. It would need to seed a PRNG, generate an expected 256 times the plaintext length (so to encrypt a 11 character "Hello world" message, we'd need (on average) to generate almost 3k of PRNG data), and then go through that data, and compare each byte to the next plaintext character. If we make the wildly optimistic assumption that a CPU can generate a byte of PRNG data and test it in a single cycle, well, you're taking an expected 256 cycles to encrypt each byte; in contrast, AES can be done in about 17 cycles. And, this is all assuming a depth of 1; if you increase it, well, that increases your encrypt time as well.

In addition, your cipher has another problem; ciphertext expansion. To encrypt a character 'H', you scan the PRNG for the next occurance of 'H'; however, the character 'H' might not show up in the next 256 characters. Instead, we might have to scan (say) 519 characters before we stumble across an 'H'. This means that the ciphertext would need to be 519; however, 519 can't find into a single byte. That means that we need to encode it somehow, and that encoding is going to be longer than the original plaintext. A variable length encoding may reduce this expansion; however if it is only 20% per depth, that means that a depth of 5 more than doubles the ciphertext, while a depth of 200 means that to encrypt a single character, you'll expect to need about 6 Petabytes; that sounds a tad excessive.

As for cryptanalytic results, well, if the PRNG is Mercenne twister, and depth is 1, you can recover the passphrase if given the encryption of a known large plaintext. That's because with known plaintext and depth of 1, you're leaking byte values of the PRNG stream at known locations; with Mercenne twister, that is enough to recover the original state. On the other hand, if the PRNG is cryptographically secure, then the construction is safe (albeit far more expensive than just a standard stream cipher).

share|improve this answer
    
Thank you for your assessement. I must agree with CPU expense you predicted, but as I remember, back in 1994 on my 386 SX 25Mhz machine it did 10-level depth of 1K text in pretty reasonable time. I should write it again and test it how it measures against today's hardware. Of course, this method wouldn't be much useful in real time encryption. –  Nenad Mandic Jul 6 '12 at 16:42
    
It was (at that time, but also today) targeted at maximum security of static data so I would really liked a proposal how to measure it against currently available methods in this area of use. As I mentioned, I'm not an expert in the field, but surely there is need for uncrackable encryption so my question is, would this be (reasonably) crackable with available HW? –  Nenad Mandic Jul 6 '12 at 16:42
    
Responded in a hurry, still thinking about it. I didn't thank you enough, sir. This is first valuable feedback I got. I will invest some more time into seeking possible solutions of obstacles you mentioned (CPU intensive, chipper expansion). I also thought of one more. If attacker tries (in first run) one seed and that one returns ASCII codes of certain mix of numbers and letters, he can dismiss it. If he finds only numbers, he got it (most likely). Need to think this over. Still, have a gut feeling, this method has some potential :-) Again, thank you, and if you have some more advice, please –  Nenad Mandic Jul 6 '12 at 17:19
    
@NenadMandic - You do understand that is a pretty big flaw right? It was for similar reasons WPS and WEP were determined to be broken. –  Ramhound Jul 6 '12 at 17:43
    
@Ramhound: well, no, the flaws of WEP were considerably different. The killer problem was that the key scheduling leaks key bits. Other problems were that two different packets with the same IV shared the same keystream, and the utter lack of integrity protection (it was easy to modify an encrypted message whose contents you knew into anything you wanted it to say). –  poncho Jul 6 '12 at 18:04
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.