sec/SOSCircle/SecureObjectSync/SOSEngine.c

   1 /*
   2  * Created by Michael Brouwer on 7/17/12.
   3  * Copyright 2012 Apple Inc. All Rights Reserved.
   4  */
   5
   6 /*
   7  * SOSEngine.c -  Implementation of a secure object syncing engine
   8  */
   9
  10 #include <SecureObjectSync/SOSEngine.h>
  11 #include <SecureObjectSync/SOSPeer.h>
  12 #include <SecureObjectSync/SOSPeerInfo.h>
  13 #include <corecrypto/ccder.h>
  14 #include <stdlib.h>
  15 #include <stdbool.h>
  16 #include <utilities/SecCFError.h>
  17 #include <utilities/SecCFRelease.h>
  18 #include <utilities/SecCFWrappers.h>
  19 #include <utilities/der_plist.h>
  20 #include <utilities/der_plist_internal.h>
  21 #include <utilities/debugging.h>
  22 #include <utilities/iCloudKeychainTrace.h>
  23 #include <AssertMacros.h>
  24 #include <CoreFoundation/CoreFoundation.h>
  25 #include <SecItemServer.h>
  26 #include <SecItemPriv.h>
  27
  28 /* DataSource helper macros and functions. */
  29
  30 // TODO: Change to create with DER.
  31 #define SOSObjectCreateWithPropertyList(dataSource, plist, error) (dataSource->createWithPropertyList(dataSource, plist, error))
  32
  33 #define SOSObjectCopyPropertyList(dataSource, object, error) (dataSource->copyPropertyList(object, error))
  34 #define SOSObjectCopyDigest(dataSource, object, error) (dataSource->copyDigest(object, error))
  35 #define SOSObjectCopyPrimaryKey(dataSource, object, error) (dataSource->copyPrimaryKey(object, error))
  36 #define SOSObjectCopyMergedObject(dataSource, object1, object2, error) (dataSource->copyMergedObject(object1, object2, error))
  37
  38 #define kSOSMaxObjectPerMessage (500)
  39
  40 static CFArrayRef SOSDataSourceCopyObjectArray(SOSDataSourceRef data_source, SOSManifestRef manifest, CFErrorRef *error) {
  41     CFMutableArrayRef objects = CFArrayCreateMutable(0, 0, &kCFTypeArrayCallBacks);
  42
  43     // Delta sync by only sending a max of kSOSMaxObjectPerMessage objects at a time.
  44     SOSManifestRef toSend = NULL;
  45     if (SOSManifestGetCount(manifest) > kSOSMaxObjectPerMessage) {
  46         toSend = SOSManifestCreateWithBytes(SOSManifestGetBytePtr(manifest), kSOSMaxObjectPerMessage * SOSDigestSize, error);
  47     } else {
  48         toSend = manifest;
  49         CFRetain(toSend);
  50     }
  51
  52     if (!data_source->foreach_object(data_source, toSend, error, ^bool (SOSObjectRef object, CFErrorRef *localError) {
  53         CFDictionaryRef plist = SOSObjectCopyPropertyList(data_source, object, localError);
  54         if (plist) {
  55             CFArrayAppendValue(objects, plist);
  56             CFRelease(plist);
  57         }
  58         return plist;
  59     })) {
  60         CFReleaseNull(objects);
  61     }
  62     CFRetainSafe(toSend);
  63     return objects;
  64 }
  65
  66 static CFDataRef SOSDataSourceCopyManifestDigest(SOSDataSourceRef ds, CFErrorRef *error) {
  67     CFMutableDataRef manifestDigest = CFDataCreateMutable(0, SOSDigestSize);
  68     CFDataSetLength(manifestDigest, SOSDigestSize);
  69     if (!ds->get_manifest_digest(ds, CFDataGetMutableBytePtr(manifestDigest), error))
  70         CFReleaseNull(manifestDigest);
  71
  72     return manifestDigest;
  73 }
  74
  75 static SOSManifestRef SOSDataSourceCopyManifest(SOSDataSourceRef ds, CFErrorRef *error) {
  76     return ds->copy_manifest(ds, error);
  77 }
  78
  79 static void SOSDataSourceRelease(SOSDataSourceRef ds) {
  80     ds->release(ds);
  81 }
  82
  83
  84 /* SOSEngine implementation. */
  85
  86 static CFStringRef sErrorDomain = CFSTR("com.apple.security.sos.engine.error");
  87
  88 static bool SOSEngineCreateError(CFIndex errorCode, CFStringRef descriptionString, CFErrorRef previousError, CFErrorRef *newError) {
  89     SecCFCreateError(errorCode, descriptionString, sErrorDomain, previousError, newError);
  90     return true;
  91 }
  92
  93 struct __OpaqueSOSEngine {
  94     SOSDataSourceRef dataSource;
  95 };
  96
  97 SOSEngineRef SOSEngineCreate(SOSDataSourceRef dataSource, CFErrorRef *error) {
  98     SOSEngineRef engine = calloc(1, sizeof(struct __OpaqueSOSEngine));
  99     engine->dataSource = dataSource;
 100
 101     return engine;
 102 }
 103
 104 void SOSEngineDispose(SOSEngineRef engine) {
 105     SOSDataSourceRelease(engine->dataSource);
 106     free(engine);
 107 }
 108
 109 /* SOSEngine. */
 110 enum SOSMessageType {
 111     SOSManifestInvalidMessageType = 0,
 112     SOSManifestDigestMessageType = 1,
 113     SOSManifestMessageType = 2,
 114     SOSManifestDeltaAndObjectsMessageType = 3,
 115 };
 116
 117 /* H(): SHA1 hash function.
 118  M: Manifest of peer p
 119  MSG: H(M).
 120
 121
 122  SOSPeerMessage := SEQUENCE {
 123  messageType INTEGER (manifestDigest, manifest, manifestDeltaAndObjects)
 124  version INTEGER OPTIONAL default v0
 125  content ANY defined by messageType
 126  }
 127
 128  ManifestDigest := OCTECT STRING (length 20)
 129  Manifest := OCTECT STRING (length 20 * number of entries)
 130
 131
 132  Value := CHOICE {
 133  bool Boolean
 134  number INTEGER
 135  string UTF8String
 136  data OCTECT STRING
 137  date GENERAL TIME
 138  dictionary Object
 139  array Array
 140  }
 141
 142  KVPair := SEQUENCE {
 143  key UTF8String
 144  value Value
 145  }
 146
 147  Array := SEQUENCE of Value
 148  Dictionary := SET of KVPair
 149
 150  Object := SEQUENCE {
 151  [0] conflict OCTECT STRING OPTIONAL
 152  [1] change OCTECT STRING OPTIONAL
 153  object Dictionary
 154
 155
 156  ManifestDeltaAndObjects := SEQUENCE {
 157  manfestDigest ManifestDigest
 158  removals Manifest
 159  additions Manifest
 160  addedObjects SEQUENCE of Object
 161  }
 162
 163  manifestDigest content = OCTECT STRING
 164  manifest content := OCTECT STRING
 165  manifestDeltaAndObjects := SEQUENCE {
 166  manfestDigest ManifestDigest
 167  }
 168
 169  */
 170
 171
 172 /* ManifestDigest message */
 173 static size_t der_sizeof_manifest_digest_message(void) {
 174     return ccder_sizeof(CCDER_CONSTRUCTED_SEQUENCE,
 175                         (ccder_sizeof_uint64(SOSManifestDigestMessageType) +
 176                          ccder_sizeof_raw_octet_string(SOSDigestSize)));
 177 }
 178
 179 static uint8_t *der_encode_manifest_digest_message(const uint8_t digest[SOSDigestSize], const uint8_t *der, uint8_t *der_end) {
 180     return ccder_encode_constructed_tl(CCDER_CONSTRUCTED_SEQUENCE, der_end, der,
 181            ccder_encode_uint64(SOSManifestDigestMessageType, der,
 182            ccder_encode_raw_octet_string(SOSDigestSize, digest, der, der_end)));
 183 }
 184
 185 /* This message is sent to each peer that joins a circle and can also be sent
 186  as a form of ACK to confirm that the local peer is in sync with the peer
 187  this is beig sent to. */
 188 CFDataRef SOSEngineCreateManifestDigestMessage(SOSEngineRef engine, SOSPeerRef peer, CFErrorRef *error) {
 189     /* TODO: avoid copying the digest here by inlining der_encode_manifest_digest_message(). */
 190
 191     uint8_t digest[SOSDigestSize];
 192     if (!engine->dataSource->get_manifest_digest(engine->dataSource, &digest[0], error)) {
 193         return NULL;
 194     }
 195
 196     size_t der_size = der_sizeof_manifest_digest_message();
 197     CFMutableDataRef message = CFDataCreateMutable(NULL, der_size);
 198     if (message == NULL) {
 199         return NULL;
 200     }
 201     CFDataSetLength(message, der_size);
 202     uint8_t *der_end = CFDataGetMutableBytePtr(message);
 203     const uint8_t *der = der_end;
 204     der_end += der_size;
 205
 206     der_end = der_encode_manifest_digest_message(digest, der, der_end);
 207     assert(der == der_end);
 208
 209     return message;
 210 }
 211
 212
 213 /* Manifest message */
 214 static size_t der_sizeof_manifest_message(SOSManifestRef manifest) {
 215     return ccder_sizeof(CCDER_CONSTRUCTED_SEQUENCE,
 216                         (ccder_sizeof_uint64(SOSManifestMessageType) +
 217                          ccder_sizeof_raw_octet_string(SOSManifestGetSize(manifest))));
 218 }
 219
 220 static uint8_t *der_encode_manifest_message(SOSManifestRef manifest, const uint8_t *der, uint8_t *der_end) {
 221     return ccder_encode_constructed_tl(CCDER_CONSTRUCTED_SEQUENCE, der_end, der,
 222            ccder_encode_uint64(SOSManifestMessageType, der,
 223            ccder_encode_raw_octet_string(SOSManifestGetSize(manifest),
 224                                          SOSManifestGetBytePtr(manifest), der, der_end)));
 225 }
 226
 227 /* This message is sent in response to a manifestDigest if our manifestDigest
 228  differs from that of the received manifestDigest, or in response to a
 229  manifestAndObjects message if the manifestDigest in the received message
 230  doesn't match our own manifestDigest. */
 231 CFDataRef SOSEngineCreateManifestMessage(SOSEngineRef engine, SOSPeerRef peer, CFErrorRef *error) {
 232     SOSManifestRef manifest = SOSDataSourceCopyManifest(engine->dataSource, error);
 233     if (!manifest)
 234         return NULL;
 235
 236     size_t der_size = der_sizeof_manifest_message(manifest);
 237     CFMutableDataRef message = CFDataCreateMutable(NULL, der_size);
 238     CFDataSetLength(message, der_size);
 239     uint8_t *der_end = CFDataGetMutableBytePtr(message);
 240     const uint8_t *der = der_end;
 241     der_end += der_size;
 242
 243     der_end = der_encode_manifest_message(manifest, der, der_end);
 244     assert(der == der_end);
 245
 246     return message;
 247 }
 248
 249
 250 /* ManifestDeltaAndObjects message */
 251 static size_t der_sizeof_manifest_and_objects_message(SOSManifestRef removals, SOSManifestRef additions, CFArrayRef objects, CFErrorRef *error) {
 252     size_t objects_size = der_sizeof_plist(objects, error);
 253     if (objects_size == 0)
 254         return objects_size;
 255
 256     return ccder_sizeof(CCDER_CONSTRUCTED_SEQUENCE,
 257                         (ccder_sizeof_uint64(SOSManifestDeltaAndObjectsMessageType) +
 258                          ccder_sizeof(CCDER_CONSTRUCTED_SEQUENCE,
 259                          (ccder_sizeof_raw_octet_string(SOSDigestSize) +
 260                           ccder_sizeof_raw_octet_string(SOSManifestGetSize(removals)) +
 261                           ccder_sizeof_raw_octet_string(SOSManifestGetSize(additions)) +
 262                           objects_size))));
 263 }
 264
 265 static uint8_t *der_encode_manifest_and_objects_message(CFDataRef digest, SOSManifestRef removals, SOSManifestRef additions, CFArrayRef objects, CFErrorRef *error, const uint8_t *der, uint8_t *der_end) {
 266     assert(CFDataGetLength(digest) == SOSDigestSize);
 267     return ccder_encode_constructed_tl(CCDER_CONSTRUCTED_SEQUENCE, der_end, der,
 268            ccder_encode_uint64(SOSManifestDeltaAndObjectsMessageType, der,
 269            ccder_encode_constructed_tl(CCDER_CONSTRUCTED_SEQUENCE, der_end, der,
 270            ccder_encode_raw_octet_string(SOSDigestSize, CFDataGetBytePtr(digest), der,
 271            ccder_encode_raw_octet_string(SOSManifestGetSize(removals), SOSManifestGetBytePtr(removals), der,
 272            ccder_encode_raw_octet_string(SOSManifestGetSize(additions), SOSManifestGetBytePtr(additions), der,
 273            der_encode_plist(objects, error, der, der_end)))))));
 274 }
 275
 276 /* This message is sent in response to a local change that needs to be
 277  propagated to our peers or in response to a manifest or manifestDigest
 278  message from a peer that is not in sync with us yet. */
 279 CFDataRef SOSEngineCreateManifestAndObjectsMessage(SOSEngineRef engine, SOSPeerRef peer, CFErrorRef *error) {
 280     /* Assumptions:
 281        peer has a manifest that corresponds to peers real manifest.
 282        we send everything in our datasource that's not in peers manifest already to peer.
 283      */
 284     CFMutableDataRef message = NULL;
 285     SOSManifestRef manifest, peerManifest, additions, removals;
 286
 287 retry:
 288     manifest = SOSDataSourceCopyManifest(engine->dataSource, error);
 289     if (!manifest)
 290         goto errOut4;
 291
 292     peerManifest = SOSPeerCopyManifest(peer, error);
 293     if (!peerManifest)
 294         goto errOut3;
 295
 296     if (!SOSManifestDiff(manifest, peerManifest, &additions, &removals, error))
 297         goto errOut2;
 298
 299     CFErrorRef localError = NULL;
 300     CFArrayRef objects = SOSDataSourceCopyObjectArray(engine->dataSource, additions, &localError);
 301     if (!objects) {
 302         if(SecErrorGetOSStatus(localError)==errSecDecode) {
 303             secnotice("engine", "Corrupted item found: %@", localError);
 304             CFReleaseNull(manifest);
 305             CFReleaseNull(additions);
 306             CFReleaseNull(removals);
 307             CFReleaseNull(peerManifest);
 308             CFReleaseNull(localError);
 309             goto retry;
 310         }
 311         if(error && *error==NULL)
 312             *error=localError;
 313         else
 314             CFReleaseNull(localError);
 315         goto errOut1;
 316     }
 317
 318     size_t der_size = der_sizeof_manifest_and_objects_message(removals, additions, objects, error);
 319     if (der_size == 0)
 320         goto errOut0;
 321
 322     /* TODO: avoid copying the digest here by inlining der_encode_manifest_and_objects_message(). */
 323     CFDataRef peerDigest = SOSPeerCopyManifestDigest(peer, error);
 324     if (!peerDigest)
 325         goto errOut0;
 326
 327     message = CFDataCreateMutable(NULL, der_size);
 328     CFDataSetLength(message, der_size);
 329     uint8_t *der_end = CFDataGetMutableBytePtr(message);
 330     const uint8_t *der = der_end;
 331     der_end += der_size;
 332
 333     der_end = der_encode_manifest_and_objects_message(peerDigest, removals, additions, objects, error, der, der_end);
 334     assert(der == der_end);
 335     if (der_end == NULL) {
 336         CFReleaseNull(message);
 337         goto errOut_;
 338     }
 339
 340     /* Record the peers new manifest assuming that peer will accept all the
 341        changes we are about to send them. */
 342     SOSPeerSetManifest(peer, manifest, error);
 343
 344 errOut_:
 345     CFRelease(peerDigest);
 346 errOut0:
 347     CFRelease(objects);
 348 errOut1:
 349     SOSManifestDispose(removals);
 350     SOSManifestDispose(additions);
 351 errOut2:
 352     SOSManifestDispose(peerManifest);
 353 errOut3:
 354     SOSManifestDispose(manifest);
 355 errOut4:
 356
 357     return message;
 358 }
 359
 360 static const uint8_t *der_decode_msg_type(enum SOSMessageType *msg_type,
 361                                           const uint8_t *der,
 362                                           const uint8_t *der_end,
 363                                           CFErrorRef *error) {
 364     const uint8_t *body_end;
 365     der = ccder_decode_sequence_tl(&body_end, der, der_end);
 366     if (!der)
 367         return NULL;
 368
 369     if (body_end != der_end) {
 370         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Trailing garbage at end of message"), NULL, error);
 371         return NULL;
 372     }
 373
 374     uint64_t msgType;
 375     der = ccder_decode_uint64(&msgType, der, der_end);
 376     if (msgType < 1 || msgType > SOSManifestDeltaAndObjectsMessageType) {
 377         SecCFCreateErrorWithFormat(kSOSEngineInvalidMessageError, sErrorDomain,
 378                                    NULL, error, NULL,
 379                                    CFSTR("Bad message type: %llu"), msgType);
 380         return NULL;
 381     }
 382     *msg_type = (enum SOSMessageType)msgType;
 383     return der;
 384 }
 385
 386 static const uint8_t *
 387 der_decode_manifest_digest(CFDataRef *digest, CFErrorRef *error,
 388                            const uint8_t *der, const uint8_t *der_end) {
 389     require_quiet(der, errOut);
 390     size_t len;
 391     der = ccder_decode_tl(CCDER_OCTET_STRING, &len, der, der_end);
 392     require_action_quiet(der, errOut, SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Failed to find string"), NULL, error));
 393     require_action_quiet(len == SOSDigestSize, errOut, SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Invalid digest size"), NULL, error));
 394
 395     *digest = CFDataCreate(0, der, len);
 396     require_action_quiet(*digest, errOut, SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Failed to create digest"), NULL, error));
 397
 398     der += len;
 399     require_action_quiet(der, errOut, CFReleaseNull(*digest); SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Failed to find string"), NULL, error));
 400
 401     return der;
 402
 403 errOut:
 404     return NULL;
 405 }
 406
 407 static const uint8_t *
 408 der_decode_manifest(SOSManifestRef *manifest, CFErrorRef *error,
 409                     const uint8_t *der, const uint8_t *der_end) {
 410     if (!der)
 411         goto errOut;
 412     size_t len;
 413     der = ccder_decode_tl(CCDER_OCTET_STRING, &len, der, der_end);
 414     if (!der) {
 415         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Failed to decode manifest"), NULL, error);
 416         goto errOut;
 417     }
 418     if (len % SOSDigestSize != 0) {
 419         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("manifest not a multiple of digest size"), NULL, error);
 420         goto errOut;
 421     }
 422     *manifest = SOSManifestCreateWithBytes(der, len, error);
 423     if (!*manifest)
 424         goto errOut;
 425
 426     return der += len;
 427
 428 errOut:
 429     return NULL;
 430 }
 431
 432 static const uint8_t *
 433 der_decode_manifest_digest_message(CFDataRef *digest, CFErrorRef *error,
 434                                    const uint8_t *der, const uint8_t *der_end) {
 435     der = der_decode_manifest_digest(digest, error, der, der_end);
 436     if (der && der != der_end) {
 437         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Trailing garbage after digest"), NULL, error);
 438         CFReleaseNull(*digest);
 439         der = NULL;
 440     }
 441     return der;
 442 }
 443
 444 static const uint8_t *
 445 der_decode_manifest_message(SOSManifestRef *manifest, CFErrorRef *error,
 446                             const uint8_t *der, const uint8_t *der_end) {
 447     der = der_decode_manifest(manifest, error, der, der_end);
 448     if (der && der != der_end) {
 449         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Trailing garbage after manifest"), NULL, error);
 450         SOSManifestDispose(*manifest);
 451         *manifest = NULL;
 452         der = NULL;
 453     }
 454     return der;
 455 }
 456
 457 static const uint8_t *
 458 der_decode_manifest_and_objects_message(CFDataRef *peerManifestDigest,
 459                                         SOSManifestRef *removals,
 460                                         SOSManifestRef *additions,
 461                                         CFArrayRef *objects,
 462                                         CFErrorRef *error, const uint8_t *der,
 463                                         const uint8_t *der_end) {
 464     const uint8_t *body_end;
 465     der = ccder_decode_sequence_tl(&body_end, der, der_end);
 466     if (!der) {
 467         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Failed to decode top level sequence"), NULL, error);
 468         goto errOut;
 469     }
 470
 471     if (body_end != der_end) {
 472         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Trailing garbage at end of message"), NULL, error);
 473         goto errOut;
 474     }
 475
 476     der = der_decode_manifest_digest(peerManifestDigest, error, der, der_end);
 477     if (!der)
 478         goto errOut;
 479     der = der_decode_manifest(removals, error, der, der_end);
 480     if (!der)
 481         goto errOut1;
 482     der = der_decode_manifest(additions, error, der, der_end);
 483     if (!der)
 484         goto errOut2;
 485
 486     CFPropertyListRef pl;
 487     der = der_decode_plist(0, 0, &pl, error, der, der_end);
 488     if (!der)
 489         goto errOut3;
 490
 491     if (der != der_end) {
 492         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("Trailing garbage at end of message body"), NULL, error);
 493         goto errOut4;
 494     }
 495
 496     // TODO Check that objects is in fact an array. */
 497     if (CFArrayGetTypeID() != CFGetTypeID(pl)) {
 498         SOSEngineCreateError(kSOSEngineInvalidMessageError, CFSTR("objects is not an array"), NULL, error);
 499         goto errOut4;
 500     }
 501     *objects = pl;
 502
 503     return der;
 504
 505 errOut4:
 506     CFRelease(pl);
 507 errOut3:
 508     CFRelease(additions);
 509 errOut2:
 510     CFRelease(removals);
 511 errOut1:
 512     CFRelease(peerManifestDigest);
 513 errOut:
 514     return NULL;
 515 }
 516
 517
 518 #if 0
 519 enum SOSMessageType SOSMessageGetType(CFDataRef message) {
 520     const uint8_t *der = CFDataGetBytePtr(message);
 521     const uint8_t *der_end = der + CFDataGetLength(message);
 522     enum SOSMessageType msg_type;
 523     der_decode_msg_type(&msg_type, der, der_end, NULL);
 524     if (!der) {
 525         return SOSManifestInvalidMessageType;
 526     }
 527
 528     return msg_type;
 529 }
 530 #endif
 531
 532 /* H(): SHA1 hash function.
 533  M: Manifest of peer p
 534  MSG: H(M) */
 535 static CFDataRef SOSEngineCopyManifestDigestReply(SOSEngineRef engine,
 536                                                   SOSPeerRef peer,
 537                                                   CFDataRef digest,
 538                                                   CFErrorRef *error) {
 539     CFDataRef reply = NULL;
 540     CFDataRef peerDigest = SOSPeerCopyManifestDigest(peer, NULL);
 541     CFDataRef manifestDigest = SOSDataSourceCopyManifestDigest(engine->dataSource, error);
 542     if (manifestDigest) {
 543         if (CFEqual(manifestDigest, digest)) {
 544             /* Our dataSources manifest and that of the peer are equal, we are in sync. */
 545             if (peerDigest && CFEqual(peerDigest, digest)) {
 546                 /* The last known digest we had for peer already matched the digest peer
 547                    sent us, so this message is redundant, consider it an ack of our last
 548                    message to peer. */
 549                 reply = CFDataCreate(kCFAllocatorDefault, NULL, 0);
 550             } else {
 551                 /* Our peer just sent us a manifest digest that matches our own, but the digest
 552                    we have for the peer (if any) doesn't match that.   Peer must have the same
 553                    manifest we do, so record that. */
 554                 SOSManifestRef manifest = SOSDataSourceCopyManifest(engine->dataSource, error);
 555                 if (manifest) {
 556                     bool ok = SOSPeerSetManifest(peer, manifest, error);
 557                     SOSManifestDispose(manifest);
 558                     if (ok) {
 559                         /* Since we got lucky and happen to have the same digest as our peer, we
 560                          send back an ack to ensure our peer ends up knowning our manifest as well. */
 561                         reply = SOSEngineCreateManifestDigestMessage(engine, peer, error);
 562                     }
 563                 }
 564             }
 565         } else if (peerDigest && CFEqual(peerDigest, digest)) {
 566             /* We know peer's current manifest is correct (the computed digest
 567                matches the passed in one) but peer and our dataSource
 568                are not in sync.  Send the deltas to peer. */
 569             reply = SOSEngineCreateManifestAndObjectsMessage(engine, peer, error);
 570         } else {
 571             /* Our peer has no digest yet, or the manifestDigest peer just sent
 572                us doesn't match the digest of the manifest we think peer has.
 573                We need to get peer to tell us their manifest, to do so we sent
 574                it ours and hope it responds with deltas. */
 575             reply = SOSEngineCreateManifestMessage(engine, peer, error);
 576         }
 577         CFRelease(manifestDigest);
 578     }
 579     CFReleaseSafe(peerDigest);
 580     return reply;
 581 }
 582
 583 /* M: Manifest of peer p
 584  MSG: M */
 585 static CFDataRef SOSEngineCopyManifestReply(SOSEngineRef engine, SOSPeerRef peer,
 586                                             SOSManifestRef manifest,
 587                                             CFErrorRef *error) {
 588     CFDataRef reply = NULL;
 589     // Peer just told us what his manifest was.  Let's roll with it.
 590     SOSPeerSetManifest(peer, manifest, error);
 591     CFDataRef peerManifestDigest = SOSPeerCopyManifestDigest(peer, error);
 592     if (peerManifestDigest) {
 593         CFDataRef manifestDigest = SOSDataSourceCopyManifestDigest(engine->dataSource, error);
 594         if (manifestDigest) {
 595             if (CFEqual(peerManifestDigest, manifestDigest)) {
 596                 /* We're in sync, optionally send peer an ack. */
 597                 reply = SOSEngineCreateManifestDigestMessage(engine, peer, error);
 598             } else {
 599                 /* Send peer the objects it is missing from our manifest. */
 600                 reply = SOSEngineCreateManifestAndObjectsMessage(engine, peer, error);
 601             }
 602             CFRelease(manifestDigest);
 603         }
 604         CFRelease(peerManifestDigest);
 605     }
 606     return reply;
 607 }
 608
 609 static bool SOSEngineProccesObjects(SOSEngineRef engine,
 610                                     SOSPeerRef peer,
 611                                     CFDataRef digest,
 612                                     SOSManifestRef removals,
 613                                     SOSManifestRef additions,
 614                                     CFArrayRef objects,
 615                                     CFErrorRef *error) {
 616     __block bool result = true;
 617     CFArrayForEach(objects, ^(const void *value) {
 618         SOSObjectRef ob = SOSObjectCreateWithPropertyList(engine->dataSource, value, error);
 619         if (ob) {
 620             SOSMergeResult mr = engine->dataSource->add(engine->dataSource, ob, error);
 621             if (!mr) {
 622                 result = false;
 623                 // assertion failure, duplicate object added during transaction, that wasn't explicitly listed in removal list.
 624                 // treat as conflict?
 625                 // oa =  ds->lookup(pkb);
 626                 // ds->choose_between(oa, ob)
 627                 // TODO: This is needed is we want to allow conflicts with other circles.
 628                 SetCloudKeychainTraceValueForKey(kCloudKeychainNumberOfTimesSyncFailed, 1);
 629                 secerror("assertion failure, add failed: %@",
 630                          error ? *error : (CFErrorRef)CFSTR("error is null"));
 631             }
 632             CFRelease(ob);
 633         }
 634     });
 635     return result;
 636 }
 637
 638 /* H(): SHA1 hash function.
 639  L: Manifest of local peer.
 640  M: Manifest of peer p.
 641  M-L: Manifest of entries in M but not in L
 642  L-M: Manifest of entries in L but not in M
 643  O(M): Objects in manifest M
 644  MSG: H(L) || L-M || M-L || O(M-L)  */
 645 static CFDataRef SOSEngineCopyManifestAndObjectsReply(SOSEngineRef engine,
 646                                                       SOSPeerRef peer,
 647                                                       CFDataRef digest,
 648                                                       SOSManifestRef removals,
 649                                                       SOSManifestRef additions,
 650                                                       CFArrayRef objects,
 651                                                       CFErrorRef *error) {
 652     CFDataRef reply = NULL;
 653     CFMutableDataRef manifestDigest = (CFMutableDataRef)SOSDataSourceCopyManifestDigest(engine->dataSource, error);
 654     if (manifestDigest) {
 655         SOSManifestRef manifest = SOSDataSourceCopyManifest(engine->dataSource, error);
 656
 657         /* Always proccess the objects after we snapshot our manifest. */
 658         if (!SOSEngineProccesObjects(engine, peer, digest, removals, additions, objects, error)) {
 659             secerror("peer: %@ SOSEngineProccesObjects(): %@", SOSPeerGetID(peer), *error);
 660         }
 661
 662         if (CFEqual(manifestDigest, digest)) {
 663             SOSManifestRef peerManifest = NULL;
 664             if (manifest) {
 665                 peerManifest = SOSManifestCreateWithPatch(manifest, removals, additions, error);
 666             }
 667             if (peerManifest) {
 668                 if (SOSPeerSetManifest(peer, peerManifest, error)) {
 669                     /* Now proccess the objects. */
 670                     if (!SOSEngineProccesObjects(engine, peer, digest, removals, additions, objects, error)) {
 671                         secerror("peer: %@ SOSEngineProccesObjects(): %@", SOSPeerGetID(peer), *error);
 672                     }
 673
 674                     CFDataRef peerDigest = SOSPeerCopyManifestDigest(peer, error);
 675                     if (peerDigest) {
 676                         /* Depending on whether after proccess objects we still have objects that need to be sent back to peer we respond with our digestManifest or with a manifestAndObjectsMessage. */
 677                         if (engine->dataSource->get_manifest_digest(engine->dataSource, CFDataGetMutableBytePtr(manifestDigest), error)) {
 678                             if (CFEqual(manifestDigest, peerDigest)) {
 679                                 reply = SOSEngineCreateManifestDigestMessage(engine, peer, error);
 680                             } else {
 681                                 reply = SOSEngineCreateManifestAndObjectsMessage(engine, peer, error);
 682                             }
 683                         }
 684                         CFRelease(peerDigest);
 685                     }
 686                 }
 687                 CFRelease(peerManifest);
 688             } else {
 689                 secerror("Received peer: %@ sent bad message: %@", SOSPeerGetID(peer), *error);
 690                 /* We failed to compute peer's digest, let's tell him ours again and hope for a retransmission. */
 691                 /* TODO: Perhaps this should be sent by the top level whenever an error occurs during parsing. */
 692                 reply = SOSEngineCreateManifestDigestMessage(engine, peer, error);
 693             }
 694         } else {
 695             /* ds->manifestDigest != msg->manigestDigest => We received deltas
 696                against a manifest we don't have respond with our current
 697                manifest to get back in sync. */
 698             reply = SOSEngineCreateManifestMessage(engine, peer, error);
 699         }
 700         CFReleaseSafe(manifest);
 701         CFRelease(manifestDigest);
 702     }
 703     return reply;
 704 }
 705
 706 /* Handle incoming message from peer p.  Return false if there was an error, true otherwise. */
 707 bool SOSEngineHandleMessage(SOSEngineRef engine, SOSPeerRef peer,
 708                             CFDataRef message, CFErrorRef *error) {
 709     CFDataRef reply = NULL;
 710     SOSManifestRef oldPeerManifest = SOSPeerCopyManifest(peer, NULL);
 711     const uint8_t *der = CFDataGetBytePtr(message);
 712     const uint8_t *der_end = der + CFDataGetLength(message);
 713     enum SOSMessageType msgType;
 714
 715     der = der_decode_msg_type(&msgType, der, der_end, error);
 716     if (der) switch (msgType) {
 717         case SOSManifestDigestMessageType:
 718         {
 719             CFDataRef digest = NULL; // Make the static analyzer happy by NULL and Release safe
 720             der = der_decode_manifest_digest_message(&digest, error, der, der_end);
 721             if (der) {
 722                 reply = SOSEngineCopyManifestDigestReply(engine, peer, digest, error);
 723             }
 724             CFReleaseSafe(digest);
 725             break;
 726         }
 727         case SOSManifestMessageType:
 728         {
 729             SOSManifestRef manifest;
 730             der = der_decode_manifest_message(&manifest, error, der, der_end);
 731             if (der) {
 732                 reply = SOSEngineCopyManifestReply(engine, peer, manifest, error);
 733                 SOSManifestDispose(manifest);
 734             }
 735             break;
 736         }
 737         case SOSManifestDeltaAndObjectsMessageType:
 738         {
 739             CFDataRef peerManifestDigest;
 740             SOSManifestRef removals;
 741             SOSManifestRef additions;
 742             CFArrayRef objects;
 743             der = der_decode_manifest_and_objects_message(&peerManifestDigest, &removals, &additions, &objects, error, der, der_end);
 744             if (der) {
 745                 reply = SOSEngineCopyManifestAndObjectsReply(engine, peer, peerManifestDigest, removals, additions, objects, error);
 746                 CFRelease(peerManifestDigest);
 747                 SOSManifestDispose(removals);
 748                 SOSManifestDispose(additions);
 749                 CFRelease(objects);
 750             }
 751             break;
 752         }
 753         default:
 754             SecCFCreateErrorWithFormat(kSOSEngineInvalidMessageError, sErrorDomain,
 755                                        NULL, error, NULL, CFSTR("Invalid message type %d"), msgType);
 756             break;
 757     }
 758
 759     bool ok = reply;
 760     if (reply && CFDataGetLength(reply)) {
 761         ok = SOSPeerSendMessage(peer, reply, error);
 762         if (!ok)
 763             SOSPeerSetManifest(peer, oldPeerManifest, NULL);
 764     }
 765     secnotice("engine", "%@", SOSPeerGetID(peer));
 766     CFReleaseSafe(oldPeerManifest);
 767     CFReleaseSafe(reply);
 768     return ok;
 769 }
 770
 771 bool SOSEngineSyncWithPeer(SOSEngineRef engine, SOSPeerRef peer, bool force,
 772                            CFErrorRef *error) {
 773     CFDataRef reply = NULL;
 774     SOSManifestRef oldPeerManifest = SOSPeerCopyManifest(peer, NULL);
 775     bool ok = true;
 776     require_quiet(SOSPeerCanSendMessage(peer), exit);
 777     CFDataRef peerDigest = SOSPeerCopyManifestDigest(peer, NULL);
 778     CFMutableDataRef manifestDigest = CFDataCreateMutable(0, SOSDigestSize);
 779     CFDataSetLength(manifestDigest, SOSDigestSize);
 780     if (engine->dataSource->get_manifest_digest(engine->dataSource, CFDataGetMutableBytePtr(manifestDigest), error)) {
 781         if (peerDigest) {
 782             if (CFEqual(peerDigest, manifestDigest)) {
 783                 /* We are in sync with peer already. */
 784                 if (force) {
 785                     /* If we are at the end of the OTR handshake, we have to send
 786                        something to our peer no matter what to break the symmmetry.  */
 787                     reply = SOSEngineCreateManifestDigestMessage(engine, peer, error);
 788                 } else {
 789                     reply = CFDataCreate(kCFAllocatorDefault, NULL, 0);
 790                 }
 791             } else {
 792                 /* We have have a digest for peer's manifest and it doesn't
 793                    match our current digest, so send deltas to peer. */
 794                 reply = SOSEngineCreateManifestAndObjectsMessage(engine, peer, error);
 795             }
 796         } else {
 797             /* We have no digest for peer yet, send our manifest digest to peer,
 798                it should respond with it's manifest so we can sync. */
 799             reply = SOSEngineCreateManifestDigestMessage(engine, peer, error);
 800         }
 801     }
 802     CFRelease(manifestDigest);
 803     CFReleaseSafe(peerDigest);
 804
 805     ok = ok && reply;
 806     if (ok && CFDataGetLength(reply)) {
 807         ok = SOSPeerSendMessage(peer, reply, error);
 808         if (!ok)
 809             SOSPeerSetManifest(peer, oldPeerManifest, NULL);
 810     }
 811
 812 exit:
 813     secnotice("engine", "%@", SOSPeerGetID(peer));
 814     CFReleaseSafe(oldPeerManifest);
 815     CFReleaseSafe(reply);
 816     return ok;
 817 }
 818
 819 #if 0
 820 static void appendObject(CFMutableStringRef desc, CFDictionaryRef object) {
 821     __block bool needComma = false;
 822     CFDictionaryForEach(object, ^(const void *key, const void *value) {
 823         if (needComma)
 824             CFStringAppend(desc, CFSTR(","));
 825         else
 826             needComma = true;
 827
 828         CFStringAppend(desc, key);
 829         CFStringAppend(desc, CFSTR("="));
 830         if (CFEqual(CFSTR("data"), key)) {
 831             CFStringAppend(desc, CFSTR("<?>"));
 832         } else if (isData(value)) {
 833             CFStringAppendHexData(desc, value);
 834         } else {
 835             CFStringAppendFormat(desc, 0, CFSTR("%@"), value);
 836         }
 837     });
 838 }
 839 #endif
 840
 841 static void appendObjects(CFMutableStringRef desc, CFArrayRef objects) {
 842     __block bool needComma = false;
 843     CFArrayForEach(objects, ^(const void *value) {
 844         if (needComma)
 845             CFStringAppend(desc, CFSTR(","));
 846         else
 847             needComma = true;
 848
 849         SecItemServerAppendItemDescription(desc, value);
 850     });
 851 }
 852
 853 CFStringRef SOSMessageCopyDescription(CFDataRef message) {
 854     if (!message)
 855         return CFSTR("<NULL>");
 856
 857     CFMutableStringRef desc = CFStringCreateMutable(0, 0);
 858     const uint8_t *der = CFDataGetBytePtr(message);
 859     const uint8_t *der_end = der + CFDataGetLength(message);
 860     enum SOSMessageType msgType;
 861
 862     CFStringAppend(desc, CFSTR("<Msg"));
 863     der = der_decode_msg_type(&msgType, der, der_end, 0);
 864     if (der) switch (msgType) {
 865         case SOSManifestDigestMessageType:
 866         {
 867             CFStringAppend(desc, CFSTR("ManifestDigest digest: "));
 868             CFDataRef digest = NULL;
 869             der = der_decode_manifest_digest_message(&digest, 0, der, der_end);
 870             if (der) {
 871                 CFStringAppendHexData(desc, digest);
 872             }
 873             CFReleaseNull(digest);
 874
 875             break;
 876         }
 877         case SOSManifestMessageType:
 878         {
 879             CFStringAppend(desc, CFSTR("Manifest"));
 880
 881             SOSManifestRef manifest;
 882             der = der_decode_manifest_message(&manifest, 0, der, der_end);
 883             if (der) {
 884                 CFStringRef mfdesc = SOSManifestCopyDescription(manifest);
 885                 if (mfdesc) {
 886                     CFStringAppendFormat(desc, 0, CFSTR(" manifest: %@"), mfdesc);
 887                     CFRelease(mfdesc);
 888                 }
 889                 SOSManifestDispose(manifest);
 890             }
 891             break;
 892         }
 893         case SOSManifestDeltaAndObjectsMessageType:
 894         {
 895             CFStringAppend(desc, CFSTR("ManifestDeltaAndObjects digest:"));
 896
 897             CFDataRef peerManifestDigest;
 898             SOSManifestRef removals;
 899             SOSManifestRef additions;
 900             CFArrayRef objects;
 901             der = der_decode_manifest_and_objects_message(&peerManifestDigest, &removals, &additions, &objects, 0, der, der_end);
 902             if (der) {
 903                 CFStringAppendHexData(desc, peerManifestDigest);
 904                 CFStringRef remdesc = SOSManifestCopyDescription(removals);
 905                 if (remdesc) {
 906                     CFStringAppendFormat(desc, 0, CFSTR(" removals: %@"), remdesc);
 907                     CFRelease(remdesc);
 908                 }
 909                 CFStringRef adddesc = SOSManifestCopyDescription(additions);
 910                 if (adddesc) {
 911                     CFStringAppendFormat(desc, 0, CFSTR(" additions: %@"), adddesc);
 912                     CFRelease(adddesc);
 913                 }
 914                 CFStringAppendFormat(desc, 0, CFSTR(" objects: "));
 915                 appendObjects(desc, objects);
 916
 917                 CFRelease(peerManifestDigest);
 918                 SOSManifestDispose(removals);
 919                 SOSManifestDispose(additions);
 920                 CFRelease(objects);
 921             }
 922             break;
 923         }
 924         default:
 925             CFStringAppendFormat(desc, 0, CFSTR("InvalidType: %d"), msgType);
 926             break;
 927     }
 928
 929     CFStringAppend(desc, CFSTR(">"));
 930
 931     return desc;
 932 }