Crumble (New Cipher)

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:

Crumble (New Cipher); A pencil-and-paper cipher I made.
Topic Started: May 20 2009, 12:15 AM (150 Views)
dabombguyman	May 20 2009, 12:15 AM Post #1
Just registered Posts: 16 Group: Members Member #3,267 Joined: May 17, 2009	I think I've invented the most powerful paper and pencil cipher. It involves converting the characters into binary numbers, then using a poly-alphabetic substituion to replace the 1s and 0s. You can see it detailed (with an encryptor) here: Crumble Cipher Please let me know what you think, or if you see any weekness. Thanks! PS: If you think it's crackable then break this . . . OrdioWmxmBnhkJDZfJAXgIltmaBbGroujxPpImBbWaBXhqeljvFsMUZUDbhPhuUXFhzLuTmOGajlMlKIUBPG seCkJHfsUqmKIuiEUAhLnDYDczUPFjgvOjBgNbOIBuFxEvGMEsPmsdgPqbBgpxBIFWYZwnHDevjROOTfEynHHn OaNIwCQdTqcrYQVBSPJrqRMYCyBOOByUaktapYmbaTOMDKZNQqxntqwMDAzqMgiExfYTdzwCswWZGOYDUgF tLVQosbEtjRlghFJrujApsSMrYp (Don't use the encryptor! That's cheating!!)
	Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt


jdege	May 20 2009, 04:20 AM Post #2
Elite member Posts: 262 Group: Admin Member #246 Joined: December 7, 2006	I'm not sure where you're seeing a polyalphabetic substitution. Looks to me like you have two monoalphabetic substitutions, one of letters to binary tetragraphs, and one of individual bits to individual letters. The result is a homophonic substitution. The thing is - the output of the first stage is easily identified. If you have properly partitioned the second-stage bit assignments correctly, the result will have at most 26 unique values out of the 32 possible, and the values will match a normal frequency distribution. The index of coincidence will be that of plain text. So, how hard is it to partition your bit assignments? Your sample ciphertext has 52 distinct letters. That means that there are 2^52 possible partitions. That's within the range of exhaustive search. But that overstates it. An almost-correct partition assignment will give a IC that's closer to that of plaintext than a not-quite-as-correct assignment. And that means that a hill-climber would be able to crack it very quickly. (Simple substitution ciphers have 26! keys, more than 80 billion more than your second-stage has, and hill-climbers routinely break them in minutes.)
	When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.


dabombguyman	May 20 2009, 12:56 PM Post #3
Just registered Posts: 16 Group: Members Member #3,267 Joined: May 17, 2009	The result isn't a mono-alphabetic substitution because every 1 and 0 is given a random character from their list. If you don't know the list that each one and zero has then you'll have to find it, and I've shown how frequency analysis doesn't work, so that is not an option. Also I calculated the possible combinations correctly. In my encryptor each 1 and 0 has 26 possible characters, so there are 26! combinations for each, making the number of TOTAL combinations 26!^2. Put that in a calculator and see what you get. My challenge still holds. If you think you can crack it so easily, solve the puzzle above. BTW: Thanks for helping me remember to work out a few kinks.
	Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt


jdege	May 20 2009, 01:19 PM Post #4
Elite member Posts: 262 Group: Admin Member #246 Joined: December 7, 2006	You have a homophonic alphabet - a single alphabet with variants. 1 maps to A, B, or C, and 0 maps to D, E, or F. Sometimes 1 will map to A, sometimes to B, but 1 will never map to D. The substitution is one-to-many, but it's always the same substitution. For it to be polyalphabetic, you'd need to have a number of bit to letter mappings, and to alternate between them in some pattern. As for your calculation of the number of possibilities, I'm not challenging that. I'm just pointing out that the number of possible keys isn't an indication of strength. You have two stages, the first is a simple substitution, the second is a binary homophonic substitution. The first stage on its own is trivial to crack, the second adds security only to the degree that it cannot be stripped off separately. And that depends upon whether we have a reliable test to indicate that a trial decryption is correct. In this case, we do, the Index of Coincidence. Do you understand what a hillclimber is, and how it works? Do you understand what the Index of Coincidence is, and how it can be used as a reliable test to indicate that the second stage of encryption has been successfully stripped? It'd take me half a day to write a hillclimber to attack this. I don't have time for that, and when it worked, it'd not give you greater understanding of where the weaknesses in your cipher are. Why don't you try to write a hillclimber to attack it? I'm sure you'd learn a lot from it.
	When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.


dabombguyman	May 20 2009, 03:49 PM Post #5
Just registered Posts: 16 Group: Members Member #3,267 Joined: May 17, 2009	Oops! Thanks for that. I took a look at your partition formula and found that I was improperly using the term 'combination'. Their are 2^52 different partitions but that's only one half of the formula. You also have to frequency analyze the binary sets either each by hand (which would take quite some time) or have the computer go through every possible substitution (which is 2^52 * 26!). I understand what you mean by "Index of Coincidence" which, unless the cipher text is HUGE, would not be as verifiable as it could be, and a google search of hillclimber won't get me anything because my school blocks Wikipedia. Could you explain?
	Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt


jdege	May 20 2009, 07:16 PM Post #6
Elite member Posts: 262 Group: Admin Member #246 Joined: December 7, 2006	There are 26! possible keys in the first stage, and there are 2^52 possible keys in the second stage, but they don't multiply because they can be attacked separately. The Index of Coincidence works fine on quite modest texts. Take a very short phrase, like "When, in the course of human events". Only 28 letters, with 15 distinct letters, and it has an IC of 0.078. Random text has an IC of 0.038. Even on a text as short as that, plaintext is clearly distinguishable from random. Now as for a hillclimber, the approach is simple. You choose a key at random. You do a test decryption. You run a scoring routine on the result. You modify the key slightly, creating what is called an "adjacent" key, decrypt with it and score again. If the result scores higher than your previous key, you keep it, if it does not, you go back to the previous key. You keep tryin the adjacent keys, scoring, and keeping the best until you find a key for which all of the adjacent keys have in lower scores. Conceptually, you are walking uphill until you find a local maximum. You keep track of the top key and its score. Then you repeat the process, starting with another random key, and climb to the top of that key's hill. If the score is higher than the previous top score, you print it out, and make it your new top score, then repeat again, beginning with a new random key. In your case, the keys I would be trying would be the bit partitions from the second stage. The decryption would be to reverse the bit assignments, then to use any arbitrary assignment of five-bit groups to letters, and then to calculate the Index of Coincidence of the result. There are 2^52 possible keys, in your second stage. But there are 26! possible keys in a simple substitution, as I said, more than 80 billion times as you have in your second state, and hill climbers routinely find the correct key after trying only a few tens of thousands of keys. I expect that one would find the correct stage two key in under a minute. Then, having stripped the second stage encryption, what you're left with is a simple substitution. Which is no protection at all.
	When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.


dabombguyman	May 21 2009, 12:47 PM Post #7
Just registered Posts: 16 Group: Members Member #3,267 Joined: May 17, 2009	Thanks for the info. BTW, the 52 characters was only an example set. You could go up to 94 characters with just a keyboard, or even into the 200s if you use special characters. 2^200 = 1.606e+60 different partitions; about how long would that take to find, even with a hill-climber? I designed it to be flexible just in case there were security issues.
	Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt


dabombguyman	May 21 2009, 12:47 PM Post #8
Just registered Posts: 16 Group: Members Member #3,267 Joined: May 17, 2009	I'll make a more powerful encryptor for the site just for that.
	Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt


jdege	May 21 2009, 03:19 PM Post #9
Elite member Posts: 262 Group: Admin Member #246 Joined: December 7, 2006	The size of the keyspace is meaningful only if adjacent keys produce very different ciphertexts. The goal in a modern computer-based cipher is for a single bit change in the key to result in having 50% of the bits in the output change. If adjacent keys produce similar text, if a slightly more correct key produces plaintext that is slightly more correct, then a computer can hill-climb to a solution. Take a single plaintext, and encrypt it. Then decrypt it with a key that is almost right. If the result looks almost right, then a hill-climber can attack it.
	When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.


dabombguyman	May 21 2009, 04:10 PM Post #10
Just registered Posts: 16 Group: Members Member #3,267 Joined: May 17, 2009	The result looks like crap (not totally illegible though). 1- Hello 2- HsQoabsjCegvSSVqpzYLDbknE 3- HsQoabSjCegvSSVqpzYLDbknE 4- HLLO Now we know it's climbable. Still, about how long to climb 2^200?
	Q3J5cHRvZ3JhcGh5IGlzIGFuIGFydCBmb3Jt


jdege	May 21 2009, 07:38 PM Post #11
Elite member Posts: 262 Group: Admin Member #246 Joined: December 7, 2006	dabombguyman May 21 2009, 04:10 PM Still, about how long to climb 2^200? It depends upon how large the "hills" are. If the key space has a great many local maxima, we're going to have to try a great many random keys before we find any that are reasonably close to correct. If there are only a relative few, we'll explore them all pretty quickly. I've run hill-climbers against Playfair ciphers that have taken many hours to find a solution. But hill-climbers can usually crack a simple substitution cipher in just a couple of minutes.
	When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.


1 user reading this topic (1 Guest and 0 Anonymous)


« Previous Topic · General · Next Topic »