contrib/pam_passwdqc/passwdqc_filter.h

   1 /*
   2  * Copyright (c) 2020 by Solar Designer
   3  * See LICENSE
   4  */
   5
   6 #ifndef PASSWDQC_FILTER_H__
   7 #define PASSWDQC_FILTER_H__
   8
   9 #include <stdint.h>
  10
  11 /* Higher-level API for use by passwdqc_check.c */
  12
  13 typedef struct {
  14         uint8_t version[4]; /* PASSWDQC_FILTER_VERSION */
  15         uint8_t threshold; /* 0 to 4 */
  16         uint8_t bucket_size; /* 2 to 4 */
  17         uint8_t hash_id; /* one of PASSWDQC_FILTER_HASH_* */
  18         uint8_t reserved1;
  19         uint64_t endianness; /* PASSWDQC_FILTER_ENDIANNESS */
  20         uint64_t reserved2; /* e.g., for checksum */
  21         uint64_t capacity, deletes, inserts, dupes, kicks;
  22 } passwdqc_filter_header_t;
  23
  24 typedef struct {
  25         passwdqc_filter_header_t header;
  26         int fd;
  27 } passwdqc_filter_t;
  28
  29 extern int passwdqc_filter_open(passwdqc_filter_t *flt, const char *filename);
  30 extern int passwdqc_filter_lookup(const passwdqc_filter_t *flt, const char *plaintext);
  31 extern int passwdqc_filter_close(passwdqc_filter_t *flt);
  32
  33 #ifdef PASSWDQC_FILTER_INTERNALS
  34 /* Lower-level inlines for shared use by pwqfilter.c and passwdqc_filter.c */
  35
  36 #include <string.h> /* for strcspn() */
  37 #ifndef _MSC_VER
  38 #include <endian.h>
  39 #endif
  40
  41 #include "md4.h"
  42
  43 #define PASSWDQC_FILTER_VERSION "PWQ0"
  44 #define PASSWDQC_FILTER_ENDIANNESS 0x0807060504030201ULL
  45
  46 static inline int passwdqc_filter_verify_header(const passwdqc_filter_header_t *header)
  47 {
  48         return (memcmp(header->version, PASSWDQC_FILTER_VERSION, sizeof(header->version)) ||
  49             header->threshold > header->bucket_size || header->bucket_size < 2 || header->bucket_size > 4 ||
  50             header->endianness != PASSWDQC_FILTER_ENDIANNESS ||
  51             (header->capacity & 3) || header->capacity < 4 || header->capacity > ((1ULL << 32) - 1) * 4 ||
  52             header->inserts - header->deletes > header->capacity) ? -1 : 0;
  53 }
  54
  55 typedef enum {
  56         PASSWDQC_FILTER_HASH_OPAQUE = 0,
  57         PASSWDQC_FILTER_HASH_MIN = 1,
  58         PASSWDQC_FILTER_HASH_MD4 = 1,
  59         PASSWDQC_FILTER_HASH_NTLM_CP1252 = 2,
  60         PASSWDQC_FILTER_HASH_MAX = 2
  61 } passwdqc_filter_hash_id_t;
  62
  63 typedef struct {
  64         uint64_t hi, lo; /* we access hi first, so let's also place it first */
  65 } passwdqc_filter_packed_t;
  66
  67 typedef uint32_t passwdqc_filter_i_t;
  68 typedef uint64_t passwdqc_filter_f_t;
  69
  70 typedef struct {
  71         passwdqc_filter_f_t slots[4];
  72 } passwdqc_filter_unpacked_t;
  73
  74 typedef union {
  75         unsigned char uc[16];
  76         uint32_t u32[4];
  77         uint64_t u64[2];
  78 } passwdqc_filter_hash_t;
  79
  80 #ifdef __GNUC__
  81 #define force_inline    __attribute__ ((always_inline)) inline
  82 #define likely(x)       __builtin_expect(!!(x), 1)
  83 #define unlikely(x)     __builtin_expect(!!(x), 0)
  84 #else
  85 #define force_inline    inline
  86 #define likely(x)       (x)
  87 #define unlikely(x)     (x)
  88 #endif
  89
  90 static force_inline passwdqc_filter_i_t passwdqc_filter_wrap(uint32_t what, passwdqc_filter_i_t m)
  91 {
  92         return ((uint64_t)what * m) >> 32;
  93 }
  94
  95 static force_inline passwdqc_filter_i_t passwdqc_filter_h2i(passwdqc_filter_hash_t *h, passwdqc_filter_i_t m)
  96 {
  97         uint32_t i;
  98 /*
  99  * Controversial optimization: when converting a hash to its hash table index
 100  * for the primary bucket, take its initial portion and swap the nibbles so
 101  * that we process most of the hash table semi-sequentially in case our input
 102  * is an ASCII-sorted list of hex-encoded hashes.  A drawback is that we fail
 103  * to reach high load if our input is a biased fragment from such sorted list.
 104  */
 105 #if defined(__BYTE_ORDER) && __BYTE_ORDER == __BIG_ENDIAN
 106         i = h->u32[0];
 107 #else
 108         i = (uint32_t)h->uc[0] << 24;
 109         i |= (uint32_t)h->uc[1] << 16;
 110         i |= (uint32_t)h->uc[2] << 8;
 111         i |= (uint32_t)h->uc[3];
 112 #endif
 113         i = ((i & 0x0f0f0f0f) << 4) | ((i >> 4) & 0x0f0f0f0f);
 114         return passwdqc_filter_wrap(i, m);
 115 }
 116
 117 static force_inline passwdqc_filter_f_t passwdqc_filter_h2f(passwdqc_filter_hash_t *h)
 118 {
 119 #if defined(__BYTE_ORDER) && __BYTE_ORDER == __LITTLE_ENDIAN
 120         return h->u64[1];
 121 #else
 122         uint64_t f;
 123         f = (uint64_t)h->uc[8];
 124         f |= (uint64_t)h->uc[9] << 8;
 125         f |= (uint64_t)h->uc[10] << 16;
 126         f |= (uint64_t)h->uc[11] << 24;
 127         f |= (uint64_t)h->uc[12] << 32;
 128         f |= (uint64_t)h->uc[13] << 40;
 129         f |= (uint64_t)h->uc[14] << 48;
 130         f |= (uint64_t)h->uc[15] << 56;
 131         return f;
 132 #endif
 133 }
 134
 135 static force_inline passwdqc_filter_i_t passwdqc_filter_alti(passwdqc_filter_i_t i, passwdqc_filter_f_t f, passwdqc_filter_i_t m)
 136 {
 137 /*
 138  * We must not use more than 33 bits of the fingerprint here for consistent
 139  * behavior in case the fingerprint later gets truncated.
 140  */
 141         int64_t alti = (int64_t)(m - 1 - i) - passwdqc_filter_wrap((uint32_t)f, m);
 142 #if 0
 143 /*
 144  * This is how we could have made use of the 33rd bit while staying in range,
 145  * but testing shows that this is unnecessary.
 146  */
 147         alti -= ((f >> 32) & 1);
 148 #endif
 149         if (alti < 0)
 150                 alti += m;
 151 #if 0
 152         assert((passwdqc_filter_i_t)alti < m);
 153 #endif
 154         return (passwdqc_filter_i_t)alti;
 155 }
 156
 157 static inline unsigned int passwdqc_filter_ssdecode(unsigned int src)
 158 {
 159         /* First 16 tetrahedral numbers (n*(n+1)*(n+2)/3!) in reverse order */
 160         static const uint16_t tab4[] = {816, 680, 560, 455, 364, 286, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1};
 161         /* First 16 triangular numbers (n*(n+1)/2!) in reverse order */
 162         static const uint8_t tab3[] = {136, 120, 105, 91, 78, 66, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1};
 163
 164         unsigned int dst, i = 0;
 165
 166         while (src >= tab4[i])
 167                 src -= tab4[i++];
 168         dst = i << 12;
 169
 170         while (src >= tab3[i])
 171                 src -= tab3[i++];
 172         dst |= i << 8;
 173
 174         while (src >= 16 - i)
 175                 src -= 16 - i++;
 176         dst |= i << 4;
 177
 178         dst |= i + src;
 179
 180         return dst;
 181 }
 182
 183 static force_inline int passwdqc_filter_unpack(passwdqc_filter_unpacked_t *dst, const passwdqc_filter_packed_t *src,
 184     const uint16_t *ssdecode)
 185 {
 186         uint64_t hi = src->hi, f = src->lo;
 187         unsigned int ssi = hi >> (64 - 12); /* semi-sort index */
 188
 189         if (likely(ssi - 1 < 3876)) {
 190                 passwdqc_filter_f_t ssd = ssdecode ? ssdecode[ssi - 1] : passwdqc_filter_ssdecode(ssi - 1);
 191                 const unsigned int fbits = 33;
 192                 const unsigned int lobits = fbits - 4;
 193                 const passwdqc_filter_f_t lomask = ((passwdqc_filter_f_t)1 << lobits) - 1;
 194                 dst->slots[0] = (f & lomask) | ((ssd & 0x000f) << lobits);
 195                 f >>= lobits;
 196                 dst->slots[1] = (f & lomask) | ((ssd & 0x00f0) << (lobits - 4));
 197                 f >>= lobits;
 198                 f |= hi << (64 - 2 * lobits);
 199                 dst->slots[2] = (f & lomask) | ((ssd & 0x0f00) << (lobits - 8));
 200                 f >>= lobits;
 201                 dst->slots[3] = (f & lomask) | ((ssd & 0xf000) << (lobits - 12));
 202                 return 4;
 203         }
 204
 205         if (likely(hi <= 1)) {
 206                 if (!hi)
 207                         return unlikely(f) ? -1 : 0;
 208
 209                 dst->slots[0] = f;
 210                 return 1;
 211         }
 212
 213         if (likely((ssi & 0xf80) == 0xf80)) {
 214                 const unsigned int fbits = 41;
 215                 const passwdqc_filter_f_t fmask = ((passwdqc_filter_f_t)1 << fbits) - 1;
 216                 dst->slots[0] = f & fmask;
 217                 f >>= fbits;
 218                 f |= hi << (64 - fbits);
 219                 dst->slots[1] = f & fmask;
 220                 if (unlikely(dst->slots[0] < dst->slots[1]))
 221                         return -1;
 222                 f = hi >> (2 * fbits - 64);
 223                 dst->slots[2] = f & fmask;
 224                 if (unlikely(dst->slots[1] < dst->slots[2]))
 225                         return -1;
 226                 return 3;
 227         }
 228
 229         if (likely((ssi & 0xfc0) == 0xf40)) {
 230                 const unsigned int fbits = 61;
 231                 const passwdqc_filter_f_t fmask = ((passwdqc_filter_f_t)1 << fbits) - 1;
 232                 dst->slots[0] = f & fmask;
 233                 f >>= fbits;
 234                 f |= hi << (64 - fbits);
 235                 dst->slots[1] = f & fmask;
 236                 if (unlikely(dst->slots[0] < dst->slots[1]))
 237                         return -1;
 238                 return 2;
 239         }
 240
 241         return -1;
 242 }
 243
 244 static inline int passwdqc_filter_f_eq(passwdqc_filter_f_t stored, passwdqc_filter_f_t full, unsigned int largest_bucket_size)
 245 {
 246         if (likely((uint32_t)stored != (uint32_t)full))
 247                 return 0;
 248 /*
 249  * Ignore optional high bits of a stored fingerprint if they're all-zero,
 250  * regardless of whether the fingerprint possibly came from a large enough slot
 251  * for those zeroes to potentially be meaningful.  We have to do this because
 252  * the fingerprint might have been previously stored in a larger (smaller-slot)
 253  * bucket and been kicked from there, in which case the zeroes are meaningless.
 254  * Exception: we don't have to do this if there were no larger buckets so far.
 255  */
 256         if ((stored >> 33) || largest_bucket_size < 4) {
 257                 if ((stored >> 41) || largest_bucket_size < 3) {
 258                         if (stored >> 61)
 259                                 return likely(stored == full);
 260                         else
 261                                 return likely(stored == (full & (((passwdqc_filter_f_t)1 << 61) - 1)));
 262                 } else {
 263                         return likely(stored == (full & (((passwdqc_filter_f_t)1 << 41) - 1)));
 264                 }
 265         } else {
 266                 return likely(stored == (full & (((passwdqc_filter_f_t)1 << 33) - 1)));
 267         }
 268 }
 269
 270 static inline void passwdqc_filter_md4(passwdqc_filter_hash_t *dst, const char *src)
 271 {
 272         MD4_CTX ctx;
 273         MD4_Init(&ctx);
 274         MD4_Update(&ctx, src, strcspn(src, "\n\r"));
 275         MD4_Final(dst->uc, &ctx);
 276 }
 277
 278 static inline void passwdqc_filter_ntlm_cp1252(passwdqc_filter_hash_t *dst, const char *src)
 279 {
 280 /*
 281  * 5 of these codes are undefined in CP1252.  We let the original single-byte
 282  * values for them pass through, which appears to match how the HIBP v7 NTLM
 283  * hashes were generated.
 284  */
 285         static const uint16_t c1[] = {
 286                 0x20ac, 0x81, 0x201a, 0x0192, 0x201e, 0x2026, 0x2020, 0x2021,
 287                 0x02c6, 0x2030, 0x0160, 0x2039, 0x0152, 0x8d, 0x017d, 0x8f,
 288                 0x90, 0x2018, 0x2019, 0x201c, 0x201d, 0x2022, 0x2013, 0x2014,
 289                 0x02dc, 0x2122, 0x0161, 0x203a, 0x0153, 0x9d, 0x017e, 0x0178
 290         };
 291
 292         MD4_CTX ctx;
 293         MD4_Init(&ctx);
 294         while (*src != '\n' && *src != '\r' && *src) {
 295                 unsigned int c = *(unsigned char *)src++;
 296                 if (c - 128 < sizeof(c1) / sizeof(c1[0]))
 297                         c = c1[c - 128];
 298 #if defined(__BYTE_ORDER) && __BYTE_ORDER == __LITTLE_ENDIAN
 299                 MD4_Update(&ctx, &c, 2);
 300 #else
 301                 uint8_t ucs2[2] = {c, c >> 8};
 302                 MD4_Update(&ctx, ucs2, 2);
 303 #endif
 304         }
 305         MD4_Final(dst->uc, &ctx);
 306 }
 307
 308 #endif /* PASSWDQC_FILTER_INTERNALS */
 309 #endif /* PASSWDQC_FILTER_H__ */