Skip to content
azuchiPublic

About

Ruby implementation of the Winternitz OTS (W-OTS+).

Topics

Resources

Code of conduct

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

WOTS+

A Ruby implementation of the Winternitz One-Time Signature Plus (WOTS+) scheme as described in RFC 8391.

WOTS+ is a post-quantum cryptographic signature scheme that provides security against quantum computer attacks.

Features

  • Complete implementation of WOTS+ as specified in RFC 8391
  • Support for multiple hash functions:
    • WOTSP-SHA2_256 (SHA-256)
    • WOTSP-SHA2_512 (SHA-512)
    • WOTSP-SHAKE_256 (SHAKE128 with a 256-bit output, as defined in RFC 8391)
  • Support for Winternitz parameters w=4 and w=16
  • Key generation from seed
  • Digital signature generation and verification

Installation

Add this line to your application's Gemfile:

gem 'wots'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install wots

Usage

Basic Example

require 'wots'

# Use predefined parameters
param = WOTS::Param::SHA256

# Generate private key from the secret seed and the public seed
seed = "693141c7ee701d13e1a7c733e0aa8326c19961429bfb54083f2f65b30c32e20b"
pub_seed = "46ece585b4c0bfa1186209270e22fa07c4716461b5a026c268e594fb94404f3a"
private_key = WOTS::PrivateKey.from_seed(param, seed, pub_seed)

# Generate public key
public_key = WOTS::PublicKey.from_private_key(private_key, pub_seed)

# Sign a message
message = "f16c96e88fb99a8287a43121962e89ed521699fa3e126c67eaaa168066354477"
signature = private_key.sign(pub_seed, message)

# Verify signature
valid = public_key.verify(signature, pub_seed, message)
puts "Signature valid: #{valid}"

Deriving several keys from one seed

Private keys are derived as sk[i] = PRF_keygen(seed, pub_seed || ADRS) (NIST SP 800-208 Section 6.2), so each address gives a different key. Pass a distinct WOTS::Address (e.g. a different ots_addr) for each key, and pass the same address to every operation on that key:

addr = WOTS::Address.new(ots_addr: 5)
private_key = WOTS::PrivateKey.from_seed(param, seed, pub_seed, addr: addr)
public_key = WOTS::PublicKey.from_private_key(private_key, pub_seed, addr: addr)
signature = private_key.sign(pub_seed, message, addr: addr)
public_key.verify(signature, pub_seed, message, addr: addr) # => true

addr defaults to WOTS::Address.new (all fields zero). Never use the same seed, pub_seed and address for two keys: they would be the same key, and signing with both would reuse a one-time key. See One-time keys for how to manage the addresses.

Available Parameter Sets

# SHA-256 based (n=32 bytes, w=16)
param = WOTS::Param::SHA256

# SHA-512 based (n=64 bytes, w=16)
param = WOTS::Param::SHA512

# SHAKE128 based (n=32 bytes, w=16), i.e. RFC 8391 WOTSP-SHAKE_256
param = WOTS::Param::SHAKE256

WOTS::Param::SHAKE256 is named after the RFC 8391 parameter set WOTSP-SHAKE_256, where 256 is the output length in bits. It uses SHAKE128, not SHAKE256 (RFC 8391 Section 5.1).

Using the WOTS+ engine from another library

WOTS::Core is the scheme-independent WOTS+ engine behind the API above. It works on binary strings and leaves the hashing and the hash address to a hasher object, so the same engine can drive other WOTS+ instantiations, such as the one in SLH-DSA (FIPS 205), implemented in another library.

core = WOTS::Core.new(n: 16, w: 16)   # w is 4 or 16
pk   = core.pk_gen(hasher)
sig  = core.sign(hasher, msg)         # msg: n-byte binary string; returns len n-byte strings
pk2  = core.pk_from_sig(hasher, sig, msg)

A hasher is bound to one WOTS+ key pair and responds to:

Method Returns
secret(chain_idx) the n-byte secret value of chain chain_idx (used by pk_gen and sign only)
step(x, chain_idx, hash_idx) one application of the chaining hash to the n-byte value x at position hash_idx of chain chain_idx
compress(values) the public key built from the len chain end values

WOTS::Core calls them in the order of FIPS 205 Algorithms 6–8: for each chain i in ascending order, secret(i) (when needed) and then step(x, i, j) for ascending j. It never sees an address, so the hasher sets the chain and hash address itself. WOTS::RFC8391Hasher is the hasher of RFC 8391 used by this library.

A hasher keeps a mutable address, so do not share one hasher between threads; create one per operation.

Input format

All key material, seeds and messages are even-length hexadecimal strings. Raw binary strings and odd-length hex strings are rejected with an ArgumentError; convert them with unpack1('H*') first.

message = Digest::SHA256.hexdigest("some payload")   # 64 hex chars = 32 bytes
signature = private_key.sign(pub_seed, message)

Security Considerations

⚠️ IMPORTANT: This is a cryptographic library implementation. While it follows RFC 8391 specifications, it has not undergone formal security audits. Use at your own risk in production environments.

One-time keys: state management is up to you

WOTS+ is a one-time signature scheme. Each private key must be used to sign one message, once. Signatures of two different messages under the same key let an attacker forge signatures.

This library does not track whether a key has been used. A flag inside WOTS::PrivateKey would not protect you: calling PrivateKey.from_seed again recreates the same key as a fresh object, and real reuse happens across process restarts, devices and backups, which no in-memory flag can see. The state belongs to the code that assigns one-time keys, typically a counter of the next address to use. Follow these rules (based on NIST SP 800-208 Sections 8.1 and 9.1):

  • One address per key. seed, pub_seed and addr determine the key: the same triple always gives the same key. Give every key its own address, e.g. by incrementing ots_addr.
  • Persist before you release. Write the updated state (e.g. the next ots_addr) to non-volatile storage, and make sure it has really reached it (e.g. File#fsync, a committed database transaction), before the signature leaves your process. If the process crashes after exporting a signature but before the state is durable, the key will be used again after the restart.
  • Never sign twice, not even the same message. Re-computing a signature over the same message is open to fault injection attacks (SP 800-208, Section 8.1, footnote 9). Sign once and store the signature if you need it again.
  • Never roll the state back or share it. Do not restore the state from backups or VM snapshots, and do not use the same seed on several devices or processes at once.

SP 800-208 additionally requires stateful hash-based key generation and signing to run inside a validated hardware cryptographic module. This software library cannot meet that requirement.

Key material

The seed passed to WOTS::PrivateKey.from_seed is secret key material and must come from a cryptographically secure random number generator, e.g. SecureRandom.hex(param.n). The private key is bound to pub_seed and the address, using the key generation method of NIST SP 800-208 (Section 6.2). Of the parameter sets supported here, SP 800-208 defines PRF_keygen only for WOTSP-SHA2_256; this library applies the same construction (Hash(toByte(4, n) || KEY || M)) to every parameter set, as the XMSS reference implementation does.

Only the Winternitz parameters defined in RFC 8391 (w = 4 and w = 16) are accepted. Other values overflow the checksum encoding, which drops the high bits of the checksum and allows an attacker to forge signatures without the private key.

Private key material is held in Ruby String objects and is not zeroized; it remains in memory until garbage collected.

Specifications

This implementation follows RFC 8391 - XMSS: eXtended Merkle Signature Scheme, Section 3 (WOTS+). Private keys are derived with the method of NIST SP 800-208 Section 6.2.

How it is tested

RFC 8391 and SP 800-208 do not publish test vectors; RFC 8391 (Section 7) points to its reference implementation instead, and NIST ACVP has no XMSS or WOTS+ test vectors yet. spec/fixtures/reference_vectors.json was therefore generated with the WOTS+ part (wots.c) of the XMSS reference implementation (commit 171ccbd26f098542a67eb5d2b128281c80bd71a6) for every parameter set, w = 4 and 16, and a non-zero address. The specs check that key generation, signing and verification reproduce those vectors.

Note that this is the reference implementation of XMSS, not of a standalone WOTS+. The chaining, signing and verification are RFC 8391 WOTS+ itself. The private key derivation is the one XMSS uses (SP 800-208); RFC 8391 leaves the derivation of WOTS+ private keys open (Section 3.1.7).

Not compatible with SLH-DSA

The WOTS+ of SLH-DSA (FIPS 205) is a different instantiation: its chain step is the tweakable hash F(PK.seed, ADRS, M) without bitmasks, its address layout differs (and is compressed for SHA2), the public key is compressed with T_len, and it uses n = 16, 24, 32 with w = 16 only. Keys and signatures of this library cannot be used with SLH-DSA, nor with schemes built on it. Such a WOTS+ can be implemented on top of WOTS::Core with its own hasher (see Using the WOTS+ engine from another library).

About

Ruby implementation of the Winternitz OTS (W-OTS+).

Topics

Resources

Code of conduct

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages