Abstract:
A method is described for defining a reserved pattern of symbols, receiving in a crypto-module an input stream including sequential input symbols, applying a cipher to the input stream in the crypto-module so as to generate an intermediate stream including sequential output symbols corresponding respectively to the input symbols, and converting the intermediate stream to an output stream from the crypto-module by comparing successive groups of the input symbols and the corresponding output symbols to the reserved pattern and, upon finding a match to the reserved pattern in a given group, substituting the input symbols in the group into the intermediate stream in place of the corresponding output symbols. Related hardware and systems are also described.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to data encryption, and specifically to techniques for controlling the output of a cipher. 
       BACKGROUND OF THE INVENTION 
       [0002]    The process of encryption converts ordinary information (referred to as “plaintext”) into unintelligible “ciphertext.” Decryption is the reverse process, converting ciphertext back to plaintext. Various algorithms—known as “ciphers”—are used for encryption and the reverse decryption process. The cipher uses a secret parameter, known as a “key,” in carrying out the encryption and decryption processes. 
         [0003]    Various types of ciphers are known in the art. For example, a stream cipher is a symmetric-key cipher in which plaintext bits are combined with a stream of pseudorandom cipher bits (referred to as a “keystream”), most commonly by an exclusive-or (XOR) operation. The plaintext symbols are typically encrypted one at a time, and the transformation of successive symbols varies during the encryption. 
         [0004]    A block cipher operates on data blocks of fixed length, such as 64 or 128 bits. There are certain standard ways, however, to build a stream cipher based on an arbitrary block cipher. For example, output feedback (OFB) mode encryption uses an encryption function E to generate a sequence of keystream blocks O i , each based on the encryption key and on the preceding keystream block. The successive keystream blocks are XORed with the successive plaintext blocks P i  to give the ciphertext blocks C i . Because of the symmetry of the XOR operation, encryption and decryption are exactly the same: 
         [0000]    
       
      
       C 
       i 
       =P 
       i 
       ⊕O 
       i  
      
     
         [0000]    
       
      
       P 
       i 
       =C 
       i 
       ⊕O 
       i  
      
     
         [0000]        O   i   =E   K ( O   i−1 ) 
         [0000]        O   0   =IV   (1)
 
         [0000]    (IV is an initialization vector, which is used to generate the first keystream block, and K is a key.) 
         [0005]    As another example, in cipher feedback (CFB) mode, each keystream block is based on the encryption key and on the preceding ciphertext block: 
         [0000]        C   i   =E ( C   i−1 )⊕ P   i  
 
         [0000]        P   i   =E ( C   i−1 )⊕ C   i  
 
         [0000]        C   0   =IV   (2)
 
         [0006]    (Since the ciphertext C i  is determined by the plaintext P i , the encryption function at any point may equivalently be framed as a function of the preceding plaintext blocks.) In this case, decryption is similar, but not identical, to the encryption operation. 
         [0007]    In some applications, only part of a plaintext stream is encrypted, while other parts are transmitted in the clear. For example, U.S. Pat. No. 7,151,833, whose disclosure is incorporated herein by reference, describes a method of selectively encrypting and decoding digital video content. Certain packets are selected for encryption according to a selection criterion, wherein the selected packets exclude packets containing start of frame (SOF) headers. The selected packets are encrypted while retaining the packets containing the SOF headers unencrypted. In decoding the selectively-encrypted digital video content, offsets are calculated for at least one of the I frames and P frames from the SOF headers, and the calculated offsets are stored as an offset table. The offset table can then be accessed to enable trick play of the selectively-encrypted digital video content. 
       SUMMARY OF THE INVENTION 
       [0008]    Common modes of encryption generate ciphertext that may comprise any arbitrary sequence of symbols. In some applications, however, a certain word or words (i.e., patterns of symbols) may be reserved, and it is desirable that these reserved words not appear in the ciphertext. 
         [0009]    There is therefore provided, in accordance with an embodiment of the present invention, a method for data encryption, including defining a reserved pattern of symbols and receiving in a crypto-module an input stream including sequential input symbols. A cipher is applied to the input stream in the crypto-module so as to generate an intermediate stream including sequential output symbols corresponding respectively to the input symbols. The intermediate stream is converted to an output stream from the crypto-module by comparing successive groups of the input symbols and the corresponding output symbols to the reserved pattern and, upon finding a match to the reserved pattern in a given group, substituting the input symbols in the group into the intermediate stream in place of the corresponding output symbols. 
         [0010]    In a disclosed embodiment, the method includes transmitting the output stream as a sequence of data records including respective headers and payloads, wherein the pattern is indicative of the headers, and applying the cipher includes encrypting the payloads, while the headers are unencrypted. 
         [0011]    In one embodiment, comparing the successive groups includes comparing each symbol in the reserved pattern to a corresponding input symbol and a corresponding output symbol in each given group, and finding the match when each of the symbols in the reserved pattern matches at least one of the corresponding input symbol and the corresponding output symbol. 
         [0012]    Applying the cipher may include applying an output feedback (OFB) mode encryption or a cipher feedback (CFB) mode encryption to the input stream. When the reserved pattern includes N symbols, the CFB mode encryption uses a feedback loop including a delay no less than N symbols in generating the cipher. 
         [0013]    There is also provided, in accordance with an embodiment of the present invention, apparatus for data processing, including an encryption module, which is configured to apply a cipher to an input stream including sequential input symbols so as to generate an intermediate stream including sequential output symbols corresponding respectively to the input symbols. A matching module is configured to convert the intermediate stream to an output stream by comparing successive groups of the input symbols and the corresponding output symbols to a reserved pattern of symbols and, upon finding a match to the reserved pattern in a given group, substituting the input symbols in the group into the intermediate stream in place of the corresponding output symbols. 
         [0014]    There is additionally provided, in accordance with an embodiment of the present invention, a computer software product, including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive an input stream including sequential input symbols, to apply a cipher to the input stream so as to generate an intermediate stream including sequential output symbols corresponding respectively to the input symbols, and to convert the intermediate stream to an output stream by comparing successive groups of the input symbols and the corresponding output symbols to a reserved pattern of symbols and, upon finding a match to the reserved pattern in a given group, substituting the input symbols in the group into the intermediate stream in place of the corresponding output symbols. 
         [0015]    There is further provided, in accordance with an embodiment of the present invention, a system for data communication, including a server including a crypto-module, which includes an encryption module, which is configured to apply a cipher to an input stream including sequential input symbols so as to generate an intermediate stream including sequential output symbols corresponding respectively to the input symbols. A matching module is configured to convert the intermediate stream to an encrypted output stream by comparing successive groups of the input symbols and the corresponding output symbols to a reserved pattern of symbols and, upon finding a match to the reserved pattern in a given group, substituting the input symbols in the group into the intermediate stream in place of the corresponding output symbols. A transmitter is coupled to transmit the encrypted output stream over a network to a client. 
         [0016]    There is moreover provided, in accordance with an embodiment of the present invention, a system for data communication, including a receiver, which is coupled to receive from a network an encrypted input stream including sequential input symbols. A client device includes a crypto-module, which includes an encryption module, which is configured to apply a cipher to the input stream so as to generate an intermediate stream including sequential output symbols corresponding respectively to the input symbols. A matching module is configured to convert the intermediate stream to a decrypted output stream by comparing successive groups of the input symbols and the corresponding output symbols to a reserved pattern of symbols and, upon finding a match to the reserved pattern in a given group, substituting the input symbols in the group into the intermediate stream in place of the corresponding output symbols. 
         [0017]    There is furthermore provided, in accordance with an embodiment of the present invention, a method for data encryption, which includes defining a reserved pattern of symbols and receiving in a crypto-module an input stream comprising sequential input symbols. A cipher and interleaving procedure is applied to the input stream in the crypto-module so as to generate an output stream including a sequence of ciphered symbols interleaved with one of the input symbols at each location in the sequence that corresponds to an occurrence of the reserved pattern. 
         [0018]    In disclosed embodiments, the output stream contains a number of output symbols, including the ciphered symbols and the interleaved input symbols, that is equal to the number of the input symbols in the input stream. 
         [0019]    The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0020]      FIG. 1  is a block diagram that schematically illustrates a system for encrypted communications, in accordance with an embodiment of the present invention; 
           [0021]      FIG. 2  is a block diagram that schematically illustrates an encryptor, in accordance with an embodiment of the present invention; 
           [0022]      FIG. 3  is a block diagram that schematically illustrates an encryptor, in accordance with another embodiment of the present invention; and 
           [0023]      FIG. 4  is a block diagram that schematically illustrates a decryptor, in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
       [0024]    In some video streaming formats, such as Motion Picture Experts Group (MPEG) compression and transmission formats, the clear (unencrypted) stream comprises records of variable length. These records start from “start codes” that are guaranteed not to appear in any position in the stream other than the record headers. For example, in MPEG2 and MPEG4, the start codes are 32-bit sequences, starting from a 24-bit “prefix” pattern “000000000000000000000001” that never appears in the payload. It is thus possible to distinguish a record header in both forward and backward search through the MPEG stream. 
         [0025]    When the stream is encrypted, it is desirable to leave the record headers in the clear, in order to preserve the capability of performing a search in the stream without decrypting it. With current methods of encryption, however, it may happen that encrypting an arbitrary stream bit pattern with an arbitrary key will cause the encrypted payload to contain what looks like a start code. It may thus become impossible to distinguish in the encrypted stream between a record header and a part of the encrypted payload that accidentally includes a start code. 
         [0026]    Embodiments of the present invention that are described hereinbelow provide methods and systems for encryption of a stream of symbols in which certain plaintext patterns (referred to herein as “reserved patterns”) are preserved in the ciphertext. At the same time, the disclosed methods guarantee that the ciphertext will not contain any spurious appearances of the reserved patterns resulting from encryption of arbitrary plaintext (not containing any of the reserved patterns), regardless of the key that is used. These methods are able to encode all possible n-bit plaintext sequences into pattern-free sequences of the same length, so that the length of the encrypted stream is exactly equal to the length of the clear stream. This feature is important because otherwise, extra information must be supplied in order to enable locating the reserved patterns in the encrypted stream. 
         [0027]    In the embodiments that are described hereinbelow, an encryption module (referred to herein simply as an “encryptor”) selects certain symbols of plaintext input that are not to be encrypted, i.e., they are passed through to the output ciphertext without modification by the keystream. The selection is based on the predefined reserved pattern or patterns. The encryptor applies a cipher and interleaving procedure to the input stream so as to generate an output stream in which the sequence of ciphered symbols is interleaved with one of the input symbols at each location in the sequence that corresponds to an occurrence of the reserved pattern. 
         [0028]    In some embodiments, the encryptor applies a cipher to the input stream so as to generate an intermediate stream comprising a sequence of output symbols, each corresponding respectively to one of the input symbols. The encryptor then compares successive groups of the input symbols and the corresponding output symbols to each reserved pattern. Upon finding a match to a reserved pattern in a given group of the input and output symbols, the encryptor substitutes the input symbols in the group into the intermediate stream in place of the corresponding output symbols. 
         [0029]    These substitutions convert the intermediate stream into an output ciphertext stream in which a given reserved pattern will appear only at locations at which it occurred in the input plaintext. If the plaintext does not contain the reserved pattern (for example, when encrypting only the payloads, and not the headers, in a MPEG stream), then the ciphertext will not contain the pattern either. Decryption operates in a symmetrical, or nearly symmetrical, manner to encryption, depending on the choice of cipher. 
         [0030]    A number of specific implementation examples are presented below, showing how common types of stream ciphers may be modified to handle reserved patterns in this fashion. The principles of the present invention, however, may similarly be applied to stream ciphers of substantially any other type, including block ciphers that have been converted to stream ciphers. (Methods for performing such conversions are known in the art.) 
         [0031]    For convenience and clarity, the encryptors and decryptors in the examples presented below are described as operating on single-bit symbols, but they may similarly operate on substantially any sort of symbol alphabet. 
         [0032]    As will be seen in the examples below, decryptors that decrypt symbol streams in accordance with embodiments of the present invention are very similar, or even identical, in structure and operation to the corresponding encryptors that create such symbol streams. Therefore, the term “crypto-module” is used in the present patent application and in the claims to refer collectively to such encryptors and decryptors and should be understood as embracing both encryptors and decryptors within its scope. 
       System Description 
       [0033]      FIG. 1  is a block diagram that schematically illustrates a system  20  for encrypted communications, in accordance with an embodiment of the present invention. This system is shown here as an example of an application in which the principles of the present invention may be applied. The encryption and decryption techniques that are described hereinbelow, however, are in no way limited to the context of this illustrative embodiment, and may be applied in substantially any setting in which encryption is used, whether or not associated with communications. 
         [0034]    In system  20 , a server  22  transmits encrypted data to a client  24 . In this example, the data are assumed to comprise MPEG video broadcast media, which are transmitted over a wireless link between a transmitter  26 , a satellite  28 , and a receiver  30 . Alternatively, server  22  and client  24  may communicate over networks of other types, including both wireless networks and terrestrial networks, such as a cable television network or the Internet, with appropriate changes to the transmitter and receiver, as will be apparent to those skilled in the art. In the pictured embodiment, server may be operated by a video broadcast distributor, while client  24  comprises a television set-top box or other receiving device. The video broadcast distributor transmits the media in encrypted form to ensure that only legitimate clients can decrypt and play the content. To enable efficient seeking (such as fast forward and reverse) through the media, the MPEG prefix bit pattern, 000000000000000000000001, is reserved in server  22 , which encrypts the MPEG stream in such a way that the pattern appears only in the record headers of the transmitted stream, and not in the payloads. 
         [0035]    Server  22  comprises or is coupled to a media repository  32 , which contains digital media content. A compression module  34  compresses the digital media data and encapsulates the compressed data in records of a suitable transport stream, such as MPEG 2 or MPEG 4 packets. Alternatively, server  22  may receive the transport stream already in compressed and encapsulated form. 
         [0036]    A demultiplexer  36  separates the MPEG record headers from the payloads. In this example, it is assumed that the headers are transmitted without encryption, in order to enable client  24  to read the headers without prior decryption. For this purpose, the demultiplexer finds occurrences of the prefix in the input stream, and then extracts the prefix and the complete record header that follows it, in accordance with the applicable standard. Alternatively, the headers may be encrypted, as well. The record payloads are encrypted by an encryptor  38 , which is described in greater detail hereinbelow. The encryptor is designed so that as long as the reserved pattern does not appear in the plaintext payloads, it will be guaranteed not to appear in the ciphertext output, as well. A multiplexer  40  recombines the headers with the appropriate encrypted payloads for transmission over the satellite link. 
         [0037]    Optionally, the encryption function E that is applied to each record may depend on the record header (or on a certain part of the header). If the transport format permits, the record header may include a random field, in order to ensure that E changes from record to record. Changing the encryption function in this manner helps to protect against malicious decryption, particularly when OFB mode is used. 
         [0038]    Client  24  receives the encrypted transport stream into a buffer memory  42 . A search module  44  enables the client, typically under user control, to search forward or back through the content in the memory by detecting the prefixes and then reading the associated records. A decryptor  46  decrypts the encrypted payloads (while leaving the plaintext headers untouched), as described in detail hereinbelow. A decompression module  48  converts the compressed records into an uncompressed video stream, which may then be output to a display  50 . 
         [0039]    For efficient processing, encryptor  38  and decryptor  46  typically comprise dedicated hardware logic circuits, in the form of an application-specific integrated circuit (ASIC), field programmable gate array (FPGA), or full-custom integrated circuit, or a combination of such devices. Alternatively or additionally, some or all of the functions of the encryptor and decryptor may be carried out by a programmable processor, such as a microprocessor or digital signal processor (DSP), under the control of suitable software. This software may be downloaded to the processor in electronic form, over a network, for example. Alternatively or additionally, the software may be stored on tangible storage media, such as optical, magnetic, or electronic memory media. Demultiplexer  36  and multiplexer  40  may similarly be implemented in either hardware or software or a combination of hardware and software components. The remaining components of system  20  are standard elements, whose construction will be apparent to those skilled in the art. 
       OFB Mode Encryption with Reserved Patterns 
       [0040]      FIG. 2  is a block diagram that schematically shows details of encryptor  38 , in accordance with an embodiment of the present invention. In this embodiment, the encryptor uses a form of OFB mode encryption (as defined in equations (1) above), which is modified so as to eliminate spurious occurrences of a reserved pattern, or patterns, in the output stream. Decryptor  46  in this case has the same form and mode of operation as encryptor  38 . 
         [0041]    A cipher encryption module  60  computes the encryption function E, as defined above. E may comprise any suitable function known in the art, such as the well-known functions of the Advanced Encryption Standard (AES) or Data Encryption Standard (DES). (Alternatively, the encryption function may be a native stream cipher, not based on any block cipher, such as the RC4 stream cipher, without any feedback.) In the present embodiment, the successive keystream bits o i  generated by module  60  are combined with the input bits p i  of an input stream  62  by a XOR operation  64 , to generate an intermediate stream  66  of output bits s i . (Alternatively, other types of encryption operations, not limited to XOR, may be applied to the input symbols, which are not necessarily bits. It is useful that the encryption operation be self-inverse in order to enable symmetrical encryption and decryption, but any invertible operation may be used.) 
         [0042]    A matching module  68  compares successive groups of input bits p i  and the corresponding output bits s i  to the reserved pattern, and generates an output stream  70  of bits c i . If the reserved pattern is n bits long, then the groups of input and output bits compared by module  68  will likewise be n bits long, in a sliding window over the input and intermediate streams. Ordinarily, as long as there is no match to the reserved pattern, module  68  passes output bits s i  to the output stream, i.e., c i =s i . If either the input bit p i  or the output bit s i  (or both) at each bit position within the window matches the bit in the reserved pattern, for all bits within a given window, however, then module  68  substitutes the input bits for the output bits in that window in output stream  70 , i.e., c i =p i . In this manner, it is guaranteed that the reserved pattern will not appear in the output stream except where it appears in the input stream. 
         [0043]    In more formal terms, encryption of a given plaintext p 1 p 2  . . . p L  will yield a sequence of pairs of symbols {p 1 ,s i }, {p 2 , s 2 }, . . . {p L ,s L }, wherein s i =o i ⊕p i . A given reserved pattern v 1 v 2  . . . v n  matches a subsequence of the sequence of pairs {p k+1 ,s k+1 } {P k+2 ,S k+2 } . . . , {p k+n ,s k+n } if for any i between 1 and n either v i =p k+i  or v i =s k+i . The algorithm carried out by encryptor  38  may then be expressed in the following form: 
         [0000]                                                                                          TABLE I               OFB MODE WITH RESERVED PATTERNS                                    For i=1..L           {                c i  = s i  = o i ⊕p i             For each pattern v 1 v 2 ...v n  ∈T                If n≦i                If v 1 v 2 ...v n  matches {p i−n+1 ,s i−n+1 },            {p i−n+2 ,s i−n+2 },...,{p i ,s i }                For j =i−n+1..i                c j  = p j                  }           Output c 1 c 2 ...c L                          
If the plaintext contains no reserved patterns, then the ciphertext produced by this algorithm will not contain any reserved patterns either. As noted above, the decryption algorithm in this example is identical to the encryption algorithm.
 
       CFB Mode Encryption with Reserved Patterns 
       [0044]      FIG. 3  is a block diagram that schematically shows details of an encryptor  80 , in accordance with another embodiment of the present invention. In this case, the encryptor implements a modified version of the CFB algorithm, as defined above by equations (2). Encryptor  80  may be substituted for encryptor  38  in system  20  ( FIG. 1 ). The functional blocks of encryptor  80  may be the same as those in encryptor  38 , although the feedback connection between the blocks is different. Therefore, for convenience and clarity, the elements of encryptor  80  are labeled with the same numbers as the corresponding elements in encryptor  38  ( FIG. 2 ). Matching module  68  in encryptor  80  carries out the same function as described above. 
         [0045]    The encryption algorithm carried out by encryptor  80  is also the same as that shown in Table I, except that in CFB mode, the keystream bits o i  are computed using feedback from output stream  70 , rather than the previous keystream values as in OFB mode. The feedback path from output stream  70  to cipher encryption module  60  contains a delay  82  that is at least as long as the longest reserved pattern used by matching module  68 . The reason for the delay is to ensure that any substitution of plaintext bits p i  for intermediate bits s i  into the output stream bits c i  is completed before those output stream bits are fed back into module  60 . 
         [0046]      FIG. 4  is a block diagram that schematically shows details of a CFB mode decryptor  90 , in accordance with an embodiment of the present invention. When encryptor  80  ( FIG. 3 ) is used in server  22 , decryptor  90  may be used in place of decryptor  46  ( FIG. 1 ) in client  24 . Output stream  70  of encryptor  80  is the input stream to decryptor  90 . Cipher encryption module  60  implements the same encryption function E as the corresponding module in encryptor  80 , but with input from stream  70 , via a delay  92 , equal in duration to delay  82 . The keystream bits generated by module  60  are combined with the ciphertext bits c i  from stream  70  by XOR operation  64 , to generate an intermediate stream  94  of decrypted bits s i . Matching module  68  compares successive groups of bits c i  and the corresponding bits s i  to the reserved pattern, and generates the final plaintext stream  96  of bits p i . 
         [0047]    The algorithms carried out by encryptor  80  and decryptor  90  may be expressed formally as follows, wherein N is the length of the longest reserved pattern checked by the matching module: 
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                 TABLE II 
               
               
                   
               
               
                 CFB MODE ENCRYPTION WITH RESERVED PATTERNS 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 For i=1..L 
               
               
                   
                 { 
               
             
          
           
               
                   
                 c i  = s i  = E(i,c 0 ...c i−N ) ⊕p i   
               
               
                   
                 For each pattern v 1 v 2 ...v n  ∈T 
               
             
          
           
               
                   
                 If n≦i 
               
             
          
           
               
                   
                 If v 1 v 2 ...v n  matches {p i−n+1 ,s i−n+1 }, 
               
               
                   
                  {p i−n+2 ,s i−n+2 },...,{p i ,s i } 
               
             
          
           
               
                   
                 For j=i−n+1..i 
               
             
          
           
               
                   
                 c j  = p j   
               
             
          
           
               
                   
                 } 
               
               
                   
                 Output c 1 c 2 ...c L   
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                 TABLE III 
               
               
                   
               
               
                 CFB MODE DECRYPTION WITH RESERVED PATTERNS 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 For i=1..L 
               
               
                   
                 { 
               
             
          
           
               
                   
                 p i  = s i  = E(i,c 0 ...c i−N ) ⊕c i   
               
               
                   
                 For each pattern v 1 v 2 ...v n  ∈T 
               
             
          
           
               
                   
                 If n≦i 
               
             
          
           
               
                   
                 If v 1 v 2 ...v n  matches {c i−n+1 ,s i−n+1 }, 
               
               
                   
                  {c i−n+2 ,s i−n+2 },...,{c i ,s i } 
               
             
          
           
               
                   
                 For j =i−n+1..i 
               
             
          
           
               
                   
                 p j  = c j   
               
             
          
           
               
                   
                 } 
               
               
                   
                 Output p 1 p 2 ...p L   
               
               
                   
                   
               
             
          
         
       
     
         [0048]    Although the specific embodiments shown in the figures above generate and operate on an intermediate stream, other implementations of the algorithms presented in the tables may, for example, carry out the operations of ciphering and interleaving the input symbols in the output stream in a single stage, without an explicit intermediate stream. Such alternative implementations are also considered to be within the scope of the present invention. 
         [0049]    It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.