Discussion: Use in symmetric encryption (section in draft)

[codespree]

Encap results in a 1120 byte ct and a 32 byte ss

Why not use ss as a key for AES 256?

+-------------------------------+----------+----------+-----------------+
| 1120 Bytes                    | 16 Bytes | 16 Bytes | == data size    |
+-------------------------------+----------+----------+-----------------+
| Encap ct                      | Nonce/IV | Tag/MAC  | Encrypted data  |
+-------------------------------+----------+----------+-----------------+
| ct                            | nonce    | tag      | encrypted_data  |
+-------------------------------+----------+----------+-----------------+
|           X-Wing KEM          |              AES-256-GCM              |
+-------------------------------+---------------------------------------+

The following example Python code demonstrates the above:

from cryptography.hazmat.primitives.ciphers.algorithms import AES256
from cryptography.hazmat.primitives.ciphers import Cipher, modes
import os

def encrypt_aes256_gcm(key, plaintext):
    alg = AES256(key)
    # 16 byte random nonce
    nonce = os.urandom(16)
    mode = modes.GCM(nonce)
    cipher = Cipher(alg, mode)
    encryptor = cipher.encryptor()

    ciphertext = encryptor.update(plaintext) + encryptor.finalize()
    return nonce + encryptor.tag + ciphertext

def decrypt_aes256_gcm(key, ciphertext):
    # First 16 bytes are the nonce
    nonce = ciphertext[:16]
    # Next 16 bytes are the tag
    tag = ciphertext[16:32]
    # The rest is the ciphertext
    ciphertext = ciphertext[32:]
    alg = AES256(key)
    mode = modes.GCM(nonce, tag)
    cipher = Cipher(alg, mode)
    decryptor = cipher.decryptor()
    return decryptor.update(ciphertext) + decryptor.finalize()

def encrypt(pk, plaintext):
    (ss, ct) = kem.encap(pk)
    enc = encrypt_aes256_gcm(ss, plaintext)
    payload = ct + enc
    return payload

def decrypt(sk, payload):
    # First 1120 are KEM ct
    ct = payload[:1120]
    enc = payload[1120:]
    ss = kem.decap(sk, ct)
    return decrypt_aes256_gcm(ss, enc)

This closely resembles ECIES:
https://github.com/ecies/py/blob/master/DETAILS.md

[codespree]

We could also (optionally) accept AAD bytes which could be passed through to the AES encrypt/decrypt functions.

[bwesterb]

You're redesigning HPKE.

[codespree]

I want to avoid the context in HPKE.

Furthermore, since the KEM (X-Wing) is already a fixed part of the triple, and ss is 32 bytes, what is the need for the variability of the (KEM, KDF, AAED) triple for simple encryption use-cases?

Like you made a choice of moving to Shake256 as a sensible default, why not make choices on sensible defaults for a simple encryption scheme like ECIES?

I would argue that I am not redesigning HPKE but supporting a more ECIES like scheme.

[codespree]

Do you think there is anything we would lose from security considerations?

ss is already random and the probability of the iv / nonce being the same (independently) is 1/256^16

[codespree]

Even if you would not like to include it in your draft, I would like to have your informed, cryptographic, opinion on whether a simple, stateless scheme such as what I described is Ok or not? From a practical perspective, could we have a stateless scheme that is reasonably secure?

In order to avoid nonce reuse, however, this encryption must be stateful. Each of the setup procedures above produces a role-specific context object that stores the AEAD and secret export parameters. The AEAD parameters consist of:

The AEAD algorithm in use
A secret key
A base nonce base_nonce
A sequence number (initially 0)
The secret export parameters consist of:

The HPKE ciphersuite in use and
An exporter_secret used for the secret export interface (see [Section 5.3](https://datatracker.ietf.org/doc/html/rfc9180#hpke-export))
All these parameters except the AEAD sequence number are constant. The sequence number provides nonce uniqueness: The nonce used for each encryption or decryption operation is the result of XORing base_nonce with the current sequence number, encoded as a big-endian integer of the same length as base_nonce. Implementations MAY use a sequence number that is shorter than the nonce length (padding on the left with zero), but MUST raise an error if the sequence number overflows. The AEAD algorithm produces ciphertext that is Nt bytes longer than the plaintext. Nt = 16 for AEAD algorithms defined in this document.

From RFC 9180.

[codespree]

This is what ChatGPT says:

A quantum computer, using Grover's algorithm (and I'm reading up), would still need:
1 / (2^(16 * 8)) ^ 1/2 operations, which is significantly faster but still infeasible with current or near-future quantum technology, given the enormous number of operations required and the current limitations in maintaining quantum coherence over that many operations.

How hard would it be to find a nonce if the algorithm was stateless and the nonce was random?

The ss in the schemes is also random though encap.

[codespree]

What I'm looking for is a stateless and reasonably secure scheme.

[bwesterb]

How hard would it be to find a nonce if the algorithm was stateless and the nonce was random?

https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits/

[codespree]

Differences Between ECIES and HPKE

1. Encryption Model

• ECIES: ECIES is a hybrid encryption scheme that derives a fresh ephemeral symmetric key for each message.
  The symmetric key is generated from the shared secret established via the elliptic curve Diffie-Hellman (ECDH) operation and typically includes randomness from the ephemeral key pair.

  Since every encryption involves a fresh key, there is no requirement to manage nonces across multiple messages for the same key.

• HPKE: HPKE uses a shared secret (derived from a KEM) to generate keys for use with an AEAD scheme.
  In HPKE, the same derived key is reused across multiple messages in certain contexts (e.g., streaming or sequential encryption), necessitating unique nonces to secure each encryption.

2. Key and Nonce Lifecycle

• ECIES: Each encryption generates a new symmetric key as part of the hybrid scheme, effectively making the nonce redundant because every encryption is independent. The key and nonce are tied to the individual encryption instance.
• HPKE: HPKE often operates in a session-like manner where the same symmetric key (derived from the shared secret) is reused for multiple messages. AEAD encryption requires unique nonces to ensure the security of these repeated operations.

3. Statefulness

• ECIES: Stateless: ECIES does not require maintaining state between encryptions because every encryption operation is independent and fresh.
• HPKE: Stateful in many use cases: By design, HPKE relies on a stateful context to manage the nonce counter for AEAD encryption.

4. Nonce Generation

• ECIES: Nonce uniqueness is implicit because each encryption operation uses a fresh key derived from randomness.
• HPKE: Nonces must be explicitly managed to ensure uniqueness for AEAD schemes when reusing the same key.

Can X-Wing KEM be used in an ECIES like scheme?

The scheme that I am proposing proceeds thus (stateless for every message):

1. Get ss, ct from encap(pk). Here ss is already random.
2. Use a 16 byte random nonce
3. Use key = KDF (how about HkdfWithSha256?) with ikm = ss, salt = nonce and info as an empty string
4. Encrypt with AES256 Gcm using the derived key and nonce to obtain random tag
5. Transmit ct || nonce || tag || encrypted_data as below:

+-------------------------------+----------+----------+-----------------+
| 1120 Bytes                    | 16 Bytes | 16 Bytes | == data size    |
+-------------------------------+----------+----------+-----------------+
| Encap ct                      | Nonce/IV | Tag/MAC  | Encrypted data  |
+-------------------------------+----------+----------+-----------------+
| ct                            | nonce    | tag      | encrypted_data  |
+-------------------------------+----------+----------+-----------------+
|           X-Wing KEM          |              AES-256-GCM              |
+-------------------------------+---------------------------------------+

6. Receive message and split to get ct, nonce, tag
7. Decap ss from ct and sk
8. Repeat step 2 to get key
9. Decrypt using key, nonce, tag

Do you see any potential pitfalls?

ss, ct will never be used more than once for any message, unless ss repeats.

Even if ss repeats, there is still a random 16 byte nonce in the AES encryption portion and in the KDF.

Omitting the KDF

In the above, I also think step 3 can be omitted (?) as ss for X-Wing is already a hash from combiner(). We could use ss directly as the key to AES 256.

This is another difference from HPKE, as HPKE would again apply a KDF to ss.

Advantages over HPKE

1. Stateless means there is no write operation for each encryption.
2. If implemented in hardware, costs are reduced as there is no need for writable storage per transaction (to store a counter).
3. If implemented on a server, there is no need for persistent storage that stores the counter.
4. No need to support multiple (KEM,KDF,AEAD) triples. X-Wing already lends itself naturally to just one triple (X-Wing, IdentityFunction, AES256 GCM).