Verifiable redactable audit log

• US 10,027,473 B2
• Filed: 05/09/2016
• Issued: 07/17/2018
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Castellucci, Ryan, Martin, Philip
• Primary Examiner(s): Hirl, Joseph P
• Assistant Examiner(s): GYORFI, THOMAS A
• Application Number:
  US15/149,499
• Publication Number:
  US 20160254906A1
• Time in Patent Office: 799 Days
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2221/2151 Time stamp
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3265 using certificate chains, trees or paths; Hierarchical trust model
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

A verifiable, redactable log, which, in some embodiments, may contain multiple hash values per entry in order to sever confidentiality of a log from verifiability. Logs may be verified using recalculation of hashes and verification of trusted digital signatures. In some embodiments, the log may be divided into segments, each signed by a time server or self-signed using a system of ephemeral keys. In some embodiments, log messages regarding specific objects or events may be nested within the log to prevent reporting omission. The logging system may receive events or messages to enter into the log.

Claims

1. A computer-implemented method comprising:

accessing first log data;

determining first random or pseudo-random data;

determining first combined data based at least on the first log data and the first random or pseudo-random data;

calculating a first log entry hash based at least on the first combined data;

calculating a first log summary hash associated with the first log data, the first log summary hash based at least on the first log entry hash and a second hash, wherein the second hash is associated with log data that was previously signed with a first ephemeral key;

generating a first log entry, the first log entry comprising the first log entry hash and the first log summary hash;

calculating a second log entry hash based at least on second log data;

calculating a second log summary hash associated with the second log data, the second log summary hash based at least on the second log entry hash;

generating a second log entry based at least on the second log data;

generating a digital signature with a second ephemeral key verifying at least part of the first log entry and the second log entry; and

storing the first log entry and the second log entry.

2. The computer-implemented method of claim 1, wherein the first combined data further comprises a timestamp.

3. The computer-implemented method of claim 1, wherein calculating the first log summary hash based at least on the first log entry hash and the second hash comprises applying a cryptographic hash function to at least part of the first log entry hash and at least part of the second hash.

4. The computer-implemented method of claim 1, further comprising:

accessing the first log entry, the first log entry comprising the first log data;

generating a redacted log entry, wherein generating the redacted log entry comprises removing the first log data from the first log entry, the redacted log entry comprising the first log summary hash; and

transmitting the redacted log entry to a computing device.

5. The computer-implemented method of claim 1, wherein an association between the first ephemeral key and the second ephemeral key is recorded by at least:

generating the second ephemeral key;

signing a public-key portion of the first ephemeral key with the second ephemeral key;

storing the signed public-key portion of the first ephemeral key; and

removing a private-key portion of the first ephemeral key.

6. A non-transitory computer storage medium storing computer executable instructions that when executed by a computer hardware processor perform operations comprising:

accessing first log data;

determining first random or pseudo-random data;

determining first combined data based at least on the first log data and the first random or pseudo-random data;

calculating a first log entry hash based at least on the first combined data;

calculating a first log summary hash associated with the first log data, the first log summary hash based at least on the first log entry hash and a second hash, wherein the second hash is associated with log data that was previously signed with a first ephemeral key;

generating a first log entry, the first log entry comprising the first log entry hash and the first log summary hash;

calculating a second log entry hash based at least on second log data;

calculating a second log summary hash associated with the second log data, the second log summary hash based at least on the second log entry hash;

generating a second log entry based at least on the second log data;

generating a digital signature with a second ephemeral key verifying at least part of the first log entry and the second log entry; and

storing the first log entry and the second log entry.

7. The non-transitory computer storage medium of claim 6, wherein the first combined data further comprises a timestamp.

8. The non-transitory computer storage medium of claim 6, wherein the first log entry comprises a commitment log entry.

9. The non-transitory computer storage medium of claim 7, wherein the timestamp comprises a digital signature from an external timestamping server.

10. The non-transitory computer storage medium of claim 6, wherein calculating a first log summary hash associated with the first log data comprises applying a cryptographic hash function to the first log entry hash and the second hash.

11. The non-transitory computer storage medium of claim 6, wherein the operations further comprise:

accessing the first log entry, the first log entry comprising the first log data;

generating a redacted log entry, wherein generating the redacted log entry comprises removing the first log data from the first log entry, the redacted log entry comprising the first log summary hash; and

transmitting the redacted log entry to a computing device.

12. The non-transitory computer storage medium of claim 6, wherein the operations further comprise:

after a configurable amount of time, generating the second ephemeral key;

signing a public-key portion of the first ephemeral key with the second ephemeral key;

storing the signed public-key portion of the first ephemeral key; and

removing a private-key portion of the first ephemeral key.

13. A computer system comprising:

one or more hardware computer processors programmed, via executable code instructions, to;

access first log data;

determine first random or pseudo-random data;

determine first combined data based at least on the first log data and the first random or pseudo-random data;

calculate a first log entry hash based at least on the first combined data;

calculate a first log summary hash associated with the first log data, the first log summary hash based at least on the first log entry hash and a second hash, wherein the second hash is associated with log data that was previously signed with a first ephemeral key;

generate a first log entry, the first log entry comprise the first log entry hash and the first log summary hash;

calculate a second log entry hash based at least on second log data;

calculate a second log summary hash associated with the second log data, the second log summary hash based at least on the second log entry hash;

generate a second log entry based at least on the second log data;

generate a digital signature with a second ephemeral key verify at least part of the first log entry and the second log entry; and

store the first log entry and the second log entry.

14. The computer system of claim 13, wherein the one or more hardware processors are further programmed, via the executable instructions, to:

after a configurable amount of time, generate the second ephemeral key;

sign a public-key portion of the first ephemeral key with the second ephemeral key;

store the signed public-key portion of the first ephemeral key; and

remove at least a private-key portion of the first ephemeral key from the system.

15. The computer system of claim 14, wherein the first combined data further comprises a timestamp.

16. The computer system of claim 14, wherein the one or more hardware processors are further programmed, via the executable instructions, to:

receive, via a user interface, a search string;

query the first log entry and the second log entry based at least on the search string to identify the second log entry; and

in response to receiving the search string, verify the second log entry by recalculating the second log summary hash from previous log hashes.

17. The computer system of claim 14, wherein the one or more hardware processors are further programmed, via the executable instructions, to:

access the second log entry, the second log entry comprising the second log data;

generate a redacted log entry, wherein generating the redacted log entry comprises removing the second log data from the second log entry, the redacted log entry comprising the second log summary hash; and

transmit the redacted log entry to a computing device.

18. The computer system of claim 14, wherein the one or more hardware processors are further programmed, via the executable instructions, to:

generate a first segment, the first segment comprising the first log entry and the second log entry, wherein the first segment is independently verifiable from other segments; and

store the first segment.

19. The computer system of claim 14, wherein the one or more hardware processors are further programmed, via the executable instructions, to:

determine second random or pseudo-random data; and

determine second combined data based at least on the second log data and the second pseudo-random data, wherein calculating the second log entry hash is further based at least on the second combined data.

20. The computer system of claim 13, wherein the first log entry hash is further based on a timestamp.

21. The computer system of claim 20, wherein the timestamp comprises a digital signature from an external timestamping server.