2

We have a database table of encrypted log entries, each encrypted entry containing information about the user who created the entry. The entry is encrypted with the encryption key of the particular user.

Users may login into web GUI and enter their decryption key to fetch and decrypt their log entries from the server, without exposing other entries. The problem is there is no way to identify the user prior to decryption (this is a requirement). Also, the user or an attacker having an access to the server possessing the user's decryption key must not be able to decrypt other users log entries.

Second requirement is the performance. There are hundreds of thousands of rows, so decrypting all rows by trial and error doesn't sound viable.

Is there some existing scheme solving this chicken and egg dilemma?

Tuomas Toivonen
  • 371
  • 1
  • 2
  • 10
  • 1
    Can't each user have an encrypted list of log entry identifiers? When logged in, they can fetch this list of identifier and ask the server to give them the selected lines for decoding. The logs in the log table remains anonymous, while the user can enjoy performance by filtering the table using their id list. – M'vy Jun 29 '18 at 13:40

2 Answers2

0

No.

Encrypted correlations between entries require decryption, and are therefore slow. Yet, non-encrypted correlations are forbidden by requirements. It follows that you're forced to use a slow scheme.

Possibly acceptable workaround: split the logs

Use a different encrypted table for each user, with table name selected at random and stored as an encrypted profile property. In systems where encrypted tables are decrypted on-the-fly in memory for each user, this will achieve performance.

The only information leaked is the number of users, which is probably known anyway from the size of the user table, and the fact that some users may have more or less log entries than others. Observation of table sizes will allow to determine which unique identifier maps to which user, but no more.

Possibly acceptable workaround: obfuscate the correlation

Instead of a one-to-one relationship, you might consider employing a one-to-many relationship, where user N can generate any ID at random of the form NP+RAND(P-1). User N's records are all those with ID in the [ NP, (N+1)*P-1 ) range and can be retrieved with a BETWEEN clause. An attacker's inspection of the table will reveal a weak correlation between records, with on average TABLESIZE/P duplicates which will all map to the same user.

Community
  • 1
LSerni
  • 22,521
  • 4
  • 51
  • 60
  • This doesn't solve the problem, as the encrypted log entries aren't allowed to have any logical correlation identifier in plaintext shared between entries. Actually the fact the entry belongs to any user is a secret (there are entries which aren't correlated to any user at all). The problem is not about identifying the user (she is already authenticated anyway), but to identify the entries without a plaintext identifier. – Tuomas Toivonen Jun 29 '18 at 09:12
  • I had not understood what it was that you were trying to achieve. Changed answer – LSerni Jun 29 '18 at 10:47
  • Security by obscurity is out of question, and so is splitting the tables, as it alone would leak confidential information. The only solution we came up with is to store the user correlation identifier in plaintext, but for each legit record generate a fake record for all users. Naturally, this would expose number of users and multiply the amount of data, but decryption would always find the correct rows. – Tuomas Toivonen Jun 29 '18 at 14:09
0

You can have a log index: the encrypted username, and an encrypted blob with the ID of every log the user have. As you have way less users than log entries, you can use the private key to try to decrypt the username of every entry on the log index.

[ encrypted username | encrypted blob                     ]
| b5hdi..........xa3 | l2ms73..........................xx |
| iek03..........ao2 | 13doad..........................yy |

After recovering the record for that user, you can decrypt the blob, and get the ID of every entry on the log table, and return those entries to the user. To make things more difficult on the attacker, make the blob a fixed size (1MB, for example), even if the user does not have any logs.

So the decrypted blob would be something like this:

[12:662:667:1234:0000000....0000]

And if an user have lots of logs and the blob is filled with IDs, put a special field on the blob indicating that, and the system should find the continuation on the next blob.

Any attacker would only get a lot of encrypted blobs with no apparent association between them, and a table full of encrypted data. The system will be able to extract the ID of every log entry for the user, and no entry for other users.

ThoriumBR
  • 50,648
  • 13
  • 127
  • 142