Key ladder apparatus and method

In one embodiment a method, apparatus and system for is described for receiving a first input including a first decryption key and a second input including an encrypted second decryption key at a cryptographic decryption apparatus, the encrypted second decryption key to be decrypted by the cryptographic apparatus according to the first decryption key, storing a value of a key ladder length in a first register by a cryptographic processor, and using the stored value as a loop index by the cryptographic processor for a number of iterations of the cryptographic decryption apparatus executed as a loop, wherein at one stage in the loop execution of the cryptographic decryption apparatus, the second input includes the key ladder length, wherein the loop operation of the cryptographic decryption apparatus operates for a number of iterations equal to an initial value of the loop index. Related methods, apparatuses and systems are also described.

TECHNICAL FIELD

The present disclosure generally relates to key ladders for use in cryptographic applications.

BACKGROUND

A Key-Ladder is a generic cryptographic construction used mostly in the content distribution domain. Typically, it comprises chaining of keyed cryptographic operations, such that each one of those operations gets its key from the output of the previous operation. The input for all operations in a key ladder is typically provided from outside of the key ladder. The highest (i.e., the first) level of the key ladder typically gets its key from the hardware itself (for example and without limiting the generality of the foregoing, from One-Time-Programmable [OTP] memory). The lowest (i.e. the final) level of the key ladder typically outputs its result out of the key-ladder for general use—for example, for decrypting encrypted content or other appropriate ciphertexts. Key-ladder intermediate levels generate varying levels of intermediate service-keys, which are typically refreshed in decreasing frequency: i.e., never, yearly, monthly, weekly, daily, etc. Alternatively, each of these intermediate keys may be provided by different entities.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

A method, apparatus and system for a cryptographic key ladder is described, the method, apparatus and system including receiving a first input including a first decryption key and a second input including an encrypted second decryption key at a cryptographic decryption apparatus, the encrypted second decryption key to be decrypted by the cryptographic apparatus according to the first decryption key, storing a value of a key ladder length in a first register by a cryptographic processor, and using the stored value as a loop index by the cryptographic processor for a number of iterations of the cryptographic decryption apparatus executed as a loop, wherein at one stage in the loop execution of the cryptographic decryption apparatus, the second input includes the key ladder length, wherein the loop operation of the cryptographic decryption apparatus operates for a number of iterations equal to an initial value of the loop index.

Exemplary Embodiments

In the present specification and claims the term “plaintext”, in all of its grammatical forms is understood as referring to information which a sender is transmitting to a receiver. Likewise, the term “ciphertext” refers to the result of an encryption operation which has been performed on the plaintext. The text of the “plaintext” is the binary form of the information to be transmitted. Similarly, the encrypted “ciphertext” is the result of performing an encryption operation on a plaintext. Less formally, the information in non-binary form may also be referred to as plaintext and ciphertext. Thus a video clip (as opposed to a binary video file), for example, may be referred to as a “plaintext” which, when encrypted produces a “ciphertext”, i.e. an encrypted video file. It is understood that the encrypted video file is actually the output of an encryption operation executed on the binary form of the plaintext video.

Reference is now made toFIG. 1which is a simplified illustration of an extendable key ladder100constructed and operative in accordance with a first embodiment.FIG. 1depicts an extendable key ladder100which encodes a number of levels to be executed in the key ladder embedded inside a top level input (or output) of the key-ladder. The key ladder100depicted inFIG. 1comprises a plurality of decryptors105,110,115,120,125.

For efficient processing, a decryptor (i.e. a cryptographic decryption apparatus, such as any one of the plurality of decryptors105,110,115,120,125) typically comprises 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 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.

The plurality of decryptors105,110,115,120,125may comprise a single cryptographic decryption apparatus—i.e. the same dedicated hardware (or, if appropriate, software) may be used repeatedly, albeit with different keys and ciphertexts in each decryption step, with a counter used to keep track of the number of rounds which either have already been executed or remain to be executed. Alternatively, the plurality of decryptors105,110,115,120,125may comprise a plurality of cryptographic decryption apparatuses. That is to say, a plurality of different hardware implementations of decryptors may be used in performing the decryption steps inFIG. 1. Persons of skill in the art will appreciate that the option of using a single decryption apparatus is a more cost-effective design. By way of example, if the key ladder100ofFIG. 1has three decryption steps, then one hardware decryptor may perform all of the decryption steps; alternatively, two of the decryption steps may be performed by a single hardware decryptor and the third decryption step may be performed by a second hardware decryptor; or still further alternatively, each one of the decryption steps may be performed by a different hardware decryptor.

The service-keys generated by the key ladder100in its intermediate levels (e.g. decryptors110,115,120, etc.) are lucrative targets for attackers to discover, expose and distribute. Thus, one of the main goals of the key ladder100designer is to design the key ladder100such that the intermediate keys (e.g. Kn−1, K4215, K3182, etc.) do not leak out to such attackers. This is typically achieved by storing the intermediate keys in volatile memory (e.g., Flip Flops) that is dedicated to the key ladder100apparatus, and is inaccessible to other components (e.g., CPUs) operating in the same system. Typically keys at higher levels of the key ladder100are more valuable, because lower level keys can be derived from them (i.e. key K4215is more valuable than key K2190).

The designer of a key ladder100often faces conflicting requirements. On the one hand, it is desirable to include multiple levels in the key ladder100, such that the key ladder100is flexible and can support all current and future use cases, which may require different numbers of levels. On the other hand, if a certain use case requires only three levels, it is wasteful to have the key ladder100execute, for example, 50 levels, just because in some future scenario, 50 levels may be necessary. And as was noted above, in addition to these two conflicting requirements, the key ladder100must also be secure against key leakage, as explained above.

Intermediate keys are not output where an attacker can easily access them, but rather, are maintained in secure hardware. Therefore, an attacker trying to obtain such an intermediate key, such as, for example K3182(which might be a key which is changed monthly), might attempt to reduce the number of rounds in the extendable length key ladder100with the hope of being able to extract it from the key ladder. However, in order to successfully extract the intermediate key, the attacker will also have to change the key ladder length field to a different value. In the embodiment described herein, substantially all intermediate (e.g. Kn−1, K4215, K3182, etc.) values in the key ladder will come out wrong, and the attacker will not succeed because the initial value the attacker provides for decryption will most likely not have the correct key ladder length.

In one embodiment, a first decryptor105in the key ladder100receives two inputs: a key130which is at the highest level of the key ladder100; and an initial input140. The key130at the highest level of the key ladder100is depicted inFIG. 1as a key130that is stored in one time programmable (OTP) memory133. It is appreciated that the representation of key130as a key stored in OTP133is by way of example, and any other appropriate way of securely storing key130, such as EEPROM, PUF (Physically Uncloneable Function) and so forth, may be implemented in key ladder100.

The second input to the first decryptor105mentioned above, the initial input140, comprises an encrypted key EKn150, which is decrypted by the decryptor105using the key130as a decryption key. The output of the decryption of encrypted key EKn150by the decryptor105is decryption key Kn155, which is then available for input into a second decryptor110for use as the decryption key Kn155, when encrypted decryption key EKn−1160is input into the second decryptor110. This process is repeated iteratively for each decryption step, indicated inFIG. 1by the various encrypted inputs, such as EK3184, EK2188, and EK1192, and output keys which, respectively, are input into subsequent decryptors115,120,125, such as keys K3182and K2190. In the final iteration of key ladder100, key K1165is output. The decryption of K1165enables the decryption of ciphertext173by decryptor170, to produce plaintext178. It is appreciated that any other use of K1165, as is known in the art, may also occur at this stage.

Those skilled in the art will appreciate that the encrypted decryption keys, such as EKn−1160, EK3184, EK2188, and EK1192, and so forth, are received as externally provided outputs, typically by the user of the key ladder100. For example, in a video security system, the user/operator can send the encrypted decryption keys in an entitlement control message (ECM) or an entitlement management message (EMM).

The initial input140to the first decryptor105also comprises a key ladder length180. In one embodiment, the maximum length of the key ladder100(i.e. the maximum number of iterations of the decryption step, as is described above) will be 2i−1, where i is the number of bits in the key ladder length180. By way of example, if the initial input140is 128 bit long, and the key ladder length180is the eight least significant bits in the 128 bits of the initial input140, then: input EKn150will be 128 bits, and the key ladder will have at most 255 iterations (i.e. 28−1). The key ladder length180is a part of EKnwhich is typically stored by a processor in a first register.

It should be appreciated that the key ladder length180will be embedded into EKnunder the control of whatever authority is managing or administering this system. By way of example, if the key ladder100system is for use in a pay television decoder, then the broadcaster or cable-TV operator would determine the value of the key ladder length180.

In practice, however, typical applications which utilize key ladders may need fewer than the 2ipossible iterations. Accordingly, in one embodiment, only n iterations of the key ladder100are executed, where n is the value of the key ladder length. Continuing with the example above where the initial input140is 128 bits long, and the key ladder length180is the first eight bits in the 128 bits of the initial input140, if the first eight bits are: 00000011 (i.e. the value of the key ladder length180is 3), then the decryptor105would perform only three iterations of decryptions, as will be described below, with reference toFIG. 2.

The key ladder length180may be placed in any location in the initial input140, so long as the location of the length180in the initial input140is known to a processor, so that the key ladder length180is determined prior to inputting the initial input140as EKn150into the first decryptor105. The decryption logic, that is to say the key ladder100itself, may be programmed (in hardware, software, or a combination of software and hardware) to locate the key ladder length180field in EKn150and to apply this value to the key ladder length180. Key ladder length180may be: at the start of the initial input140; at the end of the initial input140; or in some other known location in the initial input140. In principle, the bits comprising the key ladder length180may be distributed throughout the initial input140in known locations (e.g. if initial input140is 256 bits long, and the key ladder length180is eight bits long, the key ladder length180may be formed by taking eight known bits from among the 256 bits of the initial input140, and concatenating those eight bits to form the key ladder length180).

It should be appreciated, in this example, that although the size of key EKnremains unchanged, because the i bits of the key ladder length180are fixed (having value n), the entropy or size of the key space from which the key is chosen is reduced. Because key ladder100is operated as a loop having n steps (i.e. the value of n becomes a loop index for the key ladder) in the key ladder100, the key ladder100is of variable (i.e. extendable) length.

It should also appreciated that in some embodiments, the key ladder length180may not be included in the encrypted key EKn150, but rather the key ladder length180may be embedded in key Kn155. That is to say, that EKn150is originally encrypted so that when it is decrypted using OTP Key130, the resulting key Kn155includes in it the key ladder length180.

Reference is now made toFIG. 2, which is a simplified illustration of an apparatus200implementing the embodiment depicted inFIG. 1, executing a three step key ladder205. The left side ofFIG. 2shows a simplified block diagram depiction of an exemplary apparatus200in which the three step key ladder205is executed. The initial input140, comprising the encrypted key EKn150and the key ladder length180, is input into a decryptor210. The decryptor210retrieves the OTP key130from OTP memory230. Using the OTP key130, the decryptor210decrypts the encrypted key EKn150, and outputs decrypted key Kn240. Once EKn150is input into the decryptor210, the key ladder length180is input to the processor250, which stores it in a register260.

Turning to the right portion ofFIG. 2, the above description corresponds to inputting initial input270into decryptor210,105(both reference numbers are used, in order to show the correspondence betweenFIGS. 1 and 2). Initial input270comprises key ladder length180, depicted as 00000011 (i.e. 3), embedded in encrypted K3, i.e. EK3. Decryptor210,105decrypts EK3and outputs K3. The following two rounds depicted on the left side ofFIG. 2proceed as was noted above, with reference to the final two steps of the key ladder depicted inFIG. 1, resulting, in the final step, in the output of plaintext178by decryptor170.

With the execution of each subsequent round of the key ladder205by the apparatus200, the processor250decrements the value stored in register260. When the value stored in register260reaches zero, the loop being executed is stopped, and EK1192has been decrypted, producing key K1165. The decryption of K1165enables the decryption of ciphertext173by decryptor170, to produce plaintext178, as noted above. It should be appreciated that any other use of K1165, as is known in the art, may also occur at this stage.

Reference is now made toFIG. 3, which is a simplified illustration of the key ladder100constructed and operative in accordance with a second embodiment. In the embodiment ofFIG. 3, the key ladder100is of a fixed length determined during design time. InFIG. 3, the key ladder100is depicted as having n steps. The initial input140comprises the encrypted key EKn150. The first decryptor105also receives the OTP key130for decrypting the encrypted key EKn150. The key ladder100also receives an additional input300. The additional input300comprises an input parameter m301, which is a number of iterations above the final iteration of the key ladder100(i.e. decryptor125) where an intermediate result, Km315is side-stored in a second register350. The additional input300also comprises at least one bit input303which is indicative of the mode of operation of the key ladder100. The input parameter m301and the at least one bit input303are received by the key ladder100from a user/operator of the key ladder100. For example, in a video security system, the user/operator can send the input parameter m301and the at least one bit input303in an entitlement control message (ECM) or an entitlement management message (EMM).

In a first mode, indicated by the at least one bit input303, key ladder100operates in its entirety, from the steps of inputting the encrypted key EKn150and the OTP key130into the first decryptor105, through to the output of the final iteration of key ladder100when key K1165is output. During operation of the key ladder100in the first mode, intermediate decryptor310receives the output key km+1(from a previous decryption operation, not depicted) and encrypted key EKm305. The intermediate decryptor310outputs a decrypted key Km315, which is input into decryptor320for use in decrypting EKm−1330, and producing key Km−1340. However, key Km315is also side-stored in the second register350. Additionally, the value of m301is also side-stored along with the value Km315. This enables having different values of m which can be used for various operations. For instance, in one set of operations, m may be equal to 3, and in a second state of operations, m may be 4.

Accordingly the second register350stores the values of Kmaand in tandem, ma; Kmband in tandem, mb; and so forth, as is depicted inFIG. 3.

In a second mode, indicated by the at least one bit input303, key ladder100need not be executed in its entirety, but rather, key Km315may be retrieved from the second register350, and key ladder100may be executed beginning from the EKm−1to Km−1decryption operation (i.e., decryptor320). A savings of time, e.g., on the order of the several milliseconds of time needed to execute all of the previous decryption steps of key ladder100, thereby results for all executions of the key ladder100in this second mode.

It is appreciated that Km315may be any of the intermediate keys. When the key ladder100is resumed from step m, it proceeds for m steps, and the key ladder logic enforces the correct number of iterations, since it was side-stored alongside Kmin register350.

The key ladder100is executed in the first mode (i.e. the key ladder100operates in its entirety), when the key ladder100is reset or when the key ladder100effective height needs to be extended. The key ladder100is executed in the second mode (i.e. beginning at decryptor320) in other cases, specifically, when the intermediate result Kmalready exists, and therefore, only the final m levels of the key ladder100need to be executed.

In the present embodiment, the key ladder100is protected against shortening of the Key ladder length when the key ladder100is executed in the second mode (i.e. beginning at decryptor320) since the key ladder100has also side-stored m, and then the key ladder100proceeds to perform m levels, based on the side-stored value of m. So effectively, the key ladder100always performs exactly n levels, even though it might perform just the bottom m levels now. As such, no matter how a potential hacker may attempt to manipulate the input parameter m301and the at least one bit input303, the hacker is prevented from performing an attack by manipulating the key ladder length.

In still another embodiment, the methods described above with reference toFIG. 1andFIG. 3may be combined, so that a extendable length key ladder100may also side-store an intermediate result, so that the extendable length key ladder100may be executed beginning from an intermediate stage.

Reference is now made toFIG. 4, which is a flowchart diagram of a method of implementing the system ofFIG. 1. In step410, a first input is received at a cryptographic decryption apparatus, the first input including a decryption key. A second input is also received at a cryptographic decryption apparatus, the second input including an encrypted second decryption key, the encrypted second decryption key to be decrypted by the cryptographic decryption apparatus according to the first decryption key.

In step420, a value of a key ladder length is stored by a cryptographic processor in a first register.

In step430the stored value is used as a loop index by the cryptographic processor for a number of iterations of the cryptographic decryption apparatus to be executed as a loop, wherein, at one stage in the loop execution of the cryptographic decryption apparatus, the second input includes the key ladder length, wherein the loop operation of the cryptographic decryption apparatus operates for a number of iterations equal to an initial value of the loop index.

It should be appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques. It is further appreciated that the software components may be instantiated, for example: as a computer program product or on a tangible medium. In some cases, it may be possible to instantiate the software components as a signal interpretable by an appropriate computer, although such an instantiation may be excluded in certain embodiments of the present invention.

It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention is defined by the appended claims and equivalents thereof: