Let's say there is a shared storage: USB flash drive, external HDD, or whatever you like. I'll refer to it as disk. Also, there are multiple parties, let's say Alice and Bob (may be thousands of them) who periodically access that disk exclusively. So, for instance, one day Alice takes disk from the table, reads and writes to that disk and puts it back on the table. Next day Bob takes disk from the table, reads and writes to that disk and puts it back on the table. Than Bob again, than Alice again. Access sequence is random and unpredictable.

If we'll assume that Bob's PC is compromised and Eva sees everything written on Bob's PC, everything written on disk from Bob's PC, etc. It there any way for Alice to detect that disk was modified by Eva?

Here is Example. Let's say we store some number on the disk and all parties have assigned public and private keys and we write "Number", "Author" and "Number encrypted by private key" on the disk.

So, Bob writes

"3", "Bob", RSA("3", BobsPrivateKey)

Alice can decrypt 3rd value with Bob's public key and see if it equals to "3". But if Eva had stolen Bob's private key she can write

"5", "Bob", RSA("5", BobsPrivateKey)

So Alice validation will fail. I need some other validation, not so simple, to detect if disk was modified by Eva. I've thought about HMAC with operation sequence numbers and list of sequence numbers used, but I'm not sure.


Seems like the answer is that your goal is obviously impossible, without Bob's cooperation. How would Alice distinguish between (1) a write to the disk by Bob's PC, initiated at Bob's request, vs (2) a write to the disk by Bob's PC, initiated by the malware? She can't. They look identical from Alice's perspective.

For instance, having Bob's PC sign everything written to the disk won't work, because the malware can see Bob's private key and thus sign its malicious writes, too.

My suggestion is that you try to focus more on the specific real-world situation. Your abstraction of this into mathematics might leave out important details that might provide opportunities for risk mitigation, which aren't apparent from the abstract description but which can be identified based upon the concrete situation. However, don't get your hopes up too high. This kind of threat model -- where one person's PC has malware on it and can't be trusted -- typically tends to be very difficult to protect against, in practice.

|improve this answer|||||

Yes. $\:$ Since "Eva sees everything written on Bob's PC", the process needs to involve something
that's not written on Bob's PC. $\:$ They could use either some sort-of MAC that can be computed
with pencil-and paper, or a signature scheme whose private key is held on a hardware token.

I don't have any particular such MACs in mind, although my immediate idea would
be to lay the message out on a grid, interpret characters as modular integers,
and let the tag consist of sums of characters from certain small subsets of the grid.

Also, it is very rare for using "Number encrypted by private key"
and decrypting values with public keys to be secure.

Almost always, one should be using Number signed by private key
and verifying with the public key instead.

|improve this answer|||||
  • $\begingroup$ I'm soft of newbie, can you provide more details for the first part of your answer? $\endgroup$ – adontz Mar 31 '14 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.