This page explains how cryptographers can submit implementations of public-key-signature systems (RSA, DSA, ECDSA, Merkle hash trees, HFE signatures, etc.) to eBATS.
Don't want to handle arbitrary-length messages? No problem. Instead of implementing signedmessage and messagesigned, you can implement signedshortmessage and shortmessagesigned, and define the maximum length of a short message. BATMAN, the eBATS benchmarking software, will automatically handle longer messages using a hash function.
Don't want to provide recovery of the original message from a signature? No problem. Instead of implementing signedshortmessage and shortmessagesigned, you can implement signatureofshorthash and verification. BATMAN will automatically handle message recovery by signing a hash and appending the original message. (But systems built in this way aren't likely to successfully compete for the shortest signed messages!)
You can also provide additional functions that document additional features of your system:
The eBATS signing API is described below in more detail. There's a separate page on BATMAN; you will be able to download and use BATMAN before submission to check that your implementation works properly. There's also a separate page discussing security evaluations in more detail.
The directory name is the BAT name followed by a dash and a version number: e.g., ronald-1 for a BAT named ronald, version 1. eBATS will rename BATs if there is a conflict in names.
The file sizes.h defines various macros discussed below: SECRETKEY_BYTES, PUBLICKEY_BYTES, SIGNATURE_BYTES, optionally SHORTMESSAGE_BYTES, and optionally SHORTHASH_BYTES.
BATMAN will automatically decide whether the BAT is a C BAT, providing the eBATS API functions in C, or a C++ BAT, providing the eBATS API functions in C++. Either way, the BAT can call C functions in its *.c files and assembly-language functions in its *.S files. BATs written in other languages have to be compiled to C++, C, or assembly language.
The eBATS API can support BATs of either type. A parametrized BAT includes, in the same directory as sizes.h, a parameters file with several lines; each line specifies compilation options that select a particular parameter choice. A parameter choice is specified by BAT-specific macros, which are used by sizes.h etc., and by a PARAMETERS macro (without white space), which is used to identify parameters in the eBATS results.
For example, version 1 of the RONALD BAT has a 29-line parameters file starting
-DMODULUS_BITS=768 -DPARAMETERS="768"
-DMODULUS_BITS=832 -DPARAMETERS="832"
-DMODULUS_BITS=896 -DPARAMETERS="896"
-DMODULUS_BITS=960 -DPARAMETERS="960"
-DMODULUS_BITS=1024 -DPARAMETERS="1024"
and continuing (in roughly geometric progression) until
-DMODULUS_BITS=4096 -DPARAMETERS="4096"
The MODULUS_BITS macro controls PUBLICKEY_BYTES etc.
through the lines
#define MODULUS_BYTES (MODULUS_BITS / 8)
#define PUBLICKEY_BYTES (MODULUS_BYTES)
in the sizes.h file.
The PARAMETERS macro is printed in the eBATS measurements.
The parameters file can omit -DPARAMETERS=... if sizes.h defines PARAMETERS. For example, version 2 of the RONALD BAT has a 29-line parameters file starting
-DMODULUS_BITS=768
-DMODULUS_BITS=832
-DMODULUS_BITS=896
-DMODULUS_BITS=960
-DMODULUS_BITS=1024
and the following lines in sizes.h:
#define XSTRINGIFY(N) #N
#define STRINGIFY(N) XSTRINGIFY(N)
#define PARAMETERS (STRINGIFY(MODULUS_BITS))
BATMAN will automatically try each tuning and select the tuning where signedmessage runs most quickly. A BAT can define a TUNETARGET macro in sizes.h; in that case BATMAN will select the tuning where TUNETARGET() runs most quickly.
Any particular tuning is allowed to be unportable, failing to compile on most platforms. BATMAN will skip tunings that don't compile or that flunk some simple tests.
Functions are permitted, but not encouraged, to generate randomness in other ways, such as by opening /dev/urandom. These functions won't be benchmarkable on systems that don't have /dev/urandom, and they won't be suitable for black-box regression testing.
const unsigned char m[...]; unsigned long long mlen;
unsigned char h[32];
hash256(h,m,mlen);
hash256 hashes bytes m[0], m[1], ..., m[mlen-1]
and puts the output into h[0], h[1], ..., h[31].
Currently hash256 is implemented as SHA-256.
To simplify comparisons of public-key systems, eBATS recommends that BATs use hash256 for all necessary hashing. This is not a recommendation of SHA-256 for any purpose other than public-key benchmarking. Public-key systems may be able to gain speed and security by choosing different hash functions.
To the extent that eBATS considers security of public-key systems, it focuses on generic attacks, i.e., attacks that work with any hash function. Any security problems in SHA-256 are outside the scope of eBATS, although obviously they should be discussed elsewhere.
const unsigned char m[...]; unsigned long long mlen;
unsigned char c[...];
const unsigned char k[32];
const unsigned char n[8];
stream256(c,m,mlen,k,n);
stream256 encrypts (or decrypts) bytes m[0], m[1], ..., m[mlen-1]
and puts the output into c[0], c[1], ..., c[mlen-1].
It uses a 32-byte key k[0], k[1], ..., k[31]
and an 8-byte nonce n[0], n[1], ..., n[7].
Currently stream256 is implemented as Salsa20.
To simplify comparisons of public-key systems, eBATS recommends that BATs use stream256 for all necessary stream generation. This is not a recommendation of Salsa20 for any purpose other than public-key benchmarking. Public-key systems may be able to gain speed and security by choosing different ciphers.
To the extent that eBATS considers security of public-key systems, it focuses on generic attacks, i.e., attacks that work with any stream cipher. Any security problems in Salsa20 are outside the scope of eBATS, although obviously they should be discussed elsewhere.
#include "sizes.h"
unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;
keypair(sk,&sklen,pk,&pklen);
The keypair function
generates a new secret key and a new public key.
It puts the number of bytes of the secret key into sklen;
puts the number of bytes of the public key into pklen;
puts the secret key into
sk[0], sk[1], ..., sk[sklen-1];
and puts the public key into
pk[0], pk[1], ..., pk[pklen-1].
It then returns 0.
keypair guarantees that sklen is at most SECRETKEY_BYTES, and that pklen is at most PUBLICKEY_BYTES, so that the caller can allocate enough space.
If key generation is impossible for some reason (e.g., not enough memory), keypair returns a negative number, possibly after modifying sk[0], sk[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.
#include "sizes.h"
const unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
const unsigned char m[...]; unsigned long long mlen;
unsigned char sm[...]; unsigned long long smlen;
signedmessage(sm,&smlen,m,mlen,sk,sklen);
The signedmessage function
uses a secret key
sk[0], sk[1], ..., sk[sklen-1]
to sign a message
m[0], m[1], ..., m[mlen-1].
It puts the length of the signed message into smlen
and puts the signed message into
sm[0], sm[1], ..., sm[smlen-1].
It then returns 0.
The signedmessage function guarantees that smlen is at most mlen+SIGNATURE_BYTES. The SIGNATURE_BYTES macro is defined in sizes.h.
The signedmessage function is free to assume that the secret key sk[0], sk[1], ..., sk[sklen-1] was generated by a successful call to the keypair function.
If signing is impossible for some reason, signedmessage returns a negative number, possibly after modifying sm[0], sm[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.
Implementors of the signedmessage function are warned that they should not go to extra effort to compress the message m. Higher-level applications should be presumed to compress messages before calling the signedmessage function; in particular, BATMAN uses random messages to make compression ineffective. On the other hand, the signed message sm is longer than the original message m and might be compressible; any reduction of the signature overhead will be visible in the eBATS measurements.
#include "sizes.h"
const unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;
const unsigned char sm[...]; unsigned long long smlen;
unsigned char m[...]; unsigned long long mlen;
messagesigned(m,&mlen,sm,smlen,pk,pklen);
The messagesigned function
uses a public key
pk[0], pk[1], ..., pk[pklen-1]
to verify an allegedly signed message
sm[0], sm[1], ..., sm[smlen-1].
If the message has a valid signature,
the messagesigned function
puts the length of the original message (without the signature)
into mlen,
puts the original message into
m[0], m[1], ..., m[mlen-1],
and returns 0.
The messagesigned function guarantees that mlen is at most smlen.
The messagesigned function is free to assume that the public key pk[0], pk[1], ..., pk[pklen-1] was generated by a successful call to the publickey function. The messagesigned function is not permitted to assume that sm[0], sm[1], ..., sm[smlen-1] was generated by a call to the signedmessage function; the messagesigned function is responsible for detecting and eliminating forgeries.
If signature verification is impossible for some reason, messagesigned returns a negative number, possibly after modifying m[0], m[1], etc. Current implementations should return -100 for invalid signatures, and -1 for all other problems; other return values with special meanings may be defined in the future.
#include "sizes.h"
const unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
const unsigned char m[SHORTMESSAGE_BYTES]; unsigned long long mlen;
unsigned char sm[SIGNATURE_BYTES]; unsigned long long smlen;
signedshortmessage(sm,&smlen,m,mlen,sk,sklen);
The signedshortmessage function
uses a secret key
sk[0], sk[1], ..., sk[sklen-1]
to sign a message
m[0], m[1], ..., m[mlen-1].
It puts the length of the signed message into smlen
and puts the signed message into
sm[0], sm[1], ..., sm[smlen-1].
It then returns 0.
The signedshortmessage function is free to assume that mlen is at most SHORTMESSAGE_BYTES. The signedshortmessage function guarantees that smlen is exactly SIGNATURE_BYTES. The SHORTMESSAGE_BYTES and SIGNATURE_BYTES macros are defined in sizes.h.
The signedshortmessage function is free to assume that the secret key sk[0], sk[1], ..., sk[sklen-1] was generated by a successful call to the keypair function.
If signing is impossible for some reason, signedshortmessage returns a negative number, possibly after modifying sm[0], sm[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.
Implementors of the signedshortmessage function are warned that they should not go to extra effort to compress the message m. Higher-level applications should be presumed to compress messages before calling the signedshortmessage function; in particular, BATMAN uses random messages to make compression ineffective. On the other hand, the signed message sm is longer than the original message m and might be compressible; any reduction of the signature overhead will be visible in the eBATS measurements.
BATMAN automatically builds signedmessage on top of signedshortmessage as follows. Messages with at most SHORTMESSAGE_BYTES-1 bytes are simply signed with signedshortmessage. Messages with SHORTMESSAGE_BYTES or more bytes are hashed with SHA-256; the 32-byte hash and the first SHORTMESSAGE_BYTES-32 bytes of the message are signed with signedshortmessage; the rest of the message is appended. SHORTMESSAGE_BYTES must be at least 32.
#include "sizes.h"
const unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;
const unsigned char sm[SIGNATURE_BYTES]; unsigned long long smlen;
unsigned char m[SHORTMESSAGE_BYTES]; unsigned long long mlen;
shortmessagesigned(m,&mlen,sm,smlen,pk,pklen);
The shortmessagesigned function
uses a public key
pk[0], pk[1], ..., pk[pklen-1]
to verify an allegedly signed message
sm[0], sm[1], ..., sm[smlen-1].
If the message has a valid signature,
the shortmessagesigned function
puts the length of the original message (without the signature)
into mlen,
puts the original message into
m[0], m[1], ..., m[mlen-1],
and returns 0.
The shortmessagesigned function is free to assume that smlen is exactly SIGNATURE_BYTES. The shortmessagesigned function guarantees that mlen is at most SHORTMESSAGE_BYTES.
The shortmessagesigned function is free to assume that the public key pk[0], pk[1], ..., pk[pklen-1] was generated by a successful call to the publickey function. The shortmessagesigned function is not permitted to assume that sm[0], sm[1], ..., sm[smlen-1] was generated by a call to the signedshortmessage function; the shortmessagesigned function is responsible for detecting and eliminating forgeries.
If signature verification is impossible for some reason, shortmessagesigned returns a negative number, possibly after modifying m[0], m[1], etc. Current implementations should return -100 for invalid signatures, and -1 for all other problems; other return values with special meanings may be defined in the future.
BATMAN automatically builds messagesigned on top of shortmessagesigned by feeding the first SIGNATURE_BYTES bytes of the signed message to shortmessagesigned.
#include "sizes.h"
const unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
const unsigned char m[SHORTHASH_BYTES]; unsigned long long mlen;
unsigned char sm[SIGNATURE_BYTES]; unsigned long long smlen;
signatureofshorthash(sm,&smlen,m,mlen,sk,sklen);
The signatureofshorthash function
uses a secret key
sk[0], sk[1], ..., sk[sklen-1]
to sign a message
m[0], m[1], ..., m[mlen-1].
It puts the length of the signature into smlen
and puts the signature into
sm[0], sm[1], ..., sm[smlen-1].
It then returns 0.
The signatureofshorthash function is free to assume that mlen is at most SHORTHASH_BYTES. The signatureofshorthash function guarantees that smlen is exactly SIGNATURE_BYTES. The SHORTHASH_BYTES and SIGNATURE_BYTES macros are defined in sizes.h.
The signatureofshorthash function is free to assume that the secret key sk[0], sk[1], ..., sk[sklen-1] was generated by a successful call to the keypair function.
If signing is impossible for some reason, signatureofshorthash returns a negative number, possibly after modifying sm[0], sm[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.
BATMAN automatically builds signedmessage on top of signatureofshorthash by applying signatureofshorthash to a 32-byte SHA-256 hash of the message being signed. This means that signatureofshorthash is always given a 32-byte input, no matter what the original message length was; SHORTHASH_BYTES must be at least 32. Criticisms of the speed and security of SHA-256 are outside the scope of eBATS; eBATS focuses on public-key cryptography, not on hash functions.
#include "sizes.h"
const unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;
const unsigned char sm[SIGNATURE_BYTES]; unsigned long long smlen;
const unsigned char m[SHORTHASH_BYTES]; unsigned long long mlen;
verification(m,mlen,sm,smlen,pk,pklen);
The verification function
uses a public key
pk[0], pk[1], ..., pk[pklen-1]
to verify an alleged signature
sm[0], sm[1], ..., sm[smlen-1]
on a message
m[0], m[1], ..., m[mlen-1].
If the message has a valid signature,
the verification function returns 0.
The verification function is free to assume that smlen is exactly SIGNATURE_BYTES and that mlen is at most SHORTHASH_BYTES.
The verification function is free to assume that the public key pk[0], pk[1], ..., pk[pklen-1] was generated by a successful call to the publickey function. The verification function is not permitted to assume that sm[0], sm[1], ..., sm[smlen-1] was generated by a call to the signatureofshorthash function; the verification function is responsible for detecting and eliminating forgeries.
If signature verification is impossible for some reason, verification returns a negative number, possibly after modifying m[0], m[1], etc. Current implementations should return -100 for invalid signatures, and -1 for all other problems; other return values with special meanings may be defined in the future.
BATMAN automatically builds messagesigned on top of verification by extracting the first SIGNATURE_BYTES bytes of the signed message as a signature, extracting the remaining bytes as the original message, and applying verification to a 32-byte SHA-256 hash of the original message.
#include "sizes.h"
double e;
double s;
double p = forgerychance(e,s);
The forgerychance function
returns a number between 0 and 1,
namely the probability that an attacker spending e euros
will succeed at forging at least one signed message within s seconds,
given a public key.
Here e and s are powers of 2 between 2^0 and 2^40.
The attacker is not required to carry out a selective forgery, i.e., a forgery on a message chosen in advance by the attacker. Any forged message, no matter how random it looks, is presumed to be a disaster if it was not signed by the legitimate key owner. This is a standard presumption: without it, every application would need a separate analysis of potential forgeries within the application's message space.
The attacker is not required to carry out a blind attack. The attacker is presumed to be able to see many legitimate signatures. This is a standard presumption: most signature applications do not keep signatures secret.
The attacker is not required to carry out a passive attack. The attacker is presumed to be able to influence the legitimately signed messages. This is a standard presumption: without it, every application would need a separate analysis of the attacker's influence.
There is a separate page with more information on security evaluations.
#include "sizes.h"
double e;
double s;
double k;
double p = multiplekeyforgerychance(e,s,k);
The multiplekeyforgerychance function
returns a number between 0 and 1,
namely the probability that an attacker spending e euros
will succeed at forging at least one signed message within s seconds,
given k public keys.
Here e, s, and k
are powers of 2 between 2^0 and 2^40.
The result of multiplekeyforgerychance can be larger than the result of forgerychance by a factor as large as k.
#include "sizes.h"
int x = timingattacks();
The timingattacks function
returns 0 if the software
does not leak any secret information through timing
(variable time for branching, variable time for memory access, etc.):
i.e., if the best attack known that sees timings
is as difficult as the best attack known that does not see timings.
It returns 100 if the software leaks secret information through timing.
#include "sizes.h"
int x = copyrightclaims();
The copyrightclaims function returns
one of the following numbers:
No matter what the BAT's copyright status is, eBATS will publicly distribute copies of the BAT for benchmarking. The submitter must ensure before submission that publication is legal.
#include "sizes.h"
int x = patentclaims();
The patentclaims function returns
one of the following numbers:
No matter what the BAT's patent status is, eBATS will publicly distribute copies of the BAT for benchmarking.