I looked into AWS KMS, and also found your other questions. It became clear to me that your plan is to use envelope encryption, and that both previous versions of my answer were not relevant. On reflection, AWS KMS clearly also has this scenario in mind :
You also asked a question about when to re-key the data key - On what basis to create Data Keys. The accepted answer doesn't mention any limits associated with the symmetric cipher, which may or may not be relevant depending on how much data you plan on encrypting.
So, a revised idea:
- generate a new session data key at each service (re)start, and regenerate a new key at (or before):
- the life of the service, or
- up to the limits of the encryption cipher, or
- some arbitrary time frame that you decided upon
- the service would connect to KMS in the region, and store this next key using the CMK ^
- the service will encrypt data symmetrically before writing to the datastore, as you have already decided in your separate post
- when the limit approaches, the service will block on further submissions, re-key, and start processing submissions again
- (obv. if you only have one service, then progress will be blocked during this short period)
^ alternatively, it could encrypt the new session data key numerous times, with multiple public keys that it holds, eg, test, prod, recovery, ... and store all copies in KMS - apparently KMS can encrypt up to 4KB of data :
K_for_prod = sealed_box( StaticPK_prod, K_session_data )
KMS_payload = KMS_ENCRYPT( K_for_prod | K_for_test | K_for_recover | ... )
More on sealed box()
and another alternative: crypto_box()
Depending on the PII, you might wish to disallow edit and just have a superseding or versioning in your data model, with the new data having to be provided again, which would avoid this scenario. In one data model that I worked on, we basically made all PII non-mandatory, so when the user wishes to change something through the forms system, they simply provide the new data. (The submission form is not used to retrieve data - instead, the person must request the information through a totally different channel.) This may not suit you, however, in which case my proposal above would need some way, at time of edit, to recover the data key for that earlier session.
I also noticed you clarified your requirements around HMAC-SHA256
in another question - https://security.stackexchange.com/a/239550/228961 - which describes your desire to be able to search or filter on the encrypted data in the database without exposing it.