chiark - git - mdw - mLib/blob - hash/siphash.3.in

   1 .\" -*-nroff-*-
   2 .\"
   3 .\" Manual for SipHash
   4 .\"
   5 .\" (c) 2024 Straylight/Edgeware
   6 .\"
   7 .
   8 .\"----- Licensing notice ---------------------------------------------------
   9 .\"
  10 .\" This file is part of the mLib utilities library.
  11 .\"
  12 .\" mLib is free software: you can redistribute it and/or modify it under
  13 .\" the terms of the GNU Library General Public License as published by
  14 .\" the Free Software Foundation; either version 2 of the License, or (at
  15 .\" your option) any later version.
  16 .\"
  17 .\" mLib is distributed in the hope that it will be useful, but WITHOUT
  18 .\" ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 .\" FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  20 .\" License for more details.
  21 .\"
  22 .\" You should have received a copy of the GNU Library General Public
  23 .\" License along with mLib.  If not, write to the Free Software
  24 .\" Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  25 .\" USA.
  26 .
  27 .\"--------------------------------------------------------------------------
  28 .so ../defs.man \" @@@PRE@@@
  29 .
  30 .\"--------------------------------------------------------------------------
  31 .TH siphash 3mLib "14 April 2024" "Straylight/Edgeware" "mLib utilities library"
  32 .\" @SIPHASH_KEYSZ
  33 .\" @SIPHASH_BLKSZ
  34 .
  35 .\" @siphash_setkey
  36 .
  37 .\" @siphash
  38 .\" @SIPHASH
  39 .
  40 .\" @siphash_init
  41 .\" @siphash_hash
  42 .\" @siphash_done
  43 .\" @SIPHASH_INIT
  44 .\" @SIPHASH_WORD
  45 .\" @SIPHASH_FINAL
  46 .
  47 .\"--------------------------------------------------------------------------
  48 .SH SYNOPSIS
  49 .nf
  50 .B "#include <mLib/siphash.h>"
  51 .PP
  52 .B "struct siphash_key { kludge64 k0, k1; };"
  53 .B "struct siphash { ...\& };"
  54 .PP
  55 .B "#define SIPHASH_KEYSZ 16"
  56 .B "#define SIPHASH_BLKSZ 8"
  57 .PP
  58 .BI "void siphash_setkey(struct siphash_key *" k ", const octet *" p );
  59 .PP
  60 .ta \w'\fBkludge64 siphash('u
  61 .BI "kludge64 siphash(const struct siphash_key *" k ,
  62 .BI "   const void *" p ", size_t " sz );
  63 .ta \w'\fBvoid SIPHASH('u
  64 .BI "void SIPHASH(const struct siphash_key *" k ", kludge64 &" z_out ,
  65 .BI "   const void *" p ", size_t " sz );
  66 .PP
  67 .BI "void siphash_init(struct siphash *" s ", const struct siphash_key *" k );
  68 .BI "void siphash_hash(struct siphash *" s ", const void *" p ", size_t " sz );
  69 .BI "kludge64 siphash_done(struct siphash *" s );
  70 .PP
  71 .BI "void SIPHASH_INIT(struct siphash *" s ", const struct siphash_key *" k );
  72 .BI "void SIPHASH_WORD(struct siphash *" s ", kludge64 " m );
  73 .ta \w'\fBvoid SIPHASH_FINAL('u
  74 .BI "void SIPHASH_FINAL(struct siphash *" s
  75 .BI "   const void *" p ", unsigned " n ", size_t " msz );
  76 .fi
  77 .
  78 .\"--------------------------------------------------------------------------
  79 .SH DESCRIPTION
  80 .
  81 SipHash is a cryptographic pseudorandom function (PRF)
  82 and message authentication code
  83 designed in 2012 by Jean-Philippe Aumasson and Daniel J.\& Bernstein
  84 as a keyed hash function to be used to implement data structures
  85 to defend against malicious input.
  86 It therefore provides similar benefits to mLib's
  87 .BR unihash (3)
  88 module.
  89 Specifically, this module implements the SipHash-2-4 variant
  90 described in the original paper.
  91 .PP
  92 Prior to hashing,
  93 a
  94 .I key
  95 must be prepared.
  96 To prepare a key,
  97 fill a buffer with
  98 .BR SIPHASH_KEYSZ "\ =\ 16"
  99 bytes (128 bits) of random data,
 100 and call
 101 .BR siphash_setkey .
 102 Alternatively,
 103 initialize the
 104 .B k0
 105 and
 106 .B k1
 107 members of the
 108 .B struct siphash_key
 109 structure directly.
 110 The main limit on security of the hash function
 111 will come from the randomness of the key;
 112 the C library's
 113 .BR rand (3)
 114 function is likely unacceptable.
 115 .PP
 116 Once a key is prepared, messages can be hashed.
 117 The simplest interface is the
 118 .B siphash
 119 function:
 120 pass in the prepared key and the buffer containing the message,
 121 and it will return the computed hash.
 122 Slightly more complex, but possibly faster,
 123 the
 124 .B SIPHASH
 125 macro will leave the computed hash value in
 126 .IR z_out .
 127 The hash has type
 128 .BR kludge64 :
 129 this can be readily converted to a more convenient type using the
 130 .BR GET64 (3) macro;
 131 see
 132 .BR bits (3)
 133 for more details about the
 134 .B kludge64
 135 type.
 136 .PP
 137 If it's not convenient to arrange that
 138 the message data is in a single buffer,
 139 then the message can be processed in pieces.
 140 The
 141 .B siphash_init
 142 function intializes a hashing state
 143 in a structure of type
 144 .BR "struct siphash" .
 145 The pieces of the message can now be presented, in order,
 146 to the
 147 .B siphash_hash
 148 function,
 149 which will update the hashing state as necessary.
 150 The pieces and their sizes do not have to be aligned
 151 in any particular way.
 152 Finally, the
 153 .B siphash_done
 154 function computes and returns the final result,
 155 which is the hash of
 156 the concatenation of the message pieces, in order.
 157 The hashing state is clobbered as a result,
 158 and will no longer produce useful results
 159 (though no undefined behaviour will result).
 160 .PP
 161 Finally, there is a low-level interface, which is harder to use.
 162 It is provided primarily for the benefit of the
 163 .B SIPHASH
 164 macro,
 165 but is made available to client programs
 166 in case it turns out to be useful.
 167 The internal state managed by the internal macros
 168 consists of four
 169 .B kludge64
 170 variables named
 171 .IR a ,
 172 .IR b ,
 173 .IR c ,
 174 and
 175 .IR d .
 176 The macro
 177 .B SIPHASH_INIT
 178 will initialize these variables appropriately
 179 to begin processing a fresh message,
 180 given a prepared key
 181 .IR k .
 182 The macro
 183 .B SIPHASH_WORD
 184 updates the state given the next 64-bit word of the message;
 185 SipHash uses a little-endian convention,
 186 so the word should be read using
 187 .BR LOAD64_L_ (3)
 188 or similar.
 189 When only seven or fewer bytes of the message remain,
 190 call the macro
 191 .B SIPHASH_FINAL
 192 to compute the message hash.
 193 This expects, in addition to the four state variables,
 194 a pointer
 195 .I p
 196 to the tail of the message,
 197 the length
 198 .I n
 199 of the tail,
 200 and the overall message length
 201 .IR msz ,
 202 in bytes;
 203 the hash is returned in the
 204 .B kludge64
 205 output variable
 206 .IR z_out .
 207 .
 208 .SS "Comparison with unihash(3)"
 209 Since
 210 SipHash
 211 and mLib's existing
 212 .BR unihash (3)
 213 perform similar functions and were designed with similar motivations,
 214 it's natural to compare them.
 215 .PP
 216 SipHash is newer \(en by nearly a decade.
 217 .B unihash
 218 returns a 32-bit hash;
 219 SipHash
 220 returns a 64-bit hash,
 221 so will certainly be preferable for huge data structures.
 222 .PP
 223 SipHash can be (and, here, has been) implemented
 224 without leaking message or other secret data into
 225 caches or other microarchitectural state.
 226 Alas,
 227 .B unihash
 228 does have these kinds of leaks.
 229 The consequences of compromising a hashing key are
 230 generally limited to denial of service;
 231 furthermore, microarchitectural leaks can only be exploited by software
 232 sharing hardware resources with the victim,
 233 and locally executing software generally has other,
 234 more effective means
 235 to deny service.
 236 In many cases,
 237 .B unihash
 238 is adequate;
 239 if security agaist local adversaries is important,
 240 use SipHash.
 241 .PP
 242 In terms of performace,
 243 .B unihash
 244 seems faster than SipHash on very short messages
 245 \(en up to about 35 bytes.
 246 Despite the designers' efforts,
 247 SipHash has significant finalization overhead,
 248 which are better amortized over longer messages;
 249 as a result, SipHash performance improves with message length.
 250 By contrast
 251 .B unihash
 252 has no per-message startup or finalization overhead,
 253 and performance
 254 .I decreases
 255 with message length, mostly as a result of poorer cache utilization.
 256 .PP
 257 For now, based on these findings,
 258 mLib continues to use
 259 .B unihash
 260 in its
 261 .BR sym (3)
 262 hashtable implementation.
 263 .
 264 .\"--------------------------------------------------------------------------
 265 .SH SEE ALSO
 266 .
 267 .BR crc32 (3),
 268 .BR siphash (3),
 269 .BR unihash (3),
 270 .BR mLib (3).
 271 .PP
 272 Jean-Philippe Aumasson and Daniel J.\& Bernstein,
 273 .IR "SipHash: a fast short-input PRF" ,
 274 INDOCRYPT 2012.
 275 .
 276 .\"--------------------------------------------------------------------------
 277 .SH AUTHOR
 278 .
 279 Mark Wooding (mdw@distorted.org.uk).
 280 .
 281 .\"----- That's all, folks --------------------------------------------------