Fork me on GitHub

Caffeinated Bitstream

Bits, bytes, and words.

Implementing DES

DES, the Data Encryption Standard, was developed by IBM and the US government in the 1970's. Today, DES is considered to be weak and crackable, and a poor choice for anyone in the market for an encryption algorithm. However, many legacy protocols still use DES, so it's important to have implementations handy.

I recently found myself looking for a simple standalone DES implementation to study. Most of the open-source DES implementations are either highly optimized into obfuscation, or sloppily written. Either way, it's hard to find a clearly written and well-commented implementation suitable for educational purposes. I decided it would be a good exercise to write one myself. I wrote the implementation in Java, for the extra challenge of performing bit manipulations on signed primitive types. This implementation is undoubtedly very inefficient, but is well-commented and should be easy to understand for anyone who wants to dive into a sea of Feistel functions, S-boxes, variable rotations, and permutations.

References

I found the following resources useful in my study of DES:

Downloads

  • DES.java - My DES implementation in Java
Testing multicast support on Android devices

In my previous post, I mentioned my frustration that certain Android phones (including my HTC EVO) cannot receive multicast datagrams. I'd like to get feedback from my friends and colleagues about multicast support on their phones, so I wrote a simple app for testing multicast.

The Multicast Test Tool continually monitors the network for Multicast DNS (mDNS) packets while the app is running in the foreground, and presents the contents of these packets to the user. The app also allows the user to perform simple mDNS queries on the local network. If you run the app and touch the "Query" button, it will query for the default _services._dns-sd._udp.local name, which will solicit mDNS responses from devices on your network that advertise services via mDNS.

Mac and Linux machines will respond to this discovery query. Windows machines will also respond if you are running iTunes and have checked "Share my library on my local network" in the preferences. If you think your network may not have any of these devices which support mDNS service discovery, you can run the attached perl script to transmit a gratuitous mDNS packet.

You can also query specific hosts using the format <hostname>.local. My home network is always buzzing with mDNS traffic, so on my multicast-capable virtual machine I see lots of activity without performing any queries.

If you see any activity at all, it means that your phone supports multicast. If you see no activity, then your phone likely does not support multicast.

Downloads

  • multicast_test.apk - This is the Multicast Test Tool app, which you can download and install on your Android phone.
  • send_mdns.pl - This perl script transmits a single mDNS packet, which should be detected by the Multicast Test Tool. This is only needed if you don't already have devices on your network (Macs, Linux boxes, etc.) which implement the mDNS service discovery protocol.
  • multicast_test_tool.tar.gz - The source code for the Multicast Test Tool. This is only needed if you are curious about the inner workings. (Added 2011-02-02.)
Broken multicast networking on HTC smartphones

It looks like some (most?) HTC phones running Android, such as my HTC EVO, are not capable of receiving multicast or broadcast datagram packets over the Wi-Fi network. This means that apps which rely on such communication will fail, often with no indication of the problem. From the app's perspective, no obvious error is happening — it can only assume that no other devices on the network are transmitting such datagrams. Multicast communication is becoming increasingly common as a technique for devices to discover each other on a network, and the absence of this capability represents serious breakage that leaves apps crippled. Examples of resources an app might use multicast to discover are:

  • iTunes music libraries
  • entertainment center components such as Roku and AppleTV
  • network shares
  • other devices running the same app, to set up multiplayer games

Without a functioning multicast capability, these apps either don't work, or require the user to manually configure the IP addresses of the other devices.

There is speculation that HTC's restriction is an attempt to save power and prolong battery life — it takes energy to process a network's many multicast and broadcast packets, many of which are useless to the device and its applications. However, Android already has a facility for allowing prudent use of multicast when needed. Applications acquire a WifiManager.MulticastLock for the duration of their multicast needs, which causes the Wi-Fi chip to stop filtering multicast packets until the app releases the lock. Thus, multicast processing in the software TCP/IP stack only happens when it's really needed.

This is a bit frustrating, as I'm currently tinkering with some multicast code. Some people have been able to fix the problem by rooting their phones and replacing the /system/bin/wpa_supplicant binary with a stock version. This doesn't seem to help on my EVO. To add to the frustration, it can be difficult to test multicast in the Android emulator. I finally had some success in testing multicast code by running android-x86 in a VirtualBox virtual machine, with the network configured for bridging.

References:

The year in bandwidth

I collect data usage statistics on my home broadband connection using a script that polls my router's WAN interface counters via SNMP once a minute. Since I have all this data lying around, I thought it might be neat to chart my broadband usage for 2010 and get an idea of how much of a bandwidth hog I am. My usage includes lots of movie streaming, VoIP phone calls, and work-related applications (since I work from home).

My total usage in 2010 was about 209 GB of download and 24 GB of upload, for a monthly average of about 17 GB and 2 GB, respectively.

IPv6 protocol overhead

The IPv4 address space is nearing exhaustion. The unallocated address pool is currently expected to be depleted at the IANA level in June 2011, and at the Regional Internet Registry (RIR) level in January 2012. Networks will need to transition to IPv6, which allows for an astronomically larger address space (among other nice features). IPv6 has been around in some form since 1995. However, since network operators are human beings, the consensus has not been to methodically migrate to IPv6 over the last 15 years, but rather to procrastinate 15 years and then pull an all-nighter on the eve of exhaustion.

IPv6 is likely to become an important topic in the next few years, and I've become interested in brushing up on the protocol. (I first studied IPv6 in 1996, back when everyone figured adoption would be imminent.) IPv6 is likely to be deployed on a much larger scale in the coming years than in years past, exposing many practical network engineering challenges, and perhaps creating opportunities for a low-level software engineer such as myself to provide value in easing migration and filling in the coverage gaps.

My first experiment was to measure the extra protocol overhead of IPv6 in common network scenarios. An IPv4 header occupies 20 bytes in the common case, and an IPv6 header occupies 40 bytes in the common case. The practical difference in overhead depends on the size of the packets—with large packets, the extra 20 bytes of header doesn't matter too much when measuring the overhead with respect to the total payload being transmitted. IPv6 evangelists occasionally tout the protocols's minimum MTU (1280 bytes) which is larger than in IPv4 (68 bytes, or 576 bytes to avoid fragmentation) when calculating efficiency, and come to the conclusion that IPv6 is even more efficient than IPv4. This doesn't reflect the practical reality of the modern Internet where most routes support a path MTU of 1500 without a problem. IPv6 is a necessary and worthwhile protocol, but we shouldn't be afraid to study the actual, real-world overhead.

To measure IPv6 overhead in a real-world test, I configured two User-Mode Linux instances (similar to virtual machines) with a virtual serial connection between them which can support PPP. I used the nc program to transfer data streams of various sizes over TCP in both IPv4 and IPv6, and recorded the total number of transferred bytes as measured by pppd. Performing real-world measurements was somewhat redundant, since the theoretical overhead can be easily calculated using the size of the packet headers and payload lengths. However, it was interesting to see the protocol in action.

MTU 1500 tests, with respect to sender
512 KiB 4 MiB 16 MiB 64 MiB
IPv4 out54369243476601738983669558696
IPv4 in28681451654452214612
IPv6 out551468
(+1.4%)
4409028
(+1.4%)
17626852
(+1.4%)
70505788
(+1.4%)
IPv6 in4140
(+44.4%)
22584
(+55.6%)
75564
(+38.8%)
297396
(+38.6%)

As expected, the additional outbound overhead from our TCP sending node is quite negligible. However, the return traffic—mostly small packets of TCP ACKs with empty payloads—contains a significant amount of additional overhead. I wonder how this will affect users with asymmetric connections with a limited upload capacity. At some point, upload limitations can start bottlenecking the download. (It might be an interesting experiment to see how effective TCP sliding window sizes are at mitigating this effect.)

I performed this experiment again, limiting the outbound TCP segment payloads to 128 bytes, to get an idea of how applications with smaller packet sizes might impact an IPv6 network.

SO_SNDBUF=128 tests, with respect to sender
512 KiB 4 MiB 16 MiB
IPv4 out665856589917623596416
IPv4 in19240817042526816956
IPv6 out789868
(+18.6%)
6555668
(+11.1%)
26219068
(+11.1%)
IPv6 in284508
(+47.9%)
2360292
(+38.5%)
9438552
(+38.5%)

The IPv6 header overhead begins to really add up when using smaller packet sizes. The total bandwidth consumed by applications with small bits of sporadic data or low-latency requirements (i.e. VoIP) might be significantly higher on an IPv6 network.

All in all, I think the additional protocol overhead of IPv6 is quite manageable in most cases, and I hope network operators begin upgrading their IP networks soon.

Customizing the Mac Dashboard calendar widget

It turns out that it's not too hard to customize the dashboard widgets that come with Mac OS X, since they're implemented in HTML and Javascript. You can just copy the stock widget from /Library/Widgets to ~/Library/Widgets and go to town. In the above picture, you can see how I've hacked the calendar widget to show week numbers.

Update, April 7, 2011: Due to popular demand, I've posted a diff of my changes here, based on the Snow Leopard calendar. Copy the calendar widget into your home directory (~/Library/Widgets) and rename it to wwCal.wdgt.

HTC EVO and background network activity

HTC EVO, shown with the optional extended-life battery.

Earlier this year, I ditched my antiquated Treo 755p for the new hotness in mobile phones—the HTC EVO, an Android phone available from Sprint. Unlike my previous phone, which would last a full week in standby without recharging, the EVO gulps battery like there's no tomorrow. In fact, the limited battery life has been the primary complaint about the phone. Nobody seems to know for certain why the battery life is so poor. Maybe it's the beefy 1Ghz Snapdragon processor, the large LCD screen, or something else entirely.

I was recently traveling in a rural area, and noticed that my EVO's battery would only last halfway through the day. All mobile phones consume more battery in rural areas where they must transmit with greater power to stay in contact with faraway towers. However, the extent to which the EVO's battery life problems were exacerbated by the higher transmitting power got me thinking that perhaps at least some of the battery drain may be due to software which occasionally causes the radio to transmit.

All modern smartphones have various software components which periodically execute in the background, unbeknownst to the user, and sometimes activate the radio to chat with their buddies in the cloud. Some of this chatter may be useful for the user, such as having fresh mail delivered immediately, while other chatter may provide little or no value.

I got curious about what the phone's software was actually doing while I wasn't around, so I captured and analyzed all the network traffic from my phone over a period of four hours. I accomplished this by turning off the 3G radio and packet sniffing the Wi-Fi network. (I didn't have an easy means of sniffing the 3G traffic directly.) I have my phone syncing with my Google account, Google Latitude, a couple of mail servers, and Facebook, and this is reflected in the captured data. I did not touch the phone at all for the duration of the test, so this traffic represents only non-interactive use. Here are the main traffic categories, sorted by decreasing packet count, with local network maintenance traffic (ARP, DHCP, etc.) removed:

ip address host events packets bytes notes
209.8.115.0/24
66.220.0.0/16
profile.ak.fbcdn.net
api.facebook.com
21353921050 Facebook sync, including downloading profile photos of friends.
74.125.227.0/24mobilemaps.clients.google.com1127889604 Google Latitude updates
-mail_server_1723738572 IMAP/SSL mail traffic
-mail_server_2116787852 IMAP/SSL mail traffic
74.125.47.188yw-in-f188.1e100.netmany747298 Encrypted packets exchanged with Google throughout the period. This is probably the C2DM system which Google uses for push notifications.
-dns_server32649811 Various DNS names are queried throughout the period to support connections to the other services listed here.
184.73.171.111prod.sprintzone.org1326628 The Sprint Zone app periodically communicates with a Sprint server hosted on Amazon EC2 to receive information about promotions and announcements.
216.241.36.232static.ak.fbcdn.net
(via the local Akamai server)
2274728 Fetching the Facebook "no profile" image. (As part of the sync?)
208.17.80.85resources.static.mobitv.com1202296 Sprint TV service. This code seems to be sloppy—two identical HTTP transactions are launched at the same time.
98.137.133.176proxy101.mobile.vip.sp2.yahoo.com1153163 Yahoo Finance Widget: fetch latest stock prices
131.107.13.100time-nw.nist.gov18599 Query the date and time via the Daytime protocol. This server is located at Microsoft.
208.77.19.5us.pool.ntp.org12180 Query the date and time via NTP.

Lots of background network activity can be minimized by tweaking the sync settings.

In total, about 1.2 MB of data was exchanged in 2277 packets: 186 KB (1270 packets) were transmitted, and 1002 KB (1007 packets) were received.

The Facebook sync seems to be the biggest data hog of these background services. Every two hours, it is downloading information about all my Facebook contacts, as well as fetching profile pictures of most of them (whether or not the profile pictures have changed recently). The sync frequency for my "Facebook for HTC Sense" program can be changed in the settings, so I changed it from every two hours to once a day. After Facebook, the biggest consumers seem to be Latitude and my mail servers. I knew what I was getting into when I configured those, so I can't complain. I didn't even realize that I had Yahoo's "Stocks" program set to sync, so I turned that off altogether. The Sprint Zone sync frequency can be changed in the Sprint Zone application itself, although I haven't found a way to limit the Sprint TV syncing. The next time I'm traveling in a rural area, I should remember to turn off the "background data" and "auto-sync" items in the sync settings.

There are a few possible flaws in using this method to predict battery consumption. The exact relationship between network activity and energy usage is not clear to me. For example, is the transmitter only active for just long enough to send a packet, or does it remain on for a bit longer in the hopes of another packet becoming available in the send queue? What would consume more energy—a burst of 100 kilobytes, or 100 short transmissions of 1 kilobyte each, spread throughout a period of time? Is it more meaningful to consider packet counts, or the total byte count? Are some of these services only transmitting because they know the network connection is Wi-Fi and not 3G?


VFD Clock

I decided I needed a clock in my living room, and remembered I had this Matrix Orbital VFD2041 vacuum fluorescent display in my junk box, so I whipped up a few lines of C code to make it show the current time. The VFD connects to my home theater PC via its RS-232 interface and a USB RS-232 dongle.

Here's the source:

Multimedia and bandwidth

Back in the 1990's, I predicted that all data-oriented utilities — telephone, television, radio, etc. — would eventually become Internet services. Today, the world is rapidly approaching this ideal as people ditch their POTS telephone lines for VoIP and their cable television subscriptions for streaming video. This disruptive technology has created tension in the industry as old-school telecommunications companies cling to their non-Internet services out of fear of their infrastructure turning into “dumb pipes,” while other companies are lining up to provide services over the Internet. Discussion of this disruption usually turns to the subject of bandwidth — the measure of the telecommunications infrastructure's capacity to deliver these services to users.

I became curious about exactly how much bandwidth is used by the multimedia services that I consume, so I decided to graph the bandwidth usage while using these services. I collected the data points from the SNMP network interface counter readings on my router, and compiled them into the graphs below. Each test includes a rough ~10-second lead-in/lead-out, and the data represents 1-second averages unless indicated otherwise.

I was a little surprised to see that Vonage telephone calls use so much bandwidth. I looked at my service settings on the Vonage web site, and my service is indeed configured to use “high quality” audio which uses a nominal bitrate of 90kbps in each direction. This is astonishing, since traditional POTS phone service uses a 64kbps audio channel (8Khz 8-bit sampling). It turns out that by default, Vonage does not use audio compression [1], and encodes audio using the raw PCM format. [2] I'm probably not getting much benefit from this high quality stream, since I'm using a POTS telephone which limits me to the low-quality 8Khz audio that telephone users have experienced for decades. Some day, I would love to ditch the POTS bottleneck altogether, since I've found that hi-fi audio conferencing is much more pleasant.

There's nothing too surprising about the Pandora bandwidth usage. From the looks of the graph, it's downloading each song in a quick burst at some point before the scheduled playback.

YouTube seems to be very front-heavy, filling a large buffer at the start and topping off the buffer periodically. From the length of the quiet area at the tail of the video, I'd guess that the buffer size in this test was about 78 seconds or 7.5MB.

As expected, watching YouTube video with the HD option uses more bandwidth. The buffer in this case seems to be around 123 seconds or 30MB.

The above test was performed with a Roku HD-XR set-top box streaming a feature-length film from Netflix. The bandwidth usage is extremely bursty, with the Roku box taking large gulps from the stream periodically. Note that the interval between bursts does not reveal the buffer size, since the box is only “topping off” its buffer at these times. However, from the quiet area at the tail of the graph, we can surmise a ballpark estimate of about 350 seconds or 64MB.

Because the burstiness of the first Netflix graph doesn't convey the general bandwidth usage very well, I created this second graph which uses 5-minute averages instead of 1-second averages. This graph represents the same viewing session as the first, but with the bandwidth usage smoothed out. The average bitrate is around 1.5Mbps.

Here's another bursty graph representing the viewing of a TV show on Hulu. I believe the empty intervals within the show correspond to advertisement breaks. Interestingly, it seems that Hulu buffers the advertising in advance, and does not use the network for the duration of the advertisement.

Here's the smoothed version of the Hulu graph with 5-minute averages. The average bitrate is about 694kbps, which is quite a bit more efficient than Netflix streaming. However, I think the quality was a little lower, and Hulu certainly demands a lot from my computer. My older laptop with a Centrino/Pentium-M processor cannot play Hulu video without skipping, although my newer Core 2 Duo laptop handles it fine.

All tests were performed at the Caffeinated Bitstream testing laboratories at an undisclosed location in the Rocky Mountain region.

Footnotes

  1. “Vonage utilizes VoIP technology differently from its competition, in that it doesn't compress your voice, so the sound quality is superb.” http://www.vonage.com/how_vonage_works_faq/
  2. “Vonage uses the standard PCM audio codec by default because people prefer it.” http://www.interesting-people.org/archives/interesting-people/200407/msg00231.html
Firefox Selection Applet

After writing the ffremote.py script to help open links in the correct Firefox instance, I decided that it would be really nifty to develop a simple GNOME Panel applet to manage browser instances. (Again, not browser windows, but browser instances—completely separate Firefox processes running with distinct profiles and settings.)

When you click on the applet's icon, a menu is presented which lists the running browser windows and their associated profiles, as well as profiles which are not currently running. If you click on an item representing a running browser window, the window will be raised to the foreground. If you click on an item representing a non-running profile, a new Firefox instance will be launched with the selected profile.

Here are the instructions for using the applet:

  1. Install any needed prerequisites, such as python-xlib.
  2. Place the script in its final location:
    sudo cp ffselect.py /usr/local/bin/
  3. Run the script with the “install” argument with root privileges, to register the script as an applet:
    sudo /usr/local/bin/ffselect.py install
  4. Refresh the GNOME Panel:
    killall gnome-panel
  5. Right-click the GNOME Panel, select “Add to Panel”, and pick the Firefox Selection Applet.

Here is the applet script; be sure to note the comments at the top:

  • ffselect.py - a GNOME Panel applet for managing separate Firefox instances on the desktop.

Update 2010-01-17: This script stopped working after a recent Ubuntu update. Some change exposed a minor bug in the code. This is now corrected.