06
Dec 12

Presentation on TCP sequence number prediction

This was an in-class presentation on the concepts behind TCP sequence number prediction. I didn't record the talk itself but the slides are available below.


22
Oct 12

CAN bus

I've started working with CAN bus for a new project I'm doing, using Microchip's MCP2515 CAN controller and MCP2551 CAN transceiver. In this blog post I'll explain how the CAN bus works at the bit level, to make it easier for us to debug when something isn't working.

CAN bus on a breadboard

I hooked up a quick circuit using an ATmega32 and the two CAN bus chips. I used SPI to send a single CAN data frame to the target ID 0x555, and then captured the frame using a logic analyzer.

CAN bus frame format

Working Backwards

Let's pick through our message and understand where each of the bits came from. The bit stream that we captured with the logic analyzer was

010101010101000001001100111010011001011111111

which corresponds to the Start of Frame marker, Arbitration Field, Control Field (including Data Length Code), CRC sequence (including CRC delimiter), ACK field, and End Of Frame (EOF) delimiter. Note that the Control Field contains a run of five 0 bits, which means a 1 bit has been stuffed into the value. So we know that we should remove that extra 1 bit from the Data Length Code to get the correct value of 0000. So this message has a payload of 0 bytes. The "Arbitration Field" is just another name for the "Identifier", so our extracted identifier is 10101010101 or 0x555.

The first three bits of the Control Field are the RTR bit, IDE bit, and "r0" reserved bit. In our message these three bits are all 0. The RTR bit represents whether this CAN frame is a Remote Transmission Request or not. Apart from error handling, every CAN frame is either a Remote Frame (the sender is requesting some kind of reply from the receiving node), or is a data frame. The IDE (ID Extension) bit represents whether this data frame is addressed to an extended ID (an extended CAN message). Some manufacturers decided that 11 bits couldn't address all of their devices (211 = 2048). So they took an unused bit from the old CAN bus Control Field and called it the IDE bit. When the IDE bit is set, the message structure is slightly longer, and there is an additional 18-bit Identifier field meaning that an extended CAN message can address up to 229 = 536870912 different devices on the same bus (wow!). Alternatively, these ID bits can be split up among several fields (priority, category, sender type, etc). For now we'll ignore extended IDs, because we sent ourselves a standard CAN bus data frame (IDE bit = 0).

Since our Data Length is 0, we have 0 bytes of payload. So the next field is the CRC sequence, and the CRC delimiter. To understand where the CRC sequence came from, we need to understand a little bit about CRC checksums. I will assume that you've read up on how CRC works. The polynomial that CAN bus uses for the CRC calculation is x15+ x14+ x10+ x8+ x7+ x4+ x3+ x0  (according to the official documentation). We then checksum all the bits from the Start of Frame Marker until just before the CRC sequence, except for any stuffed bits that have been inserted to break up long runs of the same bit value. So after we remove the stuffed bit that was inserted into the Data Length field, we get the bit sequence 0101010101010000000, or 0x2AA80. We can use an online tool to help us perform the CRC calculation, and we will find that the generated value is 0b110011101001100, which is the same value that was contained in the original CAN frame. The CRC delimiter is always 1 (recessive state).

The first bit of the ACK field (the ACK bit) is transmitted as 1 (recessive state) by the sender of a data frame, and anyone who has heard the message and verified its CRC checksum pulls the bus into a dominant state (0 bit) during the message's ACK bit, which tells the sender that at least one receiver has successfully read the message. Note that we can't tell how many other nodes successfully received the message -- we can only tell if nobody received it, or at least one node got it. Most CAN controllers are configured to repeat a message until it gets received by someone. The second bit of the ACK field is always 1 (recessive).

Finally, the End Of Frame (EOF) delimiter marks the end of a CAN frame with 7 recessive bits.

That wasn't so bad!

UPDATE: I've added a bit of code to perform the CANbus CRC calculation below:

#include <stdio.h>
#include <stdint.h>

uint16_t can_crc_next(uint16_t crc, uint8_t data)
{
    uint8_t i, j;

    crc ^= (uint16_t)data << 7;

    for (i = 0; i < 8; i++) {
        crc <<= 1;
        if (crc & 0x8000) {
            crc ^= 0xc599;
        }
    }

    return crc & 0x7fff;
}

int main()
{
    int i;
    uint8_t data[] = {0x02, 0xAA, 0x80};
    uint16_t crc;

    crc = 0;

    for (i = 0; i < sizeof(data); i++) {
        crc = can_crc_next(crc, data[i]);
    }

    printf("%x\n", crc);
}

06
Aug 12

Introduction to FastCGI

This is a brief introduction to FastCGI that I created.


21
Apr 12

Decoding small QR codes by hand

It's not hard to decode QR codes with a pen and paper. For this guide I'm going to grab a random QR code from google images and show the process of decoding it by hand. QR codes contain a lot of error correction information and they can survive a lot of errors, but that's a lot harder to do using just a pen and paper (and 99% of the QR codes you encounter don't have any missing bits, so it's rarely necessary). So I'll highlight where the error correction information is stored, but I won't explain it in this guide.

The picture I found is from http://mikejcaruso.blogspot.ca/2011/04/qr-code-tattoos.html

40310107-qr-1

Before we begin we should rotate it to the proper orientation. QR codes always have 3 timing patterns (big black squares) in all the corners except for the bottom-right. So we need to rotate our picture 90 degrees counterclockwise:

40310146-qr-2

The first thing we should learn is what QR code version we're looking at. The version basically just represents the physical size of the QR code. Count the number of pixels (or modules) across the QR code, subtract 17, and divide by 4. For example, our tattoo QR code is 25 modules wide, and (25-17)/4 = 2, which means this is a version 2 QR code. Very big QR codes (versions 7-40) have a few extra features, but most consumer QR codes are fairly small and simple, so you don't need to worry about that.

Next, we will figure out our QR code's format marker. Every QR code stores two identical copies of the format marker, but we only need one of them. The format marker is 15 bits long: 5 bits of format information, and 10 bits for error correction. The first 5 bits of the format marker hold the error correction level (2 bits) and the data mask (3 bits). These 5 bits are found here:

40310322-qr-3

So in our case the format information is 01100. However this number has been XOR'ed with 10101 before being written into the QR code. So we must flip bits 1, 3 and 5. After flipping the bits, we get a format information string of 01100^10101 = 11001. The first two bits of this value are the error correction level (the amount of error correction data included in the QR code). Again, we can ignore this. The last 3 bits of the format string are 001, and this is the most important piece of information. This means the body of the QR code has been masked against the mask number 001. Here is a table of all the possible mask numbers and their appearance:

40310477-qr-mask

Here's where you need the pen and paper. The reason QR codes are masked in the first place is that sometimes particular combinations of data bytes produce QR codes with certain undesirable features (like big empty blocks in the middle). These undesirable features confuse the QR code reader, so the data is masked against a value in order to make the code easier to process when it's scanned by a QR code reader. The computer then unmasks the original data bytes using the same process, and retrieves the data.

You can imagine the masking process as essentially covering the surface of the QR code in one of the patterns seen above, starting from the top left corner. In our case we have a mask reference number 001, which means all of the odd-numbered rows are black. Once we've tiled the surface of our original QR code using the mask pattern, then every black pixel in the mask means we need to invert the corresponding bit in the original QR code. So in our case, we need to (in our mind, or using the pen and paper) invert all of the bits on odd-numbered rows. Note that we only mask the data pixels, and not the timing patterns or the format marker (otherwise we wouldn't know how to unmask it to get the mask reference number!). The data areas are the yellow areas in this picture:

40310738-qr-data

I've highlighted the data areas of the tattoo QR code below:

40310752-qr-5

Note that there's a little island in the middle of the data area that we must work around. That's called an alignment pattern, and whenever you see one in the data just skip past it to read the data bytes.
From now on we need to always remember the mask pattern above, and whenever we read bits from the data section we need to account for the mask pattern, and flip any bits that would be masked off by it (in our case, that's every odd row).

The data section consists of [header][data] chunks. Technically QR codes are allowed to have several of these chunks, but most QR codes just have one big chunk that holds all the data, so it won't matter. The header has an encoding type and a length (the number of data bytes). The encoding type is always 4 bits, but the length is stored in 8-10 bits depending on the encoding type. Here's the encoding type of our tattoo:

40310861-qr-4

But remember, every odd row needs to have its bits inverted. To help us remember, I'll use green to highlight every cell that should be inverted when we read it:

Now, the encoding type is stored as the bottom-right 4 bits, starting from the bottom right and working left and right in a zig-zag motion.

40311191-qr-7

So in our case, the tattoo itself has the bits 1000. However the bottom row is masked, so we invert the first two bits: 0100. This means that our QR code's encoding type is 0100. Here's the table of encoding types:

  • 0001 Numeric
  • 0010 Alphanumeric
  • 0100 8-bit Byte

The other encoding types are rarely used in consumer QR codes. They're used for encoding japanese characters, custom charsets and spreading a message across several QR codes in series. For our purposes these 3 encodings will be enough.

So that means that our QR code uses 8-bit byte encoding. The next piece of information is the length field, or the number of characters (clusters of bits) that are in the message. Like I said, the length field changes size depending on the encoding type. Here's the number of bits in the length field, for each encoding type:

  • Numeric (10 bits)
  • Alphanumeric (9 bits)
  • 8-bit Byte (8 bits)

Since we're using 8-bit byte mode, our length field is 8 bits long. We read the next 8 bits in a vertical zig-zag motion, like this:

So the tattoo itself contains the bits 11011100 (reading from bottom to top). However we need to mask two of these rows, so the actual length field has the value 00010000. That's 16 in decimal, which means this QR code has a message that is sixteen 8-bit bytes long. After the length field, the bytes themselves are stored, one after another, MSB first. We continue climbing in a vertical zig-zag motion until we hit the top, and then we curl over and continue downwards as seen in this picture:

40311284-qr-placement

So the first byte would be 10000110 (masked), which is 01001101 (unmasked). That corresponds to ASCII character 'M'. The next byte would be 10101101 (masked), which is 01100001 (unmasked). That corresponds to ASCII character 'a'. So far we've decoded "Ma".

Continuing up and around the corner: 10100000 (masked), or 01100011 (unmasked). That's ASCII 'c'. Then it's 'i'.

By continuing in this way, we can decode the full message: Maci Clare Peltz.


20
Mar 12

Ghetto magnetic stripe reader

It's quite easy to read data off of magnetic stripe cards. Each card has up to 3 horizontal tracks of data (but the third track is rarely used). Track 1 is formatted according to IANA standards, which means 7 bits per character. Individual bits of the digital data are physically stored using Aiken-Biphase encoding, which means a 0-bit is represented by a zone with a single direction of magnetic flux, and a 1-bit is represented by a zone of two different magnetic flux directions. This can be visualized using < and > characters representing the different directions of magnetic flux:

<<<<>>>><<<<>>>><<>><<<<>><<>>>>

This represents the bit pattern 00001010. A magnetic field acts like a flowing river of water, and at the center of a junction like >><< the two waves collide, which causes the magnetic flux density to grow very high around that point. Similarly at a <<>> junction, the magnetic flux at the middle point becomes very strong but with the opposite polarity than the >><< junction. We can detect this magnetic flux polarity by moving a coil of wire through the magnetic fields that surround the magnetic zones. As the coil moves through the field, the changing magnetic field strength causes electric potential in the coil. If the coil is hooked up to an electric circuit, it will act like an AC generator, which switches polarity whenever the coil passes from one zone of magnetic flux to a zone of the opposite magnetic flux. Spikes of electric potential will be induced in the coil as it passes the >><< and <<>> junction points. We can analyze the timing of these spikes to recreate the original data stored on the magnetic stripe.

I salvaged the tape read head from an old audio cassette player. Tape heads are just a small coil of wire mounted in a chunk of plastic or metal. The coil in the tape head was connected to 4 individual wires, and I used a multimeter and found that 2 pairs of wires had 300 ohms of resistance between them, and the other wires weren't electrically connected at all. I guess this is because the tape head has 2 separate coils to read stereo audio tapes. I cut an old audio cable in half and connected the GND and LEFT wires to one of the coils in the tape head. I plugged the audio cable into my sound card's Mic input, and turned up the amplification of the Mic channel. I swiped the tape head past a magnetic stripe and I could hear a garbled digital chirp. I used Audacity to record the chirp and zoomed in until I could see the waveform clearly. Sure enough, the areas where two opposite magnetic fields collided could be clearly seen as positive and negative spikes in the signal.

39468558-aiken_biphase

According to ISO standard 7813, track 1 (the topmost 1/3 of a magnetic stripe) is padded with 000...000 at both ends so it's easier to parse the data. At the default zoom level, I found that a pencil fit perfectly inside the width of a single bit. Then as I moved the pencil along the signal, 0-bits were represented by the signal changing state once along the pencil's width, and 1-bits were represented by the signal changing state twice within the same timeframe. Using the pencil trick, I managed to read the entire sequence of bits for track 1 of my credit card. Then I grouped them into 7-bit chunks, and looked them up in the ISO 7813 character table. Using this method I managed to read all of the stored information off of the credit card. In the waveform below you can also see that I didn't swipe the card at a constant speed, so the leftmost bits are spaced slightly wider than the rightmost bits, but it's still very easy to distinguish the data.

39468574-aiken_biphase_decoded