Try   HackMD

ECIES Encryption

Elliptic Curve Integrated Encryption Scheme (ECIES) is a hybrid encryption scheme that combines ECC-based asymmetric cryptography with symmetric ciphers to provide data encryption.

Table of Contents

Objectives

  1. Production grade implementation of ECIES encryption scheme with ZKP in Circom.
  2. Optimize implementation to reduce the number of constraints and the number of operations.

Problem

Overview

Information sharing is a fundamental aspect of any digital communication system. In a decentralized environment, where the data is shared between two or more parties, the data must be encrypted to ensure privacy and security. Symmetric encryption is a common method used to encrypt data, but the challenge arises when the key exchange is to be done securely. Sharing encrypted data on-chain or in a public channel via symmetric encryption with a ledger of interactions necessitates multiple steps by both parties involved.

Steps Involved in Symmetric Encryption

  1. Consensus on Public Parameters:

    • The anticipating recipient, say Bob, and the motivated sender, say Alice agree upon the public parameters.

  2. Private Parameters Generation:

    • Alice and Bob individually generate their private parameters and their corresponding public representations.

  3. Public Parameters Sharing:

    • They share their generated public parameters.

  4. Shared Secret Key Calculation:

    • They then calculate a shared secret key, which they can use for further communication with encrypted messages via a public channel.

  5. Message Encryption:

    • Alice encrypts the message using the shared secret key.

  6. Message Decryption:

    • Bob decrypts the message using the shared secret key.

Example Implementation

A prominent example of this implementation is the Elliptic Curve Diffie-Hellman (ECDH) key exchange protocol. More details about ECDH can be found here.

Challenges

  1. This multi-step process creates a delayed and undesirably iterative setup, leading to a tiring user experience (UX). In dynamic environments such as a marketplace, where a potential buyer must perform this setup with various probable sellers in an auction bidding or in a First-Come-First-Serve (FCFS) system where the first seller is incentivized with a reward, the data exchange process needs significant optimization.
  2. In situations where the seller is rewarded for the information creates a deadlock where in the buyer is not willing to pay until the information is shared, and the seller is not willing to share the information until the payment is made.

Solution

Overview

The Elliptic Curve Integrated Encryption Scheme (ECIES) is a hybrid encryption scheme that combines ECC-based asymmetric cryptography with symmetric ciphers to provide data encryption by EC public key and a secret random scalar and decryption by the corresponding EC private key and the public representation of the secret random scalar. This combined with a MAC (Message Authentication Code) ensures the integrity of the encrypted message.

  • Use of ECIES eliminates the need for a separate key exchange protocol and needs only the public key of the recipient to encrypt the message.

Zero-Knowledge Proof

Usage with the ECIES encryption scheme can be further optimized by using a zero-knowledge proof (ZKP) to prove that the message encrypted by the sender is indeed encrypted using the recipient's public key and that the message pre deterministically confines to the requirements of the recipient. This proof can be used to incentivize the sender to share the encrypted message with the recipient without revealing the message content.

Thus the ECIES encryption scheme with ZKP can be used to :

  1. Minimize number of interactions between the sender and the recipient.
  2. Solve the deadlock problem mentioned above because the proof of encryption combined with the proof that the encrypted message is within the constraints of the recipient can be used to instantly incentivize the sender for sharing the encrypted message with the recipient without revealing the message content.

Example Use Cases

Note : The following use cases are examples and can be extended to various scenarios where secure data exchange is required in a decentralized environment. It is important to thoroughly study and implement these use cases with the necessary security measures to ensure a robust and reliable system.

  1. Vanity Address Generation:

    • In this system a user can request a vanity address by providing pubkey of a randomly generate private key scalar (k1).
    • In a decentralized environment, a miner can generate a vanity address using homomorphic addition and share the generated half of the private key with the user who requested the address. The user can then use the shared half of the private key to generate the full private key and the corresponding public key.
    • The proof can also be colluded with the proof that the hash of homomorphic addition of the public key provided by user and the public key the shared half of the private key matches the requested vanity address.
    • ECIES will be used to share the half of the private key and the proof will be used to prove the above mentioned points.
    • The decryption of the message will be done by the user via the private key (k1).
    • This ensure that the generated vanity address will be hidden from everyone except for the miner and the user who requested the address.

  2. Private Auction Bidding:

    • In a decentralized auction system a creator will create an order with an amount of token X and constraints for the bid for token Y, now a bidder can encrypt the bid amount using the seller's public key and share the encrypted bid with the signature or secret that can used the spend the bidder funds. The bidder can then prove the following:

      1. The encrypted bid is indeed encrypted using the seller's public key
      2. The message consist of the bid amount and the signature.
      3. The bid amount is within the range of the auction.
      4. The signature or secret shared with the seller is indeed the secret that can be used to spend the bidder funds.
      5. Check if the bidder has enough funds in Y to pay the bid amount in the predefined contract address and are locked for enough time.

    • The auction creator can then decrypt the message and use the signature to spend the funds from the contract address whenever they want from a different address.

  3. Private bridge between two chains:

    • In this use case a user as a creator can provide a pubkey for destination chain, required amount on destination chain and lock the amount they are ready to provide on the source chain. A bidder will now create an deposit in a contract or a script with requested amount that can only be spent by the user on the destination chain. For complete anonymity the bidder will create a combined pubkey on destination chain that will allow only the creator to find the private key for the combined pubkey and spend those funds. The bidder will now prove the following:
      1. The encrypted message is indeed encrypted using the creator's public key.
      2. Message consist of the transaction hash and private key used to generate the pubkey on destination chain using the creator's pubkey.
      3. The outputs or amount in the transaction hash is within the range of the requested amount.
      4. The transaction hash is indeed a valid transaction hash on the destination chain.
      5. The private key generated will correspond to one half of the combined pubkey on the destination chain.
    • The creator can now decrypt the message , generate the required private key, find address on destination chain and spend the funds.

ECIES Encryption Scheme Specifications

Inputs:

  • Random scalar r
  • PublicKey: The recipient's public key
  • Message: The plaintext message to be encrypted
  • S1: Shared information for key derivation (optional)
  • S2: Shared information for MAC (optional)
    Output:
  • Ciphertext: The encrypted message

Algorithm :

  1. Generate or use a random scalar r.
  2. Compute the public key on chosen curve R = r * G, where G is the base point of that elliptic curve.
  3. Compute the shared secret:
    S = r * publicKey
  4. Derive the symmetric encryption key (Ke) and MAC key (Km):
    (Ke, Km) = KDF(S || s1)
    Where KDF is a key derivation function (e.g., HKDF with SHA-256)
  5. Encrypt the message:
    c = SymmetricEncrypt(Ke, message)
    Where SymmetricEncrypt is a symmetric encryption algorithm (e.g., AES-CTR)
  6. Compute the MAC:
    t = HMAC(Km, c || s2)
    Where HMAC is implemented as described in the specification
  7. Construct the ciphertext:
    ciphertext = R || c || t
  8. Return the ciphertext

Note: The HMAC implementation should follow the algorithm provided in the specification,
using SHA-256 as the underlying hash function.

Other Components required for ECIES Encryption

The ECIES encryption scheme requires the following components to be implemented:

  1. HMAC (Hash Message Authentication Code) with SHA-256
  2. Key Derivation Function (KDF) - HKDF with SHA-256
  3. AES-CTR (Advanced Encryption Standard in Counter mode)
  4. Elliptic Curve Cryptography (ECC) Operations - Scalar multiplication.

HMAC

The current implementation is for HMAC with the SHA-256 hashing algorithm.

Inputs

  1. Message
  2. Secret

Outputs

HMAC-SHA256 (64 bytes)

Algorithm

  1. Check the block size of the hashing algorithm, i.e., SHA-256, which is 32 bytes.
  2. If the secret is less than the block size, pad it with zeros as key
  3. else hash the secret using SHA-256. i.e sha256(key)
  4. Calculate the innerkey and outerkey
    const outerPadding = 0x5c;
    const innerPadding = 0x36;
    innerkey = key[i] ^ innerPadding // entire key
    outerkey = key[i] ^ outerPadding
  1. Calculate HMAC with hash algorithm:
    innerHash = sha256 (innerKey || message)
    hmacSha256 = sha256 (outerkey ||  innerHash)
  1. output => hmacSha256

Js Implementation for Hmac

const crypto = require("crypto");

function hmacSha256(key, message) {
  const blockSize = 64; // SHA-256 block size in bytes
  const outerPadding = 0x5c;
  const innerPadding = 0x36;

  // If the key is longer than the block size, hash it
  if (Buffer.from(key).length > blockSize) {
    key = crypto.createHash("sha256").update(key).digest();
  }

  // If the key is shorter, pad it with zeros
  let keyBuffer = Buffer.from(key);
  if (keyBuffer.length < blockSize) {
    const newBuffer = Buffer.alloc(blockSize);
    keyBuffer.copy(newBuffer);
    keyBuffer = newBuffer;
  }

  const innerKey = Buffer.alloc(blockSize);
  const outerKey = Buffer.alloc(blockSize);

  for (let i = 0; i < blockSize; i++) {
    innerKey[i] = keyBuffer[i] ^ innerPadding;
    outerKey[i] = keyBuffer[i] ^ outerPadding;
  }

  const innerHash = crypto
    .createHash("sha256")
    .update(innerKey)
    .update(message)
    .digest();

  const hmac = crypto
    .createHash("sha256")
    .update(outerKey)
    .update(innerHash)
    .digest("hex");

  return hmac;
}

Key Derivation Function (KDF)

HKDF (HMAC-based Key Derivation Function) is used to derive the symmetric encryption key and MAC key from the shared secret. The HKDF algorithm is used to expand the shared secret into two keys, one for encryption and the other for the MAC.

  • HKDF uses an Extract-then-Expand approach, where the input key material is first extracted using a pseudorandom function (PRF) and then expanded using a key derivation function to generate L bit of output keying material.

  • It generates a pseudorandom key from an input secret and a salt and then uses that key to derive additional keys.

Algorithm

Given the following inputs:

XTS : Extractor salt
SKM : Shared key material
CTXinfo : Context information
L : Output length

The HKDF algorithm is defined as follows:

HKDF(XTS,SKM,CTXinfo,L) = K(1)∥K(2)∥...∥K(t)

where the values K(i) are defined as follows:

PRK = HMAC(XTS, SKM)
K(1) = HMAC(PRK, CTXinfo ∥ 0),
K(i+1) = HMAC(PRK, K(i)∥CTXinfo∥i), 1≤i<t,

where k is the length of the output of the HMAC function, and t is the number of iterations required to generate the required output length L, i.e.,

t = ⌈L/k⌉

and the value K(t) is truncated to its first d = L mod k bits the counter i is non-wrapping and of a given fixed size, e.g., a single byte. Note that the length of the HMAC output is the same as its key length and therefore the scheme is well defined.

In our case we will use key derivation function to derive the symmetric encryption key and MAC key from the shared secret.

Security Considerations

  • The HKDF algorithm is considered less secure than its competitors, such as PBKDF2, due to its reliance on HMAC as the underlying primitive. However, it is still considered secure for many applications.
  • The major concern according to our research is the reuse of the same secret key multiple times, which can lead to key recovery attacks. Therefore the circuits using HKDF should also give out a nullifier output that prevents a prover from using the same secret key twice.
  • Nullifier output can be generated by hashing the random scalar r.

Future scope

  • The HKDF algorithm will be replaced with more secure key derivation functions like Argon2 or scrypt if potential issue are raised.

AES

AES with CTR mode will be used to encrypt the message using the key generated from the KDE function.

Read more about AES here := FIPS 197.

Simple Rust implementation of AES can be found here := tinyaes

Crema Labs has implemented a generic AES encryption circuit in Circom. The circuit is designed to be generic and can be used for any key size (128, 192, 256 bits) and block size (128 bits). The circuit strictly follows the AES standard mentioned in the FIPS 197 document. Can be found aes-circom.The package also provides the ctr mode of operation for AES encryption.

Elliptic Curve Cryptography (ECC) Operations

ECC operations are used to generate the public key and shared secret in the ECIES encryption scheme. The scalar multiplication operation is used to generate the public key from the private key and the shared secret from the private key and the recipient's public key.

We will be using the secp256k1 elliptic curve for ECC operations. The implementation of ECC operations can be found here.

Future scope

  • We also plan on adding support to all the following standards:
var (
	ECIES_AES128_SHA256 = &ECIESParams{
		Hash:      sha256.New,
		hashAlgo:  crypto.SHA256,
		KeyLen:    16,
	}

	ECIES_AES192_SHA384 = &ECIESParams{
		Hash:      sha512.New384,
		hashAlgo:  crypto.SHA384,
		KeyLen:    24,
	}

	ECIES_AES256_SHA512 = &ECIESParams{
		Hash:      sha512.New,
		hashAlgo:  crypto.SHA512,
		KeyLen:    32,
	}
)

var paramsFromCurve = map[elliptic.Curve]*ECIESParams{
	ethcrypto.S256(): ECIES_AES128_SHA256,
	elliptic.P256():  ECIES_AES128_SHA256,
	elliptic.P384():  ECIES_AES192_SHA384,
	elliptic.P521():  ECIES_AES256_SHA512,
}

Timeline

Week 1

Task Description Time
Research Research on ECIES encryption scheme , its components and potential use cases 2 days
Research Enhance understanding of KDF functions and potential issues raised regarding HKDF in the past. 1 day
Refactor Refactor our AES implementation to be more suited for ECIES. 1 days
Testing Add more tests for the AES implementation according to NIST test vectors. 1 day
Documentation Update the documentation with the new changes. 1 day

Week 2

Task Description Time
Implementation Implement HMAC with SHA-256 1 day
Testing Testing HMAC with SHA-256 with NIST test vectors 1 day
Implementation Implement HKDF with SHA-256 1 day
Testing Testing HKDF with SHA-256 1 day
Testing Test ECC operations for secp256k1 and secp256r1 2 days

Week 3

Task Description Time
Implementation Implement ECIES encryption scheme 1 days
Testing Testing ECIES encryption scheme 1 days
Implementation Implement HMAC and HKDF for all key lengths 2 day
Testing Testing HMAC and HKDF for all key lengths 1 day
Documentation Update the documentation with the new changes. 1 day
Testing Integration testing of all components 1 day

Week 4

This is an optional week for any additional testing or for implementing ; Zanity, A ZK Vanity Address Generator which would serve as a practical example and a use case for ECIES encryption scheme.

Zanity will contain the following components:

1. Backend Cuircuits

  1. A circuit that generates a vanity address using homomorphic addition.
  2. A circuit that generates a proof that the generated vanity address is indeed generated using the recipient's public key.
  3. A circuit that generates a proof that the generated vanity address is within the constraints of the recipient.
  4. ECIES will be used to encrypt and verify the miner's half of the private key.

2. Frontend

  1. The frontend will allow the user to request a vanity address.
  2. The frontend will also use one time wallet to generate a random private key which will enhance the UX and security.
  3. The frontend will decrypt the message and generate the full private key.

3. Miner

  1. The miner will generate the vanity address using homomorphic addition.
  2. The miner will share the half of the private key with the user via the the generated proof for the vanity address and correct encryption the mined half of the private key.
  3. The miner will be benchmarked for the time taken to generate the vanity address and the time taken to generate the proof.
  4. The miner will go against the benchmarks provided by Profanity2 from 1inch.

About Us

This is Work is done by yash, ayman, vikas from crema-labs

Last changed by 
 
Vikas Rushi
0
335

Read more

PDF Parsing Feasibility study in Zero-Knowledge Proofs

PDF Parser in ZK!?

Feb 24, 2025
Turbo Module Update

Turbo Module Update

Jan 24, 2025
UPI Research

This is internal docu

Jan 16, 2025
Notes of Oblivious Transfer Protocol From Homomorphic Encryption Schemes

Oblivious Transfer Protocol From Homomorphic Encryption Schemes

Dec 13, 2024
Read more from Vikas Rushi
Published on HackMD