--- a/services/sync/modules/service.js
+++ b/services/sync/modules/service.js
@@ -225,22 +225,23 @@ Sync11Service.prototype = {
         this._log.info("Suggesting retry.");
         return true;              // Try again.
       }
 
       // If not, reupload them and continue the current sync.
       cryptoKeys.ciphertext = cipherText;
       cryptoKeys.cleartext  = null;
 
-      let uploadResp = cryptoKeys.upload(this.resource(this.cryptoKeysURL));
-      if (uploadResp.success)
+      let uploadResp = this._uploadCryptoKeys(cryptoKeys, cryptoResp.obj.modified);
+      if (uploadResp.success) {
         this._log.info("Successfully re-uploaded keys. Continuing sync.");
-      else
+      } else {
         this._log.warn("Got error response re-uploading keys. " +
                        "Continuing sync; let's try again later.");
+      }
 
       return false;            // Don't try again: same keys.
 
     } catch (ex) {
       this._log.warn("Got exception \"" + ex + "\" fetching and handling " +
                      "crypto keys. Will try again later.");
       return false;
     }
@@ -671,18 +672,17 @@ Sync11Service.prototype = {
   },
 
   generateNewSymmetricKeys: function generateNewSymmetricKeys() {
     this._log.info("Generating new keys WBO...");
     let wbo = this.collectionKeys.generateNewKeysWBO();
     this._log.info("Encrypting new key bundle.");
     wbo.encrypt(this.identity.syncKeyBundle);
 
-    this._log.info("Uploading...");
-    let uploadRes = wbo.upload(this.resource(this.cryptoKeysURL));
+    let uploadRes = this._uploadCryptoKeys(wbo, 0);
     if (uploadRes.status != 200) {
       this._log.warn("Got status " + uploadRes.status + " uploading new keys. What to do? Throw!");
       this.errorHandler.checkServerError(uploadRes);
       throw new Error("Unable to upload symmetric keys.");
     }
     this._log.info("Got status " + uploadRes.status + " uploading keys.");
     let serverModified = uploadRes.obj;   // Modified timestamp according to server.
     this._log.debug("Server reports crypto modified: " + serverModified);
@@ -1137,16 +1137,29 @@ Sync11Service.prototype = {
       throw response;
     }
     // From https://docs.services.mozilla.com/storage/apis-1.5.html:
     // "Successful responses will return the new last-modified time for the collection."
     meta.modified = response.obj;
     this.recordManager.set(this.metaURL, meta);
   },
 
+  /**
+   * Upload crypto/keys
+   * @param {WBORecord} cryptoKeys crypto/keys record
+   * @param {Number} lastModified known last modified timestamp (in decimal seconds),
+   *                 will be used to set the X-If-Unmodified-Since header
+   */
+  _uploadCryptoKeys(cryptoKeys, lastModified) {
+    this._log.debug(`Uploading crypto/keys (lastModified: ${lastModified})`);
+    let res = this.resource(this.cryptoKeysURL);
+    res.setHeader("X-If-Unmodified-Since", lastModified);
+    return res.put(cryptoKeys);
+  },
+
   _freshStart: function _freshStart() {
     this._log.info("Fresh start. Resetting client.");
     this.resetClient();
     this.collectionKeys.clear();
 
     // Wipe the server.
     this.wipeServer();