gerbil-signal

A Gerbil Scheme implementation of the Signal Protocol for end-to-end encrypted messaging.

Implements X3DH key agreement, Double Ratchet message encryption, sender keys for group messaging, sealed sender for anonymous delivery, safety number fingerprints, and all associated protobuf wire formats.

Requirements

• Gerbil Scheme v0.18+
• OpenSSL (libcrypto) development headers and libraries
• A C compiler (gcc/clang) for the FFI module

On Debian/Ubuntu:

sudo apt install libssl-dev

Building

git clone <this-repo> && cd gerbil-signal
make build

Or directly:

gerbil build

Quick Start

Import everything through the top-level module:

(import :signal/src/signal)

Or import individual modules as needed:

(import :signal/src/core/keys
        :signal/src/core/prekey
        :signal/src/session/process
        :signal/src/session/cipher)

Usage

Key Generation

Each user generates a long-term identity key pair (X25519 for DH + Ed25519 for signing), along with pre-keys for asynchronous session setup:

(import :signal/src/signal)

;; Generate identity key pair
(def alice-ikp (generate-identity-key-pair))
(def bob-ikp (generate-identity-key-pair))

;; Generate pre-keys for Bob
(def bob-signed-prekey (generate-signed-prekey 1 bob-ikp))
(def bob-one-time-prekey (generate-prekey 1))

;; Verify signed pre-key
(verify-signed-prekey bob-signed-prekey bob-ikp) ;; => #t

Session Establishment (X3DH)

Alice initiates a session using Bob's published pre-key bundle:

;; Bob publishes a pre-key bundle
(def bundle
  (make-prekey-bundle
   registration-id: 1234
   device-id: 1
   prekey-id: 1
   prekey-public: (ec-key-pair-public-key (prekey-key-pair bob-one-time-prekey))
   signed-prekey-id: 1
   signed-prekey-public: (ec-key-pair-public-key (signed-prekey-key-pair bob-signed-prekey))
   signed-prekey-signature: (signed-prekey-signature bob-signed-prekey)
   identity-key: (identity-key-pair-public-key bob-ikp)
   kyber-prekey-id: #f
   kyber-prekey-public: #f
   kyber-prekey-signature: #f))

;; Alice processes the bundle to create a session
(def alice-session (process-prekey-bundle alice-ikp 5678 bundle))

Encrypting and Decrypting Messages

;; Alice encrypts her first message (automatically wrapped as PreKeySignalMessage)
(let-values (((alice-session-2 wire-msg)
              (session-encrypt-message alice-session alice-ikp
                                      (string->bytes "Hello Bob!"))))

  ;; Bob receives and decrypts the PreKeySignalMessage
  ;; He needs lookup functions for his pre-keys
  (let* ((pk-store  (lambda (id) (and (= id 1) (prekey-key-pair bob-one-time-prekey))))
         (spk-store (lambda (id) (and (= id 1) (signed-prekey-key-pair bob-signed-prekey)))))
    (let-values (((bob-session plaintext)
                  (process-prekey-message bob-ikp 1234 spk-store pk-store wire-msg)))

      (bytes->string plaintext) ;; => "Hello Bob!"

      ;; Bob replies (regular SignalMessage, no pre-key wrapper needed)
      (let-values (((bob-session-2 reply)
                    (session-encrypt bob-session (string->bytes "Hi Alice!"))))

        ;; Alice decrypts the reply
        (let-values (((alice-session-3 reply-plaintext)
                      (session-decrypt alice-session-2 reply)))

          (bytes->string reply-plaintext) ;; => "Hi Alice!"

          ;; Subsequent messages from Alice are also regular SignalMessages
          (let-values (((alice-session-4 msg2)
                        (session-encrypt alice-session-3 (string->bytes "How are you?"))))
            (let-values (((bob-session-3 pt2)
                          (session-decrypt bob-session-2 msg2)))
              (bytes->string pt2))))))) ;; => "How are you?"

Important: Every encrypt/decrypt operation returns an updated session. You must thread the updated session through subsequent calls to maintain ratchet state.

Safety Number Fingerprints

Both parties independently compute the same 60-digit safety number to verify they are communicating with the correct person:

(def fingerprint-alice
  (generate-numeric-fingerprint
   (identity-key-pair-public-key alice-ikp) "+15551234567"
   (identity-key-pair-public-key bob-ikp)   "+15559876543"))

(def fingerprint-bob
  (generate-numeric-fingerprint
   (identity-key-pair-public-key bob-ikp)   "+15559876543"
   (identity-key-pair-public-key alice-ikp) "+15551234567"))

;; Both sides get the same fingerprint
(fingerprints-equal? fingerprint-alice fingerprint-bob) ;; => #t

;; Format for display (12 groups of 5 digits)
(format-fingerprint fingerprint-alice)
;; => "54328 80691 85424 36310 12129 83796 71172 50397 15815 33840 74107 73211"

Protocol Stores

Store interfaces define how keys and sessions are persisted. In-memory implementations are provided for testing:

;; Create in-memory stores
(def id-store   (make-memory-identity-store alice-ikp 5678))
(def pk-store   (make-memory-prekey-store))
(def spk-store  (make-memory-signed-prekey-store))
(def sess-store (make-memory-session-store))
(def sk-store   (make-memory-sender-key-store))

;; Store a pre-key
((prekey-store-store-prekey pk-store) 42 (generate-prekey 42))
((prekey-store-contains-prekey pk-store) 42)   ;; => #t
((prekey-store-remove-prekey pk-store) 42)
((prekey-store-contains-prekey pk-store) 42)   ;; => #f

;; Store a session
(def addr (make-signal-address name: "bob" device-id: 1))
((session-store-store-session sess-store) addr (string->bytes "session-data"))
((session-store-contains-session sess-store) addr) ;; => #t

To implement persistent storage, create your own store structs following the same interface (see src/store/interface.ss for the full type contracts).

Sender Keys (Group Messaging)

Sender keys allow efficient group messaging where the sender encrypts once for the entire group:

;; Sender creates a distribution message and shares it with group members
(let-values (((sender-state dist-msg)
              (create-sender-key-distribution (string->bytes "group-uuid-here"))))

  ;; Each group member processes the distribution message
  (let ((receiver-state (process-sender-key-distribution dist-msg)))

    ;; Sender encrypts a group message
    (let-values (((sender-state-2 encrypted)
                  (sender-key-encrypt sender-state
                                     (string->bytes "group-uuid-here")
                                     (string->bytes "Hello group!"))))

      ;; Each receiver decrypts with their state
      (let-values (((receiver-state-2 plaintext)
                    (sender-key-decrypt receiver-state encrypted)))
        (bytes->string plaintext))))) ;; => "Hello group!"

Low-Level Crypto Primitives

The crypto layer can be used independently:

(import :signal/src/crypto/curve
        :signal/src/crypto/hmac
        :signal/src/crypto/aes
        :signal/src/crypto/hkdf
        :signal/src/crypto/random)

;; X25519 Diffie-Hellman
(let-values (((pub-a priv-a) (x25519-generate-keypair))
             ((pub-b priv-b) (x25519-generate-keypair)))
  (let ((shared-a (x25519-dh priv-a pub-b))
        (shared-b (x25519-dh priv-b pub-a)))
    (equal? shared-a shared-b))) ;; => #t (both sides derive same secret)

;; Ed25519 signatures
(let-values (((pub priv) (ed25519-generate-keypair)))
  (let ((sig (ed25519-sign priv (string->bytes "message"))))
    (ed25519-verify pub sig (string->bytes "message")))) ;; => #t

;; AES-256-CBC
(let ((key (random-bytes 32))
      (iv  (random-bytes 16)))
  (let* ((ct (aes-256-cbc-encrypt key iv (string->bytes "secret")))
         (pt (aes-256-cbc-decrypt key iv ct)))
    (bytes->string pt))) ;; => "secret"

;; HKDF-SHA256 (RFC 5869)
(hkdf-sha256 salt ikm info length) ;; => u8vector of `length` bytes

;; HMAC-SHA256
(signal-hmac-sha256 key data)                ;; => 32-byte MAC
(signal-hmac-sha256-truncated key data 8)    ;; => 8-byte truncated MAC
(constant-time-equal? mac-a mac-b)           ;; => boolean (timing-safe)

;; Secure random
(random-bytes 32) ;; => 32 random bytes

Module Reference

Module	Description
Crypto
:signal/src/crypto/random	Secure random byte generation
:signal/src/crypto/hmac	HMAC-SHA256, SHA-256, SHA-512, constant-time comparison
:signal/src/crypto/aes	AES-256-CBC and AES-256-CTR encrypt/decrypt
:signal/src/crypto/curve	X25519 key agreement, Ed25519 signatures, key serialization
:signal/src/crypto/hkdf	HKDF-SHA256 (RFC 5869)
:signal/src/crypto/kem	Kyber1024 KEM (stub, requires liboqs)
Wire Protocol
:signal/src/proto/protobuf	Minimal protobuf wire format encoder/decoder
:signal/src/proto/wire	SignalMessage, PreKeySignalMessage, SenderKey message types
:signal/src/proto/storage	Session, chain, key storage protobuf structures
:signal/src/proto/sealed	Sealed sender certificate and message types
Core Types
:signal/src/core/keys	Identity keys, EC key pairs, DH and signing operations
:signal/src/core/address	Signal protocol addresses (name:device-id)
:signal/src/core/prekey	One-time and signed pre-key generation/verification
:signal/src/core/bundle	Pre-key bundles for X3DH initiation
:signal/src/core/timestamp	Millisecond timestamp utility
Double Ratchet
:signal/src/ratchet/keys	Root key derivation, chain key advancement, message key derivation
:signal/src/ratchet/params	Protocol constants (session version, max chains, etc.)
:signal/src/ratchet/init	X3DH key agreement (Alice and Bob sides)
Session
:signal/src/session/state	Session creation for initiator and responder
:signal/src/session/cipher	Encrypt/decrypt with DH ratchet stepping
:signal/src/session/process	Pre-key bundle processing, PreKeySignalMessage wrapping
Stores
:signal/src/store/interface	Store interface definitions (identity, prekey, session, sender-key)
:signal/src/store/memory	In-memory store implementations for testing
Sender Keys
:signal/src/sender-key/state	Sender key chain management
:signal/src/sender-key/cipher	Group message encrypt/decrypt with Ed25519 signing
Sealed Sender
:signal/src/sealed-sender/cert	Server and sender certificate creation/validation
:signal/src/sealed-sender/encrypt	Sealed sender encryption
:signal/src/sealed-sender/decrypt	Sealed sender decryption
Fingerprints
:signal/src/fingerprint/fingerprint	60-digit numeric safety number generation
Top-Level
:signal/src/signal	Re-exports all modules

Architecture

signal/
├── crypto/          Cryptographic primitives (OpenSSL via FFI)
│   ├── random       Secure random bytes
│   ├── hmac         HMAC-SHA256, SHA-256/512
│   ├── aes          AES-256-CBC/CTR
│   ├── curve        X25519 DH, Ed25519 sign/verify
│   ├── curve-ffi    Raw Gambit FFI for EVP_PKEY_derive_set_peer
│   ├── hkdf         HKDF-SHA256 (RFC 5869)
│   └── kem          Kyber1024 stub
├── proto/           Protobuf wire format
│   ├── protobuf     Generic varint/length-delimited codec
│   ├── wire         Signal wire protocol messages
│   ├── storage      Session/key storage structures
│   └── sealed       Sealed sender message types
├── core/            Protocol data types
│   ├── keys         Identity keys, EC key pairs
│   ├── address      name:device-id addresses
│   ├── prekey       One-time and signed pre-keys
│   ├── bundle       Pre-key bundles
│   └── timestamp    Millisecond timestamps
├── ratchet/         Double Ratchet algorithm
│   ├── keys         Key derivation functions
│   ├── params       Protocol constants
│   └── init         X3DH session initialization
├── session/         Session management
│   ├── state        Session creation (Alice/Bob)
│   ├── cipher       Encrypt/decrypt with ratchet
│   └── process      Bundle processing, message wrapping
├── store/           Key and session storage
│   ├── interface    Store type contracts
│   └── memory       In-memory implementations
├── sender-key/      Group messaging
│   ├── state        Sender key chain state
│   └── cipher       Group encrypt/decrypt
├── sealed-sender/   Anonymous delivery
│   ├── cert         Certificate management
│   ├── encrypt      Sealed sender encryption
│   └── decrypt      Sealed sender decryption
├── fingerprint/     Safety numbers
│   └── fingerprint  60-digit numeric fingerprints
└── signal.ss        Top-level re-export

Protocol Details

This library implements the following Signal Protocol components:

• X3DH (Extended Triple Diffie-Hellman): Asynchronous session establishment using identity keys, signed pre-keys, and one-time pre-keys. Produces a shared secret used to initialize the Double Ratchet.

• Double Ratchet: Combines a Diffie-Hellman ratchet (new DH key pair per exchange direction) with a symmetric-key ratchet (HMAC-SHA256 chain) to provide forward secrecy and break-in recovery for every message.

• Sender Keys: Efficient group messaging where the sender generates a chain key and signing key shared with all group members. Each message is AES-256-CBC encrypted with keys derived from the chain and Ed25519 signed.

• Sealed Sender: Anonymous message delivery using ephemeral X25519 DH with the recipient's identity key, HKDF-derived encryption keys, and AES-256-CBC + HMAC-SHA256 authenticated encryption.

• Safety Numbers: 60-digit numeric fingerprints computed by iteratively hashing each party's identity key 5200 times with SHA-256, then encoding the result as decimal digits. Both parties compute the same fingerprint regardless of who is "local" vs "remote".

Limitations

• Kyber/PQXDH: The post-quantum key encapsulation module is a stub. It requires liboqs FFI bindings which are not yet implemented.
• Session serialization: Sessions are currently in-memory Gerbil objects. For persistence, serialize using the protobuf encode/decode functions in proto/storage.
• No wire compatibility testing: While the protobuf encoding follows the Signal .proto field numbering, full wire compatibility with libsignal has not been verified against test vectors.
• XEdDSA: The library uses separate X25519 and Ed25519 key pairs rather than deriving Ed25519 from X25519 via XEdDSA. This means identity keys contain both key types.

License

MIT

gerbil-signal