OSX/Breadcrumb/README

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