Apple's Patent Background

In the first of three security patents that our report covers titled "Securing Cryptographic Process Keys using Internal Structure," we begin with Apple's patent background which states that in the field of data security, there is a need for fast and secure encryption. This is why the AES (Advanced Encryption Standard) cipher has been designed and standardized. Cryptographic algorithms are widely used for encryption and decryption of messages, authentication, digital signatures and identification. AES is a well-known symmetric block cipher. Block ciphers operate on blocks of plaintext and ciphertext, usually of 64 or 128 bits length but sometimes longer. Stream ciphers are the other main type of cipher and operate on streams of plain text and cipher text 1 bit or byte (sometimes one word) at a time. With a block cipher, a particular plain text block will always be encrypted to the same cipher text block using the same key. However, to the contrary with a stream cipher, the same plain text bit or byte will be encrypted to a different bit or byte each time it is encrypted. Hence in the ECB (electronic code book) mode for block ciphers, each plain text block is encrypted independently. In other modes, encryption is a function of the previous blocks.

AES is approved as an encryption standard by the U.S. Government. Unlike its predecessor DES (Data Encryption Standard), it is a substitution permutation network (SPN). AES is fast to execute in both computer software and hardware implementation, relatively easy to implement, and requires little memory. AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits. Due to the fixed block size of 128 bits, AES operates on a 4.times.4 array of bytes. It uses key expansion, and like most, block ciphers a set of encryption and decryption rounds (iterations). Each round involves the same processes. Use of multiple rounds enhances security. Block ciphers of this type use in each round a substitution box (s-box). This operation provides non-linearity in the cipher and significantly enhances security.

Note that these block ciphers are symmetric ciphers, meaning the same algorithm and key are used for encryption and decryption, except usually for minor differences in the key schedule. As is typical in most modern ciphers, security rests with the (secret) key rather than the algorithm. The s-boxes or substitution boxes accept an n-bit input and provide an m-bit output. The values of m and n vary with the cipher and the s-box itself. The input bits specify an entry in the s-box in a particular manner well known in the field.

The Black Box Model

Many encryption algorithms are primarily concerned with producing encrypted data that is resistant to decoding by an attacker who can interact with the encryption algorithm only as a "Black Box" (input-output) model, and cannot observe internal workings of the algorithm or memory contents, etc due to lack of system access. The Black Box model is appropriate for applications where trusted parties control the computing systems for both encoding and decoding ciphered materials.

The White Box Model

However, many applications of encryption do not allow for the assumption that an attacker cannot access internal workings of the algorithm. For example, encrypted digital media often needs to be decrypted on computing systems that are completely controlled by an adversary (attacker). There are many degrees to which the Black Box model can be relaxed. An extreme relaxation is called the "White Box" model. In a White Box model, it is presumed that an attacker has total access to the system performing an encryption, including being able to observe directly a state of memory, program execution, modifying an execution, etc. In such a model, an encryption key can be observed in or extracted from memory, and so ways to conceal operations indicative of a secret key are important.

Software implementations of cryptographic building blocks are insecure in the White Box threat model where the attacker controls the execution process. The attacker can easily lift the secret key from memory by just observing the operations acting on the secret key. For example, the attacker can learn the secret key of an AES software implementation by observing the execution of the Key Schedule algorithm.

Two Basic Principles in the Implementation of Secure Computer Applications

Hence there are two basic principles in the implementation of secure computer applications (software). The Black Box model implicitly supposes that the user doesn't have access to the computer code nor any cryptographic keys themselves. The computer code security is based on the tampering resistance over which the application is running, as this is typically the case with Smart Cards. For the White Box model, it is assumed the (hostile) user has partially or fully access to the implemented code algorithms; including the cryptographic keys themselves. It is assumed the user can also become an attacker and can try to modify or duplicate the code since he has full access to it in a binary (object code) form. The White Box implementations are widely used (in particular) in content protection applications to protect e.g. audio and video content.

Software implementations of cryptographic building blocks are insecure in the White Box threat model where the attacker controls the computer execution process. The attacker can easily extract the (secret) key from the memory by just observing the operations acting on the secret key. For instance, the attacker can learn the secret key of an AES cipher software implementation by passively monitoring the execution of the key schedule algorithm. Also, the attacker could be able to retrieve partial cryptographic result and use it in another context (using in a standalone code, or injecting it in another program, as an example).

Current Theories don't solve all the Security needs for Block Cipher Encryption in a White Box Environment

Content protection applications are one instance where it is desired to keep the attacker from finding the secret key even though the attacker has complete control of the execution process. The publication "White-Box Cryptography in an AES implementation" Lecture Notes in Computer Science Vol. 2595, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography pp. 250-270 (2002) by Chow et al. discloses implementations of AES that obscure the operations performed during AES by using table lookups (also referred to as TLUs) to obscure the secret key within the table lookups, and obscure intermediate state information that would otherwise be available in arithmetic implementations of AES. In the computer field, a table lookup table is an operation using a data structure (the table) to replace a computation with an array indexing operation.

Chow et al. (for his White Box implementation where the key is known at the computer code compilation time) uses 160 separate tables to implement the 11 AddRoundKey operations and 10 SubByte Operations (10 rounds, with 16 tables per round, where each table is for 1 byte of the 16 byte long--128 bit--AES block). These 160 tables embed a particular AES key, such that output from lookups involving these tables embeds data that would normally result from the AddRoundKey and SubByte operations of the AES algorithm, except that this data includes input/output permutations that make it more difficult to determine what parts of these tables represent round key information derived from the AES key. Chow et al. provide a construction of the AES algorithm for such White Box model. The security of this construction resides in the use of table lookups and masked data. The input and output mask applied to this data is never removed along the process. In this solution, there is a need for knowing the key value at the compilation time, or at least to be able to derive the tables from the original key in a secure environment.

The conventional implementation of a block cipher in the White Box model is carried out by creating a set of table lookups. Given a dedicated cipher key, the goal is to store in a table the results for all the possible input messages. This principle is applied for each basic operation of the block cipher. In the case of the AES cipher, these are the shiftRow, the add RoundKey, the subByte and the mixColumns operations.

However, Chow et al. do not solve all the security needs for block cipher encryption in a White Box environment. Indeed, the case where the cipher key is derived through a given process and so is unknown at the code compilation time is not included in Chow et al.

Apple's New Solution is Powerful and Efficient

Apple states that a typical situation not addressed by Chow et al. is when a software based cryptographic process is distributed over several users and each user has his own cipher key. It is then, from a practical point of view, impossible to disseminate different software code to each user. Another situation is when generating session keys (which by definition are different for each user session) through a given process. Of course, in this case the key is unknown at the software code compilation time. A last case is when it is necessary to store a very large number of keys. It is not reasonable to consider storing about 700 kB of data for each such key.

Apple's invention addresses these problems with a powerful, efficient and new solution to harden the extraction of an AES (or other cryptographic) key in a White Box environment by masking the keys or sub-keys. Further, the present method may be used in a more general case of other cryptographic processes. Apple's invention therefore is directed to hiding the key in a better way. The present method is a powerful, efficient solution to protection of a cryptographic key in a White Box environment. This includes the situation where the key is not always the same, which is believed to be new, and which is important in real world situations.

Additionally, Apple's invention relates to a system and method addressing those cases when the cipher key is unknown at the software code compilation time or when the code size is limited, and there is a need to harden "dynamically" the process and hide the key to protect against an attacker. This aspect of the present disclosure can be combined with prior existing solutions. The most simple and known existing solution to combine it with is data transforms on the cipher key, which are done to avoid visible removable during the execution of the cryptographic process.

Patent Credits

Apple's patent application was originally filed in Q1 2011by inventors Augustin Farrugia, Benoit Chevallier-Mames and Mathieu Ciet and published Thursday July 12, 2012 by the US Patent and Trademark Office. To review Apple's full solution, see patent application 20120179920. A second related patent titled "Securing Implementation of Cryptographic Process having Fixed or Dynamic Keys," under application 20120179919.

Two Additional Security Related Patents

The two additional security patents that surfaced on Thursday to round-off Apple's big security push include the following:

Invention: System and Method for Full Disk Encryption Authentication

In Apple's second patent application-background they state that when a user enables full-disk encryption on a computing device, the user must pass two layers of authentication to use the computing device. First, the user must authenticate at the full-disk encryption level to gain access to the data stored on the computing device. Second, after the disk is decrypted or otherwise made readable, the user must authenticate at the operating system level to gain access to the operating system as well as settings, data, and applications stored thereon. This two layer authentication slows down the boot and login processing of a computing device while waiting for user input. Further, entering two sets of passwords can become tedious for users and if the user forgets the username or password of either of the layers of authentication, then the computing device is rendered unusable.

The additional security associated with full disk encryption carries with it a higher price in terms of effort, memory, and time, causing some users to avoid a simple data security measure. Apple's solution addresses these issues.

Specifically, Apple's invention relates too systems, methods, and non-transitory computer-readable storage media for authenticating a user logging in to an operating system stored on an encrypted drive. A system configured to practice the method presents a login prompt to a user and receives credentials from the user via the login prompt. The credentials can include a username, a password, biometric authentication data, a personal identification number, a user login picture, a short name, a full name, and/or a title.

The credentials can be associated with a volume key, a username, and a password and the credentials for the encrypted drive and the operating system can be synchronized. The system accesses the operating system on the encrypted drive using the credentials and starts the operating system. Then the system authenticates the user on the operating system using the credentials. The system can store credentials, such as a username and password, in memory while the operating system starts, use the credentials for authentication after the operating system has started, and remove the credentials from the memory once the login is complete.

As an added security measure, the system can deny access and disable the login prompt temporarily if the user enters invalid credentials. In order to provide a more pleasing and unified user experience, the login prompt can simulate a full login prompt of the operating system, even though the login prompt occurs before access to the operating system is available.

To that effect, the login prompt can include graphical elements in a same style as the operating system, simulating or emulating operating system specific widgets, color schemes, and so forth. The login prompt can display a user login picture, a short name, a full name, a biometric authentication widget, a password hint, a list of authorized users, computer name, operating system version, boot options, support options, and/or other login options. The first part of the received credentials and the second part of the received credentials can share at least some data.

Apple's invention also relates to systems, methods, and non-transitory computer-readable storage media for generating credentials for a computing device. A system configured to practice the method receives a request from a user to encrypt a storage device of the computing device and receives user credentials associated with the request. Then, based on the user credentials, the system generates first user authentication data associated with logging in to an operating system on the computing device and second user authentication data associated with encryption of the storage device. The system stores both pieces of user data and enables a unified login boot prompt which, when presented with the user credentials, decrypts the storage device and logs in to the operating system based on the user credentials.

Furthermore, Apple's invention includes systems, methods, and non-transitory computer-readable storage media for synchronizing an operating system login with a decryption authentication prompt. A system configured to practice the method includes a processor and an encrypted storage device storing an operating system and user data. Then the system includes a first module configured to control the processor to authenticate first user credentials associated with the operating system and second user credentials associated with decrypting the encrypted storage device, and a second module configured to control the processor to update a unified boot-time login prompt based on the first user credentials and the second user credentials, wherein the credentials provided at the unified boot-time login prompt are used for decrypting the encrypted storage device and logging in a user to an operating system based on a single set of user credentials.

For more information on Apple's security patent, see application 20120179915 which was originally filed in January 2011 and published this week by the USPTO.

Invention: System and Method for Enforcing Software Security through CPU Statistics Gathered using Hardware Features

In Apple's third security related patent application, we once again look at Apple's patent background. In it they state that there are many examples of computer software that contain sensitive information, such as proprietary algorithms, security routines, or cryptographic keys. One prime example is Digital Rights Management software, which can contain a variety of highly sensitive information. Because of this, software is often the target of various attacks, like software tampering or reverse engineering, in which a user modifies the software as part of an effort to dissect, analyze, and discover how it works or to alter the functionality. In the currently used computing model, software is particularly vulnerable to tampering and reverse engineering attacks because the software is often executed in an open environment in which the user has full control. For example, when software is executed on a user's personal computer, which is running a commonly available operating system, e.g., Mac OS, Microsoft Windows, Linux, etc., the user is able to closely monitor the execution of the program. Even in more closely managed operating systems, such as mobile device operating systems, tools are available for the user to monitor and tinker with program execution. Furthermore, with the right skills and tools, the user can even alter the execution of the program.

A variety of techniques have been employed to address these vulnerabilities, such as code obfuscation and tamper resistance techniques. Unfortunately, most of these techniques are vulnerable to the same attacks to which unprotected software is vulnerable.

Apple's solution relates to measuring hardware-based statistics, such as the number of instructions executed in a specific section of a program during execution, for enforcing software security. The counting can be accomplished through a specific set of instructions, which can either be implemented in hardware or included in the instruction set of a virtual machine. For example, the set of instructions can include atomic instructions of reset, start, stop, get instruction count, and get CPU cycle count. To obtain information on a specific section of code, a software developer can insert start and stop instructions around the desired code section. For each instruction in the identified code block, when the instruction is executed, a counter is incremented. The counter can be stored in a dedicated register. The gathered statistics can be used for a variety of purposes, such as detecting unauthorized code modifications or measuring code performance.

Apple's patent FIG. 4 illustrates an exemplary register configuration to support system wide and thread specific counters.

For more information on Apple's security patent, see application 20120179898 which was originally filed in January 2011 and published this week by the USPTO.

Notice

Patently Apple presents a detailed summary of patent applications with associated graphics for journalistic news purposes as each such patent application is revealed by the U.S. Patent & Trade Office. Readers are cautioned that the full text of any patent application should be read in its entirety for full and accurate details. Revelations found in patent applications shouldn't be interpreted as rumor or fast-tracked according to rumor timetables. About Comments: Patently Apple reserves the right to post, dismiss or edit comments.