Thoughts on AES

I posted here in early June with some general-purpose cryptographic recommendations; one of my suggestions was to use 256-bit AES rather than 128-bit or 192-bit AES. Since then, a couple of new attacks which specifically target AES-256 have been announced; and Bruce Schneier has commented that "[T]he key schedule for AES-256 is very poor. I would recommend that people use AES-128 and not AES-256.". Despite this, I still recommend the use of AES-256 for encryption in software implementations where cryptographic keys are generated randomly.

My reasoning for this is based on the nature of these attacks: They're both related-key attacks which exploit AES-256's key schedule. These break the notion of the "ideal block cipher" -- i.e., the notion that AES acts as an oracle mapping keys to random permutations -- and can be very bad if you allow an attacker to select a cryptographic key -- which is effectively how block ciphers get used to construct hash functions. I don't think it's a coincidence that related-key attacks are suddenly being found while NIST's SHA3 hash competition is running.

There are other situations where related-key attacks can be used. Some poorly designed protocols allow keys to be constructed in malleable ways (i.e., such that by fiddling with part of the protocol, a negotiated key can be modified in a predictable manner); and in smart cards and other hostile environments, it is possible for related-key attacks to be applied via the induction of faults.

However, for encrypting data in software on general-purpose systems using randomly-generated cryptographic keys -- which constitutes the vast majority of the situations where anyone reading this is ever likely to want to use AES -- none of these are relevant, and thus related-key attacks are not something which should be a major consideration. In contrast, side channel attacks are very real; and thus I believe that it is more important to provide a margin of safety in case some key bits are leaked via a side channel than it is to use a stronger key expansion function (such as AES-128 has and AES-256 lacks) which provides greater safety against related-key attacks.

Normally I would conclude by pointing out that attacks always get stronger and a small crack now can grow into a major break later -- but in this case I don't think such warnings are warranted. The AES key schedule -- especially the AES-256 key schedule -- have been known to be rather weak for many years, and the "natural" way that key schedules break is by inducing related-key attacks. If someone had found a way to translate a weakness in AES's key schedule into an attack other than a related-key attack, I'd be far more concerned; but as it is, there really isn't anything very surprising here.

Instead I'll end with a cautionary note: I haven't yet read the latest (Biryukov-Dunkelman-Keller-Khovratovich-Shamir) attack paper -- I'm just writing based on the abstract and Schneier's commentary. It is possible that they present a startling new attack method which can be leveraged to attack AES in other (more practical) ways. But I doubt it; after all, if you discovered a powerful new attack method, why would you demonstrate it by constructing a related-key attack on a cipher with a relatively puny key expansion function?

Posted at 2009-07-31 08:45 | Permanent link | Comments

Tarsnap mailing lists

If you Google for tarsnap, you can find a lot of tarsnap users doing interesting things. For example, Tim Bishop wrote a shell script for automating tarsnap backups; Mads Jorgensen wrote a similar shell script for organizing his backups; Justin Haynes created a SlackBuild for tarsnap; Aaron Schaefer create an Arch Linux PKGBUILD for tarsnap; any many tarsnap users have blogged about their experiences. Until now, however, there hasn't been any good way for tarsnap users to connect with each other.

After a couple of months of saying "soon", I've finally found time to create some tarsnap mailing lists. At the moment there are four lists:

I've also created a #tarsnap channel on EFnet for general tarsnap-related discussion.

Obviously, I'm subscribed to all of these lists and am usually on the IRC channel; but the main purpose of these (the -announce list excepted) is to allow for communication between tarsnap users. You can always email me directly about any tarsnap-related questions or problems, but in most cases the collective wisdom of tarsnap users is likely to be able to help more than just my own attempts.

Next up on the "improving communication with tarsnap users" to-do list: Creating web-accessible archives for the mailing lists; and creating a slightly less minimalist tarsnap website. Watch this space!

Posted at 2009-07-18 05:05 | Permanent link | Comments

A call for schwag

Two things happened this morning which started me thinking. First, I read Zed Shaw's rant about how he thinks he deserves more recognition and money from his Open Source work; and second, I looked at my pile of t-shirts, and realized that while I have 4 Google t-shirts (one from August 2006, when I interviewed there; and three from Google Summer of Code), I don't have a single t-shirt from any company which is using code I've written.

Now, this is not to say that I haven't received any rewards for my work on FreeBSD. In the summer of 2006 I spent four months working full-time on FreeBSD in exchange for almost $15k in donations; I've received a USB-attached hard drive; the FreeBSD Foundation paid for my flight to BSDCan'06; and last summer a FreeBSD user sent me a book off my Amazon wishlist. But aside from the book, those were all about enabling me to continue working on FreeBSD, not about acknowledging work I had already done. Perhaps the most significant benefit I've received from people recognizing my work on FreeBSD is the indirect benefit via my tarsnap online backup service: I've seen lots of people saying "I love Portsnap / FreeBSD Update / your work as FreeBSD Security Officer / etc, and based on that I'm sure your backup service is worth trying out".

Maybe it's unreasonable to expect any more recognition than this. After all, the FreeBSD project is big -- a few hundred committers, not to mention the thousands of people who contribute patches which other people end up committing -- and most companies won't have the budget to send t-shirts to hundreds of people just to say "thank you". On the other hand, my bsdiff binary patch tool has been used by Apple's Software Update tool, Firefox's software updates, and the Amazon Kindle; I'm sure they all have promotional schwag available, but in two of the three cases (I'm not going to say which) I didn't even get so much as an email to tell me that they were going to be using my work.

One of the strongest motivations for people to get involved in Open Source software is the allure of being recognized for their work. It's nice to be recognized by other developers, and this happens quite often; it's also nice to be recognized by people using one's work, and this also happens fairly regularly. But being recognized by companies? Aside from Poul-Henning Kamp, whose "beerware" license has resulted in companies sending him beer, I'm not aware of FreeBSD developers receiving any form of recognition from FreeBSD-using companies. (Again, I'm distinguishing between sending someone a gift to thank them for their work and making a contribution towards keeping the project running -- many companies have donated hardware and bandwidth to the FreeBSD project.)

So I am hereby issuing a call for schwag: If your company uses Open Source software, and your company has promotional t-shirts, bags, hats, USB disks, et cetera, please pick one of the developers who worked on the code you're using and send him/her an email:

To: Open Source Developer
From: Big company
Subject: Thanks for your work on XYZ

Dear Mr. Developer,

Thank you very much for your work on XYZ -- it's [insert comment here about why you like and are using XYZ]. Would you like a BigCo t-shirt? Let me know your address and what size you'd like and we'll send you one.

Guy who works at BigCo

Obviously, money is even better than schwag, and many developers (myself included) are available for consulting work; most companies, however, can't afford to throw money around. But a t-shirt is a much easier thing to give someone than a consulting contract; and when it comes to telling someone that you recognize and appreciate the work that they've done -- well, as they say, it's really the thought that counts.

Posted at 2009-07-14 14:15 | Permanent link | Comments

FreeBSD Update to 8.0-BETA1

In the early days of the FreeBSD 7.0 release cycle I posted here with some instructions on performing a major version upgrade of FreeBSD using FreeBSD Update; now that we're in to the 8.0 release cycle, I think it's time to post some updated instructions. For a number of reasons this post is coming almost a week late -- Ken Smith announced 8.0-BETA1 on Monday -- but I expect that I'll have FreeBSD Update bits in place when future BETAs and RCs are announced.

Please note that I am the FreeBSD security officer and the FreeBSD Update bit wrangler, but that I am not on the release engineering team -- so I'm coming to this BETA without much more knowledge than any other tester. If you have problems specifically related to FreeBSD Update, please post a comment below (if it's a problem which you think other people should be aware of) or email me directly at; but any other problems with the BETA should be directed to the FreeBSD mailing lists.

Finally, please read over all of these instructions before you start. You don't want to have a half-updated system and be scratching your head trying to figure out what the next step means. Without further ado:

Step 1 (optional): Make sure that all of your installed ports build (UPDATE 2009-09-08: this is not required when updating from 8.0-BETA3 or later to newer betas, release candidates, or 8.0-RELEASE):
# portsnap fetch update
# portupgrade -a
Some shared libraries have had their version numbers increased during the lifetime of 8-CURRENT; as a result, software installed from the FreeBSD ports tree which uses those libraries will have to be rebuilt during the upgrade process. Sometimes people make mistakes and ports end up being broken for a few days; if you make sure that the newest versions of all the ports you're using are installed before starting, it's less likely that you'll run into problems when you rebuild everything later.
Note that the 8-STABLE ABI has not been fixed yet, and library versions have not yet been bumped; so at some point later in the release cycle it will be necessary to rebuild all your ports again.

Step 2: Make sure that you have good backups.
Yeah, we always tell people to make sure they have good backups before doing anything. But I'm serious this time. I'm aware of two systems which failed to reboot after installing 8.0-BETA1 kernels. This might happen to you -- so make sure that your data is safe in case datacenter staff says "gee, we can't do anything to make your system boot... how about we just wipe everything and reinstall?"
<plug>Don't have a good way to do backups? Try using my Tarsnap online backup service (client code is in the ports tree as sysutils/tarsnap). It is efficient, easy to use, and (as you might expect from something written by the FreeBSD security officer) very secure. While I say that Tarsnap is still in beta, this is the "gmail" sort of beta, not the "first testing release of a .0 version of an operating system" sort of beta -- it's safe to trust Tarsnap on production systems. </plug>

Step 3: Disable any FreeBSD Update cron jobs.
If you have FreeBSD Update running from a cron job (e.g., in /etc/crontab) then you should disable the cron job now. When FreeBSD Update downloads updates, it starts by deleting any not-yet-installed updates; if this happens in the middle of upgrading to a new release, problems will happen.

Step 4: Download 8.0-BETA1 bits:

# freebsd-update -r 8.0-BETA1 upgrade
Looking up mirrors... 3 mirrors found.
The following components of FreeBSD seem to be installed:
The following components of FreeBSD do not seem to be installed:
Does this look reasonable (y/n)? y
FreeBSD Update will start by looking at your system and trying to figure out which parts of the FreeBSD base system you have installed (e.g., source code, documentation, profiled libraries, et cetera). FreeBSD Update will almost certainly get this right, but you should glance over the lists to check that it hasn't gotten confused.
Fetching metadata signature for 8.0-BETA1 from done.
Inspecting system... done.
Preparing to download files... done.
Attempting to automatically merge changes in files... done.
Depending on how extensively you have modified the default configuration files in /etc FreeBSD Update might be unable to automatically merge changes from the FreeBSD tree into your configuration files. If this is the case, it will open up a semi-merged file in your editor and ask you to resolve the conflicts for it.
The following changes, which occurred between FreeBSD 7.2-RELEASE and
FreeBSD 8.0-BETA1 have been merged into /etc/newsyslog.conf:
After merging updates to configuration files (with or without your help), FreeBSD Update will show you the changes it intends to make. Please look at these and make sure that everything looks reasonable.
The following files will be removed as part of updating to 8.0-BETA1-p0:
The following files will be added as part of updating to 8.0-BETA1-p0:
The following files will be updated as part of updating to 8.0-BETA1-p0:
Finally, FreeBSD Update will print three long lists of files which it wants to remove, add, and modify as part of upgrading to 8.0-BETA1. You can probably just ignore these lists: They get printed mostly just because I originally wrote FreeBSD Update as a tool for downloading security updates, and seeing such lists is useful for security updates which only modify a few files.

Step 5: Install the 8.0-BETA1 kernel and reboot:

# freebsd-update install
Installing updates...
Kernel updates have been installed. Please reboot and run
"freebsd-update install" again to finish installing updates.
# shutdown -r now
The first time you run freebsd-update install after downloading the 8.0-BETA1 upgrade bits, it will only install the new kernel. Until we reboot, we're still running the old kernel, and we never want to run a new userland on an old kernel -- so we need to reboot before installing the new userland.
If anything goes wrong, it will probably go wrong here. On both of the systems where I've seen upgrading to 8.0-BETA1 fail, it was at the point of rebooting into the new kernel.

Step 6: Install the rest of the 8.0-BETA1 bits:

# freebsd-update install
Installing updates... done.
Completing this upgrade requires removing old shared object files.
Please rebuild all installed 3rd party software (e.g., programs
installed from the ports tree) and then run "freebsd-update install"
again to finish installing updates.
At this point you have 8.0-BETA1 installed; but you also have old shared libraries lying around and you might have ports linked to those old libraries.

Step 7: Update ruby and delete portupgrade's package database (UPDATE 2009-09-08: this is not required when updating from 8.0-BETA3 or later to newer betas, release candidates, or 8.0-RELEASE):

# portupgrade -f ruby\*
# rm /var/db/pkg/pkgdb.db
I'm not entirely certain why this is necessary; but when performing major base system upgrades, portupgrade tends to get confused and think that its package database is corrupt. Rebuilding the ruby and ruby-bdb ports and then deleting the package database (which forces portupgrade to rebuild it) seems to make the problem go away.

Step 8: Rebuild all other installed ports (UPDATE 2009-09-08: this is not required when updating from 8.0-BETA3 or later to newer betas, release candidates, or 8.0-RELEASE):

# portupgrade -af
Now we'll rebuild all installed ports, in order to make sure that none of them are linked to old shared libraries which are about to go away.

Step 9: Remove old shared libraries and reboot (UPDATE 2009-09-08: when updating from 8.0-BETA3 or later to newer betas, release candidates, or 8.0-RELEASE, you don't need to re-run freebsd-update; just reboot):

# freebsd-update install
Installing updates... done.
# shutdown -r now
When we run freebsd-update install this time, it finishes the upgrade process, by getting rid of old libraries (which it couldn't do earlier because there might have still been ports using them). Finally, once the system is completely upgraded, we need to reboot a second time, so that the new (8.0-BETA1) versions of daemons get started.

Step 10: Re-enable your FreeBSD Update cron job.
If you normally run FreeBSD Update from a cron job, you should have disabled the cron job in step 3; if so, remember to re-enable it now. I hope there won't be any security issues in the next few weeks; but if there are, updates will be available via FreeBSD Update. I normally give BETAs and RCs a lifetime of 4 weeks where FreeBSD Update is concerned: If there's a security issue, I don't want to delay sending out an advisory because I'm building updates for lots and lots of different BETAs, but at the same time I want people to be able to test the BETAs without worrying about being stuck without easy security updates.

If all goes well, you should now be running FreeBSD 8.0-BETA1. Congratulations! Keep your eyes open for any problems and report them via send-pr or via the FreeBSD mailing lists -- this is the first beta of a .0 release, so I'm sure there will be bugs to fix.

If all didn't go well, and you now have a broken system: Please leave a comment below. Odds are that I can't help you fix your system (you DID make backups, right?) but if nothing else you might be able to point out a problem and help make sure that nobody else runs into the same difficulties.

Posted at 2009-07-11 16:00 | Permanent link | Comments

Recent posts

Monthly Archives

Yearly Archives