I figured the MBR would be interesting to learn a little bit more about, so I decided to load it up into IDA Pro, a tool for disassembling programs, and see what I could find out.

This baby rhino was also curious about MBRs.

For this analysis, I assume that you are familiar with the x86 architecture and assembly. If not, WikiBooks has some great information about it here. I am also using IDA Pro to do this. I have tried to provide comments and labeling in my IDA work, but I also explain each block of code separately.

The first step in figuring out the MBR was to actually get a copy of it I could work with. To do this, I used Hex Workshop, which offers a way to do a binary copy of hard disks. The MBR is always located as the first sector of the disk, so I used Hex Workshop and extracted this file. It is only 1 sector long, so it is a mere 512 bytes.

After looking at Wikipedia, I figured out the MBR structure was:

0000h - 01B7h       Code Area (440 bytes)
01B8h - 01BBh       Disk Signature (4 bytes)
01BCh - 01BDh       Generally Zeroed out (2 bytes)
01BEh - 01FDh       List of Partition Records (4 16-byte structures)
01FEh - 01FFh       MBR Signature (2 bytes - Must be AA55h)

The above structure is what gets loaded into memory and executed. The code area is going to do a few different things, which I look at below. The disk signature can be used to uniquely identify a hard disk. The partition records define different operating systems and partitions on the hard disk. Have you ever noticed how you have to jump through some hoops if you want to have more than 4 operating systems or partitions on your computer? Well, that’s because you only have 4 partition records available. The MBR signature helps illustrate that this is in fact an MBR structure.

The partition records are a pretty important part of the MBR, so I also examined their structure. It is:

0000h - 0000h    Status byte (80h for bootable, 00h for non-bootable, others are invalid) (1 byte)
0001h - 0003h    CHS address of first absolute sector (3 bytes)
0004h - 0004h    Partition type (1 byte)
0005h - 0007h    CHS address of last absolute sector (3 bytes)
0008h - 000Bh    LBA of first absolute sector (4 bytes)
000Ch - 000Fh    Number of sectors in partition (4 bytes)

That is a pretty simple structure; just a start and stop address, length, and a few informational bytes. The CHS format is a little confusing though. CHS stands for Cylinder-Head-Sector and defines an address inside of a physical hard drive. You can read more about CHS here. The LBA address stands for Logical Block Address. LBA is a format to linearly address space on the hard drive, rather than defining 3 separate numbers for Cylinder-Head-Sector format. More information about LBA is here.

After examining the file MBR structure, I loaded the binary file into IDA Pro. Since it is a binary file, IDA doesn’t know where the correct segments or entry points are, or even if it is 16 or 32 bit code. Since we don’t have an OS yet, we know that this code is 16 bit. Looking at the MBR structure, the code starts at the very first byte of the file. Knowing this, I configured IDA and converted the first few bytes to code. I got the following:

s0:0000 ; ---------------------------------------------------------------------------
s0:0000
s0:0000 ; Segment type: Pure code
s0:0000 seg000          segment byte public 'CODE' use16
s0:0000                 assume cs:seg000
s0:0000                 assume es:nothing, ss:nothing, ds:nothing, fs:nothing, gs:nothing
s0:0000                 xor     ax, ax          ; Zero out AX
s0:0002                 mov     ss, ax          ; Set SS to 0
s0:0004                 mov     sp, 7C00h       ; Set SP to 7C00h
s0:0007                 mov     es, ax          ; Set ES to 0
s0:0009                 mov     ds, ax          ; Set DS to 0
s0:000B                 mov     si, 7C00h       ; Source for the copy
s0:000E                 mov     di, 600h        ; This is the destination for the copy
s0:0011                 mov     cx, 200h        ; We want to copy 200h bytes, which is the length
s0:0011                                         ;    of one sector, i.e. the whole MBR.
s0:0014                 cld                     ; Clear Direction Flag
s0:0015                 rep movsb               ; Copies CX bytes from [SI] to [DI]
s0:0015                                         ;    i.e. from [7C00h] to [600h]
s0:0017                 push    ax              ; New value for CS
s0:0018
s0:0018 loc_18:                                 ; New value for IP
s0:0018                 push    61Ch
s0:001B                 retf                    ; Pops the top of the stack into IP then pops CS
s0:001B	                                        ;    off next.
s0:001B                                         ;    i.e. we will run from 0000h:61Ch,
s0:001B                                         ;    which is where we just copied ourselves to.
s0:001B                                         ;
s0:001B                                         ; Execution continues at the next instruction.

I have tried to add a lot of comments to show what is going on. Essentially though, what this is doing is copying the MBR from 0000h:7C00h to 0000:600h. This is necessary, because it will later load the OS to 0000h:7C00h, so it needs to get itself out of the way. It does this using the ‘rep movsb’ which does a binary copy of 200 bytes from SI (7C00h) to DI (600h).

An interesting part about the code above is the way that the ‘retf’ instruction is used. This does what is known as a ‘far jump’. This means it not only jumps to a different instruction address, but also a different code segment. Both of these values are popped off of the stack, with the offset being on top and the new segment being second. Before the retf instruction, the program pushes 0 and then ’61Ch’ onto the stack to setup for this far jump. This may seem strange, but since it just copied all the program data to 0000h:0600h, 61Ch is actually the offset to the instruction directly after the retf in the binary.

The next few instructions are:

s0:001C                 sti                     ; Enable interrupts
s0:001D                 mov     cx, 4           ; This will be used for the loop.
s0:001D                                         ;    We only want to examine 4 partition records.
s0:0020                 mov     bp, 7BEh        ; This is the offset to the first partition
s0:0020                                         ;   record.
s0:0020                                         ; In the MBR structure, the first partition
s0:0020                                         ;    record is at base+1BEh,
s0:0023                                              so it is 600h + 1BEh = 7BEh
s0:0023

First thing this code does is to enable interrupts so that it can be interrupted if necessary. Next, it sets the CX register to 4 and BP to 7BEh. BP is the offset to the partition records (there is a description of these records here). CX is indicating that we will only examine 4 records (since there are only 4 in the MBR). So this is setting up to iterate over the 4 partition records to find the bootable one that we want.

After this is a loop that tries to find a bootable partition entry. The code is:

s0:0023 loc_23:                                 ; CODE XREF: seg000:0030j
s0:0023                 cmp     byte ptr [bp+0], 0 ; Compares the status byte to 0
s0:0027                 jl      short FoundBootableEntry ; Jumps if the status flag is not 0.
s0:0027                                         ;    This will happen if the MSB of [bp+0]
s0:0027                                         ;    is 1, essentially saying that if it
s0:0027                                         ;    is 0x80, it will jump.
s0:0027                                         ;
s0:0027                                         ; This jump indicates that we have found the
s0:0027                                         ;    bootable partition.
s0:0029                 jnz     PrintInvalidPartitionTable ; It's not 0x80 and it's not 0x0, so
s0:0029                                         ;    it's invalid. Jump to an error state.
s0:002D                 add     bp, 10h         ; Go to the next partition record.
s0:0030                 loop    loc_23          ; Loop while CX != 0
s0:0032                 int     18h             ; TRANSFER TO ROM BASIC
s0:0032                                         ; causes transfer to ROM-based BASIC (IBM-PC)
s0:0032                                         ; often reboots a compatible; often has no effect
s0:0034                                         ; at all

Remember how above we moved the offset of 7BEh into BP? That is so this loop can then examine the partition records. The comparison is checking the status byte of the partition record and comparing it to 0. If it is 0, the first jump will not be taken, nor will the second jump, so 10h is added to BP and the loop is restarted. Advancing the BP register means that we will examine a different partition record. If, after 4 iterations, we have still not found a bootable partition entry, an ‘int 18h’ call will be made. On old IBM PCs, this would run a BASIC interpreter from ROM, but few computers have this. So essentially, an int 18h call will just stop the system. Imagine that, if you have no bootable entries, you’re computer won’t boot!

If the status byte of the parition record was in fact 80h, the first jump would have been taken. The JL instruction does a jump if the status flag is set to 1. This flag will get set by the previous CMP instruction if the high order bit is set in the status byte, i.e. the status byte is 80h. If the entries status byte is neither 80h or 00h, a jump is made to the PrintInvalidPartitionTable location. I’ll talk about that a little bit, but it’s pretty boring (it just prints an error message); when a bootable entry is found, things are much more fun.

The next block of code is run when a bootable entry is found. Here it is:

s0:0034 FoundBootableEntry:                     ; CODE XREF: seg000:0027j
s0:0034                                         ; seg000:00AEj
s0:0034                 mov     [bp+0], dl      ; Save the drive number for later
s0:0034                                         ;    Note that since this will most likely be the
s0:0034                                         ;    first hard drive, DL will probably be 0x80
s0:0037                 push    bp
s0:0038                 mov     byte ptr [bp+11h], 5
s0:003C                 mov     byte ptr [bp+10h], 0 ; This is a sentinel value for later
s0:0040
s0:0040 loc_40:                                 ; DATA XREF: seg000:014Fr
s0:0040                 mov     ah, 41h ; 'A'
s0:0042                 mov     bx, 55AAh
s0:0045                 int     13h             ; DISK - Installation Check
s0:0045                                         ;   CF set on error
s0:0045                                         ;   CF cleared on success
s0:0045                                         ;   BX = AA55 if installed
s0:0045                                         ;   AH = major version of extensions
s0:0045                                         ;   CX = API subset
s0:0045                                         ;   DH = Extension version
s0:0047                 pop     bp
s0:0048                 jb      short AttemptLoadFromDisk ; Jump if Below (CF=1)
s0:004A                 cmp     bx, 0AA55h      ; DATA XREF: seg000:0045r
s0:004A                                         ; seg000:007Er ...
s0:004A                                         ; Compare Two Operands
s0:004E                 jnz     short AttemptLoadFromDisk ; Jump if Not Zero (ZF=0)
s0:0050                 test    cx, 1           ; Logical Compare
s0:0054                 jz      short AttemptLoadFromDisk ; Jump if Zero (ZF=1)
s0:0056                 inc     byte ptr [bp+10h] ; This acts like a sentinel value
s0:0056                                         ;    for whether or not the INT 13
s0:0056                                         ;    extended read is installed
s0:0059

First part of this block does is moves the DL register into where the entry’s status byte used to be. I wasn’t really too sure what was going on here for a long time, since if it overwrites the partition record, won’t it not boot correctly next time? Well, it turns out that the first hard drive is represented by 80h, so most of the time, things will be fine. I don’t have 2 hard drives, so I’m not sure what would happen if you had two hard drives and had your bootable entry on the second hard drive. I suspect that the 2nd hard drive would just have its own MBR and would run that instead. Running code on 1 hard drive and loading data from another hard drive seems a little bit silly anyways, so I’m pretty sure that’s whats going on. If you know more, please leave a comment!

Next, the code saves the partition record to the stack and moves the values 5 and 0 into the status byte. The 5 indicates the number of attempts that will be made to read from disk later. Multiple attempts will be made because the disk read might fail while the disk spins up. The 0 value is a sentinel value for whether or not the BIOS supports the extended interrupt 13h feature. This is an advanced, easier way to load lots of data from disk into memory, but not all BIOSs support it. The code above runs several different checks and if they all succeed, it stores a 1 where it had just stored a 0, indicating the extended read feature is supported. If any of those checks fails, it just jumps down a few lines and continues executing and will use the older method.

The next section of code loads the first sector of the OS into memory, using a different method depending on whether or not the extended read is supported. Here it is:

s0:0059 AttemptLoadFromDisk:                    ; CODE XREF: seg000:0048j
s0:0059                                         ; seg000:004Ej ...
s0:0059                 pushad                  ; Save all our registers for a little bit
s0:005B                 cmp     byte ptr [bp+10h], 0 ; Did our sentinel value get changed?
s0:005F                 jz      short InstallationFailed ; DATA XREF: seg000:0032r
s0:005F                                         ; Jump if Zero (ZF=1)
s0:0061                 push    large 0         ; LBA of 0
s0:0067                 push    large dword ptr [bp+8] ; DATA XREF: seg000:00E5r
s0:0067                                         ; seg000:0125r
s0:0067                                         ; Transfer buffer
s0:0067                                         ;    This is also the LBA of first absolute sector
s0:0067                                         ;    in the MBR partition record
s0:006B                 push    0               ; Transfer buffer
s0:006E                 push    7C00h           ; Number of blocks
s0:006E                                         ;    Note that only the first byte is relevant,
s0:006E                                         ;    and the second is ignored, so we are only
s0:006E                                         ;    reading 7Ch
s0:0071                 push    1               ; Reserved
s0:0074                 push    10h             ; Packet is size 10h
s0:0077                 mov     ah, 42h ; 'B'
s0:0079                 mov     dl, [bp+0]      ; Drive number
s0:007C                 mov     si, sp          ; Point to the address packet we just made
s0:007E                 int     13h             ; DISK - Extended Read
s0:007E                                         ;
s0:007E                                         ;    Reads DS:SI into a disk appress packet
s0:007E                                         ;      a disk address packet is:
s0:007E                                         ;      00 BYTE: Size of packet (10h or 18h)
s0:007E                                         ;      01 BYTE: Reserved
s0:007E                                         ;      02 WORD: Number of blocks to transfer
s0:007E                                         ;      04 DWORD: Transfer buffer
s0:007E                                         ;      08 QWORD: Starting absolute block number (LBA)
s0:007E                                         ;      10 QWORD: 64-bit flat address of transfer buffer (optional, used if the DWORD at 04 is FFFFh:FFFFh)
s0:007E                                         ;
s0:007E                                         ;    CF cleared if successful
s0:007E                                         ;    AH = 0 on success
s0:0080                 lahf                    ; Preserve the flags for a second
s0:0081                 add     sp, 10h         ; Pop the address packet we were using off the stack
s0:0084                 sahf                    ; Store AH into Flags Register
s0:0085                 jmp     short PostDiskReadState ; Jump
s0:0087 ; ---------------------------------------------------------------------------
s0:0087
s0:0087 InstallationFailed:                     ; CODE XREF: seg000:005Fj
s0:0087                 mov     ax, 201h        ; The extended read interrupt is not installed,
s0:0087                                         ;    so use the legacy version
s0:0087                                         ; AH = 2 (Disk read sectors into memory)
s0:0087                                         ; AL = 1 (Read 1 sector)
s0:008A                 mov     bx, 7C00h       ; This is the destination buffer
s0:008D                 mov     dl, [bp+0]      ; Drive number
s0:0090                 mov     dh, [bp+1]      ; These 3 bytes are a CHS structure
s0:0093                 mov     cl, [bp+2]
s0:0096                 mov     ch, [bp+3]
s0:0099                 int     13h             ; DISK - READ SECTORS INTO MEMORY
s0:0099                                         ; AL = number of sectors to read, CH = track, CL = sector
s0:0099                                         ; DH = head, DL = drive, ES:BX -> buffer to fill
s0:0099                                         ; Return: CF set on error, AH = status, AL = number of sectors read

Right away, a comparison is done against the sentinel value. If it is 0 (indicating no extended read), a jump is taken to the InstallationFailed label. If the extended read is supported, an “address packet” is set up for the interrupt and then the int 13h call is made, performing the read. This was actually a pretty tricky section to figure out, mostly because I found all the documentation about address packets was pretty confusing. After the extended read is completed, the code jumps to the PostDiskReadState location. I expect there are a few errors in my comments about the address packet, which I might try to figure out more about later.

Both the extended read and the non-extended read code do essentially the same thing though. They load the first sector of the bootable partition into memory at 0000h:7C00h. This will most likely be the operating system’s loader which will get things started up properly. Before we jump to the OS though, first we have a little bit of maintenance to do, to make sure we are set up and good to go.

After the disk reads are done, we need to make sure that everything succeeded, which is what this block of code does:

s0:009B PostDiskReadState:                      ; CODE XREF: seg000:0085j
s0:009B                 popad                   ; Restore all our registers
s0:009D                 jnb     short DiskReadSuccess ; Jump if CF = 0
s0:009D                                         ;    i.e. The interrupt we just executed (either one)
s0:009D                                         ;    just succeeded.
s0:009F                 dec     byte ptr [bp+11h] ; Remember this was set to 5 before?
s0:009F                                         ;    This is looping and trying the disk several times,
s0:009F                                         ;    (it might have failed while the disk spun up)
s0:00A2                 jnz     short ReattemptDiskRead ; Jump if Not Zero (ZF=0)
s0:00A4                 cmp     byte ptr [bp+0], 80h ; 'Ç' ; Is this drive letter 80h, i.e. the
s0:00A4                                                    ; first hard drive?
s0:00A8                 jz      PrintErrorLoadingOperatingSystem ; Jump if Zero (ZF=1)
s0:00AC                 mov     dl, 80h ; 'Ç'   ; Re-try on the first hard drive
s0:00AE                 jmp     short FoundBootableEntry ; Jump
s0:00B0 ; ---------------------------------------------------------------------------
s0:00B0
s0:00B0 ReattemptDiskRead:                      ; CODE XREF: seg000:00A2j
s0:00B0                 push    bp
s0:00B1                 xor     ah, ah          ; Logical Exclusive OR
s0:00B3                 mov     dl, [bp+0]
s0:00B6                 int     13h             ; DISK - RESET DISK SYSTEM
s0:00B6                                         ; DL = drive (if bit 7 is set both hard disks and
s0:00B6                                         ;   floppy disks reset)
s0:00B6                                         ;
s0:00B6                                         ; This is important so we can try the read again
s0:00B8                 pop     bp
s0:00B9                 jmp     short AttemptLoadFromDisk ; Jump

For both style of disk reads, if the operation succeeded, the carry flag will be cleared. As such, there is a JNB instruction that is taken if the load succeeded and jumps to the DiskReadSuccess location. If not, the counter we previously set to 5 is decremented. Remember how I talked about that the disk read might fail sometimes? This code is taking into account the drive being busy, not being spun up, or any other reason by just re-trying a few times. If however, it has failed after the 5 attempts, something is wrong. A comparison is then made to see if we are on the first hard drive by comparing the drive letter we wrote to [BP+0] with 80h. If it is, there is a problem loading the OS, so we print an error message. If not, we change the DL register to 80h, indicating the first hard drive, and try the whole process again.

The ReattemptDiskRead code is pretty straightforward. All it does is resets the disk system and jumps back to the AttemptLoadFromDisk location. Pretty simple, huh?

Hopefully the disk read will succeed though, and the code will get to the DiskReadSuccess location. We are very close to actually jumping to the OS in that case. Here is the code:

s0:00BB DiskReadSuccess:                        ; CODE XREF: seg000:009Dj
s0:00BB                 cmp     word ptr ds:7DFEh, 0AA55h ; We just loaded new code to 7C00h. Check
s0:00BB                                         ;    to see if it has the bootable signature AA55.
s0:00BB                                         ;    This signature indicates a VBR, which indicates
s0:00BB                                         ;    an operating system
s0:00C1                 jnz     short PrintMissingOperatingSystem ; The last two bytes are NOT AA55h
s0:00C1                                                           ; so there is no OS.
s0:00C1                                         ;    Print an error message.
s0:00C3                 push    word ptr [bp+0]
s0:00C6                 call    CheckKeyboardSystemFlag ; Call Procedure
s0:00C9                 jnz     short CheckForTPM ; Jump if Not Zero (ZF=0)
s0:00CB                 cli                     ; Disable interrupts for a while
s0:00CC                 mov     al, 0D1h ; '-'
s0:00CE                 out     64h, al         ; AT Keyboard controller 8042.
s0:00CE                                         ;    Enables writing the output port
s0:00D0                 call    CheckKeyboardSystemFlag ; Call Procedure
s0:00D3                 mov     al, 0DFh ; '¯'
s0:00D5                 out     60h, al         ; AT Keyboard controller 8042.
s0:00D5                                         ;    Enables writing to the status register
s0:00D7                 call    CheckKeyboardSystemFlag ; Call Procedure
s0:00DA                 mov     al, 0FFh        ; Enable A20 memory line
s0:00DC                 out     64h, al         ; AT Keyboard controller 8042.
s0:00DC                                         ; Reset the keyboard and start internal diagnostics
s0:00DE                 call    CheckKeyboardSystemFlag ; Call Procedure
s0:00E1                 sti                     ; Enable interrupts
s0:0156 ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
s0:0156
s0:0156
s0:0156 CheckKeyboardSystemFlag proc near       ; CODE XREF: seg000:00C6p
s0:0156                                         ; seg000:00D0p ...
s0:0156                 sub     cx, cx          ; CX = 0
s0:0158
s0:0158 CheckByte2:                             ; CODE XREF: CheckKeyboardSystemFlag+8j
s0:0158                 in      al, 64h         ; AT Keyboard controller 8042.
s0:015A                 jmp     short $+2       ; Jump
s0:015C                 and     al, 2           ; Logical AND
s0:015E                 loopne  CheckByte2      ; Loop while rCX != 0 and ZF=0
s0:0160                 and     al, 2           ; Logical AND
s0:0162                 retn                    ; Return Near from Procedure
s0:0162 CheckKeyboardSystemFlag endp

This code first checks to see that we did, in fact load an OS and not just some garbage into memory by checking for the AA55h signature. If it is not there, we print an error message. Otherwise, we’re going to fiddle with the keyboard controller a bit. This code makes several calls to the CheckKeyboardSystemFlag function, which basically loops until the keyboard controller is ready to talk to to the CPU. I’m a little fuzzy on what the output to the ports is doing, but I’m pretty sure that it is enabling the A20 address line, which enables larger amounts of memory to be used. It’s a pretty common task and there are write-ups all over the Internet, so I won’t go into it.

After the MBR is done fiddling with the keyboard controller, it decides to check for a Trusted Platform Module. The TPM is used to do several security related things, such as for Windows BitLocker encryption. There is a lot of complex documentation, so after I figured out that this was TPM code, I decided not to investigate it further. It is listed below:

s0:00E2 CheckForTPM:                            ; CODE XREF: seg000:00C9j
s0:00E2                 mov     ax, 0BB00h
s0:00E5                 int     1Ah
s0:00E7                 and     eax, eax        ; Logical AND
s0:00EA                 jnz     short JumpToLoadedMemory ; Jump if Not Zero (ZF=0)
s0:00EC                 cmp     ebx, 41504354h  ; Compare Two Operands
s0:00F3                 jnz     short JumpToLoadedMemory ; Jump if Not Zero (ZF=0)
s0:00F5                 cmp     cx, 102h        ; Compare Two Operands
s0:00F9                 jb      short JumpToLoadedMemory ; Jump if Below (CF=1)
s0:00FB                 push    large 0BB07h
s0:0101                 push    large 200h
s0:0107                 push    large 8
s0:010D                 push    ebx
s0:010F                 push    ebx
s0:0111                 push    ebp
s0:0113                 push    large 0
s0:0119                 push    large 7C00h
s0:011F                 popad                   ; Pop all General Registers (use32)
s0:0121                 push    0
s0:0124                 pop     es
s0:0125                 int     1Ah             ; This makes a call to the TPM

The code first checks for the presence of a TPM module. If it is not there, it jumps to the JumpToLoadedMemory location, otherwise it makes a call to the TPM.

Well, ladies and gentlement, thanks for sticking with me. After all that, we are finally ready to jump to the operating system that we loaded into memory. It’s very simple, so without further adieu:

s0:0127 JumpToLoadedMemory:                     ; CODE XREF: seg000:00EAj
s0:0127                                         ; seg000:00F3j ...
s0:0127                 pop     dx
s0:0128                 xor     dh, dh          ; Logical Exclusive OR
s0:012A                 jmp     far ptr 0:7C00h ; Jump to the code we have loaded

That’s it?! Yup, that’s it. Anti-climactic, though I guess Master Boot Records aren’t supposed to be entertaining.

There is some more code that I didn’t talk about yet, because it has to do with printing the error messages out. I’m not going to explain it here, since I’m already over 3000 words and I’m sure you’re sick of reading. Here it is:

s0:0131 PrintMissingOperatingSystem:            ; CODE XREF: seg000:00C1j
s0:0131                 mov     al, ds:7B7h
s0:0134                 jmp     short DisplayErrorMessage ; Jump
s0:0136 ; ---------------------------------------------------------------------------
s0:0136
s0:0136 PrintErrorLoadingOperatingSystem:       ; CODE XREF: seg000:00A8j
s0:0136                 mov     al, ds:7B6h
s0:0139                 jmp     short DisplayErrorMessage ; Jump
s0:013B ; ---------------------------------------------------------------------------
s0:013B
s0:013B PrintInvalidPartitionTable:             ; CODE XREF: seg000:0029j
s0:013B                 mov     al, ds:7B5h
s0:013E
s0:013E DisplayErrorMessage:                    ; CODE XREF: seg000:0134j
s0:013E                                         ; seg000:0139j
s0:013E                 xor     ah, ah          ; Clear out the high byte of the AX register.
s0:0140                 add     ax, 700h        ; We now point to 700h + whatever offset we were given
s0:0140                                         ;    above.
s0:0143                 mov     si, ax
s0:0145
s0:0145 PrintErrorStringLoop:                   ; CODE XREF: seg000:0151j
s0:0145                 lodsb                   ; Load byte at DS:SI into AL
s0:0146                 cmp     al, 0           ; Is the next byte 0? We're looking at a 0 terminated
s0:0146                                         ;     string, so this is important.
s0:0148                 jz      short HaltSystem ; Jump if Zero (ZF=1)
s0:014A                 mov     bx, 7
s0:014D                 mov     ah, 0Eh
s0:014F                 int     10h             ; - VIDEO - WRITE CHARACTER AND ADVANCE CURSOR (TTY WRITE)
s0:014F                                         ; AL = character, BH = display page (alpha modes)
s0:014F                                         ; BL = foreground color (graphics modes)
s0:0151                 jmp     short PrintErrorStringLoop ; Jump
s0:0153 ; ---------------------------------------------------------------------------
s0:0153
s0:0153 HaltSystem:                             ; CODE XREF: seg000:0148j
s0:0153                                         ; seg000:0154j
s0:0153                 hlt                     ; This stops the computer.
s0:0154                 jmp     short HaltSystem ; Jump
s0:0156
s0:0162 ; ---------------------------------------------------------------------------
s0:0163 aInvalidPartiti db 'Invalid partition table',0
s0:017B aErrorLoadingOp db 'Error loading operating system',0
s0:019A aMissingOperati db 'Missing operating system',0
s0:01B3                 db    0
s0:01B4                 db    0
s0:01B5                 db  63h ; c             ; Redirect to the error message at 63h,
s0:01B5                                         ;    i.e. "Invalid Partition Table"
s0:01B6                 db  7Bh ; {             ; Redirect to the error message at 7Bh,
s0:01B6                                         ;    i.e. "Error loading operating system"
s0:01B7                 db  9Ah ; Ü             ; Redirect to the error message at 9Ah,
s0:01B7                                         ;    i.e. "Missing operating system"

I realize that a blog post is a pretty difficult way to explain an RE task like this well. As such, I’m going to make my IDA Pro database available for download here. If you don’t have IDA, there is a free version (which I use) available here. It is missing quite a few features, but the price is right, and for work like this (16-bit MBR code), a lot of the newer features aren’t even relevant.

If you’re interested, you could do this analysis on your own computer. Depending on your computer’s manufacturer, you might have some small differences, but those are what makes it fun, right? To get started, get the trial of Hex Workshop, extract the MBR (it’s the first sector on the disk), then use the free version of IDA Pro to examine it. Happy hunting!

Yesterday, I submitted a paper to the 2010 ACM DIM (Digital Identity Management) workshop. My paper was  about a project I have been working on the last semester. I used several different things in my projects, some of which I have written about before. Rather than try to explain the project now, I will show you the abstract. I’ll post the full paper once it is either officially accepted or rejected.

PEAR: A Hardware Based Protocol Authentication System

Abstract

As users have to manage an increasing number of ac-

counts, they have to balance password security and pass-

word usability. As such, many users use insecure pass-

words resulting in their accounts and data being vulnerable

to unauthorized accesses. In this paper, we present Phys-

ically Enhanced Authentication Ring, or PEAR, a system

that alleviates this problem. We leverage Physically Un-

clonable Functions (PUF) to create unclonable hardware

devices, which users use to authenticate. Using a hardware

device, our system uses zero-knowledge proofs, which pro-

vide better security than traditional passwords, yet users

must only enter a simple PIN. As such, our system is very

usable and imposes little to no burden on end users and

service providers. We present transaction levels on top of

PEAR of as an extension and then discuss some other work

that could be done in the future.

Bill Buzbee's homemade CPU, which provided some inspiration for me.

Luckily for me though, my research group started to do some work with FPGA’s, so I was able to get some hands on experience with them. Despite having the needed tools though, I was still dragging my feet on doing any work. Well, a few days ago, I got re-inspired when I found a website about a guy called Bill Buzbee who built his own (and in my opinion) pretty complex CPU. It has all sorts of neat features such as paging and interrupts. Well, that was the inspiration I needed and now, a few days later, I’ve actually got some progress worth mentioning.

I’ve tried designing a CPU several times before, either on paper or just trying to hack out some Verilog code to no avail. I think the main problem is that I haven’t had any clear direction or plan. Because of this, I decided to make a high-level block diagram of the architecture on the computer before I wrote any code. So far, this seems to pretty helpful, as I’ve had several *doh* moments already where I found an error in my design. Doing it on computer (hurray for Visio!) makes it a lot easier than working with pencil and paper too.

As I started my design, I tried to copy what I already knew a little about. In a computer architecture class I took, we had studied the MIPS architecture, so I tried to copy their style of pipelining, though I in no way claim my sketches were anything close to a MIPS design. I quickly figured out pipelining would be pretty difficult for me at this point, so I dropped that idea for now.

After I had revised my drawing a little, I noticed that the memory was being referenced in two separate places in the CPU (see diagram). So this meant that I could do one of two things:

• Revise the whole design to only reference memory in one place, retaining the Von Neumann structure.
• Use two separate memory modules, giving me a Harvard architecture.

I thought it might be fun to try something new (and also not redo the drawing again), so I decided to go with the Harvard style and split the data and instruction memory into separate chips. I might regret this later, but we’ll see how it goes for now.

Here is the initial plan for the CPU. The red parts will be external memory chips. The whole second ALU business may or may not be implemented in the first go-around.

Lots of designs are using parallelism today, so of course I didn’t want to be left out. As such, I’m going to try to add a second ALU into my design. This would allow me to do two computations at once. This will probably also make the design a lot more difficult to complete as well. I’m going to add a few restrictions to this second ALU so that it will be easier to work with though, such as it will only operate on certain source and destination registers, unlike the first ALU, which should be able to use most any register available. If this part gets too difficult to deal with, I might drop it, but I am going to try to get it to work.

I haven’t yet decided whether I want to use 8/16/32 bits for addresses and data sizes, how many I/O ports to have, nor exactly how many registers the chip is going to have, but I don’t think that is really important yet. Right now, my layout is such that these choices don’t really matter yet. These issues shouldn’t really become an issue until after the instruction set is designed. One major problem I do see coming up is the implementation of the bi-directional buses on the FPGA. What I mean is that I will need tri-state outputs for the bus, but the FPGA can’t synthesize these internally. It can however, do tri-state outputs on the physical I/O pins. What this means is that I will have to physically wire the bus to various I/O pins on the FPGA, which will be a headache. If you know of an FPGA that can do tri-state logic internally, please leave me a comment!

At this point I have started to write some basic code for the chip. Specifically, I’m working on designing the registers and I/O port modules in Verilog. These seem pretty simple, but I’m making a big effort to actually write tests and make sure that they work properly. Hopefully this attempt will pan out better than my previous efforts!

These chips can make a whole CPU?!

I personally found Jim’s work so interesting because I have been toying around with designing a somewhat useful CPU myself, since I took a class on digital design. In that class, we built a simple computer that had 1 register, 4 bit (not byte) address and data bus, and only 7 instructions. It was an interesting exercise and very educational, but it couldn’t really do anything other than add small numbers together. I have made a few attempts at starting a design, but I usually got hung up on finding a balance between instruction set power, complexity, and size. It would be nice to be able to perform 32 bit vector math with all arguments in the instruction, but thats just not realistic for me at this point.

Seeing Jim’s work is pretty inspirational; maybe this semester I’ll get off my butt and start to work on my own computer. However, I don’t think I will use 74xx chips. FPGAs are very powerful tools, and since I’ve been using them for my research, I figure they will be the perfect way to start any work. I think the biggest thing is to just get started and stop thinking about starting.

P.S. Another interesting point of note is that Konrad Zuse, a German engineer, had built his own computer during World War 2, but instead of an electric clock, he used a crank as the clock! Pretty neat!

Propeller Time!

Anyways, at Christmas, I got a starter set for the Parallax Propeller microcontroller, an 8 core, 32-bit microcontroller. I really like to work with hardware and embedded type stuff, so I was really excited about this. I’ve played with AVR chips before, but this chip has a lot more power built-in, but it won’t require as much work as using an FPGA either.

Due to the nature of the Propeller, it can perform some really complex tasks. Since it’s 32 bits, it can easily handle some tasks, such as floating point division, that would be more difficult on other architectures. Not only that, but it has 8 ‘cores’! Each core, or ’cog,’ can run up to 80 MHz, has its own ALU (Arithmetic Logic Unit), counters, frequency, and video generators. In addition, each one can control every I/O pin. There is clearly a lot of power available here, but what would be a good starting point? Music of course!

I read an article a few weeks ago about music notes and their frequencies, and since each cog can generate a unique frequency, I thought it would be fun to make some music. I have a small speaker, so this would be a doable project. Since I’m just starting out, I decided to keep the design relatively simple. Here are a few things I decided I wanted to do:

• Be able to generate any note.
• Be able to use any I/O pin.
• Be able to play a chromatic scale (all notes, sharps, and flats on the scale).
• Be able to play a note for a specified time.
• Be able to play across multiple octaves.

I also decided to make some concessions, at least for now:

• No chord support initially.
• All multi-cog management must be handled by the user.
• Only quarter notes, eighth notes, sixteenth notes, thirty-second notes, and integer quantities of quarter notes can be played.
• A BPM (Beats Per Minute) of 120 (or some other constant) will have to be used.

The Propeller chip has to be programmed in its own language, called Spin, so I had to learn that before I could get started. I found it kind of strange, as its syntax is very different from C or Java. It took me a while, but I eventually managed to figure it out a little bit.

The first step was to be able to synthesize a tone. To do this, I would need to generate a specific frequency. To achieve this, I need to calculate how long of a delay to impose between osciallting the output of the I/O pin, i.e. the period. I then need to divide the clock frequency by the period to give me the proper delay. The code for this ends up looking like:

PUB generateFrequency(Pin, Frequency)
{{
  Given a frequency, specified in Hz,
  output that frequency on the I/O pin Pin.
}}
  DIRA[Pin]~~ ' Set it to output
  repeat      ' Endless loop
    !OUTA[Pin] ' Oscillate the I/O pin
    waitcnt(cnt + CLKFREQ / Frequency) ' Wait for the specified time

Who needs a piano? I have a half-watt speaker and a microcontroller!

If you have used the Propeller before, you probably know this section could be re-written to improve performance, using the built-in counters, but I didn’t really figure those out yet. Maybe I’ll optimize this later, but it works, so for now it’s fine.

Now that I can generate an arbitrary frequency, I can play any note I want. However, the code above simply loops endlessly, playing the same note. The next step is to be able to play a note for a specified period of time. This is where the fun will start, since I can use one cog to play the notes and another master cog to manage all the timings.

To achieve this, I need to calculate how long to play the note, get an available cog to start playing the note, wait for the note to play, then stop that cog. Creating a new cog was a little confusing, since I had to provide stack space to the cog, but there are a few examples of how to do this, so I managed to figure it out. Here is what I came up with:

PUB playNote(Note, Pin, Length) | WaitLength
  {{ playNote:
        Plays a given note for a specified number
        of beats.

        Note: Length must be given in fraction form,
        not decimal form

        Note: This method assumes Length is given
        in terms of beats, not measures, where a
        beat is a quarter note.
  }}
  Cog := cognew(generateFrequency(Pin, Note), @StackSpace) ' Remember which cog was being used
  WaitLength := calculateWait(Length) ' How long do we wait?
  waitcnt(cnt + WaitLength) ' Wait for the note to end
  cogstop(Cog)  ' Stop playing the note

A problem I see that might arise is if it takes longer to calculate the wait length than the note is supposed to be playing for. I don’t think this will be a big problem though since the cog is pretty quick and the notes aren’t really that fast, so for now I think it will be OK.

The biggest difficulty I had was figuring out exactly how long to play the note for. After working on it for a while, I did a little unit elimination to figure it out. Namely, CLK pulses/second * 60 seconds/1 minute * 1 minute / 120 beats * 1 beat = CLK/2 pulses / beat. That will give the length of time for a quarter note. After that, multiply that number by the number of beats to play.

PUB calculateWait(Length) | BaseLength
  ' A quarter note is one beat long
  if Length == 1/8              ' Thirty-Second Note
    return CLKFREQ * 60 / BPM / 8
  elseif Length == 1/4          ' Sixteenth Note
    return CLKFREQ * 60 / BPM / 4
  elseif Length == 1/2          ' Eight Note
    return CLKFREQ * 60 / BPM / 2
  elseif Length == 1            ' Quarter Note
    return CLKFREQ * 60 / BPM
  elseif Length > 1             ' Multiple Quarter Notes
    return CLKFREQ * 60 / BPM * Length

I ran into some problems with division, so I put anything shorter than a quarter note into an if statement. Anything longer than a quarter note can be handled normally since its length is greater than one.

Putting those three sections of code together, I can now play a chromatic scale like so:

CON
  ' Define constants for each note
  ANote = 220
  AShNote = 233
  BNote = 247
  CNote= 261
  CShNote = 277
  DNote = 293
  DshNote = 311
  ENote = 329
  FNote = 349
  FShNote = 367
  GNote = 392
  GShNote = 415
PUB main
  DIRA~~ ' Configure the I/O as output
  ' Play the chromatic scales as eighth notes, finishing with quarter note
  playNote(CNote, 0, 1/2)
  playNote(CShNote, 0, 1/2)
  playNote(DNote, 0, 1/2)
  playNote(DShNote, 0, 1/2)
  playNote(ENote, 0, 1/2)
  playNote(FShNote, 0, 1/2)
  playNote(GNote, 0, 1/2)
  playNote(GShNote, 0, 1/2)
  playNote(ANote * 2, 0, 1/2) ' Multiply the note by 2 to go up an octave
  playNote(AShNote * 2, 0, 1/2)
  playNote(BNote * 2, 0, 1/2)
  playNote(CNote * 2, 0, 1

This code defines the proper frequencies for each musical note on the scale as constants. Then to switch octaves, I can just multiply or divide the note by a constant to change the octave. Pretty cool huh?

Doing this music program was a lot of fun. I think it has a lot of potential to be improved too. I played around trying to play chords to no avail, but I think that might be because my speaker is so crappy. Ideally, I could write a program to automatically do chords and all the cog management for me. I think the next step will be to program some common songs into the Propeller. I always have been a fan of “Twinkle, Twinkle,” so maybe that’s where I’ll start…

Happy new year everyone!

A PUF is a device that when given a “challenge,” will always generate the same “response.” In this way, an authority can give a user a challenge and, based on whether or not he produces the correct response, can determine his identity. Generating responses to challenges is also very fast; much faster than systems using exponents and modulus to prove identities through advanced cryptography. These responses are actually hardwired into the PUF device due to the internal circuitry. Since generating a response takes very little computer power and energy, PUFs are a very viable way for low-power and mobile devices to securely identify themselves.

The idea of a PUF might sound interesting, but wouldn’t it be easy to simply make a copy of a PUF, record several responses, and then impersonate the PUF? A good idea, but PUFs can deal with this easily. You see, Physically Unclonable Functions cannot actually be copied accurately. That is because there is some element of randomness introduced into the PUF so that every PUF gives a different response to the same challenge. The most common way to introduce this randomness is to use manufacturing inconsistencies. For example, you may design the PUF to have 100 nm long wires connecting the internals of the PUF, but if the manufacturing equipment has a tolerance of even 5%, the wire could be 95 nm, 105 nm, or anywhere between those two numbers. Since the tolerance is uncontrollable, two PUFs produced on the same manufacturing line using the same design files will provide very different responses to the same challenges. PUFs are designed to leverage these inconsistencies and amplify them so that even small inconsistencies will cause large differences in the output from all other PUFs.

PUFs are a very cool technology, but as for my first foray into Verilog and FPGA design, they were quite difficult. There are several different designs of PUFs, so first I had to decide which would be the best design to implement. All of them were about the same difficulty, so my group and I decided to implement a ring-oscillator based PUF, as presented by Suh and Devadas of Cornell. At first, it seemed easy enough to implement, but the more I coded and the closer my deadline got, the more difficulty I encountered. Namely, I had big problems with the design software thinking it knew what I wanted and removing large pieces of my code. Normally, it would have been doing me a favor, but in this case I did not want some specific optimizations and it took me forever to notice this was happening. I had some trouble learning and understanding some aspects of Verilog, but this was to be expected, since I hadn’t ever used it prior to this project.

As of now, the PUF device has been successfully implemented and my team has started to integrate it into the rest of our project. I won’t go into the rest of the project here, but when the paper is published (or not), I’ll upload a copy of the final paper, which you can then read for yourself. Or maybe I’ll give a summary in another post.  We’ll see I suppose!

I’d highly recommend reading the AnandTech article since it has a lot better description (and pictures) than I could do, but the one thing that I’m really excited about is the new 32nm Gulftown chips. There supposed to have 6 cores and will come in 2010. Even better, they will drop right into my X58 motherboard after a quick BIOS update. That will save me a lot of money since I won’t have to buy a new motherboard.

Don’t get me wrong, I love my quad-core i7 cpu, but 6 cores is better than 4, right?

This is Xilinix Spartan FPGA, the kind I'm using.

This was my first foray into FPGAs and it drove me crazy getting my tools all set up properly. I thought I’d post some thoughts.

To get started with FPGAs, my research group purchased the Xilinx Spartan-3AN Starter Kit. We chose this kit because the board it comes with has all sorts of useful peripherals, such as USB, RS-232, Ethernet, VGA outputs and an LCD character screen. All these extras will really help to speed up development and make learning a lot easier.

Last spring, I had decided I wanted to give FPGAs a try, so I purchased a book called “FPGA Prototyping by Verilog Examples“. This book is actually really helpful now since it uses the exact same chip that my board comes with. It has tons of sample code and examples, and I think it’s really going to help me learn.

I was really excited when I first got this board, but that’s always when the problems start don’t they? Well, firstly, the software that came with the board (an IDE and Xilinx utilities) was version 9.1, but the current version is 11.1. Ok, I’m sure I won’t be able to really tell a difference anyways since I’m just starting out.

The software only runs on Windows XP and RHEL officially. I recently installed Windows 7 and Arch Linux on my computer, so this might cause problems. Well, it did. The software refused to install properly on Windows 7, so I tried it on Linux. The software installed fine on Linux, but I couldn’t get the drivers to connect tot he chip itself to work. I worked on this problem to no avail for about 10 hours, absolutely drove me crazy! But what good is software if it can’t talk to the board? Not much. As such, I’m now using Windows XP on my Mac through Boot Camp. Turns out when they say Windows XP and RHEL only, they really do mean only.

I can program a little Abel, but I’ve never actually used Verilog before. I’m pretty excited to learn a new language though, especially an HDL (Hardware Description Language) since it’s completely different from what I normally work with.

Maybe you’re asking, what did I do for hello world in a circuit? I did a simple 1 bit comparator! Basically, when 1 of 2 DIP switches is on, an LED is on. If both switches are off, the LED is off. This was actually kind of tricky to do since I had to find the correct pin numbers of the FPGA to communicate with. Luckily, there was a really good starter manual available that mapped all the LEDs to their corresponding pins.

I think starting to work with FPGAs will be a really exciting project and probably teach me a lot along the way. Once my research group moves a little farther along, I’ll post some updates about how we’re using the FPGA and how work is progressing.

These rhinos are hot on the trail of some cryptography!

I find the task very interesting, but I quickly got tired of coding even a 10-letter “sentence”. Then I thought to myself, wait, I can program! This specifically seems like something that could quickly be done with a Python script. So I decided to spend a little time typing, and 5 minutes later, no more ciphering by hand! Below are the results for your own amusement!

For my assignment, we were told to use the Beaufort cipher, which is similar to the Vigenere cipher, both of which are several hundred years old. The Beaufort cipher takes some plaintext M and a key K of length t, and then performs the mathematical operation C[i]=(m[i] + k[i mod t]) mod 26 for each letter i of the plaintext. An interesting fact is that this operation will both encrypt and decrypt, making it a reciprocal cipher.

Anyways, here is the Python code that I wrote to perform encryption/decryption:

[code language="python"]

k = [10,4,24]
t = len(k)

def asint(theChar):
    return ord(theChar)-ord('A')

def asletter(theNum):
    return chr(theNum+ord('A'))

def applyBeaufort(plaintext):
    results = []
    for i in range(len(plaintext)):
        results += [asletter((k[i % t] - asint(plaintext[i])) % 26)]
    return results

[/code]

That code isn’t bulletproof, obviously, and makes a few assumptions:

• All text will be entered as a capital letter.
• The key will be specified as a list of numbers.

These two points aren’t really that hard to correct, but they’re the 20% of work that will take 80% to do right. I just wanted to give you a quick sample.

Want to see if it works? Alright, here you go!

About to encrypt!
Using plaintext: RANTSRAMBLESANDRHINOS
['T', 'E', 'L', 'R', 'M', 'H', 'K', 'S', 'X', 'Z', 'A', 'G', 'K', 'R', 'V', 'T', 'X', 'Q', 'X', 'Q', 'G']
-------
About to decipher!
['R', 'A', 'N', 'T', 'S', 'R', 'A', 'M', 'B', 'L', 'E', 'S', 'A', 'N', 'D', 'R', 'H', 'I', 'N', 'O', 'S']

That’s all for now, I hope you enjoyed this little tidbit about the Beaufort cipher and maybe even find the code snippet useful!

My new distro of choice

Well, that’s when I discovered the wonderful Arch Linux. I don’t plan on looking back.

What really turned me on to Arch Linux at first was its mission statement, aka The Arch Way.

Arch Linux defines simplicity as a lightweight UNIX-like base structure without unnecessary additions, modifications, or complications, that allows an individual user to shape the system according to their own needs. In short; an elegant, minimalist approach.

I was still a little skeptical though, because I wanted to see how Arch is compared to other distributions. Well, Arch thought about this already. A wiki page is provided comparing and making a case for Arch versuses all the other big and a few small distros. It definately convinced me to at least TRY Arch.

Alright, Arch Linux seems like it won’t provide me with a bunch of features that I don’t want, but does this mean that I’ll have a hard time learning how to use and set it up properly? I consider myself a pretty competent Linux user, but I definately don’t know everything that is needed to set up a whole operating system. Good documentation is invaluable and is key for users to learn how to use your project. On the opposite hand, bad documentation is almost worse than no documentation. Jeff Atwood has a few words on this, which he calls “undocumentation”.

After a quick look around Arch’s website, I found not one, but TWO installation guides for the distribution. There was a beginner guide as well as an official guide, with the former holding your hand through installation and the latter explaining a lot more details but expecting you to know what to do with them. I found it helpful to work through both guides simultaneously, as they were both very complemenetary.

Since Arch wants you to install everything yourself, once you’re done with the basic installation, you are presented with just a command prompt. No Gnome, no KDE, no X. Oh boy, I’ve had bad experiences messing around with X before, so I was a little worried about this step. The fact that I have 2 monitors of different sizes didn’t really make things any better (actually it made it MUCH harder).

Luckily, the install guide covered this topic pretty well. I did have to search forums and the wiki quite a bit since I had a somewhat unique setup with dual monitors and I’d never configured X before. This was definately the hardest step of the installation, but after I got it all set up properly, I have a Gnome installation with no clutter and customized just the way I want.

Another potential problem that I was worried about was how software management would be. Since Arch is a minimalist, I was concerned that managing packages might fall entirely on my shoulders. If this was the case, I don’t think I would have used Arch, since while it gives me more control, I’d much rather just have a package manager handle everything for me automatically. I was very pleased to see that Arch has the pacman package manager. Installing software is as simple as ‘pacman -S package’. The repositories are also current and seem to have a very large selection of software available.

I’m still getting my system setup to my liking, but so far, I’ve liked nearly everything I’ve seen about Arch. This is probably due to the fact that Arch really just provides powerful tools for you to build a Linux system to fit your exact needs. I’d highly recommend it to you if you’re looking for a new distro (or even if you’re not!).