[Cryptography] Data erasure by erasure of a salt

[Arnold Reinhold]

On Mon, 30 Apr 2018 12:55 Phillip Hallam-Baker wrote:
…
> But when we get to the message body, we might want to be able to
> effectively erase the body by erasing the salt value:
> 
> "For data erasure to be effective, the salt must be constructed so that the
> difficulty of recovering the key is sufficiently high that it is
> infeasible. For most purposes, a salt with 128 bits of appropriately random
> data will be sufficient."
> 
> 
> Now the neat thing here is that even if I am using AES-256, a salt of 128
> bits is almost certainly sufficient because it is a 'hard' workfactor. We
> are literally deleting that part of the key. 2^128 is an infeasible work
> factor, the only reason to go higher is because we worry about the
> algorithm not being as good as we think, not because someone could build a
> machine that could break a workfactor that size.
> 
> Or can they? Does Shorr's algorithm mean I need to go longer or does the
> same argument apply?


If I understand you correctly, you want to insure that anyone with all the details of how a data element was encrypted, except for the salt, will be unable to read the data element. So in effect your are creating a derived symmetric encryption algorithm with the salt as the key. The general take on symmetric encryption and quantum computers is that an encryption algorithm with work factor N on conventional computers would take sqrt(N) on an ideal quantum computer (Grover). See e.g. https://ws680.nist.gov/publication/get_pdf.cfm?pub_id=901595

NSA guidance suggests using 256-bit keys for quantum resistance. It may be that the totality of what you are doing will be harder to implement on a quantum computer than, say, AES, but given how speculative QC is, I can’t imagine anyone giving you reliable assurance that 128-bits is enough if you want long term security at the highest levels. Adding 16 bytes per file does not seem a high price to protect against an uncertain future.

Arnold Reinhold