diff --git a/services/identity/src/client_service.rs b/services/identity/src/client_service.rs
--- a/services/identity/src/client_service.rs
+++ b/services/identity/src/client_service.rs
@@ -14,10 +14,9 @@
     RegistrationFinishResponse, RegistrationStartRequest,
     RegistrationStartResponse, SenderKeysForUserRequest,
     SenderKeysForUserResponse, UpdateUserPasswordFinishRequest,
-    UpdateUserPasswordFinishResponse, UpdateUserPasswordStartRequest,
-    UpdateUserPasswordStartResponse, UploadOneTimeKeysRequest,
-    VerifyUserAccessTokenRequest, VerifyUserAccessTokenResponse,
-    WalletLoginRequest, WalletLoginResponse,
+    UpdateUserPasswordStartRequest, UpdateUserPasswordStartResponse,
+    UploadOneTimeKeysRequest, VerifyUserAccessTokenRequest,
+    VerifyUserAccessTokenResponse, WalletLoginRequest, WalletLoginResponse,
   },
   config::CONFIG,
   database::{DatabaseClient, Error as DBError, KeyPayload},
@@ -40,6 +39,7 @@
 pub enum WorkflowInProgress {
   Registration(UserRegistrationInfo),
   Login(UserLoginInfo),
+  Update(UpdateState),
 }
 
 #[derive(Clone)]
@@ -55,6 +55,11 @@
   pub opaque_server_login: comm_opaque2::server::Login,
 }
 
+#[derive(Clone)]
+pub struct UpdateState {
+  pub user_id: String,
+}
+
 #[derive(Clone)]
 pub struct FlattenedDeviceKeyUpload {
   pub device_id_key: String,
@@ -211,18 +216,77 @@
 
   async fn update_user_password_start(
     &self,
-    _request: tonic::Request<UpdateUserPasswordStartRequest>,
+    request: tonic::Request<UpdateUserPasswordStartRequest>,
   ) -> Result<tonic::Response<UpdateUserPasswordStartResponse>, tonic::Status>
   {
-    unimplemented!();
+    let message = request.into_inner();
+
+    let access_token = self
+      .client
+      .get_access_token_data(message.user_id.clone(), message.device_id_key)
+      .await
+      .map_err(handle_db_error)?;
+
+    if let Some(token) = access_token {
+      if !token.is_valid() || token.access_token != message.access_token {
+        return Err(tonic::Status::permission_denied("bad token"));
+      }
+
+      let server_registration = comm_opaque2::server::Registration::new();
+      let server_message = server_registration
+        .start(
+          &CONFIG.server_setup,
+          &message.opaque_registration_request,
+          message.user_id.as_bytes(),
+        )
+        .map_err(protocol_error_to_grpc_status)?;
+
+      let update_state = UpdateState {
+        user_id: message.user_id,
+      };
+      let session_id = generate_uuid();
+      self
+        .cache
+        .insert(session_id.clone(), WorkflowInProgress::Update(update_state))
+        .await;
+
+      let response = UpdateUserPasswordStartResponse {
+        session_id,
+        opaque_registration_response: server_message,
+      };
+      Ok(Response::new(response))
+    } else {
+      Err(tonic::Status::permission_denied("bad token"))
+    }
   }
 
   async fn update_user_password_finish(
     &self,
-    _request: tonic::Request<UpdateUserPasswordFinishRequest>,
-  ) -> Result<tonic::Response<UpdateUserPasswordFinishResponse>, tonic::Status>
-  {
-    unimplemented!();
+    request: tonic::Request<UpdateUserPasswordFinishRequest>,
+  ) -> Result<tonic::Response<Empty>, tonic::Status> {
+    let message = request.into_inner();
+
+    if let Some(WorkflowInProgress::Update(state)) =
+      self.cache.get(&message.session_id)
+    {
+      self.cache.invalidate(&message.session_id).await;
+
+      let server_registration = comm_opaque2::server::Registration::new();
+      let password_file = server_registration
+        .finish(&message.opaque_registration_upload)
+        .map_err(protocol_error_to_grpc_status)?;
+
+      self
+        .client
+        .update_user_password(state.user_id, password_file)
+        .await
+        .map_err(handle_db_error)?;
+
+      let response = Empty {};
+      Ok(Response::new(response))
+    } else {
+      Err(tonic::Status::not_found("session not found"))
+    }
   }
 
   async fn login_password_user_start(
@@ -466,7 +530,7 @@
       .map_err(handle_db_error)?;
 
     let response = WalletLoginResponse {
-      user_id: user_id,
+      user_id,
       access_token,
     };
     Ok(Response::new(response))
diff --git a/services/identity/src/database.rs b/services/identity/src/database.rs
--- a/services/identity/src/database.rs
+++ b/services/identity/src/database.rs
@@ -248,6 +248,32 @@
     Ok(())
   }
 
+  pub async fn update_user_password(
+    &self,
+    user_id: String,
+    password_file: Vec<u8>,
+  ) -> Result<(), Error> {
+    let update_expression =
+      format!("SET {} = :p", USERS_TABLE_REGISTRATION_ATTRIBUTE);
+    let expression_attribute_values = HashMap::from([(
+      ":p".to_string(),
+      AttributeValue::B(Blob::new(password_file)),
+    )]);
+
+    self
+      .client
+      .update_item()
+      .table_name(USERS_TABLE)
+      .key(USERS_TABLE_PARTITION_KEY, AttributeValue::S(user_id))
+      .update_expression(update_expression)
+      .set_expression_attribute_values(Some(expression_attribute_values))
+      .send()
+      .await
+      .map_err(|e| Error::AwsSdk(e.into()))?;
+
+    Ok(())
+  }
+
   pub async fn delete_user(
     &self,
     user_id: String,
diff --git a/shared/protos/identity_client.proto b/shared/protos/identity_client.proto
--- a/shared/protos/identity_client.proto
+++ b/shared/protos/identity_client.proto
@@ -19,7 +19,7 @@
   rpc UpdateUserPasswordStart(UpdateUserPasswordStartRequest) returns
     (UpdateUserPasswordStartResponse) {}
   rpc UpdateUserPasswordFinish(UpdateUserPasswordFinishRequest) returns
-    (UpdateUserPasswordFinishResponse) {}
+    (Empty) {}
   // Called by user to register device and get an access token
   rpc LoginPasswordUserStart(OpaqueLoginStartRequest) returns
     (OpaqueLoginStartResponse) {}
@@ -147,6 +147,10 @@
   bytes opaqueRegistrationRequest = 1;
   // Used to validate user, before attempting to update password
   string accessToken = 2;
+  string userID = 3;
+  // Public ed25519 key used for signing. We need this to look up a device's
+  // access token
+  string deviceIDKey = 4;
 }
 
 // Do a user registration, but overwrite the existing credentials
@@ -164,11 +168,6 @@
   bytes opaqueRegistrationResponse = 2;
 }
 
-message UpdateUserPasswordFinishResponse {
-  // After validating client reponse, mint a new token
-  string accessToken = 1;
-}
-
 // LoginUser
 
 message OpaqueLoginStartRequest {