A simple encryption cipher... Thoughts?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
nyeguy
Posts: 580
Joined: Sat Aug 04, 2007 5:59 pm UTC

A simple encryption cipher... Thoughts?

Postby nyeguy » Sun Apr 11, 2010 2:26 am UTC

Mods, I wasn't sure where to put this, so I apologize if it needs to be moved.

I was working on a cypher earlier today, when I started thinking about ways to make a cypher harder to crack. So I thought that, if I were to use a different cypher on different segments of the text, it would be orders of magnitude more complex to solve.

I figured a Caeser cipher would be easiest to work with, from a known character set. My algorithm starts with the plain text, and a key. The key is a set of two 2-digit numbers. The first number is the shift for the cipher. The second number is the segment length, and determines how many characters I use this cipher on. So the key 4513 means I will take the first 13 characters from the string, and append a new key to it. This will be the key used for the next segment. This segment, including the key, is shifted 45 characters through my character set. I repeat this until the entire cleartext is encoded.

To decrypt, you reverse this process. You only need the key for the first segment, since when you decode each segment, you get the key for the next one.

For example: "The quick brown fox jumped over the lazy dog." with the key 9524 becomes "gVN"5,)a7"^%w6m"qwP"0,`tI2k(? F7'?OF#y?F=,SqF 7/kaU~H". You can grab the source code to my python script if you wish.

It obviously has the same weaknesses as any other cipher, in that you have to give someone a key and the character set ahead of time for it to be decoded, and compromising the key compromises the algorithm. But does this make sense as a simple way to generate codes?
Image

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby jareds » Sun Apr 11, 2010 7:37 am UTC

If I wanted to decipher this by hand, I'd go through the message character by character from the beginning, looking for groups of 4 characters that could all be digits under the same shift value. False positives would be rare and would quickly be obvious. For each such group, there would only be a handful of ways to make them all numbers, and again the incorrect choices would quickly be obvious.

Or, maybe I would try each shift value for the start of the message. Caesar cipher is weak, even by hand.

What are your goals here?

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby cogman » Sun Apr 11, 2010 1:28 pm UTC

As was already stated, but bares repeating. the Caesar cipher is weak. Just looking at the encrypted output, it becomes obvious pretty quick that " is a space (the distance between "s looks a lot like the distance between words).

This cipher is working on the premise of security through obscurity, which is a bad paradigm for a cipher. Once the ciphering method is known, any key generated by this cipher is instantly compromised. It is vulnerable to a multitude of attacks from known message, to statistical analysis.

In short, any encryption algorithm that uses the Caesar cipher in any way is fundamentally flawed.

Check out encryption methods like RSA, DES, and AES, for examples of how a good cipher is implemented. If you aren't rotating bits and doing matrix swaps, or using modular arithmetic in some inventive way, you probably aren't creating a strong encryption method.

(I've always found RSA particularly fascinating. It looks so simple, yet, to this day, remains one of the most secure encryption methods out there)

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: A simple encryption cipher... Thoughts?

Postby Meteorswarm » Sun Apr 11, 2010 4:23 pm UTC

The thing is, there are no (to my knowledge) strong encryption methods that you can perform by hand, so if you want one you can do by hand, you'll need to pick something you think is obscure enough to fool people. Caesar shifts are not strong enough.

One method I've seen is to, rather than shift a constant amount, shift the first letter up, then the second letter down, the third up and so on. Almost as easy as caesar but harder to crack since most people don't think to test against it.

Of course, now that I've posted it, the game's out...
The same as the old Meteorswarm, now with fewer posts!

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: A simple encryption cipher... Thoughts?

Postby headprogrammingczar » Sun Apr 11, 2010 4:31 pm UTC

One-time pad is easy to do by hand, and is also uncrackable unless someone gets your key.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
nyeguy
Posts: 580
Joined: Sat Aug 04, 2007 5:59 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby nyeguy » Mon Apr 12, 2010 2:19 am UTC

The goal wasn't really to create a good encryption system... I was just playing with the idea. Obviously it isn't as good as things like RSA, and I said in the OP that I knew it was still fairly weak. It was more of a little thought experiment of mine.

My thought was that part of why Caesar shifts are so weak is that they are easy to find patterns in to crack even if you don't know going into it what the code is. I thought that using this sort of segmented encoding obscures patterns, since each part is different, and so is a bit harder to crack.
Image

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: A simple encryption cipher... Thoughts?

Postby BlackSails » Mon Apr 12, 2010 4:42 am UTC

headprogrammingczar wrote:One-time pad is easy to do by hand, and is also uncrackable unless someone gets your key.


Its also pretty easy to screw up, and depending on how you screw it up, could render most of your message junk.

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby cogman » Thu Apr 15, 2010 1:41 pm UTC

BlackSails wrote:
headprogrammingczar wrote:One-time pad is easy to do by hand, and is also uncrackable unless someone gets your key.


Its also pretty easy to screw up, and depending on how you screw it up, could render most of your message junk.

By that notion, a Caesar cipher is also pretty easy to screw up, and depending on the type of cipher (IE, is it segmented) could equally render most of your message junk.

Ciphering in general is something that is easy to screw up by hand.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11088
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A simple encryption cipher... Thoughts?

Postby Yakk » Fri Apr 16, 2010 4:36 pm UTC

The punchline is that one time pads are Caesar ciphers with a different cipher for each character.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

Re: A simple encryption cipher... Thoughts?

Postby Agent_Irons » Fri May 14, 2010 11:23 pm UTC

You might want to look into the Vignére cipher, which is a caesar cipher with a mnemonic keyword that changes the length of the shift in a repeating pattern. The generalization is better, but then you need the entire 26x26 square. The upside is then you have 26 substitution ciphers to choose from. It can be broken from nothing automatically these days, though. Ciphertext to plaintext, revealing the keyword while you're at it.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby WarDaft » Tue May 18, 2010 2:50 pm UTC

Meteorswarm wrote:The thing is, there are no (to my knowledge) strong encryption methods that you can perform by hand, so if you want one you can do by hand, you'll need to pick something you think is obscure enough to fool people. Caesar shifts are not strong enough.

One method I've seen is to, rather than shift a constant amount, shift the first letter up, then the second letter down, the third up and so on. Almost as easy as caesar but harder to crack since most people don't think to test against it.

Of course, now that I've posted it, the game's out...

You could do a single digit MWC by hand pretty easily. Still not considered cryptographically secure, but for the minimal effort it takes it's not too shabby.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

mroctogon
Posts: 17
Joined: Fri Feb 29, 2008 1:26 am UTC

Re: A simple encryption cipher... Thoughts?

Postby mroctogon » Tue Jun 22, 2010 4:33 am UTC

The wikipedia article on the Nazi Enigma machine (http://en.wikipedia.org/wiki/Enigma_machine) is fascinating. Basically, it is a series of cyphers that changes after each character. Even this complicated cypher was broken by some brilliant mathematicians using minimal technology. The weakness is that if you know the initial configuration you can read any message. The allies were able to look for words they thought would be in the message, and reverse engineer the start state from matches there, and other captured information. An enigma simulator is a project I would recommend to anybody who wants to explore cyphers. An enigma bomb is a project I would recommend to anybody who wants to be blown away by awesome maths.

heelium
Posts: 118
Joined: Mon Jun 28, 2010 3:47 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby heelium » Wed Jun 30, 2010 2:43 am UTC

I highly favor one cipher:

1. Take the total length of all files you are possibly going to encrypt and send from A to B. Let's call this length total_length.
2. Seek for some hardware based good random number generator.
3. Produce a file with length total_length + sizeof(int) containing one zeroed integer at beginning and otherwise only random characters.
[4. Do the same for files you are possibly going to encrypt and send from B to A.]

Now, you have a stream of random characters. Let's say that key.getByte(x) returns byte at position x after integer at beginning of this file. Also, key.getPos() returns zeroed integer at beginning and key.setPos(pos) changes it and saves the change; key.getLen() returns length of key (generated file) in bytes without counting integer at beginning.

Now, encryption looks like that (all size units are bytes):

Code: Select all

function encryptFile(inFile, outFile, key) {
    pos := key.getPos();
    outFile.writeInt(pos);
    for (i = 0; i < inFile.getLen(); i++) {
        if (pos > key.getLen()) {
            throw KeyExhaustionError();
        }
        outFile.writeInt(inFile.getByte(i) XOR key.getByte(i + pos));
        pos++;
    }
    key.setPos(pos);
}


This is impossible to break. It could not be used for internet connection, but it can be used on short and important messages ...one CD filled with keys should be enough to have something like twitter running for hundreds of people to resist pretty long time. Each person might have a personal code stored at beginning of crypted file followed by key number - this allows them to generate new keys, share each key with people they want to make this information available to and have it all encrypted.

Ideal method for breaking keys would never break that one.

It has an advantage that files generated that way contain total noise - if key is made up from true random numbers, it directly follows that each encrypted file contains totally random numbers. You must only ensure that file length does not give you up - the best way to ensure that is to think out the maximum number of bytes you send per day, divide it into ten-minute-chunks and send a chunk with fixed length every ten minutes (unless you are also hiding a radio signal or internet traffic). Such kind of problems will stay.

Also, you can use another trick thought out for quite a while ago - when you take some pixel image and choose some bits you are going to use for encrypted images, you can make it so that those bits look like a random chaos. Then, receiver must also have those images in original form. You can randomly generate a set of bits, which will contain noise - every third or every tenth pixel is not a good idea, because it looks like chaos. Article, where I did read this pixel-noising method, told that such pictures are just added to some web page - today, adding a few pictures to some blog each day would very much hide any kind of such information sharing. Anyway, I'm pretty sure that for every camera, one can build a database of normal patterns produced by this camera - I think that last-pixel-noise will be somewhat similar for each picture of some camera type; some cameras will probably just zero the last pixel anyway as they won't detect so slight things. So, this is possible to detect by a clever bot that some blogs are used that way ;) You shouldn't mess with government with that method as they might already detect such things and visit you if you are not obviously playing LARP :P ...especially in Germany, I think.

Alnasi
Posts: 2
Joined: Wed Feb 17, 2010 12:47 am UTC

Re: A simple encryption cipher... Thoughts?

Postby Alnasi » Mon May 13, 2013 7:12 am UTC

Re: A simple encryption cipher... Thoughts?

by heelium » Tue Jun 29, 2010 6:43 pm UTC

I highly favor one cipher:

1. Take the total length of all files you are possibly going to encrypt and send from A to B. Let's call this length total_length.
2. Seek for some hardware based good random number generator.
3. Produce a file with length total_length + sizeof(int) containing one zeroed integer at beginning and otherwise only random characters.
[4. Do the same for files you are possibly going to encrypt and send from B to A.]

Now, you have a stream of random characters. Let's say that key.getByte(x) returns byte at position x after integer at beginning of this file. Also, key.getPos() returns zeroed integer at beginning and key.setPos(pos) changes it and saves the change; key.getLen() returns length of key (generated file) in bytes without counting integer at beginning.

Now, encryption looks like that (all size units are bytes):

Code: Select allfunction encryptFile(inFile, outFile, key) {
pos := key.getPos();
outFile.writeInt(pos);
for (i = 0; i < inFile.getLen(); i++) {
if (pos > key.getLen()) {
throw KeyExhaustionError();
}
outFile.writeInt(inFile.getByte(i) XOR key.getByte(i + pos));
pos++;
}
key.setPos(pos);
}

This is impossible to break. It could not be used for internet connection, but it can be used on short and important messages ...one CD filled with keys should be enough to have something like twitter running for hundreds of people to resist pretty long time. Each person might have a personal code stored at beginning of crypted file followed by key number - this allows them to generate new keys, share each key with people they want to make this information available to and have it all encrypted.

Ideal method for breaking keys would never break that one.

It has an advantage that files generated that way contain total noise - if key is made up from true random numbers, it directly follows that each encrypted file contains totally random numbers. You must only ensure that file length does not give you up - the best way to ensure that is to think out the maximum number of bytes you send per day, divide it into ten-minute-chunks and send a chunk with fixed length every ten minutes (unless you are also hiding a radio signal or internet traffic). Such kind of problems will stay.

Also, you can use another trick thought out for quite a while ago - when you take some pixel image and choose some bits you are going to use for encrypted images, you can make it so that those bits look like a random chaos. Then, receiver must also have those images in original form. You can randomly generate a set of bits, which will contain noise - every third or every tenth pixel is not a good idea, because it looks like chaos. Article, where I did read this pixel-noising method, told that such pictures are just added to some web page - today, adding a few pictures to some blog each day would very much hide any kind of such information sharing. Anyway, I'm pretty sure that for every camera, one can build a database of normal patterns produced by this camera - I think that last-pixel-noise will be somewhat similar for each picture of some camera type; some cameras will probably just zero the last pixel anyway as they won't detect so slight things. So, this is possible to detect by a clever bot that some blogs are used that way You shouldn't mess with government with that method as they might already detect such things and visit you if you are not obviously playing LARP ...especially in Germany, I think.


But isn't that just an electronic version of a one-time-pad? It still has key management problems. Both with compromise and with discoverability. What we need here is a pencil and paper CSPRNG, and as far as I know, one easy enough to run a message long string does not exist. I bow to superior knowledge. Pencil and Paper CSPRNG, anyone?

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6301
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: A simple encryption cipher... Thoughts?

Postby Thesh » Mon May 13, 2013 8:42 am UTC

One thing you could do is apply chaining via addition modulo n where n is the number of characters (which can be done quickly since if a+b > n then you subtract n).

For example, let's take a simple case of a substitution cipher with 26 letters, where A=0, B=1, ..., Z=25.

Key = BCDEFGHIJKLMNOPQRSTUVWXYZA

Input = THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOG
Output = UCHYTCFQSKZWKQFDNIVLQUJFKMGOTFGFEIXD
(note that I did this by hand, and I didn't check to see if I made mistakes)

It doesn't add secrecy, but it reduces the patterns and it can take a cryptographer longer to figure out what you are doing if they don't know already. If they do know what you are doing, then all bets are off.

Also, if you want to get more time consuming (assuming pencil and paper). Lets say you had a randomly chosen secret key, and then you prepended your message with another known key. Take the known key, run it through the secret key and use the new key to encrypt the first character. Take the new key, run it through the secret key again, and keep repeating until the message is encrypted.
Summum ius, summa iniuria.

wumpus
Posts: 533
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: A simple encryption cipher... Thoughts?

Postby wumpus » Mon May 13, 2013 6:31 pm UTC

To expand "pen and paper" to "pen, paper, and a deck of cards" consider the solitaire cipher (cryptosystem):
http://www.schneier.com/solitaire.html
This is believed to be in roughly the security level of AES finalists (some serious attempts at breaking it and failing) as opposed to well known means of breaking it: Caesar encryption is weaker than cryptojumbles included in newspapers (they tend to have random letters assigned), the means to break Vignére was fairly well known by the US Civil War (1861-1865) but only well known enough that the North knew it and the South kept using Vignére.

One-time pads (the "random" code above) works fine if you are sending it to someone who already has your random files (you gave them a DVD-R with 4.7G of noise, perhaps). If you haven't sent the random noise: you now have two problems (send the noise and send the encoded file). Note: reusing a one-time pad is a known huge mistake and changes the code from "unbreakable assuming a decent source of noise" to "easily breakable, or at least large sections of your files get known".

It all depends on what you want your cryptosystem to do. If you want to learn programming, writing a Caesar cipher works. If you want to learn anything about cryptography, you might want to take a step back and consider various levels of cryptographic codes:

stuff you can do with pen & paper (except solitaire)
: breakable by anyone who googles it and codes up the break.
Stuff you come up with on your own and code into a computer: likely included in introductory cryptanalysis texts as a "basic cipher for beginners to break" (people finding their early ideas included as such is pretty much a cliche in cryptography).
Basic open cryptosystems (AES, SHA256, SHA-3, RSA): Unbreakable by any but the most elite intelligence agencies. If you code it right, likely not by them as well. Even if they decode such a file, it will never be passed outside or acted on a way that might imply that they decoded it (like criminal or civil prosecution). There is always the danger of using even strong encryption to store your photos and having your grandchildren use google2100 to see picures of you gasp smoking in front of your gasp, and fall down fainting, car. But most encryption threats tend to be password guessing, password stealing (see "buy your password for a candybar"), stealing the plaintext (probably with a virus or some other malware or social engineering).

KnightExemplar
Posts: 5494
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby KnightExemplar » Thu May 16, 2013 5:21 am UTC

http://www.opensource.apple.com/source/ ... /rc4/rc4.c

This algorithm is responsible for protecting your credit cards online. The majority of servers (SSL) use RC4 encryption right now. If you want "simple" and "secure", nothing gets there quite like RC4. That said, there are some caveats... the first 256 bytes of the cipher is considered weak... so just throw those away and you'll get better security.
First Strike +1/+1 and Indestructible.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6301
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: A simple encryption cipher... Thoughts?

Postby Thesh » Thu May 16, 2013 5:33 am UTC

This is about pencil and paper ciphers, which RC4 isn't really suited for.

That said, RC4 is not that common anymore for SSL. Modern browsers (including IE7, Firefox, and Chrome) are going to prefer AES over RC4. There are also issues with the lack of support for an initialization vector built in and a weak key schedule, so if you are going to use it securely you need to use a cryptographic hash to combine the key and the IV. If you are going to use a software cipher for any new development, do not use RC4 and instead use AES.
Summum ius, summa iniuria.

lgw
Posts: 437
Joined: Mon Apr 12, 2010 10:52 pm UTC

Re: A simple encryption cipher... Thoughts?

Postby lgw » Fri May 17, 2013 7:07 pm UTC

Reordering the text isn't a bad "by hand" approach to encryption, but only because it's so hard to do any good encryption "by hand". Not my field, but apparently text reordering is reasonably easy to solve as an algebraic problem. I'd love to hear how, though, from someone who is in the field.

Abstractly, the number of ways you can reasonably re-order text by hand is a very small keyspace, but I couldn't tell you in practice how to efficiently brute force it.

As an aside, it's always worth remembering that XORing (or however you do you Caesar cypher interaction) two English documents together is properly viewed today as a compression technique, not an encryption technique.
"In no set of physics laws do you get two cats." - doogly

User avatar
Xenomortis
Not actually a special flower.
Posts: 1425
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: A simple encryption cipher... Thoughts?

Postby Xenomortis » Fri May 17, 2013 8:13 pm UTC

lgw wrote:As an aside, it's always worth remembering that XORing (or however you do you Caesar cypher interaction) two English documents together is properly viewed today as a compression technique, not an encryption technique.

Surely that would make it a really bad compression technique; far worse than it is an encryption method?
Image

wumpus
Posts: 533
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: A simple encryption cipher... Thoughts?

Postby wumpus » Fri May 17, 2013 9:10 pm UTC

Xenomortis wrote:
lgw wrote:As an aside, it's always worth remembering that XORing (or however you do you Caesar cypher interaction) two English documents together is properly viewed today as a compression technique, not an encryption technique.

Surely that would make it a really bad compression technique; far worse than it is an encryption method?


It is a "compressor function" in the cryptographic sense of n bits in and m bits out where n>m (m=2n). It has nothing to do with data compression (and you don't want to use plaintext as an encryption key. There is a famous bit of ciphertext that is said to tell the location of a gold mine: the broken bits have plaintext keys, the unbroken bits don't appear to). One last thing, there are three things a data compression program can do with encrypted data: try to compress it and fail (return a longer message), Do nothing and leave it as is, and break the encryption, compress the plaintext, store the encryption method and key so you can re-encrypt the plaintext after you uncompress it. Obviously, a compressor successful at doing anything other than "noop" mean something is wrong with your encryption.

User avatar
scarecrovv
It's pronounced 'double u'
Posts: 674
Joined: Wed Jul 30, 2008 4:09 pm UTC
Location: California

Re: A simple encryption cipher... Thoughts?

Postby scarecrovv » Sat May 18, 2013 2:53 am UTC

wumpus wrote:It is a "compressor function" in the cryptographic sense of n bits in and m bits out where n>m (m=2n). It has nothing to do with data compression (and you don't want to use plaintext as an encryption key. There is a famous bit of ciphertext that is said to tell the location of a gold mine: the broken bits have plaintext keys, the unbroken bits don't appear to). One last thing, there are three things a data compression program can do with encrypted data: try to compress it and fail (return a longer message), Do nothing and leave it as is, and break the encryption, compress the plaintext, store the encryption method and key so you can re-encrypt the plaintext after you uncompress it. Obviously, a compressor successful at doing anything other than "noop" mean something is wrong with your encryption.


I believe you're referring to the Beale ciphers. The decrypted one isn't actually an XOR. It's a series of numbers, which index into the Declaration of Independence. For example, the number 191 decrypts to the 191st word of the Declaration of Independence. Also, it is likely to be a hoax, for various reasons described in the article. It makes a fun story though.

wumpus
Posts: 533
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: A simple encryption cipher... Thoughts?

Postby wumpus » Mon May 20, 2013 5:17 pm UTC

Beale ciphers it is, although I was thinking along the lines of addition mod 26, as XOR wouldn't have been popular back then.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 8 guests