Teaching the Snake a New Trick

I learned Python about three years ago. At that time, I didn't know Python at all and took a job with a company that uses Python extensively. My job didn't actually consist of any Python work, but since I liked the company, I knew learning Python would be important for getting rehired. Python has since grown on me quite a bit, and whenever I am given a programming problem, I often find I come up with a Python solution the fastest. There are a few things that I love about it, but I'm not here to start a language war. I just taught the snake a new trick and I want to share it with you.

First, some background. I am a huge fan of the functional programming syntax that Python provides. Its for loops and list manipulation helpers are particularly natural and it's never been easier to mix and match imperative and functional programming.

One thing that I have been trying to do for a while but never actually found a Good Solution (TM) to is iterating over each consecutive pair of elements in a list. For example, if the list contains [1, 2, 3, 4], I want to execute some block of code with the pairs (1, 2), (2, 3), (3, 4).

The naive solution looks something like this:

L = [1, 2, 3, 4]

for i in range(len(L) - 1):

  a, b = L[i], L[i + 1]

  # work with a, b here

But come on, how ugly is that?

A much nicer solution uses the zip function as follows:

for a, b in zip(L[:-1], L[1:]):

  # work with a, b here

This forms two lists, one with the last element chopped off and one which is missing its first element. The pairs of corresponding elements of these two lists are the pairs of consecutive elements in the original list (zip does this part). Neat, huh? Can anyone come up with an even cleaner solution?

I leave you with a quote about programmers from Tidbits from the Dungeon:

Programmers are in a race with the Universe to create bigger and better idiot-proof programs, while the Universe is trying to create bigger and better idiots. So far the Universe is winning. -- Rich Cook

Well, it's back to homework for me.

-Cat

Lenovo Battery Sudden Death Syndrome

I'm a proud owner of a Lenovo ThinkPad X61s notebook. I bought it just over a year ago and I've been thoroughly happy with it. Until a month ago.

On October 16, two days after the end of my battery's one-year warranty, I came home after leaving the laptop plugged in during the entire day and, without thinking twice, unplugged the AC adapter as I usually do to take the laptop to the couch. The laptop turned off instantly and would not power back up with the battery. The ThinkPad Power Manager had this to say:

With the battery connected, the battery light on the front of the laptop flashed rapidly orange (it's supposed to be flashing green when charging and solid green when finished charging). Note that this happened suddenly -- the day before this happened, I had about 4 to 5 hours of battery life as usual.

I immediately called customer support and was greeted by a polite yet very unhelpful man. He was unable to help me in any way because my warranty had expired 2 days prior. It's a little silly, but I don't blame him; he's just following company policy. It looked like I would have to figure this out on my own.

From what I had heard, one of the most common causes of failure of Lithium-based batteries is failure of one of the cells (this battery pack, for example, is made up of 8 cells). The charging circuitry then avoids charging or discharing the cell, since damaged Lithium cells can be quite dangerous (explosions, etc.). Sometimes, it's as easy as replacing that cell; failed cells typically have a very low voltage, usually lower than 1.5V.

So, what does a good reverse engineer do with a potentially repairable battery pack? He cracks it open. WARNING: DON'T DO THIS AT HOME. It could literally blow up in your face.

Here's what a ThinkPad X61s 92P1172 battery looks like inside:

At this point, it's worth noting how the cells are connected in such a battery. The 8 cylindrical cells (part number "LH7M2D8") are grouped into 4 pairs. The two cells in each pair are in parallel, while the pairs are in series. If the cell voltage is Vcell, then the total voltage Vtotal = 4 * Vcell.

I measured each of the cell (pair) voltages, and they were all approximately 3.97V. According to TI's Using NiMH and Li-Ion in Portable Applications (Figure 1), this is a normal voltage for a mostly-charged cell. In fact, the Power Manager applet showed a total voltage of 15.86V, which adds up. However, it's debatable whether the PM reading should be trusted, since, not knowing exactly how the PM works, there is a possibility that the battery is in fact damaged and the reading is stale data from when it was last healthy. Either way, my multimeter confirmed the cells have a healthy voltage (I don't know enough about Li cells to say for sure that this means the cells are completely healthy). I also haven't tried measuring their voltage under load (a small resistor), since that's fairly dangerous if not done properly and I would prefer to avoid any fires until it becomes absolutely necessary.

And this is about where I got stuck. All signs so far point to a defective charge controller or a corrupted controller nonvolatile memory. I have tried doing the "reset battery gauge" procedure in Power Manager, but that results in my laptop hard-crashing (powering off) and nothing happens to the battery. I'm quite open to suggestions.

Thanks for reading, see you next time! :-)

Better iTap Learning

iTap (or T9 for you Nokia fans out there) is a widespread predictive text technology for cell phones, typically used when composing text messages (SMS). Each key on a cell phone's keypad is labelled with 3 (or 4) letters and, as you're pressing one number at a time, the phone tries to figure out which permutation of the sets of letters is most likely to be the word you are writing.

Of course, it always helps to integrate your own personal touch: new predictive text technologies actually learn from the words that you type. The newest versions even go so far as to record combinations of words and propose them to you when you're typing in case you want to repeat the same phrase. Very helpful stuff. But all this is done only based on what you write.

But what if the cell phone were to learn from your received text messages as well? Chances are you and your friends' vocabularies are pretty close. This potentially doubles the amount of learning material and therefore doubles the learning speed. Also, by associating the learned information with a particular correspondent, the device can make intelligent choices about the words it proposes to you. (You probably didn't mean to text "whats up dawg" to your mom.)

Motorola, hire me so I can implement this for you.

What do IPsec and Larvae Have in Common?

This is a bit of a digression from the usual topic of this blog, but I found the problem interesting enough to mention.

I have a Linux server at home, on which I tend to keep the command-line rtorrent client running in a detached screen session. I recently noticed that my rtorrent started hanging randomly -- the process would be in the sleeping state with no noticeable CPU usage, but it was entirely unresponsive to key presses. All other processes on the system were unaffected.

The first thing I did was Google search for "rtorrent hang". Sure enough, someone had had this problem before and reported that rtorrent was hanging on the "madvise" system call. The comment had claimed that it was a kernel bug, which wasn't entirely unrealistic since madvise seems to be a fairly esoteric, rarely-used, and therefore rarely-tested system call. The post pointed to a newer version of rtorrent, but, to my disappointment, even the latest version from SVN didn't solve the problem. My rtorrent was still hanging. And on top of that, HTTP requests seemed to be broken in the newer version because of what I can only assume is some incopmatibility with the relatively old version of libcurl on my machine.

I recompiled the original stable version of rtorrent, and thankfully HTTP torrent fetches and tracker requests worked again, but the hang was still there. I decided to investigate based on a clue left by the madvise post: use strace to see what syscall rtorrent was blocked in. This is what I found:

socket(PF_INET, SOCK_STREAM, IPPROTO_TCP) = 579

fcntl64(579, F_SETFL, O_RDONLY|O_NONBLOCK) = 0

setsockopt(579, SOL_IP, IP_TOS, [8], 4) = 0

connect(579, {sa_family=AF_INET, sin_port=htons(37320), sin_addr=inet_addr("189.51.247.163")}, 16) = -1 EINPROGRESS (Operation now in progress)

epoll_ctl(3, EPOLL_CTL_ADD, 579, {EPOLLOUT, {u32=139804600, u64=139804600}}) = 0

epoll_ctl(3, EPOLL_CTL_MOD, 579, {EPOLLOUT|EPOLLERR, {u32=139804600, u64=139804600}}) = 0

socket(PF_INET, SOCK_STREAM, IPPROTO_TCP) = 580

fcntl64(580, F_SETFL, O_RDONLY|O_NONBLOCK) = 0

setsockopt(580, SOL_IP, IP_TOS, [8], 4) = 0

connect(580, {sa_family=AF_INET, sin_port=htons(57524), sin_addr=inet_addr("192.168.0.10")}, 16

"How was this possible??" I asked myself. You can clearly see that socket 579 was put in nonblocking more and connect immediately returned "EINPROGRESS", as it should. But socket 580, which was doing virtually the same thing, was blocking in "connect." How was that possible? What was the difference?

It turns out the difference was in the destination IP address. I had almost forgotten that, prior to this hanging problem, I had set up an IPsec tunnel to my friends' network. His network is on 192.168.0.0/24, so when rtorrent was trying to connect to 192.168.0.10, my kernel was actually trying to establish an SA (IPsec tunnel) to my friend's network. A quick search for "ipsec blocking socket" quickly revealed that this behaviour is documented and configurable (http://lkml.org/lkml/2007/12/4/260). In fact, by simply "echo 0 > /proc/sys/net/core/xfrm_larval_drop", I solved the mystery of the hanging rtorrent. In this case, the kernel simply drops any packets associated with an IPsec tunnel that is in the process of being established -- instead of blocking the calling process until that tunnel is fully established.

This solution, of course, does have its downsides: when setting up or debugging an IPsec tunnel, you end up seeing packet loss without really knowing the reason. Temporarily turning xfrm_larval_drop is probably a good idea while tweaking your IPsec configuration!

See you next time.

-Cat

Laundry Part 3

Let's recall from last time: we're studying an Atmel AT88SC0404C ("CryptoMemory") in smart card form factor. We can communicate with it via a serial bus compatible with a regular PC serial port. We identified it using the Answer-to-Reset string, which ISO 7816 specifies all such cards must send when brought out of reset. Now we want to poke around the card a bit, hopefully doing something like reading the card's balance.
From this point on, the AT88SC0404C datasheet is an essential part of our work. At the very least, it's important to quickly scan it to get an idea of how the device works. There's a couple of tables you'll find yourself referring to fairly often:

• Figure 4-10 (AT88SC0104C, 0204C, 0404C Configuration Memory) on page 14;
• Table 8-2 (CryptoMemory Asynchronous Command Set) on page 41;
• Table 8-3. Asychronous Mode Return Status Definitions.

The chip has some fuses that provide chip-level protection. Let's try to read the fuse status byte:
ATR 3b b2 11 00 10 80 00 04
--> 00 b6 01 00 01
<-- (b6) 20 [90 00]
That (b6) is the INS byte (command) sent back to us, the 20 is the fuse byte, and the trailing [90 00] is the status code. According to the datasheet (page 24), this means that all fuses have been blown.

The AT88SC0404C has a great deal of configuration memory (256 B); let's try to dump it using the "Read Config Zone" command. Keep in mind that bytes that we don't have rights to read will appear as 20 (the fuse byte):
ATR 3b b2 11 00 10 80 00 04
--> 00 b6 00 00 f0
<-- (b6) 3b b2 ... 20 20 [69 00]

Here's the data, formatted for comparing with the configuration zone map on page 14 (and with potentially identifying data removed):
000000 3b b2 11 00 10 80 00 04
000008 40 40 ff ff ff ff ff ff
000010 69 x2 08 x2 28 x0 40 x0
000018 bf 00 00 00 x0 x5 xd xb
000020 df 08 df 08 df 58 df 58
000028 ff ff ff ff ff ff ff ff
000030 ff ff ff ff ff ff ff ff
000038 ff ff ff ff ff ff ff ff
000040 ff ff ff ff ff ff ff ff
000048 ff ff ff ff ff ff ff ff
000050 ff 5d ae 47 5a 06 51 db
000058 20 20 20 20 20 20 20 20
000060 ff ff ff ff ff ff ff ff
000068 20 20 20 20 20 20 20 20
000070 ff ff ff ff ff ff ff ff
000078 20 20 20 20 20 20 20 20
000080 ff ff ff ff ff ff ff ff
000088 20 20 20 20 20 20 20 20
000090 20 20 20 20 20 20 20 20
000098 20 20 20 20 20 20 20 20
0000a0 20 20 20 20 20 20 20 20
0000a8 20 20 20 20 20 20 20 20
0000b0 ff 20 20 20 ff 20 20 20
0000b8 ff 20 20 20 ff 20 20 20
0000c0 ff 20 20 20 ff 20 20 20
0000c8 ff 20 20 20 ff 20 20 20
0000d0 ff 20 20 20 ff 20 20 20
0000d8 ff 20 20 20 ff 20 20 20
0000e0 ff 20 20 20 ff 20 20 20
0000e8 88 20 20 20 ff 20 20 20
0000f0 end

Let's take a look at some of the interesting fields and their values:

• Offset 18h - DCR = BFh
• Offset 19h - Identification Number Nc = "00 00 00 x0 x5 xd xb"
• Offset 20h - AR0 = DFh
• Offset 21h - PR0 = 08h
• Offset 22h - AR1 = DFh
• Offset 23h - PR2 = 08h
• Offset 24h - AR2 = DFh
• Offset 25h - PR2 = 58h
• Offset 26h - AR3 = DFh
• Offset 27h - PR3 = 58h
• Offset 50h - Reserved for Authentication and Encryption = "ff 5d ae 47 5a 06 51 db"
• Offset E8h - PAC = 88h

The DCR value is the Device Configuration Register and the meaning of its bits are explained in detail in section 5.3.8. The conclusion is that the Write 7 password (master password) has been disabled, "Unlimited Checksum Reads" is asserted, "Unlimited Authentication Trials" are not allowed and we are only allowed 4 incorrect password attempts before the device locks itself out in hardware, permanently. (Be careful not to "brick" your card!)

Next, we have an Identification Number that varies according to the number on the back of the card. It's not quite the same number, but the value of Nc does increase by 1 per every increment of the number of the back (i.e., it's just an offset).

The Access Registers are a bit more interesting. The AR values have PM(1:0)="11", meaning "no password", but since AM(1:0)="01", this means the cryptographic authentication protocol is in effect. "Encryption Required" is set to 1, which appears to mean deasserted. The rest of the bits aren't too interesting.

The Password Registers tell us that the device's user memory is split into two areas, accessed by different passwords/keys. The first half uses AK(1:0)="00" and POK(1:0)="00" and the second half uses AK(1:0)="01" and POK(1:0)="01".

The next part appears to be "Cryptograms" (section 5.3.12). This is most likely part of the cryptographic authentication protocol. The first page of the datasheet states that the chips use a "64-bit Mutual Authentication Protocol" under license from ELVA. If you look them up, they appear to be a French company that has filed patents on the topic to the US Patent Office: Method of enabling a server to authorize access to a service from portable... The patent makes reference to various cryptograms that get shuffled around to validate the identity of the device and/or host. Of course, the patent omits the details truly valuable to an implementation or for cryptoanalysis. (Okay, fine, I didn't read it all. If anyone finds and juicy details, please post!)

The very last field we can look at is the Password Attempts Counter for the Write 7 password. Because I attempted to validate the Write 7 password a couple times, this counter has decreased to 88h. This means I only have one attempt before the card locks itself out completely. Ouch! Don't do this at home!

Well, that's about it for now. I ordered a kit from Atmel that includes all the libraries, in binary format, needed to use the cryptographic authentication protocol. When I have something new to report, rest assured you'll be the first to know. Until then, 73.

-Cat

Laundry, Semi-part 2b

To all my faithful readers:

It has been far too long since I've posted here. Unfortunately, my blog tends to take a rather low priority for me, and Real Life has been knocking on my door pretty insistently the past few months. Nonetheless, I will make an effort to post a bit more often and keep you posted on my techy adventures.

See you in a bit and don't give up on me!

-Cat

Laundry Part 2

Here's the deal. We've got what looks like an ISO 7861 smartcard. It's used for "laundry," something most of us geeks reject as part of the alternate universe we like to call the "Real World." I digress. We're trying to communicate with this smartcard, hoping to unlock its secrets...

Let's start with a review of the electrical signals defined by the ISO standard.

VCC and Ground are pretty straightforward. Clock must be provided to the smartcard, TTL-level and on the order of 3 MHz. Input/Output is a bidirectional data pin; the protocol determines whether the host or the smartcard is driving this line at a given instant. The Reset signal is active-low.

We'll be connecting the I/O pin to a MAX-232 level shifter to convert the TTL level to the PC's RS-232 levels (and vice-versa). From the PC side, you have separate signals for transmit and receive; I connected the I/O pin directly to the PC's receive; the PC's transmit is spliced in with a 1 kOhm resistor. The resistor should limit the current in case something goes wrong, and in normal operation, the current is low enough that the voltage drop across the resistor isn't high enough to disturb data sent from the PC.

Now let's talk a bit about the protocol on this I/O pin. Right after reset, the card sends a block of data called the Answer to Reset (ATR); this is documented in section 2.3.4 of the standard. The baud is specified as being the input clock frequency divided by exactly 372. The other parameters are: 8 bits, even parity and one stop bit.

Assuming we want to work at a baud of 9600 (fairly typical baud for PC serial ports), this means we need an input frequency of 3.5712 MHz. While there's crystals out there that provide this frequency, I don't have one and I don't have a signal generator either. So I had to improvise.

I had laying around an Altera UP2 development board with a 25.175 MHz crystal. This is an educational board with a CPLD and an FPGA (programmable logic chips); I also happened to have a working copy of Quartus usable to create designs for the chips. I basically used a binary counter as a frequency divider from the main 25.175 MHz clock. In the end, it looked something like this:

Don't be deceived by the large board; it's just an oversized clock generator.

At first, I tried using a divisor of 7, which adds up to a baud of (25.175 MHz / 7 / 372 = ) 9668. This is really close to 9600, and most serial port receivers tolerate a certain margin of error, but 9668 turned out to be too far off; data become garbled after the first few bytes. If I settled for an I/O baud of 1200 bps, the required clock for the smartcard would be only 0.4464 MHz. With a divisor of 56, I would get a baud of 1208 bps, which was close enough for the serial port. I was able to get an ATR:

atr: read 8 bytes: atr: read 8 bytes: 3b b2 11 00 10 80 00 04

A quick Google search for this hex string quickly uncovered the identity of this smart card:

3B B2 11 00 10 80 00 04
Atmel memory card AT88SC0404C
http://www.atmel.com/dyn/resources/prod_documents/doc5210.pdf

Aha! Luckily, the datasheet is fairly explicit regarding the command set of the chip. But you'll have to wait until next time to see what happened when I started poking commands at it.

Laundry

Nowadays, it seems like real money (in the sense of cash) barely even exists anymore. We have debit cards, credit cards, paypal accounts, wire transfers... And in a sense, this is much more convenient than hiding 35 grams of gold under your pillow. On the other hand, as good as one may be at staring contests, it's a lot easier to convince a smart card that you put money on it than to convince 35 grams of gold that it's really 45 grams.

The laundry machines at my apartment building use SmartCity smart cards. There is a refill machine that takes debit (aka Interac) as well as credit cards. Here's what the cards look like (and the transcribed text for the benefit of search engines and visually impaired readers):


"SmartCity

Smart cards by Coinamatic

Canada's Most Trusted Name in Apartment Services™"

"Please treat this card like cash. The value on this card will not be replaced if the card is lost, stolen, destroyed, or altered. Use of this card constitutes acceptance of the terms and condition stated in the SmartCity® Resident Card Information section on http://www.coinamatic.com/
Questions? 1-800-561-1972 ou customerservices@coinamatic.com"

On the back, in the bottom-left corner, is what looks like a 7-digit numeric serial number.

The electrical contacts you can see on the front side (first photo) are the typical ISO 7861 physical interface. Most (if not all) of these cards also obey the electrical interface and protocol defined by the same standard. Luckily for us, this means all we need to communicate with them is a clock generator, an RS-232 level shifter (MAX232) and a regular PC serial port.

Stay tuned for more details on what happened when I hooked the card up to my PC! For now, I've got some homework to do.

-Cat

Back in Black

Yesterday, I came back from Montreal after having attended my 3^rd CUSEC. I have attended the conference every year since my first year in Software Engineering and I have to say that I was very happy this year to see a continued commitment to high quality talks and a friendly and fun atmosphere all around.

I thoroughly enjoyed most of the keynotes, but Jeff Atwood's talk was particularly motivating to me. I remembered I had started this blog a long time ago, and abandoned it (alas, for this is the destiny of so many of my projects); Jeff reminded me that I did indeed have something to say to the world.

I'm a Software Engineer by University program; a versatile programmer by experience and a hacker at heart. It's hard to keep me from reverse engineering just about any piece of technology that happens to drop on my lap. I happily drop from the virtual world of ones and zeroes and get my hands dirty with my soldering iron.

As for most geeks, my home page speaks of me better than I can: http://vv.carleton.ca/~cat/

See you around the blogosphere!