Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Cryptography Challenge

By End in News
Thu May 04, 2000 at 07:53:07 PM EST
Tags: etc (all tags)
/etc

Just yesterday, geeky.org and I put up a cryptography challenge. The short version is, if you can solve the puzzle, you get a $25 thinkgeek gift certificate. You may have seen this already, but read more for some interesting thoughts I have since had about the puzzle itself, ciphers, and cryptography in general.


First let's take a look at some readily observable aspects of the puzzle:
  • The algorithm is not disclosed
  • The algorithm can be done by hand on paper without the use of a computer
  • The ciphertext is readable (albeit a bit Lewis-Carol-esque)

This puzzle presents an interesting situation. On the one hand the puzzle itself is hand-made, without the aid of a computer, and I do not realy consider myself a cryptography expert; so perhaps the code will be cracked quite easily by some smart MIT student or something. On the other hand, although it didn't take long to design the algorithm, I made it pretty tough, and I don't see how anyone could do it! I know it would be beyond my own ability to solve it if I ever came across something similair.

As the title on the challenge page says, strong cryptography may be easier than it looks. This puzzle is intrinsically harder because the problem has changed. Usually you know or can somehow guess the algorithm and are searching for the key. Here you do not even have the algorithm. The puzzle is so ambiguous that you look at it and have no idea where to begin. I could have taken this idea a lot farther than I did. This is an experiment in meta-problems as much as it is a contest.

Cryptography through Obscurity?
Someone pointed out that this puzzle might be called an excercise in cryptography through obscurity. Let's consider what that means on a practical basis[1]. Let's say I want to send a message to Osama Bin Laden[2]. Using a custom algorithm or cipher, I encipher my message and disguise it so well that no one would know by looking at it that it was encoded. Even if the CIA was logging all the email that goes to osama-bin-laden@microsoft.com and just knew that the email was a secret message, traditional attacks would be useless. Why? The algorithm is not only unknown, but the message would be just too ambiguous for meaningful attempts at figuring it out.

There is a historical example of this. During WWII, the Germans used a cipher they invented called Enigma. This was a very complex and advanced cipher, but being based purely on technology, it was eventually cracked by the Allies. The Americans hired a bunch of Navajo American Indians and simply used their little-known extinct language as part of a code. Even if the Germans could have figured out what language they were using it would have been almost uncrackable. As it was, no one ever cracked it because the cipher was on another level than what they were expecting, a level which just can't be practically tackled with technology and mathematics.

I'm guessing that in such a case, the old objection to "security through obscurity" simply doesn't apply. This is axiomatically not the same as attacking a piece of software where you have somewhere to start and know areas and points of the program and its design where security holes would be likely to exist. The reason obscurity doesn't work there is that you can never have true obscurity in computer software! Something is always known that gives you a starting point from which to proceed with your testing, probing and deductions, no matter how tight the source code.

Notes on the contest itself
Someone made an intersting point: "If it can be cracked from just one sample then the algo is really weak. But there are weak algorithms which are difficult to crack if you have only one sample and not told what the algorithm is....In effect it's similar to the case of a one time pad - except that it's more of a one time algorithm...In order for a proper evaluation/examination there should be more samples and the algorithm should be provided as well."

Perhaps this guy is correct. I'll wait a bit (just to see if this falls under the first case he mentioned) and then maybe post more examples using the exact same algorithm. If that doesn't help then maybe I'll analyze the tacks some people have been taking and give out a few hints. As I've noted, this is my first shot at a crypto challenge, so I'll augment the contest if somebody raises good points that I hadn't thought of and that warrants a change.

Lastly, I hope all this made some kind of sense ;-)

-JD  

Footnotes:
[1] We are talking about textual person-to-person level communication here, not machine-to-machine methods such as encrypting TCP/IP packets.
[2] This is just an example :-)

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o geeky.org
o cryptograp hy challenge
o thinkgeek
o smart MIT student
o [1]
o [2]
o  
o Also by End


Display: Sort:
Cryptography Challenge | 25 comments (25 topical, editorial, 0 hidden)
Very cool. I've been trying to tack... (none / 0) (#5)
by dlc on Thu May 04, 2000 at 02:35:54 PM EST

dlc voted 1 on this story.

Very cool. I've been trying to tackle it myself on and off throughout the day... and it's failing miserably. Is there a prize for last place?


(darren)

Re: Mmm.. cryptolicious.. (none / 0) (#11)
by Marcin on Thu May 04, 2000 at 09:13:33 PM EST

Very cool. I've been trying to tackle it myself on and off throughout the day... and it's failing miserably. Is there a prize for last place?

Sure! You get to order whatever you want from ThinkGeek, but without the discount.. how cool is that??!!! :)

They say it can be done by hand.. since they want you to provide info on how you did it do you get penalised if you use a computer based method to solve it?

I might play with it on the weekend, though i'm sure some geek (no offence ;)) would have worked it out long before then.
M.
[ Parent ]

Watch out for the 'security through... (none / 0) (#2)
by bmetzler on Thu May 04, 2000 at 02:39:53 PM EST

bmetzler voted 1 on this story.

Watch out for the 'security through obscurity' argument. Just to touch on it here, software that you know what it is that it will do must be open and audited to be secure. However, encryption must have a piece of obscurity if it is to really prevent someone from decrypting the message.

If you'd give out your gpg secret key, then your messages will no longer be secure. But in order to know that gpg really does wat it says it does, the code (or implementation) itself must not be obscured.

-Brent
www.bmetzler.org - it's not just a personal weblog, it's so much more.
Uh, what was with that broken link ... (1.00 / 1) (#3)
by fluffy grue on Thu May 04, 2000 at 02:39:57 PM EST

fluffy grue voted 0 on this story.

Uh, what was with that broken link for the "Smart MIT student"?
--
"Is not a quine" is not a quine.
I have a master's degree in science!

[ Hug Your Trikuare ]

covered on TOS ... (none / 0) (#8)
by haiku san on Thu May 04, 2000 at 02:52:21 PM EST

haiku san voted -1 on this story.

covered on TOS

Good article, but it misses one of ... (none / 0) (#7)
by Paradox on Thu May 04, 2000 at 02:54:39 PM EST

Paradox voted 1 on this story.

Good article, but it misses one of the main objections to security through obscurity. The main problem is that if someone conceals their algorithm, for all you know this closed algorithm you could be trusting a simple XOR of a 110 bit key. Not very secure, and you won't know, but an experienced cryptographer has tools and tricks to not only test for this simple type of encryption, but break it with little or no effort.

This dosen't mean obscurity is BAD, per se. If I use a very strong, custom designed algorithm, I am getting excellent security compounded by the fact that someone would have to do an enourmous amount of crypanalysis to figure out what to do anyways (provided that I don't give them any plaintext/ciphertext pairs and my algorithm really is strong.)

The worst part I see about this cipher is that it is human readable. These types tick me off because the meaning of the ciphertext distracts me :).
Dave "Paradox" Fayram

print print join q( ), split(q,q,,reverse qq;#qsti
qq)\;qlre;.q.pqevolqiqdog.);#1 reason to grin at Perl
print "\n";

Hey, now this is interesting! Not ... (none / 0) (#4)
by Zarniwoop on Thu May 04, 2000 at 03:14:08 PM EST

Zarniwoop voted 1 on this story.

Hey, now this is interesting! Not that I'd know the first place to start on something like crypto. Is there a good resource to read up on criptography (methods, algorithyms, what works, what doesn't)?

Place to start (4.00 / 1) (#16)
by Paradox on Fri May 05, 2000 at 04:19:02 AM EST

Applied Cryptography by Bruce Schneier. It's not an in depth study, but it's a good beginners book that will definitly answer the needs of someone just starting. Get it and check out that Ciphersaber Project that was covered here awhile ago. With that book, you'll make a ciphersaber-1 program in less than an hour. It's great.
Dave "Paradox" Fayram

print print join q( ), split(q,q,,reverse qq;#qsti
qq)\;qlre;.q.pqevolqiqdog.);#1 reason to grin at Perl
print "\n";
[ Parent ]
Re: Place to start (none / 0) (#19)
by Zarniwoop on Fri May 05, 2000 at 04:33:42 PM EST

Cool! Thanks!

[ Parent ]
Klaatu Verrata Nikt-[cough]!... (none / 0) (#1)
by joeyo on Thu May 04, 2000 at 04:21:14 PM EST

joeyo voted 1 on this story.

Klaatu Verrata Nikt-[cough]!

--
"Give me enough variables to work with, and I can probably do away with the notion of human free will." -- demi

Re: Klaatu Verrata Nikt-[cough]!... (none / 0) (#14)
by rusty on Fri May 05, 2000 at 12:02:10 AM EST

"Did you say the words?"
"Weeeell, most of them, yeah. I mean, maybe I didn't get every last syllable..."

:-)

____
Not the real rusty
[ Parent ]

Yes, it's been posted on That Other... (none / 0) (#6)
by RobotSlave on Thu May 04, 2000 at 04:26:11 PM EST

RobotSlave voted 1 on this story.

Yes, it's been posted on That Other Site, but this is from the author of the puzzle, and it contains some nice clarifications.

This is a challenge, but.. (3.00 / 2) (#9)
by Inoshiro on Thu May 04, 2000 at 08:13:39 PM EST

I'd expect that this could be done in a week or two, just by hand. With computers, a week at most ;) .. Of course, you need some specialised knowledge.

This is either a two step, or a one step, solution. Judging by the amount of random-seeming text, I'd say there's a level of steganography in play, too. Likely there are two steps (if it is advanced as the fellow said), otherwise there will be one step. "1) Extract complete cipher text. 2) Decode cipher text." If it's simple, extracting the cipher text will be the same as decyphering. If it's more advanced, a simple algorithm to do sliding and coincidence counting (as well as frequency) will reveal the code. Unless, of course, the message is in celtic. :-)

Here are selected portions of my notes on the given text:
Known plaintext: "the message is"
"An Poc ar Buile" -> "An Poc ar Buile" (uhn POK ehr BWIH-luh) [@n pok er' bil'@] = The Mad Billy Goat (lit., the buck on frenzy) - the title of a well-known traditional celtic song
Magic numbers:

  • # of colours in crest: 5 (yellow, black, white, purple, blue)
  • # of shapes in crest: 6 (9 if you count the "regions" they are on)
  • # of different shapes in crest: 3 (star, square, triangle) (or 6 with regions)
  • Other magic numbers: "seven" couriers, "13"th year.

The magic numbers part assumes that the way of extracting the cipher text from the "noise" is somehow encoded in the magic numbers, or that they are a clue to the sliding required to decode the cipher text. From there, it's as easy to break as XOR encryption (with a trivial keylength) if you have a program to shift it for you (otherwise, you get to do a lot of testing manually). Of course, I did this all late at night and haven't had a chance to play with it more :-)



--
[ イノシロ ]
Slightly Off topic (none / 0) (#12)
by Zer0 on Thu May 04, 2000 at 09:13:37 PM EST

From there, it's as easy to break as XOR encryption (with a trivial keylength) if you have a program to shift it for you (otherwise, you get to do a lot of testing manually).

I read your previous article on encryption and how to break XOR encryption and i still dont understand how you are supposed to easily break it. You mention finding the keylength, but in XOR encryption the key is also part of the data. (aka chaining XOR?)



[ Parent ]
Re: Slightly Off topic (none / 0) (#13)
by Zer0 on Thu May 04, 2000 at 09:20:40 PM EST

Just an eg.

AB CD EF FF AA ... to encode: AB XOR Random(256), (CD XOR AB) XOR Random(256)), (EF XOR CD) XOR Random(256)), (FF XOR EF) XOR Random(256)), Etc

So the key length is actually as long as the original data.

[ Parent ]
Re: Slightly Off topic (none / 0) (#15)
by Inoshiro on Fri May 05, 2000 at 02:11:34 AM EST

Any cipher (like the caesar cipher, XOR ciphers, etc) can be broken by shifting the text around until you get a higher "coincidence index" .. If the key length is the same length as the text, this won't work. Chances are the key is short (otherwise this'd just be an exercise in proving how hard OTPs are to crack ;-)

So given it's a short key cipher, shifting bits will likely help us. I'll write up a formal technique once I've written a program to do this with the text. I'll also hopefully be able to claim the prize, as I need some cool things >:)



--
[ イノシロ ]
[ Parent ]
Re: Cryptography Challenge (none / 0) (#10)
by Dacta on Thu May 04, 2000 at 09:09:08 PM EST

What's this? A ThinkGeek gift voucher for a prize? Is Andover trying to take over kuro5hin? *S*

Good idea, BTW. I'm not too sure what it proves (I think that it is close to a one-time pad), but it is an excellent idea for a contest, and great that someone went and did it (especially someone who I recognize from Slashdot).

Re: Cryptography Challenge (3.00 / 1) (#17)
by henrik on Fri May 05, 2000 at 05:25:54 AM EST

On the other hand, although it didn't take long to design the algorithm, I made it pretty tough, and I don't see how anyone could do it! I know it would be beyond my own ability to solve it if I ever came across something similair.
The history of cryptography is littered with crypto's where some unexperienced author is terribly impressed with him/herself and think they've created a really hard crypto. It's easy to make an algorithm that you can't solve yourself, but the trick is to make it so that no one else can solve it either. :)

I don't think it'd take too long for someone who knew what they were doing (that rules me out)

-henrik

Akademiska Intresseklubben antecknar!

Re: Cryptography Challenge (none / 0) (#20)
by End on Fri May 05, 2000 at 05:14:18 PM EST

Too true. In fact Phil Zimmerman himself did the same thing early on (when he was about my age I believe). That's part of why this is interesting to me, if not to no one else perhaps. We'll wait and see if someone solves it or until I finally spill the beans and then I'll probably get more peer review on the algorithm than I bargained for :-)

-JD
[ Parent ]

The problem with security through obscurity. (4.00 / 1) (#18)
by Anonymous Hero on Fri May 05, 2000 at 10:55:22 AM EST

If an algorithm has been proven secure through peer review, then the theft of a key means that only those messages sent with that key become readable. Since you change keys regularly, the damage is limited.

However, when an untested algorithm becomes known, and found to be weak, then ALL past and future messages become breakable, no matter what key they had or will have. An absolute utter disaster.

There's no problem with using obscurity as an added layer, but you'd bloody well better make sure that if it's an algorithm you're obscuring, then it had better be secure. This is hard to prove if you haven't shown it to anybody...

The example of using Navajo is quite different. Please note that this was used solely for voice communications, not text, and the advantage was that Navajo has such subtleties of inflection that it would take a decade at least to learn to speak it... if you could find a teacher.

Navajo thus made for a fast, unspoofable and reasonably secure voice "scrambling" system, which is exactly what you want in a tactical code. Once again, long term security is awful: find a willing Navajo and all past and future messages become known, but for tactical messages this doesn't matter (as long as you know that no willing Navajos have been captured by the enemy).

Re: The problem with security through obscurity. (none / 0) (#23)
by End on Sat May 06, 2000 at 11:30:13 PM EST

You make some good points. Perhaps I was mistaken in my use of terminology. I have used "strong" in the general sense of "very tough to break," whereas probably to most crypto people it has a more specific meaning.

However, most peer-reviewed "strong" algorithms really draw their strength from the impracticability of defeating them using brute-force methods (checking every possible key). DES may be considered intrinsically strong in your sense of the word, but if you're only using 56 bit DES you don't have a whole lot of security (these days).

What I am sort of asking in the article is whether the whole question of algorithm's strength can be sidestepped. Normally when you brute-force a ciphered message, your computer/human brain is only searching for the right keu in a (very large) range of possible keys. When the algorithm has been sufficiently obscured, the computer/person has a new problem: it must now search through all possible algorithms. Not nearly as easy. Probably not even possible. Theoretically, if it becomes next to impossible to figure out what algorithm has been used, why does it matter whether the algorithm itself is secure? Is such a thing possible?

-JD
[ Parent ]

Re: The problem with security through obscurity. (none / 0) (#24)
by Anonymous Hero on Mon May 08, 2000 at 08:45:57 AM EST

Using an algorithm which is in fact part of the key ( "key" understood as "everything you need to know to read the message") inhances the disadvantage of symmetric encryption compared to asymmetric:
- you need one key for every party you are communicating with
- you need to get the key to them on a secure way
by adding the following:
- you need to create a sufficiently different algorithm, not only a marginally different key
- suppose its an algorithm suited for computers: you need to do all the coding, testing, porting yourself
- suppose it isn't because it uses the creativeness and or the pattern matching abilities of the brain: you won't be able to use it on a regular basis

The puzzle is fun, I really like it, even though I'm hopelessly lost. But I cannot see it as a practical alternative to standard cryptographic techniques.

If you consider this flame ( which it isn't meant to be ), mention it and i will provide means to contact me. I'm just to lazy to create an account now :)

[ Parent ]
Re: Cryptography Challenge (none / 0) (#21)
by Anonymous Hero on Fri May 05, 2000 at 06:31:17 PM EST

A few years ago, I made a program for DOS that's designed for decrypting codes like this. It may not have the features required for cracking something like this, but it's a tool at your disposal. It worked for me when I needed it. The link for download is: MHCODE I hope someone can use it--it takes a while to get the hang of.

Intriguing (3.00 / 1) (#22)
by Anonymous Hero on Sat May 06, 2000 at 12:02:36 AM EST

You know, I've been pondering this challenge on and off all day, and throughout most of my french class. A few points which confuse me thus far: 1- It cannot possibly be a substitution cypher, since the new substituted letters would unlikely form real coherent words and phrases. 2- Taking this into consideration, I tried to figure out how the author proceeded in encrypting this message. Did he choose an already made text, then hide the message within it using some sort of key (unlikely) or.. did he choose a message to be encrypted then generate that text based on that? If the latter, how the hell would he be able to generate meaningful, coherent and related sentences? This would take forever, and a lot of imagination. He offered to post more messages using the same cypher, leading me to believe that he probably has a faster automated way of doing this. 3- To hide the message in a premade text would be tricky, because, while not impossible, it'd be hard to find a key to retreive it. Unless you're key was something like long and complicated indicating the letter position or something, but I don't think his is that complicated. The little picture above the text probably has clues to his key and/or methods of obtaining the key.. That picture is pretty bland, hard to extract long and complicated information from it. It does seem to have numerous prime numbers, though. An interesting thing I've found, using the prime numbers 3-5-7 (as hiroshimo(?) pointed out in an earlier post), is that if you take the 3rd, 5th and 7th word, convert all their letters to numbers then add those numbers together, so that the word "aaa" would = 3, the results are always divisible by 9. This leads me to believe that maybe 9 is some kind of important number, or something. Anyways.. It's late, and I'm rambling. Let me know if any of you could extract more information based on what (little) I've found. ragman@warezone.net

Crypto challenge (none / 0) (#25)
by Anonymous Hero on Tue Jun 27, 2000 at 07:03:31 AM EST

Revisit site - JD made a mistake in the original encryption. Second sample also available - just as obscure as the original. Anyone know the recipe for "dazzled eggs" ?

Cryptography Challenge | 25 comments (25 topical, 0 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!