If You’re Typing The Letters A-E-S Into Your Code, You’re Doing It Wrong
Date Jul 22, 2009 at 8:51PM, Author Thomas Ptacek
NOTE: (I’m mirroring this here because it somehow disappeared from google-accessible web. -exa)
1. INT. COFFEE SHOP, MORNING
DISCUSSING AN INTERVIEW
A “young, cool-people’s” coffee shop on the first floor of an old office building in downtown Chicago. “My band is playing” notices line the wall. A hipster in a tight t-shirt hands a cappucino to MIKE TRACY while THOMAS PTACEK waits impatiently. The coffee shop is loud; Mike and Thomas raise their voices to be heard over the noise.
MIKE TRACY
Did you see that? He worked so hard on my coffee.
THOMAS PTACEK
What? Right. Whatever. Let’s get…
MIKE TRACY
He got all those little beans and put them in the thing and tamped them down and
THOMAS PTACEK
Whatever. Ok. We’ve gotta get ready for this interview
MIKE TRACY (CONT’D)
and he clickity-clack clickity-clacked with the machine and
THOMAS PTACEK
Mike! I get it! He made the shit out of your coffee. What are we going to ask this guy?
Mike walks to a table at the side of the shop, grabbing a lid and a sleeve for his coffee.
MIKE TRACY (Miffed)
I don’t know. It’s your interview. Single signon cookies?
THOMAS PTACEK
Why SSO?
Mike is maneuvering around people entering the shop through a door leading out to the hallway.
MIKE TRACY
It’s got crypto in it. Everyone always fucks it up.
INT. HALLWAY – CONTINUOUS
Thomas follows Mike, walking towards the elevators.
THOMAS PTACEK
Yeah, that could work. We’ll have two apps. User logged into one of them, needs the other app to do something without making them log in.
MIKE TRACY
Print an invoice.
THOMAS PTACEK
Yeah, this will work. We’ll see if he comes up with the industry standard answer; the cookie both apps honor to let you in, encrypted so users can’t change their account to someone else’s.
MIKE TRACY
So, a base64 blob AES encrypted with a key both servers share? That’s pretty easy, isn’t it? Are we sure this isn’t a layup?
DING. An elevator opens. Thomas and Mike step inside.
THOMAS PTACEK
You’ll be surprised.
2. INT. OFFICE – LATER THAT MORNING
An unadorned off-white office lined with Ikea desks, piled with books, papers, and in one case a pile of random electronics tools (soldering iron, multi, etc). An EASEL PAD stands next to a large window looking out on a brick wall. Thomas and Mike sit office chairs with THE CANDIDATE.
THOMAS PTACEK
So you’d have app ‘A’ set a cookie with your account ID in it, right, but how would you keep the user from switching their account by messing with the cookie?
THE CANDIDATE
Uh, I’d encrypt the cookie?
THOMAS PTACEK
Show us how on the pad?
Thomas hands The Candidate a dry erase marker, as The Candidate walks to the easel pad.
THE CANDIDATE
Does it matter what language I write it in?
MIKE TRACY
Whatever you’re comfortable with.
THE CANDIDATE (Writing awkwardly, addressing the easel)
Ok, so in C#, I’d use Response.Cookies, and
THOMAS PTACEK
You can just do the part where you encrypt the cookies.
THE CANDIDATE
Oh, ok.
The Candidate writes on the pad, slowly:
public static string Encrypt(string toEncrypt, string key, bool useHashing)
{
byte[] keyArray = UTF8Encoding.UTF8.GetBytes(key);
byte[] toEncryptArray = UTF8Encoding.UTF8.GetBytes(toEncrypt);
if (useHashing)
keyArray = new MD5CryptoServiceProvider().ComputeHash(keyArray);
var tdes = new TripleDESCryptoServiceProvider()
{ Key = keyArray, Mode = CipherMode.ECB, Padding = PaddingMode.PKCS7 };
ICryptoTransform cTransform = tdes.CreateEncryptor();
byte[] resultArray = cTransform.TransformFinalBlock(
toEncryptArray, 0, toEncryptArray.Length);
return Convert.ToBase64String(resultArray, 0, resultArray.Length);
}
THE CANDIDATE
Sorry.
MIKE TRACY
No worries, writing code during interviews sucks.
THOMAS PTACEK
Can you walk us through what that code is doing?
THE CANDIDATE
Sure. So I’m Triple-DES encrypting the cookie, which is the “toEncrypt” function argument.
MIKE TRACY
Triple DES? Seriously?
THE CANDIDATE
Ah, yeah, you’re right, in my last job we had to use Triple DES for compatibility, but I’d use AES now.
The Candidate starts correcting the text on the pad.
THOMAS PTACEK
Don’t worry about it, keep going. But yeah, don’t use Triple DES for anything. It has a bunch of problems, but also an 8 byte block size, which is tiny.
THE CANDIDATE
Ok, so, I take the key and I turn it into an AES key by MD5’ing it.
MIKE TRACY
You know MD5 is broken, right?
THOMAS PTACEK
Yeah, that’s not really the problem there though.
THE CANDIDATE
Oh, I could just use SHA-1.
THOMAS PTACEK
SHA-1 is really fast. Can you see why that’s a problem here?
THE CANDIDATE (Haltingly)
Um. Not really? Don’t I want this to be fast?
MIKE TRACY
What’s in the cookie you’re encrypting again?
THE CANDIDATE
A string of URL arguments…
The Candidate starts writing on the pad, “userId=39493&role=user×tamp=1414919”
MIKE TRACY
So what’s to stop me from just running a dictionary through MD5, generating a key, and trying to decrypt the cookie? I’ll know I won when I get clean ASCII.
THE CANDIDATE
And how do I keep that from happening? You should use strong passwords anyways. And I use a salt with the key anyways.
Mike vomits onto the floor.
THOMAS PTACEK
Gross.
MIKE TRACY (Wiping mouth)
A salt doesn’t do anything here!
THOMAS PTACEK
Just put a “for” loop around SHA-1 and run it 1000 times to generate the key; that’ll at least slow down a brute force attack. SHA-1 is lightning fast. By itself, it’s a crappy way to generate a key.
(To Mike)
Clean that up?
THE CANDIDATE
Well, I guess. Wait, why should we use a password here at all? I could just use a random string of bytes…
The Candidate writes again on the whiteboard
new RNGCryptoServiceProvider().GetBytes(keyArray);THOMAS PTACEK
That is much better. Sometimes it’s a lot more convenient to use a readable string. If you do, the loop around SHA-1 is similar to what PBKDF does, which is I guess a best practice here. But if you can keep structure out of your crypto keys, that’s much better.
THE CANDIDATE
Ok. Should I keep going?
THOMAS PTACEK
Your encryption function. Do you know what the “ECB” thing there means?
THE CANDIDATE
Oh, fuck! You’re right, that should be CBC.
(Pausing)
Sorry for swearing.
MIKE TRACY
S’okay. You’ll fit right in.
THOMAS PTACEK
You know the difference between ECB and CBC?
THE CANDIDATE
Yeah, like, each block feeds into the next one?
The candidate draws on the easel.
THOMAS PTACEK
Why’s that a win?
THE CANDIDATE
Because if any of the blocks repeat, you can see them repeat?
Mike has opened his laptop and is typing.
MIKE TRACY (To the laptop)
We have a picture of that somewhere. Oh, here.
Mike raises the laptop up to show The Candidate
MIKE TRACY (CONT’D)
The top part is unencrypted. The bottom part is encrypted ECB. You’re like Jack from Heat Vision and Jack.
THE CANDIDATE
I know EVERYTHING! Right, because one bunch of 16 “black” bytes is the same as the next, so they show up the same in the picture. Neat. Also, in ECB mode you can cut and paste the blocks, right? He could take the “userid” out of your cookie and put it in his own?
THOMAS PTACEK
Sure. That’s a good answer. Let’s move on. Say you’re implementing a web server. What do you think, processes or threads?
3. INT. OFFICE CONFERENCE ROOM – AFTERNOON
A room in the same office, roughly the same size, with an oversized brown kitchen table in the middle, littered with paper and McDonalds wrappers. Thomas and Mike sit at the table, talking to a CONFERENCE PHONE.
CONFERENCE PHONE
So how’d he do?
THOMAS PTACEK
Pretty much aced it.
MIKE TRACY
What? He bombed the cookie part. He used ECB, MD5, and Triple DES!
THOMAS PTACEK
I’m impressed that he could spell ECB, MD5, or Triple DES. And it wouldn’t have mattered if he had used CBC, SHA-256, and AES-256. His code still would have been broken.
CONFERENCE PHONE
How so?
THOMAS PTACEK
He didn’t authenticate the message. Encryption isn’t —-
MIKE TRACY (Chanting)
Encryption – isn’t – authentication.
CONFERENCE PHONE
Don’t you mean integrity?
THOMAS PTACEK
No, Dave, I mean authentication. They’re called message authentication codes.
CONFERENCE PHONE
Ok, Tom. But he screwed that up?
THOMAS PTACEK
Yeah, but who cares? I’m surprised he even knew what CBC was. But we just asked that to see how he thinks. We’re never going to let him implement crypto code anyways.
CONFERENCE PHONE
I guess we don’t even let you write crypto code.
THOMAS PTACEK
Sure, and when I asked him about processes and threads…
MIKE TRACY
Can I stop you both here for a second?
THOMAS PTACEK
Yeah?
MIKE TRACY
This room is pretty fucking boring. We’re in a screenplay, right?
THOMAS PTACEK
Oh, yeah, you’re right. Let’s fix that.
(Shouting)
Wings of silver!
CONFERENCE PHONE
Nerves of steel!
MIKE TRACY
Thundercats go!
EXT. HURTLING THROUGH SPACE – CONTINUOUS
The office melts away around them, revealing a starfield hurtling past as if moving at awesome speed. Meanwhile, the conference phone transforms into a UNICORN WITH LASER HORN.
DAVE THE LASER UNICORN
It’s “Silverhawks”, jackass.
THOMAS PTACEK
Where were we?
MIKE TRACY
Authentication?
THOMAS PTACEK
Oh yeah. Even if he had done AES-256-CBC. His code is still busted. I can make his messages say whatever I want them to.
DAVE THE LASER UNICORN
How do you do that? Isn’t that the point of CBC mode? Anything you change in the ciphertext randomizes the output. What can an attacker do with that?
THOMAS PTACEK
First of all, sometimes randomizing the output is all you need. If one of the key-value pairs in the cookie is your role, and the default role is “admin”, but the server always generates a “role=user” field…
MIKE TRACY
Yikes. Yeah, that’s bad. Have you ever seen that bug in the wild?
THOMAS PTACEK
Garbling a block to confuse an app? I found a similar problem recently. Login generates an encrypted cookie. Inside the cookie, comma-seperated key-value pairs. If you put a comma in your user name, the server doesn’t want you to inject your own key-value pairs, like “bob comma admin equals yes”. So it quotes the commas. You can mess up a block to eat the quote character.
DAVE THE LASER UNICORN
How do you know what block to mess up?
THOMAS PTACEK
It’s a cookie. You get unlimited tries. Each time, you add another ‘A’ to the login name, or mess with a different block. Eventually you line things up just right so that you’ve garbled the quote character but not the comma. Here, let me show you.
Thomas puts his hand to his forehead, and a beam of light emerges from his forehead, projecting a picture, because it’s my script dammit.
THOMAS PTACEK
Top hexdump. The plaintext of the cookie. Nothing’s been done to it. Second hexdump. The encrypted cookie. Key doesn’t matter. Third hexdump. I’ve flipped a bit in the second AES block.
DAVE THE LASER UNICORN
Convenient how AES blocks and hexdump lines are the same width.
THOMAS PTACEK
Fourth hexdump. The decrypted output, after flipping that bit in the ciphertext. Notice that flipping one bit totally garbled the second block —- and ate my quote character.
MIKE TRACY
Doesn’t the app reject the cookie because of the garbled stuff in the middle of it?
THOMAS PTACEK
Probably not. Why would it? C# and Java and Ruby and Python don’t care what go in your strings. And hey, if it does reject them, flip a different bit. Totally different output. You get 2^128 tries.
MIKE TRACY
Good point. What’s with the red “B” in the decrypted hexdump?
THOMAS PTACEK
Getting to that. Turns out, I can make the cookie say whatever I want. It’s a property of CBC.
The property is this: take a ciphertext block and flip bit 0 (or 2, or N). The resulting plaintext for that block? Garbage. But the next block is normal… except has that bit flipped. Not good!
MIKE TRACY
So you sacrifice one block and flip bits in the second block?
THOMAS PTACEK
Yeah. Although let’s stop calling it “flipping bits” and call it “rewriting”, because that’s what you’re doing.
DAVE THE LASER UNICORN
If you know what bits to flip.
THOMAS PTACEK
You always know what the bits are.
DAVE THE LASER UNICORN
How?
THOMAS PTACEK
Because the bits are always 0×41414141.
DAVE THE LASER UNICORN
Huh?
MIKE TRACY
Because that’s what he stuffed them with. He logged in as bob A-A-A-A-A-A-A-A-A.
THOMAS PTACEK
Right. An SSO cookie is usually, what, 100 bytes? If I stuff 1000 A’s after my login name, and the cookie grows to 1100 bytes? Almost all of those bytes are known to me. Here.
Again with the forehead beam thing.
AES encrypt something that I partially control. Doesn’t matter what the key is. Now XOR that block into the ciphertext. Decrypt it, and somewhere in it you get a random block and “&admin=yes&x=AAAAA”.
MIKE TRACY
Not good.
THOMAS PTACEK
If you’re encrypting something it’s usually somehow user-controlled. I’ll find that by plugging 100 A’s into each form field and waiting for the cookie to grow.
DAVE THE LASER UNICORN
How will you know if the cookie is AES?
THOMAS PTACEK
Same way Chris Eng said to. Add A’s one at a time, see what increments the cookie grows in. 16 bytes at a time? AES.
DAVE THE LASER UNICORN
And CBC?
MIKE TRACY
If you’re encrypting all A’s, the ciphertext blocks will repeat.
DAVE THE LASER UNICORN
And how do you know the format to write into the cookie?
MIKE TRACY
Who cares? Trial and error.
THOMAS PTACEK
Yeah. Point is, you thought encryption protected the contents of the cookie. It doesn’t. Oh look, we’re almost there.
Thomas, Mike, and Dave hurtle towards a star system, a solar system, a planet, powers-of-ten-style, towards the Michigan shore, converging eventually on an office building, and then
INT. OFFICE CONFERENCE ROOM – AFTERNOON
CONFERENCE PHONE
That was really fucking anticlimactic.
EXT. PARKING GARAGE – EARLY EVENING
Thomas stands next to his car, a black Volvo 850 held together with duct tape, talking on a cell phone to NATE LAWSON.
NATE LAWSON
You know this scene is a really bad setup for a movie, right?
THOMAS PTACEK
Yeah yeah, whatever. Shut up before I turn you into a claymation character. So yeah, it’s amazing how you can be a top tier vuln researcher for over a decade and not really get how bad it is not to have a MAC.
NATE LAWSON
A MAC doesn’t necessarily save you either.
THOMAS PTACEK
How so?
NATE LAWSON
There’s still a bunch of things you can do wrong. Like I was just saying, Google Keyczar did almost everything right, but compared the MAC using a timeable comparison function. You could tell how many bytes of the MAC matched by watching how long the function took. People make that mistake all the time. An even more common mistake is to generate an error message when your padding is wrong. If you do that, you can decrypt messages.
THOMAS PTACEK
I’ve heard about that. The Bleichenbacher PKCS thing, and the Vaudenay paper.
NATE LAWSON
This was a major TLS finding too.
THOMAS PTACEK
I’ve never really been all that clear on how this works.
NATE LAWSON
Well you know how PKCS 7 padding works, right?
THOMAS PTACEK
Yeah, you have 2 bytes, you need to fill 16 bytes for an AES block, so you fill the remaining 14 bytes with 0xe.
NATE LAWSON
So if you tack a random block onto a CBC message, what happens when the receiver decrypts it?
THOMAS PTACEK
It comes out random.
NATE LAWSON
And the padding?
THOMAS PTACEK
Broken.
NATE LAWSON
Right. And if you send an error when that happens, you know the padding failed. Now if you keep trying different random blocks, what’s eventually going to happen?
THOMAS PTACEK
Uh…
NATE LAWSON
You’ll get a message with valid padding. Valid padding might be 0×3 0×3 0×3. Or it might be 0×4 0×4 0×4 0×4. But if you’re basically generating random blocks, what’s the mostly likely padding you’re going to get that will pass the check?
THOMAS PTACEK
0×1.
NATE LAWSON
Right. And you’re randomizing the output by tacking a random block in front of real ciphertext, which gets XOR’d during decryption. So you know the last byte of your random block…
THOMAS PTACEK
And the 0×1 that you know the padding is, and so that random byte XOR the last byte of the plaintext is 0×1, and so you know the last byte of the plaintext.
(Pausing)
And now that you know the last byte of the plaintext, you can make the padding come out to 0×2 and try randomizing the other 15 bytes to find out the next byte, and so on?
NATE LAWSON
Close enough.
THOMAS PTACEK
That is fucked up. All you did wrong was show me the exception your library generated when you decrypted the block, and I could decrypt a block. You got to reason byte by byte instead of block by block.
NATE LAWSON
You can decrypt whole messages that way. It’s called an error oracle. You can’t show clients discernable errors. You can’t even take different amounts of time to do things! You can watch the system with random inputs and measure how much time things take.
THOMAS PTACEK
There’s no way any programmer is ever going to get this stuff right.
NATE LAWSON
Professional crypto people don’t even get this stuff right. But if you have to encrypt something, you might as well use something that has already been tested.
THOMAS PTACEK
GPG for data at rest. TLS for data in motion.
NATE LAWSON
You can also use Guttman’s cryptlib, which has a sane API. Or Google Keyczar. They both have really simple interfaces, and they try to make it hard to do the wrong thing. What we need are fewer libraries with higher level interfaces. But we also need more testing for those libraries.
THOMAS PTACEK
Like I’ve been saying, if you have to type the letters “A-E-S” into your source code, you’re doing it wrong.
NATE LAWSON
Uh. Ok. Whatever you say, Tom.