File system support for rolling keys

This application relates to a key rolling process for a file system of a computing device. The key rolling process allows for files to be transparently re-encrypted in a background process while still allowing applications to access files being re-encrypted. During re-encryption, a portion of the file is decrypted using a current key for the file and re-encrypted using a new key for the file. During re-encryption, the portion of the file can be relocated to another location in memory. Metadata associated with the file can be updated to include information pertaining to the location of the re-encrypted portion. The metadata can also be updated include information pertaining to how much of the file has been re-encrypted with the new key and how much of the file remains encrypted with the current key.

FIELD

The described embodiments relate generally to encryption algorithms for file systems. More particularly, the present embodiments relate to encryption algorithms for transparently re-encrypting a file of a file system by iteratively encrypting portions of the file and relocating the portions of the file to a location on disk that is different than an original location of the file.

BACKGROUND

Since the inception of wireless consumer electronics, accessibility to personal information of a user has become more prevalent. Concern over the safety of such personal information has given rise to advanced encryption algorithms. Although these algorithms have previously prevented hackers from accessing valuable data on certain devices, some algorithms may fail against more modern hacking techniques. For example, the prevalence of bots that can rapidly generate and guess passwords has made cracking certain encryption algorithms a relatively simple process where time is the only limiting variable. As a result, devices having file systems protected by simple encryption algorithms may occasionally be compromised, thereby making device users subject to data loss, and, in some instances, identity theft.

SUMMARY

This paper describes various embodiments that relate to systems, methods, and apparatus for encrypting a file system. In some embodiments, a method is set forth for implementing a background process for re-encrypting a file on a computing device. The method can include the steps of decrypting an encrypted portion of a file using a first key to generate a decrypted portion of the file. The encrypted portion of the file can be stored in a first memory location. The method can further include steps of encrypting the decrypted portion of the file using a second key to generate a new encrypted portion of the file, and writing the new encrypted portion of the file to a second memory location. While writing the new encrypted portion of the file to the second memory location, a portion of the file can remain encrypted with the first key at the first location. Furthermore, the method can include updating metadata associated with the file to include an indication of an amount of data of the file that has been re-encrypted using the second key.

In other embodiments, a computing device is set forth. The computing device can include a memory configured to store a file, and a key storage configured to store keys for encrypting the file. A first portion of the file can be encrypted using a first key and a second portion of the file is encrypted using a second key. The computing device can further include a processor configured to modify metadata associated with the file to include a first location of the first portion of the file in the memory and a second location of the second portion of the file in the memory. The first portion of the file can be re-encrypted with the second key in a background process configured to run simultaneous to an application executing at the computing device.

In yet other embodiments, a machine-readable non-transitory storage medium is set forth. The storage medium can store instructions that, when executed by a processor included in a computing device, cause the computing device to carry out steps that include decrypting a portion of a file using a first key. The portion of the file can be stored in a first location in a memory of the computing device. The steps can further include encrypting the portion of the file using a second key and storing the portion of the file in a second location. When the portion of the file is being encrypted with the second key, a different portion of the file can remain encrypted with the first key at the first location. Furthermore, the steps can include updating metadata associated with the file to indicate portions of the file that are encrypted with the first key and the second key. Additionally, the steps can include updating the metadata associated with the file to include data representative of the first location and the second location.

Other aspects and advantages of the invention will become apparent from the following detailed description taken in conjunction with the accompanying drawings that illustrate, by way of example, the principles of the described embodiments.

DETAILED DESCRIPTION

Encryption of electronic data has helped to securely establish a global network of devices in which sharing of the electronic data can be accomplished with minimal risk of the theft or fraud. Encryption is also used to securely transmit signals between components within a device. The popularity of many devices such as cell phones and laptops, combined with the prevalence of hacking, has caused device manufacturers to be constantly faced with the challenge of making device data more secure. Despite efforts and investments made to provide a more secure device architecture, device data can be occasionally compromised by malicious software designed to discover keys that are used to secure the device data. In some cases, the only limiting variable for some malicious software is time, therefore it is critical for device manufacturers to periodically re-encrypt data on a device with a new key. In this way, fraud and theft of electronic data can be avoided by generating new keys for a device before the malicious software has the time to guess the old keys. However, decrypting a file on a device using an old key and re-encrypting the file with a new key, also referred to a key rolling, has its own drawbacks. Specifically, key rolling can inhibit processor performance and consume power because of the amount of data that is processed when, for example, key rolling is performed across an entire file system. As a result, the user experience can be degraded. In order to resolve these issues, the embodiments discussed herein provide algorithms for key rolling that transparently re-encrypt data of a file system in a background process that improves both power and processor efficiency.

In some embodiments discussed herein, key rolling is performed transparently by allowing all or some portions of a file to be accessible by a program on a computing device while the file is being re-encrypted with a new key. When re-encryption is occurring, the program can attempt to access the file and be granted access to all portions of the file—even those portions that are being re-encrypted with the new key. As a result, a portion of the file can be encrypted with an old key and a different portion of the file re-encrypted with a new key. Depending on the size of the portion of the file being re-encrypted, the re-encryption will seem transparent to a user or process of the computing device that may be directing the program to access the file.

A key rolling program on the computing device can track the progress of the re-encryption of a file by updating metadata associated with the file. The metadata can include an offset value that indicates the location in the file where the re-encryption of the file last ended. For example, if a key rolling process for a file has not begun then the metadata can include data representing a null or zero value for the progress of the key rolling process. Furthermore, if the key rolling process for the file has successfully re-encrypted half of the file with a new key, the metadata for the file will include a value indicating half of the data in the file has been re-encrypted. Additionally, if the key rolling process for the file has successfully re-encrypted the entire file with the new key, the metadata for the file will include a value indicating that the file is encrypted entirely with the new key.

In some embodiments, the key rolling program can track the progress of the re-encryption of the file using a bitmap. The bitmap can be associated with the metadata and managed at least in part by the key rolling program. The bitmap can be a single or multi-dimensional array or tree structure for determining the portions of a file are encrypted with a specific key. A bitmap is useful when portions of the file encrypted with a new key may not be clearly identified from a single offset value. Additionally, in some instances it can be beneficial to perform key rolling non-sequentially such that certain portions of the file are skipped at a given time during key rolling. For example, if key rolling is to be performed on a file that is being used by an application, the key rolling program can skip sections of data of interest to the application. The bitmap associated with the metadata of the file can thereafter be updated to indicate the portions of the file that are encrypted with the new key and the portions of the file that are encrypted with the old key. In some embodiments, a file can be encrypted with more than two keys at a time. Furthermore, re-encryption of a file can be initiated by the key rolling program or any other application associated with a file that is to be encrypted or re-encrypted. In some embodiments, the file can be a group file that allows a group of people to access and edit the file. The file can be encrypted with multiple keys and each person in the group can have access to the multiple keys. When updates are made to the file by one or more person in the group, the updated portion of the file can be encrypted with one or more existing keys. However, if a person leaves the group and updates are made to the file subsequent to the person leaving the group, a new key can be generated and the updates to the file can be encrypted with the new key according to the key rolling process discussed herein. In this way, the person who left the group will be able to access any portions of the file except for those portions of the file that were created after the person left the group.

In some embodiments, the key rolling program can include a reserve operation for reserving portions of memory for newly encrypted portions of a file. In order to protect against loss of data that can occur from power loss or computer crashes, the key rolling program can copy portions of a file to be re-encrypted, and write the re-encrypted portion of data to the reserved portion of memory. In this way, if the computer operating the key rolling program crashes during a re-encryption of a portion of the file, only a copy of the portion of the file will potentially be lost. Additionally, by reserving portion of memory for the key rolling operation, memory fragmentation of files can be reduced. The metadata associated with the file can be updated to point to where the re-encrypted file is in memory. For example, the metadata can indicate (i) before re-encryption that a portion of the file is encrypted with an old key, and (ii) after re-encryption that a portion of the file is re-encrypted with the new key. As a result, any applications attempting to use the file can determine the appropriate key to access the file by referencing the metadata associated with the file.

The key rolling program can be scheduled to execute at different times. For example, the key rolling program can be scheduled to execute when a computing device operating the key rolling program is connected to an external power supply. The key rolling program can also be scheduled to execute when the computing device has entered an idle, locked, or low power mode. In this way, the impact of the key rolling program on the power and processing efficiency of the computing device can be mitigated. However, in some embodiments, the key rolling program can be scheduled to execute at any suitable time, including when a user is actively operating the computing device. In such embodiments, the key rolling program functions as a background process for transparently re-encrypting a file system of the computing device, as discussed herein.

FIG. 1illustrates a system diagram100for a computing device102that can perform key rolling according to the embodiments discussed herein. The computing device102can be a cell phone, laptop, desktop, display, watch, media player, or any other computing device102suitable for storing encrypted data. The data stored by the computing device102can be encrypted using a user key104and/or a hardware key106. The user key104can be a key that is created by a user or is otherwise uniquely associated with the user. Additionally, the user key104can be stored by the computing device102or provided to the computing device102through an interface of the computing device102. In this way, data that is encrypted using the user key104can require the user to enter the user key104before the user can access the data. The computing device102can also include a hardware key106, which can be provided by a manufacturer of the computing device102. In this way, the hardware key106can be unique per computing device102. In some embodiments of the computing device102, both the hardware key106and the user key104are used to encrypt data. In other embodiments of the computing device102, the hardware key106is used to encrypt the user key104, and the resulting encrypted user key is used to encrypt certain files114in a file system112of the computing device102. For example, certain files114that are used during a startup of the computing device102can be encrypted using the encrypted user key, and therefore certain features of the computing device102can be unavailable until the user enters the user key104.

A key storage108can also be provided in the computing device102for storing keys110that can be used to encrypt files114of the file system112according to different policies associated with the keys110. For example, some keys110can only be made available after a user has activated the computing device102for the first time, therefore any files encrypted with such keys will only be available after activation of the computing device102. Additionally, some keys110can only be made available after the computing device102has connected to an external device such as a network device. As a result, any files encrypted with such keys will only be available when the computing device102has connected to the external device. Encrypting the files114in this way limits the availability of the files114to applications118stored in an application storage116of the computing device102.

Each application118can request one or more keys110from the key storage108before accessing files114from the file system112. The granting of keys110to applications118and deletion of keys110from memory can be based on the policies in place for each key110. This prevents malicious applications from being loaded on the computing device102and thereafter accessing the file system112without first obtaining a key110. Unfortunately, some malicious applications can be designed to frequently make attempts to access the files114by guessing key values. In some cases, given a long enough time frame, the malicious applications can succeed, therefore the computing device102can frequently or periodically generate new keys to replace old keys. A key rolling program on the computing device102can be used to re-encrypt files114in the file system112with new keys. The key rolling program can initially decrypt a portion of a file114using an old key, re-encrypt the file114using a new key, and thereafter store the re-encrypted portion of the file114in a different location than the previous location of the portion of the file.

FIG. 2illustrates a flow diagram200of an application accessing an encrypted file. Specifically,FIG. 2provides an example of a process that can occur while a key rolling program210is executing in the background of the process. For example, an application118can attempt to access a decrypted portion of a file204stored as an encrypted file206in a file system memory208. However, in order in order to gain access to one or more file keys202that can unlock the encrypted file206, a user key104and hardware key106are used to first unlock a key storage108. Once the key storage108is unlocked using the user key104and hardware key106, the key storage108can provide various keys in response to requests received from the application118. For example, the file key(s)202can be provided by the key storage108to decrypt the encrypted file206. In some embodiments, the encrypted file206can be decrypted using one or more keys that are generated using the hardware key106. The decrypted portion of the file204can thereafter be accessible to the application118while the key rolling program210is decrypting and re-encrypting a different portion of the encrypted file206, as discussed herein. In this way, the key rolling program210will be a transparent process relative to the application118, which is able to access different portions of the encrypted file206.

FIG. 3illustrates a flow diagram300of an application process302operating with a key rolling process304. Specifically, the flow diagram300provides an example of a key rolling process304that can re-encrypt portions of an encrypted file316and relocate a re-encrypted file portion320of the file in the file system memory208. The application process302can involve obtaining a first file key308for accessing a first encrypted portion314of an encrypted file316. Once obtained, the first file key308can be used to decrypt the first encrypted portion314so that a first file portion306(i.e., the first encrypted portion314decrypted using the first file key308) can be accessed during the application process302. Simultaneous to the application process302accessing the first file portion306, the key rolling process304can also obtain the first file key308for decrypting a second encrypted portion318of the encrypted file316. Once decrypted, the key rolling process304can re-encrypt a second file portion312(i.e., the second encrypted portion318decrypted using the first file key308) using a second file key324. The second file key324can be an updated file key that was created after the first file key308. Additionally, it should be noted that any key discussed herein (e.g., the first file key308and/or the second file key324) can be a single key, a key encrypted using one or more keys, and/or one or more keys encrypted with additional data (e.g., salt).

The second file portion312can be stored in the file system memory208as a re-encrypted file portion320. In some embodiments of the key rolling process304, the re-encrypted file portion320is stored in reserved memory322. The reserved memory322represents a portion of a memory that can be initially reserved at the beginning of the key rolling process304in order to mitigate fragmentation of files. Once the key rolling process304is complete for the entire encrypted file316, the entire encrypted file316will be re-encrypted with the second file key324and be located in the reserved memory322. Thereafter, the previous location of the encrypted file316can be marked or otherwise indicated as unused space in the file system memory208. However, in some embodiments, the re-encrypted can occupy the same location in memory as the encrypted file316once re-encrypted with the second file key324.

The key rolling process304can iteratively re-encrypt individual portions of data that are the same size or different size per iteration. For example, in some embodiments, each iteration can re-encrypt a 2 megabyte portion of a file. In other embodiments, each iteration can re-encrypt a portion that is greater than or less than 2 megabytes. The key rolling process304can, in some embodiments, select different sizes of a file to re-encrypt for each iteration. For example, if power is low or the processor has a number of tasks scheduled already, the size of data re-encrypted per iteration of the key rolling process304can be reduced. Thereafter, when the power is no longer low or the processor has a reduced number of tasks scheduled, the size of the data re-encrypted per iteration of the key rolling process304can be increased.

FIG. 4illustrates a method400for performing a key rolling process on a file of a computing device. The method400can be performed by any suitable component or module not limited to an application, a processor, or a kernel of the computing device. The method400can include a step402of identifying a file stored in a memory of the computing device. The file can be any suitable type of file stored by a computer not limited to media data, system data, graphics data, hardware data, device data, or any other data suitable for encryption. The method400can also include a step404of reading a portion of data of the file at a first location in the memory. At step406, the portion of data is decrypted using a first key. The decrypted portion of data, at step408, is encrypted using a second key. At step410, the portion of data encrypted using the second key is written to a second location in the memory that is different than the first location. Optionally, at step412, metadata associated with the file is updated to indicate that the portion of data is located at the second location. Additionally, the metadata can optionally be updated, at step414, to indicate that the portion of data has been encrypted using the second key. In some embodiments, the metadata corresponding to one or more files in the memory can maintain a history of keys that have been used to encrypt the one or more files. In other embodiments, the metadata only keeps track of the keys that are currently being used to encrypt a file and expunges data corresponding to keys that were previously used to encrypt the file.

FIG. 5illustrates a method500for accessing a file that has been or is being re-encrypted according to a key rolling process, as discussed herein. The method500can be performed by any suitable component or module not limited to an application, a processor, or a kernel of the computing device. The method500can include a step502of identifying a file stored in a memory of a computing device. The method500can also include a step504of determining a first location of a first portion of the file in the memory. Step506of the method500includes determining that the first portion of the file is encrypted using a first key. At step508, the first portion of the file is decrypted using the first key. Step510of the method500includes determining a second location, different than the first location, of a second portion of the file in the memory. Additionally, step512of the method500includes determining that the second portion of the file is encrypted using a second key, different than the first key. At step514of the method500, the second portion of the file is decrypted using the second key. The method500can be performed simultaneous to a key rolling program re-encrypting the file with the first key, the second key, or another suitable key. In some embodiments, the file can be accessed using either the first key or the second key after the file has been, or when the file is being re-encrypted according to the key rolling process discussed herein. Therefore, access to the file can require either a single key or multiple keys.

FIG. 6is a block diagram of a computing device600that can represent the components of a computing device102or any other suitable device or component for realizing any of the methods, systems, apparatus, and embodiments discussed herein. It will be appreciated that the components, devices or elements illustrated in and described with respect toFIG. 6may not be mandatory and thus some may be omitted in certain embodiments. The computing device600can include a processor602that represents a microprocessor, a coprocessor, circuitry and/or a controller for controlling the overall operation of computing device600. Although illustrated as a single processor, it can be appreciated that the processor602can include a plurality of processors. The plurality of processors can be in operative communication with each other and can be collectively configured to perform one or more functionalities of the computing device600as described herein. In some embodiments, the processor602can be configured to execute instructions that can be stored at the computing device600and/or that can be otherwise accessible to the processor602. As such, whether configured by hardware or by a combination of hardware and software, the processor602can be capable of performing operations and actions in accordance with embodiments described herein.

The computing device600can also include user input device604that allows a user of the computing device600to interact with the computing device600. For example, user input device604can take a variety of forms, such as a button, keypad, dial, touch screen, audio input interface, visual/image capture input interface, input in the form of sensor data, etc. Still further, the computing device600can include an output608that can be controlled by processor602. The output608can include a display device, audio device, haptic feedback device, or any other output device suitable for providing output to a user of a device. Controller610can be used to interface with and control different equipment through equipment control bus612. The computing device600can also include a network/bus interface614that couples to data link616. Data link616can allow the computing device600to couple to a host computer or to accessory devices. The data link616can be provided over a wired connection or a wireless connection. In the case of a wireless connection, network/bus interface614can include a wireless transceiver.

The computing device600can also include a storage device618, which can have a single disk or a plurality of disks (e.g., hard drives) and a storage management module that manages one or more partitions (also referred to herein as “logical volumes”) within the storage device618. In some embodiments, the storage device618can include flash memory, semiconductor (solid state) memory or the like. Still further, the computing device600can include Read-Only Memory (ROM)620and Random Access Memory (RAM)622. The ROM620can store programs, code, instructions, utilities or processes to be executed in a non-volatile manner. The RAM622can provide volatile data storage, and store instructions related to components of the storage management module that are configured to carry out the various techniques described herein. The computing device600can further include data bus624. Data bus624can facilitate data and signal transfer between at least processor602, controller610, network/bus interface614, storage device618, ROM620, and RAM622.

The various aspects, embodiments, implementations or features of the described embodiments can be used separately or in any combination. Various aspects of the described embodiments can be implemented by software, hardware or a combination of hardware and software. The described embodiments can also be embodied as computer readable code on a computer readable storage medium. The computer readable storage medium can be any data storage device that can store data, which can thereafter be read by a computer system. Examples of the computer readable storage medium include read-only memory, random-access memory, CD-ROMs, HDDs, DVDs, magnetic tape, and optical data storage devices. The computer readable storage medium can also be distributed over network-coupled computer systems so that the computer readable code is stored and executed in a distributed fashion. In some embodiments, the computer readable storage medium can be non-transitory.