home *** CD-ROM | disk | FTP | other *** search
/ Hacker Chronicles 2 / HACKER2.BIN / 1225.PGFORMAT.DOC < prev    next >
Text File  |  1991-05-22  |  9KB  |  258 lines
  1. Appendix A.  (Beta test release 22 May 91)
  2.  
  3.  
  4. Internal Data Structures Used by PGP
  5. ====================================
  6.  
  7. This appendix describes the data structures used internally by Pretty
  8. Good Privacy (PGP), the RSA public key cryptography application.  The
  9. intended audience mainly includes software engineers trying to port
  10. PGP to other hardware environments or trying to implement other PGP-
  11. compatible cryptography products.
  12.  
  13. Some of these data structures may change before PGP is released.  
  14. Also, CRC-16 frame checks may be added to some packets.
  15.  
  16.  
  17. Byte Order
  18. ----------
  19.  
  20. All integer data used by PGP is externally stored least significant
  21. byte (LSB) first, regardless of the byte order used internally by the
  22. host CPU architecture.  This is for cross-compatibility of messages
  23. and keys between hosts.  This covers multiprecision RSA integers, bit
  24. count prefix fields, byte count prefix fields, key IDs, and
  25. timestamps.
  26.  
  27.  
  28. Multiprecision Integers
  29. -----------------------
  30.  
  31. RSA arithmetic involves a lot of multiprecision integers, often
  32. having hundreds of bits of precision.  PGP externally stores a
  33. multiprecision integer (MPI) with a 16-bit prefix that gives the
  34. number of significant bits in the integer that follows.  The integer
  35. that follows this bitcount field is stored LSB first, with the MSB
  36. padded with zero bits if the bitcount is not a multiple of 8.  The
  37. bitcount always specifies the exact number of significant bits.  For
  38. example, the integer value 5 would be stored as these three bytes:
  39.  
  40.     03 00 05
  41.  
  42. An MPI with a value of zero is simply stored with the 16-bit bitcount 
  43. prefix field containing a 0, with no value bytes following it.
  44.  
  45.  
  46.  
  47. Key ID
  48. ------
  49.  
  50. Some packets use a "key ID" field.  The key ID is the least
  51. significant 64 bits of the RSA public modulus that was involved in
  52. creating the packet.  For all practical purposes it unique to each 
  53. RSA public key.
  54.  
  55.  
  56. User ID
  57. -------
  58.  
  59. Some packets contain a "user ID", which is an ASCII string that
  60. contains the user's name.  Unlike a C string, the user ID has a
  61. length byte at the beginning that has a byte count of the rest of the
  62. string.  This length byte does not include itself in the count.
  63.  
  64.  
  65. Timestamp
  66. ---------
  67.  
  68. Some packets contain a timestamp, which is a 32-bit unsigned integer
  69. of the number of seconds elapsed since 1970 Jan 1 00:00:00 GMT.  This
  70. is the standard format used by Unix timestamps.  It spans 136 years. 
  71.  
  72.  
  73.  
  74. Cipher Type Byte (CTB)
  75. ----------------------
  76.  
  77. Many of these data structures begin with a Cipher Type Byte (CTB),
  78. which specifies the type of data structure that follows it.  The CTB 
  79. bit fields have the following meaning (bit 0 is the LSB, bit 7 is the
  80. MSB):
  81.  
  82. Bit 7:     Always 1, which designates this as a CTB
  83. Bit 6:     Reserved.
  84. Bits 5-2:  CTB type field, specifies type of packet that follows
  85.            0001 - RSA public-key-encrypted packet
  86.            0010 - RSA secret-key-encrypted (signed) packet
  87.            0011 - Message digest packet
  88.            0100 - Conventional key packet
  89.            0101 - Secret key certificate
  90.            0110 - Public key certificate
  91.            1000 - Compressed data packet
  92.            1001 - Conventional-Key-Encrypted data
  93.            1100 - Raw literal plaintext data
  94.            Other CTB packet types are unimplemented.
  95. Bits 1-0:  Length-of-length field:
  96.            00 - 1 byte packet length field follows CTB
  97.            01 - 2 byte packet length field follows CTB
  98.            10 - 4 byte packet length field follows CTB
  99.            11 - no length field follows CTB, unknown packet length.
  100.            The 8-, 16-, or 32-bit packet length field after the CTB 
  101.            gives the length in bytes of the rest of the packet, not
  102.            counting the CTB and the packet length field.
  103.  
  104.  
  105.  
  106. RSA public-key-encrypted packet
  107. -------------------------------
  108.  
  109. Offset  Length  Meaning
  110. 0       1       CTB for RSA public-key-encrypted packet
  111. 1       2       16-bit length of packet
  112. 3       8       64-bit Key ID
  113. 11      ?       RSA-encrypted integer, encrypted conventional key
  114.                 packet.  (MPI with bitcount prefix)
  115.  
  116. The conventionally-encrypted ciphertext packet begins right after the 
  117. RSA public-key-encrypted packet that contains the conventional key.
  118.  
  119.  
  120.  
  121. RSA secret-key-encrypted (signed) packet
  122. ----------------------------------------
  123.  
  124. Offset  Length  Meaning
  125. 0       1       CTB for RSA secret-key-encrypted (signed) packet
  126. 1       2       16-bit length of packet
  127. 3       8       64-bit Key ID
  128. 11      ?       RSA-encrypted integer, encrypted message digest
  129.                 packet.  (MPI with bitcount prefix)
  130.  
  131. If the plaintext that was signed is included in the same file as the
  132. signature packet, it begins right after the RSA secret-key-signed 
  133. packet that contains the message digest.  The plaintext has a
  134. "literal" CTB prefix.
  135.  
  136.  
  137.  
  138. Message digest packet
  139. ---------------------
  140.  
  141. Offset  Length  Meaning
  142. 0       1       CTB for Message digest packet
  143. 1       1       8-bit length of packet
  144. 2       1       Message digest algorithm selector byte
  145. 3       16      128-bit message digest
  146. 19      4       32-bit timestamp
  147.  
  148.  
  149.  
  150. Conventional key packet
  151. -----------------------
  152.  
  153. Offset  Length  Meaning
  154. 0       1       CTB for Conventional key packet
  155. 1       1       8-bit length of packet
  156. 2       1       Conventional encryption algorithm selector byte
  157. 3       ?       Key material for conventional algorithm
  158.  
  159.  
  160.  
  161. Conventional Key Encrypted data packet
  162. --------------------------------------
  163.  
  164. Offset  Length  Meaning
  165. 0       1       CTB for Conventional-Key-Encrypted data packet
  166. 1    ?    conventionally-encrypted data, no length field
  167.  
  168. The conventionally-encrypted ciphertext begins right after the 
  169. CTB.  No length field follows CTB, unknown packet length.
  170. The decrypted ciphertext may contain a compressed data packet or a
  171. literal plaintext packet.
  172.  
  173. The conventionally-encrypted data has a 4-byte "key-check" prefix. 
  174. This key-check prefix is inserted before encryption and discarded
  175. after decryption.  The key-check prefix is only visible only after
  176. decrypting the ciphertext in the packet.  The key-check prefix is
  177. composed of two identical copies of a 16-bit random number.  During
  178. decryption, the first 4 bytes of decrypted plaintext are checked to
  179. see if the first 2 bytes match the second 2 bytes.  If this key-check
  180. prefix meets this criterium, then the conventional key is assumed to
  181. be correct.  
  182.  
  183.  
  184.  
  185. Compressed data packet
  186. ----------------------
  187.  
  188. Offset  Length  Meaning
  189. 0       1       CTB for Compressed data packet
  190. 1    1    Compression algorithm selector byte
  191. 2    ?    compressed data, no length field
  192.  
  193. The compressed data begins right after the algorithm selector byte.
  194. No length field follows CTB, unknown packet length.
  195. The compressed data may decompress into a raw literal plaintext data
  196. packet with its own CTB.
  197.  
  198.  
  199.  
  200. Literal data packet
  201. -------------------
  202.  
  203. Offset  Length  Meaning
  204. 0       1       CTB for raw literal data packet
  205. 1    ?    raw literal plaintext data, no length field
  206.  
  207. The raw literal plaintext data begins right after the 
  208. CTB.  No length field follows CTB, unknown packet length.
  209.  
  210.  
  211.  
  212. RSA secret key certificate
  213. --------------------------
  214.  
  215. Offset  Length  Meaning
  216. 0       1       CTB for RSA secret key certificate
  217. 1       2       16-bit length of packet
  218. 3       4       Timestamp
  219. 7       ?       User ID
  220. ?       ?       MPI of RSA public modulus n
  221. ?       ?       MPI of RSA public encryption exponent e
  222. ?       ?       MPI of RSA secret decryption exponent d
  223. ?       ?       MPI of RSA secret factor p
  224. ?       ?       MPI of RSA secret factor q
  225. ?       ?       MPI of RSA secret multiplicative inverse u
  226.                 (All MPI's have bitcount prefixes)
  227.  
  228. All secret fields in the secret key certificate may be password-
  229. encrypted.  The public fields are not encrypted.
  230.  
  231.  
  232.  
  233. Public key certificate
  234. ----------------------
  235.  
  236. Offset  Length  Meaning
  237. 0       1       CTB for RSA public key certificate
  238. 1       2       16-bit length of packet
  239. 3       4       Timestamp
  240. 7       ?       User ID
  241. ?       ?       MPI of RSA public modulus n
  242. ?       ?       MPI of RSA public encryption exponent e
  243.                 (All MPI's have bitcount prefixes)
  244.  
  245.  
  246.  
  247. "Secret key compromised" certificate
  248. ------------------------------------
  249.  
  250. Note that a "secret key compromise" certificate is exactly the same 
  251. as a public key certificate, but with public exponent e=0.
  252.  
  253. The current version of PGP does not generate any secret key
  254. compromise certificates.
  255.  
  256.  
  257.  
  258.