Ok, another batch of questions have come in, all variants on
the same theme.
The question is, if mortgages are at the root of the current economic disaster, how can it possibly result in close to a trillion dollars worth of losses?
It definitely seems strange, on two different levels. On an absolute scale, it’s hard to see how mortgage losses could add up to a trillion dollars. And on a relative scale, it’s hard to see how the foreclosures could really overwhelm the lenders when even an extremely high foreclosure rate represents a fairly modest loss considered as a percentage.
There is at least a little bit of interesting bath math
to learn from in the whole financial mess going on now. A couple
of commenters beat me to it, but I’ll go ahead and write about
it anyway.
One of the big questions that comes up again and again is: how did they get away with this? How could they find any way of
taking things that were worthless, and turn them into something that could be represented as safe?
With the insanity that’s been going on in the financial world
lately, a bunch of people have asked me to post a followup to my
earlier posts on the whole mortgage disaster, to try to explain
what’s going on lately.
As I keep saying when people ask me things like this, I’m not an economist. I don’t know much about economics, and what little I do know, I tend to find terribly boring. And in this case, the discussion inevitably gets political, so I’m expecting lots of nasty email.
So, as it turned out, I made a major screwup in my post earlier today on modes of operation. Rather than just edit the post, I’m adding a new post with the corrected description of the counter mode, and a bit of explanation. I figure that if I screw up badly, it’s more honest to make a second post explaining the error than it is to just correct it and pretend that all was well.
What I got wrong was the order in which things happen. In the counter mode,
you encrypt the counter using the key, and then you exclusive-or the result of that with the plaintext to get the ciphertext. The plaintext never enters the block cipher; the block cipher just produces a complex and random looking block of bits which are then used to obscure a block of plaintext.
What I said in the original post was that you exclusive or the plaintext with the counter, and then run it through the block cipher. In my screwed up version, the plaintext is being put through the block cipher mechanism; in the correct version, it’s not. Below is some of my psuedo-python showing my screwed up CTR mode,
and the (hopefully) correct CTR mode. I’ve also included a diagram of the correct CTR mode.
def EncryptWithMarksScrewedUpCTR(blocks, ctr, key):
for b in blocks:
encrypted = encrypt(key, b ^ ctr)
ctr = ctr + 1
output(encrypted)
def EncryptWithRealCTR(blocks, ctr, key):
for b in blocks:
e_ctr = encrypt(key, ctr)
encrypted = e_ctr ^ b
output(encrypted)
ctr = ctr + 1
This can make a big difference in the effectiveness of the cipher against various attacks. I’m not going to get into details now, but over the course of future posts, I hope that I’ll be able to make it clear why changes like this can have huge impacts on
the security and quality of a cipher.
Sorry for the slow pace of the blog lately. I’ve been sick with a horrible
sinus infection for the last month, and I’ve also been particularly busy with work, which have left me with neither the time nor the energy to do the research necessary to put together a decent blog post. After seeing an ENT a couple of days ago, I’m on a batch of new antibiotics plus some steroids, and together, those should knock the infection out.
With that out of the way: we’re going to look at how to get from simple block ciphers to stream ciphers, using the oh-so-imaginatively named modes of operation!
As a quick refresher, block encryption specifies an encryption scheme that operates on fixed-size blocks of bits. In the case of DES, that’s 64 bits. In the
real world, that’s not terribly useful on its own. What we want is something called
a stream cipher: a cipher that’s usable for messages with arbitrary lengths. The way to get from a block cipher to a stream cipher is by defining
some mechanism for taking an arbitrary-sized message, and describing how to break it into blocks, and how to connect those blocks together.
Modes of operation are formal descriptions of the way that you
use block encryption on a message that’s larger than a single block. Modes of operation (MOOs) are critical in making effective use of a block cipher. Of course, there’s always a tradeoff in things like this: you have to choose what properties of your encrypted communication you want to protect. Particularly for DES encryption, the standard MOOs can provide confidentiality (making sure that no one can read your encrypted communication), or integrity (making sure that your communication isn’t altered during transmission), but not both.
My apologies for how slow the blog has been lately. I’ve been sick with a horrible
sinus infection for the last month. I saw an ENT on wednesday, and with massive doses of antibiotics and steroids, I’m finally on the mend, so hopefully things
will get back to normal soon.
Marillion, “Thunder Fly”: For those of us who pre-ordered Marillion’s upcoming album, they just made mediocre-quality prerelease copies available for download. Overall, I’m very happy with it. It’s quite good; I can’t wait to listen to it in its high-quality CD form. This is a fun track; it’s got a nice bounce
to it, but also has some of those wonderful Marillion transitions. It’s a vast improvement over anything from their last album.
Explosions in the Sky, “Yasmin the Light”: some Mogwai style post rock. Explosions is one of my favorites of this style of post-rock. This is very typical of them – really excellent.
Motionless, “United States of Amnesia”: another post-rock band,
whose style is a lot like Mogwai. Not quite as good as “Explosions in the Sky”,
but still very good.
Red Sparowes, “Buildings Begin to Stretch Wide”: even more post-reck. Yes, I do love my post-rock. The Red Sparowes have a louder, harder sound. Much less derivative of Mogwai than the last two bands. The Red Sparowes are a favorite of mine. In fact, for people who haven’t listened to any post-rock before, the two things I recommend are Red Sparrowes, and “Godspeed You Black Emperor”.
The Klezmatics, “In Kamf”: The first time I ever seriously listened to Klezmer was back in college. I was really involved in Hillel (a campus Jewish organization), and we sponsored a concert by a NY klezmer band called the Klezmaniacs. Two of the members of the Klezmaniacs are also members of the Klezmatics; this album is the first klezmer album I ever bought. This isn’t one of my favorite songs on it; I prefer the dance music.
Thee Silver Mt. Zion Memorial Orchestra & Tra-La-La Band, “Goodbye Desolate Railyard”: Yet more post-rock; one of the sillier names that “A Silver Mt. Zion” has used. In
general, I really like ASMZ, but the leader’s voice is awful, and this track has a strong vocal lead. So it’s just an eh. In general, I love this album, just not
this track.
David Sylvian and Robert Fripp, “The First Day”: this is one of my overall favorite albums. I love just about everything Fripp has ever done. Sylvian is excellent, except that he’s sometimes lacking in energy. The two of them together are absolutely stunning. Everything on this album is pure brilliance.
Victor Wooten, “Happy Song”: a very appropriately named song. Vic Wooten is the bass player from the Flecktones, and he’s an incredible master
of the electric bass. The guy is up there with folks like Jaco Pastorius in
his skill at the bass. This is a catchy, bouncy, happy little song which has some really stunning bass work going on in the back. It’s not a style of music that I’m wild about, but it’s worth it to hear that kind of ass-kicking bass. Once it gets past the intro, into the middle of the song, it’s just dazzling. The first time
I heard this, I was in the car with my wife, and they were playing it on NPR. I was listening, saying “I gotta find out who this is, they’re amazing. The style sounds a lot like Vic Wooten, but I don’t think he’s quite that good”. And then the song finishes, and they start talking to him, and it’s Vic.
Metaphor, “When it All Comes Together”: Metaphor is a great, unknown neo-progressive band. This is very typical of their sound. You can get their stuff online from bitmunk, which is one of my favorite places for buying music.
Tony Levin, “What Would Jimi Do?”: a wonderful track from another
bass genius. In a wonderful takeoff from the garbage being spewed by christian loonies, the song is about asking “What would Jimi Do?”
This is about as off-topic as it gets, but I can’t resist posting. Y’see, I’m a spectacularly uncoordinated person. I can trip over nothing. If you throw me a ball, the chances of my being able to catch it are frighteningly low. When I was in high school, my physics teacher invented the Carroll Scale of Spasticity for measuring the incidents in which I damaged or destroyed a lab experiment by tripping or bumping things (and he was still telling students about it 6 years later when my sister’s friends were in his class).
So this video is amazing. It makes me feel coordinated. It makes the kinds of things that happen to me look downright mild. This was a live TV broadcast. It’s just eight seconds long. Enjoy!
As promised, now we’re going to look at the first major block
cipher: the DES. DES stands for “data encryption standard”; DES was the first encryption system standardized by the US government for official use. It’s an excellent example of a strong encryption system; to this day, while there are several theoretical attacks, there’s no feasible attack on a single DES-encrypted message that’s better than brute force. The main problem with DES is the shortness of its key: only 56 bits, which makes it downright practical to implement brute-force attacks against it using today’s hardware.
DES works with 64 bit blocks, and a 56 bit key. As an interesting aside, there are some serious questions about just why the standard key was 56 bits. Officially, the key length is 64 bits, but during the standardization process, the key was modified at the request of the NSA so that 8 of the bits were used as parity checks – that is, as extra bits that could be used for checking the validity of a key. 8 bits for parity checking on a 56 bit key is really overkill – in fact, putting parity checks into the key at all is really rather questionable. There’s been a lot of speculation that either
the NSA knew some kind of trick that could be used against a 56 bit key, or that 56 bits put the encryption within the range of what they could crack using a brute force attack. But no one has ever admitted to either solution, and as far as I know, no one knows of any way that a 56 bit key could have been feasibly cracked using brute force with the technology of the time.
Anyway – getting past the politics of it, it’s still a really interesting
system. It’s a rather elegant combination of simplicity and complexity. It’s got a simple repetitive structure based on lookup tables, which gives it its deceptive simplicity; but those lookup tables are actually an implementation of a very complex non-linear discrete mathematical system.
Where encryption starts getting really interesting, in my opinion, is
block ciphers. Block ciphers are a general category of ciphers that
are sort of a combination of substitution and transposition ciphers, and
sort of something entirely different. They’re really fascinating
things, but they’re pretty complicated.
The basic core of block ciphers is encryption of blocks. A block is
a fixed-length series of bits. The basic cipher is a pair of functions (E,E-1), where E (the encryption function) takes a block B and a key K, and generates a new block B’=E(K,B), which is the encrypted form of the block; and E-1 (the decryption function) takes a key and an encrypted block, and returns the original plaintext block: B=E-1(K,B’).
