Wednesday, October 1, 2008

Gentoo libselinux coreutils silliness

This blog entry probably isn't interesting to anyone. I'm writing it because Blogger blogs often turn up in Google results and it might be useful to a random searcher. Point: if you have libselinux on your system and want to get rid of it because it doesn't belong in your profile and is masked and frequently causes lots of obnoxious warnings, you probably shouldn't just emerge -C libselinux. You also probably shouldn't just do a emerge --depclean libselinux or even emerge -C libselinux && revdep-rebuild --library=libselinux.so.1. They might not work.

Not only will they not work, the emerge -C libselinux might not even finish correctly. The problem is that coreutils will build against libselinux even if you USE=-selinux. One of the autoconfiggey scripts does it. There's a bug in Gentoo bugzilla but no official action has been taken yet. If you happen to have updated coreutils since libselinux turned up, after you delete /lib/libselinux.so.1, lots of stuff doesn't work. /bin/ls, for example. And plenty of other programs you take for granted, and that emerge needs to finish unmerging libselinux. This was my experience and that of others. Learn from it.

The first thing you need to do is get a coreutils that doesn't need libselinux. First just make sure you need to do this at all: ldd /bin/mv | grep selinux. If no results you're OK. emerge -C libselinux && revdep-rebuild --library=libselinux.so.1 is all you need. Otherwise a new build of coreutils is in order. The person that filed the Gentoo bug kindly provided a couple patches that do the trick perfectly. It took a bit of messing around to figure out exactly where to put 'em, though.

The way I did it was to create a partial portage overlay. It has just one package in it. Hey, might as well learn this stuff. Create the directory /usr/local/portage/sys-apps/coreutils and copy the ebuild from the main portage tree into it. Also copy over the files directory and its contents from the the main portage tree. Apply the ebuild patch to the ebuild, and download the other patch into the files directory. Then run ebuild $fn manifest, where $fn is the name of the ebuild. This builds the manifest file so portage doesn't suspect your ebuilds of mischief. Now set up PORTDIR_OVERLAY in your /etc/make.conf to include your overlay directory (/usr/local/portage). At this point you should just be able to emerge coreutils and you'll get a version with no libselinux dependency. Now you can safely unmerge libselinux, run revdep-rebuild, and drink some delicous beer. I recommend a porter for this occasion, for obvious reasons. Then you can get rid of the overlay, because you shouldn't need it anymore.

If you don't want to mess with overlays you can always just download the straight source of coreutils, patch it up similarly to how Andreas did, and install that; you can just overwrite it with officially sanctioned coreutils whenever you get around to it, or not. However you do it, check your resulting binaries to be sure they don't need libselinux.so.1 before unmerging it. Also make sure the binaries get installed to /bin and not /usr/local/bin so portage, etc. will find them. You knew that.

Wednesday, January 16, 2008

Enoch Root and Edward Abbey on the El

In Cryptonomicon Enoch Root devises an encryption scheme that he initially calls "Pontifex" and describes with the following perl script:

#!/usr/bin/perl -s
$f=$d?-1:1;$D=pack('C*',33..86);$p=shift;
$p=~y/a-z/A-Z/;$U='$D=~s/(.*)U$/U$1/;
$D=~s/[A-Z]/$k=ord($&)-64,&e/eg;$k=0;
while(<>){y/a-z/A-Z/;y/A-Z//dc;$o.=$_}$o.='X'
while length ($o)%5&&!$d;
$o=~s/X*$// if $d;$o=~s/.{5}/$& /g;
print"$o/n";sub v{$v=ord(substr($D,$_[0]))-32;
$v>53?53:$v}
sub w{$D=~s/(.{$_[0]})(.*)(.)/$2$1$3/}
sub e{eval"$U$V$V";$D=~s/(.*)([UV].*[UV])(.*)/$3$2$1/;
&w(&v(53));$k?(&w($k)):($c=&v(&v(0)),$c>53?&e:$c)}


(The program is somewhat obfuscated; to really understand it I had to type it out in a more readable form. Also, in reality the algorithm was designed by Bruce Schneier and the Perl script written by Ian Goldberg. Here is Bruce's description of the system)

It's later revealed that the same instructions, written in natural language instead of Perl, can be followed by a person with a deck of cards to generate a "keystream" of random-looking numbers. Two people that start with their decks in the same order can generate this same random sequence. The sender writes out his message, writes a number from the keystream under each letter, then circularly-shifts each letter forward in the alphabet by that number. The receiver receives a message that looks random to anyone else, circularly-shifts each letter backward by the same number the first person used, and the result is the original message. The whole system relies on a shared secret: the two people communicating know how to arrange the deck into its initial position, but nobody else does. In this sense it's similar to a one-time pad, where the communicators generate long sequences of random numbers while physically in contact and agree on which to use for which messages before they start communicating this way. The advantage is that in this case the shared secret, instead of pages full of numbers that can be physically confiscated by eavesdroppers, could be something memorizable, like (as Bruce Schneier suggests in an appendix to the novel) a simple system for generating a deck ordering based on Bridge scenarios published in some newspaper on the day the message was written. As with a one-time pad, there are two major ways that an eavesdropper could break it. First, by discovering the shared secret. Second, by discovering a bias, that is, by mathematically analyzing the keystream-generating algorithm and finding patterns in it. Finding a bias would cut down the number of likely keystreams, perhaps enough that they can all be checked by brute force. Such a bias has been found in Solitaire, as mentioned in Bruce Schneier's page, linked above.

So.

Today after work I got on a Brown-Line train at the Merchandise Mart stop to ride all the way out to Francisco to go to my gym. Doors open on the right at Merchandise Mart, so I entered the crowded train from the right and had to stop and stand in the doorway, looking towards the left of the train. Seated to the right of the doors on the opposite side were a woman reading a book (not very interesting to watch) and a man repeatedly shuffling and fanning a deck of cards (somewhat more interesting). This guy must not have had much to do, or was practicing to escape the Chicago winters to become a card dealer in Vegas. Or maybe he was an Enoch Root, well-practiced at his card transformations, memorizing or analyzing the keystream generated from his deck transformations. It wasn't all that interesting, though, so I started reading.

Maybe at the Sedgwick stop the woman next to him got up, and I was the closest person to the seat she left, so I sat down. The man continued to shuffle his cards, sometimes accidentally jabbing me with an elbow, occasionally sneaking a glance at my book. I don't read secretly, so he may have caught a bit of Edward Abbey's description of his lazy trip down the Colorado River just before the building of the dam to form Lake Powell. At Belmont he stood up and flicked a card from his deck perfectly into the middle of the seat. The two of hearts. He walked out of the train. Transfer to Red- and Purple-Line trains at Belmont? Unlikely. Transferring at Belmont is for fools and amateurs. A man of his caliber would have obviously known to transfer at Fullerton.

So anyway a woman walked on the train, looked at the card on the seat. She recognized immediately that the first number of the keystream was 28! She probably looked at me funny, like I'd put the card there for some reason, but I don't really know because I had my face buried in Desert Solitaire trying to contain my laughter. Joy, mirth and laughter are not allowed on CTA vehicles. Do not make eye contact with other customers. If you see something, say something! Play safe; ski only in clockwise direction. Let's all have fun together. Especially with doomsday looming. She pocketed the card, sat down and started reading.