I was away on vacation this week, which explains the near-total
silence on the blog. But at least you’ll get a FRT from me. And some
nice posts on cryptography and game theory coming next week.
- Gogol Bordello, “Dub the Frequencies of Love”: Eastern
european gypsies meet punk meets reggae.
- Hawkwind, “Urban Guerilla”: A live recording of a rather
catchy tune by Hawkwind. Personally, I prefer their spacier stuff.
- Porcupine Tree, “Glass Arm Shattering”: Porcupine Tree is
always great. This one starts off slow and quiet, and then builds.
- IQ, “Harvest of Souls”: Peter Nichols, the leader of IQ
in their incarnation on this album is nothing short of a
genius. This is a wonderful song – which is not surprising, since
everything from the “Dark Matter” album is wonderful.
- Naftule’s Dream, “Afterwards”: Lately, I’ve been very
into Klezmer – particularly the more modern jazzy/experimental type.
Naftule’s Dream is one of my favorite bands of this style. They
record traditional Klezmer as “the Shirim Klezmer Orchestra”, and
their more out-there stuff as “Naftule’s Dream”. This is a
deceptively mellow track, which has a lot of strange stuff going on.
- Genesis, “Supper’s Ready”: early Genesis – this track is
the direct precursor of “The Lamb Lays Down on Broadway”, which is
one of the best works in the history of rock music.
- Sonic Youth, “Lights Out”
- Flying Bulgar Klezmer Band, “Buma”: More Klez.
- Peter Gabriel, “Signal to Noise”: a masterpiece off of
Peter Gabriel’s latest album. This is an amazing track – blending
orchestral backing, African singing and drumming, and some
traditional progressive tropes. Really great – this gives me chills
every time I listen to it.
- The Flower Kings, “A King’s Prayer”: As far as I’m
concerned, the Flower Kings can do no wrong. I can pick out any
track off of any FK album, and be pretty much guaranteed to
hear something amazing.
The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be
rather dull; in their pure form, they’re very simple, and not very difficult
to crack, even without computers. But some of the most sophisticated
modern ciphers can be looked at as a sort of strange combination of
substitution and transposition, so it’s worth looking at.
A transposition cipher doesn’t change the characters in the plain-text when it generates the cipher-text – it just re-arranges them. It applies some kind of permutation function to the text to produce a re-arrangement, which can be reversed if you know the secret to the the permutation.
An alert reader sent me link to a stupid
article published by Reuters about the Olympics and Astrology.
It’s a classic kind of crackpot silliness, which I’ve described
in numerous articles before. It’s yet another example of pareidolia – that is, seeing patterns where there aren’t any.
When we look at large quantities of data, there are bound
to be things that look like patterns. In fact, it would be
surprising if there weren’t apparent parents for us to find. That’s
just the nature of large quantities of data.
In this case, it’s an astrologer claiming to have found
astrological correlations in who wins olympic competitions:
Something fishy is happening at the Olympic Games in Beijing. Put it all down to the stars.
Forget training, dedication and determination. An athlete’s star sign could be the secret to Olympic gold.
After comparing the birthdates of every Olympic winner since the modern Games began in 1896, British statistician Kenneth Mitchell discovered gold medals really are written in the stars.
He found athletes born in certain months were more likely to thrive in particular events.
Mitchell dubbed the phenomenon “The Pisces Effect” (pisces is Latin for fish) after finding that athletes born under the sign received around 30 percent more medals than any other star sign in events like swimming and water polo.
I found a fun meme via Rev. BigDumbChimp, involving food. I’m a sucker for anything involving eating.
- Venison: Nope.
- Nettle tea: yes. Didn’t like it.
- Huevos rancheros: Yes, yummy.
- Steak tartare: nope.
- Crocodile: Yup. Mediocre. Not a bad flavor, but it had a nasty texture.
- Black pudding: Gads, no.
- Cheese fondue: Yup.
- Carp: Yup.
- Borscht: I’m an Ashkenazi Jew, of course I’ve had borscht. Out of a jar, it’s absolutely, mind-bogglingly horrible. Cooked fresh, it’s at best mediocre.
- Baba ghanoush: Yum!
- Calamari: Tried it once. Turned out that I’m violently allergic
to it. Not one of my more pleasant food experiences.
- Pho: Nope, but I’ve had the chinese version (Nu Rou Mien).
- PB&J sandwich: of course.
- Aloo gobi: Yup; in fact, I make it myself. Great stuff – one of the
very best things you can do with a cauliflower.
- Hot dog from a street cart: of course. I’m a NYer.
- Epoisses: One of my favorite cheeses! Nothing compares
to Epoisses washed in Sauvingon blanc. Yum.
- Black truffle: yup. Overrated. They’re very good, but
considering what they cost, they need to be *better* than just very good.
- Fruit wine made from something other than grapes: I’ve had hungarian
brandies made from peaches, but that’s not wine. I’ve had something
that’s called blackberry wine, but it’s really blackberry juice mixed
with neutral brandy and sugar, so I assume that doesn’t count. So I guess
that’s a no.
- Steamed pork buns: Nope. I don’t like pork.
- Pistachio ice cream: yes.
- Heirloom tomatoes: Oh, yes. Really good, fresh, vine-grown
tomatoes – not the commercially bred shippable kind, but the kind
that you get from the farmer, and have to carry carefully because
they’ll bruise – are one of the greatest culinary treasures of the
world. The things you buy in the store simply are not
- Fresh wild berries: Yup. As a kid, I lived in a house on a wooded lot,
and there were wild raspberries. The wild ones really do taste better.
- Foie gras: Yes. Another favorite. Yeah, it’s not particularly nice for
the duck. I don’t care; it’s too damned good. Not something I’d
eat every day, but it’s a treat when I can get it.
- Rice and beans: Yes.
- Brawn, or head cheese: No. And I hopefully never will!
- Raw Scotch Bonnet pepper: Yes, accidentally. My grad-school roommate
bought some, not knowing what they were. And then he made me taste one.
The heat was mind-boggling, and my eyes starting burning, so I rubbed
them. Wound up spending the next half-hour or so in the the bathroom soaking my eye in cold water.
- Dulce de leche: Yes.
- Oysters: Yes. I love oysters.
- Baklava: Yes.
- Bagna cauda: Yes, I’ve made it.
- Wasabi peas: Yes. Eh.
- Clam chowder in a sourdough bowl: a favorite of mine.
- Salted lassi: nope.
- Sauerkraut: NY Jew – of course!
- Root beer float: yup.
- Cognac with a fat cigar: I don’t do the smoking thing. Cognac, yes;
but it’s not my favorite. I prefer the subtler Armagnac in the french
grape brandies, or Calvados if I can get away from the grapes.
- Clotted cream tea: Yes.
- Vodka jelly/Jell-O: No.
- Gumbo: Yes.
- Oxtail: No.
- Curried goat: Yes. I worked for a computer store owned by an
Indian family during college. They had a party that they invited
all of the employees too. The only thing that wasn’t too hot for us
to eat was goat. Not thrilling, but not bad.
- Whole insects: Nope.
- Phaal: looked it up to see what it was. I’m honestly not sure.
See my story two up – I tried nibbles of a few things there, which were
considerably spicier than goat vindaloo. So maybe. But since I don’t
know, I’ll count this as a “no”.
- Goat’s milk: Nope. Lots of goat’s milk cheeses, but not the milk itself.
- Malt whisky from a bottle worth £60/$130 or more: Once. Didn’t
much like it.
- Fugu: Nope.
- Chicken tikka masala: Who hasn’t had this?
- Eel: One of the most wonderful tasting fish in the world. I adore
- Krispy Kreme original glazed doughnut: Yes. Not impressed.
- Sea urchin: No.
- Prickly pear: Yes. Eh.
- Umeboshi: Yes. Eh.
- Abalone: Yes. Eh.
- Paneer: Yes. Eh.
- McDonald’s Big Mac Meal: Yes. Ick.
- Spaetzle: I’ve never had German spaetzle; I have had the hungarian
galushka, which are supposedly pretty much the same. It’s wonderful.
I’ve also had Da Sha Mien, which is sort of the chinese equivalent, also
wonderful. There’s nothing quite like the texture of a fresh dough
- Dirty gin martini: Nope. I’m not a huge martini fan, and a martini
with the olive juice mixed in just sounds awful.
- Beer above 8% ABV: Oh, yes. In my opinion, most of the beers worth drinking are up there. I tend to like Belgian bottle-fermented ales,
and they can get up to 12-14% ABV. I also once had a fantastic
barley wine, which is basically a strongly hopped beer coming in at 18% ABV!
- Poutine: Yum! My wife is Canadian, and she introduced me to it. If you’ve never heard of it, it’s french fries with fresh cheese curds
and brown gravy. It’s really, really fantastic stuff. We mail order
cheese curds from Wisconsin so that we can make it at home!
- Carob chips: Yes. It’s no substitute for chocolate.
- S’mores: of course.
- Sweetbreads: Nope. Very few organ meats appeal to me.
- Kaolin: Not sure what this is… A quick search suggests one of the
ingredients of kaopectate – a horrific substance with which I have
had entirely too much experience. (I’ve got some really awful stomach
- Currywurst: Like I said, I’m not a fan of pork. If you could make this with some other meat, it sounds yummy.
- Durian: Nope. I’d love to try it. Another grad school roommate of mine
was from Bangladesh, and raved about how good it was despite the smell.
Since when it comes to cheese, the stinkier it is, the more I like it,
I suspect that I’d really enjoy it.
- Frogs’ legs: Yes. Greasy, bland. Not thrilling.
- Beignets, churros, elephant ears or funnel cake: all of the above.
- Haggis: What am I, crazy? Hell no!
- Fried plantain: Yes. Ech.
- Chitterlings, or andouillette: Nope.
- Gazpacho: Yes! Love it when it’s a bit chunky and nice and spicy!
- Caviar and blini: Yes. Overrated.
- Louche absinthe: Nope. Definitely want to.
- Gjetost, or brunost: Yes. Some friends are big fans of it, and they’ve
gotten me to try it. It’s very peculiar.
- Roadkill: No.
- Baijiu: I think so. When I went to Taiwan to meet my in-laws, we went out to dinner with some of their friends, and we had some kind of very
strong, warm stuff. I think it was Baijiu, but I’m not sure. I definitely
did not like whatever it was.
- Hostess Fruit Pie: Yes.
- Snail: Yum!
- Lapsang souchong: never tasted it. Smelled it, because of another
guy I knew who drank the stuff constantly, but every time he brewed
a cup, the entire room would stink like stale cigar smoke. Ech.
- Bellini: Yup, at one of Mario Batalli’s restaurants. My wife ordered
it, and I had a taste. Very nice, refreshing.
- Tom yum: Oh, yes. One of my favorite soups!
- Eggs Benedict: Yes. As I keep saying, I’m not a big pork fan, so
I prefer many of the numerous variants better than the traditional.
Benedict with fresh cold-smoked pacific salmon is my favorite.
- Pocky: Yes. Eh.
- Tasting menu at a three-Michelin-star restaurant: Nope. Until
very recently, I was a non-meat-eater, and I still can’t stand most
Pork or most organ meats. So there’s not much point in the great
French restaurants. I have done chefs tasting menu at Nobu, which
deserves to be a three-star.
- Kobe beef: Nope.
- Hare: Nope.
- Goulash: Yes! I really like Hungarian food. Goulash, paprikash,
roast goose with red cabbage, etc. Hungarian food isn’t fancy, but
it’s really wonderful.
- Flowers: Yes, in many forms. I’ve had candied flowers, flowers in
salads, flowers in cookies, stuffed zucchini flowers, etc.
- Horse: Nope.
- Criollo chocolate: I’m not sure. I’ve had a lot of very fine chocolates,
but I’m not sure if any of it was Criollo. Probably not – the makers
generally flaunt it if they use it, so I’d probably know.
- Spam: Nope.
- Soft shell crab: One of my favorite foods in the entire world. There is
absolutely nothing as wonderful as a Maryland Blue softshell.
- Rose harissa: no. I’ve had harissa, but never rose. It sounds wonderful!
- Catfish: Yes. I love farmed catfish; wild is a bit overwhelming.
- Mole poblano: Yes, yummy.
- Bagel and lox: New York Jew. Of course!
- Lobster Thermidor: no. I’m not a huge lobster fan. It’s good, but
not my favorite thing. Every time I’ve had a chance to order it,
there’s been something I’d rather have.
- Polenta: Yes. Ick. I hate polenta.
- Jamaican Blue Mountain coffee: Yes. Overrated. I think that many
of the really top-quality Indonesian coffees are better.
- Snake: Nope.
The Rev also added a few extras.
- Elk: No.
- Ostrich: Yes. Several times. I really don’t like it. I keep trying it
cooked different ways, because people who’s taste I trust keep
telling me that it’s something I should really love. But every time
I’ve tried it, I’ve been disappointed.
- Moose: No.
- Whole hog BBQ. I’ve been to BBQs where they did it, but since I don’t
like pork, I didn’t have any. (Just the smell of it cooking was
unpleasant to me; there’s just something about pork that I can’t stand.
It’s not a kosher thing, because there’s plenty of non-kosher stuff that
I eat all the time.)
- Wine @ >$400/bottle.: Nope. I’d like to, but I can’t afford it.
- Home made bacon/sausage: again, no pork.
- Chocolate and chilis: an amazing combination. I found a south american chocolate bar with chilis in it. Strange from an american perspective – they didn’t do the kind of very smooth chocolate that we tend to like. This was brittle, with hard crystals of sugar in it, and visible flecks of chili pepper. It was fantastic.
- Chittlins: Nope.
- Moonshine: Nope.
- Quail eggs: Yup.
And I’ll add a few of my own that I’ve tried:
- Monkfish liver: nice, but not exceptional.
- Live scallop: amazing!
- Fried chicken giblets.
- Duck cracklings. Yummy! This is what you get when you take duck skin,
and render it for duck fat. You cook it very slowly to get out the fat
without getting any burned skin flavor in it. When you’re done, you’ve got
these crispy little bits of duck skin fried in duck fat. A sprinkle of
salt, and you’ve got something amazing.
- Grappa: amazingly wonderful.
Someone sent me some questions about information theory; or actually,
about some questions raised by a bozo creationist arguing about information
theory. But the issues raised are interesting. So while I’m
nominally snarking at a clueless creationist, I’m really using it
as an excuse to talk about one of my favorite mathematical subjects.
The creationist is confused by the information theory idea of information and complexity. That is somewhat confusing.
Intuitively, we think of information in terms of semantics and communication. We think that information is related to semantic content. And our understanding of semantic content comes from language. So we expect
things that are rich in information to be highly structured, like language.
One of the things that I always like to talk about is how a natural
expression of randomness will periodically produce something that appears
non-random – and in fact, if it doesn’t, then it’s not really random!
This weeks friday random 10 is a great example of this. In the past, when I’ve been in a mood for a particular kind of music, I’m done random shuffles within a playlist containing the stuff I feel like listening to. I didn’t do that this week. I let iTunes randomly pick out 10 things, and these are the first ten from the list. It
turned out to be a nice week for progressive music.
- IQ, “Infernal Chorus”: IQ is one of the great neo-progressive bands that started off as
a Genesis ripoff. A lot of those bands have gone on to do a two-album magnum-opus work that
tries to be comparable to “The Lamb Lays Down on Broadway”. IQ is the only one that’s really been
able to pull it off. “Infernal Chorus” is off of a double-album concept set by IQ called “Subterannea”,
and in my opinion it’s as good as “Lamb”. Magnificent.
- The Flower Kings, “The Devil’s Danceschool”: Instrumental flower kings featuring
improv played on a trumpet piped through a distortion rig. Seriously out-there; they wander pretty far
away from the tonic chord in this. It’s the kind of thing that only the Flower Kings could really pull off.
- Yes, “Our Song”: Ick.
- Porcupine Tree, “Mellotron Scratch”: Another great neo-progressive band. Porcupine Tree started
off as a joke, and turned into one of the best serious bands out there. This is a mellow piece off of their
- The Police, “King of Pain”: a track off of an album that Sting one described as a “nasty piece of work”.
It’s all very dark, but it’s good music.
- Naftule’s Dream, “Emperor Red”: progressive Klezmer, with a seriously bluesy feel to it.
- Marillion, “Paper Lies”: Brave is one of my favorite Marillion albums. Every bit of it is
wonderful. This is a track that’s actually sort of catchy, which seems sort of incongruous considering how
totally dark “Brave” is. But it fits in, and it’s a great song.
- Spock’s Beard, “Skeletons at the Feast”: Another band that started off as a Genesis ripoff. They
did try to do their own “Lamb”, called “Snow”, but unlike IQ, they didn’t pull it off so well. After that,
their founder left, and it took them a while to find their feet again. But they did, and this album is
- Genesis, “Here Comes the Supernatural Anaesthetist”: I really didn’t plan this – it’s just
the way the shuffle turned out. But here’s a track from “Lamb”. Not my favorite track, but every on Lamb is
- Metaphor, “Battle of the Archons”: A relatively unknown neo-progressive band. Definitely not
from the Genesis ripoff school.
To understand why serious encryption algorithms are so complex, and why it’s
so important to be careful with the critical secrets that make an encryption
system work, it’s useful to understand something about how people break
encryption systems. The study of this is called cryptanalysis, and it’s
an amazingly fascinating field of applied mathematics. I’m going to be
interspersing information about cryptanalysis with my cryptography posts. One
thing to remember here is that we’ll be talking about it mainly in the context
of how you can break an encryption system – but cryptanalysis is also used for
designing cryposystems, because you can only design a successful cryptosystem by
thinking about how it can defeat the ways that it could be broken.
One caveat: I’m going to be describing cryptanalysis in terms of how I understand it, which is sometimes different from classical descriptions by cryptanalysists. My
understanding is strongly rooted in computation and information theory, rather than pure math. So sometimes my presentation will be a bit different, but hopefully by staying in the ground where I’m most comfortable, I can do a better job of making it comprehensible.
So, last time, we looked at simple substitution ciphers. In a substitution
cipher, you take each letter, and pick a replacement for it. To encrypt a
message, you just substitute the replacement for each instance of each letter.
As I explained, it’s typically pretty each to break that encryption – the basic
secret of the encryption is the substitution system, and it’s pretty easy to
figure that out, because the underlying information being encrypted still has a
lot of structure.
There are a couple of easy improvements on a simple substitution cipher, some of which came up in the comments. For example, two
good easy improvements are:
- Instead of defining substitutions for single characters, define
substitutions for groups (pairs, triplets) of characters. This improves things,
because it allows you to work with groups that will reduce the visibility of
patterns. Still, because there’s so much structure in human language, given
enough data, an encrypted message is still likely to be easy to decode. So this
is great for short messages, but not for anything bigger.
- Multiple substitutions: instead of always substituting, say, “x” for “a”,
substitute each letter with a two-digit number. Then for common letters, allow
multiple possible substitutions. By assigning many codes to common letters, and
few codes to uncommon letters, you can make the coded symbols appear with
roughly equal frequency. This can seriously hamper frequency based analyses.
Both of those changes help. They work particularly well when combined. To do
a two-character version of that, you create a list of all possible two-character
sequences. Then you generate a frequency table for how often each two-character
sequence occurs in a large sample of the kind of text you’re going to encode.
Then, finally, you assign a number of substitutions for each pair so that they
occur with approximately equal frequency. That gives you a pretty good
Still, it’s not great. Given enough encoded text, it can be cracked with a
relatively small amount of computational power. If I know the basic idea of the
cipher, and I’ve got a decent amount of encoded text, I can write a program that
will figure it out pretty quickly. Plus, it’s really a lot of work to generate
the cipher – you need to generate frequency tables, and work out the number of
substitions, etc. It’s definitely not trivial to set up, and it’s still pretty
easy to crack.
For that reason, those kinds of solutions aren’t used much – there’s a lot
of prep work, and the secret that you need to share with your partner is large
and complicated. You can get better quality with less effort and a
simple secret using a different scheme called a rotating cipher.
The starting point talking about encryption is to understand
what the point of it is; what it’s supposed to do, what problems it’s supposed to avoid.
Encryption is fundamentally about communication: you’ve got two parties who want to communicate, but don’t want anyone else to be able to listen in.
They way that you do that is by sharing a secret. You use that secret to somehow modify the information that you’re going to send, so that it can’t be read by someone who doesn’t have the secret. People often think of encryption as a way of using a password to hide information, but a password is just one of many kinds of secrets that you can use. The secret that you share with your counterpart can be a password, a number, a textbook, or just about anything else you can imagine.