Abstract:
A security mechanism suitable for wireless local area networks is disclosed that exhibits a reasonable trade-off between computation speed and resistance to attack. The illustrative embodiment can be implemented with operations that are quickly performed on most processors, and, therefore be in many cases reasonably implemented in software. The illustrative embodiment comprises modulo 2 additions, modulo 2 B  additions, bit rotations, and byte transpositions.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]    This application claims the benefit of U.S. Provisional Patent Application 60/396,286 filed Jul. 15, 2002 (Attorney Docket: 680-026us), which is incorporated by reference. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    The present invention relates to telecommunications in general, and, more particularly, to a cryptographic authentication system suitable for wireless local area networks.  
         BACKGROUND OF THE DISCLOSURE  
         [0003]    IEEE 802.11 is a wireless local area network protocol standard that includes a security mechanism called Wireless Equivalent Privacy or “WEP.” The goal of the IEEE 802.11&#39;s Wireless Equivalent Privacy was to provide a degree of privacy and authentication for transmissions that is “equivalent” to that provided by physical wiring.  
           [0004]    Unfortunately, the IEEE 802.11&#39;s Wireless Equivalent Privacy is flawed and an eavesdropper or spoofer can easily circumvent it. Therefore, the need exists for an improved security mechanism.  
         SUMMARY OF THE DISCLOSURE  
         [0005]    The present invention provides a secure telecommunications system that avoids some of the costs and disadvantages associated with secure telecommunications systems in the prior art. In particular, the illustrative embodiment of the present invention exhibits a reasonable trade-off between computation speed and resistance to attack. The illustrative embodiment can be implemented with operations that are quickly performed on most processors, and can, therefore, be reasonably implemented in software. The illustrative embodiment comprises modulo 2 additions, modulo 2 B  additions, bit rotations, and transpositions.  
           [0006]    The illustrative embodiment comprises a method for transforming a first message integrity codeword, L, and a second message integrity codeword, R, said method comprising:  
           [0007]    1) setting said second message integrity codeword, R, equal to the modulo 2 sum of said second message integrity codeword, R, plus said first message integrity codeword, L, after being rotated left 17 bits;  
           [0008]    2) setting said first message integrity codeword, L, equal to the modulo 2 B  sum of said first message integrity codeword, L, plus said second message integrity codeword, R;  
           [0009]    3) setting said second message integrity codeword, R, equal to the modulo 2 sum of said second message integrity codeword, R, plus a transposition of said first message integrity codeword, L;  
           [0010]    4) setting said first message integrity codeword, L, equal to the modulo 2 B  sum of said first message integrity codeword, L, plus said second message integrity codeword, R;  
           [0011]    5) setting said second message integrity codeword, R, equal to the modulo 2 sum of said second message integrity codeword, R, plus said first message integrity codeword, L, after being rotated left 3 bits;  
           [0012]    6) setting said first message integrity codeword, L, equal to the modulo 2 B  sum of said first message integrity codeword, L, plus said second message integrity codeword, R;  
           [0013]    7) setting said second message integrity codeword, R, equal to the modulo 2 sum of said second message integrity codeword, R, plus said first message integrity codeword, L, after being rotated right 2 bits; and  
           [0014]    8) setting said first message integrity codeword, L, equal to the modulo 2 B  sum of said first message integrity codeword, L, plus said second message integrity codeword, R; wherein B is a positive integer. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    [0015]FIG. 1 depicts a block diagram of the salient components of secure telecommunications system  100  in accordance with the illustrative embodiment of the present invention.  
         [0016]    [0016]FIG. 2 depicts a block diagram of the salient components of transmitter  101  in accordance with the illustrative embodiment.  
         [0017]    [0017]FIG. 3 depicts a flowchart of the salient tasks performed by transmitter  101  in accordance with the illustrative embodiment.  
         [0018]    [0018]FIG. 4 depicts a flowchart of the salient subtasks performed in task  304 .  
         [0019]    [0019]FIG. 5 depicts a block diagram of the salient subtasks performed in task  404 .  
         [0020]    [0020]FIG. 6 depicts a block diagram of the salient components of receiver  102  in accordance with the illustrative embodiment of the present invention.  
         [0021]    [0021]FIG. 7 depicts a flowchart of the salient tasks performed by receiver  102  in accordance with the illustrative embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0022]    [0022]FIG. 1 depicts a block diagram of the salient components of secure telecommunications system  100  in accordance with the illustrative embodiment of the present invention. Secure telecommunications system  100  comprises host computer  121  and host computer  122 , which are connected via cryptographic telecommunications system  123 . Cryptographic telecommunications system  123  comprises transmitter  101 , communications channel  110 , and receiver  102 , interconnected as shown.  
         [0023]    Host computer  121  is a computer system such as a desktop, notebook, or stylus-based machine, or even a network-based peripheral such as a printer, scanner, fax machine, or server. It will be clear to those skilled in the art how to make and use host computer  121 .  
         [0024]    Host computer  122  is a computer system such as a desktop, notebook, or stylus-based machine, or even a network-based peripheral such as a printer, scanner, fax machine, or server. It will be clear to those skilled in the art how to make and use host computer  122 . Either or both of host computer  121  and host computer  122  can be a network access point.  
         [0025]    Transmitter  101  receives an n byte message, m 0 , . . . , m n−1 , a B-Bit authentication key, K 0 , a B-Bit authentication key, K 1 , a B-Bit privacy key, P 0 , and a B-Bit privacy key, P 1 , wherein B and n are positive integers. In accordance with the illustrative embodiment, B=32, but it will be clear to those skilled in the art how to make and use embodiments of the present invention that have different values for B.  
         [0026]    From these, transmitter generates a ciphertext message, C, that can be transmitted over communications channel  110  to receiver  102 . Receiver  102  receives the ciphertext message, C, the authentication keys K 0  and K 1 , and the privacy keys P 0  and P 1 , and from them recovers the message, m 0 , . . . , M n−1 , and a 1-bit authentication indication, AI. The authentication indication, AI, indicates whether receiver  102  was able to authenticate that the ciphertext message, C, did, in fact, originate with an entity that had access to the authentication keys K 0  and K 1 . It will be clear to those skilled in the art how to make and use alternative embodiments of the present invention that have different length authentication keys and different length privacy keys.  
         [0027]    The details of transmitter  101  are described in detail below and with respect to FIGS. 2 through 5. The details of receiver  102  are described in detail below and with respect to FIGS. 6 and 7. It will be clear to those skilled in the art how to make and use communications channel  110 .  
         [0028]    [0028]FIG. 2 depicts a block diagram of the salient components of transmitter  101  in accordance with the illustrative embodiment. Transmitter  101  comprises message padder  201 , message integrity code generator  202 , and encryptor  203 , which are interconnected as shown. In accordance with the illustrative embodiment, message padder  201  and message integrity code generator  202  are implemented in software on a general-purpose processor, and encryptor  203  is implemented in special-purpose hardware. It will be clear to those skilled in the art, however, after reading this disclosure, how to make and use alternative embodiments of the present invention in which message padder  201 , message integrity code generator  202 , and encryptor  203  are implemented in any combination of software, general-purpose hardware, and special-purpose hardware. The operation of transmitter  101  is described in detail below and with respect to FIGS. 3, 4, and  5 .  
         [0029]    [0029]FIG. 3 depicts a flowchart of the salient tasks performed by transmitter  101  in accordance with the illustrative embodiment.  
         [0030]    At task  301 , message padder  201  receives an n byte message, m 0 , . . . , m n−1 , which represents the plaintext message to be transmitted securely to receiver  102 .  
         [0031]    At task  302 , message padder  201  pads the message, m 0 , . . . , m n−1 , at the end with a single byte with the value 0×5a and then between 4 and 7 zero bytes. The number of bytes is chosen so that the overall length of the message plus the padding is a multiple of 4. The message is then converted to a sequence of B-Bit words M 0 , . . . , M N−1  wherein N:=┌(n+5)/4┐. It will be clear to those skilled in the art, however, how to make and use alternative embodiments of the present invention that use different padding systems.  
         [0032]    At task  303 , message integrity code generator  202  receives the authentication keys K 0  and K 1 , and encryptor  203  receives the privacy keys P 0  and P 1 . It will be clear to those skilled in the art how to make and use alternative embodiments of the present invention in which tasks  301  and  302  and task  303  are performed concurrently or in a different order.  
         [0033]    At task  304 , message integrity code generator  202  generates the first message integrity codeword, L, and the second message integrity codeword, R, based on the message words M 0 , . . , M N−1 , and the authentication keys K 0  and K 1 . The procedure that message integrity code generator  202  uses to generate the first message integrity codeword, L, and the second message integrity codeword, R, is described in detail below and with respect to FIGS. 4 and 5.  
         [0034]    At task  305 , encryptor  203  encrypts, in well-known fashion, the message words M 0 , . . . , M N−1 , and the first message integrity codeword, L, and the second message integrity codeword, R, with the privacy keys P 0  and P 1 , as the key in accordance with RC4 symmetric cryptosystem to produce the ciphertext message C. It will be clear to those skilled in the art how to make and use embodiments of the present invention that use other cryptosystems.  
         [0035]    At task  306 , transmitter  101  transmits the ciphertext message C onto communications channel  110  in well-known fashion.  
         [0036]    [0036]FIG. 4 depicts a flowchart of the salient subtasks performed in task  304 .  
         [0037]    At subtask  401 , message integrity codeword generator  202  initializes the first message integrity codeword, L, and the second message integrity codeword, R, by setting the first message integrity codeword, L, equal to the first authentication key, K 0 , and by setting the second message integrity codeword, R, equal to the second key, K 1 .  
         [0038]    At subtask  402 , message integrity codeword generator  202  sets a placeholder variable i equal to zero, wherein i is a non-negative integer, as shown in Equation 1.  
         i:=0   (Eq. 1)  
         [0039]    At subtask  403 , message integrity codeword generator  202  sets the first message integrity codeword, L, equal to the modulo 2 sum of the first message integrity codeword, L, plus message word M i , as shown in Equation 2.  
         L:=L⊕M i    (Eq. 2)  
         [0040]    At subtask  404 , message integrity codeword generator  202  sets the first message integrity codeword, L, and the second message integrity codeword, R, equal to a block transformation of the first message integrity codeword, L, and the second message integrity codeword, R, as shown in Equation 3.  
         (L, R):=b(L, R)   (Eq. 3)  
         [0041]    This transformation is described in detail below and with respect to FIG. 5.  
         [0042]    At subtask  405 , message integrity codeword generator  202  increments the value of the variable i.  
         [0043]    At subtask  406 , message integrity codeword generator  202  checks whether the value of the variable i is equal to N. If it is, then task  304  ends and control proceeds to task  305 ; otherwise control returns to subtask  403 .  
         [0044]    [0044]FIG. 5 depicts a block diagram of the salient subtasks performed in task  404 .  
         [0045]    At subtask  501 , message integrity codeword generator  202  sets the first message integrity codeword, L, and the second message integrity codeword, R, by setting the second message integrity codeword, R, equal to the modulo 2 sum of the second message integrity codeword, R, plus the first message integrity codeword, L, after being rotated left 17 bits. This is shown in Equation 4.  
         R:=R⊕(L         17)   (Eq. 4)  
         [0046]    wherein the symbol           represents the rotate left operator. It will be clear to those skilled in the art how to make and use alternative embodiments of the present invention in which the first message integrity codeword, L, is rotated a different number of bits or is rotated right.  
         [0047]    At subtask  502 , message integrity codeword generator  202  sets the first message integrity codeword, L, equal to the modulo 2 B  sum of the first message integrity codeword, L, plus the second message integrity codeword, R, as shown in Equation 5.  
           L :=( L+R ) mod 2 B    (Eq. 5)  
         [0048]    wherein the symbol + represents the summation operator.  
         [0049]    At subtask  503 , message integrity codeword generator  202  sets the second message integrity codeword, R, equal to the modulo 2 sum of the second message integrity codeword, R, plus a transposition of the first message integrity codeword, L, as shown in Equation 6.  
         R:=R⊕XSWAP(L)   (Eq. 6)  
         [0050]    wherein the transposition XSWAP(L) swaps the position of the two least significant bytes of L with each other and swaps the position of the two most significant bytes of L with each other.  
         [0051]    At subtask  504 , message integrity codeword generator  202  sets the first message integrity codeword, L, equal to the modulo 2 B  sum of the first message integrity codeword, L, plus the second message integrity codeword, R, as shown in Equation 7.  
           L :=( L+R ) mod 2 B    (Eq. 7)  
         [0052]    At subtask  505 , message integrity codeword generator  202  sets the second message integrity codeword, R, equal to the modulo 2 sum of the second message integrity codeword, R, plus the first message integrity codeword, L, after being rotated left 3 bits, as shown in Equation 8.  
         R:=R⊕(L         3)   (Eq. 8)  
         [0053]    It will be clear to those skilled in the art how to make and use alternative embodiments of the present invention in which the first message integrity codeword, L, is rotated a different number of bits or is rotated right.  
         [0054]    At subtask  506 , message integrity codeword generator  202  sets the first message integrity codeword, L, equal to the modulo 2 B  sum of the first message integrity codeword, L, plus the second message integrity codeword, R, as shown in Equation 9.  
           L :=( L+R ) mod 2 B    (Eq. 9)  
         [0055]    It will be clear to those skilled in the art how to make and use alternative embodiments of the present invention in which the first message integrity codeword, L, is rotated a different number of bits or is rotated right.  
         [0056]    At subtask  507 , message integrity codeword generator  202  sets the second message integrity-codeword, R, equal to the modulo 2 sum of the second message integrity codeword, R, plus the first message integrity codeword, L, after being rotated right 2 bits, as shown in Equation 10.  
         R:=R⊕(L         2)   (Eq. 10)  
         [0057]    wherein the symbol           represents the rotate right operator. It will be clear to those skilled in the art how to make and use alternative embodiments of the present invention in which the first message integrity codeword, L, is rotated a different number of bits or is rotated left.  
         [0058]    At subtask  508 , message integrity codeword generator  202  sets the first message integrity codeword, L, equal to the modulo 2 B  sum of the first message integrity codeword, L, plus the second message integrity codeword, R, as shown in Equation 11.  
           L :=( L+R ) mod 2 B    (Eq. 11)  
         [0059]    [0059]FIG. 6 depicts a block diagram of the salient components of receiver  102  in accordance with the illustrative embodiment of the present invention. Receiver  102  comprises decryptor  601 , message integrity code generator  602 , and message integrity code comparator  603 . In accordance with the illustrative embodiment, decryptor  601  is implemented in special-purpose hardware, and message integrity code generator  602  and message integrity code comparator  603  are implemented in software on a general-purpose processor. It will be clear to those skilled in the art, however, after reading this disclosure, how to make and use alternative embodiments of the present invention in which decryptor  601 , message integrity code generator  602 , and message integrity code comparator  603  are implemented in any combination of software, general-purpose hardware, and special-purpose hardware. The operation of transmitter  201  is described in detail below and with respect to FIG. 7.  
         [0060]    [0060]FIG. 7 depicts a flowchart of the salient tasks performed by receiver  102  in accordance with the illustrative embodiment of the present invention.  
         [0061]    At task  701 , decryptor  601  receives the ciphertext message C from communications channel  110 , in well-known fashion.  
         [0062]    At task  702 , decryptor  601  and message integrity code generator  602  receive the first authentication key, K 0 , and the second key, K 1 . It will be clear to those skilled in the art that tasks  701  and  702  can be performed concurrently or in a different order in some alternative embodiments of the present invention.  
         [0063]    At task  703 , decryptor  601  decrypts the ciphertext message C with the privacy keys P 0  and P 1 , as the key to recover the candidate message words M 0 , . . . , M N−1 , the candidate message integrity codewords L C  and R C . The recovered message words and message integrity codewords are called “candidate” words and codewords at this point because they might have been fabricated by a spoofer and have not yet been authenticated by receiver  102 . As part of task  703 , decryptor  601  feeds the candidate message words M 0 , . . . , M N−1  to message integrity codeword generator  602  and feeds the candidate message integrity codewords L C  and R C  to message integrity codeword comparator  603 .  
         [0064]    At task  704 , message integrity codeword generator  602  generates the first benchmark message integrity codeword, L B , and the second benchmark message integrity codeword, R B , based on the candidate message words M 0 , . . . , M N−1 , and the authentication keys K 0  and K 1 . The function of message integrity codeword generator  602  is identical to the function performed by message integrity codeword generator  202 , and task  704  is identical to task  304 . The generated message integrity codewords L B  and R B  are called “benchmark” codewords because they are the touchstone against which receiver  102  will judge the authenticity of the candidate codewords L C  and R C  recovered in task  703 .  
         [0065]    At task  705 , decryptor  601 :  
         [0066]    (i) depads the candidate message words M 0 , . . . , M N−1  to produce the candidate message, m 0 , . . . , M n−1 ;  
         [0067]    (ii) outputs the candidate message, m 0 , . . . , m n−1  to host computer  122 ;  
         [0068]    (iii) outputs the candidate message words M 0 , . . . , M N−1  to message integrity codeword generator  602 , and  
         [0069]    (iv) outputs the benchmark message integrity codewords L B  and R B  to message integrity codeword comparator  603 .  
         [0070]    At task  706 , message integrity codeword comparator  603  authenticates the candidate message words M 0 , . . , M N−1  when and only when:  
         [0071]    1. the first benchmark message integrity codeword, L B , equals the first candidate message integrity codeword, L C , and  
         [0072]    2. the second benchmark message integrity codeword, R B , equals the second candidate message integrity codeword, R C .  
         [0073]    As part of task  706 , message integrity codeword comparator  603  outputs the authentication indication, AI, that indicates whether or not the candidate message words M 0 , . . . , M N−1  output in task  705  are authenticated or not.  
         [0074]    It is to be understood that the above-described embodiments are merely illustrative of the present invention and that many variations of the above-described embodiments can be devised by those skilled in the art without departing from the scope of the invention. It is therefore intended that such variations be included within the scope of the following claims and their equivalents.