Hacking Linux Exposed

About
Authors
Contents
Reviews
Foreword
Purchase

Articles
Books
Sourcecode
Tools
Errata

Home

 


previous article
index
next article
Home grown crypto is bad crypto. (+contest)
By Bri Hatch.

Summary: Every programmer tries to build their own encryption algorithm at some point. In one word: Don't.

Cryptography is a fun but tricky art. Almost every programmer has at some point in their career tried to write their own cryptographic algorithms. While the computations used to create the resulting encrypted output may be complicated and seem rock solid, usually custom cryptographic algorithms end up falling for one or more classic crypto pitfalls.

Substitution ciphers
While you may have pages upon pages of input manipulation, many custom written algorithms result in simple substitution ciphers. The most basic example, ROT13, shifts each English letter 13 spaces, wrapping around at "Z". This simply replaces "a" with "n", "b" with "o", "c" with "p", and so on. Thus "Apple Baker" becomes "Nccyr Onxre".

Custom ciphers usually create a much stronger illusion of security because the resulting output is less legible than the input. However this doesn't change the fact that the cipher boils down to a degenerate substitution cipher, which can be cracked fairly easily. Some would even consider substitution ciphers to be obfuscation, rather than a cipher in it's own right, they are so breakable.

Poor key strength
Ideally the security of a cryptographic algorithm should depend on the strength of the keys used for the encryption. Take for example an algorithm which relied on XORing[1] the unencrypted input with a stream of data. In this case, our stream can be considered a key[2]. So, say your key (some string of bytes) was 100 characters long in this case - that'd be plenty to protect a message that was less than 100 characters long. But if you needed to keep reusing that key for a 1 Mb message, a cryptographer would have a much better chance of deciphering the message.

Key Reuse
Cryptanalysis, the attempt to decipher encrypted text, is easiest when you have the same message encrypted more than once (known plaintext attack) or the same key is reused to encrypt different plaintext streams. For example if we used our 100 character long XOR key to encrypt several different <100 character messages, we can perform some mathematical handiwork against the results to learn about and eventually discover the key itself.

Failing to keep the key secret
The worst case of key use is when you include the key in the encrypted message itself in some way that allows it to be recovered. A message encrypted with PGP, for example, has several keys. The message is encrypted with an encryption cipher (for example Blowfish, 3DES, or AES) using a random key for the message. This key is stored in the PGP file itself, however it is encrypted with the recipient's public key, such that only the recipient can decode the key and thus decode the message.

Unfortunately, many home-grown crypto algorithms attempt to avoid key reuse by imbedding the key in the encrypted file itself with, perhaps, some minimal obfuscation. Not good.

These are just some of the problems that come up time and time again when someone creates their own cryptographic algorithms. If you want to securely encrypt data, you should use any of the freely available systems, for example PGP for files, SSL for network connections, or Blowfish/AES/etc for arbitrary data encryption. When using public cryptographic systems you must still take care to use them properly -- don't use SSL unless you verify certificates on both ends, don't reuse the same key for Blowfish encryption, etc -- but at least the algorithm itself will be one that has been scrutinized by respected cryptographers.

So, why did this all come up today? I was working with a client and was curious why their database was filled with seemingly meaningless data. They told me it was the encrypted billing info for the clients. Looking at it, I could tell that they'd whipped up some "encryption" algorithm on their own, and sat down and broke it.

Now, it's your turn.

I've encrypted five strings (normal printable English) using this weak encryption algorithm. If you're able to decrypt the input strings, send me an email explaining how you did it. The best writeup works will get a copy of Hacking Linux Exposed, Second Edition in the mail.

On Sunday morning, I'll post a hint or two on this page[3] for those who need the extra help. Entries submitted before I post hints will be prefered over those received later.

Here are the encrypted strings:

  !8@!>@!E`!EP!H`!GP!I0!GP!60!A@!I`!J@!L@!M@!7P!A0!N0!L@!L@!MP!J@!J@

  !!@!1P!=P!?P!=P!?`!>`!<0!?0!;0!?0!=@!B`!,`!>@!A0!,P!>@!B@!A`

  !^`!P0![0![0!IP!]0!H@!Z`!Y0!^0!I@!``![0!]0!]@!^@!`P!K0!`0!_0!_P!"`!P`

  !T`!M0!TP!V0!X0!Y0!C@!P0!Y0!W0!UP!Y@!H@

  !S@!O0!W`!SP!BP!V0!X@!X@!XP!D`!G@!D@!YP!V0![0!Z@!EP!X0![`!F@!W0!X0!\`!\@!K0

Happy decrypting!


New Hints Yes, all those ! characters are supposed to be there. Think uunecode.

NOTES:

[1] XOR is the exclusive bitwise OR operation, frequently used in cryptographic algorithms. It boils down to this: 0 XOR 0 == 0, 0 XOR 1 == 1, 1 XOR 0 == 1, 1 XOR 1 == 0.

[2] Usually this stream is actually created by some mathematical algorithm, where the algorithm is seeded by an actual key.

[3] Those reading this newsletter in email, check the web page version at http://www.hackinglinuxexposed.com/articles/20030122.html for the hints.


Bri Hatch is Chief Hacker at Onsight, Inc and author of Hacking Linux Exposed and Building Linux VPNs. He developed his first (horribly insecure) cryptographic algorithm when he was six. It was no better than ROT13, but took up a lot more space and CPU power. Bri can be reached at bri@hackinglinuxexposed.com.


Copyright Bri Hatch, 2003


This is the January 22, 2003 issue of the Linux Security: Tips, Tricks, and Hackery newsletter. If you wish to subscribe, visit http://lists.onsight.com/ or send email to Linux_Security-request@lists.onsight.com.

previous article
index
next article