Tag: Cryptography

Salted Length Extensions….

Today I’m writing about the length extension attack. It could be used in many applications so I felt that developers who are reading this blog should get to know how this works.

The Scenario

You have a site that allows users to upload files and make them available to their customers. When a user logs in to view resources you give these users access to certain folders on your site and place it in a cookie. You decide that the cookie should have a signature for security 😉 .


The signature is a salted sha1 hash of the resource in the following format.


Before showing the user a file you verify that they have access to the resource by calculating the signature and then verify that the signature matches what they passed to you in the cookie.

Now why would you do this instead of encrypting the whole damn thing? Simple… Encryption does not provide integrity, meaning from a programming standpoint it’s safer. Because if an encrypted cookie is tampered with your application can fail in the decryption throwing, exceptions and access violations. I have seen this lead to other notorious things like buffer overruns. Hashing data that is passed, even if tampered with is much safer than decrypting a value that has been tampered with. If you need confidentiality (meaning something in the cookie is secret) then by all means encrypt the cookie, you’ll still however need a MAC to validate the cookie (see Padding oracle attack against ASP.NET).

The Problem With The Approach

Lets look at a generic hash function….we’ll call it H. Pretend it’s this fantastic function below.


It’s very simple you see it takes some fixed length doodoo in and spits some fixed length doodoo out, the same input value will always have the same corresponding output value AND I know exactly how long that output is going to be every single time.

One Problem!
My hash function operates on fixed lengths (blocks), this isn’t going to work…we need it to work on arbitrary lengths. Now how do we achieve this? Well the Merkle–Damgård construction (MD5,SHA1,SHA2) splits our hash function into multiple steps, it operates on fixed length blocks chained together.


There are two inputs, our block and the hash of the previous block. For The first block there is an initialization vector which just gives you a starting point. By looking at this picture it’s easy to see that this construction is a simple state machine. You can take any of the outputs from any of the blocks and you will get the internal state of that machine.

Warning ::robot voice:: The following descriptions are an oversimplification of this problem. They are meant only as a description, please don’t try this at home. ::end robot voice:: End Warning

What does this mean my nerdy friend?
Lets pretend that my hash function operates on blocks of characters and not blocks of bytes. Lets also pretend that a single block is the length of 1 character. My Hash function H now has two inputs to generate its output. Therefore:


If I were to do the hash of AB and ABC the internal state would be exactly the same until the last letter (C) is processed (makes sense right?)

Lets look at that cookie again

Lets say your user logged in and they only have access to A_RESOURCE.


Lets pretend that user turns out to be malicious, they want some free shit like B_RESOURCE. What can they do? Well if they know the salt (key) then no problem, but we’re going to assume your attacker doesn’t have access to the key. If they do then you have bigger problems and you should stop reading right about now and go try to figure out WTF happened to your shit.

My attacker wants to get access to B_RESOURCE so they need to generate a signature without knowing what the key is. Now Remember the previous formula.


Treat our current signature as our hash functions internal state. So therefore:


In other words

NewSignature = H(Signature,B_RESOURCE)

Relax It’s Not Exactly That Simple

Before you go freaking out…It’s not exactly that simple, you’re not going to just take your signature and add your B_RESOURCE to it. This attack only works if your signature is in a certain format, for example this wouldn’t always* work if the signature incorporated the timestamp at the end of the hash like so:

Signature = H(KEY||A_RESOURCE||TimeStamp)

Because it would be difficult to generate a message with the new permissions in the middle.

Signature = H(KEY||A_RESOURCE||B_RESOURCE||TimeStamp)

You also need to know how long the salt is to construct your new message because you need to know how much padding was added, but this isn’t particularly difficult to find out (trial and error). This attack is called the length extension attack, and regardless of how simple or complex it is there are tools out there that allow attackers to perform length extension attacks against your application. It’s not beyond a determined attacker to do so, especially if you have data that has some value.

This won’t happen to me…

Oh Ye of little faith…. It happened to Flickr… nuff said…

The Fix

There are a lot of crappy solutions to this problem and a good solution. I’m just going to give you the good solution and it’s really simple… Don’t use a straight up hash function with salt, instead use the HMAC construction of that hash function. HMAC is resistant to the length extension attack as well as other problems that plague these cryptographic hash functions…. and guess what! It’s made specifically for this type of scenario, so why reinvent the wheel? There are many libraries that use the HMAC construction and if you use the .NET framework for your work you can simply use the HMAC construction available within the System.Security.Cryptography library. SHA3 (Keccak) is also resistant to the length extension attack without the HMAC construction, but it’s relatively new (it was accepted as the standard in October 2012) so it will take a little time before it’s adopted in libraries out there.

*Putting something at the end wouldn’t always work but in some cases and with some of the development practices out there it is plausable that you could extend the message after the timestamp and it would still result in a valid signature and permissions. You’ve been warned…

How I beat Crypto Challenge 3

For the 2013 GRRCon Crypto Challenge 3 we were given an image that needed to be decrypted, there were multiple levels and the final code could be used to get a free ticket to the conference.

Crypto Challenge 3

Crypto Challenge 3

The first level was probably the toughest part. While looking at it during lunch, a friend of mine and I noticed that it was braille. We went through and converted the first few letters and I noticed that the words IBMIsTheDevil were in there. The challenge with this part was that if you make a single mistake in the translation you would not know exactly where that mistake was without going through the entire image over again. I first tried to decode it by hand, that became annoying quick, so I looked to see if there was some OCR software out there for reading braille. Luckily for me I have a good friend of mine that has a PHD in image processing, unfortunately for me he told me he doesn’t know of any software that could OCR braille.

Take 2

After failure to find a good OCR software I decided to write a rudimentary OCR software myself. Things to notice, #1 The image can be split up into blocks of equal size. #2 The only value that matters was to get what was at the center of the circle. The image to the right shows a blown up version of a single letter. To perform OCR I simply created a C# application that would sample the center pixle of each dot and create an array of Boolean values, if the pixle was black it value was true, if it was white value was false.� Note: I did have to convert the gif to a PNG.

After creating the array simply check them against the known braille alphabet.

WARNING: The code I’m showing was just for this one task and was built in approximately 2 hours without any testing, it is not meant in any way shape or form to be used in a production environment or for any other task.

You’ll need to add a reference to system.drawing.

   class BrailleReader
        private Bitmap image;
        int col, row;
        Point lastPoint;

        bool capital = false;
        bool number = false;

        Color Black = new Color();

        private Dictionary<int[], string> translate;

        public BrailleReader()
            col = 0;
            row = 0;
            this.Black = Color.FromArgb(4, 2, 4);

            // setup dictionary
            translate = new Dictionary<int[], string>();
            translate.Add(new int[] { 0 }, "a");
            translate.Add(new int[] { 0, 1 }, "b");
            translate.Add(new int[] { 0, 3 }, "c");
            translate.Add(new int[] { 0, 3, 4 }, "d");
            translate.Add(new int[] { 0, 4 }, "e");
            translate.Add(new int[] { 0, 1, 3 }, "f");
            translate.Add(new int[] { 0, 1, 3, 4 }, "g");
            translate.Add(new int[] { 0, 1, 4 }, "h");
            translate.Add(new int[] { 1, 3 }, "i");
            translate.Add(new int[] { 1, 3, 4 }, "j");
            translate.Add(new int[] { 0, 2 }, "k");
            translate.Add(new int[] { 0, 1, 2 }, "l");
            translate.Add(new int[] { 0, 2, 3 }, "m");
            translate.Add(new int[] { 0, 2, 3, 4 }, "n");
            translate.Add(new int[] { 0, 2, 4 }, "o");
            translate.Add(new int[] { 0, 1, 2, 3 }, "p");
            translate.Add(new int[] { 0, 1, 2, 3, 4 }, "q");
            translate.Add(new int[] { 0, 1, 2, 4 }, "r");
            translate.Add(new int[] { 1, 2, 3 }, "s");
            translate.Add(new int[] { 1, 2, 3, 4 }, "t");
            translate.Add(new int[] { 0, 2, 5 }, "u");
            translate.Add(new int[] { 0, 1, 2, 5 }, "v");
            translate.Add(new int[] { 1, 3, 4, 5 }, "w");
            translate.Add(new int[] { 0, 2, 3, 5 }, "x");
            translate.Add(new int[] { 0, 2, 3, 4, 5 }, "y");
            translate.Add(new int[] { 0, 2, 4, 5 }, "z");


        public void Process(string path, int columns)
            if (!File.Exists(path))

            using (image = new Bitmap(path))
                for (int i = 0; i < 28; i++)
                    col = 0;
                    this.lastPoint = new Point(0, i * 50);

                    while (col < columns)
                        var result = GetNextLetter();

        private string GetNextLetter()
            bool[] brailleCode = new bool[6] { false, false, false, false, false, false };

            Rectangle section = new Rectangle(FindNext(), new Size(17, 27));

            Bitmap bmp = new Bitmap(section.Width, section.Height);
            Graphics g = Graphics.FromImage(bmp);

            g.DrawImage(this.image, 0, 0, section, GraphicsUnit.Pixel);

            brailleCode[0] = bmp.GetPixel(3, 3) == this.Black;
            brailleCode[1] = bmp.GetPixel(3, 13) == this.Black;
            brailleCode[2] = bmp.GetPixel(3, 23) == this.Black;
            brailleCode[3] = bmp.GetPixel(13, 3) == this.Black;
            brailleCode[4] = bmp.GetPixel(13, 13) == this.Black;
            brailleCode[5] = bmp.GetPixel(13, 23) == this.Black;

            string result = FindString(brailleCode);

            return result;

        private string FindString(bool[] brailleCode)
            string result = string.Empty;

            foreach (var item in this.translate)
                result += GetString(brailleCode, item.Key, item.Value);

            if (GetString(brailleCode, new int[] { 2, 3, 4, 5 }, "NUMBER") != string.Empty)
                number = true;
                return string.Empty;
            else if (GetString(brailleCode, new int[] { 4, 5 }, "STOP") != string.Empty)
                number = false;
                return string.Empty;

            if (GetString(brailleCode, new int[] { 5 }, "UPPER") != string.Empty)
                this.capital = true;
                return string.Empty;

            if (number && result != string.Empty)
                result = ConvertToNumber(result);

            if (capital)
                result = result.ToUpper();
                capital = false;

            return result;

        private string ConvertToNumber(string value)
            value = value.ToLower();
            switch (value)
                case "j":
                    value = "0";
                case "a":
                    value = "1";
                case "b":
                    value = "2";
                case "c":
                    value = "3";
                case "d":
                    value = "4";
                case "e":
                    value = "5";
                case "f":
                    value = "6";
                case "g":
                    value = "7";
                case "h":
                    value = "8";
                case "i":
                    value = "9";
                    return string.Empty;

            return value;

        private Point FindNext()
            int x = lastPoint.X + 7;
            int y = lastPoint.Y + 7;

            lastPoint.X = x + 23;
            return new Point(x, y);

        public string GetString(bool[] brailleCode, int[] indexes, string letter)
            for (int i = 0; i < brailleCode.Length; i++)
                if ((brailleCode[i] && !indexes.Contains(i)) || (indexes.Contains(i) && !brailleCode[i]))
                    return string.Empty;

            return letter;


    class Program
        static void Main(string[] args)
            BrailleReader reader = new BrailleReader();
            reader.Process(args[0], 17);



Stage 2 – Break the Cipher

The IBM is the devil part lead me to DES. If you study the history of cryptography you know is related to the Lucifer algorithm which later became DES. Just as a little background, DES is essentially the same algorithm as Lucifer except the S-Boxes (Substitution Boxes) were given to IBM by the NSA as well as a reduction of the key size from 128 bits to 56 bits. DES was the gold standard for encryption algorithms through even the 1990′s because of it’s resistance to cryptanalysis techniques that were being discovered. So using an online tool to decrypt DES I began guessing passwords, Lucifer was one of the first guesses I took and it partially worked.


You’ll notice that the readable characters are 8 characters, a char is typically 8 bits in ASCII which in this case would mean 8 Characters * 8 Bits = 64 bits. 64 bits is exactly 1 block for DES. Typically when you’re encrypting you’d want to use CBC mode (or better), which stands for cipher block chaining. CBC means that once a block is encrypted, that result is XORed with the next block to give you an avalanche effect over your entire cipher text rather than just over a single block. Because only the first block of cipher text was decrypted that lead me to believe that the mode was not CBC but ECB (Electronic Code Book). In ECB mode each block is encrypted separately, it’s not recommended to ever use this mode in a production setting.

Switching to ECB Mode the following was the result.


Stage 3 – All Out War

It seems that the writer of this challenge really loved crypto history. Archduke Franz Ferdinand was a royal from Austria who’s assassination set off World War I, again if you’re a student of cryptography you know that World War I was huge for cryptography. So now the challenge was to #1 figure out which algorithm was being used, and #2 figure out the key. At the time the state of the art were transposition ciphers, these were used by both the Allies as well as the Axis powers. I worked through a few ciphers but I was hell bent on ADFGVX, which I couldn’t get to work no matter how much I tried. Then I realized it was a little known cipher called Übchi, which was used by the Germans around that time. Now for that key… I noticed that there was a game on the GRRCon website (this was my first year going so I didn’t have any knowledge of the game before hand), game was called Hacker Feud… so I tried it and….


Stage 4 – Free Ticket

Simply copy and paste the code 1fy0ur3h4v1n6l0ckp1ck1n6pr0bl3m51f33lb4df0ry0u50n160799l0ckp1ck5bu71ju57n33d1 into eventbright and I got myself 1 free ticket! So… if you’re having lock picking problems I feel bad for you son, I got 99 lock picks but I just need 1!