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
Modified Vernam Cipher ("MVC"); A new(?) cipher variant proposed
Topic Started: Jan 24 2014, 05:29 PM (866 Views)
otelin
Just registered
[ * ]
Modified Vernam Cipher ("MVC")


Vernam Cipher (or One-time pad) is theoretically unbreakable given certain assumptions but it has the annoying feature that the key can securely be used just once. Here's a suggestion how to avoid the limitation.

First you generate a set of truly random byte arrays (like the truly random key in the Vernam Cipher). How you get them is up to you. For example you get 1000 arrays of million random bytes each (e.g. bytes in the range of 0...255, or 33...125 as in the figure MVC.png). The arrays need to be generated just once (they are fixed), and can be saved on a disk. See the upper table of the figure where you have the generated random arrays numbered 0...N (N = 1000 in the example). The arrays are identified by their number 0...N.

The length of the arrays (i.e. a million bytes in the example) must be at least as long as the plaintext (just like in the Vernam Cipher). In other words, with million byte arrays you can encrypt a million byte plaintext at most.

Next you need to randomly pick for example 50 arrays from the set of 1000 arrays. Each array can be picked just once (no repetition) because using an array twice in an XOR operation (see below) would just undo its effect. So basically you generate 50 unique random numbers between 0 and 999 to select the respective arrays. You can use a hashed password with salt or another method to determine the random (or "random") numbers, the exact algorithm or method is not proposed here.

You get the ciphertext from the plaintext by successive XOR operations (in the Vernam Cipher there is just one XOR operation per byte). For example you begin with the first byte "P" of PLAINTEXT (see the lower table of the figure) and XOR it with the first byte of the first random byte array ("m") - actually using ASCII codes 80 XOR 109 = 61. Then you XOR the result with "^", with ".", "d",... and finally with "S". You repeat the XOR operation M times (M = 50 in the example I'm using). As the result you get the first ciphertext byte "C" (of course it would really be something else with a high probability, as this is just an example clarifying the point).

To get the second ciphertext byte you apply the successive XOR operation taking the second plaintext byte "L", and XOR that with the second byte from each random byte array - i.e. "|", "u", ...).

To decrypt, you first select the 50 arrays from the set of 1000 arrays in exactly the same way as when encrypting and then reverse the rest of the algorithm, i.e. you start from the ciphertext and run the successive XOR operations to get the plaintext (byte by byte). The order of the 50 XOR operations doesn't matter - the end result is always the same. For example using some arbitrary ASCII codes:

17 XOR 58 XOR 4 XOR 244 XOR 103 = 188 (encrypt)
17 XOR 244 XOR 4 XOR 58 XOR 103 = 188 (XOR order doesn't matter)
188 XOR 103 XOR 244 XOR 4 XOR 58 = 17 (decrypt)
188 XOR 4 XOR 244 XOR 103 XOR 58 = 17 (XOR order doesn't matter)

Taking N = 1000 and M = 50, as in the example, there are 1000*999*998*...*951 / 50! = 9.5 * 10^84 possibilities to select the 50 unique arrays from the set of 1000 arrays saved on the disk (in the formula you divide by 50! because the order of the XOR operations doesn't matter). The assumption is that due to the true randomness of the 1000 fixed byte arrays a brute force attack is the only way to crack the ciphertext, even if you would know the random byte arrays, and the number of possibilities for that task is huge (and actually you can easily scale the big numbers up and down if needed).

This method sounds very secure to me, it is very understandable, based on an unbreakable method, and pretty easy to implement. But a drawback is that the method is very resource hungry: you need to have the random byte arrays saved (once) on disk (total 1 GB in the example), you are limited to encrypt a plaintext with a million bytes at most (as in the example), you probably would need to read all the selected 50 random byte arrays from the disk to memory (50 MB in the example) to use them efficiently, and the encyption operation is probably quite slow(?).

On the other hand, if the encryption is slow, so is the decryption when a brute force attack is concerned. And of course if you manage to keep the random byte arrays secret, even the brute force attack becomes practically impossible. But I think it is not necessary to keep them secret. What really matters is the selection of M random byte arrays out of N possible.

I'm almost sure I'm not the first one to think of this idea. Any reference to existing similar specifications or applications?

otelin
Attached to this post:
Attachments: MVC.png (141.9 KB)
Offline Profile Quote Post Goto Top
 
novice
Super member
[ *  *  *  * ]
Hi otelin,

George Foot in the early 1990's tried to market a scheme that has similarities to yours. His idea, as I remember, was to fill a CD-ROM with random numbers. The key for enciphering a message would be 5 addresses on the CD from which five streams would be taken of the length of the message. These five streams would be XOR'd with the message to provide the cipher text. Different keys would be chosen for each message and both sender and recipient would securely hold lists of these keys. It was envisaged that the CD itself would be in the public domain. The chance of breaking a message without knowing the keys was calculated to be some infinitesimal figure.

There was a brief discussion on this Forum some 5 years ago (I can't find the thread) in which it was pointed out that technology had progressed and the random data could be held on a memory stick.

Other than that I haven't come across any other cipher similar to yours.

novice
Offline Profile Quote Post Goto Top
 
otelin
Just registered
[ * ]
Thank you novice for the interesting background information!

I thought about this method a bit more and found some improvements and tweaks. Below is a skeleton of the algorithm I propose.

These improvements make sure that you really use each totally random pad just once ("one-time-pad"), and you can handle plaintext of any size (no more a limit of 1000000 bytes or whatever).

1) Produce 256 arrays of 1000000 random bytes each and save them as separate files on hard disk - this is needed just once and you don't need to keep the files secret. It is up to you how you generate the files, but make sure they are as close to true randomness as possible. Name the files e.g. Array000.bin ... Array255.bin for easy access.

2) Get a password from the user (result ---> P).

3) Produce a random salt string of 32 bytes (256 bits)- you can use a good PRNG for this purpose (result ---> S).

4) Concatenate P and S, and hash the result using a cryptographically secure hash function (hashed result ---> H).

5) Read H byte by byte until you get 128 non-repeating numbers between 0 and 255 referring to the numbered 256 files created in step 1. If you run out of bytes read from H, generate more by first concatenating P, S, and H and hashing the result using the same hash function to get a new H. Finally, array R = the list of generated 128 numbers.

6) Read numbers from R one by one and open the respective numbered files generated in step 1 one by one so that you XOR the file contents byte by byte (1st and 2nd file is a pair for XOR, then XOR the result with the 3rd file and so on). Once a file is read, close it. Finally you get an array of 1000000 bytes (the result of 128 XOR operations) stored in memory. Let's call the outcome X that will always be different assuming that the PRNG always generates a different S. It will always be different even if P would be the same.

7) Open the plaintext file F for reading.

8) Open the ciphertext file C for writing.

9) Write into C the salt S (32 bytes).

10) XOR the contents of X and F byte by byte ("one-time-pad"), and store the result into C. If F is bigger than 1000000 bytes, leave the file pointers F and C as-is, go back to step 3 to generate a new block of 1000000 bytes with S, H, R, and X changed but not touching P. As long as you always write the new S into C (32 bytes every 1000000 bytes), you can continue the process as long as needed. When F is completely read, the encryption process ends. Note that S generated by a PRNG does not affect the individual XOR operations at all, it just affects which 128 of the 256 truly random files are selected to the XOR process.

11) To decrypt, you simply reverse the process starting from step 2 except that you never generate S but you read it from C (you know that it is always 32 bytes long and stored in C every 1000000 bytes). And of course considering steps 7 and 8, you read from C and write to F to decrypt.

If you use 256 truly random byte arrays (see step 1) and R contains 128 numbers, the total number of possibilities for a brute force attack is around 5.8 * 10^75 which should be more than sufficient for any purpose. The huge number also makes sure that you will never use the same X twice ("one-time-pad").
Offline Profile Quote Post Goto Top
 
fiziwig
Elite member
[ *  *  *  *  * ]
1000 arrays might be overkill. Instead of picking 50 from a set of 1000, why not pick 50 from a set of 100, and then pick 50 different starting points within each of those arrays.

Or taking it even further, having one array of a million random bytes is nearly as good as having a million arrays of a million bytes because you have a million starting points to choose from. A single array XORed with sequential bytes from fifty different starting points within that single array might be just as good. (This is just a hunch. I have no statistics to back it up.)

So then, instead of having 50 choices selected from a pool of 1000 you have 50 choices selected from a pool of a million. In fact, you could get your 10^84 possible keys by selecting only 14 keys from a pool of one million, with each key being 6 digits long. (6*14 = 84 digit key).
Offline Profile Quote Post Goto Top
 
otelin
Just registered
[ * ]
Hello fiziwig,

The numbers (50 from 1000, or 128 from 256, ...) are not that important - they can be adjusted easily as needed. I have used the numbers just to make the examples concrete. The idea is important, and please see my second post containing major improvements.

I'm not sure if I understood your point about picking different starting points. Whatever that means, it should not contradict the two basic ideas of an OTP: 1) true randomness, and 2) a random array must never be used twice.

otelin
Offline Profile Quote Post Goto Top
 
fiziwig
Elite member
[ *  *  *  *  * ]
otelin
Feb 17 2014, 06:00 PM

I'm not sure if I understood your point about picking different starting points. Whatever that means, it should not contradict the two basic ideas of an OTP: 1) true randomness, and 2) a random array must never be used twice.
My only point was that when you start to use an array you don't necessarily have to start with the first byte of the array. I only need one array of a million bytes if I pick 14 different starting points in that array and then XOR plaintext(0) with array(a), array(b), array(c), ... array(n), and plaintext(1) with array(a+1), array(b+1), array(c+1), ... array(n+1), and plaintext(2) with array(a+2), array(b+2), array(c+2), ... array(n+2), and so on.

As long as the unordered set of keys {a,b,c,d,e,f,g,h,i,j,k,l,m,n} was only used once the resultant "OTP" would never be reused.

I think the two conditions are met this way requiring only one array of 1 million bytes. Now this is off the top of my head, and I haven't thought deeply about it, and there may be a flaw in my reasoning having to do with overlapping ranges within that array, but I suspect that's not the case. I don't believe that any two non-identical sets of keys would have any similarity to each other. Even a known plaintext attack couldn't tease out any one of the individual 14 different streams.

Re: The second post. If your password is short it can still be attacked by brute force.

otelin
 
If you use 256 truly random byte arrays (see step 1) and R contains 128 numbers, the total number of possibilities for a brute force attack is around 5.8 * 10^75 which should be more than sufficient for any purpose.


But if your password is "TopSecret99" it doesn't matter what happens after the password is typed in. What matters in this case is how strong a password is selected. Having a long random key is vital. The key should be long enough to encode all 128 selections, 0-255.

Using {a..z;A..Z;0..9;?&} or 64 different characters, your password would have to be 144 characters long to be as strong as it can be under this system. If you're only going to have a 30 character password then anything more than 1.53E54 possibilities is wasted. That works out to between 22 and 23 arrays picked, rather than 128.

Anyway, there's no point in over-engineering the system beyond the strength of the weakest link.

It would also help to make order significant. A XOR B XOR C is the same as B XOR C XOR A, or any other order of those three. But, if you do something like A XOR ((B XOR (C*3 mod 256))*5 mod 256) then order does matter and you get many (many, many, many) more different keys.

Details aside, I like this approach. I think it has a lot of promise.
Edited by fiziwig, Feb 18 2014, 12:17 AM.
Offline Profile Quote Post Goto Top
 
osric
Super member
[ *  *  *  * ]
If you use a hash algorithm, there is no need for the pools of random numbers.

All you need is a secure key (long enough to be impossible to brute force).

The computer can make a salt, add it to the key and then make random numbers from the hash.

For example if you use SHA512, you get 64 hex numbers every hash. Use the key with salt appended for the first hash. For more random numbers, use the first hash to make a second hash, and so on until you have enough for the message.

Encipher and decipher by Xoring the plaintext and random numbers, vigenering or whatever system you choose.

The computer can prepend to the ciphertext an indicator for the salt to be used on deciphering. All the receiver needs to know is the secure key.

Here is a GUI program you can run that enciphers and deciphers in this way. Note that with the same key you get a different ciphertext every time you encipher. This is because the time is different on each occasion, giving a different indicator and salt.

Reverse engineering the SHA512 algorithm from a probable word would be, I think, very difficult if not impossible.


Offline Profile Quote Post Goto Top
 
fiziwig
Elite member
[ *  *  *  *  * ]
osric
Feb 18 2014, 05:21 PM
If you use a hash algorithm, there is no need for the pools of random numbers.

All you need is a secure key (long enough to be impossible to brute force).

The computer can make a salt, add it to the key and then make random numbers from the hash.
---

That makes sense.

How about appending the keyphrase to the first hash to get the second hash. Otherwise, in the unlikely event the enemy discovered the first hash, all subsequent hashes would be exposed. That's a small detail since the odds of finding the first hash are so small, but what the heck.
Offline Profile Quote Post Goto Top
 
osric
Super member
[ *  *  *  * ]
fiziwig
 
How about appending the keyphrase to the first hash to get the second hash.


Yes, why not indeed!
Offline Profile Quote Post Goto Top
 
fiziwig
Elite member
[ *  *  *  *  * ]
Or, to get really retro, use a straddling checkerboard to encode the message AND the alphabetic keyphrase into a decimal number, devise an easy-to-use paper-and-pencil decimal hash method, and turn the whole thing into a secure paper-and-pencil encryption method.

The only trick is to work out a decimal hash algorithm that could be easily performed without a computer.
Offline Profile Quote Post Goto Top
 
mok-kong shen
NSA worthy
[ *  *  *  *  *  * ]
I can't exclude my view being quite biased. But, if a standard hash algorithm is employed for purposes of the present context, I wonder whether it wouldn't be just as well, or perhaps even more advantageous in practice, to use AES in counter mode.
Offline Profile Quote Post Goto Top
 
osric
Super member
[ *  *  *  * ]
fiziwig
 
The only trick is to work out a decimal hash algorithm that could be easily performed without a computer.


Here's one approach:

Key: ZETABOARDS

First part of hash from ZETAB:
Z = dec 25 = bin 11001
E = dec 04 = bin 00100
T = dec 19 = bin 10011
A = dec 00 = bin 00000
B = dec 01 = bin 00001

1st col = bin 10100 = 18
2nd col = bin 10000 = 16
3rd col = bin 01000 = 8
4th col = bin 00100 = 4
5th col = bin 10101 = 21


1st part: = 18 16 8 4 21

Following same procedure, second part of hash from OARDS = 5 16 16 19 6

Complete hash (!) =18 16 8 4 21 5 16 16 19 6

Use the hash to encipher by Vigenere

pt: mary had a li

12 00 17 24 07 00 03 0 0 11 8
18 16 08 04 21 05 16 16 19 06

ct: EQZCC FTQEO


Continue by hashing the hash.
Edited by osric, Feb 19 2014, 01:34 PM.
Offline Profile Quote Post Goto Top
 
dave321
Member Avatar
Member
[ *  * ]
just out of interest have you seen the otp system below ?

http://www.nonview.com

maybe it uses a similar sort of system to make sure the pads are only used once

not worth the money though

dave

Offline Profile Quote Post Goto Top
 
fiziwig
Elite member
[ *  *  *  *  * ]
dave321
Feb 19 2014, 07:30 PM
just out of interest have you seen the otp system below ?

http://www.nonview.com

maybe it uses a similar sort of system to make sure the pads are only used once

not worth the money though

dave

They sure like throwing around that word "Quantum". What it probably means in this context is that a tunnel-diode based hardware RNG is used to generate the random stream on the CD or stick. After all, I tunnel diode does depend on quantum tunneling to work.

As for their claim that any alteration makes the data un-decipherable, that also means any transmission error will make the text un-decipherable also. Sounds like an autokey, or some other system that propagates errors throughout the file.

PR hype aside, I'm sure it could be just as good as they claim.
Offline Profile Quote Post Goto Top
 
mok-kong shen
NSA worthy
[ *  *  *  *  *  * ]
otelin
Jan 24 2014, 05:29 PM
Vernam Cipher (or One-time pad) is theoretically unbreakable given certain assumptions but it has the annoying feature that the key can securely be used just once. Here's a suggestion how to avoid the limitation.

Sorry for a question: What is the consequence of that modification and usage? Is it still a one-time pad or rather a "multiple-time" pad and hence doesn't have the "same" merit as the one-time pad?
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
Go to Next Page
« Previous Topic · General · Next Topic »
Add Reply