@@@ fltfmt mess

[mLib] / hash / siphash.3.in

.\" -*-nroff-*-
.\"
.\" Manual for SipHash
.\"
.\" (c) 2024 Straylight/Edgeware
.\"
.
.\"----- Licensing notice ---------------------------------------------------
.\"
.\" This file is part of the mLib utilities library.
.\"
.\" mLib is free software: you can redistribute it and/or modify it under
.\" the terms of the GNU Library General Public License as published by
.\" the Free Software Foundation; either version 2 of the License, or (at
.\" your option) any later version.
.\"
.\" mLib is distributed in the hope that it will be useful, but WITHOUT
.\" ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
.\" FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
.\" License for more details.
.\"
.\" You should have received a copy of the GNU Library General Public
.\" License along with mLib.  If not, write to the Free Software
.\" Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
.\" USA.
.
.\"--------------------------------------------------------------------------
.so ../defs.man \" @@@PRE@@@
.
.\"--------------------------------------------------------------------------
.TH siphash 3mLib "14 April 2024" "Straylight/Edgeware" "mLib utilities library"
.\" @SIPHASH_KEYSZ
.\" @SIPHASH_BLKSZ
.
.\" @siphash_setkey
.
.\" @siphash
.\" @SIPHASH
.
.\" @siphash_init
.\" @siphash_hash
.\" @siphash_done
.\" @SIPHASH_INIT
.\" @SIPHASH_WORD
.\" @SIPHASH_FINAL
.
.\"--------------------------------------------------------------------------
.SH SYNOPSIS
.nf
.B "#include <mLib/siphash.h>"
.PP
.B "struct siphash_key { kludge64 k0, k1; };"
.B "struct siphash { ...\& };"
.PP
.B "#define SIPHASH_KEYSZ 16"
.B "#define SIPHASH_BLKSZ 8"
.PP
.BI "void siphash_setkey(struct siphash_key *" k ", const octet *" p );
.PP
.ta \w'\fBkludge64 siphash('u
.BI "kludge64 siphash(const struct siphash_key *" k ,
.BI "	const void *" p ", size_t " sz );
.ta \w'\fBvoid SIPHASH('u
.BI "void SIPHASH(const struct siphash_key *" k ", kludge64 &" z_out ,
.BI "	const void *" p ", size_t " sz );
.PP
.BI "void siphash_init(struct siphash *" s ", const struct siphash_key *" k );
.BI "void siphash_hash(struct siphash *" s ", const void *" p ", size_t " sz );
.BI "kludge64 siphash_done(struct siphash *" s );
.PP
.BI "void SIPHASH_INIT(struct siphash *" s ", const struct siphash_key *" k );
.BI "void SIPHASH_WORD(struct siphash *" s ", kludge64 " m );
.ta \w'\fBvoid SIPHASH_FINAL('u
.BI "void SIPHASH_FINAL(struct siphash *" s
.BI "	const void *" p ", unsigned " n ", size_t " msz );
.fi
.
.\"--------------------------------------------------------------------------
.SH DESCRIPTION
.
SipHash is a cryptographic pseudorandom function (PRF)
and message authentication code
designed in 2012 by Jean-Philippe Aumasson and Daniel J.\& Bernstein
as a keyed hash function to be used to implement data structures
to defend against malicious input.
It therefore provides similar benefits to mLib's
.BR unihash (3)
module.
Specifically, this module implements the SipHash-2-4 variant
described in the original paper.
.PP
Prior to hashing,
a
.I key
must be prepared.
To prepare a key,
fill a buffer with
.BR SIPHASH_KEYSZ "\ =\ 16"
bytes (128 bits) of random data,
and call
.BR siphash_setkey .
Alternatively,
initialize the
.B k0
and
.B k1
members of the
.B struct siphash_key
structure directly.
The main limit on security of the hash function
will come from the randomness of the key;
the C library's
.BR rand (3)
function is likely unacceptable.
.PP
Once a key is prepared, messages can be hashed.
The simplest interface is the
.B siphash
function:
pass in the prepared key and the buffer containing the message,
and it will return the computed hash.
Slightly more complex, but possibly faster,
the
.B SIPHASH
macro will leave the computed hash value in
.IR z_out .
The hash has type
.BR kludge64 :
this can be readily converted to a more convenient type using the
.BR GET64 (3) macro;
see
.BR bits (3)
for more details about the
.B kludge64
type.
.PP
If it's not convenient to arrange that
the message data is in a single buffer,
then the message can be processed in pieces.
The
.B siphash_init
function intializes a hashing state
in a structure of type
.BR "struct siphash" .
The pieces of the message can now be presented, in order,
to the
.B siphash_hash
function,
which will update the hashing state as necessary.
The pieces and their sizes do not have to be aligned
in any particular way.
Finally, the
.B siphash_done
function computes and returns the final result,
which is the hash of
the concatenation of the message pieces, in order.
The hashing state is clobbered as a result,
and will no longer produce useful results
(though no undefined behaviour will result).
.PP
Finally, there is a low-level interface, which is harder to use.
It is provided primarily for the benefit of the
.B SIPHASH
macro,
but is made available to client programs
in case it turns out to be useful.
The internal state managed by the internal macros
consists of four
.B kludge64
variables named
.IR a ,
.IR b ,
.IR c ,
and
.IR d .
The macro
.B SIPHASH_INIT
will initialize these variables appropriately
to begin processing a fresh message,
given a prepared key
.IR k .
The macro
.B SIPHASH_WORD
updates the state given the next 64-bit word of the message;
SipHash uses a little-endian convention,
so the word should be read using
.BR LOAD64_L_ (3)
or similar.
When only seven or fewer bytes of the message remain,
call the macro
.B SIPHASH_FINAL
to compute the message hash.
This expects, in addition to the four state variables,
a pointer
.I p
to the tail of the message,
the length
.I n
of the tail,
and the overall message length
.IR msz ,
in bytes;
the hash is returned in the
.B kludge64
output variable
.IR z_out .
.
.SS "Comparison with unihash(3)"
Since
SipHash
and mLib's existing
.BR unihash (3)
perform similar functions and were designed with similar motivations,
it's natural to compare them.
.PP
SipHash is newer \(en by nearly a decade.
.B unihash
returns a 32-bit hash;
SipHash
returns a 64-bit hash,
so will certainly be preferable for huge data structures.
.PP
SipHash can be (and, here, has been) implemented
without leaking message or other secret data into
caches or other microarchitectural state.
Alas,
.B unihash
does have these kinds of leaks.
The consequences of compromising a hashing key are
generally limited to denial of service;
furthermore, microarchitectural leaks can only be exploited by software
sharing hardware resources with the victim,
and locally executing software generally has other,
more effective means
to deny service.
In many cases,
.B unihash
is adequate;
if security agaist local adversaries is important,
use SipHash.
.PP
In terms of performace,
.B unihash
seems faster than SipHash on very short messages
\(en up to about 35 bytes.
Despite the designers' efforts,
SipHash has significant finalization overhead,
which are better amortized over longer messages;
as a result, SipHash performance improves with message length.
By contrast
.B unihash
has no per-message startup or finalization overhead,
and performance
.I decreases
with message length, mostly as a result of poorer cache utilization.
.PP
For now, based on these findings,
mLib continues to use
.B unihash
in its
.BR sym (3)
hashtable implementation.
.
.\"--------------------------------------------------------------------------
.SH SEE ALSO
.
.BR crc32 (3),
.BR siphash (3),
.BR unihash (3),
.BR mLib (3).
.PP
Jean-Philippe Aumasson and Daniel J.\& Bernstein,
.IR "SipHash: a fast short-input PRF" ,
INDOCRYPT 2012.
.
.\"--------------------------------------------------------------------------
.SH AUTHOR
.
Mark Wooding (mdw@distorted.org.uk).
.
.\"----- That's all, folks --------------------------------------------------