home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1851 < prev    next >
Text File  |  1995-10-02  |  20KB  |  620 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                            P. Karn
  8. Request for Comments: 1851                                      Qualcomm
  9. Category: Experimental                                        P. Metzger
  10.                                                                 Piermont
  11.                                                               W. Simpson
  12.                                                               Daydreamer
  13.                                                           September 1995
  14.  
  15.  
  16.                       The ESP Triple DES Transform
  17.  
  18.  
  19. Status of this Memo
  20.  
  21.    This document defines an Experimental Protocol for the Internet
  22.    community.  This does not specify an Internet standard of any kind.
  23.    Discussion and suggestions for improvement are requested.
  24.    Distribution of this memo is unlimited.
  25.  
  26.  
  27. Abstract
  28.  
  29.    This document describes the Triple DES-CBC security transform for the
  30.    IP Encapsulating Security Payload (ESP).
  31.  
  32.  
  33. Table of Contents
  34.  
  35.      1.     Introduction ..........................................    2
  36.         1.1       Keys ............................................    2
  37.         1.2       Initialization Vector ...........................    2
  38.         1.3       Data Size .......................................    3
  39.         1.4       Performance .....................................    3
  40.  
  41.      2.     Payload Format ........................................    4
  42.  
  43.      3.     Algorithm .............................................    6
  44.         3.1       Encryption ......................................    6
  45.         3.2       Decryption ......................................    7
  46.  
  47.      SECURITY CONSIDERATIONS ......................................    7
  48.      ACKNOWLEDGEMENTS .............................................    8
  49.      REFERENCES ...................................................    9
  50.      AUTHOR'S ADDRESS .............................................   11
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Karn, et al                   Experimental                      [Page 1]
  59.  
  60. RFC 1851                        ESP 3DES                  September 1995
  61.  
  62.  
  63. 1.  Introduction
  64.  
  65.    The Encapsulating Security Payload (ESP) [RFC-1827] provides
  66.    confidentiality for IP datagrams by encrypting the payload data to be
  67.    protected.  This specification describes the ESP use of a variant of
  68.    of the Cipher Block Chaining (CBC) mode of the US Data Encryption
  69.    Standard (DES) algorithm [FIPS-46, FIPS-46-1, FIPS-74, FIPS-81].
  70.    This variant, known as Triple DES (3DES), processes each block of the
  71.    plaintext three times, each time with a different key [Tuchman79].
  72.  
  73.    This document assumes that the reader is familiar with the related
  74.    document "Security Architecture for the Internet Protocol" [RFC-
  75.    1825], which defines the overall security plan for IP, and provides
  76.    important background for this specification.
  77.  
  78.  
  79.  
  80. 1.1.  Keys
  81.  
  82.    The secret 3DES key shared between the communicating parties is
  83.    effectively 168-bits long.  This key consists of three independent
  84.    56-bit quantities used by the DES algorithm.  Each of the three 56-
  85.    bit subkeys is stored as a 64-bit (eight octet) quantity, with the
  86.    least significant bit of each octet used as a parity bit.
  87.  
  88.  
  89.  
  90. 1.2.  Initialization Vector
  91.  
  92.    This mode of 3DES requires an Initialization Vector (IV) that is
  93.    eight octets in length.
  94.  
  95.    Each datagram contains its own IV.  Including the IV in each datagram
  96.    ensures that decryption of each received datagram can be performed,
  97.    even when other datagrams are dropped, or datagrams are re-ordered in
  98.    transit.
  99.  
  100.    The method for selection of IV values is implementation dependent.
  101.  
  102.    Notes:
  103.       A common acceptable technique is simply a counter, beginning with
  104.       a randomly chosen value.  While this provides an easy method for
  105.       preventing repetition, and is sufficiently robust for practical
  106.       use, cryptanalysis may use the rare serendipitous occurrence when
  107.       a corresponding bit position in the first DES block increments in
  108.       exactly the same fashion.
  109.  
  110.  
  111.  
  112.  
  113.  
  114. Karn, et al                   Experimental                      [Page 2]
  115.  
  116. RFC 1851                        ESP 3DES                  September 1995
  117.  
  118.  
  119.       Other implementations exhibit unpredictability, usually through a
  120.       pseudo-random number generator.  Care should be taken that the
  121.       periodicity of the number generator is long enough to prevent
  122.       repetition during the lifetime of the session key.
  123.  
  124.  
  125.  
  126. 1.3.  Data Size
  127.  
  128.    The 3DES algorithm operates on blocks of eight octets.  This often
  129.    requires padding after the end of the unencrypted payload data.
  130.  
  131.    Both input and output result in the same number of octets, which
  132.    facilitates in-place encryption and decryption.
  133.  
  134.    On receipt, if the length of the data to be decrypted is not an
  135.    integral multiple of eight octets, then an error is indicated, as
  136.    described in [RFC-1825].
  137.  
  138.  
  139.  
  140. 1.4.  Performance
  141.  
  142.    Three DES-CBC implementations may be pipelined in series to provide
  143.    parallel computation.  At the time of writing, at least one hardware
  144.    implementation can encrypt or decrypt at about 1 Gbps [Schneier94, p.
  145.    231].
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Karn, et al                   Experimental                      [Page 3]
  171.  
  172. RFC 1851                        ESP 3DES                  September 1995
  173.  
  174.  
  175. 2.  Payload Format
  176.  
  177.  
  178.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  179.    |                Security Parameters Index (SPI)                |
  180.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  181.    |                                                               |
  182.    ~                   Initialization Vector (IV)                  ~
  183.    |                                                               |
  184.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  185.    |                                                               |
  186.    ~                          Payload Data                         ~
  187.    |                                                               |
  188.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  189.              ... Padding           |  Pad Length   | Payload Type  |
  190.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  191.  
  192.  
  193.    Security Parameters Index (SPI)
  194.  
  195.       A 32-bit value identifying the Security Parameters for this
  196.       datagram.  The value MUST NOT be zero.
  197.  
  198.    Initialization Vector (IV)
  199.  
  200.       The size of this field is variable, although it is constant for
  201.       all 3DES datagrams of the same SPI and IP Destination.  Octets are
  202.       sent in network order (most significant octet first) [RFC-1700].
  203.  
  204.       The size MUST be a multiple of 32-bits.  Sizes of 32 and 64 bits
  205.       are required to be supported.  The use of other sizes is beyond
  206.       the scope of this specification.  The size is expected to be
  207.       indicated by the key management mechanism.
  208.  
  209.       When the size is 32-bits, a 64-bit IV is formed from the 32-bit
  210.       value followed by (concatenated with) the bit-wise complement of
  211.       the 32-bit value.  This field size is most common, as it aligns
  212.       the Payload Data for both 32-bit and 64-bit processing.
  213.  
  214.       All conformant implementations MUST also correctly process a 64-
  215.       bit field size.  This provides strict compatibility with existing
  216.       hardware implementations.
  217.  
  218.          It is the intent that the value not repeat during the lifetime
  219.          of the encryption session key.  Even when a full 64-bit IV is
  220.          used, the session key SHOULD be changed at least as frequently
  221.          as 2**32 datagrams.
  222.  
  223.  
  224.  
  225.  
  226. Karn, et al                   Experimental                      [Page 4]
  227.  
  228. RFC 1851                        ESP 3DES                  September 1995
  229.  
  230.  
  231.    Payload Data
  232.  
  233.       The size of this field is variable.
  234.  
  235.       Prior to encryption and after decryption, this field begins with
  236.       the IP Protocol/Payload header specified in the Payload Type
  237.       field.  Note that in the case of IP-in-IP encapsulation (Payload
  238.       Type 4), this will be another IP header.
  239.  
  240.    Padding
  241.  
  242.       The size of this field is variable.
  243.  
  244.       Prior to encryption, it is filled with unspecified implementation
  245.       dependent (preferably random) values, to align the Pad Length and
  246.       Payload Type fields at an eight octet boundary.
  247.  
  248.       After decryption, it MUST be ignored.
  249.  
  250.    Pad Length
  251.  
  252.       This field indicates the size of the Padding field.  It does not
  253.       include the Pad Length and Payload Type fields.  The value
  254.       typically ranges from 0 to 7, but may be up to 255 to permit
  255.       hiding of the actual data length.
  256.  
  257.       This field is opaque.  That is, the value is set prior to
  258.       encryption, and is examined only after decryption.
  259.  
  260.    Payload Type
  261.  
  262.       This field indicates the contents of the Payload Data field, using
  263.       the IP Protocol/Payload value.  Up-to-date values of the IP
  264.       Protocol/Payload are specified in the most recent "Assigned
  265.       Numbers" [RFC-1700].
  266.  
  267.       This field is opaque.  That is, the value is set prior to
  268.       encryption, and is examined only after decryption.
  269.  
  270.          For example, when encrypting an entire IP datagram (Tunnel-
  271.          Mode), this field will contain the value 4, which indicates
  272.          IP-in-IP encapsulation.
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282. Karn, et al                   Experimental                      [Page 5]
  283.  
  284. RFC 1851                        ESP 3DES                  September 1995
  285.  
  286.  
  287. 3.  Algorithm
  288.  
  289.    The 3DES algorithm is a simple variant on the DES-CBC algorithm.  The
  290.    DES function is replaced by three rounds of that function, an
  291.    encryption followed by a decryption followed by an encryption, each
  292.    with independant keys, k1, k2 and k3.
  293.  
  294.    Note that when all three keys (k1, k2 and k3) are the same, 3DES is
  295.    equivalent to DES-CBC.  This property allows the 3DES hardware
  296.    implementations to operate in DES mode without modification.
  297.  
  298.    For more explanation and implementation information for Triple DES,
  299.    see [Schneier94].
  300.  
  301.  
  302.  
  303. 3.1.  Encryption
  304.  
  305.    Append zero or more octets of (preferably random) padding to the
  306.    plaintext, to make its modulo 8 length equal to 6.  For example, if
  307.    the plaintext length is 41, 5 octets of padding are added.
  308.  
  309.    Append a Pad Length octet containing the number of padding octets
  310.    just added.
  311.  
  312.    Append a Payload Type octet containing the IP Protocol/Payload value
  313.    which identifies the protocol header that begins the payload.
  314.  
  315.    Provide an Initialization Vector (IV) of the size indicated by the
  316.    SPI.
  317.  
  318.    Encrypt the payload with Triple DES (EDE mode), producing a
  319.    ciphertext of the same length.
  320.  
  321.    Octets are mapped to DES blocks in network order (most significant
  322.    octet first) [RFC-1700].  Octet 0 (modulo 8) of the payload
  323.    corresponds to bits 1-8 of the 64-bit DES input block, while octet 7
  324.    (modulo 8) corresponds to bits 57-64 of the DES input block.
  325.  
  326.    Construct an appropriate IP datagram for the target Destination, with
  327.    the indicated SPI, IV, and payload.
  328.  
  329.    The Total/Payload Length in the encapsulating IP Header reflects the
  330.    length of the encrypted data, plus the SPI, IV, padding, Pad Length,
  331.    and Payload Type octets.
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Karn, et al                   Experimental                      [Page 6]
  339.  
  340. RFC 1851                        ESP 3DES                  September 1995
  341.  
  342.  
  343. 3.2.  Decryption
  344.  
  345.    First, the SPI field is removed and examined.  This is used as an
  346.    index into the local Security Parameter table to find the negotiated
  347.    parameters and decryption key.
  348.  
  349.    The negotiated form of the IV determines the size of the IV field.
  350.    These octets are removed, and an appropriate 64-bit IV value is
  351.    constructed.
  352.  
  353.    The encrypted part of the payload is decrypted using Triple DES (DED
  354.    mode).
  355.  
  356.    The Payload Type is removed and examined.  If it is unrecognized, the
  357.    payload is discarded with an appropriate ICMP message.
  358.  
  359.    The Pad Length is removed and examined.  The specified number of pad
  360.    octets are removed from the end of the decrypted payload, and the IP
  361.    Total/Payload Length is adjusted accordingly.
  362.  
  363.    The IP Header(s) and the remaining portion of the decrypted payload
  364.    are passed to the protocol receive routine specified by the Payload
  365.    Type field.
  366.  
  367.  
  368.  
  369. Security Considerations
  370.  
  371.    Users need to understand that the quality of the security provided by
  372.    this specification depends completely on the strength of the Triple
  373.    DES algorithm, the correctness of that algorithm's implementation,
  374.    the security of the key management mechanism and its implementation,
  375.    the strength of the key [CN94], and upon the correctness of the
  376.    implementations in all of the participating nodes.
  377.  
  378.    Among other considerations, applications may wish to take care not to
  379.    select weak keys for any of the three DES rounds, although the odds
  380.    of picking one at random are low [Schneier94, p. 233].
  381.  
  382.    It was originally thought that DES might be a group, but it has been
  383.    demonstrated that it is not [CW92].  Since DES is not a group,
  384.    composition of multiple rounds of DES is not equivalent to simply
  385.    using DES with a different key.
  386.  
  387.    Triple DES with independent keys is not, as naively might be
  388.    expected, as difficult to break by brute force as a cryptosystem with
  389.    three times the keylength.  A space/time tradeoff has been shown
  390.    which can brute-force break triple block encryptions in the time
  391.  
  392.  
  393.  
  394. Karn, et al                   Experimental                      [Page 7]
  395.  
  396. RFC 1851                        ESP 3DES                  September 1995
  397.  
  398.  
  399.    naively expected for double encryption [MH81].
  400.  
  401.    However, 2DES can be broken with a meet-in-the-middle attack, without
  402.    significantly more complexity than breaking DES requires [ibid], so
  403.    3DES with independant keys is actually needed to provide this level
  404.    of security.  An attack on 3DES using two independent keys that is
  405.    somewhat (sixteen times) faster than any known for independent keys
  406.    has been shown [OW91].
  407.  
  408.    The cut and paste attack described by [Bell95] exploits the nature of
  409.    all Cipher Block Chaining algorithms.  When a block is damaged in
  410.    transmission, on decryption both it and the following block will be
  411.    garbled by the decryption process, but all subsequent blocks will be
  412.    decrypted correctly.  If an attacker has legitimate access to the
  413.    same key, this feature can be used to insert or replay previously
  414.    encrypted data of other users of the same engine, revealing the
  415.    plaintext.  The usual (ICMP, TCP, UDP) transport checksum can detect
  416.    this attack, but on its own is not considered cryptographically
  417.    strong.  In this situation, user or connection oriented integrity
  418.    checking is needed [RFC-1826].
  419.  
  420.    Although it is widely believed that 3DES is substantially stronger
  421.    than DES, as it is less amenable to brute force attack, it should be
  422.    noted that real cryptanalysis of 3DES might not use brute force
  423.    methods at all.  Instead, it might be performed using variants on
  424.    differential [BS93] or linear [Matsui94] cryptanalysis.  It should
  425.    also be noted that no encryption algorithm is permanently safe from
  426.    brute force attack, because of the increasing speed of modern
  427.    computers.
  428.  
  429.    As with all cryptosystems, those responsible for applications with
  430.    substantial risk when security is breeched should pay close attention
  431.    to developments in cryptography, and especially cryptanalysis, and
  432.    switch to other transforms should 3DES prove weak.
  433.  
  434.  
  435.  
  436. Acknowledgements
  437.  
  438.    Some of the text of this specification was derived from work by
  439.    Randall Atkinson for the SIP, SIPP, and IPv6 Working Groups.
  440.  
  441.    Comments should be submitted to the ipsec@ans.net mailing list.
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Karn, et al                   Experimental                      [Page 8]
  451.  
  452. RFC 1851                        ESP 3DES                  September 1995
  453.  
  454.  
  455. References
  456.  
  457.    [Bell95] Bellovin, S., "An Issue With DES-CBC When Used Without
  458.             Strong Integrity", Proceedings of the 32nd IETF, Danvers,
  459.             MA, April 1995.
  460.  
  461.    [BS93]   Biham, E., and Shamir, A., "Differential Cryptanalysis of
  462.             the Data Encryption Standard", Berlin: Springer-Verlag,
  463.             1993.
  464.  
  465.    [CN94]   Carroll, J.M., and Nudiati, S., "On Weak Keys and Weak Data:
  466.             Foiling the Two Nemeses", Cryptologia, Vol. 18 No. 23 pp.
  467.             253-280, July 1994.
  468.  
  469.    [CW92]   Campbell, K.W., and Wiener, M.J., "Proof that DES Is Not a
  470.             Group", Advances in Cryptology -- Crypto '92 Proceedings,
  471.             Berlin: Springer-Verlag, 1993, pp 518-526.
  472.  
  473.    [FIPS-46]
  474.             US National Bureau of Standards, "Data Encryption Standard",
  475.             Federal Information Processing Standard (FIPS) Publication
  476.             46, January 1977.
  477.  
  478.    [FIPS-46-1]
  479.             US National Bureau of Standards, "Data Encryption Standard",
  480.             Federal Information Processing Standard (FIPS) Publication
  481.             46-1, January 1988.
  482.  
  483.    [FIPS-74]
  484.             US National Bureau of Standards, "Guidelines for
  485.             Implementing and Using the Data Encryption Standard",
  486.             Federal Information Processing Standard (FIPS) Publication
  487.             74, April 1981.
  488.  
  489.    [FIPS-81]
  490.             US National Bureau of Standards, "DES Modes of Operation"
  491.             Federal Information Processing Standard (FIPS) Publication
  492.             81, December 1980.
  493.  
  494.    [Matsui94]
  495.             Matsui, M., "Linear Cryptanalysis method dor DES Cipher,"
  496.             Advances in Cryptology -- Eurocrypt '93 Proceedings, Berlin:
  497.             Springer-Verlag, 1994.
  498.  
  499.    [MH81]   Merle, R.C., and Hellman, M., "On the Security of Multiple
  500.             Encryption", Communications of the ACM, v. 24 n. 7, 1981,
  501.             pp. 465-467.
  502.  
  503.  
  504.  
  505.  
  506. Karn, et al                   Experimental                      [Page 9]
  507.  
  508. RFC 1851                        ESP 3DES                  September 1995
  509.  
  510.  
  511.    [OW91]   van Oorschot, P.C., and Weiner, M.J.  "A Known-Plaintext
  512.             Attack on Two-Key Triple Encryption", Advances in Cryptology
  513.             -- Eurocrypt '90 Proceedings, Berlin: Springer-Verlag, 1991,
  514.             pp. 318-325.
  515.  
  516.    [RFC-1800]
  517.             Postel, J., "Internet Official Protocol Standards", STD 1,
  518.             RFC 1800, USC/Information Sciences Institute, July 1995.
  519.  
  520.    [RFC-1700]
  521.             Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC
  522.             1700, USC/Information Sciences Institute, October 1994.
  523.  
  524.    [RFC-1825]
  525.             Atkinson, R., "Security Architecture for the Internet
  526.             Protocol", RFC-1825, Naval Research Laboratory, July 1995.
  527.  
  528.    [RFC-1826]
  529.             Atkinson, R., "IP Authentication Header", RFC-1826, Naval
  530.             Research Laboratory, July 1995.
  531.  
  532.    [RFC-1827]
  533.             Atkinson, R., "IP Encapsulating Security Protocol (ESP)",
  534.             RFC-1827, Naval Research Laboratory, July 1995.
  535.  
  536.    [Schneier94]
  537.             Schneier, B., "Applied Cryptography", John Wiley & Sons, New
  538.             York, NY, 1994.  ISBN 0-471-59756-2
  539.  
  540.    [Tuchman79]
  541.             Tuchman, W, "Hellman Presents No Shortcut Solutions to DES",
  542.             IEEE Spectrum, v. 16 n. 7, July 1979, pp. 40-41.
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562. Karn, et al                   Experimental                     [Page 10]
  563.  
  564. RFC 1851                        ESP 3DES                  September 1995
  565.  
  566.  
  567. Author's Address
  568.  
  569.    Questions about this memo can also be directed to:
  570.  
  571.       Phil Karn
  572.       Qualcomm, Inc.
  573.       6455 Lusk Blvd.
  574.       San Diego, California  92121-2779
  575.  
  576.       karn@unix.ka9q.ampr.org
  577.  
  578.  
  579.       Perry Metzger
  580.       Piermont Information Systems Inc.
  581.       160 Cabrini Blvd., Suite #2
  582.       New York, NY  10033
  583.  
  584.       perry@piermont.com
  585.  
  586.  
  587.       William Allen Simpson
  588.       Daydreamer
  589.       Computer Systems Consulting Services
  590.       1384 Fontaine
  591.       Madison Heights, Michigan  48071
  592.  
  593.       Bill.Simpson@um.cc.umich.edu
  594.           bsimpson@MorningStar.com
  595.  
  596.  
  597.  
  598.  
  599.  
  600.  
  601.  
  602.  
  603.  
  604.  
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618. Karn, et al                   Experimental                     [Page 11]
  619.  
  620.