Monthly Archives: August 2008

Friday Random Ten, The Vacation Edition

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.

  1. Gogol Bordello, “Dub the Frequencies of Love”: Eastern
    european gypsies meet punk meets reggae.
  2. Hawkwind, “Urban Guerilla”: A live recording of a rather
    catchy tune by Hawkwind. Personally, I prefer their spacier stuff.
  3. Porcupine Tree, “Glass Arm Shattering”: Porcupine Tree is
    always great. This one starts off slow and quiet, and then builds.
  4. 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.
  5. 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.
  6. 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.
  7. Sonic Youth, “Lights Out”
  8. Flying Bulgar Klezmer Band, “Buma”: More Klez.
  9. 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.
  10. 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.

Transposition Ciphers

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.

Continue reading

Friday Random 10, August 22

  1. Solas, “Darkness, Darkness”: One of my favorite Irish
    bands doing a great cover of an old song.
  2. A Silver Mt. Zion, “Goodbye Desolate Railyard”: a decent
    ASMZ track, but not an outstanding one.
  3. Mogwai, “Acid Food”: Anything by Mogwai is terrific. This
    is no exception.
  4. Kansas, “Myriad”: One of my favorite tracks of the latest
    from Kansas.
  5. Metaphor, “Stella Maris”: I just got this album today, and haven’t even gotten to listen to it all the way through yet, so I haven’t really formed a strong opinion yet. But it sounds like Metaphor, and that’s a good thing.
  6. Rush, “The Enemy Within”: A classic old Rush tune.
  7. David Sylvian and Robert Fripp, “Jean the Birdman”: this is
    pretty much what you’d expect from Fripp and Sylvian. Sylvian’s
    crooning; Fripp playing with tape loops and strange tonality. Even
    though it’s what you expect, it’s still amazing – these are two of the
    most creative guy’s you’ll find anywhere, and when they work together,
    the result is something special.
  8. Porcupine Tree, “The Moon Touches Your Shoulder”: A bit
    off of PTs most traditionally progressive album. Not my favorite
    bit of the album, but the whole album is amazing.
  9. Kruzenshtern & Parahod, “Sippurim”: K&P is one of my
    favorite things to listen to lately. I usually describe it as
    progressive klezmer, which I think is accurate; but it’s also
    not really adequate. These guys are stretching the boundaries so
    far that it’s hard to describe. There’s a very strong Klezmer element;
    but also very strong Jazz and Rock influences. Their stuff is hard
    to track down, but well worth the effort. It’s really spectacular.
  10. Tie the Bonnet: Traditional Irish, from the masters. Lunasa
    is wonderful. This, however, is not one of my favorite bits by
    them. Like many popular Irish bands, they tend to over-rush
    the tempo. It’s damned impressive, but it deprives the music of some
    of its heart. This stuff is music to dance to – but they’re playing it at tempos that no one could ever dance to.

Astrology and the Olympics

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.

Continue reading

The Food Experience Meme

I found a fun meme via Rev. BigDumbChimp, involving food. I’m a sucker for anything involving eating.

  1. Venison: Nope.
  2. Nettle tea: yes. Didn’t like it.
  3. Huevos rancheros: Yes, yummy.
  4. Steak tartare: nope.
  5. Crocodile: Yup. Mediocre. Not a bad flavor, but it had a nasty texture.
  6. Black pudding: Gads, no.
  7. Cheese fondue: Yup.
  8. Carp: Yup.
  9. 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.
  10. Baba ghanoush: Yum!
  11. Calamari: Tried it once. Turned out that I’m violently allergic
    to it. Not one of my more pleasant food experiences.
  12. Pho: Nope, but I’ve had the chinese version (Nu Rou Mien).
  13. PB&J sandwich: of course.
  14. Aloo gobi: Yup; in fact, I make it myself. Great stuff – one of the
    very best things you can do with a cauliflower.
  15. Hot dog from a street cart: of course. I’m a NYer.
  16. Epoisses: One of my favorite cheeses! Nothing compares
    to Epoisses washed in Sauvingon blanc. Yum.
  17. Black truffle: yup. Overrated. They’re very good, but
    considering what they cost, they need to be *better* than just very good.
  18. 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.
  19. Steamed pork buns: Nope. I don’t like pork.
  20. Pistachio ice cream: yes.
  21. 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
    tomatoes.
  22. 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.
  23. 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.
  24. Rice and beans: Yes.
  25. Brawn, or head cheese: No. And I hopefully never will!
  26. 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.
  27. Dulce de leche: Yes.
  28. Oysters: Yes. I love oysters.
  29. Baklava: Yes.
  30. Bagna cauda: Yes, I’ve made it.
  31. Wasabi peas: Yes. Eh.
  32. Clam chowder in a sourdough bowl: a favorite of mine.
  33. Salted lassi: nope.
  34. Sauerkraut: NY Jew – of course!
  35. Root beer float: yup.
  36. 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.
  37. Clotted cream tea: Yes.
  38. Vodka jelly/Jell-O: No.
  39. Gumbo: Yes.
  40. Oxtail: No.
  41. 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.
  42. Whole insects: Nope.
  43. 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”.
  44. Goat’s milk: Nope. Lots of goat’s milk cheeses, but not the milk itself.
  45. Malt whisky from a bottle worth £60/$130 or more: Once. Didn’t
    much like it.
  46. Fugu: Nope.
  47. Chicken tikka masala: Who hasn’t had this?
  48. Eel: One of the most wonderful tasting fish in the world. I adore
    eel.
  49. Krispy Kreme original glazed doughnut: Yes. Not impressed.
  50. Sea urchin: No.
  51. Prickly pear: Yes. Eh.
  52. Umeboshi: Yes. Eh.
  53. Abalone: Yes. Eh.
  54. Paneer: Yes. Eh.
  55. McDonald’s Big Mac Meal: Yes. Ick.
  56. 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
    dumpling.
  57. Dirty gin martini: Nope. I’m not a huge martini fan, and a martini
    with the olive juice mixed in just sounds awful.
  58. 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!
  59. 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!
  60. Carob chips: Yes. It’s no substitute for chocolate.
  61. S’mores: of course.
  62. Sweetbreads: Nope. Very few organ meats appeal to me.
  63. 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
    problems.)
  64. Currywurst: Like I said, I’m not a fan of pork. If you could make this with some other meat, it sounds yummy.
  65. 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.
  66. Frogs’ legs: Yes. Greasy, bland. Not thrilling.
  67. Beignets, churros, elephant ears or funnel cake: all of the above.
  68. Haggis: What am I, crazy? Hell no!
  69. Fried plantain: Yes. Ech.
  70. Chitterlings, or andouillette: Nope.
  71. Gazpacho: Yes! Love it when it’s a bit chunky and nice and spicy!
  72. Caviar and blini: Yes. Overrated.
  73. Louche absinthe: Nope. Definitely want to.
  74. Gjetost, or brunost: Yes. Some friends are big fans of it, and they’ve
    gotten me to try it. It’s very peculiar.
  75. Roadkill: No.
  76. 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.
  77. Hostess Fruit Pie: Yes.
  78. Snail: Yum!
  79. 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.
  80. Bellini: Yup, at one of Mario Batalli’s restaurants. My wife ordered
    it, and I had a taste. Very nice, refreshing.
  81. Tom yum: Oh, yes. One of my favorite soups!
  82. 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.
  83. Pocky: Yes. Eh.
  84. 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.
  85. Kobe beef: Nope.
  86. Hare: Nope.
  87. 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.
  88. Flowers: Yes, in many forms. I’ve had candied flowers, flowers in
    salads, flowers in cookies, stuffed zucchini flowers, etc.
  89. Horse: Nope.
  90. 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.
  91. Spam: Nope.
  92. Soft shell crab: One of my favorite foods in the entire world. There is
    absolutely nothing as wonderful as a Maryland Blue softshell.
  93. Rose harissa: no. I’ve had harissa, but never rose. It sounds wonderful!
  94. Catfish: Yes. I love farmed catfish; wild is a bit overwhelming.
  95. Mole poblano: Yes, yummy.
  96. Bagel and lox: New York Jew. Of course!
  97. 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.
  98. Polenta: Yes. Ick. I hate polenta.
  99. Jamaican Blue Mountain coffee: Yes. Overrated. I think that many
    of the really top-quality Indonesian coffees are better.
  100. Snake: Nope.

The Rev also added a few extras.

  1. Elk: No.
  2. 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.
  3. Moose: No.
  4. 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.)
  5. Wine @ >$400/bottle.: Nope. I’d like to, but I can’t afford it.
  6. Home made bacon/sausage: again, no pork.
  7. 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.
  8. Chittlins: Nope.
  9. Moonshine: Nope.
  10. Quail eggs: Yup.

And I’ll add a few of my own that I’ve tried:

  1. Monkfish liver: nice, but not exceptional.
  2. Live scallop: amazing!
  3. Fried chicken giblets.
  4. 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.
  5. Grappa: amazingly wonderful.

Why is randomness informative? Correcting the Clueless Creationists

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.

Continue reading

Friday Random 10, August 15

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.

  1. 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.
  2. 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.
  3. Yes, “Our Song”: Ick.
  4. 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
    “Deadwing” album.
  5. 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.
  6. Naftule’s Dream, “Emperor Red”: progressive Klezmer, with a seriously bluesy feel to it.
  7. 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.
  8. 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
    terrific.
  9. 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
    incredible.
  10. Metaphor, “Battle of the Archons”: A relatively unknown neo-progressive band. Definitely not
    from the Genesis ripoff school.

Introducing Cryptanalysis

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.

Continue reading

Rotating Ciphers

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:

  1. 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.
  2. 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
system.

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.

Continue reading

Simple Encryption: Introduction and Substitution Ciphers

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.

Continue reading