PAD


Pilot Authentication Device

Final Report

URL: http://www.hedge.net/fields/projects/PAD/report.html
by Adam Fields
for CS4995, Internet Security
Proposal: http://www.hedge.net/fields/projects/PAD/proposal.html

Choice of environments

Since the Pilot is a relatively new platform, the major obstacle to be overcome with this project has been finding a development environment to work in. The only offical such environment is the CodeWarrior platform for Macintosh, which is infeasible for me as I have neither a Macintosh nor the $300 with which to purchase the CodeWarrior package. the CodeWarrior for Pilot for Windows is currently in beta testing and not yet available as I'd hoped. Working in a non-USR-sanctioned development environment has had two large drawbacks: 1) There is not yet any interface to the built-in TCP/IP stack, wiping out the possibility of doing direct network communications between the desktop and the Pilot, as I'd originally planned, and 2) Most of the third-party development environments are extremely poorly documented, if at all, and sample code is scarce and hard to come by. This problem was minimized by using a commerical third-party language instead of a freeware package.

Environments that exist:

  1. asdk: ASDK is the Alternate Software Development Kit for Pilot. ASDK includes PILA, the pilot assembler, which translates 68000 assembly into .prc files for the Pilot. I discarded this environment fairly quickly, as it's been a very long time since I've done any assembly, and never on the Macintosh. This was just too daunting to even consider on any kind of a schedule.
  2. gcc for win32 for pilot: This looked the most promising, as C is one of my languages of choice, the Macintosh development environment uses C, and much of the source code available on the web is written in C. However, the only distribution I could track down (after many broken links) seemed to be missing a few key files and would not compile a running application.
  3. JUMP: This was my second choice. JUMP is a backend translator that takes Java code (sprinkled with PalmOS API calls) as input and generates 68000 assembly that can be fed into PILA. I have done Java programming in the past, so this seemed like a good choice. Unfortunately, after a week or two and some unrelated sample programs, I realized that Java has no unsigned numeric variables, and thus no way to do bit operations. At this point, the clock was starting to tick, and I had no intention of trying to piece together Java classes to treat signed variables as unsigned. I moved on.
  4. CASL: I had originally not considered CASL (Compact Application Solutions Language) as a good candidate for doing real development on the Pilot, as it's a scripting language and is fairly limited in it's numeric function. However, failing with all of the other environments, I sent some mail to the author of CASL, who informed me of the binary array variable in CASL. I would have to write some functions to treat groups of 8-bit fields as 32-bit words, but that didn't seem so difficult. And indeed, it only took a few days to get those functions completely finished and tested. The current version of PAD, described in the next section, is implemented as a CASL script. This is good because it works. This is bad because it works slowly. The lack of speed is partially because the Pilot has a relatively basic processor (compared to any modern desktop), but also because of the inherent overhead in any scripting language. I hope to one day translate it to C, but as this project is as much about proof of concept as it is about workable final product, CASL will have to do for now.

    Other tools

    PAD Documentation

    The Pilot Authentication Device consists of three programs - a desktop server, a desktop password generator, and a PalmPilot client. The first step is to compile the two server programs, "pad.c" and "padpwd.c", using standard unix make. These programs are written for SunOS4, though it should be fairly easy to port to your favorite flavor, as the only thing that should be sun4 specific is the file access. Then, use the padpwd program (syntax: "padpwd ") to generate a password file of the same name as . This file must exist before running the program (use "touch " if it does not exist), and it will blindly overwrite whatever filename you give it. Be careful!. The program will print the password to standard out, in the format in which it must be entered into the Pilot, and save it to disk in binary form. You should remember your password. In a real environment, this file should be encrypted to prevent access to your password, but that has not been done for this project. After the password is generated, the pad.prc file (and the CASLrt.prc file, if necessary) should be installed on the Pilot using the standard mechanism. Then, the authentication protocol can be run. The protocol is as follows:
    1. The server generates a random challenge + datestamp, appends the private key of the user, and hashes the concatenation with SHA. Challenge + Datestamp, 64 bits + Key, 64 bits = 128 bits. These 128 bits are expanded to 512 bits, which equals 1 SHA message block with no padding. After printing the challenge, the program will prompt for the five response blocks, as generated by thte Pilot. (syntax: "pad ")
    2. The user enters in his/her password and the challenge, and the Pilot computes the hashed response. This computation takes roughly 2 minutes on the PalmPilot. During this step, the Pilot may timeout and power off, depending on the settings, but when the green power button is pressed again, the response will still be on the screen.
    3. The server checks the response against its own response and grants or denies access.

    Technical details:

    • The SHA algorithm implemented is the unmodified NIST algorithm, meaning that the inital blocks are not bit-rotated before filling the array. This decision was made because of limitations in the Pilot program (explained shortly) on bit-rotation, and purely for the sake of speed. When coded in C, the modified algorithm should be used.
    • CASL does not have unsigned 32-bit integers, so an array of 4 8-bit bitfields was used to simulate them. CASL also does not have bit shifts or 32-bit add, so special-purpose functions were written to compute bit rotation and 32-bit add, taking 4-cell 8-bit fields as input and output and treating them as contiguous numbers.
    • The run time of the Pilot program was cut significantly after I realized that a lot of the computation time was being swallowed by performing 30 individual left-bit-rotations in a row. The bit-rotation function was written to do one rotate at a time with n iterations. I wrote a new function to do right rotations, changed the algorithm to 2 right-rotations, and it sped up a lot. This optimization is obviously not needed in C, which has bit shifts.
    • The random numbers generated for the password and challenge are probably not random enough to be secure. If this program is to be used for a real secure authentication, some package like "truerand" should be substituted. This should be fairly easy to accomplish and does not require modification of the pad.prc program.
    • The initial proposal calls for the Pilot to function as a "smartcard", but this goal has proven to be not possible, as there's no way to guarantee that any given Pilot containing information is the same Pilot which contained that information at any previous point. There is also no way to prevent information stored on the Pilot from being tampered with. Thus, the authentication is implemented using the Pilot as a cryptographic calculator. This function could be performed by any computer with the appropriate algorithm, but probably not on anything as small and general-purpose as the Pilot, which makes it uniquely suited for this task.

    Comments:


    As mentioned earlier, all i/o is user/screen. Ideally, this package should be incorporated into some sort of login process for online applications using the Pilot. Since TCP/IP support has only been added to the Pilot in the past two months and the TCP/IP SDK is not widely available, there is a dearth of applications, but this should change over the course of the next few months. This project is as much about demonstrating that the Pilot is capable of performing cryptographic algorithms in addition to the standard "data collection" programs. This program is somewhat slow, due to the fact that it is implemented in a scripting language instead of C (and thus required special-purpose functions to get around the limitations of the language), but several optimizations enabled me to cut the runtime of the Pilot program from an initial 5 minutes to just over 2 minutes. I have every reason to believe that recoding in C will cause substantial time savings. If the run time can be brought down to less than 30 seconds, I will have a product that could be used under everyday circumstances.

    Screen Shots