
9th USENIX Security Symposium Paper 2000
[Technical Index]
PGP in Constrained Wireless DevicesMichael Brown^{*}, Donny Cheung^{*}, Darrel Hankerson^{+}, Julio Lopez Hernandez^{#}, Michael Kirkup^{*}, Alfred Menezes^{*} ^{*}Dept. of Combinatorics and Optimization,
University of Waterloo, Canada ^{+}Dept. of Discrete and Statistical Sciences,
Auburn University, USA ^{#}Institute of Computing, State University
of Campinas, Brazil
AbstractThe market for Personal Digital Assistants (PDAs) is growing at a rapid pace. An increasing number of products, such as the PalmPilot, are adding wireless communications capabilities. PDA users are now able to send and receive email just as they would from their networked desktop machines. Because of the inherent insecurity of wireless environments, a system is needed for secure email communications. The requirements for the security system will likely be influenced by the constraints of the PDA, including limited memory, limited processing power, limited bandwidth, and a limited user interface.This paper describes our experience with porting PGP to the Research in Motion (RIM) twoway pager, and incorporating elliptic curve cryptography into PGP's suite of publickey ciphers. Our main conclusion is that PGP is a viable solution for providing secure and interoperable email communications between constrained wireless devices and desktop machines.
1 IntroductionIt is expected that there will be more than 530 million wireless subscribers by the year 2001, and over a billion by 2004 (see [46]). Efforts are underway, most notable among them the Wireless Application Protocol (WAP) [50], to define and standardize the emerging wireless Internet. Users will access wireless services including telephony, email and web browsing, using a variety of wireless devices such as mobile phones, PDAs (such as the PalmPilot), pagers, and laptop computers equipped with wireless modems. Many wireless devices are constrained by limited CPU, memory, battery life, and user interface (e.g., small screen size, or a lack of graphics capabilities). Wireless networks are constrained by low bandwidth, high latency, and unpredictable availability and stability. The purpose of this paper is to examine the viability of using PGP for providing secure and interoperable email communications between constrained wireless devices and desktop machines. There are two popular standards for email security: S/MIME and PGP. S/MIME [40] provides confidentiality and authentication services to the MIME (Multipurpose Internet Mail Extensions) Internet email format standard. PGP (Pretty Good Privacy) [8,16] is an email security standard that has been widely used since it was first introduced by Zimmermann in 1991 [52]. While it appears that S/MIME will emerge as the industry standard for commercial and organizational use, it also appears that PGP will remain the choice for personal email security for many users in the years to come. The specific goals of this project were threefold:
The remainder of this paper is organized as follows. §2 provides a brief history of PGP, and summarizes the security services offered by PGP. A description of the RIM twoway pager including hardware, software, user interface, development tools, and the paging environment, is provided in §3. A brief overview of the PalmPilot is presented in §4. Elliptic curve cryptography is introduced in §5, along with a description of our implementation. We provide timing comparisons of our ECC implementation with RSA and DL implementations on a variety of platforms. Our experience with porting PGP to the RIM pager is described in §6. Our implementation, including a description of the user interface and key management facilities, is presented in §7. In §8, we describe some possible directions for future work. Finally, §9 makes concluding remarks.
2 Pretty Good Privacy
2.1 History of PGPThe history of the Pretty Good Privacy (PGP) application is both interesting and convoluted, and encompasses issues in national security, personal privacy, patents, personalities, and politics; see, for example, [16]. A myriad of PGP releases emerged, in part due to US Government restrictions on exports. The initial PGP application was released in 1991. According to [16] this was an "emergency release" prompted in part by a proposed anticrime bill which would require eavesdropping ability for the US Government on all communications systems. An RSAbased publickey scheme was used, along with a symmetrickey algorithm developed by Zimmermann known as BassOMatic. Security concerns over BassOMatic resulted in its replacement with IDEA in PGP 2. A commercial version of PGP was developed in 1993 with ViaCrypt (which had a license from Public Key Partners for RSA). Although RSA Data Security had released a reference implementation (RSAREF) of RSA that could be used for noncommercial purposes, there were interface and other difficulties preventing its use in PGP. In 1994, RSAREF 2.0 was released and included changes which MIT recognized would solve the interface problems. This eventually led to PGP 2.6, a version which could be used freely for noncommercial purposes, and which quickly leaked out of the US and developed into several international variants. MIT PGP 2.6.2 increased the ceiling on the maximum size of an RSA modulus (from 1024 to 2048 bits, although ViaCrypt reports a patch correcting certain bugs with the longer moduli). The symmetrickey cipher is IDEA, a 64bit block cipher with 128bit keys; MD5 is used as the hash function, having digest length of 128 bits. A dependency tree for various US and international versions and variants may be found via [38]. Work on PGP 3 began in 1994, and was released by PGP Inc (formed by Zimmermann) as PGP 5 in May 1997.^{1} New algorithms were present, including DSA [34] for signatures, an ElGamal publickey encryption scheme [12], the Secure Hash Algorithm (SHA1) [35] with 160bit message digests, and the symmetrickey ciphers CAST and TripleDES (64bit block ciphers with key sizes of 128 and 168 bits, respectively). In August of 1997, the IETF was approached concerning a proposal to bring PGP to a standards body as a protocol. An OpenPGP working group was formed. Using PGP 5 as the base, a format specification was promoted to a Proposed Standard by the IESG in October 1998. The resulting IETF specification for OpenPGP [9] describes an unencumbered architecture, although compatibility with PGP 2.6 was encouraged. A reference implementation was written by Tom Zerucha and provided in a form suitable for scanning to circumvent US export restrictions [8]. In December 1999, Network Associates (which had acquired PGP Inc in December 1997) was granted a license by the US Government to export PGP. An international PGP project [25], which had been making PGP available worldwide by scanning paper copies that were (legally) exported from the US, announced that the lifting of the ban on strong encryption "marks the end of the PGPi scanning and OCR project, which started with PGP 5.0i in 1997." Several OpenPGPcompliant applications have been developed. The reference implementation by Zerucha [8] relies on the OpenSSL library [37], and has been used by Zerucha as the basis for a PalmPilot implementation. The standard does not require the use of patented algorithms, and applications such as GNU Privacy Guard [18], released in 1999 as a replacement for PGP, can be both compliant and distributable without patent restrictions (since it does not include IDEA or RSA).
2.2 PGP security servicesKEY GENERATION AND STORAGE. PGP allows a user to generate multiple key pairs (publickey/privatekey pairs) for each public scheme supported. Different key pairs are generated for publickey encryption and for digital signatures. The key pairs, together with public keys of other users, are stored in a file called the key ring. Information stored with a public key includes the user's name, email address, trust and validity indicators, key type, key size, expiry date, fingerprint (e.g., the 160bit SHA1 hash of the formatted public key), and a key ID (e.g., the low order 64 bits of the fingerprint). Private keys are not stored directly in the key ring. Instead, the user selects a passphrase which is salted and hashed to derive a key k for a symmetric encryption scheme. The private key is encrypted using k, the passphrase is discarded, and the encrypted private key is stored. Subsequently, when the user wishes to access a private key (in order to decrypt a message or sign a message), the passphrase must be supplied so that the system can regenerate k and recover the private key. CRYPTOGRAPHIC SERVICES. PGP uses a combination of symmetrickey and publickey methods to provide authentication and confidentiality. A message can be signed using the private key from a suitable publickey signature scheme. The recipient can verify the signature once an authentic copy of the signer's corresponding public key is obtained. The OpenPGP standard requires support for SHA1 as a hash algorithm and the DSA, and encourages support for the MD5 hash function and RSA as a signature algorithm. The use of symmetrickey algorithms (such as DES) alone for encryption is supported, although PGP is known more for the confidentiality provided by a combination of publickey and symmetrickey schemes. Since publickey encryption schemes tend to be computationally expensive, a session key is used with a symmetrickey scheme to encrypt a message; the session key is then encrypted using one or more public keys (typically, one for each recipient), and then the encrypted message along with each encrypted session key is delivered. The standard requires support for an ElGamal publickey encryption scheme and TripleDES; support for RSA, IDEA, and CAST is encouraged. Signatures and encryption are often used together, to provide authentication and confidentiality. The message is first signed and then encrypted as described above. KEY MANAGEMENT. The OpenPGP standard does not have a trust model. An OpenPGPcompliant PGP implementation could support a hierarchical X.509based public key infrastructure (PKI). The trust model employed by existing PGP implementations is a combination of direct trust and the web of trust. In the former, user A obtains B's public key directly from B; fingerprints facilitate this process as only the fingerprints have to be authenticated. In the web of trust model, one or more users can attest to the validity of B's public key by signing it with their own signing key. If A possesses an authentic copy of the public key of one of these users, then A can verify that user's signature thereby obtaining a measure of assurance of the authenticity of B's public key. This chaining of trust can be carried out to any depth.
3 RIM's Pager
3.1 OverviewThe RIM wireless handheld device is built around a custom Intel 386 processor running at 10 MHz. Current models carry 2 Mbytes of flash memory and 304 Kbytes of SRAM. There is a fairly conventional (if rather small) keyboard with a 6 or 8line by 28 character (depending on font) graphical display. A thumboperated trackwheel takes the place of a conventional mouse (see Figure 1).
A set of applications including a calendar and address book are commonly installed; even the occasional game of Tetris (falling blocks) is possible with efficient use of the graphical display. The main attraction is the wireless communication features, in particular, email solutions. The integrated wireless modem is essentially invisible, with no protruding antennae. The device is roughly 3.5in x 2.5in x 1in (89mm x 64mm x 25mm) and weighs 5 ounces (142 g) with the single AA battery (there is also an internal lithium cell). RIM claims that the battery will last roughly three weeks with typical usage patterns. A docking cradle can be used to directly connect the device to a serial port. Software for Microsoft Windows is provided to download programs and other information, and to synchronize application data. An RS232 compatible serial port on the pager runs at 19200 bps. To be slightly more precise, RIM has two hardware devices, the 850 and the 950, which are combined with software to provide communications solutions. We used RIM's BlackBerry solution [6] which uses the same hardware as the RIM Inter@ctive Pager 950. The 950 is more of a 2way pager, sold in Canada by Cantel and in the US by BellSouth Wireless Data. The BlackBerry is sold directly by RIM and includes features such as single mailbox integration and PIM synchronization to the device. The RIM 850 looks very similar to the 950 device, but runs on a different wireless network (ARDIS for the 850 as opposed to Mobitex for the 950). The RIM 850 is resold through American Mobile Satellite Corporation (AMSC) in the US, and is part of the AMSC and SkyTel eLink solution.
3.2 Software developmentThe BlackBerry Software Developer's Kit (SDK) is designed to make use of the features in Microsoft's C++ compiler packages. The SDK is freely available from [41]. A handheld application is built as a Windows DLL, a process which allows use of development and debugging facilities available for Windows. However, only a small subset of the usual library calls may be used, along with calls to SDKsupplied routines. The resulting DLL is then stripped of extraneous information and ported into the handheld operating system. For simplicity, the multitasking is cooperative. An application is expected to periodically yield control; in fact, failure to yield within 10 seconds can trigger a pager reset. As an example, publickey operations tend to be computationally expensive, and it was necessary to insert explicit task yields in the code developed for this paper. The SDK includes a simulator which can be used to test applications on the handheld operating system without having to download to the device (the images in this paper are snapshots of the simulator). A radio device (RAP modem) can be connected via serial port to the host machine so that applications running in the simulator can communicate with the Mobitex network. Alternately, a pager in the cradle can be used to exchange email with the simulator, provided that the pager is in coverage. The simulator is essential for serious development, although testing on the pager can reveal bugs not found in the simulator. For example, we managed to link applications in such a way that they would work in the simulator but fail on the pager. At one point, we carelessly used some instructions introduced on the Intel 486, which would work in the simulator when running on a 486orbetter, but would fail on a 386.
3.3 File systemThe pager relies on flash memory to store nonvolatile data. Writing to flash is significantly more expensive than reading, primarily because flash is a writeonce, bulkerase device. Rewriting a single word of flash involves saving the contents of the 64K sector, erasing, and rewriting the entire sector. The longest step in this operation is erasing the sector, and takes approximately 5 seconds. A logstructured file system is employed in order to maintain acceptable performance. Periodically, the expensive process of committing the log updates is performed in order to free file system space. The programming interface to the file system is generally through a relatively small number of highlevel databasestyle calls. Handles are used to read and update databases and variablelength records, a simple but effective method to cooperate with the updating process of the logstructured file system. It is possible to use streamstyle I/O operations of the type familiar to C programmers, which we occasionally found useful for testing code fragments developed on more traditional systems.
4 The PalmPilotFor comparison, our crypto routines were also run on the PalmPilot, a very popular PDA based on a 16 MHz Motorola 68000type "Dragonball" processor.^{2} Recent models carry 24 MB of memory in addition to ROM, although considerable expansion is possible. In 1999, wireless capabilities were introduced on the Palm VII. The communications model differs from the RIM device; in particular, the Palm does not qualify as a pager in the usual sense. There is an antenna which must be physically activated and then the device can request information. A NiCad battery charged from two AAA batteries common in the Palm series is used to power the radio. Ian Goldberg had adapted portions of Eric Young's wellknown SSLeay library (now OpenSSL [37]) for use on the PalmPilot [19]. The resulting library was used by Zerucha in building a Palm version of his reference OpenPGP, and by Daswani and Boneh [11] in their paper on electronic commerce. We used Palm development tools based on the GNU C compiler (gcc2.7.2.2). Timings were done on a Palm V running PalmOS 3.0. There are code segment and stack restrictions which must be considered in the design of a larger application, and our code had to be divided into several libraries in order to accommodate the Palm.
5 Elliptic Curve Cryptography
5.1 IntroductionElliptic curve cryptography (ECC) was proposed independently in 1985 by Neal Koblitz [27] and Victor Miller [33]. For an introduction to ECC, the reader is referred to Chapter 6 of Koblitz's book [29], or the recent book by Blake, Seroussi and Smart [7]. The primary reason for the attractiveness of ECC over RSA and discrete log (DL^{3}) publickey systems is that the best algorithm known for solving the underlying hard mathematical problem in ECC (the elliptic curve discrete logarithm problem, ECDLP) takes fully exponential time. On the other hand, the best algorithms known for solving the underlying hard mathematical problems in RSA and DL systems (the integer factorization problem, and the discrete logarithm problem) take subexponential time. This means that the algorithms for solving the ECDLP become infeasible much more rapidly as the problem size increases than those algorithms for the integer factorization and discrete logarithm problems. For this reason, ECC offers security equivalent to that of RSA and DL systems, while using significantly smaller key sizes. Table 1 lists ECC key lengths and very rough estimates of DL and RSA key lengths that provide the same security (against known attacks) as some common symmetric encryption schemes. The ECC key lengths are twice the key lengths of their symmetric cipher counterparts since the best general algorithm known for the ECDLP takes (Ö{p2^{k}})/2 steps for kbit ECC keys, while exhaustive key search on a symmetric cipher with lbit keys takes 2^{l} steps. The estimates for DL security were obtained from [2]. The estimates for RSA security are the same as those for DL security because the best algorithms known for the integer factorization and discrete logarithm problems have the same expected running times. These estimates are roughly the same as the estimates provided by Lenstra and Verheul in their very thorough paper [31].
The advantages that may be gained from smaller ECC parameters include speed (faster computation) and smaller keys and certificates. These advantages are especially important in environments where processing power, storage space, bandwidth, or power consumption are at a premium such as smart cards, pagers, cellular phones, and PDAs.
5.2 Selecting ECC parametersNOTATION. In the following, F_{q} denotes a finite field of order q, and E denotes an elliptic curve defined over F_{q}. #E(F_{q}) denotes the number of points on the elliptic curve E. The point at infinity is denoted by O. There is a group law for adding any two elliptic curve points. If k is an integer and P Î E(F_{q}) is a point, then kP is the point obtained by adding together k copies of P; this process is called scalar multiplication.
DOMAIN PARAMETERS.
ECC domain parameters consist of the following:
CURVES SELECTED. For this project, we chose binary fields F_{2m}, for m = 163, 233 and 283. Suitably chosen elliptic curves over these fields provide at least as much security as symmetrickey ciphers with key lengths 80, 112 and 128 bits respectively (see Table 1). A polynomial basis representation was used to represent field elements. Such a representation is defined by a reduction polynomial f(x), which is an irreducible binary polynomial of degree m. For each field F_{2m}, we chose a random curve over F_{2m} and a Koblitz curve [28] over F_{2m} from the list of elliptic curves recommended by NIST for US federal government use [34]. The salient features of the Koblitz curves are provided in Table 2. Koblitz curves have special structure that enable faster elliptic curve arithmetic in some environments (see [44,45]). The number of points on each of the chosen curves is almost prime; that is, #E(F_{2m}) = nh, where n is prime and h = 2 or h = 4. Since #E(F_{2m}) » 2^{m}, it follows that the ECC key length is approximately equal to m. Security implications of these choices are discussed in §5.4.
5.3 ECC protocolsKEY GENERATION. An entity A's public and private key pair is associated with a particular set of EC domain parameters (q,FR,a,b,G,n,h). This association can be assured cryptographically (e.g., with certificates) or by context (e.g., all entities use the same domain parameters). To generate a key pair, entity A does the following:
PUBLIC KEY VALIDATION. This process ensures that a public key has the requisite arithmetic properties. A public key Q = (x_{Q},y_{Q}) associated with domain parameters (q,FR,a,b,G,n,h) is validated using the following procedure:
The computationally expensive operation in public key validation is the scalar multiplication in step 4. This step can sometimes be incorporated into the protocol that uses Q  this is done in the ECAES below. Public key validation with step 4 omitted is called partial public key validation. ELLIPTIC CURVE AUTHENTICATED ENCRYPTION SCHEME (ECAES). The ECAES, proposed by Abdalla, Bellare and Rogaway [1], is a variant of the ElGamal publickey encryption scheme [12]. It is efficient and provides security against adaptive chosenciphertext attacks. We suppose that receiver B has domain parameters D = (q,FR,a,b,G,n,h) and public key Q. We also suppose that A has authentic copies of D and Q. In the following, MAC is a message authentication code (MAC) algorithm such as HMAC [30], ENC is a symmetric encryption scheme such as TripleDES. KDF denotes a key derivation function which derives cryptographic keys from a shared secret point. To encrypt a message m for B, A does:
To decrypt ciphertext (R,c,t), B does:
The computationally expensive operations in encryption and decryption are the scalar multiplications in steps 23 and step 2, respectively. ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM (ECDSA). The ECDSA is the elliptic curve analogue of the DSA [34]. SHA1 is the 160bit hash function [35]. We suppose that signer A has domain parameters D = (q,FR,a,b,G,n,h) and public key Q. We also suppose that B has authentic copies of D and Q. To sign a message m, A does the following:
To verify A's signature (r,s) on m, B should do the following:
The computationally expensive operations in signature generation and signature verification are the scalar multiplications in step 2 and step 5, respectively.
5.4 Security issuesHARDNESS OF THE ECDLP. It can easily be verified that the elliptic curves E(F_{q}) chosen resist all known attacks on the ECDLP. Specifically:
SECURITY OF ECAES. The ECAES modifies the ElGamal encryption scheme by using the onetime DiffieHellman shared secret, hrdG, to derive secret keys k_{1} and k_{2} The first key k_{1} is used to encrypt the message using a symmetric cipher, while the second key k_{2} is used to authenticate the resulting ciphertext. The latter provides resistance to chosenciphertext attacks. Some formal justification of ECAES security is provided in [1], where it is proven to be semantically secure against adaptive chosenciphertext attack on the assumption that the underlying symmetric encryption and MAC schemes are secure, and assuming the hardness of certain variants of the elliptic curve DiffieHellman problem. In order to correctly balance the security of the ECAES cryptographic components, one should ideally employ a k/2bit block cipher and a kbit hash function for HMAC when using a kbit elliptic curve (see Table 1). Our implementation used the 112bit block cipher TripleDES in CBCmode and the 160bit hash function SHA1 for all 3 choices of ECC key lengths (163, 233 and 283). A future version of our implementation should allow for a variable outputlength hash function (e.g., the forthcoming SHA2) and a variablelength block cipher (e.g., the AES). SECURITY OF ECDSA. ECDSA is the straightforward elliptic curve analogue of the DSA, which has been extensively scrutinized since it was proposed in 1991. For a summary of the security properties of the ECDSA, see [26]. Our implementation used the 160bit hash function SHA1 for all 3 choices of ECC key lengths (163, 233 and 283). As with the ECAES, a future version of our ECDSA implementation should allow for a variable outputlength hash function.
5.5 TimingsThis section presents timings for the ECC operations on a Pentium II 400 MHz machine, a PalmPilot and the RIM pager, and compares them with timings for RSA and DL operations. ECC TIMINGS. Our ECC code was written entirely in C on a Sun Sparcstation and, in order to ensure portability, no assembler was used. We encountered no problems in porting the code to the Pentium II, RIM pager, and PalmPilot platforms, although some changes were required in order to cooperate with the 16bit options used in the Palm version of the "big number" library of OpenSSL. No effort was made to optimize the ECC code for these particular platforms; it is very likely that significant performance improvements could be obtained by optimizing the ECC (and DL and RSA) code for these platforms. Further details of our ECC implementations are reported in [23]. For other ECC implementation reports, see [42] for a C implementation of elliptic curve arithmetic over F_{2155}, [49] for a C/C++ of elliptic curve arithmetic over F_{2191} and over a 191bit prime field, and [22] for an assembly language implementation of elliptic curve arithmetic over a 160bit prime field on a 10 MHz 16bit microcomputer. Tables 3, 4 and 5 present timings of our implementation for ECC operations using the Koblitz curves and random curves over F_{2163}, F_{2233} and F_{2283}.
RSA TIMINGS. The RSA code, written entirely in C, was taken from the OpenSSL library [37]. Tables 6 and 7 present timings for 512, 768, 1024, and 2048bit RSA operations.
DL TIMINGS. The DSA and ElGamal code, also written entirely in C, was obtained from the OpenSSL and OpenPGP libraries. For ElGamal, the prime p was chosen to be a safe prime; that is p = 2q+1 where q is also prime. Table 8 presents timings for 512, 768 and 1024bit DSA and ElGamal operations. For encryption, the permessage secret key is not of full length (i.e., the bitlength of p), but of bitlength 200 + (bitlength of p)/32; this explains why ElGamal encryption is faster than ElGamal decryption. The ElGamal operations could be sped up significantly if DSAlike parameters were used (i.e., p = kq+1, where q is a 160bit prime).
COMPARISON. The performance of all three families of publickey systems (ECC, RSA and DL) are sufficiently fast for PGP implementations on a Pentium machineit hardly matters whether a user has to wait 10 ms or 100 ms to sign and encrypt a message. On the pager, RSA publickey operations (encryption and signature verification) are faster than ECC publickey operations, especially when the public exponent is e = 3. For example, verifying a 1024bit RSA signature takes about 300 ms, while verifying a 163bit ECC signature (using a Koblitz curve) takes about 1,800 ms. On the other hand, RSA privatekey operations (decryption and signature generation) are slower than ECC privatekey operations. For example, signing with a 1024bit RSA key takes about 16,000 ms, while signing with a 163bit ECC key takes about 1,000 ms. ECC has a clear advantage over RSA for PGP operations that require both private key and public key computations. Signingandencrypting together takes 16,400 ms with 1024bit RSA (using e = 3), and 2800 ms with 163bit ECC (using a Koblitz curve). Verifyinganddecrypting together takes 16,200 ms with 1024bit RSA, and 2,900 ms with 163bit ECC. Similar conclusions are drawn when comparing RSA and ECC performance on the PalmPilot. Private key operations with 2048bit RSA are too slow for the pager and the PalmPilot, while 233bit ECC and 283bit ECC operations are tolerable for PGP applications on the pager. Since domain parameters are used in our ECC implementation, ECC key generation only involves a single scalar multiplication and thus is very fast on the pager. RSA, ElGamal and DSA key generation on the pager is prohibitively slow. However, ElGamal and DSA key generation would be feasible on the pager if precomputed domain parameters (primes p and q, and generator g) were used.
5.6 InteroperabilityThe elliptic curves and protocols were selected to conform with the prevailing ECC standards and draft standards. The Koblitz and random curves over F_{2163}, F_{2233} and F_{2283} are from the list of NIST recommended curves [34]. The representations, for both field elements and for elliptic curve points, are compliant with the ANSI X9.62 [4], ANSI X9.63 [5], IEEE P1363 [24] and FIPS 1862 [34] standards. In addition, the Koblitz curve over F_{2163} is explicitly listed in the WAP wTLS specification [51]. Our ECDSA implementation conforms to the security and interoperability requirements of ANSI X9.62, IEEE P1363, and FIPS 1862. Our ECAES implementation conforms to the security and interoperability requirements of ANSI X9.63. The cryptographic components HMAC and TripleDES (in CBC mode) of ECAES are compliant, respectively, with RFC 2104 [30] and ANSI X9.52 [3].
6 Porting PGP to the PagerThere are now a number of cryptographic libraries and PGP applications which have received extensive development and for which source code is available; see, for example, cryptlib by Peter Gutmann [20] and Crypto++ by Wei Dai [10]. Our plan was to adapt existing code, adding publickey schemes based on elliptic curves. For comparisons and development, it was essential that the code run on several platforms in addition to the RIM device. Our initial work was with GNU Privacy Guard (GnuPG) [18], an OpenPGPcompliant freely distributable replacement for PGP, which was nearing a postbeta release in 1999. Initial tests on the pager with several fragments adapted from GnuPG sources were promising, and the code appeared to be ideal for adding the elliptic curve routines and testing on Unixbased and other systems. However, it appeared that untangling code dependencies for our use on the pager would be unpleasant. (Perhaps a better understanding of GnuPG internals and design decisions would have changed our opinion.) Jonathan Callas suggested that we look again at the OpenPGP reference implementation [8], which we had put aside after initial testing revealed a few portability and alignment problems in the code. The reference implementation relied on the OpenSSL library [37]. The OpenPGP reference implementation is surprisingly complete for the amount of code, although it is admittedly a little rough on the edges.^{4} The code was developed on a Linux/x86 system, and modifications were required for alignment errors which prevented the program from running on systems such as Solaris/SPARC. In addition, some portability changes were required, including code involving the "long long" data type. For the RIM pager, the separation of the PGP code from the welltested OpenSSL library, along with the small size of the OpenPGP sources, were definite advantages. Finally, it should be noted that the OpenSSL libraries build easily on Unix and Microsoft Windows systems, and are designed so that adding routines such as the elliptic curve code is straightforward. Although applications for the pager are built as Windows DLLs, the pager is not a Windowsbased system. There are significant restrictions on the calls that can be used, extending to those involving memory allocation, time and character handling, and the file system. There is no floatingpoint processor on the pager. In order to adapt code developed on more traditional systems, we wrote a library of compatibility functions to use with the pager. Some functions were trivial (such as those involving memory allocation, since the SDK included equivalent calls); others, such as the stream I/O calls, were written to speed testing and porting and cannot be recommended as particularly robust or elegant. We used portions of OpenSSL 0.9.4, along with the library in the OpenPGP reference implementation. Relatively few changes to OpenSSL were required, and could be restricted to header files in many cases. The elliptic curve routines were integrated, including additions to the scripts used to build OpenSSL. For some platforms, OpenSSL can be built using assemblylanguage versions of certain key routines to improve execution speed. Some of these files for the Intel x86 include instructions (such as bswap) which were introduced for the 486, and cannot be used on the pager. The OpenPGP sources were modified to correct the alignment bugs and portability problems mentioned above, and necessary changes were made for the elliptic curve schemes (publickey algorithms 18 and 19 in the OpenPGP specification [9]). The compatibility library, along with a few streamtomemory conversion functions allowed fairly direct use of the OpenPGP sources on the pager. The only code tested exclusively in the pager environment involved the user interface (see §7.1). The SDK provides a fairly powerful and highlevel API for working with the display and user input. The difficulties we encountered were mostly due to the lack of support in the API for direct manipulation of messages desired in a PGP framework. In part, this reflects a deliberate design decision by BlackBerry to develop a robust and intuitive communication solution which provides some protection against misbehaving applications.^{5} The pager DLLs for the interface and PGP library were over 400 KB in combined size. This includes all of the OpenPGP required algorithms and recommended algorithms such as IDEA and RSA, along with the new schemes based on elliptic curves. For a rough comparison, the code size for the main executable from the OpenPGP reference implementation (with the addition of the elliptic curve routines) is 300400 KB, depending on platform.
7 Implementation
7.1 User interfacePGP in any form has not been an easy application for novices to manage properly, in part due to the sophistication required, but also because of poor interface design [47]. The goals for our user interface design were rather modest: that a user who is familiar with using PGP on a workstation, and is comfortable operating the RIM device, should, without having to refer to a manual or help pages, be easily able to figure out how to use PGP on the pager and avoid dangerous errors (such as those described in [47]). As mentioned in §3.1, the graphics capabilities and screen size of the RIM device are very limited. This forced us to keep our PGP implementation simple and only offer the user the essential features. A glimpse of our user interface is provided in Figures 15. Clicking on the PGP icon (see Figure 1) displays the list of users whose keys are in the public key ring (see Figure 2).
Selecting a user name displays the menu shown in Figure 3, which allows the user to view the key's attributes, compose a new key, delete a key, or send a key.
7.2 Key generation and storageThe main PGP menu (Figure 3) has an option "New Key" for creating a key pair. Users can enter their name, email address, pager PIN, and select a key type and key length (see Figure 4).
The key types and key sizes presently available are ECC (random curve or Koblitz curve; over F_{2163}, F_{2233} or F_{2283}), DH/DSS (512/512, 768/768, 1024/1024, 1536/1024 or 2048/1024 bits), and RSA (512, 768, 1024, 1536 or 2048 bits). The DH/DSS and RSA key sizes are the ones available in many existing PGP implementations. For the DSA, the maximum bitsize of the prime p is 1024 bits in conformance with the DSS [34]. For ECC, separate key pairs are generated for publickey encryption and digital signatures. Public keys and private keys are stored in separate key rings. Public key attributes (see Figure 5) can be viewed using the "View Key" function available on the main menu.
As required by OpenPGP, private keys are encrypted under a userselected passphrase, and the encrypted private key is stored. The passphrase has to be entered whenever a private key is required to sign or decrypt a message.
7.3 Cryptographic servicesThe three basic PGP services are available: sign only, encrypt only, or signandencrypt. Users can decide to sign an email, or to encrypt an email, after composing the message. The user is prompted for the passphrase to unlock the private signing key, and to select the public encryption key of the intended recipient. In addition to the times given in Tables 38 for the main operations, there is additional overhead which can be apparent to the user. Verifying the passphrase, for example, may require 20 seconds if the default iteration count is used when hashing the salted passphrase; our implementation used a smaller default iteration count. A small amount of time is added for interaction with the database filesystem for large memory transfers.
7.4 Key managementThe key management system we implemented was the simplest one possiblethe direct trust model (see §2.2). A menu item is available (see Figure 3) for emailing one's public key to another user. A function is also available for extracting and storing a public key received in an email message. If desired, a public key can be authenticated by verifying its fingerprint by some direct means (e.g., communicating it over the telephoneauthenticity is provided by voice recognition).
8 Future WorkThe following are some directions for future work. RANDOM NUMBER GENERATION. Many systems implement a "random gathering device" which attempts to use environmental noise (keyboard data, system timers, disk characteristics, etc.) to build a cryptographically secure source of random bits [21]. Our pager application used only a rather simple (and most likely not sufficiently secure) seeding process involving the clock and a few other sources. A more sophisticated solution is essential, perhaps tapping into the radio apparatus as a source. CODE SIZE. No serious effort was made to minimize the size of the programs loaded to the pager. There is some code linked from the OpenSSL cryptographic library which could easily be removed (in fact, we were somewhat surprised that the library with the added elliptic curve routines could be used with relatively few modifications for the pager). The library routines adapted from OpenSSL and OpenPGP along with various glue needed to adapt to the pager accounts for approximately 3/4 of the 370 KB loaded on the device (with the remainder attributed to code involving the screen and userinterface). If some interoperability can be sacrificed, then the code size can also be reduced by removing routines such as CAST or some of the hash algorithms. MAKING THE OPENPGP CODE MORE ROBUST. The OpenPGP reference implementation provides minimal diagnostics and can easily break on bad data. The occasional segmentation fault triggered by bad user data may be merely unpleasant when an application is used on a workstation; such errors on the pager are completely unacceptable. Our application corrects some of the most troublesome shortcomings, but better errorhandling is needed. KEY MANAGEMENT. We would like to implement an X.509based PKI or the web of trust model. In either case, we would implement a key server for retrieving and storing keys in a key repository. This would involve setting up a proxy wireless server with which the pager would communicate directly. The proxy server in turn would communicate with existing key servers on the Internet.
9 ConclusionsIMPLEMENTING PGP ON THE RIM PAGER. The 32bit architecture, relatively sophisticated operating system and development environment, and relatively large memory size means that development for the pager is closer to that done for more traditional systems than the small size might suggest. The user interface must be customized for the device, but "generic code" which does not involve file I/O moves fairly easily to the pager. On the other hand, it appears likely that such devices will continue to have processors which run much more slowly than their desktop counterparts. Long delays in handling encrypted messages or signatures will be a considerable annoyance for users of this type of device. While we used a significant amount of the available memory on the pager, it would be desirable to reduce the resource consumption in a production version of PGP. Battery life will continue to be a major concern, and the overhead of authentication and confidentiality competes with the need to minimize transmissions from the device. INTEROPERABILITY. The goal of interoperability was met. All of the required algorithms from RFC 2440 are included, along with several listed as recommended and the elliptic curve routines. Our PGP implementation interoperated with existing implementations for the PalmPilot and workstations. ELLIPTIC CURVE CRYPTOGRAPHY. Elliptic curve solutions fit particularly well into the constrained environment. 1024bit and 2048bit RSA privatekey operations are too slow for PGP applications, while the performance of 163bit, 233bit and 283bit ECC operations is tolerable for PGP applications. If PGP (or other email security solutions) is to be used for securing email communications between constrained wireless devices and desktop machines, then our timings show that ECC is preferable to RSA since the performance of the latter on some wireless devices is too slow, while both systems perform sufficiently well on workstations. GENERAL. This paper concentrated on PGP, although the results are more widely applicable. Many of the services targeted at the growing wireless market will require security solutions involving the cryptographic mechanisms used by PGP. The constraints on small wireless devices are likely to be with us for some time, and will require a balance of usability, computational requirements, security, and battery life.
AcknowledgementsThe authors would like to thank Jonathan Callas for some enlightening discussions about PGP, and Herb Little for answering our numerous questions about the RIM pager.
References
Footnotes:^{1} Callas [8] notes that ViaCrypt had released several products with a version number of 4 although they were derivatives of PGP 2, and "it was easier to explain why three became five than to explain why three was the new program and four the old one." ^{2}According to [39], "Even after two rounds of Microsoft's best Windows CE efforts, PalmPilot OS devices still represent 80% of all palmtop sales." ^{3} Examples of DL systems are the ElGamal publickey encryption scheme and the DSA signature scheme which is specified in the Digital Signature Standard. PGP documentation refer to these two schemes as DiffieHellman/DSS or DH/DSS. ^{4}Zerucha writes that he wasn't "careful about wiping memory and preventing memory leaks and other things to make the code robust" [8]. ^{5} During our work on this project, BlackBerry modified the API to provide some of the access needed to smoothly integrate PGP into their mail application. File translated from T_{E}X by T_{T}H, version 2.68, on 13 Jun 2000. 
This paper was originally published in the
Proceedings of the 9th USENIX Security Symposium,
August 1417, 2000, Denver, Colorado, USA
Last changed: 29 Jan. 2002 ml 
