pretty much everyone who studies cryptography a little eventually thinks they’re clever and comes up with their own encryption scheme. of course, since they’re just amateurs, most of these schemes are easily broken by any expert who has time to crack it. but experts’ time is precious so the end result is thousands and thousands of (weak) amateur encryption routines floating around. still, coming up with your own encryption scheme is fun and good practice so here’s my attempt. i at least know enough to do a little analysis and maybe point out some of the interesting parts. it’s a pretty straightforward cipher so i’d be surprised if no one else has independently discovered it, but i couldn’t find anything similar in the small collection of crypto books in my apartment.
<p>first, i need to explain a little about pseudo-random number generators (<span class="caps">PRNG</span>s). since it’s really impossible to generate true randomness with a deterministic machine like a computer (as Von Neumann said: “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”). so when computers need “random” numbers, they resort to <span class="caps">PRNG</span>s, often using a “seed” from the outside world. a <span class="caps">PRNG</span> is essentially a mathematical function that given a particular number as input will give you another number as an output in a way that doesn’t really have any predictableness or pattern to it. you generate a series of random numbers by feeding the output of each cycle back in as input. you can generally prove that for any starting “seed”, a given <span class="caps">PRNG</span> will eventually loop back to the beginning and give that seed as output after a certain number of cycles. the better the <span class="caps">PRNG</span>, the more cycles you have to go through before you get this repetition. the algorithms most cryptographic applications use will only loop after somewhere on the order of 2^256 cycles. since that’s more than the number of atoms in the universe, even though it’s not “true” randomness it’s usually good enough for practical applications.</p>
<p>the other key thing to understand with <span class="caps">PRNG</span>s is that they should be repeatable. meaning that if you give it the same seed twice, you will get the same sequence of random numbers both times. this is useful because it lets you check the results of some simulation that you may have used the numbers for. it also means that if you really want random numbers, you have to be careful to pick a seed that can’t be guessed. so usually some kind of outside source of randomness will be used as the seed, eg, a number based on the time between keystrokes as the user types.</p>
<p>also a note about one-time pads. one-time pads are the only <em>provably</em> secure cipher. as long as the key used is longer than the message being encrypted, is random, and the same key is <strong>never</strong> used more than once, a one-time pad provides perfect encryption. the problem is that the restriction of keys never being used more than once makes them somewhat impractical.</p>
<p>my cipher essentially makes use of a <span class="caps">PRNG</span> to generate keys for one-time pads. here’s how it works:</p>
<p>Alice and Bob have a shared number K<small><sub>A-B</sub></small> that they generated randomly (using a “true” random number generator) that’s about 128 bits long (or longer if they’re really paranoid). they’re the only ones that know the number and have gone to great pains to keep it secret. there is also a <span class="caps">PRNG</span> P which is public, has a really long period (ie, it’s a good <span class="caps">PRNG</span>) and is repeatable.</p>
<p>when Alice wants to send a message to Bob, she generates another random number S (also about 128 bits long). then she takes the bitwise <span class="caps">XOR</span> of S and K<small><sub>A-B</sub></small> (<span class="caps">XOR</span> is the exclusive-or logical operation: 1 <span class="caps">XOR</span> 1 = 0, 1 <span class="caps">XOR</span> 0 = 1, 0 <span class="caps">XOR</span> 1 = 1, 0 <span class="caps">XOR</span> 0 = 0). she uses the result of this <span class="caps">XOR</span> as a seed for P. the string of random numbers that P produces, she uses as a one-time pad key for encrypting her message M. she takes the resulting ciphertext C and sends (C,S) to Bob. </p>
<p>to decrypt, Bob takes S, <span class="caps">XOR</span>s it with K<small><sub>A-B</sub></small> and feeds it to P to produce the one-time pad key. with that he decrypts C to retrieve M.</p>
<p>that’s all there is to it. what i think makes this algorithm interesting is that it offloads all the security to K<small><sub>A-B</sub></small> being secret and large enough that guessing it would be pretty much impossible and to the <span class="caps">PRNG</span> not being predictable. if fact it should be fairly simple to prove that cracking this scheme is <em>entirely</em> dependent on discovering a pattern in the <span class="caps">PRNG</span>. while i’m not an expert, i believe that there are some pretty good <span class="caps">PRNG</span> algorithms out there. however, i would guess that, similar to how we suspect but haven’t ever proven that factoring large numbers is extremely difficult, the best we could do for a <span class="caps">PRNG</span> is suspect but not prove its lack of predictability.</p>
<p>the drawback may be that since you have to generate a new random S for every message, the generation of S could be slow if you require that S also be truely random. i’m not sure if that’s really a requirement though; it’s probably good enough if S was generated from a <span class="caps">PRNG</span> that was given a truely random seed. in that case, we could also prove that the speed of encrypting and decrypting is pretty much dependent on the speed of the <span class="caps">PRNG</span>.</p>
<p>the advantages are that if you have a <span class="caps">PRNG</span> which you know to be efficient and secure, you can do encryption that is just about as efficient and just as secure.</p>
<p>from a theoretical point of view, the cipher may be interesting because it is provably as secure as the <span class="caps">PRNG</span>. eg, Rabin public key encryption, though not used very much, was considered a big theoretical advancement because it was provably as secure as factoring large numbers. ie, you could crack Rabin encryption if and only if you could factor large numbers. <span class="caps">RSA</span> on the other hand, <em>may</em> someday be shown to have other weaknesses.</p>
ok, so i’ve finally made the newest version of the thraxil source code available for inspection.
<p>as i try to make clear in the <a href="code/README"><span class="caps">README</span></a>, it’s not really in a condition that one could take it and just install it on another machine and expect it to work. this release is more so people can take a look at the code, point out any problems they see, or just see how certain things work.</p>
<p>enjoy.</p>
after discovering that feb 22 != mar 22 and therefore prasanth wouldn’t be visiting this last weekend, i found myself with some unexpected free time. so i went down to DC to hang out with lani, cj, and my sister who was down visiting cj (after she’d spent a couple days hanging out in new york with me).
<p>corey (my sister) had to catch a train back up to maine on saturday afternoon so we pretty much only had friday night to all hang out together. so we got a bunch of beer, ordered some pizzas and stayed up all night watching movies. children of the corn 2 and 3 were cj’s picks (he’s a bit of a horror movie fan). then tank girl, one of my all-time favorites that neither lani nor my sister had seen.</p>
<p>we eventually passed out and slept a while. on saturday we brought corey to the train station then lani and i went back to hang out at her place. lani had a japanese study group meeting that she had to go to. they were meeting at a cafe in her neighborhood and i tagged along because i didn’t have anything better to do. it was really warm, i’d just filled my belly with food, i hadn’t slept much the night before and everyone around me was talking in a language i don’t know. so i fell asleep. i’ve slept in plenty of strange places before but i think this was the first time i’ve dozed in a restaurant/cafe type environment. </p>
<p>when they finally poked me awake and everyone left lani and i went to the Asylum for those wonderful 25 cent pints. after dinner we watched, with lani’s roomate kim, this japanese action movie called <a href="http://us.imdb.com/Title?0116015">non-stop</a>. it bills itself as “a cross between pulp fiction and run lola run”. i wouldn’t give it quite that much credit but it was pretty amusing and strange.</p>
<p>on sunday we walked down to a organic grocery store to procure fruit for breakfast. they had a vast selection of soy cheeses; i was most impressed. we pretty much lounged around for the rest of the day till right before i had to go when lani attacked me with scissors. well, she mostly attacked my hair. a very subtle trim designed to make it do less of a crack-addict-esque frizz thing.</p>
<p>on the bus back, i discovered that the batteries in my diskman had died so i was pretty much forced to watch some horrible movie about racecars with sylvester stallone. ugh.</p>
yesterday, jason and i were invited to give a talk to this year’s Microprocessor Systems Lab class about our experiences building XinT last year.
<p>it went pretty well. we talked a bit about XinT itself, how we designed it and how the development process went. mostly we were there to give the students a feel for what they’re in for and give them advice on how to deliver a good project. </p>
<p>i’m not much of a public speaker but i think it went pretty smoothly. especially considering that everything started late and i had to talk really fast if i had any hopes of making it to my crypto class on time which was scheduled for right after our talk.</p>
i was walking home from work last night and was appalled to see a truck coming up Broadway with giant screens on the side and blaring loudspeakers advertising some kind of health club membership. i guess advertisers have decided that the 70 foot tall calvin klein ads on the sides of buildings, ads on the tops of cabs and sides of buses, 20 minutes of ads before movies in the theatre, 15 minutes of ads at the beginning of DVDs that you can’t skip, product placements, super imposed animated ads in televised sports, banner and flash ads on the web, popups and popunders, ads in magazines and endless commercials on tv aren’t enough anymore. time to try something even more annoying.
<p>i remember hearing that after sept. 11th no one was buying ads anymore and all the advertisers were going out of business. i thought “wow, maybe some good will come out of all this after all.” apparently the ones that are still around have just gotten even more desperate to grab our eyeballs and control our minds. </p>
<p>there’s no escape anymore. i think we’re reaching the point where nothing is too sleazy for advertisers. i remember seeing King’s “I have a dream” speech turned into a commercial and getting mildly nauseous. how long before footage of sept. 11th makes it into an ad? maybe greyhound or amtrak advertising a “safer” way to travel? how much do you think McDonald’s would have paid to have their logo on the side of the <span class="caps">WTC</span>, clearly visible to every eyeball in the world as we sat, hypnotized, watching over and over again for months? the TV networks are already cashing in on it with endless exploitative “news” shows that they know are guaranteed to bring in the ratings and it’s been a wonderful propaganda vehicle for promoting “patriotism”, censorship, and racism. U2 incorporated the names of the victims in their superbowl half-time show.</p>
<p>i’m going to go throw up now. then i’m going to have a Pepsi Cola <small>TM</small>.</p>
alex and sarah came down from providence to visit julintip. last night we all went out for dinner and then to some bar on houston called “Puck Fair” and had drinks (they have hefeweize). over the course of the evening about 15 bates alumni showed up. many that i’ve never met before. nevertheless, i’m always amazed at how many batesies are around just waiting to climb out of the woodwork. kind of creepy actually.
lani hitched a ride up to new york this weekend with her roommate who was driving to new jersey.
<p>last night we went down to korea-town for korean food with julintip, adam, and sheela. huge place that appeared to be named ‘korean restaurant’. good food and they claim to be open 24 hours a day. i don’t remember exactly what i got; it was some kind of stew that came with a fire still going under it. so i was the coolest person at the table (being the only one with fire) for a little while till i realized that as neat as it was to have my dinner on fire, it’s rather difficult to actually <em>eat</em> food that is still literally boiling.</p>
<p>after we ate, lani suggested that we go to the bar down in soho i’d told her about that gerard turned me onto that had lychee martinis. this posed a bit of a problem since i have no sense of direction at all and could not for the life of me remember where it was. eventually i remembered that it was called ‘Clay’ and <a href="http://www.vindigo.com/">vindigo</a> tracked down the address for me. i love technology.</p>
<p>as we were walking up prince st towards Clay, lani spotted one of those japanese photo-sticker booths and we were drawn in. don’t worry, the results will be scanned in when i have time.</p>
<p>picked up a cheap 60GB hard-drive today to augment the nearly full 9GB i’ve had in my computer for the last few years. i figure that with 60GB i can keep about 1000 albums worth of mp3s archived. i love technology :)</p>
i love open-source software. have i mentioned that lately?
<p>i’ve been experimenting with different email clients lately and finally found one that does everything i need it to: <span class="caps">GPG</span> integration, decent <span class="caps">IMAP</span> support, no html support (i hate html email) and the ability to remap the keybindings so i can make it behave exactly like pine (i’ve been using pine from the shell on the mailserver for years but the connection between my cable-modem provider and columbia’s network is spotty enough that typing over that connection has gotten annoyingly slow) which my fingers know mechanically.</p>
<p>after trying and discarding for one reason or another kmail, evolution, balsa, and schemes involving fetchmail with pine or mutt on a local machine, i tried <a href="http://www.tkrat.org/">TkRat</a>. it handles everything i need it too and is extremely lightweight to boot. it’s written in <span class="caps">TCL</span> using the Tk widget library so it doesn’t <em>look</em> very pretty but it’s quite functional. </p>
<p>after using it for a couple days, the only problem i had with it was that it has these huge tooltips for pretty much every part and no option to turn them off. the tooltips are nice for about the first hour you’re using it and figuring out where all the features live but gets annoying after that. it gets to the point where you have to make sure to move the mouse out of the window all the time to keep what you’re reading or typing from being obscured by some huge tooltip explaining in depth that the “send” button is used to “send” the email or something retarded like that.</p>
<p>luckily, because TkRat is open-source, i was able to do a quick grep through its source code, find the function that shows tooltips, or “balloon help” as they refer to it (called ‘rat_balloon::Show’) and add a ‘return’ to the function before it actually shows anything on the screen, essentially nullifying the tooltip functionality. i don’t even know <span class="caps">TCL</span> but i was able to do this entire operation in about a minute, making the program immensely more usable to me. </p>
<p>with closed-source software, you’re stuck with whatever microsoft or adobe or whoever decides to give you.</p>
<p>if i get ambitious enough to learn some <span class="caps">TCL</span> basics i’ll add a preferences option for tooltips and contribute the patch back to the project so other people can benefit from it.</p>