US5978475A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Event auditing system
Assignee: BT Americas Inc
•
Filing: 1997-07-18
•
Granted: 1999-11-02
•
Expires: 2017-07-18
Abstract
Abstract In many computer applications, sensitive information must be kept on an untrusted machine. Such information must be protected against attackers, as well as against partially trusted entities to be given partial, but not total, access to the stored information. This invention provides a method, apparatus and computer-readable data structure for inhibiting an attacker from accessing or corrupting information stored by an untrusted machine. More specifically, in a log file generated during a process in which the untrusted machine is in limited communication with a trusted machine, entries generated prior to the attack remain secure (they cannot be modified without detection), even though subsequent entries can not be trusted. One embodiment of the invention also allows a partially trusted verifier to read and verify entries in the log file, but not to change them without detection. In another embodiment of the invention, operating with or without the trusted machine, the untrusted machine's log file can also incorporate log files of other processes.
Inventors
- 👤 Bruce Schneier
- 👤 John M. Kelsey
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 04:22
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/32; H04L9/3236; H04L9/3242; G; G06; G06F; G06F21/00; G06F21/60; G06F21/62; G06F21/6209; G06F21/64; H04L9/08; H04L9/0816; H04L9/0819; H04L9/0825; H04L9/0838; H04L9/0841; H04L9/321; H04L9/3297; H04L9/50; G06F2221/00; G06F2221/21; G06F2221/2101; G06F2221/2107; H04L2209/00; H04L2209/04; H04L2209/56
Claims Analysis
Total Claims: 78
Claim 1
Independent Claim
103 words
A method for creating an audit log entry having enhanced security against tampering, comprising the steps of: (a) receiving a quantity to be logged; (b) concatenating said quantity with at least a portion of a verification chain entry for a preceding entry; (c) using an entry-specific cryptographic key having been derived by computing a cryptographic hash on at least a cryptographic key for a preceding entry, performing a verifiable cryptographic operation on the result of step (b) to generate a current verification chain entry; and (d) writing, to a memory, an audit log entry including said quantity and said generated verification chain entry.
Claim 2
Independent Claim
103 words
A method for creating an audit log entry having enhanced security against tampering, comprising the steps of: (a) receiving a quantity to be logged; (b) concatenating said quantity with at least a portion of a verification chain entry for a preceding entry; (c) using an entry-specific cryptographic key having been derived by computing a cryptographic hash on at least a cryptographic key for a preceding entry, performing a verifiable cryptographic operation on the result of step (b) to generate a current verification chain entry; and (d) writing, to a memory, an audit log entry including said quantity and said generated verification chain entry.
Claim 3
Dependent Claim
32 words
The method of claim 1 further comprising the step of generating a cryptographic key usable for a subsequently generated audit log entry by computing a cryptographic hash on said entry-specific cryptographic key.
Claim 4
Dependent Claim
15 words
The method of claim 2 further comprising the step of deleting said entry-specific cryptographic key.
Claim 5
Dependent Claim
19 words
The method of claim 1 wherein said verifiable cryptographic operation is an encryption operation using said entry-specific cryptographic key.
Claim 6
Dependent Claim
26 words
The method of claim 4 wherein said verifiable cryptographic operation is a MAC operation using said entry-specific cryptographic key as an authentication key for said MAC.
Claim 7
Dependent Claim
11 words
The method of claim 1 where said quantity includes a datum.
Claim 8
Dependent Claim
12 words
The method of claim 6 where said datum is an encrypted value.
Claim 9
Dependent Claim
36 words
The method of claim 1 where: (a) said quantity includes a permission mask; and (b) said entry-specific cryptographic key depends on: (i) said permission mask, in addition to (ii) said cryptographic key for said preceding entry.
Claim 10
Dependent Claim
25 words
The method of claim 1 comprising the step, prior to said step of receiving said datum, of establishing mutually verified communications with a logging partner.
Claim 11
Dependent Claim
13 words
The method of claim 9 wherein said logging partner is a trusted computer.
Claim 12
Dependent Claim
13 words
The method of claim 9 wherein said logging partner is an untrusted computer.
Claim 13
Dependent Claim
24 words
The method of claim 11 further comprising the step of committing, to said untrusted computer, an information pertaining to a final audit log entry.
Claim 14
Dependent Claim
22 words
The method of claim 11 wherein said logging partner is part of a distributed logging scheme involving a plurality of untrusted computers.
Claim 15
Dependent Claim
22 words
The method of claim 13 wherein said distributed logging scheme includes maintaining parallel logfiles on at least some of said untrusted computers.
Claim 16
Dependent Claim
23 words
The method of claim 14 further comprising storing said quantity plus at least one pad value in at least some of said logfiles.
Claim 17
Dependent Claim
29 words
The method of claim 13 where said distributed logging scheme includes using a secret sharing scheme to store a logging parameter among at least some of said untrusted machines.
Claim 18
Dependent Claim
27 words
The method of claim 1 where said step of writing said audit log entry to said memory includes writing said audit log entry to a non-rewritable medium.
Claim 19
Dependent Claim
24 words
The method of claim 1 wherein step (b) further comprises including a value from a complementary audit log process in said verification chain entry.
Claim 20
Dependent Claim
19 words
The method of claim 1 further comprising the step of transmitting said audit log entry to a trusted computer.
Claim 21
Dependent Claim
20 words
The method of claim 8 further comprising the step of transmitting said audit log entry to a partially trusted verifier.
Claim 22
Dependent Claim
24 words
The method of claim 1 further comprising the use of an asymmetric cryptographic operation in at least one of steps (a), (b), and (c).
Claim 23
Dependent Claim
27 words
The method of claim 1 where said step of writing said audit log entry to said memory includes writing said audit log entry to an electronic wallet.
Claim 24
Dependent Claim
125 words
A computer-readable medium embodying a software program for creating an audit log entry having enhanced security against tampering, said software program comprising: (a) program code configured to receive a quantity to be logged; (b) program code configured to concatenate said quantity with at least a portion of a verification chain entry for a preceding entry; (c) program code configured to use an entry-specific cryptographic key that was derived by computing a cryptographic hash on at least a cryptographic key for a preceding entry, to perform a verifiable cryptographic operation on the result of step (b) to generate a current verification chain entry; and (d) program code configured to write, to a memory, an audit log entry including said quantity and said generated verification chain entry.
Claim 25
Dependent Claim
125 words
A computer-readable medium embodying a software program for creating an audit log entry having enhanced security against tampering, said software program comprising: (a) program code configured to receive a quantity to be logged; (b) program code configured to concatenate said quantity with at least a portion of a verification chain entry for a preceding entry; (c) program code configured to use an entry-specific cryptographic key that was derived by computing a cryptographic hash on at least a cryptographic key for a preceding entry, to perform a verifiable cryptographic operation on the result of step (b) to generate a current verification chain entry; and (d) program code configured to write, to a memory, an audit log entry including said quantity and said generated verification chain entry.
Claim 26
Dependent Claim
11 words
The software program of claim 23 contained in an electronic wallet.
Claim 27
Dependent Claim
84 words
A computer-readable medium comprising a data structure for use as an audit log entry having enhanced security against tampering, said data structure including: (a) a logged quantity; and (b) a verification chain entry comprising a verifiable cryptographic representation of: (i) at least a portion of a preceding verification chain entry, and (ii) said logged quantity; said cryptographic representation having been computed using an entry-specific cryptographic key that was derived by computing a cryptographic hash on at least a cryptographic key for said preceding entry.
Claim 28
Dependent Claim
84 words
A computer-readable medium comprising a data structure for use as an audit log entry having enhanced security against tampering, said data structure including: (a) a logged quantity; and (b) a verification chain entry comprising a verifiable cryptographic representation of: (i) at least a portion of a preceding verification chain entry, and (ii) said logged quantity; said cryptographic representation having been computed using an entry-specific cryptographic key that was derived by computing a cryptographic hash on at least a cryptographic key for said preceding entry.
Claim 29
Dependent Claim
10 words
The computer-readable medium of claim 25 comprising an electronic wallet.
Claim 30
Dependent Claim
19 words
The computer-readable medium of claim 25, said verifiable cryptographic operation being an encryption operation using said entry-specific cryptographic key.
Claim 31
Dependent Claim
26 words
The computer-readable medium of claim 25, said verifiable cryptographic operation being a MAC operation using said entry-specific cryptographic key as an authentication key for said MAC.
Claim 32
Dependent Claim
13 words
The computer-readable medium of claim 25 where said logged quantity includes a datum.
Claim 33
Dependent Claim
13 words
The computer-readable medium of claim 25 where said datum is an encrypted value.
Claim 34
Dependent Claim
38 words
The computer-readable medium of claim 25 where: (a) said logged quantity includes a permission mask, and (b) said entry-specific cryptographic key depends on: (i) said permission mask, in addition to (ii) said cryptographic key for said preceding entry.
Claim 35
Dependent Claim
21 words
The computer-readable medium of claim 31 further comprising initialization information evidencing the status of mutually verified communication with a logging partner.
Claim 36
Dependent Claim
14 words
The computer-readable medium of claim 32 wherein said logging partner is a trusted computer.
Claim 37
Dependent Claim
14 words
The computer-readable medium of claim 32 wherein said logging partner is an untrusted computer.
Claim 38
Dependent Claim
24 words
The computer-readable medium of claim 34 wherein said mutually verified communication includes a commitment to an information pertaining to a final audit log entry.
Claim 39
Dependent Claim
23 words
The computer-readable medium of claim 34 wherein said logging partner is part of a distributed logging scheme using a plurality of untrusted computers.
Claim 40
Dependent Claim
23 words
The computer-readable medium of claim 36 wherein said distributed logging scheme includes maintaining parallel logfiles on at least some of said untrusted computers.
Claim 41
Dependent Claim
23 words
The computer-readable medium of claim 37 wherein said parallel logging includes the use of pad values in at least some of said logfiles.
Claim 42
Dependent Claim
27 words
The computer-readable medium of claim 36 wherein said distributed logging scheme includes secret sharing to store a logging parameter among at least some of said untrusted computers.
Claim 43
Dependent Claim
12 words
The computer-readable medium of claim 25 wherein said computer-readable medium is non-rewritable.
Claim 44
Dependent Claim
21 words
The computer-readable medium of claim 25 wherein said verification chain entry further comprises a value from a complementary audit log process.
Claim 45
Dependent Claim
25 words
The computer-readable medium of claim 25 wherein at least one of said elements (a), (b), (c), and (d) reflects the use of asymmetric cryptographic operations.
Claim 46
Independent Claim
105 words
A method for verifying entries in an audit log, comprising the steps of: (a) receiving an audit log including a plurality of log entries, each entry having: (i) a logged quantity; and (ii) a verification chain entry comprising a verifiable cryptographic representation of: (A) at least a portion of a preceding verification chain entry, and (B) said logged quantity; said cryptographic representation having been computed using an entry-specific cryptographic key that was derived by computing a cryptographic hash on at least a cryptographic key for said preceding entry; and (b) verifying a sequence of said verification chain entries from their respective preceding verification chain entries.
Claim 47
Independent Claim
105 words
A method for verifying entries in an audit log, comprising the steps of: (a) receiving an audit log including a plurality of log entries, each entry having: (i) a logged quantity; and (ii) a verification chain entry comprising a verifiable cryptographic representation of: (A) at least a portion of a preceding verification chain entry, and (B) said logged quantity; said cryptographic representation having been computed using an entry-specific cryptographic key that was derived by computing a cryptographic hash on at least a cryptographic key for said preceding entry; and (b) verifying a sequence of said verification chain entries from their respective preceding verification chain entries.
Claim 48
Dependent Claim
73 words
The method of claim 43 where said step of verifying said sequence of said verification chain entries includes: (a) extracting, from said audit log, initialization information including a starting cryptographic key; and (b) starting from said extracted starting authentication key, computing an entry-specific cryptographic key for each of said audit log entries in said sequence by performing a cryptographic hash operation on at least a cryptographic key for a preceding audit log entry.
Claim 49
Dependent Claim
26 words
The method of claim 44 further comprising the step of verifying each of said verification chain entries using a corresponding one of said computed cryptographic keys.
Claim 50
Independent Claim
125 words
A method for creating an audit log entry having enhanced security against tampering, comprising the steps of: (a) receiving a datum to be logged; (b) encrypting said datum with a first cryptographic key; (c) concatenating a permission mask and a first verification chain entry with said encrypted datum; (d) performing a first verifiable cryptographic operation on the result of step (c) to generate a second verification chain entry; and (e) using a first authentication key, performing an authenticatable cryptographic operation on said second verification chain entry to form a cryptographically authenticatable representation thereof; (f) writing, to a memory, an audit log entry including said encrypted datum, said permission mask, said second verification chain entry, and said cryptographically authenticatable representation of said second verification chain entry.
Claim 51
Independent Claim
125 words
A method for creating an audit log entry having enhanced security against tampering, comprising the steps of: (a) receiving a datum to be logged; (b) encrypting said datum with a first cryptographic key; (c) concatenating a permission mask and a first verification chain entry with said encrypted datum; (d) performing a first verifiable cryptographic operation on the result of step (c) to generate a second verification chain entry; and (e) using a first authentication key, performing an authenticatable cryptographic operation on said second verification chain entry to form a cryptographically authenticatable representation thereof; (f) writing, to a memory, an audit log entry including said encrypted datum, said permission mask, said second verification chain entry, and said cryptographically authenticatable representation of said second verification chain entry.
Claim 52
Dependent Claim
23 words
The method of claim 46 further comprising the step of generating a second authentication key usable for a subsequently generated audit log entry.
Claim 53
Dependent Claim
24 words
The method of claim 47 wherein said step of generating a second authentication key includes computing a cryptographic hash on said first authentication key.
Claim 54
Dependent Claim
23 words
The method of claim 46 further comprising the step of generating a second cryptographic key usable for a subsequently generated audit log entry.
Claim 55
Dependent Claim
28 words
The method of claim 49 wherein said step of generating said second cryptographic key includes computing a cryptographic hash on said permission mask and said first authentication key.
Claim 56
Dependent Claim
15 words
The method of claim 50 further comprising the step of deleting said first cryptographic key.
Claim 57
Dependent Claim
15 words
The method of claim 50 further comprising the step of deleting said first authentication key.
Claim 58
Dependent Claim
155 words
A computer-readable medium embodying a software program for creating an audit log entry having enhanced security against tampering, said software program comprising: (a) program code configured to receive a datum to be logged; (b) program code configured to encrypt said datum with a first cryptographic key; (c) program code configured to concatenate a permission mask and a first verification chain entry with said encrypted datum; (d) program code configured to perform a first verifiable cryptographic operation on the result of step (c) to generate a second verification chain entry; and (e) program code configured to use a first authentication key to perform an authenticatable cryptographic operation on said second verification chain entry to form a cryptographically authenticatable representation thereof; (f) program code configured to write, to a memory, an audit log entry including said encrypted data, said permission mask, said second verification chain entry, and said cryptographically authenticatable representation of said second verification chain entry.
Claim 59
Dependent Claim
155 words
A computer-readable medium embodying a software program for creating an audit log entry having enhanced security against tampering, said software program comprising: (a) program code configured to receive a datum to be logged; (b) program code configured to encrypt said datum with a first cryptographic key; (c) program code configured to concatenate a permission mask and a first verification chain entry with said encrypted datum; (d) program code configured to perform a first verifiable cryptographic operation on the result of step (c) to generate a second verification chain entry; and (e) program code configured to use a first authentication key to perform an authenticatable cryptographic operation on said second verification chain entry to form a cryptographically authenticatable representation thereof; (f) program code configured to write, to a memory, an audit log entry including said encrypted data, said permission mask, said second verification chain entry, and said cryptographically authenticatable representation of said second verification chain entry.
Claim 60
Dependent Claim
11 words
The software program of claim 53 contained in an electronic wallet.
Claim 61
Dependent Claim
111 words
A computer-readable medium comprising a data structure for use as an audit log entry having enhanced security against tampering, said data structure including: (a) a permission mask; (b) an encrypted datum having been encrypted using a cryptographic key, said cryptographic key comprising a first cryptographic representation of: (i) said permission mask, and (ii) an authentication key; (c) a verification chain entry comprising a second cryptographic representation of: (i) a preceding verification chain entry, (ii) said permission mask, and (iii) said encrypted datum; and (d) a third cryptographic representation, of said verification chain entry, having been derived by performing an authenticatable cryptographic operation on said verification chain entry using said authentication key.
Claim 62
Dependent Claim
111 words
A computer-readable medium comprising a data structure for use as an audit log entry having enhanced security against tampering, said data structure including: (a) a permission mask; (b) an encrypted datum having been encrypted using a cryptographic key, said cryptographic key comprising a first cryptographic representation of: (i) said permission mask, and (ii) an authentication key; (c) a verification chain entry comprising a second cryptographic representation of: (i) a preceding verification chain entry, (ii) said permission mask, and (iii) said encrypted datum; and (d) a third cryptographic representation, of said verification chain entry, having been derived by performing an authenticatable cryptographic operation on said verification chain entry using said authentication key.
Claim 63
Dependent Claim
10 words
The computer-readable medium of claim 55 comprising an electronic wallet.
Claim 64
Dependent Claim
18 words
The data structure of claim 55, said first cryptographic representation having been derived using a cryptographic hash operation.
Claim 65
Dependent Claim
18 words
The data structure of claim 55, said second cryptographic representation having been derived using a cryptographic hash operation.
Claim 66
Dependent Claim
14 words
The data structure of claim 55, said authenticatable cryptographic operation being a MAC operation.
Claim 67
Dependent Claim
23 words
The data structure of claim 55, said authentication key having been derived by performing a cryptographic hash operation on a preceding authentication key.
Claim 68
Independent Claim
135 words
A method for verifying entries in an audit log, comprising the steps of: (a) receiving an audit log including a plurality of log entries, each entry having: (i) a permission mask, (ii) an encrypted datum having been encrypted using a cryptographic key, said cryptographic key being a first cryptographic representation of: (A) said permission mask, and (B) an authentication key specific to said entry, (iii) a verification chain entry that is a second cryptographic representation of: (A) a preceding verification chain entry, (B) said permission mask, and (C) said encrypted datum; and (iv) a cryptographically authenticatable representation of said verification chain entry, derived by performing an authenticatable cryptographic operation on said verification chain entry using said authentication key; and (b) verifying a sequence of said verification chain entries from their respective preceding verification chain entries.
Claim 69
Independent Claim
135 words
A method for verifying entries in an audit log, comprising the steps of: (a) receiving an audit log including a plurality of log entries, each entry having: (i) a permission mask, (ii) an encrypted datum having been encrypted using a cryptographic key, said cryptographic key being a first cryptographic representation of: (A) said permission mask, and (B) an authentication key specific to said entry, (iii) a verification chain entry that is a second cryptographic representation of: (A) a preceding verification chain entry, (B) said permission mask, and (C) said encrypted datum; and (iv) a cryptographically authenticatable representation of said verification chain entry, derived by performing an authenticatable cryptographic operation on said verification chain entry using said authentication key; and (b) verifying a sequence of said verification chain entries from their respective preceding verification chain entries.
Claim 70
Dependent Claim
78 words
The method of claim 61 further comprising the steps of: (a) extracting, from said audit log: (i) initialization information including a starting authentication key and a starting cryptographic key, and (ii) a permission mask entry for each of said audit log entries; and (b) starting from said extracted starting authentication key, computing an authentication key, for each of said audit log entries, by performing a first cryptographic operation on an authentication key for a preceding audit log entry.
Claim 71
Dependent Claim
14 words
The method of claim 62 wherein said first cryptographic operation is a hash operation.
Claim 72
Dependent Claim
42 words
The method of claim 62 further comprising the step of verifying a last of said verification chain entries by recomputing said third cryptographic representation of said last verification chain entry, using said authentication key for said last of said audit log entries.
Claim 73
Dependent Claim
26 words
The method of claim 62 further comprising the step of verifying each of said verification chain entries using a corresponding one of said computed authentication keys.
Claim 74
Dependent Claim
39 words
The method of claim 62 further comprising the step of computing a cryptographic key for each of said audit log entries, by performing a second cryptographic operation on corresponding ones of said permission masks and said computed authentication keys.
Claim 75
Dependent Claim
14 words
The method of claim 66 wherein said second cryptographic operation is a hash operation.
Claim 76
Dependent Claim
26 words
The method of claim 66 further comprising the step of decrypting at least some of said encrypted data using corresponding ones of said computed cryptographic keys.
Claim 77
Dependent Claim
97 words
The method of claim 61 further comprising the steps of: (a) identifying a subset of said audit log entries to which access is desired; (b) sending a request, including corresponding ones of said permission masks for said audit log entries of said subset, to a trusted computer that participated in creation of said audit log; and (c) receiving from said trusted computer a response to said request, said response including a cryptographic key for each of said audit log entries in said request, each said cryptographic key having been computed from said permission masks in said request.
Claim 78
Dependent Claim
24 words
The method of claim 69 further comprising the step of using said received cryptographic keys to decrypt said audit log entries of said subset.
References Cited (Backward Citations)
US34954A
Cited
US4672572A
Cited
US5032979A
Cited
USRE34954E
Cited
US5155693A
Cited
US5136646A
Cited
US5428795A
Cited
US5557742A
Cited
US5696702A
Cited
US5675510A
Cited
US5828882A
Cited
US5826021A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |