1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2012 Lennart Poettering
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
28 #include "journal-def.h"
29 #include "journal-file.h"
30 #include "journal-authenticate.h"
31 #include "journal-verify.h"
38 * - write bit mucking test
39 * - tag timestamps should be between entry timestamps
40 * - output validated time ranges
41 * - evolve key even if nothing happened in regular intervals
43 * - Allow building without libgcrypt
49 static int journal_file_object_verify(JournalFile *f, Object *o) {
53 /* This does various superficial tests about the length an
54 * possible field values. It does not follow any references to
57 if ((o->object.flags & OBJECT_COMPRESSED) &&
58 o->object.type != OBJECT_DATA)
61 switch (o->object.type) {
66 if (le64toh(o->data.entry_offset) <= 0 ||
67 le64toh(o->data.n_entries) <= 0)
70 if (le64toh(o->object.size) - offsetof(DataObject, payload) <= 0)
73 h1 = le64toh(o->data.hash);
75 if (o->object.flags & OBJECT_COMPRESSED) {
77 uint64_t alloc = 0, b_size;
79 if (!uncompress_blob(o->data.payload,
80 le64toh(o->object.size) - offsetof(Object, data.payload),
84 h2 = hash64(b, b_size);
87 h2 = hash64(o->data.payload, le64toh(o->object.size) - offsetof(Object, data.payload));
96 if (le64toh(o->object.size) - offsetof(FieldObject, payload) <= 0)
101 if ((le64toh(o->object.size) - offsetof(EntryObject, items)) % sizeof(EntryItem) != 0)
104 if ((le64toh(o->object.size) - offsetof(EntryObject, items)) / sizeof(EntryItem) <= 0)
107 if (le64toh(o->entry.seqnum) <= 0 ||
108 le64toh(o->entry.realtime) <= 0)
113 case OBJECT_DATA_HASH_TABLE:
114 case OBJECT_FIELD_HASH_TABLE:
115 if ((le64toh(o->object.size) - offsetof(HashTableObject, items)) % sizeof(HashItem) != 0)
118 if ((le64toh(o->object.size) - offsetof(HashTableObject, items)) / sizeof(HashItem) <= 0)
123 case OBJECT_ENTRY_ARRAY:
124 if ((le64toh(o->object.size) - offsetof(EntryArrayObject, items)) % sizeof(le64_t) != 0)
127 if ((le64toh(o->object.size) - offsetof(EntryArrayObject, items)) / sizeof(le64_t) <= 0)
133 if (le64toh(o->object.size) != sizeof(TagObject))
141 static void draw_progress(uint64_t p, usec_t *last_usec) {
145 if (!isatty(STDOUT_FILENO))
148 z = now(CLOCK_MONOTONIC);
151 if (x != 0 && x + 40 * USEC_PER_MSEC > z)
156 n = (3 * columns()) / 4;
157 j = (n * (unsigned) p) / 65535ULL;
160 fputs("\r\x1B[?25l" ANSI_HIGHLIGHT_GREEN_ON, stdout);
162 for (i = 0; i < j; i++)
163 fputs("\xe2\x96\x88", stdout);
165 fputs(ANSI_HIGHLIGHT_OFF, stdout);
167 for (i = 0; i < k; i++)
168 fputs("\xe2\x96\x91", stdout);
170 printf(" %3lu%%", 100LU * (unsigned long) p / 65535LU);
172 fputs("\r\x1B[?25h", stdout);
176 static void flush_progress(void) {
179 if (!isatty(STDOUT_FILENO))
182 n = (3 * columns()) / 4;
186 for (i = 0; i < n + 5; i++)
193 static int write_uint64(int fd, uint64_t p) {
196 k = write(fd, &p, sizeof(p));
205 static int contains_uint64(MMapCache *m, int fd, uint64_t n, uint64_t p) {
220 r = mmap_cache_get(m, fd, PROT_READ|PROT_WRITE, 0, c * sizeof(uint64_t), sizeof(uint64_t), (void **) &z);
236 static int entry_points_to_data(
249 assert(entry_fd >= 0);
251 if (!contains_uint64(f->mmap, entry_fd, n_entries, entry_p)) {
252 log_error("Data object references invalid entry at %llu", (unsigned long long) data_p);
256 r = journal_file_move_to_object(f, OBJECT_ENTRY, entry_p, &o);
260 n = journal_file_entry_n_items(o);
261 for (i = 0; i < n; i++)
262 if (le64toh(o->entry.items[i].object_offset) == data_p) {
268 log_error("Data object not referenced by linked entry at %llu", (unsigned long long) data_p);
272 /* Check if this entry is also in main entry array. Since the
273 * main entry array has already been verified we can rely on
276 n = le64toh(f->header->n_entries);
277 a = le64toh(f->header->entry_array_offset);
283 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
287 m = journal_file_entry_array_n_items(o);
288 for (j = 0; i < n && j < m; i++, j++)
289 if (le64toh(o->entry_array.items[j]) == entry_p)
292 a = le64toh(o->entry_array.next_entry_array_offset);
298 static int verify_data(
300 Object *o, uint64_t p,
301 int entry_fd, uint64_t n_entries,
302 int entry_array_fd, uint64_t n_entry_arrays) {
304 uint64_t i, n, a, last, q;
309 assert(entry_fd >= 0);
310 assert(entry_array_fd >= 0);
312 n = le64toh(o->data.n_entries);
313 a = le64toh(o->data.entry_array_offset);
315 /* We already checked this earlier */
318 last = q = le64toh(o->data.entry_offset);
319 r = entry_points_to_data(f, entry_fd, n_entries, q, p);
328 log_error("Array chain too short at %llu", (unsigned long long) p);
332 if (!contains_uint64(f->mmap, entry_array_fd, n_entry_arrays, a)) {
333 log_error("Invalid array at %llu", (unsigned long long) p);
337 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
341 next = le64toh(o->entry_array.next_entry_array_offset);
342 if (next != 0 && next <= a) {
343 log_error("Array chain has cycle at %llu", (unsigned long long) p);
347 m = journal_file_entry_array_n_items(o);
348 for (j = 0; i < n && j < m; i++, j++) {
350 q = le64toh(o->entry_array.items[j]);
352 log_error("Data object's entry array not sorted at %llu", (unsigned long long) p);
357 r = entry_points_to_data(f, entry_fd, n_entries, q, p);
361 /* Pointer might have moved, reposition */
362 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
373 static int verify_hash_table(
375 int data_fd, uint64_t n_data,
376 int entry_fd, uint64_t n_entries,
377 int entry_array_fd, uint64_t n_entry_arrays,
384 assert(data_fd >= 0);
385 assert(entry_fd >= 0);
386 assert(entry_array_fd >= 0);
389 n = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
390 for (i = 0; i < n; i++) {
391 uint64_t last = 0, p;
393 draw_progress(0xC000 + (0x3FFF * i / n), last_usec);
395 p = le64toh(f->data_hash_table[i].head_hash_offset);
400 if (!contains_uint64(f->mmap, data_fd, n_data, p)) {
401 log_error("Invalid data object at hash entry %llu of %llu",
402 (unsigned long long) i, (unsigned long long) n);
406 r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
410 next = le64toh(o->data.next_hash_offset);
411 if (next != 0 && next <= p) {
412 log_error("Hash chain has a cycle in hash entry %llu of %llu",
413 (unsigned long long) i, (unsigned long long) n);
417 if (le64toh(o->data.hash) % n != i) {
418 log_error("Hash value mismatch in hash entry %llu of %llu",
419 (unsigned long long) i, (unsigned long long) n);
423 r = verify_data(f, o, p, entry_fd, n_entries, entry_array_fd, n_entry_arrays);
431 if (last != le64toh(f->data_hash_table[i].tail_hash_offset)) {
432 log_error("Tail hash pointer mismatch in hash table");
440 static int data_object_in_hash_table(JournalFile *f, uint64_t hash, uint64_t p) {
445 n = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
448 q = le64toh(f->data_hash_table[h].head_hash_offset);
455 r = journal_file_move_to_object(f, OBJECT_DATA, q, &o);
459 q = le64toh(o->data.next_hash_offset);
465 static int verify_entry(
467 Object *o, uint64_t p,
468 int data_fd, uint64_t n_data) {
475 assert(data_fd >= 0);
477 n = journal_file_entry_n_items(o);
478 for (i = 0; i < n; i++) {
482 q = le64toh(o->entry.items[i].object_offset);
483 h = le64toh(o->entry.items[i].hash);
485 if (!contains_uint64(f->mmap, data_fd, n_data, q)) {
486 log_error("Invalid data object at entry %llu",
487 (unsigned long long) p);
491 r = journal_file_move_to_object(f, OBJECT_DATA, q, &u);
495 if (le64toh(u->data.hash) != h) {
496 log_error("Hash mismatch for data object at entry %llu",
497 (unsigned long long) p);
501 r = data_object_in_hash_table(f, h, q);
505 log_error("Data object missing from hash at entry %llu",
506 (unsigned long long) p);
514 static int verify_entry_array(
516 int data_fd, uint64_t n_data,
517 int entry_fd, uint64_t n_entries,
518 int entry_array_fd, uint64_t n_entry_arrays,
521 uint64_t i = 0, a, n, last = 0;
525 assert(data_fd >= 0);
526 assert(entry_fd >= 0);
527 assert(entry_array_fd >= 0);
530 n = le64toh(f->header->n_entries);
531 a = le64toh(f->header->entry_array_offset);
536 draw_progress(0x8000 + (0x3FFF * i / n), last_usec);
539 log_error("Array chain too short at %llu of %llu",
540 (unsigned long long) i, (unsigned long long) n);
544 if (!contains_uint64(f->mmap, entry_array_fd, n_entry_arrays, a)) {
545 log_error("Invalid array at %llu of %llu",
546 (unsigned long long) i, (unsigned long long) n);
550 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
554 next = le64toh(o->entry_array.next_entry_array_offset);
555 if (next != 0 && next <= a) {
556 log_error("Array chain has cycle at %llu of %llu",
557 (unsigned long long) i, (unsigned long long) n);
561 m = journal_file_entry_array_n_items(o);
562 for (j = 0; i < n && j < m; i++, j++) {
565 p = le64toh(o->entry_array.items[j]);
567 log_error("Entry array not sorted at %llu of %llu",
568 (unsigned long long) i, (unsigned long long) n);
573 if (!contains_uint64(f->mmap, entry_fd, n_entries, p)) {
574 log_error("Invalid array entry at %llu of %llu",
575 (unsigned long long) i, (unsigned long long) n);
579 r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
583 r = verify_entry(f, o, p, data_fd, n_data);
587 /* Pointer might have moved, reposition */
588 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
599 static int journal_file_parse_verification_key(JournalFile *f, const char *key) {
604 unsigned long long start, interval;
606 seed_size = FSPRG_RECOMMENDED_SEEDLEN;
607 seed = malloc(seed_size);
612 for (c = 0; c < seed_size; c++) {
631 seed[c] = (uint8_t) (x * 16 + y);
640 r = sscanf(k, "%llx-%llx", &start, &interval);
646 f->fsprg_seed = seed;
647 f->fsprg_seed_size = seed_size;
649 f->fss_start_usec = start * interval;
650 f->fss_interval_usec = interval;
655 int journal_file_verify(JournalFile *f, const char *key) {
658 uint64_t p = 0, last_tag = 0, last_epoch = 0, last_tag_realtime = 0;
659 uint64_t entry_seqnum = 0, entry_monotonic = 0, entry_realtime = 0;
660 sd_id128_t entry_boot_id;
661 bool entry_seqnum_set = false, entry_monotonic_set = false, entry_realtime_set = false, found_main_entry_array = false;
662 uint64_t n_weird = 0, n_objects = 0, n_entries = 0, n_data = 0, n_fields = 0, n_data_hash_tables = 0, n_field_hash_tables = 0, n_entry_arrays = 0, n_tags = 0;
663 usec_t last_usec = 0;
664 int data_fd = -1, entry_fd = -1, entry_array_fd = -1;
665 char data_path[] = "/var/tmp/journal-data-XXXXXX",
666 entry_path[] = "/var/tmp/journal-entry-XXXXXX",
667 entry_array_path[] = "/var/tmp/journal-entry-array-XXXXXX";
672 r = journal_file_parse_verification_key(f, key);
674 log_error("Failed to parse seed.");
679 data_fd = mkostemp(data_path, O_CLOEXEC);
681 log_error("Failed to create data file: %m");
687 entry_fd = mkostemp(entry_path, O_CLOEXEC);
689 log_error("Failed to create entry file: %m");
695 entry_array_fd = mkostemp(entry_array_path, O_CLOEXEC);
696 if (entry_array_fd < 0) {
697 log_error("Failed to create entry array file: %m");
701 unlink(entry_array_path);
703 /* First iteration: we go through all objects, verify the
704 * superficial structure, headers, hashes. */
706 p = le64toh(f->header->header_size);
708 draw_progress(0x7FFF * p / le64toh(f->header->tail_object_offset), &last_usec);
710 r = journal_file_move_to_object(f, -1, p, &o);
712 log_error("Invalid object at %llu", (unsigned long long) p);
716 if (le64toh(f->header->tail_object_offset) < p) {
717 log_error("Invalid tail object pointer");
724 r = journal_file_object_verify(f, o);
726 log_error("Invalid object contents at %llu", (unsigned long long) p);
730 if (o->object.flags & OBJECT_COMPRESSED &&
731 !(le32toh(f->header->incompatible_flags) & HEADER_INCOMPATIBLE_COMPRESSED)) {
732 log_error("Compressed object in file without compression at %llu", (unsigned long long) p);
737 switch (o->object.type) {
740 r = write_uint64(data_fd, p);
752 r = write_uint64(entry_fd, p);
756 if (last_tag_realtime > le64toh(o->entry.realtime)) {
757 log_error("Older entry after newer tag at %llu", (unsigned long long) p);
762 if (!entry_seqnum_set &&
763 le64toh(o->entry.seqnum) != le64toh(f->header->head_entry_seqnum)) {
764 log_error("Head entry sequence number incorrect at %llu", (unsigned long long) p);
769 if (entry_seqnum_set &&
770 entry_seqnum >= le64toh(o->entry.seqnum)) {
771 log_error("Entry sequence number out of synchronization at %llu", (unsigned long long) p);
776 entry_seqnum = le64toh(o->entry.seqnum);
777 entry_seqnum_set = true;
779 if (entry_monotonic_set &&
780 sd_id128_equal(entry_boot_id, o->entry.boot_id) &&
781 entry_monotonic > le64toh(o->entry.monotonic)) {
782 log_error("Entry timestamp out of synchronization at %llu", (unsigned long long) p);
787 entry_monotonic = le64toh(o->entry.monotonic);
788 entry_boot_id = o->entry.boot_id;
789 entry_monotonic_set = true;
791 if (!entry_realtime_set &&
792 le64toh(o->entry.realtime) != le64toh(f->header->head_entry_realtime)) {
793 log_error("Head entry realtime timestamp incorrect");
798 entry_realtime = le64toh(o->entry.realtime);
799 entry_realtime_set = true;
804 case OBJECT_DATA_HASH_TABLE:
805 if (n_data_hash_tables > 1) {
806 log_error("More than one data hash table at %llu", (unsigned long long) p);
811 if (le64toh(f->header->data_hash_table_offset) != p + offsetof(HashTableObject, items) ||
812 le64toh(f->header->data_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
813 log_error("Header fields for data hash table invalid");
818 n_data_hash_tables++;
821 case OBJECT_FIELD_HASH_TABLE:
822 if (n_field_hash_tables > 1) {
823 log_error("More than one field hash table at %llu", (unsigned long long) p);
828 if (le64toh(f->header->field_hash_table_offset) != p + offsetof(HashTableObject, items) ||
829 le64toh(f->header->field_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
830 log_error("Header fields for field hash table invalid");
835 n_field_hash_tables++;
838 case OBJECT_ENTRY_ARRAY:
839 r = write_uint64(entry_array_fd, p);
843 if (p == le64toh(f->header->entry_array_offset)) {
844 if (found_main_entry_array) {
845 log_error("More than one main entry array at %llu", (unsigned long long) p);
850 found_main_entry_array = true;
859 if (!(le32toh(f->header->compatible_flags) & HEADER_COMPATIBLE_SEALED)) {
860 log_error("Tag object in file without sealing at %llu", (unsigned long long) p);
865 log_debug("Checking tag %llu..", (unsigned long long) le64toh(o->tag.seqnum));
867 if (le64toh(o->tag.seqnum) != n_tags + 1) {
868 log_error("Tag sequence number out of synchronization at %llu", (unsigned long long) p);
873 if (le64toh(o->tag.epoch) < last_epoch) {
874 log_error("Epoch sequence out of synchronization at %llu", (unsigned long long) p);
879 last_tag_realtime = (o->tag.epoch + 1) * f->fss_interval_usec + f->fss_start_usec;
880 if (entry_realtime_set && entry_realtime >= last_tag_realtime) {
881 log_error("Tag/entry realtime timestamp out of synchronization at %llu", (unsigned long long) p);
886 /* OK, now we know the epoch. So let's now set
887 * it, and calculate the HMAC for everything
888 * since the last tag. */
889 r = journal_file_fsprg_seek(f, le64toh(o->tag.epoch));
893 r = journal_file_hmac_start(f);
898 r = journal_file_hmac_put_header(f);
902 q = le64toh(f->header->header_size);
907 r = journal_file_move_to_object(f, -1, q, &o);
911 r = journal_file_hmac_put_object(f, -1, q);
915 q = q + ALIGN64(le64toh(o->object.size));
918 /* Position might have changed, let's reposition things */
919 r = journal_file_move_to_object(f, -1, p, &o);
923 if (memcmp(o->tag.tag, gcry_md_read(f->hmac, 0), TAG_LENGTH) != 0) {
924 log_error("Tag failed verification at %llu", (unsigned long long) p);
929 f->hmac_running = false;
931 last_tag = p + ALIGN64(le64toh(o->object.size));
940 if (p == le64toh(f->header->tail_object_offset))
943 p = p + ALIGN64(le64toh(o->object.size));
946 if (n_objects != le64toh(f->header->n_objects)) {
947 log_error("Object number mismatch");
952 if (n_entries != le64toh(f->header->n_entries)) {
953 log_error("Entry number mismatch");
958 if (JOURNAL_HEADER_CONTAINS(f->header, n_data) &&
959 n_data != le64toh(f->header->n_data)) {
960 log_error("Data number mismatch");
965 if (JOURNAL_HEADER_CONTAINS(f->header, n_fields) &&
966 n_fields != le64toh(f->header->n_fields)) {
967 log_error("Field number mismatch");
972 if (JOURNAL_HEADER_CONTAINS(f->header, n_tags) &&
973 n_tags != le64toh(f->header->n_tags)) {
974 log_error("Tag number mismatch");
979 if (JOURNAL_HEADER_CONTAINS(f->header, n_entry_arrays) &&
980 n_entry_arrays != le64toh(f->header->n_entry_arrays)) {
981 log_error("Entry array number mismatch");
986 if (n_data_hash_tables != 1) {
987 log_error("Missing data hash table");
992 if (n_field_hash_tables != 1) {
993 log_error("Missing field hash table");
998 if (!found_main_entry_array) {
999 log_error("Missing entry array");
1004 if (entry_seqnum_set &&
1005 entry_seqnum != le64toh(f->header->tail_entry_seqnum)) {
1006 log_error("Invalid tail seqnum");
1011 if (entry_monotonic_set &&
1012 (!sd_id128_equal(entry_boot_id, f->header->boot_id) ||
1013 entry_monotonic != le64toh(f->header->tail_entry_monotonic))) {
1014 log_error("Invalid tail monotonic timestamp");
1019 if (entry_realtime_set && entry_realtime != le64toh(f->header->tail_entry_realtime)) {
1020 log_error("Invalid tail realtime timestamp");
1025 /* Second iteration: we follow all objects referenced from the
1026 * two entry points: the object hash table and the entry
1027 * array. We also check that everything referenced (directly
1028 * or indirectly) in the data hash table also exists in the
1029 * entry array, and vice versa. Note that we do not care for
1030 * unreferenced objects. We only care that everything that is
1031 * referenced is consistent. */
1033 r = verify_entry_array(f,
1035 entry_fd, n_entries,
1036 entry_array_fd, n_entry_arrays,
1041 r = verify_hash_table(f,
1043 entry_fd, n_entries,
1044 entry_array_fd, n_entry_arrays,
1051 mmap_cache_close_fd(f->mmap, data_fd);
1052 mmap_cache_close_fd(f->mmap, entry_fd);
1053 mmap_cache_close_fd(f->mmap, entry_array_fd);
1055 close_nointr_nofail(data_fd);
1056 close_nointr_nofail(entry_fd);
1057 close_nointr_nofail(entry_array_fd);
1064 log_error("File corruption detected at %s:%llu (of %llu, %llu%%).",
1066 (unsigned long long) p,
1067 (unsigned long long) f->last_stat.st_size,
1068 (unsigned long long) (100 * p / f->last_stat.st_size));
1071 mmap_cache_close_fd(f->mmap, data_fd);
1072 close_nointr_nofail(data_fd);
1075 if (entry_fd >= 0) {
1076 mmap_cache_close_fd(f->mmap, entry_fd);
1077 close_nointr_nofail(entry_fd);
1080 if (entry_array_fd >= 0) {
1081 mmap_cache_close_fd(f->mmap, entry_array_fd);
1082 close_nointr_nofail(entry_array_fd);