How To Break The Palm OS Password

by matt
darkstar labs
===================================
	

	Palm OS offers a built-in Security application which is used for the
legitimate user to protect and hide records from unauthorized users by
means of a password. In all basic built-in applications (Address, Date
Book, Memo Pad, and To Do List), individual records can be marked as
"Private" and will only be accessible if the correct password is entered.

    It is possible to obtain an encoded form of the password, determine
the actual password due to a weak, reversable encoding scheme, and access
a users private data. In order for this attack to be successful, the
attacker must have physical access to the target Palm device.

    The threat of physical attacks internal to a company is very real and
this advisory makes the point that security is not limited to the
network/internet arena. The private records often contain passwords,
financial data, and company confidential information. Our experience with
physical audits has revealed that most users of Palm or other portable
devices do not realize that their private information could possibly be
accessed by unauthorized users.

                                          
Overview:
	
    During the HotSync process, the Palm device sends an encoded form of
the password over the serial, IR, or network ports to the HotSync Manager
or HotSync Network Server on the desktop. The password is transmitted to
enable the Palm Desktop program to protect the users private records when
being accessed on the desktop machine. However, based on an encoding
scheme of XOR'ing against a constant block of data, the encoded password
is easily decoded into the actual ASCII version of the password. The
encoded block is also stored on the Palm device in the Unsaved Preferences
database, readable by any application on the Palm device.

    The transfer of a secret component (i.e. password), even if it is
encoded or obfuscated, over accessible buses (serial, IR, or network) is a
very risky design decision and is oftentimes considered a design flaw. It
is unfortunately common practice that applications choose to simply
obfuscate passwords instead of using encryption. Without proper encryption
methodologies in place, the task of determining the secret data is greatly
simplified as shown in this research.

    This advisory is an attempt to remind users and developers of the
common problem of storing secrets and the reliance on simple obfuscation.


Detailed Description:

    The password is set by the legitimate user with the Security
application. The maximum length of the ASCII password is 31 characters.
Regardless of the length of the ASCII password, the resultant encoded
block is always 32 bytes.

    It is possible to obtain the encoded password block in a number of ways:

    () Retrieve from the "Unsaved Preferences" database on the Palm device.
    () Monitor the serial or network traffic during an actual HotSync.
    () Imitate the initial HotSync negotiation sequence in order to obtain 
       the password (which is transmitted by the target device). This is 
       demonstrated in our proof-of-concept tool written for the PalmOS 
       platform.

    The Palm desktop software makes use of the Serial Link Protocol (SLP)
to transfer information between itself and the Palm device. Each SLP
packet consists of a packet header, client data of variable size, and a
packet footer [Palm OS Programmer's Companion, pg. 255]. During the
HotSync negotiation process, one particular SLP packet's client data
consists of a structure which contains the encoded password block (Figure
1).

    struct {
      UInt8 header[4];
      UInt8 exec_buf[6];
      Int32 userID; // 0
      Int32 viewerID; // 4
      Int32 lastSyncPC; // 8
      UInt8 successfulSyncDate[8]; // 12, time_t
      UInt8 lastSyncDate[8]; // 20, time_t
      UInt8 userLen; // 28
      UInt8 passwordLen; // 29
      UInt8 username[128]; // 30 -> userLen
      UInt8 password[128]; 
    };

    Figure 1: Structure sent during the HotSync process which contains the 
    encoded password block.

    Two methods are used to encode the ASCII password depending on its
length. For passwords of 4 characters or less, an index is calculated
based on the length of the password and the string is XOR'ed against a
32-byte constant block. For passwords greater than 4 characters, the
string is padded to 32 bytes and run through four rounds of a function
which XOR's against a 64-byte constant block. It is unknown why disparate
methods were implemented. By understanding the encoding schema used, it is
possible to essentially run the routines in reverse to decode the
password, as shown in our proof-of-concept tools. Details of each method
are described below.

    Neither encoding schema make use of the username, user ID, or unique
serial number of the Palm device. A common practice often used for
copy-protection purposes is to use a unique identifier as input into an
encoding or encryption algorithm, which PalmOS does not do. The resultant
encoded password block is completely independent of the Palm device used
and makes it easier to determine the original ASCII password from the
block.


Passwords of 4 characters or less:

    By comparing the encoded password blocks of various short length
passwords (Figure 2), it was determined that a 32-byte constant (Figure 3)  
was being XOR'ed against the ASCII password in the following fashion:

    56 8C D2 3E 99 4B 0F 88 09 02 13 45 07 04 13 44
    0C 08 13 5A 32 15 13 5D D2 17 EA D3 B5 DF 55 63

    Figure 2: Encoded password block of ASCII password 'test'


    09 02 13 45 07 04 13 44 0C 08 13 5A 32 15 13 5D 
    D2 17 EA D3 B5 DF 55 63 22 E9 A1 4A 99 4B 0F 88

    Figure 3: 32-byte constant block for use with passwords of length 4 
    characters or less

    Let A_j be the jth byte of A, the ASCII password
    Let B_k be the kth byte of B, the 32-byte constant block
    Let C_m be the mth byte of C, the encoded password block

    The starting index, i, into the constant block where the XOR'ing
should begin is calculated by the following:

    i = (A_0 + strlen(A)) % 32d;

    The encoded password block is then created:

         C_0 = A_0 XOR B_i
         C_1 = A_1 XOR B_i+1
         C_2 = A_2 XOR B_i+2
         C_3 = A_3 XOR B_i+3
         C_4 = B_i+4
             .
             .
             .
        C_31 = B_i+31 (wrapping around to the beginning of the constant 
                      block if necessary)

Example:  0x56 = 0x74 ('t') XOR 0x22
          0x8C = 0x65 ('e') XOR 0xE9
          0xD2 = 0x73 ('s') XOR 0xA1
          0x3E = 0x74 ('t') XOR 0x4A


Passwords greater than 4 characters:

    The encoding scheme for long length passwords (up to 31 characters in
length) is more complicated than for short length passwords, although it,
too, is reversable.

    First, the ASCII string is padded to 32 bytes in the following fashion:

    Let A_j be the jth byte of A, the ASCII password

    len = strlen(A);
    while (len < 32)
    {
       for (i = len; i < len * 2; ++i) 
          pass[i] = pass[i - len] + len; // increment each character by len

       len = len * 2;
    }

Example:  A_0 = 0x74 ('t')
          A_1 = 0x65 ('e')
          A_2 = 0x73 ('s')
          A_3 = 0x74 ('t')
          A_4 = 0x61 ('a')
          A_5 = 0x79
          A_6 = 0x6A
          A_7 = 0x78
          A_8 = 0x79
          A_9 = 0x66
         A_10 = 0x7E
              .
              .
              .

    The resultant 32-byte array, A, is then passed through four rounds of
a function which XOR's against a 64-byte constant (Figure 4):

    B1 56 35 1A 9C 98 80 84 37 A7 3D 61 7F 2E E8 76
    2A F2 A5 84 07 C7 EC 27 6F 7D 04 CD 52 1E CD 5B
    B3 29 76 66 D9 5E 4B CA 63 72 6F D2 FD 25 E6 7B
    C5 66 B3 D3 45 9A AF DA 29 86 22 6E B8 03 62 BC

    Figure 4: 64-byte constant block for use with passwords greater than 4
    characters

    Let B_k be the kth byte of B, the 64-byte constant block
    Let m = 2, 16, 24, 8 for each of the four rounds

    index = (A_m + A_m+1) & 0x3F; // 6 LSB
    shift = (A_m+2 + A_m+3) & 0x7; // 3 LSB
		
    for (i = 0; i < 32; ++i)
    {
      if (m == 32) m = 0; // wrap around to beginning
      if (index == 64) index = 0; // wrap around to beginning

      temp = B_index; // xy
      temp <<= 8;
      temp |= B_index; // xyxy

      temp >>= shift;
      A_m ^= (unsigned char) temp;

      ++m;
      ++index;
    }

    The resultant 32-byte encoded password block (Figure 5) does not have
any remnants of the constant block as the short length encoding method
does.  Although the block appears to be "random", it is indeed reversable
with minimal computing resources as shown in our proof-of-concept tools.

    18 0A 43 3A 17 7D A3 CA D7 9D 75 D2 D3 C8 A5 CF 
    F1 71 07 03 5A 52 4B B9 70 2D B2 D1 DF A5 54 07

    Figure 5: Encoded password block of ASCII password 'testa'


Temporary Solution:

The Security application provides functionality to "turn off and lock
device". If the Palm device is turned off and locked using this feature,
the device will not be operational until the correct password is entered.
This will prevent an unauthorized user from running applications on the
device (hence preventing them from starting the HotSync process). This
workaround is only useful if the legitimate user can be sure that the
attacker hasn't attained the system password already - simply change the
password to be sure. It may be possible to bypass the system lock-out
mechanism by entering into the PalmOS debug mode before the lock-out
features are called. This may allow an attacker to step over the security
code during a debugging session.

The use of third-party encryption solutions, such as Secure Memopad by
Certicom, which implement strong and tested cryptological algorithms to
protect the data of certain Palm applications.

Proof-of-Concept Code:
	 
    Proof-of-concept tools have been written for the Windows 9x/NT and
PalmOS 3.3 and greater platforms which demonstrate the simplicity of
obtaining the encoded password block from the target device and the weak
encoding scheme used to obfuscate the password. The PC version,
"PalmCrypt", will encode and decode ASCII passwords to encoded password
blocks and vice versa. The PalmOS version, "NotSync", will imitate the
initial stages of the HotSync process via the IR port, retrieve the
encoded password block of the target device, and decode and display the
resultant ASCII password.

    Source code and binaries for the proof-of-concept tools can be found at:

    http://www.atstake.com/research/advisories/2000/notsync.zip    
    http://www.atstake.com/research/advisories/2000/palmcrypt.zip

    Successfully using NotSync requires two Palm devices: One device
running the NotSync application and the other being the target device in
which the password is desired.

    Facing the two devices head-to-head, run the HotSync application on
the target Palm device and initiate an "IR to a PC/Handheld" HotSync.
NotSync, running on the other device, will obtain the legitimate user's
encoded password block, decode the password, and display the result on the
screen.





 