journald: initial version of FSPRG hookup

This adds forward-secure authentication of journal files. This patch
includes key generation as well as tagging of journal files,
Verification of journal files will be added in a later patch.

10 files changed, 1182 insertions, 74 deletions

diff --git a/src/journal/fsprg.c b/src/journal/fsprg.c
new file mode 100644
index 0000000000..34ce3be96b
--- /dev/null
+++ b/src/journal/fsprg.c
@@ -0,0 +1,384 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/*
+ * fsprg v0.1  -  (seekable) forward-secure pseudorandom generator
+ * Copyright (C) 2012 B. Poettering
+ * Contact: fsprg@point-at-infinity.org
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301  USA
+ *
+ */
+
+#include <gcrypt.h>
+#include <string.h>
+#include <assert.h>
+
+#include "fsprg.h"
+
+#define ISVALID_SECPAR(secpar) (((secpar) % 16 == 0) && ((secpar) >= 16) && ((secpar) <= 16384))
+#define VALIDATE_SECPAR(secpar) assert(ISVALID_SECPAR(secpar));
+
+#define RND_HASH GCRY_MD_SHA256
+#define RND_GEN_P 0x01
+#define RND_GEN_Q 0x02
+#define RND_GEN_X 0x03
+
+/******************************************************************************/
+
+static void mpi_export(void *buf, size_t buflen, const gcry_mpi_t x) {
+        unsigned len;
+        size_t nwritten;
+
+        assert(gcry_mpi_cmp_ui(x, 0) >= 0);
+        len = (gcry_mpi_get_nbits(x) + 7) / 8;
+        assert(len <= buflen);
+        memset(buf, 0, buflen);
+        gcry_mpi_print(GCRYMPI_FMT_USG, buf + (buflen - len), len, &nwritten, x);
+        assert(nwritten == len);
+}
+
+static gcry_mpi_t mpi_import(const void *buf, size_t buflen) {
+        gcry_mpi_t h;
+        unsigned len;
+
+        gcry_mpi_scan(&h, GCRYMPI_FMT_USG, buf, buflen, NULL);
+        len = (gcry_mpi_get_nbits(h) + 7) / 8;
+        assert(len <= buflen);
+        assert(gcry_mpi_cmp_ui(h, 0) >= 0);
+
+        return h;
+}
+
+static void uint64_export(void *buf, size_t buflen, uint64_t x) {
+        assert(buflen == 8);
+        ((uint8_t*) buf)[0] = (x >> 56) & 0xff;
+        ((uint8_t*) buf)[1] = (x >> 48) & 0xff;
+        ((uint8_t*) buf)[2] = (x >> 40) & 0xff;
+        ((uint8_t*) buf)[3] = (x >> 32) & 0xff;
+        ((uint8_t*) buf)[4] = (x >> 24) & 0xff;
+        ((uint8_t*) buf)[5] = (x >> 16) & 0xff;
+        ((uint8_t*) buf)[6] = (x >>  8) & 0xff;
+        ((uint8_t*) buf)[7] = (x >>  0) & 0xff;
+}
+
+static uint64_t uint64_import(const void *buf, size_t buflen) {
+        assert(buflen == 8);
+        return
+                (uint64_t)(((uint8_t*) buf)[0]) << 56 |
+                (uint64_t)(((uint8_t*) buf)[1]) << 48 |
+                (uint64_t)(((uint8_t*) buf)[2]) << 40 |
+                (uint64_t)(((uint8_t*) buf)[3]) << 32 |
+                (uint64_t)(((uint8_t*) buf)[4]) << 24 |
+                (uint64_t)(((uint8_t*) buf)[5]) << 16 |
+                (uint64_t)(((uint8_t*) buf)[6]) <<  8 |
+                (uint64_t)(((uint8_t*) buf)[7]) <<  0;
+}
+
+/* deterministically generate from seed/idx a string of buflen pseudorandom bytes */
+static void det_randomize(void *buf, size_t buflen, const void *seed, size_t seedlen, uint32_t idx) {
+        gcry_md_hd_t hd, hd2;
+        size_t olen, cpylen;
+        uint32_t ctr;
+
+        olen = gcry_md_get_algo_dlen(RND_HASH);
+        gcry_md_open(&hd, RND_HASH, 0);
+        gcry_md_write(hd, seed, seedlen);
+        gcry_md_putc(hd, (idx >> 24) & 0xff);
+        gcry_md_putc(hd, (idx >> 16) & 0xff);
+        gcry_md_putc(hd, (idx >>  8) & 0xff);
+        gcry_md_putc(hd, (idx >>  0) & 0xff);
+
+        for (ctr = 0; buflen; ctr++) {
+                gcry_md_copy(&hd2, hd);
+                gcry_md_putc(hd2, (ctr >> 24) & 0xff);
+                gcry_md_putc(hd2, (ctr >> 16) & 0xff);
+                gcry_md_putc(hd2, (ctr >>  8) & 0xff);
+                gcry_md_putc(hd2, (ctr >>  0) & 0xff);
+                gcry_md_final(hd2);
+                cpylen = (buflen < olen) ? buflen : olen;
+                memcpy(buf, gcry_md_read(hd2, RND_HASH), cpylen);
+                gcry_md_close(hd2);
+                buf += cpylen;
+                buflen -= cpylen;
+        }
+        gcry_md_close(hd);
+}
+
+/* deterministically generate from seed/idx a prime of length `bits' that is 3 (mod 4) */
+static gcry_mpi_t genprime3mod4(int bits, const void *seed, size_t seedlen, uint32_t idx) {
+        size_t buflen = bits / 8;
+        uint8_t buf[buflen];
+        gcry_mpi_t p;
+
+        assert(bits % 8 == 0);
+        assert(buflen > 0);
+
+        det_randomize(buf, buflen, seed, seedlen, idx);
+        buf[0] |= 0xc0; /* set upper two bits, so that n=pq has maximum size */
+        buf[buflen - 1] |= 0x03; /* set lower two bits, to have result 3 (mod 4) */
+
+        p = mpi_import(buf, buflen);
+        while (gcry_prime_check(p, 0))
+                gcry_mpi_add_ui(p, p, 4);
+
+        return p;
+}
+
+/* deterministically generate from seed/idx a quadratic residue (mod n) */
+static gcry_mpi_t gensquare(const gcry_mpi_t n, const void *seed, size_t seedlen, uint32_t idx, unsigned secpar) {
+        size_t buflen = secpar / 8;
+        uint8_t buf[buflen];
+        gcry_mpi_t x;
+
+        det_randomize(buf, buflen, seed, seedlen, idx);
+        buf[0] &= 0x7f; /* clear upper bit, so that we have x < n */
+        x = mpi_import(buf, buflen);
+        assert(gcry_mpi_cmp(x, n) < 0);
+        gcry_mpi_mulm(x, x, x, n);
+        return x;
+}
+
+/* compute 2^m (mod phi(p)), for a prime p */
+static gcry_mpi_t twopowmodphi(uint64_t m, const gcry_mpi_t p) {
+        gcry_mpi_t phi, r;
+        int n;
+
+        phi = gcry_mpi_new(0);
+        gcry_mpi_sub_ui(phi, p, 1);
+
+        /* count number of used bits in m */
+        for (n = 0; ((uint64_t)1 << n) <= m; n++)
+                ;
+
+        r = gcry_mpi_new(0);
+        gcry_mpi_set_ui(r, 1);
+        while (n) { /* square and multiply algorithm for fast exponentiation */
+                n--;
+                gcry_mpi_mulm(r, r, r, phi);
+                if (m & ((uint64_t)1 << n)) {
+                        gcry_mpi_add(r, r, r);
+                        if (gcry_mpi_cmp(r, phi) >= 0)
+                                gcry_mpi_sub(r, r, phi);
+                }
+        }
+
+        gcry_mpi_release(phi);
+        return r;
+}
+
+/* Decompose $x \in Z_n$ into $(xp,xq) \in Z_p \times Z_q$ using Chinese Remainder Theorem */
+static void CRT_decompose(gcry_mpi_t *xp, gcry_mpi_t *xq, const gcry_mpi_t x, const gcry_mpi_t p, const gcry_mpi_t q) {
+        *xp = gcry_mpi_new(0);
+        *xq = gcry_mpi_new(0);
+        gcry_mpi_mod(*xp, x, p);
+        gcry_mpi_mod(*xq, x, q);
+}
+
+/* Compose $(xp,xq) \in Z_p \times Z_q$ into $x \in Z_n$ using Chinese Remainder Theorem */
+static void CRT_compose(gcry_mpi_t *x, const gcry_mpi_t xp, const gcry_mpi_t xq, const gcry_mpi_t p, const gcry_mpi_t q) {
+        gcry_mpi_t a, u;
+
+        a = gcry_mpi_new(0);
+        u = gcry_mpi_new(0);
+        *x = gcry_mpi_new(0);
+        gcry_mpi_subm(a, xq, xp, q);
+        gcry_mpi_invm(u, p, q);
+        gcry_mpi_mulm(a, a, u, q); /* a = (xq - xp) / p  (mod q) */
+        gcry_mpi_mul(*x, p, a);
+        gcry_mpi_add(*x, *x, xp); /* x = p * ((xq - xp) / p mod q) + xp */
+        gcry_mpi_release(a);
+        gcry_mpi_release(u);
+}
+
+static void initialize_libgcrypt(void) {
+        const char *p;
+        if (gcry_control(GCRYCTL_INITIALIZATION_FINISHED_P))
+                return;
+
+        p = gcry_check_version("1.4.5");
+        assert(p);
+
+        /* Turn off "secmem". Clients which whish to make use of this
+         * feature should initialize the library manually */
+        gcry_control(GCRYCTL_DISABLE_SECMEM);
+        gcry_control(GCRYCTL_INITIALIZATION_FINISHED, 0);
+}
+
+/******************************************************************************/
+
+size_t FSPRG_mskinbytes(unsigned _secpar) {
+        VALIDATE_SECPAR(_secpar);
+        return 2 + 2 * (_secpar / 2) / 8; /* to store header,p,q */
+}
+
+size_t FSPRG_mpkinbytes(unsigned _secpar) {
+        VALIDATE_SECPAR(_secpar);
+        return 2 + _secpar / 8; /* to store header,n */
+}
+
+size_t FSPRG_stateinbytes(unsigned _secpar) {
+        VALIDATE_SECPAR(_secpar);
+        return 2 + 2 * _secpar / 8 + 8; /* to store header,n,x,epoch */
+}
+
+static void store_secpar(void *buf, uint16_t secpar) {
+        secpar = secpar / 16 - 1;
+        ((uint8_t*) buf)[0] = (secpar >> 8) & 0xff;
+        ((uint8_t*) buf)[1] = (secpar >> 0) & 0xff;
+}
+
+static uint16_t read_secpar(const void *buf) {
+        uint16_t secpar;
+        secpar =
+                (uint16_t)(((uint8_t*) buf)[0]) << 8 |
+                (uint16_t)(((uint8_t*) buf)[1]) << 0;
+        return 16 * (secpar + 1);
+}
+
+void FSPRG_GenMK(void *msk, void *mpk, const void *seed, size_t seedlen, unsigned _secpar) {
+        uint8_t iseed[FSPRG_RECOMMENDED_SEEDLEN];
+        gcry_mpi_t n, p, q;
+        uint16_t secpar;
+
+        VALIDATE_SECPAR(_secpar);
+        secpar = _secpar;
+
+        initialize_libgcrypt();
+
+        if (!seed) {
+                gcry_randomize(iseed, FSPRG_RECOMMENDED_SEEDLEN, GCRY_STRONG_RANDOM);
+                seed = iseed;
+                seedlen = FSPRG_RECOMMENDED_SEEDLEN;
+        }
+
+        p = genprime3mod4(secpar / 2, seed, seedlen, RND_GEN_P);
+        q = genprime3mod4(secpar / 2, seed, seedlen, RND_GEN_Q);
+
+        if (msk) {
+                store_secpar(msk + 0, secpar);
+                mpi_export(msk + 2 + 0 * (secpar / 2) / 8, (secpar / 2) / 8, p);
+                mpi_export(msk + 2 + 1 * (secpar / 2) / 8, (secpar / 2) / 8, q);
+        }
+
+        if (mpk) {
+                n = gcry_mpi_new(0);
+                gcry_mpi_mul(n, p, q);
+                assert(gcry_mpi_get_nbits(n) == secpar);
+
+                store_secpar(mpk + 0, secpar);
+                mpi_export(mpk + 2, secpar / 8, n);
+
+                gcry_mpi_release(n);
+        }
+
+        gcry_mpi_release(p);
+        gcry_mpi_release(q);
+}
+
+void FSPRG_GenState0(void *state, const void *mpk, const void *seed, size_t seedlen) {
+        gcry_mpi_t n, x;
+        uint16_t secpar;
+
+        initialize_libgcrypt();
+
+        secpar = read_secpar(mpk + 0);
+        n = mpi_import(mpk + 2, secpar / 8);
+        x = gensquare(n, seed, seedlen, RND_GEN_X, secpar);
+
+        memcpy(state, mpk, 2 + secpar / 8);
+        mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, x);
+        memset(state + 2 + 2 * secpar / 8, 0, 8);
+
+        gcry_mpi_release(n);
+        gcry_mpi_release(x);
+}
+
+void FSPRG_Evolve(void *state) {
+        gcry_mpi_t n, x;
+        uint16_t secpar;
+        uint64_t epoch;
+
+        initialize_libgcrypt();
+
+        secpar = read_secpar(state + 0);
+        n = mpi_import(state + 2 + 0 * secpar / 8, secpar / 8);
+        x = mpi_import(state + 2 + 1 * secpar / 8, secpar / 8);
+        epoch = uint64_import(state + 2 + 2 * secpar / 8, 8);
+
+        gcry_mpi_mulm(x, x, x, n);
+        epoch++;
+
+        mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, x);
+        uint64_export(state + 2 + 2 * secpar / 8, 8, epoch);
+
+        gcry_mpi_release(n);
+        gcry_mpi_release(x);
+}
+
+uint64_t FSPRG_GetEpoch(const void *state) {
+        uint16_t secpar;
+        secpar = read_secpar(state + 0);
+        return uint64_import(state + 2 + 2 * secpar / 8, 8);
+}
+
+void FSPRG_Seek(void *state, uint64_t epoch, const void *msk, const void *seed, size_t seedlen) {
+        gcry_mpi_t p, q, n, x, xp, xq, kp, kq, xm;
+        uint16_t secpar;
+
+        initialize_libgcrypt();
+
+        secpar = read_secpar(msk + 0);
+        p  = mpi_import(msk + 2 + 0 * (secpar / 2) / 8, (secpar / 2) / 8);
+        q  = mpi_import(msk + 2 + 1 * (secpar / 2) / 8, (secpar / 2) / 8);
+
+        n = gcry_mpi_new(0);
+        gcry_mpi_mul(n, p, q);
+
+        x = gensquare(n, seed, seedlen, RND_GEN_X, secpar);
+        CRT_decompose(&xp, &xq, x, p, q); /* split (mod n) into (mod p) and (mod q) using CRT */
+
+        kp = twopowmodphi(epoch, p); /* compute 2^epoch (mod phi(p)) */
+        kq = twopowmodphi(epoch, q); /* compute 2^epoch (mod phi(q)) */
+
+        gcry_mpi_powm(xp, xp, kp, p); /* compute x^(2^epoch) (mod p) */
+        gcry_mpi_powm(xq, xq, kq, q); /* compute x^(2^epoch) (mod q) */
+
+        CRT_compose(&xm, xp, xq, p, q); /* combine (mod p) and (mod q) to (mod n) using CRT */
+
+        store_secpar(state + 0, secpar);
+        mpi_export(state + 2 + 0 * secpar / 8, secpar / 8, n);
+        mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, xm);
+        uint64_export(state + 2 + 2 * secpar / 8, 8, epoch);
+
+        gcry_mpi_release(p);
+        gcry_mpi_release(q);
+        gcry_mpi_release(n);
+        gcry_mpi_release(x);
+        gcry_mpi_release(xp);
+        gcry_mpi_release(xq);
+        gcry_mpi_release(kp);
+        gcry_mpi_release(kq);
+        gcry_mpi_release(xm);
+}
+
+void FSPRG_GetKey(const void *state, void *key, size_t keylen, uint32_t idx) {
+        uint16_t secpar;
+
+        initialize_libgcrypt();
+
+        secpar = read_secpar(state + 0);
+        det_randomize(key, keylen, state + 2, 2 * secpar / 8 + 8, idx);
+}
diff --git a/src/journal/fsprg.h b/src/journal/fsprg.h
new file mode 100644
index 0000000000..306ef18d73
--- /dev/null
+++ b/src/journal/fsprg.h
@@ -0,0 +1,64 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#ifndef __fsprgh__
+#define __fsprgh__
+
+/*
+ * fsprg v0.1  -  (seekable) forward-secure pseudorandom generator
+ * Copyright (C) 2012 B. Poettering
+ * Contact: fsprg@point-at-infinity.org
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301  USA
+ *
+ */
+
+#include <sys/types.h>
+#include <inttypes.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define FSPRG_RECOMMENDED_SECPAR 1536
+#define FSPRG_RECOMMENDED_SEEDLEN (96/8)
+
+size_t FSPRG_mskinbytes(unsigned secpar);
+size_t FSPRG_mpkinbytes(unsigned secpar);
+size_t FSPRG_stateinbytes(unsigned secpar);
+
+/* Setup msk and mpk. Providing seed != NULL makes this algorithm deterministic. */
+void FSPRG_GenMK(void *msk, void *mpk, const void *seed, size_t seedlen, unsigned secpar);
+
+/* Initialize state deterministically in dependence on seed. */
+/* Note: in case one wants to run only one GenState0 per GenMK it is safe to use
+   the same seed for both GenMK and GenState0.
+*/
+void FSPRG_GenState0(void *state, const void *mpk, const void *seed, size_t seedlen);
+
+void FSPRG_Evolve(void *state);
+
+uint64_t FSPRG_GetEpoch(const void *state);
+
+/* Seek to any arbitrary state (by providing msk together with seed from GenState0). */
+void FSPRG_Seek(void *state, uint64_t epoch, const void *msk, const void *seed, size_t seedlen);
+
+void FSPRG_GetKey(const void *state, void *key, size_t keylen, uint32_t idx);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/src/journal/journal-def.h b/src/journal/journal-def.h
index 096dd8ed83..af22e17822 100644
--- a/src/journal/journal-def.h
+++ b/src/journal/journal-def.h
@@ -37,11 +37,13 @@ typedef struct FieldObject FieldObject;
 typedef struct EntryObject EntryObject;
 typedef struct HashTableObject HashTableObject;
 typedef struct EntryArrayObject EntryArrayObject;
-typedef struct SignatureObject SignatureObject;
+typedef struct TagObject TagObject;
 
 typedef struct EntryItem EntryItem;
 typedef struct HashItem HashItem;
 
+typedef struct FSPRGHeader FSPRGHeader;
+
 /* Object types */
 enum {
         OBJECT_UNUSED,
@@ -51,7 +53,7 @@ enum {
         OBJECT_DATA_HASH_TABLE,
         OBJECT_FIELD_HASH_TABLE,
         OBJECT_ENTRY_ARRAY,
-        OBJECT_SIGNATURE,
+        OBJECT_TAG,
         _OBJECT_TYPE_MAX
 };
 
@@ -84,7 +86,6 @@ _packed_ struct FieldObject {
         le64_t hash;
         le64_t next_hash_offset;
         le64_t head_data_offset;
-        le64_t tail_data_offset;
         uint8_t payload[];
 };
 
@@ -119,12 +120,11 @@ _packed_ struct EntryArrayObject {
         le64_t items[];
 };
 
-#define SIGNATURE_LENGTH 160
+#define TAG_LENGTH (256/8)
 
-_packed_ struct SignatureObject {
+_packed_ struct TagObject {
         ObjectHeader object;
-        le64_t from;
-        uint8_t signature[SIGNATURE_LENGTH];
+        uint8_t tag[TAG_LENGTH]; /* SHA-256 HMAC */
 };
 
 union Object {
@@ -134,7 +134,7 @@ union Object {
         EntryObject entry;
         HashTableObject hash_table;
         EntryArrayObject entry_array;
-        SignatureObject signature;
+        TagObject tag;
 };
 
 enum {
@@ -149,17 +149,19 @@ enum {
 };
 
 enum {
-        HEADER_COMPATIBLE_SIGNED = 1
+        HEADER_COMPATIBLE_AUTHENTICATED = 1
 };
 
+#define HEADER_SIGNATURE ((char[]) { 'L', 'P', 'K', 'S', 'H', 'H', 'R', 'H' })
+
 _packed_ struct Header {
         uint8_t signature[8]; /* "LPKSHHRH" */
-        uint32_t compatible_flags;
-        uint32_t incompatible_flags;
+        le32_t compatible_flags;
+        le32_t incompatible_flags;
         uint8_t state;
         uint8_t reserved[7];
         sd_id128_t file_id;
-        sd_id128_t machine_id; /* last writer */
+        sd_id128_t machine_id;
         sd_id128_t boot_id;    /* last writer */
         sd_id128_t seqnum_id;
         le64_t header_size;
@@ -181,3 +183,19 @@ _packed_ struct Header {
         le64_t n_data;
         le64_t n_fields;
 };
+
+#define FSPRG_HEADER_SIGNATURE ((char[]) { 'K', 'S', 'H', 'H', 'R', 'H', 'L', 'P' })
+
+_packed_ struct FSPRGHeader {
+        uint8_t signature[8]; /* "KSHHRHLP" */
+        le32_t compatible_flags;
+        le32_t incompatible_flags;
+        sd_id128_t machine_id;
+        sd_id128_t boot_id;    /* last writer */
+        le64_t header_size;
+        le64_t fsprg_start_usec;
+        le64_t fsprg_interval_usec;
+        le16_t secpar;
+        le16_t reserved[3];
+        le64_t state_size;
+};
diff --git a/src/journal/journal-file.c b/src/journal/journal-file.c
index 718dc5d6ea..0e4889378c 100644
--- a/src/journal/journal-file.c
+++ b/src/journal/journal-file.c
@@ -31,6 +31,7 @@
 #include "journal-file.h"
 #include "lookup3.h"
 #include "compress.h"
+#include "fsprg.h"
 
 #define DEFAULT_DATA_HASH_TABLE_SIZE (2047ULL*sizeof(HashItem))
 #define DEFAULT_FIELD_HASH_TABLE_SIZE (333ULL*sizeof(HashItem))
@@ -66,13 +67,21 @@
 #define JOURNAL_HEADER_CONTAINS(h, field) \
         (le64toh((h)->header_size) >= offsetof(Header, field) + sizeof((h)->field))
 
-static const char signature[] = { 'L', 'P', 'K', 'S', 'H', 'H', 'R', 'H' };
+static int journal_file_maybe_append_tag(JournalFile *f, uint64_t realtime);
 
 void journal_file_close(JournalFile *f) {
         int t;
 
         assert(f);
 
+        /* Sync everything to disk, before we mark the file offline */
+        for (t = 0; t < _WINDOW_MAX; t++)
+                if (f->windows[t].ptr)
+                        munmap(f->windows[t].ptr, f->windows[t].size);
+
+        if (f->writable && f->fd >= 0)
+                fdatasync(f->fd);
+
         if (f->header) {
                 /* Mark the file offline. Don't override the archived state if it already is set */
                 if (f->writable && f->header->state == STATE_ONLINE)
@@ -81,10 +90,6 @@ void journal_file_close(JournalFile *f) {
                 munmap(f->header, PAGE_ALIGN(sizeof(Header)));
         }
 
-        for (t = 0; t < _WINDOW_MAX; t++)
-                if (f->windows[t].ptr)
-                        munmap(f->windows[t].ptr, f->windows[t].size);
-
         if (f->fd >= 0)
                 close_nointr_nofail(f->fd);
 
@@ -94,6 +99,14 @@ void journal_file_close(JournalFile *f) {
         free(f->compress_buffer);
 #endif
 
+#ifdef HAVE_GCRYPT
+        if (f->fsprg_header)
+                munmap(f->fsprg_header, PAGE_ALIGN(f->fsprg_size));
+
+        if (f->hmac)
+                gcry_md_close(f->hmac);
+#endif
+
         free(f);
 }
 
@@ -105,9 +118,15 @@ static int journal_file_init_header(JournalFile *f, JournalFile *template) {
         assert(f);
 
         zero(h);
-        memcpy(h.signature, signature, 8);
+        memcpy(h.signature, HEADER_SIGNATURE, 8);
         h.header_size = htole64(ALIGN64(sizeof(h)));
 
+        h.incompatible_flags =
+                htole32(f->compress ? HEADER_INCOMPATIBLE_COMPRESSED : 0);
+
+        h.compatible_flags =
+                htole32(f->authenticate ? HEADER_COMPATIBLE_AUTHENTICATED : 0);
+
         r = sd_id128_randomize(&h.file_id);
         if (r < 0)
                 return r;
@@ -149,7 +168,9 @@ static int journal_file_refresh_header(JournalFile *f) {
 
         f->header->state = STATE_ONLINE;
 
-        __sync_synchronize();
+        /* Sync the online state to disk */
+        msync(f->header, PAGE_ALIGN(sizeof(Header)), MS_SYNC);
+        fdatasync(f->fd);
 
         return 0;
 }
@@ -157,17 +178,31 @@ static int journal_file_refresh_header(JournalFile *f) {
 static int journal_file_verify_header(JournalFile *f) {
         assert(f);
 
-        if (memcmp(f->header, signature, 8))
+        if (memcmp(f->header->signature, HEADER_SIGNATURE, 8))
                 return -EBADMSG;
 
+        /* In both read and write mode we refuse to open files with
+         * incompatible flags we don't know */
 #ifdef HAVE_XZ
-        if ((le64toh(f->header->incompatible_flags) & ~HEADER_INCOMPATIBLE_COMPRESSED) != 0)
+        if ((le32toh(f->header->incompatible_flags) & ~HEADER_INCOMPATIBLE_COMPRESSED) != 0)
                 return -EPROTONOSUPPORT;
 #else
         if (f->header->incompatible_flags != 0)
                 return -EPROTONOSUPPORT;
 #endif
 
+        /* When open for writing we refuse to open files with
+         * compatible flags, too */
+        if (f->writable) {
+#ifdef HAVE_GCRYPT
+                if ((le32toh(f->header->compatible_flags) & ~HEADER_COMPATIBLE_AUTHENTICATED) != 0)
+                        return -EPROTONOSUPPORT;
+#else
+                if (f->header->compatible_flags != 0)
+                        return -EPROTONOSUPPORT;
+#endif
+        }
+
         /* The first addition was n_data, so check that we are at least this large */
         if (le64toh(f->header->header_size) < HEADER_SIZE_MIN)
                 return -EBADMSG;
@@ -200,6 +235,9 @@ static int journal_file_verify_header(JournalFile *f) {
                 }
         }
 
+        f->compress = !!(le32toh(f->header->incompatible_flags) & HEADER_INCOMPATIBLE_COMPRESSED);
+        f->authenticate = !!(le32toh(f->header->compatible_flags) & HEADER_COMPATIBLE_AUTHENTICATED);
+
         return 0;
 }
 
@@ -781,8 +819,6 @@ static int journal_file_append_data(
                         o->object.size = htole64(offsetof(Object, data.payload) + rsize);
                         o->object.flags |= OBJECT_COMPRESSED;
 
-                        f->header->incompatible_flags = htole32(le32toh(f->header->incompatible_flags) | HEADER_INCOMPATIBLE_COMPRESSED);
-
                         log_debug("Compressed data object %lu -> %lu", (unsigned long) size, (unsigned long) rsize);
                 }
         }
@@ -1057,6 +1093,10 @@ int journal_file_append_entry(JournalFile *f, const dual_timestamp *ts, const st
             ts->monotonic < le64toh(f->header->tail_entry_monotonic))
                 return -EINVAL;
 
+        r = journal_file_maybe_append_tag(f, ts->realtime);
+        if (r < 0)
+                return r;
+
         /* alloca() can't take 0, hence let's allocate at least one */
         items = alloca(sizeof(EntryItem) * MAX(1, n_iovec));
 
@@ -1832,6 +1872,394 @@ int journal_file_move_to_entry_by_realtime_for_data(
                                              ret, offset, NULL);
 }
 
+static void *fsprg_state(JournalFile *f) {
+        uint64_t a, b;
+        assert(f);
+
+        if (!f->authenticate)
+                return NULL;
+
+        a = le64toh(f->fsprg_header->header_size);
+        b = le64toh(f->fsprg_header->state_size);
+
+        if (a + b > f->fsprg_size)
+                return NULL;
+
+        return (uint8_t*) f->fsprg_header + a;
+}
+
+static int journal_file_append_tag(JournalFile *f) {
+        Object *o;
+        uint64_t p;
+        int r;
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        if (!f->hmac_running)
+                return 0;
+
+        log_debug("Writing tag for epoch %llu\n", (unsigned long long) FSPRG_GetEpoch(fsprg_state(f)));
+
+        assert(f->hmac);
+
+        r = journal_file_append_object(f, OBJECT_TAG, sizeof(struct TagObject), &o, &p);
+        if (r < 0)
+                return r;
+
+        /* Get the HMAC tag and store it in the object */
+        memcpy(o->tag.tag, gcry_md_read(f->hmac, 0), TAG_LENGTH);
+        f->hmac_running = false;
+
+        return 0;
+}
+
+static int journal_file_hmac_start(JournalFile *f) {
+        uint8_t key[256 / 8]; /* Let's pass 256 bit from FSPRG to HMAC */
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        if (f->hmac_running)
+                return 0;
+
+        /* Prepare HMAC for next cycle */
+        gcry_md_reset(f->hmac);
+        FSPRG_GetKey(fsprg_state(f), key, sizeof(key), 0);
+        gcry_md_setkey(f->hmac, key, sizeof(key));
+
+        f->hmac_running = true;
+
+        return 0;
+}
+
+static int journal_file_get_epoch(JournalFile *f, uint64_t realtime, uint64_t *epoch) {
+        uint64_t t;
+
+        assert(f);
+        assert(epoch);
+        assert(f->authenticate);
+
+        if (le64toh(f->fsprg_header->fsprg_start_usec) == 0 ||
+            le64toh(f->fsprg_header->fsprg_interval_usec) == 0)
+                return -ENOTSUP;
+
+        if (realtime < le64toh(f->fsprg_header->fsprg_start_usec))
+                return -ESTALE;
+
+        t = realtime - le64toh(f->fsprg_header->fsprg_start_usec);
+        t = t / le64toh(f->fsprg_header->fsprg_interval_usec);
+
+        *epoch = t;
+        return 0;
+}
+
+static int journal_file_need_evolve(JournalFile *f, uint64_t realtime) {
+        uint64_t goal, epoch;
+        int r;
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        r = journal_file_get_epoch(f, realtime, &goal);
+        if (r < 0)
+                return r;
+
+        epoch = FSPRG_GetEpoch(fsprg_state(f));
+        if (epoch > goal)
+                return -ESTALE;
+
+        return epoch != goal;
+}
+
+static int journal_file_evolve(JournalFile *f, uint64_t realtime) {
+        uint64_t goal, epoch;
+        int r;
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        r = journal_file_get_epoch(f, realtime, &goal);
+        if (r < 0)
+                return r;
+
+        epoch = FSPRG_GetEpoch(fsprg_state(f));
+        if (epoch < goal)
+                log_debug("Evolving FSPRG key from epoch %llu to %llu.", (unsigned long long) epoch, (unsigned long long) goal);
+
+        for (;;) {
+                if (epoch > goal)
+                        return -ESTALE;
+                if (epoch == goal)
+                        return 0;
+
+                FSPRG_Evolve(fsprg_state(f));
+                epoch = FSPRG_GetEpoch(fsprg_state(f));
+        }
+}
+
+static int journal_file_maybe_append_tag(JournalFile *f, uint64_t realtime) {
+        int r;
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        r = journal_file_need_evolve(f, realtime);
+        if (r <= 0)
+                return 0;
+
+        r = journal_file_append_tag(f);
+        if (r < 0)
+                return r;
+
+        r = journal_file_evolve(f, realtime);
+        if (r < 0)
+                return r;
+
+        r = journal_file_hmac_start(f);
+        if (r < 0)
+                return r;
+
+        return 0;
+}
+
+static int journal_file_hmac_put_object(JournalFile *f, int type, uint64_t p) {
+        int r;
+        Object *o;
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        r = journal_file_hmac_start(f);
+        if (r < 0)
+                return r;
+
+        r = journal_file_move_to_object(f, type, p, &o);
+        if (r < 0)
+                return r;
+
+        gcry_md_write(f->hmac, o, offsetof(ObjectHeader, payload));
+
+        switch (o->object.type) {
+
+        case OBJECT_DATA:
+                /* All but: entry_array_offset, n_entries are mutable */
+                gcry_md_write(f->hmac, &o->data.hash, offsetof(DataObject, entry_array_offset) - offsetof(DataObject, hash));
+                gcry_md_write(f->hmac, o->data.payload, le64toh(o->object.size) - offsetof(DataObject, payload));
+                break;
+
+        case OBJECT_ENTRY:
+                /* All */
+                gcry_md_write(f->hmac, &o->entry.seqnum, le64toh(o->object.size) - offsetof(EntryObject, seqnum));
+                break;
+
+        case OBJECT_FIELD_HASH_TABLE:
+        case OBJECT_DATA_HASH_TABLE:
+        case OBJECT_ENTRY_ARRAY:
+                /* Nothing: everything is mutable */
+                break;
+
+        case OBJECT_TAG:
+                /* All */
+                gcry_md_write(f->hmac, o->tag.tag, le64toh(o->object.size) - offsetof(TagObject, tag));
+                break;
+
+        default:
+                return -EINVAL;
+        }
+
+        return 0;
+}
+
+static int journal_file_hmac_put_header(JournalFile *f) {
+        int r;
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        r = journal_file_hmac_start(f);
+        if (r < 0)
+                return r;
+
+        /* All but state+reserved, boot_id, arena_size,
+         * tail_object_offset, n_objects, n_entries, tail_seqnum,
+         * head_entry_realtime, tail_entry_realtime,
+         * tail_entry_monotonic, n_data, n_fields, header_tag */
+
+        gcry_md_write(f->hmac, f->header->signature, offsetof(Header, state) - offsetof(Header, signature));
+        gcry_md_write(f->hmac, &f->header->file_id, offsetof(Header, boot_id) - offsetof(Header, file_id));
+        gcry_md_write(f->hmac, &f->header->seqnum_id, offsetof(Header, arena_size) - offsetof(Header, seqnum_id));
+        gcry_md_write(f->hmac, &f->header->data_hash_table_offset, offsetof(Header, tail_object_offset) - offsetof(Header, data_hash_table_offset));
+        gcry_md_write(f->hmac, &f->header->head_seqnum, offsetof(Header, head_entry_realtime) - offsetof(Header, head_seqnum));
+
+        return 0;
+}
+
+static int journal_file_load_fsprg(JournalFile *f) {
+        int r, fd = -1;
+        char *p = NULL;
+        struct stat st;
+        FSPRGHeader *m = NULL;
+        sd_id128_t machine;
+
+        assert(f);
+
+        if (!f->authenticate)
+                return 0;
+
+        r = sd_id128_get_machine(&machine);
+        if (r < 0)
+                return r;
+
+        if (asprintf(&p, "/var/log/journal/" SD_ID128_FORMAT_STR "/fsprg",
+                     SD_ID128_FORMAT_VAL(machine)) < 0)
+                return -ENOMEM;
+
+        fd = open(p, O_RDWR|O_CLOEXEC|O_NOCTTY, 0600);
+        if (fd < 0) {
+                log_error("Failed to open %s: %m", p);
+                r = -errno;
+                goto finish;
+        }
+
+        if (fstat(fd, &st) < 0) {
+                r = -errno;
+                goto finish;
+        }
+
+        if (st.st_size < (off_t) sizeof(FSPRGHeader)) {
+                r = -ENODATA;
+                goto finish;
+        }
+
+        m = mmap(NULL, PAGE_ALIGN(sizeof(FSPRGHeader)), PROT_READ, MAP_SHARED, fd, 0);
+        if (m == MAP_FAILED) {
+                m = NULL;
+                r = -errno;
+                goto finish;
+        }
+
+        if (memcmp(m->signature, FSPRG_HEADER_SIGNATURE, 8) != 0) {
+                r = -EBADMSG;
+                goto finish;
+        }
+
+        if (m->incompatible_flags != 0) {
+                r = -EPROTONOSUPPORT;
+                goto finish;
+        }
+
+        if (le64toh(m->header_size) < sizeof(FSPRGHeader)) {
+                r = -EBADMSG;
+                goto finish;
+        }
+
+        if (le64toh(m->state_size) != FSPRG_stateinbytes(m->secpar)) {
+                r = -EBADMSG;
+                goto finish;
+        }
+
+        f->fsprg_size = le64toh(m->header_size) + le64toh(m->state_size);
+        if ((uint64_t) st.st_size < f->fsprg_size) {
+                r = -ENODATA;
+                goto finish;
+        }
+
+        if (!sd_id128_equal(machine, m->machine_id)) {
+                r = -EHOSTDOWN;
+                goto finish;
+        }
+
+        if (le64toh(m->fsprg_start_usec) <= 0 ||
+            le64toh(m->fsprg_interval_usec) <= 0) {
+                r = -EBADMSG;
+                goto finish;
+        }
+
+        f->fsprg_header = mmap(NULL, PAGE_ALIGN(f->fsprg_size), PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
+        if (f->fsprg_header == MAP_FAILED) {
+                f->fsprg_header = NULL;
+                r = -errno;
+                goto finish;
+        }
+
+        r = 0;
+
+finish:
+        if (m)
+                munmap(m, PAGE_ALIGN(sizeof(FSPRGHeader)));
+
+        if (fd >= 0)
+                close_nointr_nofail(fd);
+
+        free(p);
+        return r;
+}
+
+static int journal_file_setup_hmac(JournalFile *f) {
+        gcry_error_t e;
+
+        if (!f->authenticate)
+                return 0;
+
+        e = gcry_md_open(&f->hmac, GCRY_MD_SHA256, GCRY_MD_FLAG_HMAC);
+        if (e != 0)
+                return -ENOTSUP;
+
+        return 0;
+}
+
+static int journal_file_append_first_tag(JournalFile *f) {
+        int r;
+        uint64_t p;
+
+        if (!f->authenticate)
+                return 0;
+
+        log_debug("Calculating first tag...");
+
+        r = journal_file_hmac_put_header(f);
+        if (r < 0)
+                return r;
+
+        p = le64toh(f->header->field_hash_table_offset);
+        if (p < offsetof(Object, hash_table.items))
+                return -EINVAL;
+        p -= offsetof(Object, hash_table.items);
+
+        r = journal_file_hmac_put_object(f, OBJECT_FIELD_HASH_TABLE, p);
+        if (r < 0)
+                return r;
+
+        p = le64toh(f->header->data_hash_table_offset);
+        if (p < offsetof(Object, hash_table.items))
+                return -EINVAL;
+        p -= offsetof(Object, hash_table.items);
+
+        r = journal_file_hmac_put_object(f, OBJECT_DATA_HASH_TABLE, p);
+        if (r < 0)
+                return r;
+
+        r = journal_file_append_tag(f);
+        if (r < 0)
+                return r;
+
+        return 0;
+}
+
 void journal_file_dump(JournalFile *f) {
         Object *o;
         int r;
@@ -1876,8 +2304,8 @@ void journal_file_dump(JournalFile *f) {
                         printf("Type: OBJECT_ENTRY_ARRAY\n");
                         break;
 
-                case OBJECT_SIGNATURE:
-                        printf("Type: OBJECT_SIGNATURE\n");
+                case OBJECT_TAG:
+                        printf("Type: OBJECT_TAG\n");
                         break;
                 }
 
@@ -1928,8 +2356,8 @@ void journal_file_print_header(JournalFile *f) {
                f->header->state == STATE_OFFLINE ? "offline" :
                f->header->state == STATE_ONLINE ? "online" :
                f->header->state == STATE_ARCHIVED ? "archived" : "unknown",
-               (f->header->compatible_flags & HEADER_COMPATIBLE_SIGNED) ? " SIGNED" : "",
-               (f->header->compatible_flags & ~HEADER_COMPATIBLE_SIGNED) ? " ???" : "",
+               (f->header->compatible_flags & HEADER_COMPATIBLE_AUTHENTICATED) ? " AUTHENTICATED" : "",
+               (f->header->compatible_flags & ~HEADER_COMPATIBLE_AUTHENTICATED) ? " ???" : "",
                (f->header->incompatible_flags & HEADER_INCOMPATIBLE_COMPRESSED) ? " COMPRESSED" : "",
                (f->header->incompatible_flags & ~HEADER_INCOMPATIBLE_COMPRESSED) ? " ???" : "",
                (unsigned long long) le64toh(f->header->header_size),
@@ -1961,6 +2389,8 @@ int journal_file_open(
                 const char *fname,
                 int flags,
                 mode_t mode,
+                bool compress,
+                bool authenticate,
                 JournalMetrics *metrics,
                 JournalFile *template,
                 JournalFile **ret) {
@@ -1983,13 +2413,13 @@ int journal_file_open(
                 return -ENOMEM;
 
         f->fd = -1;
-        f->flags = flags;
         f->mode = mode;
-        f->writable = (flags & O_ACCMODE) != O_RDONLY;
-        f->prot = prot_from_flags(flags);
 
-        if (template)
-                f->compress = template->compress;
+        f->flags = flags;
+        f->prot = prot_from_flags(flags);
+        f->writable = (flags & O_ACCMODE) != O_RDONLY;
+        f->compress = compress;
+        f->authenticate = authenticate;
 
         f->path = strdup(fname);
         if (!f->path) {
@@ -2011,6 +2441,12 @@ int journal_file_open(
         if (f->last_stat.st_size == 0 && f->writable) {
                 newly_created = true;
 
+                /* Try to load the FSPRG state, and if we can't, then
+                 * just don't do authentication */
+                r = journal_file_load_fsprg(f);
+                if (r < 0)
+                        f->authenticate = false;
+
                 r = journal_file_init_header(f, template);
                 if (r < 0)
                         goto fail;
@@ -2037,6 +2473,10 @@ int journal_file_open(
                 r = journal_file_verify_header(f);
                 if (r < 0)
                         goto fail;
+
+                r = journal_file_load_fsprg(f);
+                if (r < 0)
+                        goto fail;
         }
 
         if (f->writable) {
@@ -2049,10 +2489,13 @@ int journal_file_open(
                 r = journal_file_refresh_header(f);
                 if (r < 0)
                         goto fail;
+
+                r = journal_file_setup_hmac(f);
+                if (r < 0)
+                        goto fail;
         }
 
         if (newly_created) {
-
                 r = journal_file_setup_field_hash_table(f);
                 if (r < 0)
                         goto fail;
@@ -2060,6 +2503,10 @@ int journal_file_open(
                 r = journal_file_setup_data_hash_table(f);
                 if (r < 0)
                         goto fail;
+
+                r = journal_file_append_first_tag(f);
+                if (r < 0)
+                        goto fail;
         }
 
         r = journal_file_map_field_hash_table(f);
@@ -2081,7 +2528,7 @@ fail:
         return r;
 }
 
-int journal_file_rotate(JournalFile **f) {
+int journal_file_rotate(JournalFile **f, bool compress, bool authenticate) {
         char *p;
         size_t l;
         JournalFile *old_file, *new_file = NULL;
@@ -2120,7 +2567,7 @@ int journal_file_rotate(JournalFile **f) {
 
         old_file->header->state = STATE_ARCHIVED;
 
-        r = journal_file_open(old_file->path, old_file->flags, old_file->mode, NULL, old_file, &new_file);
+        r = journal_file_open(old_file->path, old_file->flags, old_file->mode, compress, authenticate, NULL, old_file, &new_file);
         journal_file_close(old_file);
 
         *f = new_file;
@@ -2131,6 +2578,8 @@ int journal_file_open_reliably(
                 const char *fname,
                 int flags,
                 mode_t mode,
+                bool compress,
+                bool authenticate,
                 JournalMetrics *metrics,
                 JournalFile *template,
                 JournalFile **ret) {
@@ -2139,7 +2588,7 @@ int journal_file_open_reliably(
         size_t l;
         char *p;
 
-        r = journal_file_open(fname, flags, mode, metrics, template, ret);
+        r = journal_file_open(fname, flags, mode, compress, authenticate, metrics, template, ret);
         if (r != -EBADMSG && /* corrupted */
             r != -ENODATA && /* truncated */
             r != -EHOSTDOWN && /* other machine */
@@ -2154,6 +2603,9 @@ int journal_file_open_reliably(
         if (!(flags & O_CREAT))
                 return r;
 
+        if (!endswith(fname, ".journal"))
+                return r;
+
         /* The file is corrupted. Rotate it away and try it again (but only once) */
 
         l = strlen(fname);
@@ -2170,7 +2622,7 @@ int journal_file_open_reliably(
 
         log_warning("File %s corrupted or uncleanly shut down, renaming and replacing.", fname);
 
-        return journal_file_open(fname, flags, mode, metrics, template, ret);
+        return journal_file_open(fname, flags, mode, compress, authenticate, metrics, template, ret);
 }
 
 struct vacuum_info {
diff --git a/src/journal/journal-file.h b/src/journal/journal-file.h
index eed49e062f..25d972040c 100644
--- a/src/journal/journal-file.h
+++ b/src/journal/journal-file.h
@@ -23,6 +23,10 @@
 
 #include <inttypes.h>
 
+#ifdef HAVE_GCRYPT
+#include <gcrypt.h>
+#endif
+
 #include <systemd/sd-id128.h>
 
 #include "sparse-endian.h"
@@ -42,7 +46,7 @@ enum {
         WINDOW_DATA_HASH_TABLE = OBJECT_DATA_HASH_TABLE,
         WINDOW_FIELD_HASH_TABLE = OBJECT_FIELD_HASH_TABLE,
         WINDOW_ENTRY_ARRAY = OBJECT_ENTRY_ARRAY,
-        WINDOW_SIGNATURE = OBJECT_SIGNATURE,
+        WINDOW_TAG = OBJECT_TAG,
         WINDOW_HEADER,
         _WINDOW_MAX
 };
@@ -59,9 +63,13 @@ typedef struct JournalFile {
         char *path;
         struct stat last_stat;
         mode_t mode;
+
         int flags;
         int prot;
         bool writable;
+        bool compress;
+        bool authenticate;
+
         bool tail_entry_monotonic_valid;
 
         Header *header;
@@ -74,12 +82,18 @@ typedef struct JournalFile {
 
         JournalMetrics metrics;
 
-        bool compress;
-
 #ifdef HAVE_XZ
         void *compress_buffer;
         uint64_t compress_buffer_size;
 #endif
+
+#ifdef HAVE_GCRYPT
+        gcry_md_hd_t hmac;
+        bool hmac_running;
+
+        FSPRGHeader *fsprg_header;
+        size_t fsprg_size;
+#endif
 } JournalFile;
 
 typedef enum direction {
@@ -91,6 +105,8 @@ int journal_file_open(
                 const char *fname,
                 int flags,
                 mode_t mode,
+                bool compress,
+                bool authenticate,
                 JournalMetrics *metrics,
                 JournalFile *template,
                 JournalFile **ret);
@@ -101,6 +117,8 @@ int journal_file_open_reliably(
                 const char *fname,
                 int flags,
                 mode_t mode,
+                bool compress,
+                bool authenticate,
                 JournalMetrics *metrics,
                 JournalFile *template,
                 JournalFile **ret);
@@ -134,7 +152,7 @@ int journal_file_copy_entry(JournalFile *from, JournalFile *to, Object *o, uint6
 void journal_file_dump(JournalFile *f);
 void journal_file_print_header(JournalFile *f);
 
-int journal_file_rotate(JournalFile **f);
+int journal_file_rotate(JournalFile **f, bool compress, bool authenticate);
 
 int journal_directory_vacuum(const char *directory, uint64_t max_use, uint64_t min_free);
 
diff --git a/src/journal/journalctl.c b/src/journal/journalctl.c
index 62bb904dbe..138bf09d48 100644
--- a/src/journal/journalctl.c
+++ b/src/journal/journalctl.c
@@ -41,6 +41,10 @@
 #include "logs-show.h"
 #include "strv.h"
 #include "journal-internal.h"
+#include "fsprg.h"
+#include "journal-def.h"
+
+#define DEFAULT_FSPRG_INTERVAL_USEC (15*USEC_PER_MINUTE)
 
 static OutputMode arg_output = OUTPUT_SHORT;
 static bool arg_follow = false;
@@ -48,14 +52,19 @@ static bool arg_show_all = false;
 static bool arg_no_pager = false;
 static int arg_lines = -1;
 static bool arg_no_tail = false;
-static bool arg_new_id128 = false;
-static bool arg_print_header = false;
 static bool arg_quiet = false;
 static bool arg_local = false;
 static bool arg_this_boot = false;
 static const char *arg_directory = NULL;
 static int arg_priorities = 0xFF;
 
+static enum {
+        ACTION_SHOW,
+        ACTION_NEW_ID128,
+        ACTION_PRINT_HEADER,
+        ACTION_SETUP_KEYS
+} arg_action = ACTION_SHOW;
+
 static int help(void) {
 
         printf("%s [OPTIONS...] [MATCH]\n\n"
@@ -73,9 +82,11 @@ static int help(void) {
                "  -l --local          Only local entries\n"
                "  -b --this-boot      Show data only from current boot\n"
                "  -D --directory=PATH Show journal files from directory\n"
-               "  -p --priority=RANGE Show only messages within the specified priority range\n"
+               "  -p --priority=RANGE Show only messages within the specified priority range\n\n"
+               "Commands:\n"
+               "     --new-id128      Generate a new 128 Bit id\n"
                "     --header         Show journal header information\n"
-               "     --new-id128      Generate a new 128 Bit id\n",
+               "     --setup-keys     Generate new FSPRG key pair\n",
                program_invocation_short_name);
 
         return 0;
@@ -88,7 +99,8 @@ static int parse_argv(int argc, char *argv[]) {
                 ARG_NO_PAGER,
                 ARG_NO_TAIL,
                 ARG_NEW_ID128,
-                ARG_HEADER
+                ARG_HEADER,
+                ARG_SETUP_KEYS
         };
 
         static const struct option options[] = {
@@ -107,6 +119,7 @@ static int parse_argv(int argc, char *argv[]) {
                 { "directory", required_argument, NULL, 'D'           },
                 { "header",    no_argument,       NULL, ARG_HEADER    },
                 { "priority",  no_argument,       NULL, 'p'           },
+                { "setup-keys",no_argument,       NULL, ARG_SETUP_KEYS},
                 { NULL,        0,                 NULL, 0             }
         };
 
@@ -163,7 +176,7 @@ static int parse_argv(int argc, char *argv[]) {
                         break;
 
                 case ARG_NEW_ID128:
-                        arg_new_id128 = true;
+                        arg_action = ACTION_NEW_ID128;
                         break;
 
                 case 'q':
@@ -183,7 +196,11 @@ static int parse_argv(int argc, char *argv[]) {
                         break;
 
                 case ARG_HEADER:
-                        arg_print_header = true;
+                        arg_action = ACTION_PRINT_HEADER;
+                        break;
+
+                case ARG_SETUP_KEYS:
+                        arg_action = ACTION_SETUP_KEYS;
                         break;
 
                 case 'p': {
@@ -400,6 +417,161 @@ static int add_priorities(sd_journal *j) {
         return 0;
 }
 
+static int setup_keys(void) {
+#ifdef HAVE_GCRYPT
+        size_t mpk_size, seed_size, state_size, i;
+        uint8_t *mpk, *seed, *state;
+        ssize_t l;
+        int fd = -1, r;
+        sd_id128_t machine, boot;
+        char *p = NULL, *k = NULL;
+        struct FSPRGHeader h;
+        uint64_t n, interval;
+
+        r = sd_id128_get_machine(&machine);
+        if (r < 0) {
+                log_error("Failed to get machine ID: %s", strerror(-r));
+                return r;
+        }
+
+        r = sd_id128_get_boot(&boot);
+        if (r < 0) {
+                log_error("Failed to get boot ID: %s", strerror(-r));
+                return r;
+        }
+
+        if (asprintf(&p, "/var/log/journal/" SD_ID128_FORMAT_STR "/fsprg",
+                     SD_ID128_FORMAT_VAL(machine)) < 0)
+                return log_oom();
+
+        if (access(p, F_OK) >= 0) {
+                log_error("Evolving key file %s exists already.", p);
+                r = -EEXIST;
+                goto finish;
+        }
+
+        if (asprintf(&k, "/var/log/journal/" SD_ID128_FORMAT_STR "/fsprg.tmp.XXXXXX",
+                     SD_ID128_FORMAT_VAL(machine)) < 0) {
+                r = log_oom();
+                goto finish;
+        }
+
+        mpk_size = FSPRG_mskinbytes(FSPRG_RECOMMENDED_SECPAR);
+        mpk = alloca(mpk_size);
+
+        seed_size = FSPRG_RECOMMENDED_SEEDLEN;
+        seed = alloca(seed_size);
+
+        state_size = FSPRG_stateinbytes(FSPRG_RECOMMENDED_SECPAR);
+        state = alloca(state_size);
+
+        fd = open("/dev/random", O_RDONLY|O_CLOEXEC|O_NOCTTY);
+        if (fd < 0) {
+                log_error("Failed to open /dev/random: %m");
+                r = -errno;
+                goto finish;
+        }
+
+        log_info("Generating seed...");
+        l = loop_read(fd, seed, seed_size, true);
+        if (l < 0 || (size_t) l != seed_size) {
+                log_error("Failed to read random seed: %s", strerror(EIO));
+                r = -EIO;
+                goto finish;
+        }
+
+        log_info("Generating key pair...");
+        FSPRG_GenMK(NULL, mpk, seed, seed_size, FSPRG_RECOMMENDED_SECPAR);
+
+        log_info("Generating evolving key...");
+        FSPRG_GenState0(state, mpk, seed, seed_size);
+
+        interval = DEFAULT_FSPRG_INTERVAL_USEC;
+        n = now(CLOCK_REALTIME);
+        n /= interval;
+
+        close_nointr_nofail(fd);
+        fd = mkostemp(k, O_WRONLY|O_CLOEXEC|O_NOCTTY);
+        if (fd < 0) {
+                log_error("Failed to open %s: %m", k);
+                r = -errno;
+                goto finish;
+        }
+
+        zero(h);
+        memcpy(h.signature, "KSHHRHLP", 8);
+        h.machine_id = machine;
+        h.boot_id = boot;
+        h.header_size = htole64(sizeof(h));
+        h.fsprg_start_usec = htole64(n * interval);
+        h.fsprg_interval_usec = htole64(interval);
+        h.secpar = htole16(FSPRG_RECOMMENDED_SECPAR);
+        h.state_size = htole64(state_size);
+
+        l = loop_write(fd, &h, sizeof(h), false);
+        if (l < 0 || (size_t) l != sizeof(h)) {
+                log_error("Failed to write header: %s", strerror(EIO));
+                r = -EIO;
+                goto finish;
+        }
+
+        l = loop_write(fd, state, state_size, false);
+        if (l < 0 || (size_t) l != state_size) {
+                log_error("Failed to write state: %s", strerror(EIO));
+                r = -EIO;
+                goto finish;
+        }
+
+        if (link(k, p) < 0) {
+                log_error("Failed to link file: %m");
+                r = -errno;
+                goto finish;
+        }
+
+        if (isatty(STDOUT_FILENO)) {
+                fprintf(stderr,
+                        "\n"
+                        "The new key pair has been generated. The evolving key has been written to the\n"
+                        "following file. It will be used to protect local journal files. This file does\n"
+                        "not need to be kept secret. It should not be used on multiple hosts.\n"
+                        "\n"
+                        "\t%s\n"
+                        "\n"
+                        "Please write down the following " ANSI_HIGHLIGHT_ON "secret" ANSI_HIGHLIGHT_OFF " seed value. It should not be stored\n"
+                        "locally on disk, and may be used to verify journal files from this host.\n"
+                        "\n\t" ANSI_HIGHLIGHT_RED_ON, p);
+                fflush(stderr);
+        }
+        for (i = 0; i < seed_size; i++) {
+                if (i > 0 && i % 3 == 0)
+                        putchar('-');
+                printf("%02x", ((uint8_t*) seed)[i]);
+        }
+
+        printf("/%llx-%llx\n", (unsigned long long) n, (unsigned long long) interval);
+
+        if (isatty(STDOUT_FILENO))
+                fputs(ANSI_HIGHLIGHT_OFF "\n", stderr);
+
+        r = 0;
+
+finish:
+        if (fd >= 0)
+                close_nointr_nofail(fd);
+
+        if (k) {
+                unlink(k);
+                free(k);
+        }
+
+        free(p);
+
+        return r;
+#else
+        log_error("Forward-secure journal verification not available.");
+#endif
+}
+
 int main(int argc, char *argv[]) {
         int r;
         sd_journal *j = NULL;
@@ -416,11 +588,16 @@ int main(int argc, char *argv[]) {
         if (r <= 0)
                 goto finish;
 
-        if (arg_new_id128) {
+        if (arg_action == ACTION_NEW_ID128) {
                 r = generate_new_id128();
                 goto finish;
         }
 
+        if (arg_action == ACTION_SETUP_KEYS) {
+                r = setup_keys();
+                goto finish;
+        }
+
 #ifdef HAVE_ACL
         if (!arg_quiet && geteuid() != 0 && in_group("adm") <= 0)
                 log_warning("Showing user generated messages only. Users in the group 'adm' can see all messages. Pass -q to turn this message off.");
@@ -436,7 +613,7 @@ int main(int argc, char *argv[]) {
                 goto finish;
         }
 
-        if (arg_print_header) {
+        if (arg_action == ACTION_PRINT_HEADER) {
                 journal_print_header(j);
                 r = 0;
                 goto finish;
diff --git a/src/journal/journald.c b/src/journal/journald.c
index 7c89689e84..8c41d9bab1 100644
--- a/src/journal/journald.c
+++ b/src/journal/journald.c
@@ -281,7 +281,6 @@ static JournalFile* find_journal(Server *s, uid_t uid) {
         char *p;
         int r;
         JournalFile *f;
-        char ids[33];
         sd_id128_t machine;
 
         assert(s);
@@ -305,7 +304,8 @@ static JournalFile* find_journal(Server *s, uid_t uid) {
         if (f)
                 return f;
 
-        if (asprintf(&p, "/var/log/journal/%s/user-%lu.journal", sd_id128_to_string(machine, ids), (unsigned long) uid) < 0)
+        if (asprintf(&p, "/var/log/journal/" SD_ID128_FORMAT_STR "/user-%lu.journal",
+                     SD_ID128_FORMAT_VAL(machine), (unsigned long) uid) < 0)
                 return s->system_journal;
 
         while (hashmap_size(s->user_journals) >= USER_JOURNALS_MAX) {
@@ -315,7 +315,7 @@ static JournalFile* find_journal(Server *s, uid_t uid) {
                 journal_file_close(f);
         }
 
-        r = journal_file_open_reliably(p, O_RDWR|O_CREAT, 0640, &s->system_metrics, s->system_journal, &f);
+        r = journal_file_open_reliably(p, O_RDWR|O_CREAT, 0640, s->compress, false, &s->system_metrics, s->system_journal, &f);
         free(p);
 
         if (r < 0)
@@ -341,7 +341,7 @@ static void server_rotate(Server *s) {
         log_info("Rotating...");
 
         if (s->runtime_journal) {
-                r = journal_file_rotate(&s->runtime_journal);
+                r = journal_file_rotate(&s->runtime_journal, s->compress, false);
                 if (r < 0)
                         if (s->runtime_journal)
                                 log_error("Failed to rotate %s: %s", s->runtime_journal->path, strerror(-r));
@@ -352,7 +352,7 @@ static void server_rotate(Server *s) {
         }
 
         if (s->system_journal) {
-                r = journal_file_rotate(&s->system_journal);
+                r = journal_file_rotate(&s->system_journal, s->compress, true);
                 if (r < 0)
                         if (s->system_journal)
                                 log_error("Failed to rotate %s: %s", s->system_journal->path, strerror(-r));
@@ -364,7 +364,7 @@ static void server_rotate(Server *s) {
         }
 
         HASHMAP_FOREACH_KEY(f, k, s->user_journals, i) {
-                r = journal_file_rotate(&f);
+                r = journal_file_rotate(&f, s->compress, false);
                 if (r < 0)
                         if (f->path)
                                 log_error("Failed to rotate %s: %s", f->path, strerror(-r));
@@ -2006,14 +2006,12 @@ static int system_journal_open(Server *s) {
                 if (!fn)
                         return -ENOMEM;
 
-                r = journal_file_open_reliably(fn, O_RDWR|O_CREAT, 0640, &s->system_metrics, NULL, &s->system_journal);
+                r = journal_file_open_reliably(fn, O_RDWR|O_CREAT, 0640, s->compress, true, &s->system_metrics, NULL, &s->system_journal);
                 free(fn);
 
-                if (r >= 0) {
-                        s->system_journal->compress = s->compress;
-
+                if (r >= 0)
                         server_fix_perms(s, s->system_journal, 0);
-                } else if (r < 0) {
+                else if (r < 0) {
 
                         if (r != -ENOENT && r != -EROFS)
                                 log_warning("Failed to open system journal: %s", strerror(-r));
@@ -2035,7 +2033,7 @@ static int system_journal_open(Server *s) {
                          * if it already exists, so that we can flush
                          * it into the system journal */
 
-                        r = journal_file_open(fn, O_RDWR, 0640, &s->runtime_metrics, NULL, &s->runtime_journal);
+                        r = journal_file_open(fn, O_RDWR, 0640, s->compress, false, &s->runtime_metrics, NULL, &s->runtime_journal);
                         free(fn);
 
                         if (r < 0) {
@@ -2051,7 +2049,7 @@ static int system_journal_open(Server *s) {
                          * it if necessary. */
 
                         (void) mkdir_parents(fn, 0755);
-                        r = journal_file_open_reliably(fn, O_RDWR|O_CREAT, 0640, &s->runtime_metrics, NULL, &s->runtime_journal);
+                        r = journal_file_open_reliably(fn, O_RDWR|O_CREAT, 0640, s->compress, false, &s->runtime_metrics, NULL, &s->runtime_journal);
                         free(fn);
 
                         if (r < 0) {
@@ -2060,11 +2058,8 @@ static int system_journal_open(Server *s) {
                         }
                 }
 
-                if (s->runtime_journal) {
-                        s->runtime_journal->compress = s->compress;
-
+                if (s->runtime_journal)
                         server_fix_perms(s, s->runtime_journal, 0);
-                }
         }
 
         return r;
diff --git a/src/journal/sd-journal.c b/src/journal/sd-journal.c
index 33686ed2b2..359a7cac3e 100644
--- a/src/journal/sd-journal.c
+++ b/src/journal/sd-journal.c
@@ -1118,7 +1118,7 @@ static int add_file(sd_journal *j, const char *prefix, const char *filename) {
                 return 0;
         }
 
-        r = journal_file_open(path, O_RDONLY, 0, NULL, NULL, &f);
+        r = journal_file_open(path, O_RDONLY, 0, false, false, NULL, NULL, &f);
         free(path);
 
         if (r < 0) {
diff --git a/src/journal/test-journal-stream.c b/src/journal/test-journal-stream.c
index fd448cb1ef..0925995fca 100644
--- a/src/journal/test-journal-stream.c
+++ b/src/journal/test-journal-stream.c
@@ -79,9 +79,9 @@ int main(int argc, char *argv[]) {
         assert_se(mkdtemp(t));
         assert_se(chdir(t) >= 0);
 
-        assert_se(journal_file_open("one.journal", O_RDWR|O_CREAT, 0666, NULL, NULL, &one) == 0);
-        assert_se(journal_file_open("two.journal", O_RDWR|O_CREAT, 0666, NULL, NULL, &two) == 0);
-        assert_se(journal_file_open("three.journal", O_RDWR|O_CREAT, 0666, NULL, NULL, &three) == 0);
+        assert_se(journal_file_open("one.journal", O_RDWR|O_CREAT, 0666, true, false, NULL, NULL, &one) == 0);
+        assert_se(journal_file_open("two.journal", O_RDWR|O_CREAT, 0666, true, false, NULL, NULL, &two) == 0);
+        assert_se(journal_file_open("three.journal", O_RDWR|O_CREAT, 0666, true, false, NULL, NULL, &three) == 0);
 
         for (i = 0; i < N_ENTRIES; i++) {
                 char *p, *q;
diff --git a/src/journal/test-journal.c b/src/journal/test-journal.c
index ca3b4741f5..7b1583c889 100644
--- a/src/journal/test-journal.c
+++ b/src/journal/test-journal.c
@@ -41,7 +41,7 @@ int main(int argc, char *argv[]) {
         assert_se(mkdtemp(t));
         assert_se(chdir(t) >= 0);
 
-        assert_se(journal_file_open("test.journal", O_RDWR|O_CREAT, 0666, NULL, NULL, &f) == 0);
+        assert_se(journal_file_open("test.journal", O_RDWR|O_CREAT, 0666, true, false, NULL, NULL, &f) == 0);
 
         dual_timestamp_get(&ts);
 
@@ -109,8 +109,8 @@ int main(int argc, char *argv[]) {
 
         assert(journal_file_move_to_entry_by_seqnum(f, 10, DIRECTION_DOWN, &o, NULL) == 0);
 
-        journal_file_rotate(&f);
-        journal_file_rotate(&f);
+        journal_file_rotate(&f, true, true);
+        journal_file_rotate(&f, true, true);
 
         journal_file_close(f);