sqleet v1 cryptosystem

[resilar]

A draft of a new cryptosystem for the next major version of sqleet. The current sqleet v0 cryptosystem is strong and the goal here is improving secure enclave (TPM/SGX/TrustZone) support and reducing the security impact of nonce reuse attacks (if an attacker obtains a Poly1305 key of a single page somehow, the attacker can reuse the key and nonce to compromise the security of other database pages). See the description below for more details.

Warning: This is just a draft and subject to changes. I'm still in the process of getting the proposed cryptosystem verified by "professionals", so some changes are expected.

Encrypted database page format
==============================

  +----------------------------------------+----------------+----------------+
  | (n - 16 - 16)-byte Page data           | 16-byte Nonce  | 16-byte MAC    |
  +----------------------------------------+----------------+----------------+
     n = 512, 1024, 2048, ... (page size)  | Reserved area of 32 bytes total |

Old implementation (sqleet v0.x.y)
==================================

Basic ChaCha20-Poly1305 AEAD construction using 128-bit random nonces.
Basically, RFC7539 with minor modifications

    EncryptV0(K, PageNumber, Data[0..n])
    |
    | Nonce = randombytes(16)
    | K_stream, K_mac = ChaCha20(K, Nonce ^ PageNumber)
    | Data ^= ChaCha20(K_stream, (Nonce ^ PageNumber) + 1)
    | MAC = Poly1305(K_mac, Data || Nonce)
    |
    | Output: (Data[0..n-32], Nonce[0..16], MAC[0..16])

    DecryptV0(K, PageNumber, Data[0..n-32], Nonce[0..16], MAC[0..16])
    |
    | K_stream, K_mac = ChaCha20(K, Nonce ^ PageNumber)
    | Verify MAC = Poly1305(K_mac, Data || Nonce)
    | Data ^= ChaCha20(K_stream, (Nonce ^ PageNumber) + 1)
    |
    | Output: Data[0..n-32]

Run-time cost: (n + 1) × ChaCha20 + n × Poly1305 blocks in total.

List of known (theoretical) issues:

 1. Random nonces allow nonce reuse attacks

    - Preventing nonce reuses is infeasible, in practice, with random nonces.

    - Exploitation can be detected by checking the nonce values of a database
      file. Non-malicious nonces are uniform-randomly distributed.

 2. C implementations of Poly1305/ChaCha20 may leak one-time K_mac & K_stream
    keys onto the stack. ChaCha20(K, Nonce) cannot leak master key K because the
    following ChaCha20(K_stream, ...) overwrites stack memory and registers.

 3. If Poly1305 leaks K_mac (by whatever means; let's say via a side channel,
    bad RNG or direct process memory inspection), then the attacker can generate
    valid Poly1305 MACs for arbitrary messages by reusing the nonce and K_mac.

    - The ability to produce valid MACs allows bit-flipping bits in plaintext
      by changing the corresponding ciphertext ("stream cipher attack").

    - K_mac is not properly page-specific to prevent nonce & K_mac reuse across
      database pages. Let's force page j to reuse a leaked K_mac from page i:

      +----------------------------------------------------------------------+
      | Page i with nonce N:                                                 |
      | K_stream, K_mac = ChaCha20(K, N ^ i)                                 |
      +----------------------------------------------------------------------+
      | Page j with nonce N ^ i ^ j:                                         |
      | K_stream, K_mac = ChaCha20(K, (N ^ i ^ j) ^ j) = ChaCha20(K, N ^ i)  |
      +----------------------------------------------------------------------+

      In other words, the nonce N and K_mac of page i can be reused at page j by
      with the adjusted nonce value N ^ i ^ j. Notice K_stream is reused also.

    - In conclusion, a single *one-time* key K_mac is sufficient to break the
      whole cryptosystem. This is poor design, despite the fact that attacker
      obtaining K_mac is only a theoretical threat and a very unlikely attack
      scenario in practice. Requires Heartbleed type of a information disclosure
      vulnerability but in stack memory (more powerful exploits such as code
      execution exploits can already bypass the encryption by other means).

    - K_stream, if leaked, compromises only the corresponding database page.
      This is correct and expected behavior since *one-time* keys are limited
      and not intended to be powerful enough to break the full cryptosystem.

    - K (master key) leak would be devastating to the cryptosystem, obviously.
      There is nothing we can do about this, given the definition of master key.

  4. ChaCha20 streams of distinct pages overlap (with negligible probability) if
     randomly generated nonces are within distance (page_size / 64) - 1 from
     each other. XOR between the ciphertexts encrypted with the overlapping
     stream segment reveals the XOR of the associated plaintexts, breaking the
     confidentiality of data.

New cryptosystem (sqleet v1.x.y)
================================

ChaCha20-Poly1305 AEAD construction with deterministic nonces. Draft!

    EncryptV1(K, PageNumber, Data[0..n]):
    |
    | K_i, K_j = ChaCha20(K, PageNumber)
    | Hash = Poly1305(K_i, Data)
    | Nonce = Hash ^ randombytes(16)
    | K_stream, K_mac = ChaCha20(K_j, Nonce)
    | Data ^= ChaCha20(K_stream ^ K_i, 0)
    | MAC = Poly1305(K_mac, Hash)
    |
    | Output: (Data[0..n-32], Nonce[0..16], MAC[0..16])

    DecryptV1(K, PageNumber, Data[0..n-32], Nonce[0..16], MAC[0..16])
    |
    | K_i, K_j = ChaCha20(K, PageNumber)
    | K_stream, K_mac = ChaCha20(K_j, Nonce)
    | Data ^= ChaCha20(K_stream ^ K_i, 0)
    | Hash = Poly1305(K_i, Data)
    | Verify MAC = Poly1305(K_mac, Hash)
    |
    | Output: Data[0..n-32]

Run-time cost: (n + 2) × ChaCha20 + (n + 1) × Poly1305 blocks in total.

Improvements:

 1. Page subkeys K_i, K_j allow a secure enclave implementation with SGX/TPM/TZ
    technologies (derive subkeys from K within a hardware-enforced safe space).
    Probably not going to be implemented in sqleet, but a nice option to have.

 2. Deterministic hash-based nonces prevents nonce reuse attacks.

 3. One-time keys K_stream & K_mac are truly one-time and, if leaked, compromise
    only the associated page and nonce/data combination.

 4. C implementations (most likely) do not leak master key or subkeys via stack.
    Subsequent ChaCha20/Poly1305 function calls overwrite secrets spilled to the
    stack before exiting the function. Only K_stream & K_mac can be exposed, but
    they are truly one-time keys and compromise only the current page and data.

 5. Power/EM side-channel resistance (in addition to the usual time and cache
    side-channel resistance). Published side-channel attacks against ChaCha20
    require an attacker-controlled nonce, making ChaCha(K_j, Nonce) vulnerable.
    To mitigate the security impact of leaked K_j, we use K_stream ^ K_i as the
    ChaCha20 encryption key (if the attacker knows K_j, she can also calculate
    K_stream). Power/EM side-channel attacks do not expose K_i because it is
    derived from K with non-attacker-controlled nonce (PageNumber) and never
    used with attacker-controlled nonce.

    Power/EM attacks are not my area of expertise, so the reasoning above may be
    flawed. The biggest assumption is that Poly1305 is secure against power and
    EM side-channel attacks, which is true to my limited understanding.

 5. MAC-then-Encrypt is fine in this particular context.

Disadvantages (in comparison to old version):

 1. Requires additional ChaCha20 and Poly1305 block computations.

 2. Complexity. Ugly. Not battletested nor approved by crypto wizards (yet).

Any feedback is appreciated.

[resilar]

PBKDF2-HMAC-SHA256 will be replaced by Balloon hashing with BLAKE2s or BLAKE3 hash function.

Balloon hashing is a elegant memory-hard key derivation algorithm with the same or superior security properties as Argon2; for example, the memory-hardness of Balloon hashing has been proven while the memory-hardness of Argon2 remains unproven. (Argon2 sucks for multiple other reasons as well...)

[resilar]

    EncryptV1(K, PageNumber, Data[0..n]):
    |
    | K_i, K_j = ChaCha20(K, PageNumber)
    | Hash = Poly1305(K_i, Data)
    | Nonce = Hash ^ randombytes(16)
    | K_stream, K_mac = ChaCha20(K_j, Nonce)
    | Data ^= ChaCha20(K_stream ^ K_i, 0)
    | MAC = Poly1305(K_mac, Hash)
    |
    | Output: (Data[0..n-32], Nonce[0..16], MAC[0..16])

Notice that Hash = Poly1305(K_i, Data) is dangerous because reusing a Poly1305 key for distinct messages leaks the Poly1305 key. With broken RNG, Nonce = Hash ^ randombytes(16) = Hash ^ 0 yields nonce Poly1305(K_i, Data). Therefore, an attacker can recover K_i after observing 2 nonces for the same page assuming a known-plaintext attack.

Fortunately, leaked K_i is not useful to the attacker because ChaCha20(K_stream ^ K_i, 0) XORs K_i with K_stream before use. Leaking K_i is still unacceptable though, because the attacker may be able to reveal K_stream with another attack (e.g., power/EM side-channel attack to find K_j and consequently K_stream).

The problem can be addressed by computing Hash = H(Data) with regular hash function like BLAKE2 or SHA-256. Alternatively, Hash = H(Poly1305(K_i, Data)) can be used as a optimization (Poly1305 is fast). Or simply fix the RNG...

[resilar]

Codec API deprecation and switching to VFS-level encryption makes deterministic counter-based (instead of hash-based) nonces feasible by allowing sqleet to maintain persistent state. I think the proposed v1 crypto should be revised to exploit this fact in order to simplify and improve the crypto, for example and most importantly, by avoiding random number generation.

[utelle]

Using counter-based nonces sounds good, and would allow to get rid of problematic RNG implementations.

BTW, I have now a first implementation of VFS-level encryption ready for testing (see SQLite3 Multiple Ciphers).

[resilar]

Closing this issue. A redesign is needed to fully exploit the new VFS-based architecture.