"Fossies" - the Fresh Open Source Software Archive

Member "passwdqc-2.0.3/passwdqc_filter.h" (23 Jun 2023, 9384 Bytes) of package /linux/privat/passwdqc-2.0.3.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "passwdqc_filter.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.0.2_vs_2.0.3.

    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 #if !defined(_MSC_VER) && !defined(__APPLE__)
   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__ */