1Breadcrumbs
2===========
3
4simple defintions:
5
6	old password 
7	new password
8	K = random 16 byte key
9	EK = Encrypted K
10	EKold =  ECB(PBKDF2(password_old), K)
11	EKnew =  ECB(PBKDF2(password_new), K)
12	Breadcrumb = AES-GCM(K, old password)
13
14
15Breadcrumbs are to make life easier when using AppleID password as
16local password by allowing upgrade of keychains from old password to new
17password.
18
19When changing the password on one machine, the keychains for the user are
20still encrypted (AES-GCM, key derived using PBKDF2) with the old password on
21all machines.
22
23This happens for one machine when changing password on the AppleID.apple.com webpage.
24
25An EK is stored on the apple server. Each machine have its own EK stored on the web server.
26
27When user change the password on the AppleID.apple.com website, the
28web server will unwrap the key K with the old password and then rewrap
29it with the new password.
30
31	unwrap(EKold, old password) -> K
32	wrap(K, new password) -> EKnew
33
34This means that if the user changes password more then ones, the computer can still upgrade the keychain to the current password since K will be the same until a new EK is uploaded the the computer.
35
36PKDF2 is used to avoid prebuilt lists of string2key tables attacks on
37the breadcrumb + encryptedKey if the attacker possesses both.
38
39Breadcrumb contain current password that encrypts the keychain. The breadcrumb itself is encrypted with a machine-specific key K.
40
41The breadcrumb is stored on the local machine and never leaves the
42local machine.
43
44When the computer have upgrade keychain to the current password and new K, EK, and breadcrumb is generated.
45
46Format
47======
48
49K = Random 16 byte
50EK = ECB(PBKDF2(pw), key K) (16byte) | pbkdf-salt (20byte) | 4byte int network order of pbdf-iter
51Breadcrumb = version (1) 1byte | AES-GCM-ENC(key K, password length (4byte, network order) | password | pad  ) | tag
52
53The encrypted key (EK) is a PKDF2 salt + iteration count + random AES-128 key (K) 
54encrypted with ECB of the PKDF2(salt, iteration, password).
55
56There is no integrity on this encryption on purpose since that would make the
57EK an verifier.
58
59The format of the EncryptedKey is
60
61    ECB(PBKDF2(pw), key K) (16byte) | pbkdf-salt (20byte) | 4byte int network order of pbdf-iter
62    
63The random key (K) is used to encrypt a breadcrumb that is stored
64locally on the machine. The breadcrumb allows you to recover the old
65password if you know the new password and have the encrypted key.
66
67The client machine encrypts the password with AES-GCM using key K. The data
68is padded to 256 bytes to no tell password length.
69
70The format of the breadcrumb
71
72    version (1) 1byte | AES-GCM-ENC(key K, password length (4byte, network order) | password | pad  ) | tag
73    
74tag is the 16 byte GCM tag
75key is the key (K) from the EncryptedKey (EK)
76assoc data i AES-GCM covers version byte
77
78Password length including up to pad is encrypted with AES-GCM
79
80Password is padded to paddingSize (256) to avoid exposing length of password.
81
82The PBKDF2 function is PBKDF2-HMAC-SHA256.
83
84
85Updating the Encrypted Key (EK) on server
86=========================================
87
88When a user update the password on the apple id server the server
89updates the breadcrumb for each machine that the user have associsated
90with the account.
91
921. The server takes the old password generates a the key using PBKDF2
93   using the salt and interation count.
94
952. The server takes the new password generates a the key using PBKDF2
96   using the same salt and interation count.
97
983. Decrypts the first block with the key of old password and
99   re-encrypt with the key of new password.
100