This week in history

This week was the kind of week that a hobbit is very fond of. No adventures of any kind, no fuss, no huss. Until the day before yesterday that is... But all adventures are made to learn something from them, aren't they? Therefore I'd like first of all to give my thanks to metadev and andrei which were some of the most helpful persons that I found this week.

I went home and relaxed for the first time in my life, or so it seemed. I came back full of life, and I finally got to go to an interview. Even better, before leaving I finished all the bonuses at osix.net and I also discovered another challenge site (a little bit harder than osix though). You can find it here.

The day before yesterday I went to an interview and things looked okay. I went home and got myself a natural juice (no more cola). When I came back from the shop,... the display was black. Other than that the monitor was functioning normally as far as I could tell (no smoke, no buzzes, the led appeared to function correctly)... just an ugly black monitor, which didn't display anything.

The problem was aggravated by the fact that I had to send a very urgent formulary that was quite important for my future employment. My room-mate was kind enough to spare me some minutes at his computer (but not kind enough to create an account for me), but still I wasn't able to use a computer for quite long.

As a further humiliation, while using his computer, Windows broke and gave the blue screen of death. And this happened while I was TYPING!!!

Ok, so I will not be able to buy a new monitor for at least a week. Now the annoying part here was that while I knew at least two persons that had another monitor a week ago, it seemed that none of them had another monitor right now.

To my suprise, metadev called me this evening saying that he is able to give me a monitor for a week or so, tommorrow. Andrei also gave me a monitor for today, to complete my form and send it. I must say that I found this to be one of the most amazing turn of events of the last six months or so. Once again, thanks a lot guys.

Doru

Brasov

Ladies and gentlemen,

I've decided not to bother you anymore with this blog until Monday. I'm going to make use of the precious little time that is left of this holiday and go in my hometown, Brasov. My father probably awaits his prodigal son to return in order to cut the veal.

If any one of you has the time to get in Brasov I strongly recommend you do so. In case it's not raining it is one of the most beautiful towns over here. If not, go to wikipedia and see some crappy photographies of it...

Bye, bye!

Cryptography 2 - polyalphabetic and polygraphic substitution ciphers

Beautiful, for some reason or another, since yesterday (when I published my tutorial), my number of page-loads/day has doubled. So it would seem that this crappy style indeed gave some results. Therefore, I shall return to my cryptographic articles. There were a lot of replies to the previous articles (for a lot of in the range 0 to 1).

We have seen in the previous article that there is a simple modality of cracking simple substitution ciphers, using only the cipher text and without any knowledge of any part of the clear text. The method for cracking it is called frequency analysis and works for any reasonable message (say 20 or so characters). The obvious question comes here: if substitution is so easy to be broken, is there any way to make it harder? Well, the answer is yes, and this article tries to give some better alternatives to the simple substitution.

First of all, though, a tip. Writing a frequency analyzer is fairly simple. However, there is a tool which is already written, in case you would like to use it. It is called CryptTool. It does some nice things like plotting frequency graphs, cracking substitution ciphers, cracking Vigenere ciphers and other stuff like that. You might give it a try. If you get a similar tool, by all means please let me know.

Back to the meat of the article: How do we make substitution harder? I bet some of you are simply thinking of adding another substitution, or even 3-4 other substitutions. Well, this doesn't really work. The reason for this is that adding more substitutions can be solved as easy as one substitution. For example, if E becomes Z and in the next substitution Z becomes K, the cryptanalyst will easily see that the frequency of all the K's is very large and will therefore infere that K is substitutes E (which circumvents all of our protections). So multiple substitutions are no better than simple substitution.

What else could we do? Suppose we have a text like this one:

This is a cipher text which is encoded with a polyalphabetic substitution.

If we use Caesar 1 we get this:
Uijt jt b djqifs ufyu xijdi jt fodpefe xjui b qpmzbmqibcfujd tvctujuvujpo.

If we use Caesar 13 (or ROT-13 as it is called on the net) we get this:
Hvwg wg o qwdvsf hslh kvwqv wg sbqcrsr kwhv o dczmozdvopshwq gipghwhihwcb.

The idea when using polyalphabetic ciphers is something like this. Let us use different code portions for different parts of the message. The above message could therefore be crypted like this:

AuijtjtbdjqifsufyuxijdijtNsbqcrsrkwhvodczmozdvopshwqgipghwhihwcb.

This encryption is fairly simple. The capital letters are indicators for the type of Caesar used. In the above example, A means we use Caesar 1 and N (the 13th letter) means we use Caesar 13.

Now the above example might be easily decrypted, because it seems pretty obvious that the capital letters look like some separators. So ultimately, the cryptanalyst will probably get the idea to use frequency analysis on each of the parts.

However, our idea is not entirely without a merit since frequency analysis becomes harder, the smaller the pieces. If we have small enough pieces, which are all crypted differently (i.e. no two Caesar-1), frequency analysis becomes very hard.

I believe this is the route of thinking towards safer ciphers, and probably Giovan Batista Belaso thought so too. This guy took the above idea to the extreme. He made all the segments one letter long, and made the key invisible.

Suppose we have this message:

Sing, O goddess, the anger of Achilles son of Peleus, that brought countless ills upon the Achaeans.

First we make capitalize everything and remove all the spaces and punctuations:

SINGOGODDESSTHEANGEROFACHILLESSONOFPELEUSTHATBROUGHTCOUNTLESSILLSUPONTHEACHEANS.

After this, we think of a key. Suppose the key is EXQUISITE. We write it like this:

EXQUISITEEXQUISITEEXQUISITEEXQUISITEEXQUISITEEXQUISITEEXQUISITEEXQUISITEEXQUISI
SINGOGODDESSTHEANGEROFACHILLESSONOFPELEUSTHATBROUGHTCOUNTLESSILLSUPONTHEACHEANS.

Now, we use for each of the letters in the plain-text the Caesar alphabet indicated for the letter above it. This should give us this text:

WFDAWYWWHIPINPWIGKIOEZIUPBPPBIMWFWYTIIUOALPTXFOEOOZBVSYKJFMKABPPPKJWFBAIEZXYIFA.

The method of encryption described above is called Vigenere cipher after the name of a 16th century French cryptographer. As we shall see Vigenere (the cipher) is not by any means unbreakable. Vigenere (the man) actually invented a much stronger encryption method, but thus are the strange workings of history.

For now, I shall tell you that Vigenere is breakable, but I'll leave the breaking method to be guessed by you. I will explain it in the next instalment, but you should think of this opportunity as a nice occasion of practicing what you learned until now. Try to find a method of breaking the Vigenere without using Google to find out exactly how it's done. I promise to you that we'll get to that in the next chapter.

Hint 1: Use large texts (1000-2000 or more)
Hint 2: Use this site for frequency tables in any language. (note: on the main page of this dude there is a mention of a guy who e-mailed something about Romanian or somewhat. It's not me.) Another approach would be to write your own tool of frequency analysing and to find out the letter frenquecies in your language using a large enough text (the larger, the better).

Now on to polygraphic substitution ciphers. Polygraphic means simply "more drawings(letters)". We use a technique similar to simple substitution but instead of substituting each letter with a symbol letter, we substitute each two(or three, or four,..) letters with a symbol. The easiest symbol is another two letters.

The problem that appears here is the following: 26 letters are easily represented in a table with 26 rows and and 2 columns (or 26 columns and 2 rows). The method is however inadequated for 26*26==676 pairs of letters. A solution would be a table of 26x26. This is still inadequate however, because it is difficult to remember very easy each of the combinations within the table. A truly efficient polygraphic cipher would be random (so each table would have equal probability of substitution with another two letters).

An elegant solution was found to this problem by Charles Wheatstone in 1854. The cipher he developed was called the Playfair cipher. Here we will show a similar idea called the 4-square Playfair cipher which is considered safer and is also easier to understand. The idea was to use 4 tables of 5x5 in size and fill them with letters, in a random order. The we arrange the 4 tables like this:

 A | B
---+---
 C | D

How do we use them? It is a bit complicated, but I will try to make it as easy as possible. Suppose you have this text:

As he spoke he wept aloud, and his mother heard him where she was sitting in the depths of the sea hard by the old man her father.

1. The first thing we do is to remove all the spaces.


2. Second, we pad the text with the letter X up to an even number of letters.


3. Third, for each pair in the plain text, we do the following:




1. search the position of the first letter in table A and the position of the second letter in table D.


2. find in table B the letter which is on the same line as the letter found in table A and on the same column as the letter found in table D. This is the first letter of the ciphered pair


3. find in table C the letter which is on the same line as the letter found in table D and on the same column as the letter found in table A. This is the second letter of the ciphered pair

The Playfair is a fairly difficult cipher to cryptanalyse, so I will not ask you to do it (although you can if you want to). Here is another challenge: try to find an easy to remember method to generate random alphabets. This method should allow you to easily recreate the cipher text if you were to lose the 4 tables.

The answer to the challenges will be provided in the next instalment of the series, however, if you get to solve them, I would like to hear from you either by e-mail or through comments.

Best wishes to everyone!

Tutorial

Gentle reader,

I was informed by Statcounter that on average there are about 3 page loads per day. This is a decrease from the previous number of 7 page loads per day (the last two weeks or so). There are a lot of factors that could explain this, of which there is undoubtedly true at least one: a bad writer doesn't have any audience.

Being the lazy-ass that I am, instead of becoming a better writer, I have decided to write a tutorial on how to be part of the audience of this blog.

1. Post comments. The more comments, the better. Don't worry that somebody else has already thought of what you want to say (they did, and furthermore, they thought of a better way to express it). However, avoid spam or similar stuff with commercial content.


2. Read other blogs. After you have read them, come here and contradict me and say that somebody else said what I said and probably even better than me.


3. Try to find mistakes in the stuff I wrote, and post comments.


4. Get a RSS feed reader and subscribe to this entry. In this way you'll be able to see when it is updated.


5. If you are too timid to post comments, send me a mail.

This short tutorial will reveal without a doubt the true way of the blog-reader.

May the browser be with you.

The Yin and Yang Of Knowledge

Now that's a funny title, isn't it? I was gonna add some other stuff on Cryptography (there are about 3 more issues), but I thought, what's the hurry? (Besides this, I am stuck at one of the cryptographic bonus challenges at osix so I am not really in the mood of talking about this).

Here we are going to talk about something else. It is about this particular article. Now I am not by any means an expert in computer security. Actually, I am not an expert in anything, but the guy has some strange points in that article. Even more, he is pretty serious about them (if you look over the site you see some similar articles over there).

Let us see some ideas that he very often puts on his site: "Hacking is bad". In the article he mentions "Hacking is cool" as an 'anti-good idea' (sic). I am only going to pick on this particular idea, because this is what got me going. The problem here goes as follows: Marcus Ranum says that it is a bad idea to hire hackers to protect your system. This is like allowing a "reformed wolf" for a shepherd.

This is in my opinion blatantly wrong. In any domain if you are going to get good at something you have to play with that something over and over again. Let's say that you want to become a good piano player. Is it reasonable to think that you are ever going to reach some degree of virtuosity without serious exercise at least 4 hours a day? No, I don't think so. A piano player must gain knowledge on how the piano works and what it makes it tick. However, this is not the most important part. The most important part is to gain knowledge of the music. And this, he gains by repeated play of things that others wrote.

You do not become a Beethoven or a Mozart over night. You first must listen to this kind of music over and over again. Then you must reproduce it.... and to write similar pieces. Probably you will never get as good as Mozart at it, but trying to write stuff from zero, without first playing and listening music, is without doubt fruitless.

In the same way, if you want to be able to fix bugs and to write secure programs you must be able to crack first insecure programs. Otherwise, you will never be able to know what is secure and what is not.

Now another controversial thing... Skript Kiddies (or whatever spelling you have there). They are generally considered the worst there is in computers. They are guys who take the program as is and then compile it just to trash your system.

Well, here is another strange fact. I don't think them as ultimately so bad. After all, the kid who actually has knowledge on how to compile a script to trash a site understands something about computers. Besides, he ultimately will get to become a better programmer, if he is curious enough. Think of it... how many game programmers haven't started the stuff as players?

Herein lies another interesting thing. People who want to do something, will generally do it in spite of artificial conventions. Marcus Ranum treats hackers with outmost disrespect blaming them for almost every problem the internet has ever faced. However, if we think about it, a lot of the internet is powered by hacker products. Think of Linux. Think of Macintosh. Think of Google... and yes, think even of Microsoft. Every one of these companies was started by some guys who could have probably been called skript kiddies and good for nothings.

If it weren't up to some guys who like to break the rules just for gaining knowledge we wouldn't be here today. Yes, we have in equal amount the bad stuff: child pornography, commercialization, spam, etc. The solutions to these problems however, will not come from a suit in some office. They will probably come from a guy in Siberia who night after night buttons the heck out of his keyboard.

This is in my opinion the Yin and Yang of knowledge. New ideas, new informations, are only obtained by those radical enough to gain it. Look at it this way:

In ancient Egypt the fractional numbers were very undeveloped. You only had numbers like 1/2, 1/3, 1/4, 1/5, but no 7/15 or 3/4. Some of the numbers like 3/4 were only expressed as a sum of other numbers (in this case 1/2+1/4). A good question might be issued here: Why in the world were the egyptians so dumb as to not see that you could easily change the numerator from 1 to another number?

The answer is pretty simple: Egyptians wrote this number (the inverses of natural numbers) not as we write it today but in a different fashion. Something like a point and under that the number. For example:

1   .
- = 2
2

1   .
- = 3
3

1   .
- = 4
4

Therefore, they didn't even imagine that there was a 1 hidden somewhere because of the notation. Also, the writing was considered holy (the hiero part from hieroglyphs means holy). To change it would have been a blasphemy. This explains why the writing in Ancient Egypt remained pretty much unchanged from the years of the Old Kingdom up to the days of Cleopatra.

When some irreverent Greeks found about these interesting ideas they started playing with them. They experimented with 2/3 and other similar numbers.

The same is in computer security. To gain knowledge you must not be afraid to play with sacred cows. If you are able to write a secure OS, write it. However, if your knowledge stops only at compromising an insecure OS, write an exploit on it, document it, post in on a mailing list and wait the reactions of others. This will also get you knowledge.

---------------------

P.S.: I for one do not use the term "to hack" a lot. It seems however that lately, I stay around a lot of people who use it in the most interesting senses of which almost none have any relationship to security. A guy recently told me that he "hacked together a script to make his homework" or stuff like that. Now most of the applications that were linked to the word "hack" I generally considered interesting in purpose, if not really cool. So perhaps this is another reason why I picked on the article above.

Cryptography 1 - substitution ciphers

The title contains a link to a very interesting site regarding cryptographic methods. The site is given as a tutorial link towards level 13 at OSIX.

As probably some of you know, I have completed all of the challenges at Osix. Right now I am trying to solve the bonus challenges and after that I'll go to reversing challenges. You probably remember that I promised last time to post something on cryptography, so here it is.

First of all, let us talk about cryptography and cryptanalysis. Although I heard these terms used interchangeably, they are actually quite different. Kryptos in greek, means secret. The -graphy part in cryptography means "to write". The -analysis suffix means to solve. So the two sciences are basically opposites. While one is concerned with hiding informations, the other is concerned with finding hidden information.

Now that we've got over this, let us also explain, for sake of completness, the terms cipher and code. The two terms are closely related but they are considered to be different by the cryptographist.

A cipher is a way to modify the text (in order to hide it). The modality to modify the text is based on changing units like letters or certain fixed blocks of letters in an algorithmic fashion. We shall give an example of a cipher. The following cipher is generally called atbash and comes from the ancient hebrews. This cipher also appears in the recent best-seller The Da Vinci Code.

The atbash is a simple cipher. To use it, you simply replace A with Z, B with Y, C with X, and so on. You can write a simple substitution table:

A B C D E F G H I J K L M N O P Q S R T U V W X Y Z
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Of course, we can shorten this table a little bit and write it like this:
A B C D E F G H I J K L M
Z Y X W V U T S R Q P O N

As you can see, the logical processing units are letters.

A code is also a way to modify text (in order to hide it or for other purposes). Unlike a cipher, a code operates on phrases, words or similar blocks that generally have a semantic unity.

A simple example of a code is the so called 1337speek. I will not detail it here, as I believe most of you are familiar with it.

The word code is also used in other senses as well. An example would be "error-correcting code". However, for the time being we will use the definitions above.

In the next part we shall discuss different coding methods that enjoyed some popularity at some moment or other in time, as well as different ways of breaking those ciphers.

Probably the most useful cipher to know, when surfing the net, is the so called Caesar cipher. This one is a substitution cipher, not unlike the atbash that we met above. Here, we consider that the alphabet is written on a disk. To find the code of a letter we simply look on the disk for the letter that is forward one position on the disk. In this way we substitute A with B, B with C and so forth. Z is substituted with A.

It is called Caesar cipher because it was used by Caesar the first time.

A first generalization that we could make of this code is to move with more than one letter on a disk. For example we could move with two letters, and we would substitute A with C, B with D, and so forth. We could call this cipher Caesar-2 (and the first one is Caesar-1).We could have up to Caesar-25.

The reason that I said that this is one of the most useful ciphers to know is because Caesar-13 is very used on the web. It is used by people to give answers for logic puzzles on the same page as the puzzle. This is similar to the usual practice of some editors to write the answer of a puzzle on the same page as the problem, but upside down.

Both atbash and Caesar are quite easy to crack. To crack the you usually use something called frequency analysis. To decrypt the text, you find out the most used letter in your text. Then, you compare this with the most used letters in the language in which the message is written.

For example, in English the most used letters are (in this order): E, T, N, O, A, I. In Romanian, the most used letters are: E, I, A, R, T, N, L. If you see a letter repeated over a long period, it is probably certain that the letter in cause is the most frequent letter in your language. Once this guess is made, you look at the shortest words in your message (assuming the message has words clearly delimited). These words will help you deduce some of the other letters. In this way, messages get decrypted quite easily.

For now, besides the link in the title, I will give you this link of Lanaki's classical cryptography course.

Until next time....

The Last Challenge

Here is an update on my situation at OSIX. As probably some of you know, I am currently struggling with the last level (level 13).

The level requires cryptoanalysing a message. Well... let us see, what do I know about cryptoanalysing? Before this challenge I knew jack s**t. Now I know a little bit more. I was able to get about half of the challenge. However, there still is a long way to go.

When I'll finish this stuff I'll post an entry on cryptoanalysis and cryptography. Untill then, take care of yourself and don't forget to post comments.

On Education

By now, if you have read at least 3 of the entries in this blog you probably realized that my preoccupation with various ideas is not very persistent. The plus however is that I focus on a lot of various domains. Today we shall speak about an interesting mail that I received one of these days.

I will quote the mail, hoping that there will not be any copyright problems. Neither the question, nor the mail are written by me. I have received them because I have subscribed to a mailing list called "The Art of Memory". However, they resonated somehow with the ideas I had regarding the schooling system.

> Has anyone ever taught the memory systems to students?
>  
 
My wife is a school teacher, and we have talked about this
a lot.  It seems that, at least in the U.S. there are many
in the educational establishment who believe that mnemonics 
are:
1) a cheap trick perfomed by show off's
2) the people who use mnemonics are mental freaks.  You see 
when someone demonstrates mnemonics to a group of educators, 
it makes them look dumb or stupid.  They don't like looking 
stupid.  Therefore, the person using mnemonics is a freak.
 
All of this goes back the 18th and 19th centuries when there 
was a push to introduce mnemonics into the school system and 
it was defeated because mnemonics would:
 
1) make learning too easy!  That's right.  Many people at the
 time wanted schools to teach rigid dicipline to prepare 
students for the repetitive work of the industrial world.  
Rote learning with its constant repitition of the same thing 
seemed the perfict analog to the repetitive processes of 
machines.
 
2) the imagination, fantasy and mental images used in mnemonics 
were greatly discouraged because they "broke down mental 
dicipline".
 
This concern with dicipline is very real.  The primary problem 
faced by teachers is keeping order among 20 or so children.  
This is no small feat. Anything that detracts from the teachers 
ability to maintain controll of the classroom does not have a 
chance of being adopted.
 
> I've often wondered why the mnemonic systems are not being 
> taught in school systems.
>  
 
I know the above is a very incomplete explanation.  But these 
are some of the reasons mnemonics and the Art of Memory are not 
used in schools.
 
Byron

Solved LVL 9

>:) I SOLVED LEVEL 9 from Osix. :D. After coding the last few days a lot of algorithms (and driving my girlfriend crazy in the meantime) I cut a piece of paper to solve the puzzle. After some pondering, I finally got through with it.

On to level 10

Remorses

Ok, so someone once said that for every bad thing you do, you should also do a good thing (but not vice-versa ;) ).

I felt some remorses regarding the previous entry because I felt that I was only picking on that article. To alleviate this and give you also a good article I put forward this second post.

The article I am talking about is Are Games Getting Easier?. It speaks of the decline of the design component in the games.

Let me explain this better. Any game has two main components. The design component (which decides how things will actually be) and the technology component (which makes things the way they were decided to be). Over the last years games are getting a little bit easier. You do not really feel the same excitement when playing games the way you used to some time ago. The games do not have the same complexity and they also miss difficult puzzles and complex endings. They actually lose the element of fun.

The article describes in more detail this phenomenon.

ASCII 0x004

Various

Today's entry will have two parts. The first part is about an article that probably everyone will find amusing. After that, I will write how I am standing.

So first the funny part. Please go here and read the article. I know that I have been critical of Google, but the article is ridiculous. Probably everyone likes to pick on Google. And since this brings in more visitors, why not do it? Softpedia should really revise these articles before publishing them.

Now that I've got over the part that I intended to be funny, here is an update on my status

Things sometimes go well, sometimes go bad. To me they seem to go from bad to worse. First of all, the OSIX challenge goes bad. I've beaten the 8th level but got stuck at level 9. It is called "The Hexbox". The problem is that I do have an idea on how to do it, but I can't really find the perfect method of implementing it.

Second, I should get hired :(. I particularly dislike being hired. The reason is that while you generally have enough money to do whatever you want to do, you are not having any time for doing anything else. So my question is: what good is the money when you cannot spend them?

That about wraps it up.