Automatic identification of invalid participants in a secure synchronization system

CLAIM OF BENEFIT TO PRIOR APPLICATIONS

0001This application claims the benefit of U.S. Provisional Patent Application 62/172,124, filed Jun. 7, 2015. U.S. Provisional Patent Application 62/172,124 is incorporated herein by reference.

BACKGROUND

0002Synchronization systems allow secure synchronization of data items among a number of devices without a central authority being able to gain access to the data items. A common way for a device to identify itself to others in the synchronization system is by using a public/private key pair, the private key of which is only kept on the device.

0003Over time, the set of devices that participate in synchronization may have a number of “ghosts” or non-participant members. These are devices that are valid members of the synchronization system that have lost their private key, making it impossible for them to participate again. One class of non-participant members is caused by devices that are members of the synchronization system and are erased and re-introduced back into the synchronization system. This could be because the owner selected to erase all contents and settings on a device (e.g., to lend the device to a family member temporally), or replaced the device's hard drive and decided to start afresh rather than restoring from a backup.

0004Non-participants cause performance and power issues, as other devices in the synchronization system continue to try to synchronize items with them. Non-participants might also clutter up management user interfaces and even cause a security problem. For instance, the owner of a device may become used to seeing old devices that are not used anymore being displayed alongside with the active devices. The owner might become less able to spot an attacker's device should one make its way into the synchronization system.

BRIEF SUMMARY

0005Some embodiments provide a novel method of removing non-participant members from a synchronization group without revealing the identity of the individual devices to other devices in the synchronization group or to entities outside the synchronization group. Each device has a public and private key pair and uses the public key to join the synchronization group. The public key of the device is stored in a storage associated with the synchronization group and is used to identify the device to other members of the group.

0006When a device is reconfigured, the public and private keys are erased from the device storage and the device can no longer participate in the synchronization group. The public key of the device, however, remains in the storage associated with the synchronization group and the other members of the synchronization group still will try to synchronize their data items with the device.

0007In some embodiments, each device in the synchronization group uses an additional identifier to identify the device as a member of the group. In some embodiments, the device synchronization group identifier is a symmetric signature such as message authentication code (or message digest). In some embodiments a key derivation function is used to generate a cryptographic key from a device-specific identifier. A cryptographic function then receives the cryptographic key as input and generates the device synchronization group identifier. Since the identifier is generated from a device-specific identifier, it is unique to each device. The identifier is also persistent in each device and is not erased or can be re-generated from the same device-specific identifier.

0008Since the identifier is encrypted, the other members of the synchronization group and entities outside the group cannot track the identifier to any specific physical device. The device synchronization group identifier is generated in such a way that it is only possible to decrypt, verify, or derive the identifier with the knowledge of a hardware secret or a secret that is deterministically derived from hardware which persists over erase and restore operations. The requirement is for the identifier to be indistinguishable from a random number (even when the device identifier key is known) so that it can't be used to track a device in the event that the device public identifier is changed.

0009When a device is reconfigured, a new public and private key pair is created for the device. The device rejoins the synchronization group by using the new public key of the device and the encrypted identifier of the device that is the same as the previous encrypted identifier used by the device to join the synchronization group. Once the device joins the synchronization group, the device compares the encrypted identifiers of other members of the synchronization group with its own encrypted identifier. If there is a match, the device determines that the matched encrypted identifier and the associated public key are its own encrypted identifier and public key form a previous membership in the group. Since the device has erased the private key associated with old public key, the device removes the old public key and any information associated with the old key from the synchronization group. Since the public key of the device is changed, without the use of the unique encrypted identifier, it would not have been possible for the device to recognize its own old public key and remove it from the synchronization group.

0010The preceding Summary is intended to serve as a brief introduction to some embodiments of the invention. It is not meant to be an introduction or overview of all inventive subject matter disclosed in this document. The Detailed Description that follows and the Drawings that are referred to in the Detailed Description will further describe the embodiments described in the Summary as well as other embodiments. Accordingly, to understand all the embodiments described by this document, a full review of the Summary, Detailed Description and the Drawings is needed. Moreover, the claimed subject matters are not to be limited by the illustrative details in the Summary, Detailed Description and the Drawing, but rather are to be defined by the appended claims, because the claimed subject matters can be embodied in other specific forms without departing from the spirit of the subject matters.

BRIEF DESCRIPTION OF THE DRAWINGS

0011The novel features of the invention are set forth in the appended claims. However, for purposes of explanation, several embodiments of the invention are set forth in the following figures.

0012<figref idref="DRAWINGS">FIG. 1</figref> conceptually illustrates an example of starting a synchronization group and adding devices to the synchronization group according to some embodiments of the invention.

0013<figref idref="DRAWINGS">FIG. 2</figref> conceptually illustrates an example of a synchronization group that loses a device.

0014<figref idref="DRAWINGS">FIG. 3</figref> conceptually illustrates a synchronization group where over time all participating devices have lost the private key associated with the public key that was used to join them in the synchronization group.

0015<figref idref="DRAWINGS">FIG. 4</figref> conceptually illustrates using a public key and a device synchronization group identifier for joining a device in a synchronization group in some embodiments of the invention.

0016<figref idref="DRAWINGS">FIG. 5</figref> conceptually illustrates the data stored (e.g., in a storage device in a cloud storage service and/or in the storage of each synchronization group member) in the synchronization group in some embodiments of the invention.

0017<figref idref="DRAWINGS">FIG. 6</figref> conceptually illustrates an alternative embodiment for generating the device synchronization group identifier using a secure processor embedded in a device.

0018<figref idref="DRAWINGS">FIG. 7</figref> conceptually illustrates a synchronization group in which a new member detects a previous public key associated with a non-participant member as its own and retires the public key and the associated non-participant member from the group.

0019<figref idref="DRAWINGS">FIG. 8</figref> conceptually illustrates a process for joining a device into a synchronization group and removing a non-participant member of the synchronization group in some embodiments of the invention.

0020<figref idref="DRAWINGS">FIG. 9</figref> conceptually illustrates the software architecture of a keychain manager of a device of some embodiments that supports such a system with multiple verification and synchronization sub-groups.

0021<figref idref="DRAWINGS">FIG. 10</figref> conceptually illustrates a network architecture for a direct P2P network according to some embodiments of the invention.

0022<figref idref="DRAWINGS">FIG. 11</figref> conceptually illustrates a data structure for a keychain as stored by the keychain manager of some embodiments.

0023<figref idref="DRAWINGS">FIG. 12</figref> conceptually illustrates a network architecture for an indirect P2P network according to some embodiments of the invention.

0024<figref idref="DRAWINGS">FIG. 13</figref> conceptually illustrates another example of an electronic system with which some embodiments of the invention are implemented.

DETAILED DESCRIPTION

0025In the following detailed description of the invention, numerous details, examples, and embodiments of the invention are set forth and described. However, it will be clear and apparent to one skilled in the art that the invention is not limited to the embodiments set forth and that the invention may be practiced without some of the specific details and examples discussed. For instance, many of the figures in this application are described with respect to a particular number of devices for the purposes of simplicity and/or explanation. One of ordinary skill in the art will realize the invention is not limited to the number of devices illustrated in these figures and that the invention may be practiced with any number of different devices.

0026Some embodiments provide a method of identifying invalid participants in a synchronization group (also referred to as a synchronization circle or a sync circle). In some embodiments, each device in the synchronization group uses an identifier to identify the device as a member of the group. In some embodiments, the device synchronization group identifier is a symmetric signature such as message authentication code. In some embodiments a key derivation function is used to generate a cryptographic key from a device-specific identifier. A cryptographic function then receives the cryptographic key as input and generates the device synchronization group identifier. Since the identifier is generated from a device-specific identifier, it is unique to each device. The identifier is also persistent in each device and is not erased or can be re-generated from the same device-specific identifier.

0027For instance, a cryptographic key is derived in some embodiments from a device specific identifier, such as media access control (MAC) address or unique device identifier (UDID). The derived cryptographic key is then used as the key for calculation of an encrypted identifier (or key) for the device to join the synchronization group identifier. This “device synchronization group identifier” is used to identify the device and is stored in the synchronization system (e.g., in a storage accessible by all member devices and/or in storage of individual member devices) without any of the privacy issues of directly using a hardware identifier of the device (e.g., because the encrypted identifier is calculated with a one-way function). In addition, in some embodiments, the device synchronization group identifier is used to sign the public key (or any other ephemeral property of the device's current instantiation) that is used by the device to join the synchronization group.

0028When a device with a newly created public/private key pair joins the synchronization system, the device compares the device synchronization group identifier of other members with its own device synchronization group identifier. If the device synchronization group identifiers match, then the new device determines that the matched device synchronization group identifier and the associated public key are its own device synchronization group identifier and public key form a previous membership in the group. The device then retires the old public key (e.g., the device deletes the old public key from the storage associated with the synchronization group or informs the other group members to delete the old public key from the storage that the other devices maintain for the synchronization group).

0029<figref idref="DRAWINGS">FIG. 1</figref> conceptually illustrates an example of starting a synchronization group and adding devices to the synchronization group according to some embodiments of the invention. The figure illustrates three stages <b>101</b>-<b>103</b> of registering two devices into the synchronization group <b>105</b>. Each of the stages <b>101</b>-<b>103</b> shows a conceptual depiction of the synchronization group <b>105</b> and a storage <b>150</b> that stores data for the synchronization group <b>105</b>. In some embodiments, the storage <b>150</b> is implemented in a cloud storage service as described in more detail below. In some embodiments, each device that is a member of the synchronization group <b>105</b> (in lieu of or in addition to the cloud storage service) stores a copy of the data in a storage <b>150</b> locally on the device. For simplicity, <figref idref="DRAWINGS">FIG. 1</figref> and several other exemplary figures described below show storage <b>150</b> as a single storage although the storage may be kept individually on each group member device.

0030The first stage <b>101</b> illustrates the synchronization group <b>105</b> with no devices registered into the synchronization group <b>105</b>. As shown, the synchronization group <b>105</b> is empty and the storage <b>150</b> contains no data regarding members of the synchronization group. The synchronization group <b>105</b> in some embodiments is linked to a cloud storage service account and devices associated with the cloud storage service account (e.g., devices that have an application or program for accessing the cloud storage associated with the account) are candidates for registering into the synchronization group <b>105</b>. The storage <b>150</b> in some such embodiments stores metadata describing the devices associated with the account.

0031In some embodiments, the synchronization group <b>105</b> does not actually exist when the synchronization group <b>105</b> is empty. The synchronization group <b>105</b> is created in some such embodiments when a first device registers into the synchronization group <b>105</b>. When one of the devices associated with the cloud storage service account enables a keychain synchronization feature on the device, the device creates the synchronization group <b>105</b> and registers itself into the synchronization group <b>105</b>.

0032The second stage <b>102</b> shows the synchronization group <b>105</b> after a device <b>110</b> has registered into the synchronization group. As shown in the second stage <b>102</b>, device A <b>110</b> is registered into the synchronization group <b>105</b> and the storage <b>150</b> is storing data identifying device A as a member of the synchronization group <b>105</b>. To register into the synchronization group, device A stores the encrypted device synchronization group identifier <b>125</b> in the storage <b>150</b> to uniquely identifies device A as a member of the synchronization group <b>105</b> without revealing the actual identity of the device. The device also stores an encryption key such as a public key <b>120</b> of the device in the storage <b>150</b>.

0033In some embodiments, each device that is in the synchronization group <b>105</b> or may potentially join the synchronization group <b>105</b> uses a public-key cryptography algorithm (e.g., an RSA algorithm, an elliptic curve cryptography (ECC) algorithm, etc.) to generate the device public/private key pair. When a device intends to identify itself to other devices, the device uses its own private key to sign a message that is sent to other devices. The other devices use the public key of the device to decrypt the messages to verify the identity of the device. Each device generates in some embodiments a device signing public/private key pair randomly. This way, each device generates a unique device signing public/private key pair that is different from the device signing public/private key pairs generated by any other device.

0034In some embodiments, when a device intends to send a secure message to another device in the synchronization group to synchronize data, the two devices establish a secure communication channel using a message-based communication protocol (e.g., off-the-record (OTR) messaging). Other embodiments, establish a secure communication channel between each pair of devices using a stream-based communication protocol (e.g., secure sockets layer (SSL)). Further details for establishing a secure communication channel between each pair of devices in a synchronization group are described below.

0035The device synchronization group identifier <b>125</b> is also unique for each device. Each device uses the corresponding encrypted device synchronization group identifier to identify the device in the synchronization group. It should be understood that the device synchronization group identifier is only verifiable by the device which generated the identifier since that is the only device that has the required key (which is derived from hardware secrets) to do so. In other words, each device can use the corresponding device synchronization group identifier to only identify itself.

0036The use of persistent and unchangeable hardware identifiers such as media access control (MAC) address or unique device identifier (UDID) causes privacy problems. Such hardware identifiers can be used to track a device across multiple accounts and multiple owners. As described in further detail below, some embodiments use a hardware unique identifier to derive a cryptographic key. The cryptographic key can be derived from a device specific identifier (such as the UDID) or from another hardware identifier via a key derivation function. The derived key is then used as the key to calculate a unique encrypted identifier (such as the device synchronization group identifier <b>125</b>) for the device. The encrypted identifier is persistent in the device and is not erased or can be re-generated from the same device-specific identifier.

0037This device synchronization group identifier is stored in the synchronization group without any of the privacy issues of using the hardware identifier directly. Since device A <b>110</b> is the first device registered into the synchronization group <b>105</b>, device A stores the public key <b>120</b> and the device synchronization group identifier <b>125</b> of the device <b>110</b> in the storage <b>150</b>. For instance, the public key <b>120</b> and the device synchronization group identifier <b>125</b> are stored in a table <b>140</b> in storage <b>150</b>.

0038The third stage <b>103</b> illustrates another device registered into the synchronization group <b>105</b>. As shown, device B <b>115</b> has joined the synchronization group <b>105</b>. The storage <b>150</b> stores the public key <b>130</b> and the device synchronization group identifier <b>135</b> of device <b>115</b>. Once device A and device B are members of the synchronization group <b>105</b>, data (such as keychain data) of the two devices are synchronized.

0039In order for device B to register into the synchronization group <b>105</b>, some embodiments require (1) that device B submit a request to join the synchronization group <b>105</b> by storing the request in the storage <b>150</b> and (2) that device A approve of the request. Different embodiments define different requirements to approve a request to join a synchronization group. For instance, some embodiments require only one device that is a member of the synchronization group to approve of the request while other embodiments require every device that is a member of the synchronization group to approve of the request.

0040Several more detailed embodiments of the invention are described in the sections below. Section I describes identifying and removing non-participant members of a synchronization group. Next, Section II describes sets of devices that use multiple verification sub-groups and synchronization sub-groups, while Section III conceptually describes details of example P2P network architectures according to some embodiments of the invention. Finally, Section IV describes an electronic system that implements some embodiments of the invention.

0000I. Removing Non-Participants from a Synchronization Group

0041As mentioned, non-participants may be an issue when the key(s) used by a device to join a synchronization group and identify itself in that synchronization group are erased, while the synchronization group still believes that the device is a valid member of the group. This may occur even after the device has re-joined the group with a new set of keys. <figref idref="DRAWINGS">FIG. 2</figref> conceptually illustrates an example of a synchronization group <b>205</b> that loses a device. The figure is shown in three stages <b>201</b>-<b>203</b>. In stage <b>201</b> three devices <b>210</b>-<b>220</b> are members of the synchronization group <b>205</b>. In stage <b>202</b>, the public/private key pair of device A <b>210</b> is erased. For instance, the hard drive of device A is replaced without restoring a backup or the public/private key is deliberately erased.

0042As shown, although device A <b>210</b> has lost its private key associated with the public key and cannot use the public key to access the synchronization group <b>205</b>, a copy of the public key is still stored in the synchronization group (e.g., in a storage accessible by all member devices and/or in storage of individual member devices). This is conceptually shown as a dashed box <b>230</b> to indicate that the other members of the synchronization group still consider device A as a member and try to synchronize data items with device A.

0043In stage <b>203</b> device A rejoins the synchronization group. For instance, device A creates a new public/private key pair and uses the new public key to join the synchronization group <b>205</b>. As shown, although device A <b>210</b> has rejoined the synchronization group, all group members including device A <b>210</b> will still try to synchronize with the “ghost” <b>230</b> of device A since the old public key of device A is still stored in the synchronization group.

0044<figref idref="DRAWINGS">FIG. 3</figref> conceptually illustrates a synchronization group where over time all participating devices have lost the private key associated with the public key that was used to join them in the synchronization group. The figure is shown in four stages <b>301</b>-<b>304</b>. Stage <b>301</b> is similar to stage <b>201</b> in <figref idref="DRAWINGS">FIG. 2</figref> where three devices <b>210</b>-<b>220</b> are members of the synchronization group <b>205</b>. In stage <b>302</b>, the public/private key pairs that were used by the device <b>210</b> to join the group are erased. For instance, the hard drive of the device is replaced without restoring from a backup. As a result, although device A <b>210</b> has lost the private key associated with its public key and cannot use the public key to access the synchronization group <b>205</b>, a copy of the public key is still stored in the synchronization group (e.g., in a storage accessible by all member devices and/or in storage of individual member devices). This is conceptually shown as a dashed box <b>310</b> to indicate that the other members of the synchronization group still consider device A as a member and try to synchronize data items with it.

0045In stage <b>303</b>, device <b>215</b> becomes a non-participant. For instance, device <b>215</b> is lost or retired. As a result, the synchronization group <b>205</b> in stage <b>303</b> only one valid participant <b>220</b>. Other members <b>310</b> and <b>315</b> of the group are non-participant (or invalid) members.

0046In stage <b>304</b>, device C <b>210</b> also becomes a non-participant. For instance, some systems require a device to maintain a certain security level (e.g., a certain number of characters in a password, etc.) in order to be a member of a synchronization group. A device that meets the security level criteria can join the synchronization group. If at a later time, the device no longer meets the security criteria (e.g., the device changes the password to include fewer than the required number of characters), the device is automatically excluded from the synchronization group. As a result, the synchronization group in stage <b>304</b> only includes non-participants <b>310</b>-<b>320</b>. Since none of the member devices can access the synchronization group and approve new devices to join the group, no devices can join the group. The synchronization group <b>205</b> has to be deleted (or left inaccessible) and a new synchronization group has to be started.

0047As described above, devices that are members of a synchronization group use a public key as well as a device synchronization group identifier to join the synchronization group. <figref idref="DRAWINGS">FIG. 4</figref> conceptually illustrates using a public key and a device synchronization group identifier for joining a device in a synchronization group in some embodiments of the invention. As shown, the device <b>420</b> generates a public Key <b>405</b> and private key <b>410</b> using a public/private key generation function <b>415</b> such as an RSA algorithm, an elliptic curve cryptography (ECC) algorithm, etc. In some embodiments a new public/private key pair is generated when the device is rest, the existing public/private key pair is deliberately erased, or when the device hard drive is replaced without restoring the contents from a backup.

0048The device also generates a unique identifier that is used to identify the device as a member of the synchronization group but cannot be used to identify the particular device to other devices in the synchronization group or to entities outside the synchronization group. For instance, the identifier can be used to identify a device as the device with identifier “abc” or as member number 5 of the synchronization group but not as Joe's cell phone, or the device with media access control (MAC) address “03:0b:96:7d:68:12”, or the device with a particular unique device identifier (UDID). In other words, the identifier can only be used to identify the device in the synchronization group but cannot be mapped to an actual physical device that can be tracked and identified. The use of an unencrypted persistent and unchangeable hardware identifier causes privacy problems, as they can be used to track a device across multiple accounts and multiple owners.

0049In the example of <figref idref="DRAWINGS">FIG. 4</figref>, a key derivation function <b>425</b> is used to generate a cryptographic key <b>430</b> from a device-specific identifier <b>435</b> (such as the MAC address or the UDID). Since the MAC address is exposed through Internet traffic, it does not alone fulfill the requirement for the device-specific hardware key. However, the MAC address can be used in the derivation of the UUID (which is unique to a device) or group identifier (GID) (which is shared among a category of products).

0050In some embodiments, the device specific identifier <b>435</b> is a high entropy key seed that is computationally prohibitive to be found by trial and error. A cryptographic function <b>440</b> such as a hash-based cryptographic function is used to generate the device synchronization group identifier. In some embodiments, the device synchronization group identifier is a message authentication code (or message digest). In some embodiments, the cryptographic function <b>440</b> is a hash-based cryptographic function, such as security hash algorithm 1 (SHA-1), that receives the cryptographic key <b>430</b> as input (the input is sometimes is referred to as a message) and generates an output (referred to as hash value or message digest) in such a way that it is practically impossible to recreate the input data from the hash value. Some embodiments use other techniques to provide the input to the cryptographic function <b>440</b>. For instance, some embodiments do not utilize a key derivation function <b>425</b> and directly provide the device-specific identifier <b>435</b> as the input to the cryptographic function <b>440</b>.

0051The device <b>420</b> then sends (e.g., through a keychain manager <b>450</b>) a request to join the synchronization group to the synchronization group <b>460</b>. Further details for the keychain manager are provided in Sections II and III, below. The request to join includes the public key <b>405</b> and the device synchronization group identifier <b>445</b> of the device. In some embodiments any of the devices <b>470</b>-<b>475</b> that are already in the synchronization group <b>460</b> can authorize device <b>420</b> to join the synchronization group <b>460</b>. In other embodiments, all member devices have to authorize a new device to join the group. In some embodiments, the device synchronization group identifier <b>445</b> is used to sign the public key <b>405</b> of the device.

0052<figref idref="DRAWINGS">FIG. 5</figref> conceptually illustrates the data stored (e.g., in a storage device in a cloud storage service and/or in the storage of each synchronization group member) in the synchronization group in some embodiments of the invention. As shown the storage <b>550</b> includes a structure such as table <b>555</b> that stores the public keys <b>508</b>, <b>515</b>, and <b>405</b> and device synchronization group identifiers <b>510</b>, <b>520</b>, and <b>445</b> of the members of the synchronization group <b>460</b>.

0053<figref idref="DRAWINGS">FIG. 6</figref> conceptually illustrates an alternative embodiment for generating the device synchronization group identifier using a secure processor embedded in a device. As shown, the device <b>620</b> includes an embedded secure processor <b>605</b>. An example of such secure processor is a secure enclave processor (SEP) that is used to secure confidential data of a device. The SEP in some embodiments includes a processor and one or more security peripherals. The SEP in some embodiments is isolated from the rest of the device (e.g., from one or more central processing units (CPUs) or application processors (APs) in the device). Access to the SEP in some embodiments is strictly controlled by hardware. For instance, some embodiments provide a mechanism in which the CPUs/APs can only access a mailbox location in the SEP. The CPUs/APs write a message to the mailbox, which the SEP reads and responds to. The SEP includes one or more of the following in some embodiments: secure key management, SEP control of boot and/or power management, and separate trust zones in memory.

0054Similar to device <b>420</b> in <figref idref="DRAWINGS">FIG. 4</figref>, device <b>620</b> generates a public Key <b>405</b> and private key <b>410</b> using a public/private key generation function <b>415</b> such as an RSA algorithm, an elliptic curve cryptography (ECC) algorithm, etc. In some embodiments a new public/private key pair is generated when the existing public/private key pair is deliberately erased or when the device hard drive is replaced without restoring the contents from a backup.

0055The secure embedded processor <b>620</b> includes a secure key <b>635</b> that is persistent after the device is rest, the device is reconfigured, or the hard drive of the device erased. The secure embedded processor <b>620</b> uses a key derivation function <b>625</b> to generate a cryptographic key <b>630</b> from secure key <b>635</b>. A cryptographic function <b>640</b> such as a hash-based cryptographic function is used to generate a device synchronization group identifier <b>645</b> from the cryptographic key <b>630</b>. In some embodiments, the SEP use other techniques to provide the input to the cryptographic function <b>640</b>. For instance, some embodiments do not utilize a key derivation function <b>625</b> and directly provide the device-specific identifier <b>635</b> as the input to the cryptographic function <b>640</b>.

0056When the device is going to join the synchronization group, the keychain manager <b>650</b> requests from the secure processor <b>605</b> and receives the device synchronization group identifier <b>645</b>. The keychain manager <b>650</b> then sends a request to join the synchronization group to the synchronization group <b>460</b>. The request to join includes the public key <b>405</b> and the device synchronization group identifier code <b>645</b> of the device. In some embodiments any of the devices <b>470</b>-<b>475</b> that are already in the synchronization group <b>460</b> can authorize device <b>620</b> to join the synchronization group <b>460</b>. In other embodiments, all member devices have to authorize a new device to join the group. In some embodiments, the device synchronization group identifier <b>645</b> is used to sign the public key <b>405</b> of the device.

0057As described above by reference to <figref idref="DRAWINGS">FIG. 2</figref>, once a device that is a member of the synchronization group loses the public key that was used to join the synchronization group the device has to rejoin the synchronization group by using a new public key. In prior art, the previous public key of the device remains in the synchronization group storage and the synchronization group members still consider the non-participant (or invalid member) device with the previous public key as a member of the synchronization group and try to synchronize data items with the non-participant member.

0058<figref idref="DRAWINGS">FIG. 7</figref> conceptually illustrates a synchronization group in which a new member detects a previous public key associated with a non-participant member as its own and retires the public key and the associated non-participant member from the group. The figure is shown in three stages <b>701</b>-<b>703</b>. In stage <b>701</b>, devices <b>710</b>-<b>720</b> are members of the synchronization group <b>705</b>. The public keys <b>730</b>-<b>740</b> and device synchronization group identifiers <b>745</b>-<b>750</b> of the member devices <b>710</b>-<b>720</b> are stored in storage <b>770</b>.

0059In stage <b>702</b>, the public key of device A <b>710</b> is erased from the device's storage. For instance, the device is reconfigured without restoring from a backup, or the public key is expressly deleted from the device. As a result, device <b>710</b> cannot use the old public key to participate in the synchronization group. However, a copy <b>730</b> of the public key and a copy <b>735</b> of the device synchronization group identifier of the device <b>710</b> are still stored in storage <b>770</b>. Other members <b>715</b>-<b>720</b> of the synchronization group <b>705</b> still consider a member <b>790</b> in the group with public key <b>730</b> and device synchronization group identifier <b>745</b>. This member <b>730</b>, however, is a non-participant or invalid member since the public key <b>730</b> is no longer accessible to the actual device <b>710</b>.

0060In stage <b>703</b>, device <b>710</b> rejoins the synchronization group with a new public key <b>760</b>. Since the device uses (as described above by reference to <figref idref="DRAWINGS">FIGS. 4-6</figref>) a device-specific identifier that does not change each time the device is reconfigured, hard drive is changed, and/or the public key of the device is erased, the device synchronization group identifier <b>745</b> of the device does not change. The new public key <b>760</b> and the device synchronization group identifier <b>745</b> are stored in the storage <b>770</b> as the information used to identify a new member of the synchronization group <b>705</b>.

0061As conceptually shown by arrows <b>780</b> and <b>785</b> in stage <b>703</b>, device A <b>710</b> determines that the device synchronization group identifier of another group member matches the device's synchronization group identifier. The device determines the other group member as itself from a previous membership in the synchronization group. Since device A <b>710</b> no longer has a private key associated with public key <b>730</b>, the device retires the non-participant member <b>730</b> from the synchronization group by removing the information (e.g., the public key <b>730</b>) from storage <b>770</b> (or by informing the other members to remove the old public key from their storages).

0062<figref idref="DRAWINGS">FIG. 8</figref> conceptually illustrates a process <b>800</b> for joining a device into a synchronization group and removing a non-participant member of the synchronization group in some embodiments of the invention. As shown, the process creates (at <b>805</b>) a public and private key pair for the device. The process then creates (at <b>810</b>) a device synchronization group identifier from a device-dependent key. For instance, the device uses any one of the methods described above by reference to <figref idref="DRAWINGS">FIGS. 4 and 6</figref>.

0063The process then joins (at <b>815</b>) the synchronization group using the public key and the device synchronization group identifier. The process then determines (at <b>820</b>) whether any other member in the synchronization group is using the same device synchronization group identifier. If not, the process ends. Otherwise, the process determines (at <b>825</b>) that the other member is a non-participant (or invalid) member of the synchronization group. Since the device synchronization group identifiers are generated from a device-specific identifier and are unique for each device, the process determines that the other member is in fact the same device that had previously joined the synchronization group with a public key that is since been erased from the device.

0064The process then retires (at <b>830</b>) the non-participant member by removing all information associated with the non-participant device including the old public key from the synchronization group storage. The process then ends.

0000II. Multiple Synchronization Groups

0065In the above examples, the user devices all participate in a single synchronization group. However, some embodiments define several synchronization sub-groups to synchronize different sets of keychain data, with devices only able to join a particular sub-group if the device meets the requirements for the sub-group. Specifically, some embodiments define verification sub-groups that devices may join if the devices satisfy membership requirements for the verification sub-groups, and use the verification sub-groups to define synchronization sub-groups in which the devices participate. Different synchronization sub-groups, in some embodiments, define different types of data items that the devices participating in the synchronization sub-groups share with each other via synchronization processes.

0066In some embodiments, the set of related electronic devices includes all devices that a user associates with a third-party service (e.g., with a particular cloud services account of the user). Knowledge of the cloud services account password serves as a requirement for membership in at least one of the verification sub-groups of some embodiments, while some embodiments define additional verification sub-groups that the various devices may join. Different embodiments define different sets of requirements for joining such additional verification sub-groups, including requirements that a device have a particular operating system, have a particular level of password strength, have a secure processor, or other device configuration properties. Some embodiments require that a device prove possession of a particular cryptographic secret in order to join a particular verification sub-group (e.g., possession of a key provided with an enterprise profile in order to join a verification sub-group defined by the enterprise), or that a user verify the membership of a new device on a device already established in the verification sub-group. In addition, some verification sub-groups may require that a new device verify a property of itself to an established device via an out-of-band process (e.g., by using a third party for verification).

0067<figref idref="DRAWINGS">FIG. 9</figref> conceptually illustrates the software architecture of a keychain manager <b>950</b> of a device <b>900</b> of some embodiments that supports such a system with multiple verification and synchronization sub-groups. In some embodiments, the keychain manager <b>950</b> performs the functions of the keychain managers <b>450</b> or <b>650</b> described above. These verification sub-groups are also referred to as rings and the synchronization sub-groups are also referred to as views. The device <b>900</b> is one of several devices associated with a cloud services account. For the discussion in this section, it will be assumed that the various devices joining rings and sharing data items through views are all associated with a single user (e.g., via a cloud services account or other user verification mechanism). Thus, in addition to the device <b>900</b>, <figref idref="DRAWINGS">FIG. 9</figref> illustrates a set of additional devices (D₂-D_N) <b>905</b>. These devices may be any different type of electronic device that is capable of storing data and communicating with a network. For instance, these devices may include smartphones, tablets, laptop and/or desktop computers, smartwatches, set top boxes (either separate from or integrated into a television), virtual devices operating on another device (e.g., virtual machines), etc.

0068As shown, the keychain manager <b>950</b> includes a synchronization engine <b>910</b>, a ring assessor <b>915</b>, and a view assessor <b>920</b>. In addition, the keychain manager <b>950</b> includes view and ring requirements <b>945</b>. The view and ring requirements might be modifiable data stored in a physical storage (e.g., a hard disk, solid state memory, random access memory, etc.) in some embodiments, or embedded into the code of the modules. For example, if the view requirements are fixed, this information might be part of the view assessor, rather than separate data pulled from storage by these modules.

0069In addition, the device <b>900</b> includes a keychain data storage <b>935</b> and a key and device ID storage <b>940</b>. The keychain data storage <b>935</b> stores keychain data items, which are the data items synchronized between the device <b>900</b> and the other device <b>905</b> in some embodiments. These data items, in some embodiments, are stored on the device encrypted with the public key associated with the device (and are stored on the other devices encrypted with the public keys of those other devices). In addition, in some embodiments, each data item stored on the device is tagged as belonging to one or more views (according to a set of view requirements that define to which views data items belong.

0070The keys and device synchronization group ID storage <b>940</b>, in some embodiments, stores various keys that the device uses for data storage, data synchronization, and ring membership joining/verification. For instance, this storage includes the public and private keys <b>405</b> and <b>410</b> as well as the device synchronization group identifier <b>445</b>, in some embodiments. In some embodiments, the keys storage <b>940</b> may also store ring signing keys (e.g., a key generated from a shared user credential such as a cloud services account password, enterprise or other keys used to join various different rings) as well as keys for protecting the synchronization data items during transport between devices. In some embodiments, these keys may be stored in various different locations on the device <b>900</b>, rather than in a single storage. For instance, some of the keys may be stored in a secure processor, separate from the standard operation of the device <b>900</b>.

0071The view and ring requirements storage <b>945</b> conceptually stores the requirements for different rings, as defined by third party developers, the device manufacturer, or the user. These requirements may include the possession of various credentials and/or cryptographic keys (e.g., the shared user password or other credential, an enterprise key, etc.), the assertion of various device and/or application properties (e.g., passcode length, operating system, possession of a secure processor, application configuration, etc.), the out-of-band verification of various properties (e.g., operating system, device validity, etc.), or various user actions (e.g., the entering of a code shown on one device on another device, moving one device within the proximity of another device, taking a picture of one device with another device, etc.). The storage <b>945</b> also stores the view requirements, which in some embodiments identify which rings a particular device (i.e., device <b>900</b> or one of the other devices <b>905</b>) must be a member of in order to participate in each different view. In addition, the storage <b>945</b> of some embodiments includes the view description, which identifies, for each view, which types of data items belong to the view. This view description may identify data items for a view based on various characteristics, including which application the data item is received from (e.g., passwords from the Wi-Fi application for a first view, passwords from a web browser application for a second view), to which World Wide Web domain a password relates (e.g., passwords from a comprehensive list of financial web domains being assigned to a specific view). In some embodiments, the view description simply specifies data items tagged as belonging to the particular view, and the user selects from a list of views when first entering the data item.

0072The ring assessor <b>915</b> (i) generates requests for the device <b>900</b> to join rings and (ii) assesses requests from the other devices <b>905</b> to join rings of which the device <b>900</b> is already a member. To generate requests, the ring assessor <b>915</b> of some embodiments uses the ring requirements to determine when the device <b>900</b> meets the membership criteria for a ring. The ring requirements may be part of the ring assessor code (e.g., if hard-coded by the device manufacturer) or retrieved from the storage <b>945</b> (e.g., if defined by the user of the device or by third-party developers). In some embodiments, the ring assessor <b>915</b> checks periodically to determine whether the device <b>900</b> has changed in such a way that it meets the requirements for a ring of which it is not yet a member, or no longer meets the requirements for a ring of which it is already a member. In other embodiments, the ring assessor <b>915</b> operates in an event-driven manner. That is, when the a device property (or other criteria that affect ring membership) changes, the ring assessor <b>915</b> is notified to determine whether the device's ring status should change.

0073When the ring assessor <b>915</b> identifies that the device meets the criteria for joining a new ring (other than any request-driven actions, such as a user approving ring membership or carrying a code from one of the devices <b>905</b> to the device <b>900</b> (or vice versa)), the ring assessor <b>915</b> generates and signs a ring joining request <b>970</b>, using any keys required for the ring request (e.g., the device public key and device synchronization group identifier used as part of the device identity for the ring, the device private key and/or any ring-specific keys used to sign the request, etc.). In addition, the ring assessor <b>915</b> may also send notifications to the other devices when it determines that the device should no longer be a member of a particular ring.

0074The ring assessor <b>915</b> also verifies ring joining requests received from the other devices <b>905</b>. As with the device <b>900</b>, when one of the other devices determines that it meets the criteria for joining a ring, that device generates and sends a ring joining request to the other devices in the ring (each device, in some embodiments, stores a list of devices in each ring, including those of which it is not a member). When the device <b>900</b> receives such a request, the ring assessor <b>915</b> verifies whether the requesting device should be allowed into the ring that it is asking to join. This may entail verifying that the request is signed with the appropriate key(s), verifying that any out-of-band criteria have been met or performing the out-of-band checks (e.g., that the requesting device is a valid device, that a code generated on the device <b>900</b> has been properly entered on the requesting device, etc.), that the device has properly asserted its criteria for joining the ring, that the user of the device <b>900</b> has approved the requesting device, etc. When the ring joining request is verified, the ring assessor <b>915</b> sends out a ring status message (not shown) to the other devices <b>905</b> that are in the ring. The ring status message, in some embodiments, is a list of the devices in the ring, including the recently-added device. This serves to notify the requesting device that it has successfully joined the ring, as well as to notify the other devices that the device <b>900</b> has approved the membership of the requesting device (and therefore that they do not need to separately process the membership request). In some embodiments, this notification message is signed with a private key of a ring-specific key pair (e.g., the key that was used to sign the membership request).

0075The ring assessor <b>915</b> also keeps the view assessor <b>920</b> regularly apprised of the current ring status <b>980</b> of the device <b>900</b> as well as the other devices <b>905</b>. In some embodiments, the view assessor <b>920</b> requests this information as needed from the ring assessor <b>915</b> (or from a storage to which the ring assessor stores this information). The view assessor <b>920</b> is responsible for determining which of the devices (including the device <b>900</b> and the other devices <b>905</b>) participate in each of the different views defined for the group of devices. Specifically, in some embodiments, the view assessor determines (at any given point in time, based on the current ring membership status of all of the devices) a mapping between views and devices (i.e., for each device, in which views does the device participate; or for each view, which device participate). The view assessor <b>920</b> makes this determination based on the view requirements which, again, may either be coded in to the view assessor by the device manufacturer or be variable information generated by third-party developers and/or users in various different embodiments.

0076In some embodiments, the synchronization engine <b>910</b> is responsible for syncing the view-tagged keychain data items with other devices <b>905</b>, as well as communicating the ring joining requests and notifications. The sync engine <b>910</b>, in some embodiments, determines that it should synchronize data items with another device, and receives from the view assessor <b>920</b> the list <b>990</b> of views in which the particular other device participates, and any special channel requirements for each of the views. The synchronization engine <b>910</b> retrieves the view-tagged keychain data items <b>960</b> that belong to the correct views from the keychain data storage <b>935</b> and synchronizes these data items to the other device via the secure channel. In some embodiments, this entails removing the encryption on the keychain data items used during storage on the device and re-encrypting the keychain data items with a shared key used for the secure channel.

0077Thus, devices may belong to multiple rings (verification sub-groups) and participate in the synchronization process for multiple views (synchronization sub-groups). In some embodiments, the device group identifier and public key are used to join rings, and thus the devices (e.g., the ring assessors on the devices) monitor ring membership to determine whether duplicate devices are members (based on the duplicate device IDs with different public keys). When this is the case, the devices remove the old duplicate device from the ring membership, which will in turn remove that device from the views that require membership in that particular ring. The rings and views of some embodiments are described in greater detail in U.S. Provisional Patent Application 62/168,893, filed May 31, 2015, and the concurrently filed U.S. Application 14/872,013, now published as U.S. Patent Publication 2016/0349999, and entitled “Synchronization and Verification Groups Among Related Devices,” which are incorporated herein by reference.

0000III. Peer-to-Peer Network Architectures

0078Some embodiments synchronize keychains between devices that are members of a synchronization group through a peer-to-peer (P2P) network. The P2P network of different embodiments are implemented using different network architectures in order to facilitate communication between the devices in the synchronization group. The following figures illustrate several examples of different implementations of P2P network architectures.

0079<figref idref="DRAWINGS">FIG. 10</figref> conceptually illustrates a network architecture for a direct P2P network according to some embodiments of the invention. In this example, devices A-C <b>1001</b>-<b>1003</b> are members of a synchronization group. As shown, each of the devices A-C includes storage <b>1010</b> for storing passwords and a keychain manager <b>1005</b>. The keychain manager <b>1005</b> in some embodiments is responsible for performing the functions for facilitating the synchronization of keychain data between devices A-C.

0080A keychain, in some embodiments, is a defined collection of data. Examples of data items in a keychain include one or more of the following: private keys; certificates; secure notes; usernames, passwords, and/or account numbers for accessing websites, applications, networks, bank accounts, credit cards; other types of passwords and confidential information; information about a device's accounts such as electronic mail, contacts, calendar, and messages; and any other information that is desired to be shared among a set of different devices.

0081In some embodiments, the keychain manager generates and stores a data structure to represent a keychain. <figref idref="DRAWINGS">FIG. 11</figref> conceptually illustrates a data structure <b>1105</b> for a keychain as stored by the keychain manager of some embodiments. As shown, the data structure <b>1105</b> includes a keychain identifier (ID) <b>1110</b>, keychain items <b>1</b>-N, and access data <b>1115</b>. The keychain ID <b>1110</b> is a unique identifier for identifying the keychain <b>1105</b>. The access data <b>1115</b> is for controlling access (e.g., what applications may access the keychain <b>1105</b> and/or what operations (e.g., read, write, delete, etc.) may be performed on the keychain <b>1105</b>, etc.) to the keychain <b>1105</b> itself and is similar in structure to the access data <b>1135</b> described below.

0082As shown in <figref idref="DRAWINGS">FIG. 11</figref>, keychain item <b>1120</b> represents keychain item <b>1</b> of the keychain <b>1105</b>. Keychain item <b>1120</b> includes a keychain item ID <b>1125</b>, data <b>1130</b>, attributes 1-M, an access data <b>1135</b> (also referred to as an access object). The keychain item ID <b>1125</b> is a unique identifier for identifying the keychain item <b>1120</b>.

0083Data <b>1130</b> is the actual data value and/or values of the keychain item <b>1120</b>. For instance, if the keychain <b>1120</b> represents a password, the data <b>1130</b> stores the value of the password (e.g., a string of alphanumeric characters). In some embodiments, the keychain manager encrypts the data of certain types of a keychain items (e.g., passwords, private keys, etc.) when the keychain manager stores the data. For the data of other types of keychain items (e.g., certificates), the keychain manager simply stores the data without encrypting the data.

0084Attributes 1-M of the keychain item <b>1120</b> are for storing metadata describing the keychain item <b>1120</b>. Different types of keychain items have different sets of attributes. For example, Internet passwords have attributes that include attributes such as security domain, protocol type (e.g., hypertext transfer protocol (HTTP), hypertext transfer protocol secure (HTTPS), file transfer protocol (FTP), etc.), path (e.g., a uniform resource locator (URL) of an Internet resource), etc.

0085Each keychain item in some embodiments includes a date field attribute that indicates the time and date (also referred to as a timestamp) of the most recent modification to the keychain item. In some embodiments, each keychain item also includes an attribute for specifying that the keychain item is a keychain item that has been deleted (also referred to as a tombstone). When the attribute specifies that the keychain item is a tombstone, the keychain manager maintains the date field of the keychain item, but the keychain manager sets the value of the keychain items' data <b>1130</b> to null or empty. In some embodiments, a keychain item that resulted from a resolution of conflicting keychain items includes a set of attributes that includes (1) a flag indicating that the keychain item is the result of a conflict resolution, (2) a version number of the conflict resolver used to resolve the conflict, and (3) the conflicting keychain items from which the keychain item was resolved (also referred to as the parent keychain items). The set of attributes is referred to as the keychain item's conflict resolution metadata in some embodiments.

0086In some embodiments, the attributes or a subset of the attributes of a keychain item is used as a primary key for uniquely identifying the keychain item. That is, two keychain items with the same primary key are considered the same keychain item (regardless of whether the values of the data of the keychain items are the same).

0087The access data <b>1135</b> is for controlling access to the keychain item <b>1120</b>. As illustrated, the access data <b>1135</b> includes access control list (ACL) entries 1-K for controlling access to the keychain item <b>1120</b>. <figref idref="DRAWINGS">FIG. 11</figref> illustrates an ACL entry <b>1140</b> that represents the ACL entry 1 of the access data <b>1135</b>. The ACL entry <b>1140</b> includes authorization tags <b>1145</b> that specify operations (e.g., read, write, delete, decrypt, authenticate, etc.) that can be performed on the keychain item <b>1120</b>. In this example, the authorization tags <b>1145</b> includes authorization tags 1-H.

0088Additionally, the ACL entry <b>1140</b> includes a list of trusted applications <b>1150</b>. As shown, the list of trusted application <b>1150</b> includes application ID 1-J. Each application ID is a unique identifier for identifying a particular application that may perform the operations specified by the authorization tags <b>1145</b> without user authorization.

0089One of ordinary skill in the art will recognize that the keychain data structure <b>1150</b> is only one possible data structure that the keychain manager might use to store the required information for a keychain. For example, different embodiments might store additional or less information, store the information in a different order, etc.

0090Referring back to <figref idref="DRAWINGS">FIG. 10</figref>, the keychain manager <b>1005</b> in some embodiments handles the registration of the device into synchronization group, synchronizing passwords between devices in the group, resolving conflicts between conflicting passwords, and providing a secure communication channel for transporting data between devices A-C, etc.

0091As illustrated in <figref idref="DRAWINGS">FIG. 10</figref>, devices A-C communicate with each other through an overlay network with a fully connected mesh topology. As such, each of the devices A-C can directly communicate with each of the other devices. That is, device A can directly communicate with devices B and C, device B can directly communicate with devices A and C, and device C can directly communicate with devices A and B. As shown, a synchronization group <b>1050</b> is created using the P2P network and some or all devices <b>1001</b>-<b>1003</b> can join. In the example of <figref idref="DRAWINGS">FIG. 10</figref>, devices <b>1001</b> and <b>1002</b> have joined the synchronization group <b>1050</b> and maintain a data structure <b>1010</b> that is similar to data structures <b>550</b> and <b>770</b> described above to store the information (e.g., the public keys and device synchronization group identifiers) of the members of the synchronization group.

0092Some embodiments provide a secure transport layer to protect the data that devices communicate with each other. For this example, devices A-C communicate with each other through secure communication channels established between each pair of devices A-C. The secure communication channels may be implemented using any number of different protocols, such as message-based communication protocols (e.g., OTR messaging), stream-based communication protocols (e.g., SSL), etc.

0093In addition, each individual device uses the device's own public key and a public key of the user of the device to encrypt any data items that are stored on the device. In some embodiments, all devices in a synchronization group belong to the same user and the public key of the user of the device is the same in all devices.

0094<figref idref="DRAWINGS">FIG. 12</figref> conceptually illustrates a network architecture for an indirect P2P network according to some embodiments of the invention. In this example, devices A-C <b>1001</b>-<b>1003</b> are members of a synchronization group and each of the devices A-C includes the storage <b>1010</b> and the keychain manager <b>1005</b>.

0095As shown in <figref idref="DRAWINGS">FIG. 12</figref>, devices A-C communicate with each other through an overlay network with a star topology. In particular, devices A-C communicate with each other through cloud services <b>1205</b>, which serves as the center of the star topology and provides a cloud storage service for storing data as well as other cloud services (e.g., cloud computing services). For instance, when device A wishes to communicate data to device B, device A stores the data in the cloud services <b>1205</b>, the cloud services <b>1205</b> notifies (e.g., via a push notification service) device B about the data, and device B retrieves the data from the cloud services <b>1205</b>. The set of cloud servers <b>1235</b> in some embodiments control storages <b>1210</b>-<b>1230</b> of the cloud services as well as providing computing services.

0096As illustrated, the cloud services <b>1205</b> includes a group of cloud storage servers <b>1235</b>. The cloud service may include one or more other servers such as application servers, network servers, etc., which are not shown for simplicity. As shown, the cloud storage servers <b>1235</b> include one or more storages <b>1210</b>-<b>1230</b>. One of ordinary skill in the art will recognize that storages shown in <figref idref="DRAWINGS">FIG. 12</figref> are only examples of the storages provided by a cloud service.

0097As shown, a synchronization group <b>1280</b> is created using the P2P network and some or all devices <b>1001</b>-<b>1003</b> can join. In the example of <figref idref="DRAWINGS">FIG. 12</figref>, the cloud service stores the information regarding the synchronization group. In other embodiments, in addition or as an alternative, each individual device that is a member of the synchronization group stores the information regarding the synchronization group. <figref idref="DRAWINGS">FIG. 12</figref> shows the embodiments in which the cloud service stores the synchronization information. The embodiments that store the information in each member device maintain similar exemplary information in each individual device.

0098As shown, the cloud services in some embodiments stores a name for a synchronization group and a synchronization group device list in storage <b>1210</b> that specifies the devices that are members of the synchronization group. In some embodiments, the devices are specified by data uniquely identifying the devices. Examples of such data include a public key of a device signing public/private key pair for authenticating the identity of a device, a device type of the device (e.g., a desktop computer, a tablet, a smartphone, etc.), a name of the device, etc., or a combination of any number of such data.

0099The cloud services <b>1205</b> also stores user signatures in storage <b>1215</b>. A user signature in some embodiments is a digital signature for authenticating the identity of a user as the signer of a message, document, or any other type of data. In some embodiments, the synchronization group is linked to a cloud services account and devices associated with the cloud services account (e.g., devices that have an application or program for accessing the cloud services associated with the account) are candidates for registering into the synchronization group. The storage <b>1215</b> in some such embodiments includes signatures signed with a private key of a user signing public/private key pair generated based on a password of the cloud services account to indicate that the user of the cloud services account is the signer. Examples of user signatures that are stored in the storage <b>1215</b> include a signature of the synchronization group device list signed with a private key of a user signing public/private key pair, signatures of registration requests signed with the private key of the user signing key pair, and/or any other signatures for authenticating the identity of the user of the cloud services account.

0100<figref idref="DRAWINGS">FIG. 12</figref> also shows that the cloud services <b>1205</b> stores device signatures in storage <b>1220</b>. In some embodiments, a device signature is a digital signature for authenticating the identity of a device in the synchronization group as the signer of a message, document, or any other type of data. For example, in some embodiments, the storage <b>1220</b> includes signatures of the synchronization group device list signed with a private key of a device signing public/private key pair that belongs to a device that is a member of the synchronization group. Such a signature indicates that the signing device affirms the list of devices in the synchronization group device list as the members of the synchronization group. In some embodiments, when the synchronization group is in a steady state (e.g., no registration requests are pending nor unapproved), the device signatures in the storage <b>1220</b> includes for each device that is a member of the synchronization group a signature of the synchronization group device list signed with a private key of the device's device signing public/private key pair. That is, the signatures in such instances collectively indicate that every device listed in the synchronization group device list agrees that the devices listed in the synchronization group device list are the members of the synchronization group.

0101In some embodiments, the cloud services <b>1205</b> stores the device public keys and device synchronization group identifiers in a storage <b>1240</b> similar to storages <b>550</b> and <b>770</b> described above. In addition, the cloud services <b>1205</b> stores keychain data in storage <b>1225</b> for synchronizing keychains between the devices in the synchronization group, and other data in storage <b>1230</b> that may include a public key of a user signing public/private key pair, a random string (e.g., a 256-bit string) shared between the devices in the synchronization group for generating the user signing key pair, and a list of pending registration requests. In some embodiments, the cloud services <b>1205</b> implements the storages <b>1210</b>-<b>1240</b> as key-value stores.

0102While the storages <b>1210</b>-<b>1240</b> are illustrated in <figref idref="DRAWINGS">FIG. 12</figref> as separate storages, in some embodiments, the storages <b>1210</b>-<b>1240</b> are implemented as a single storage, while, in other embodiments, the storages <b>1210</b>-<b>1240</b> are implemented across several storages.

0103In some embodiments, the secure transport layer described above by reference to <figref idref="DRAWINGS">FIG. 10</figref> is utilized to protect the data that devices communicate with each other through the cloud services <b>1205</b>. That is, while devices A-C communicate with each other through secure communication channels established between each pair of devices A-C, the devices A-C use the cloud services <b>1205</b> as a mechanism for transporting the communications. The secure communication channels of some embodiments may be implemented in some embodiments using any number of different protocols (e.g., message-based communication protocols (e.g., OTR messaging), stream-based communication protocols (e.g., SSL), etc.).

0000IV. Electronic System

0104Many of the above-described features and applications are implemented as software processes that are specified as a set of instructions recorded on a computer readable storage medium (also referred to as computer readable medium). When these instructions are executed by one or more computational or processing unit(s) (e.g., one or more processors, cores of processors, or other processing units), they cause the processing unit(s) to perform the actions indicated in the instructions. Examples of computer readable media include, but are not limited to, CD-ROMs, flash drives, random access memory (RAM) chips, hard drives, erasable programmable read-only memories (EPROMs), electrically erasable programmable read-only memories (EEPROMs), etc. The computer readable media does not include carrier waves and electronic signals passing wirelessly or over wired connections.

0105In this specification, the term “software” is meant to include firmware residing in read-only memory or applications stored in magnetic storage, which can be read into memory for processing by a processor. Also, in some embodiments, multiple software inventions can be implemented as sub-parts of a larger program while remaining distinct software inventions. In some embodiments, multiple software inventions can also be implemented as separate programs. Finally, any combination of separate programs that together implement a software invention described here is within the scope of the invention. In some embodiments, the software programs, when installed to operate on one or more electronic systems, define one or more specific machine implementations that execute and perform the operations of the software programs.

0106<figref idref="DRAWINGS">FIG. 13</figref> conceptually illustrates another example of an electronic system <b>1300</b> with which some embodiments of the invention are implemented. The electronic system <b>1300</b> may be a computer (e.g., a desktop computer, personal computer, tablet computer, etc.), phone, PDA, or any other sort of electronic or computing device. Such an electronic system includes various types of computer readable media and interfaces for various other types of computer readable media. Electronic system <b>1300</b> includes a bus <b>1305</b>, processing unit(s) <b>1310</b>, a system memory <b>1320</b>, a network <b>1325</b>, a read-only memory <b>1330</b>, a permanent storage device <b>1335</b>, input devices <b>1340</b>, and output devices <b>1345</b>.

0107The bus <b>1305</b> collectively represents all system, peripheral, and chipset buses that communicatively connect the numerous internal devices of the electronic system <b>1300</b>. For instance, the bus <b>1305</b> communicatively connects the processing unit(s) <b>1310</b> with the read-only memory <b>1330</b>, the system memory <b>1320</b>, and the permanent storage device <b>1335</b>.

0108From these various memory units, the processing unit(s) <b>1310</b> retrieves instructions to execute and data to process in order to execute the processes of the invention. The processing unit(s) may be a single processor or a multi-core processor in different embodiments.

0109The read-only-memory (ROM) <b>1330</b> stores static data and instructions that are needed by the processing unit(s) <b>1310</b> and other modules of the electronic system. The permanent storage device <b>1335</b>, on the other hand, is a read-and-write memory device. This device is a non-volatile memory unit that stores instructions and data even when the electronic system <b>1300</b> is off. Some embodiments of the invention use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive, integrated flash memory) as the permanent storage device <b>1335</b>.

0110Other embodiments use a removable storage device (such as a floppy disk, flash memory device, etc., and its corresponding drive) as the permanent storage device. Like the permanent storage device <b>1335</b>, the system memory <b>1320</b> is a read-and-write memory device. However, unlike storage device <b>1335</b>, the system memory <b>1320</b> is a volatile read-and-write memory, such a random access memory. The system memory <b>1320</b> stores some of the instructions and data that the processor needs at runtime. In some embodiments, the invention's processes are stored in the system memory <b>1320</b>, the permanent storage device <b>1335</b>, and/or the read-only memory <b>1330</b>. For example, the various memory units include instructions for processing multimedia clips in accordance with some embodiments. From these various memory units, the processing unit(s) <b>1310</b> retrieves instructions to execute and data to process in order to execute the processes of some embodiments.

0111The bus <b>1105</b> also connects to the input and output devices <b>1340</b> and <b>1345</b>. The input devices <b>1340</b> enable the user to communicate information and select commands to the electronic system. The input devices <b>1340</b> include alphanumeric keyboards and pointing devices (also called “cursor control devices”), cameras (e.g., webcams), microphones or similar devices for receiving voice commands, etc. The output devices <b>1345</b> display images generated by the electronic system or otherwise output data. The output devices <b>1345</b> include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD), as well as speakers or similar audio output devices. Some embodiments include devices such as a touchscreen that function as both input and output devices.

0112Finally, as shown in <figref idref="DRAWINGS">FIG. 13</figref>, bus <b>1305</b> also couples electronic system <b>1300</b> to a network <b>1325</b> through a network adapter (not shown). In this manner, the computer can be a part of a network of computers (such as a local area network (“LAN”), a wide area network (“WAN”), or an Intranet), or a network of networks, such as the Internet. Any or all components of electronic system <b>1300</b> may be used in conjunction with the invention.

0113Some embodiments include electronic components, such as microprocessors, storage and memory that store computer program instructions in a machine-readable or computer-readable medium (alternatively referred to as computer-readable storage media, machine-readable media, or machine-readable storage media). Some examples of such computer-readable media include RAM, ROM, read-only compact discs (CD-ROM), recordable compact discs (CD-R), rewritable compact discs (CD-RW), read-only digital versatile discs (e.g., DVD-ROM, dual-layer DVD-ROM), a variety of recordable/rewritable DVDs (e.g., DVD-RAM, DVD-RW, DVD+RW, etc.), flash memory (e.g., SD cards, mini-SD cards, micro-SD cards, etc.), magnetic and/or solid state hard drives, read-only and recordable Blu-Ray® discs, ultra density optical discs, any other optical or magnetic media, and floppy disks. The computer-readable media may store a computer program that is executable by at least one processing unit and includes sets of instructions for performing various operations. Examples of computer programs or computer code include machine code, such as is produced by a compiler, and files including higher-level code that are executed by a computer, an electronic component, or a microprocessor using an interpreter.

0114While the above discussion primarily refers to microprocessor or multi-core processors that execute software, some embodiments are performed by one or more integrated circuits, such as application specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs). In some embodiments, such integrated circuits execute instructions that are stored on the circuit itself. In addition, some embodiments execute software stored in programmable logic devices (PLDs), ROM, or RAM devices.

0115As used in this specification and any claims of this application, the terms “computer”, “server”, “processor”, and “memory” all refer to electronic or other technological devices. These terms exclude people or groups of people. For the purposes of the specification, the terms display or displaying means displaying on an electronic device. As used in this specification and any claims of this application, the terms “computer readable medium,” “computer readable media,” and “machine readable medium” are entirely restricted to tangible, physical objects that store information in a form that is readable by a computer. These terms exclude any wireless signals, wired download signals, and any other ephemeral signals.

0116While the invention has been described with reference to numerous specific details, one of ordinary skill in the art will recognize that the invention can be embodied in other specific forms without departing from the spirit of the invention. In addition, a number of the figures such as <figref idref="DRAWINGS">FIG. 8</figref> conceptually illustrate processes. The specific operations of these processes may not be performed in the exact order shown and described. The specific operations may not be performed in one continuous series of operations, and different specific operations may be performed in different embodiments. Furthermore, the process could be implemented using several sub-processes, or as part of a larger macro process. Thus, one of ordinary skill in the art would understand that the invention is not to be limited by the foregoing illustrative details, but rather is to be defined by the appended claims.