Security record: bcrypt

The record of nish/crypto/bcrypt (#873): bcrypt password hashing, $2b$ out and $2a$, $2b$, $2y$ in. It sets down what the reference implementations do with each kind of key before the module was written, the choices the module makes where they differ, what the module wipes and what no wipe reaches, and the test that pins each property. It is written with the code rather than after an audit, so that the audit starts from evidence.

Anchors are function names in std/crypto/bcrypt.ts on the head that merges this record.

Result. For every password, salt and cost tried, the module makes the hash libxcrypt's crypt_r makes, crypt_r accepts the hash the module makes, and the module answers every well-formed $2a$, $2b$ and $2y$ verify as crypt_r does, NULs, 8-bit bytes and passwords past 72 bytes included (a hash string that is not 60 characters, or has a digest character outside the alphabet, is an Err here, where crypt_r reports a mismatch).

The password is only read inside exposeWith; the Blowfish state, the expanded key, the key stream, the block and the digest are wiped by stores opt -O2 keeps, and so are the hash the verify rebuilds from the password and the given hash's bytes it compares that with; the verify compares the whole 60-character hash in constant time.

Two things are not reached, by the nature of the algorithm or of the language, and are recorded: the secret-indexed S-box loads (BCRYPT-6) and registers and spills (BCRYPT-7). Nothing was found to fix or left open. Where the implementations a hash travels between answer differently, the interoperability table is the one place that says who answers what; the module departs from crypt_r on three rows of it, $2x$, a hash string of the wrong length and a digest character outside the alphabet.

The batch, bcryptHashN and bcryptVerifyN for one to six passwords and bcryptHash4 and bcryptVerify4 for up to four, gives each lane the single path's answer byte for byte, so every row of that table holds for it lane by lane. Its state is one Secret<u32[]>, wiped by a store opt -O2 keeps, as are its digests and, in the verify, each lane's rebuilt hash and given hash's bytes; the ways it can differ from single calls (null lanes, a malformed lane, lanes of different costs) are set down in The batch. bcryptCalibrate, which picks a width by timing throwaway passwords, handles no secret of the caller's (BCRYPT-10).

The login batcher, nish/crypto/bcrypt-batch in std/crypto/bcrypt-batch.ts, queues verifies and hashes and runs them as those batches on one std/threads task per core. It keeps its own copy of each queued password in a holder whose one field is a Secret, and wipes the copy on the calling thread once the scope that read it has joined. Every answer is the one bcryptVerify or bcryptHash would give; a damaged stored hash answers its Err on its own row. What it leaves unwiped is a batcher dropped with requests still queued (BCRYPT-11). See The login batcher.

Scope

File Functions
std/crypto/bcrypt.ts bcryptHash, bcryptVerify; bcryptHashInto, bcryptHashExposed, bcryptVerifyExposed, bcryptSameWiped, bcryptVerifyOne, bcryptExposed, bcryptKeySchedule, bcryptSetKey, bcryptInitState, bcryptEncrypt, bcryptBody, bcryptXorKey, bcryptXorSalt, bcryptStore, bcryptMagic, bcryptPutBlock; bcryptParse, bcryptDecodeSalt, bcryptSaltWords, bcryptSettingOf, bcryptEncode, bcryptEncodeInto, bcryptPut, bcryptCharOf, bcryptSextetOf, bcryptParseHash; the batch: bcryptHashN, bcryptVerifyN, bcryptHash4, bcryptVerify4, bcryptVerifyGroup, bcryptLoadN, bcryptLoadSlot, bcryptHashNExposed, bcryptVerifyNExposed, bcryptMaskOf, bcryptSlotsOf, bcryptInitN, bcryptKeyWord, bcryptLoadLane (and its six bcryptLoadLane0–5), bcryptEksN, bcryptBodyN, bcryptBody2–bcryptBody6, bcryptEncryptAt, bcryptXorKeyN, bcryptXorSaltN, bcryptExpandAt, bcryptMagicAt, bcryptSaltOf, bcryptBatchSalt, bcryptJoin, bcryptLaneString, bcryptLaneOk, bcryptJoinedOk, bcryptBytesOf; the calibration: bcryptCalibrate, bcryptCalibrateTime, bcryptCalibrateKey
std/crypto/bcrypt-batch.ts bcryptBatcher; BcryptBatcher (verify, hash, enqueue, pending, waitNanos, run, orderOf, compact); BcryptBatchKey (and its wipe), bcryptBatchTake, bcryptBatchFill, bcryptBatchCopy, bcryptBatchLengthOf; BcryptBatchShare, bcryptBatchShareRun, bcryptBatchOfKind, bcryptBatchLane, bcryptBatchVerifyRun, bcryptBatchVerifyLanes, bcryptBatchVerifyAlone, bcryptBatchHashRun, bcryptBatchHashLanes; bcryptBatchCostOf, bcryptBatchLines, bcryptBatchAnswerOf; BcryptAnswer, BcryptBatchConfig

Out of scope: timingSafeEqual (std/crypto/ct.ts, in crypto-k1.md), the Secret rules the checker enforces (secret.md), where the salt comes from (the caller's CSPRNG), and how a program stores hashes or rate-limits guesses.

A std/threads task may call bcryptHash and bcryptVerify: everything they wipe is an array the call made itself, which a task may wipe (tests/link/thread_task_wipe), and a task hashing a password its parent owns is tests/link/thread_bcrypt_task. It may call the batch too (tests/link/thread_bcrypt_batch, BCRYPT-9): the batch's state is a Secret made with secret(...) from an array the call made, which a task may wipe.

Threat model

Two attackers. The first holds a stolen hash and wants the password: bcrypt's cost is the defence, and a win here is a hash cheaper to test than the reference's, or one that verifies a password it should not. The second can call bcryptVerify with any hash string and password and time it, or read the process's memory after a call returns: a win is a panic, a hash string that reads past its bytes, a verify whose time follows how many characters matched, or the password, or the state derived from it, left in memory.

The reference's behaviour

The references are Solar Designer's crypt_blowfish 1.3 (the code the module adapts) and libxcrypt's crypt_r, which uses crypt_blowfish. The module answers as they do on every input in the table below but $2x$, a hash string of the wrong length and a digest character outside the alphabet. How a hash is built:

Input What crypt_blowfish and crypt_r do What the module does
The key bytes The password as a C string, its terminating NUL included, cycled until the 18 P words (72 bytes) are filled. The same.
A password of 72 bytes or more The first 72 bytes are used under every prefix; the terminating NUL is not reached, and the rest is ignored. The same (BCRYPT-1).
An embedded NUL The key ends at it: C reads a string to its first NUL, so ab\0cd is the key of ab. The same (BCRYPT-2).
8-bit bytes, $2b$ and $2y$ Read unsigned. The same.
8-bit bytes, $2a$ The countermeasure: the key is also built with sign-extended bytes, as the old bug built it; if an 8-bit byte was sign-extended into a word and yet the two keys come out equal, bit 16 of P[0] is flipped, so the $2a$ digest of such a password (\xff\xff\xa3) is not its $2y$ one. It fires only for an 8-bit byte after the first byte of some key word with only 0xff bytes before it in that word, every such byte in all 18 words being so placed (\xff\xa3345 is not: its $2a$ digest is its $2y$ one); UTF-8 never holds such a key. The same (BCRYPT-3).
$2x$ Hashed with the bug, for old hashes. Refused (BCRYPT-3).
The salt's last character It carries 2 bits of the 128; the 4 low bits of its sextet are dropped, and the hash made is written with them cleared. The same; a hash string with them set verifies false, as crypt_r's whole-string compare does (BCRYPT-4).
A cost outside 04–31, a bad prefix or salt character Refused (*0/*1). An Err naming it (BCRYPT-5).
A hash string that is not 60 characters A mismatch: the recomputed string differs. An Err (BCRYPT-5).
A digest character outside the alphabet A mismatch: the recomputed string differs. An Err (BCRYPT-5).

Interoperability

What each implementation answers for the inputs where any two of them differ. Every other input (a password of up to 72 bytes with no NUL, under $2b$, or under $2a$ that does not set off the countermeasure, which takes an 8-bit byte after the first byte of a key word with only 0xff bytes before it) hashes alike in all four.

The sources: libxcrypt as packaged here, built with its $2a$, $2y$ and $2x$ hashes (they are a build option, --enable-hashes, and tests/differential/bcrypt.js assumes a build with $2a$ and $2y$), with crypt_blowfish 1.3's wrapper.c; OpenBSD's lib/libc/crypt/bcrypt.c 1.58 (openbsd/src 65a9769f7625, the file bench/crypto/bcrypt/run.mjs fetches); Go's golang.org/x/crypto/bcrypt v0.58.0. Line numbers are in those files.

Input This module libxcrypt, crypt_blowfish OpenBSD bcrypt.c Go x/crypto
8-bit bytes under $2a$, each one after a key word's first byte with only 0xff bytes before it in the word (\xff\xff\xa3; not \xff\xa3345, whose hashes agree in all four) The countermeasure. The countermeasure. None: the $2a$ digest is the $2y$/$2b$ one, so its hash of such a password verifies false here ("and is not the $2y$ digest under $2a$"). None, as OpenBSD.
An embedded NUL The key ends at it. The key ends at it. The key ends at it (strlen, lines 118 and 125). The whole slice and one NUL are the key (line 226), so ab\0cd is not ab: a Go hash of a password with a NUL verifies false here.
More than 72 bytes, hashing The first 72. The first 72. The first 72 (bcrypt_newhash makes $2b$, capped at line 126). Refused, ErrPasswordTooLong (line 97). Verifying reads the first 72.
More than 72 bytes, a $2a$ hash The first 72. The first 72. The length plus one is kept in a byte (line 118), so for n of 255 and up the key is the first (n + 1) mod 256 bytes of the password, with no NUL (n = 300 gives 45): the first 72 bytes only when that is 72 or more. For n of 255 to 326, 511 to 582, and every such run 256 on, it is shorter, and the hash verifies false here ("OpenBSD's $2a$ hash of 300 bytes does not verify"); elsewhere it agrees ("its $2a$ hash of 400 bytes does"). The first 72.
$2y$ Accepted, as $2b$. Accepted, as $2b$. Refused: any minor but a and b is (lines 116–131). Accepted, as $2b$.
$2x$ Refused. Hashed with the bug. Refused (lines 116–131). Accepted and hashed as $2b$, with no bug and no countermeasure (decodeVersion, line 265, takes any minor letter).
A bare $2$, no minor letter Refused (an Err). Refused. Refused: the minor switch's default (lines 116–131); older releases accepted it. Accepted, and hashed as every prefix is there (decodeVersion, line 265, reads no minor when the third character is $, line 274).
The salt's last character with its 4 low bits set Verifies false. Verifies false. Verifies false: the salt is decoded and re-encoded, and the strings differ (line 222). Verifies true: the 22 salt characters are kept as given (line 187) and the hash is rebuilt with them.
A hash string that is not 60 characters An Err. A mismatch. A mismatch (bcrypt_checkpass compares the lengths first, line 228). A mismatch (a longer string's extra characters stay in the digest compared).
A digest character outside the alphabet An Err. A mismatch. A mismatch (bcrypt_checkpass, line 222, compares the recomputed string). A mismatch (the recomputed string is compared, line 120).

The OpenBSD hashes the checks use were made by OpenBSD's own code, built from the files bench/crypto/bcrypt/run.mjs fetches into build/bench/bcrypt/openbsd-65a9769f7625/, with a ten-line vec.c that calls bcrypt(p, setting) on the password p of n bytes abc…z repeated and prints the result:

O=build/bench/bcrypt/openbsd-65a9769f7625
gcc -O2 -w -include $O/shim.h -I$O $O/bcrypt.c $O/blowfish.c vec.c -o vec
./vec 300 '$2a$04$abcdefghijklmnopqrstuu'   # ...ZhbhEFpDIPOzoWgIIoxfm98VTZSo7Ny
./vec 400 '$2a$04$abcdefghijklmnopqrstuu'   # ...p5OpK2YVWOf8zhcTL0LOco4/tHSabd2
./vec 300 '$2b$04$abcdefghijklmnopqrstuu'   # ...p5OpK2YVWOf8zhcTL0LOco4/tHSabd2

The same program gives the 400-byte digest from n = 327 on, the first length past the run, and refuses $2y$ and $2x$ settings.

The batch

bcryptHashN(p0, p1, p2, p3, p4, p5, salts, cost) and bcryptVerifyN(p0, …, p5, hashes) take lane 0 and up to five more passwords, each Secret<u8[]> | null, with 96 bytes of salt or six hash strings. bcryptHash4 and bcryptVerify4 are the same computation for up to four, with 64 bytes of salt or four strings, and keep the signatures, errors and outputs they had.

The given lanes' Blowfish encryptions run interleaved in one loop of the width given (bcryptBodyN, one of bcryptBody2 to bcryptBody6, through bcryptEncryptAt): the chains are independent, so the S-box loads of one overlap the others' and a core is not left waiting on one chain's latency. Each lane's hash is the single path's, byte for byte. The kernels other than bcryptBody4 are written out by bench/crypto/bcrypt/gen-body.mjs, whose output is the source as committed; its width 4 is bcryptBody4's text below the doc comment, and gen-body.mjs --check compares all five with the module.

One state, one wipe. A Secret cannot be stored in an array or a field, so the lanes' states cannot be several Secrets handed to one kernel. They are one Secret<u32[]> of 6366 words (BCRYPT_BATCH_WORDS): slot s's Blowfish state at 1042s, its expanded key at 6252 + 18s and its $2a$ safety word at 6360 + s. The given lanes take slots 0, 1, … in order (bcryptSlotsOf), so a batch of w lanes runs the w-wide kernel and no slot runs without a key.

bcryptHashN and bcryptVerifyGroup make the state, set it to π (bcryptInitN), load each given lane's key with one exposeWith of the state per password (bcryptLoadN, through bcryptLoadSlot and bcryptLoadLane), run the salted expansion, the 2^cost rounds and the magic string on all slots in one more (bcryptHashNExposed or bcryptVerifyNExposed, through bcryptEksN), and wipe it. The hash's exposed half returns the 60-byte hashes, which are the strings bcryptHashN returns and so are not wiped; the verify's compares each slot's rebuilt hash with the given one inside the exposure, wipes both and the digests, and returns one bit per slot.

A key word at a time. While bcryptLoadLane has the state exposed it cannot also expose the password, so it takes the key one word at a time: exposeWith(password, …, bcryptKeyWord) builds the lane's whole key schedule in a fresh array, keeps one word, wipes the array and returns the word. The schedule is built 18 times per lane (each in microseconds against a hash of milliseconds), and only a u32 leaves each call, into bcryptLoadLane's unwiped local word and then the state. That local is a register or a spill slot, which no wipe reaches (BCRYPT-7).

Null lanes. A null lane takes no slot and is not hashed. bcryptHashN gives "" for it and does not read its salt; bcryptVerifyN gives false and does not read its hash string, so a malformed string in a null lane is no error. One given lane runs as the single path, so a batch of one costs one hash and not six.

A malformed lane. bcryptVerifyN and bcryptVerify4 parse every given hash string before it hashes anything; a malformed one in any given lane makes the whole call Err("bcrypt: lane k: …"), the single path's message with the lane named. A per-lane Err was the alternative; it was not chosen because a Result<boolean[], string> can say only one thing, and folding the bad row into false would let a corrupted stored hash read as a wrong password. A caller whose rows come from storage it trusts sees the error as the corruption it is.

Costs. One kernel runs one cost. bcryptVerifyN groups the given lanes by the cost their hash names: a group of two or more runs as one interleaved computation (bcryptVerifyGroup), a group of one as bcryptVerify. Lanes of a group may carry different prefixes; each lane's safety word is its own, so a $2a$ lane gets the countermeasure beside a $2y$ one. A batch of six costs takes the time of six single verifies.

The comparison is timingSafeEqual over each lane's whole 60 characters, as in bcryptVerify; the lanes' answers do not depend on one another, and the time of the call follows only which lanes are given and the costs, all of which the caller chose.

The login batcher

std/crypto/bcrypt-batch.ts fills the batch for a server whose logins arrive one at a time. verify(password, hash, now) and hash(password, salt, now) queue a request and answer its ticket; run(now), when width requests are queued or the oldest has waited holdNanos, takes at most width × cores of them, oldest first, deals them in even contiguous shares to min(cores, taken) tasks of one scope, and answers a BcryptAnswer for each.

The taken requests are ordered verifies first, by the cost their hash names, then hashes (orderOf), so a share's requests of one kind and cost sit together, and the share calls bcryptVerifyN or bcryptHashN for each run of up to width of them.

The copy. A queued password must outlive the caller's Secret, which the checker makes the caller wipe, and a Secret cannot be an array element (NL2429). So bcryptBatchTake makes a BcryptBatchKey, a class whose one field is a readonly Secret<u8[]> of the password's length, and copies the password into it with one exposeWith inside another (bcryptBatchFill, bcryptBatchCopy): the bytes go from one exposure straight into the other and are never in an array outside a Secret. The queue is an array of these holders.

The wipe. After the scope joins, run calls wipe() on every holder it took, on the calling thread. No task can be reading a holder then: a task's reads end before its scope's join returns. The tasks themselves wipe nothing of the batcher's; they call bcryptVerifyN, bcryptHashN and, for a single lane, bcryptVerify or bcryptHash, which wipe what they make, and a task may wipe its own scratch (BCRYPT-9). The holders of a run are wiped whatever it answered, a batch Err included.

What crosses the tasks. A task answers one string, its requests' answers joined by "\n": a hash string, "1" or "0", or an error message. None is secret; a verify's answer is the bit the caller asked for, and a hash string is the public output. The passwords reach the tasks only as holders, read inside exposeWith.

A damaged stored hash makes bcryptVerifyN an Err for its whole batch, before anything is hashed. The share then verifies each lane of that batch alone with bcryptVerify, so the damaged row answers the Err and every other row the answer it would have had. The batch's choice not to fold a malformed row into false (above) holds row by row. A hash request whose salt is not 16 bytes is answered with its Err by the next run and never queued, so no copy of its password is made.

Timing. A verify's answer arrives with its batch's, so its time follows the batch: the other requests it was queued with, and their costs. Those are other users' logins, which say nothing about this password; within a batch the comparison is bcryptVerifyN's, constant-time per lane. The hold adds at most holdNanos to any request, whatever its password.

Findings

Rows BCRYPT-1 to BCRYPT-5 are the decisions a reviewer might question, each following the reference; BCRYPT-6 and BCRYPT-7 are what a wipe and a constant-time compare cannot reach; BCRYPT-8 to BCRYPT-10 are the batch's, and BCRYPT-11 the login batcher's. They are accepted, or a limitation of the language since lifted, not flaws, and none is counted as fixed or open in the index.

Id Severity Where Description Disposition
BCRYPT-1 Low bcryptSetKey A password past 72 bytes hashes as its first 72, so two passwords sharing those verify each other. Accepted. crypt_blowfish and crypt_r cut there at any length, and a hash is useful only if the reference verifies it: refusing would make a password they accept fail here, and pre-hashing it would make a hash no other implementation verifies. A program that wants long passphrases to count whole can pass an HMAC of them as the password; the guide page says so.
BCRYPT-2 Low bcryptSetKey A NUL ends the key, so ab\0cd verifies ab. Accepted. As BCRYPT-1: crypt_r takes a C string, so a hash made with the NUL kept would verify only in Go (Interoperability). Text from a form has no NUL; a program hashing raw bytes refuses one itself.
BCRYPT-3 Low bcryptSetKey, bcryptParse $2x$ hashes, made by the sign-extension bug, cannot be verified. Accepted. Verifying them means running the bug; the systems that made them were told to rehash in 2011. $2a$ keeps the countermeasure, so a $2a$ hash made with the bug verifies false rather than verifying the wrong password.
BCRYPT-4 Low bcryptDecodeSalt A hash whose last salt character has the dropped bits set verifies false for its own password. Accepted. It is crypt_r's answer: it rebuilds the string with the bits cleared and compares the whole of it. Accepting it would make a hash string that verifies here and not there. OpenBSD answers the same; Go verifies such a string true, since it keeps the salt characters as given (Interoperability).
BCRYPT-5 Low if it failed bcryptVerify, bcryptParse A hash string of any length or bytes must not panic or read past itself. Holds. The length is checked to be 60 first; every character after that is read at an index below 60 and checked against the alphabet, each refusal an Err.
BCRYPT-6 Low bcryptEncrypt Each Blowfish round loads four S-box words at indexes taken from the secret state, so the cache lines touched follow the password. Accepted. It is the algorithm: every bcrypt does it, and the expensive key setup that is bcrypt's point is made of these loads. A local attacker sharing a cache with the hashing core could in principle learn about the state; a remote one times a cost-10 hash of ~50 ms, against which the loads' variance is noise. The key schedule (bcryptSetKey) does not branch on a password byte's value, but the copy's trip count follows the password's length (up to 72), and the cycle position p of the key[p & 0x7f] loads restarts at its first NUL (or at 72), so which of the 128-byte key array's two cache lines each load touches follows the length up to that NUL. A local attacker who can watch those lines learns the length (to within the line split), not a byte; C implementations walk a C string the same way. The base64 that encodes the digest (bcryptCharOf, bcryptSextetOf) is branchless, since the digest is the stored hash when the password is right, and the verify's compare is constant-time.
BCRYPT-7 Low bcryptExposed, bcryptHashExposed, bcryptKeyWord, bcryptLoadLane, bcryptHashNExposed Values the generated code holds in registers, and any it spills to the stack, are not wiped; nor is the caller's own copy of the password before it became a Secret. Accepted. No store from the language reaches a register or a spill slot (as AEAD-4 for the AES kernels). Every array holding key material is wiped, and so is every array the verify makes: the hash bcryptVerifyExposed rebuilds and the given hash's bytes, and in the batch the digests and each lane's joined and given hash (bcryptJoinedOk), all through bcryptSameWiped, since a rebuilt hash is a crackable hash of whatever password was tried. The hash paths' 60 bytes (bcryptHashExposed, the batch's all from bcryptHashNExposed) are not wiped: they are the hash strings bcryptHash, bcryptHashN and bcryptHash4 return, public by design, and the strings themselves are the caller's. The Secret the caller passes is the caller's to wipe, and the checker makes it do so. The batch's 19 key words per lane each pass through bcryptLoadLane's word, an unwiped u32 local, on their way from bcryptKeyWord's wiped array into the state: a register, or a spill slot if the code generator spills it, which no wipe reaches; the same reach as a round's working values.
BCRYPT-8 Low bcryptEksN, bcryptSlotsOf A null lane, or a lane of another cost in a verify group, ran through the four-lane kernel with π and no key, and its digest was computed and dropped. Superseded. It was accepted, since nothing secret was in such a lane and its digest was wiped with the rest. Now the given lanes take consecutive slots (bcryptSlotsOf) and the kernel is as wide as they are, so no slot runs without a key: three lanes of a four-lane call run bcryptBody3. Pinned by link/crypto_bcrypt_width's "hashN, width w, lanes m" lines, whose lane masks m leave gaps (lanes 33 is lanes 0 and 5, run in slots 0 and 1), each lane equal to bcryptHash.
BCRYPT-9 Low bcryptHash4, bcryptVerify4 The batch could not run in a std/threads task: a task calling bcryptHash4 was refused, "hashFour writes memory its caller can see through bcryptHash4". Closed: the language limitation is lifted. A task may now wipe a Secret it made with secret(...) from a fresh value (secret.md, LANGUAGE.md NL2471), and bcryptVerify4 no longer counts as writing the caller's hashes: handing a string element to a call writes nothing, since a string has no slot a callee can store into. Before: tests/link/thread_bcrypt_batch_refused, refused. After: tests/link/thread_bcrypt_batch runs bcryptHash4 and bcryptVerify4 on two tasks under NISH_NUM_THREADS of 1, 2 and 8, and checks the hashes against bcryptHash. The analysis as it stood: the batch made its state with secret(new Array…) and wipes it; the task rule counts that wipe as a shared write: threads.md and LANGUAGE.md (NL2471) say a wipe of a Secret made with secret(...) is a write to memory the caller can see, since the rule does not follow a fresh array through secret(…). The way round it costs more than it buys: a plain u32[] state would hold every lane's key schedule and S-boxes outside a Secret and outside expose, where the checker no longer makes each use go through exposeWith nor makes the function wipe it, and a zeroing loop in place of the wipe is a store opt -O2 may drop. The language change it needs: a Secret made by secret(e) from a fresh allocation e that the function neither returns nor stores is the function's own scratch, as the fresh array is, so its wipe and its exposeWith writes are local writes. That is the change made.
BCRYPT-10 Low bcryptCalibrate, bcryptCalibrateTime The width a program runs follows a clock, so it differs between machines, between runs and with the load at startup. Accepted. The width changes only the speed: every width gives each lane the single path's hash byte for byte (BCRYPT-8's test, and the differential at widths 2 to 6), so a hash made at one width verifies at any other. The calibration hashes its own one-byte throwaway passwords (bcryptCalibrateKey), wiped like any other, and an all-zero salt; it reads no caller's secret, and its running time follows only the widths and the core. It reads the clock (monotonicNanos), the one function of the module that does.
BCRYPT-11 Low BcryptBatcher.run, bcryptBatchTake The batcher keeps a copy of each queued password until its request has run; a batcher dropped with requests still queued leaves those copies to the allocator unwiped. Accepted. The copy is what lets the caller wipe its own Secret at once, as after bcryptVerify, and every copy is wiped by the run that takes it, after the scope joins (tests/link/thread_bcrypt_batcher). Nish has no destructor to wipe a dropped object's fields, so the module documents the rule instead: call run until pending() is 0 before dropping a batcher. A server that runs while it accepts logins never holds more than the requests of one hold window and one run.

Properties verified

Each property below is pinned by a test that fails if it stops holding. The module's own checks are lines of tests/link/crypto_bcrypt/expected.out, which link/crypto_bcrypt: exits with 0 and stdout matches expected.out compares byte for byte; the same program under --number-mode f64 is link/crypto_bcrypt_f64: exits with 0 and stdout matches expected.out.

The reference's answers (crypt_blowfish's wrapper.c and libxcrypt's vectors): "UU", "UU*", "UUU", "the empty password", "72 bytes of \xaa, then more", "\xaa\x55 36 times", "\x55\xaa\xff 24 times", "hash UU at cost 4", "hash U at cost 4", "hash U*V at cost 4", "hash the empty password at cost 5", "hash ab".

Against crypt_r, both ways, on random inputs: bcrypt differential: Nish and libxcrypt crypt_r agree on random passwords and salts, both ways (tests/differential/bcrypt.js): 48 seeded cases of 0 to 309 bytes over every byte value at cost 4 to 6 or 10, of which 7 hold a NUL, 31 an 8-bit byte, 11 run past 72 bytes and 3 past 255, and 1 is at cost 10.

A separate one-line link test decides the skip, so a harness that does not build fails. Each passes when the module's $2b$ hash is crypt_r's, crypt_r accepts it, and the module verifies crypt_r's $2a$, $2b$ and $2y$ hashes and refuses a wrong password as crypt_r does. Without a C compiler or libxcrypt it skips, saying which.

Hashes from Go (golang.org/x/crypto v0.58.0): "the Go seed hash verifies" (the $2a$10$ hash github.com/arjaythedev/multicore-server-challenge seeds at c3012257f2ee), "and not under another password", "Go, cost 10", "Go, cost 4", "Go, a passphrase". "hash at cost 10" is a $2b$10$ known answer from crypt_r. OpenBSD's tree has no libc bcrypt regress (regress/lib/libutil/bcrypt_pbkdf only), so crypt_blowfish's wrapper.c table is the published vector set.

The 72-byte cut and the NUL (BCRYPT-1, BCRYPT-2): "a key past 72 bytes: the rest is ignored", "hash a 72-byte password at cost 6", "a 73rd byte changes nothing", "200 x hash as 72", "72 x", "255 x hash as 72 under $2b$", "256 x", "300 x", "255 x verify as 72 under $2a$", "256 x under $2a$", "300 x under $2a$", "OpenBSD's $2a$ hash of 300 bytes does not verify", "its $2a$ hash of 400 bytes does", "and so does its $2b$ hash of 300 bytes", "ab\0cd hashes as ab: the key ends at its first NUL", "and verifies as ab".

8-bit bytes and the sign-extension bug (BCRYPT-3): "$2y$ \xff\xff\xa3", "$2b$ \xff\xff\xa3 is $2y$'s digest", "$2a$ \xff\xff\xa3 takes the countermeasure", "and is not the $2y$ digest under $2a$", "$2a$ \xa3 (one 8-bit byte: no countermeasure needed)", "$2y$ \xa3", "$2b$ \xa3", "$2a$ \xff\xa3345", "$2y$ \xff\xa3345", "$2a$ \xff\xa334\xff\xff\xff\xa3345", "$2y$ \xff\xa334\xff\xff\xff\xa3345", "$2a$ \xa3ab", "$2y$ \xa3ab", "hash \xa3", "hash \xff\xa334\xff\xff\xff\xa3345", "$2x$ \xa3 is refused", "$2x$ \xd1\x91 is refused".

The salt's last character (BCRYPT-4): "the canonical last salt character verifies", "one with dropped bits set does not, as with crypt_r".

Verify and refusals (BCRYPT-5): "a hash verifies under its own password", "and not under another", "nor under the empty password", "cost 3 is refused", "cost 32 is refused", "a 15-byte salt is refused", "a 17-byte salt is refused", "a 59-character hash is refused", "a 61-character hash is refused", "the empty string is refused", "$2c$ is refused", "$3b$ is refused", "a cost that is not two digits is refused", "cost 03 is refused", "cost 32 in a hash is refused", "a salt character outside bcrypt base64 is refused", "a digest character outside bcrypt base64 is refused".

The Secret boundary: a plain u8[] password does not compile (reject_bcrypt_plain_password: rejected with "Argument 1 of \nish.bcryptHash`: expected Secret<u8[]>, got u8[]"), nor does a program that leaves the Secret it passed unwiped (reject_bcrypt_password_not_wiped: rejected with "that this exit leaves neither wiped nor returned"), nor one that drops a verify's answer (reject_bcrypt_result_dropped: rejected with "`Result<boolean, string>` must be handled, not discarded"`).

The wipes survive -O2: crypto: the wipes survive opt -O2 (bcrypt's Blowfish state, expanded key, key stream, block, digest, rebuilt and given hash in bcryptVerifyExposed) (tests/wipes/crypto.js) counts the volatile wipes reached after opt -O2 from bcryptHashInto and bcryptHash (five: bcryptExposed's, inlined) and from bcryptVerifyExposed and bcryptVerify (seven: those five, and the rebuilt hash and the given hash's bytes, both wiped in bcryptSameWiped). Turning either of those two wipes into fill(0) drops the verify's two to six.

The batch (tests/link/crypto_bcrypt_batch, whose lines are compared by link/crypto_bcrypt_batch: exits with 0 and stdout matches expected.out): "hash4, null lanes 0" to "hash4, null lanes 14", every null pattern with lane 0 given, each the same four strings as four bcryptHash calls (a null lane ""); "hash4, four lanes, round 0" to "round 5", random passwords of 0 to 80 bytes, NULs and repeats among them; "verify4: crypt_blowfish's and Go's vectors, costs 5, 5, 4, 5" (the \xff\xff\xa3 $2a$ vector in lane 1, so the countermeasure runs in a lane); "verify4 = verify, null lanes 0" to "14"; "verify4: a wrong password is false in its lane only"; "verify4 = verify, mixed costs, round 0" to "round 2" (costs 4 and 6, $2a$, $2b$ and $2y$ in one call); and the refusals "63 bytes of salt are refused", "cost 3 is refused", "a malformed lane is an Err naming it", "and is not read when the lane is null", "a batch is four hashes".

The widths (tests/link/crypto_bcrypt_width, compared by link/crypto_bcrypt_width: exits with 0 and stdout matches expected.out): "hashN, width w, lanes m, cost c" for widths 2 to 6, costs 4 to 8 and 10, and lane masks m with gaps, each lane the string bcryptHash makes and a null lane ""; "hashN, lane 0 alone"; "verifyN = verify, width w, lanes m" and "verifyN = verify, lane 5 wrong, width w" for widths 1 to 6; "verifyN: crypt_blowfish's vector in all six lanes"; "a malformed lane k is an Err naming it" for each of lanes 0 to 5, and "and is not read when lane k is null"; the refusals "95 bytes of salt are refused", "cost 3 is refused", "cost 32 is refused", "a batch is six hashes"; and "bcryptCalibrate answers 1 to 6" and, called again, "and again".

bcrypt differential: Nish and libxcrypt crypt_r agree on random passwords and salts, both ways runs its cases again through bcryptHashN and bcryptVerifyN in batches of widths 6 down to 2, every lane checked against crypt_r both ways.

The batch's wipes survive -O2: crypto: the wipes survive opt -O2 (bcrypt's batch state, key words, block, digests, joined and given hashes in bcryptVerify4Exposed) (a name kept from the four-lane batch) counts the volatile wipes reached from bcryptKeyWord (2), bcryptEksN (2), bcryptLoadN (4), bcryptHashNExposed (3), bcryptVerifyNExposed (5), bcryptHashN (13), bcryptVerifyN (52), bcryptHash4 (13), bcryptVerify4 (52) and bcryptCalibrateTime (19); tests/wipes/crypto.js says where each comes from.

Turning the digests' wipe into fill(0) drops each of those from bcryptHashNExposed on by one. The login batcher's copy of each password: crypto: the wipes survive opt -O2 (the bcrypt login batcher's copy of each password, in BcryptBatcher.run) counts BcryptBatcher.run's one volatile wipe, BcryptBatchKey.wipe inlined into the loop over the requests a run took.

Threads: link/thread_bcrypt_task: exits with 0 and stdout matches expected.out hashes two passwords and verifies one on three tasks, natively and under NISH_NUM_THREADS of 1, 2 and 8; link/thread_bcrypt_batch runs the batch's hash and verify on two tasks at the same sizes, and its hashes match bcryptHash's (BCRYPT-9).

link/thread_bcrypt_batcher: exits with 0 and stdout matches expected.out drives the login batcher at cost 4 under NISH_NUM_THREADS of 1, 2 and 8: the hold window and a full batch's early run, width × cores per run, a damaged stored hash answering its Err on its own row while the rest of its batch answers as it would have, a salt of the wrong length answered without a batch, and every answer equal to the single bcryptVerify and bcryptHash (BCRYPT-11).

The half-round's shape: bcrypt barrier: after opt -O3 all 16 of bcryptBody's half-rounds end in one XOR with the barrier's `and` (16) counts the XORs that close a half-round after the value barrier's and (The half-round's critical path).

wasm32: the module has no I/O and no C; crypto_bcrypt and crypto_bcrypt_batch build and run under WASI with the rest of std/crypto (node tests/run.js wasi), each printing its expected.out.

Speed

CPU milliseconds per cost-10 hash, single-threaded, on a 4-core x86-64 Xeon whose /proc/cpuinfo says 2.80 GHz and whose clock measures 3.1 to 3.25 GHz (machine C; the clock measured by timing a long chain of dependent xor, add and imul instructions) (node bench/crypto/bcrypt/run.mjs --rounds 9: user time of 8 hashes, median and spread of 9 interleaved rounds; a row of w lanes is the time of 8 batches over 8w; every row prints the same hash):

Implementation ms per hash
Nish bcryptHash 57.6 (56.4–59.0)
Nish bcryptHash4, four lanes 23.1 (22.0–26.4)
libxcrypt crypt_r, $2b$ 59.0 (58.0–60.1)
OpenBSD bcrypt.c, gcc -O2 61.8 (61.3–64.0)
OpenBSD bcrypt.c, clang -O2 69.6 (68.1–71.8)
tigokraft bc_hash_n, one lane, gcc -O2 -march=native 61.3 (60.3–62.9)
tigokraft bc_hash_n, four lanes, gcc -O2 -march=native 33.6 (31.1–37.0)
tigokraft bc_hash_n, one lane, clang -O2 -march=native 62.0 (61.6–68.1)
tigokraft bc_hash_n, four lanes, clang -O2 -march=native 24.6 (23.0–27.0)

The bcryptHashN rows this table held, one to six lanes, were measured on machine C and are removed. Five and six lanes did not lead there; on machine D they do. The current figures, per width, are in BMI2 and x86-64-v3, where six lanes lead.

The targets. The single path, with the half-round's order pinned (below), takes 0.98 times crypt_r's time, inside the 1.2 aimed at and level with it inside the noise; it is 6% ahead of OpenBSD's gcc build and tigokraft's one-lane gcc build, outside their spreads, and 17% ahead of OpenBSD's clang build. Four lanes, bcryptHash4, hash 2.55 times as fast per password as crypt_r on one core, past the 1.5 aimed at; on machine D (below) six lanes take 15.7 ms, 0.28 of the one-lane time, and four 19.4. Neither AMD nor AArch64 was measured: the best width there is what bcryptCalibrate answers, which is why it measures.

Cycles. A cost-10 hash encrypts 2^10 × 1042 + 713 = 1,067,721 Blowfish blocks (each of the 1 + 2 × 1024 key expansions encrypts 521, the magic string 192), so cycles per block = clock × time / 1,067,721. The bench prints 151 for the single path at cpuinfo's 2.80 GHz; at the measured 3.2 GHz it is 173, 10.8 cycles per half-round, against the 11-cycle chain one half-round waits on (below): the single path is latency-bound. crypt_r takes 177. Per lane, on machine D at its measured 3.15 GHz, the widths take 94 (2), 71 (3), 57 (4), 50 (5) and 46 (6) cycles per block.

The four-lane kernel, read. The loop of bcryptBody4 after opt -O3 and llc, from its objdump, is one round (two half-rounds) of all four lanes in 103 instructions: 40 loads (each lane's 4 S-box words and P word per half-round), no stores and no spills, and one compare and backward branch, the only branch; it runs 8 times per block, not unrolled further. It has been shortened twice, both in Cascade Lake: the first form was 123 instructions, 45 loads and 5 stores; the rotated copy made it 112, 44 (4 of them reloads of spilled values) and 4; the paired bytes made it what it is now. Checked against the suspects: no bounds check (each S-box index is masked to 0–255 and the state's length is checked once, before the loop) and no overflow check (the arithmetic is u32, which wraps); no Secret or wipe work inside the loop, which calls nothing; the lanes interleave, each lane's loads issued between the others'.

The state's slots are 1042 words, 4168 bytes, apart, not a multiple of 4096, so the lanes' S-box words at one index fall in different L1 sets, and the six-lane state, 25.5 KB, fits the 32 KB L1. Four lanes' two halves, base, counter and temporaries now fit the 16 general-purpose registers; five and six lanes still spill (4 and 9 stores a round).

Reproducing the clock and the counts. run.mjs turns times into cycles at cpuinfo's clock unless --ghz gives one, so the 3.2 GHz figures are node bench/crypto/bcrypt/run.mjs --rounds 9 --ghz 3.2. The clock is a chain of dependent one-cycle adds timed with CLOCK_MONOTONIC; on machine C it printed 3.12, 3.14 and 3.23 on three runs, with a build running beside it:

cat > clock.c <<'C'
#include <stdio.h>
#include <time.h>
int main(void) {
  unsigned long x = 1, n = 1000000000;
  struct timespec a, b;
  clock_gettime(CLOCK_MONOTONIC, &a);
  for (unsigned long i = 0; i < n; i++)
    __asm__ volatile("add %0, %0\n\tadd %0, %0\n\tadd %0, %0\n\tadd %0, %0" : "+r"(x));
  clock_gettime(CLOCK_MONOTONIC, &b);
  printf("%.2f GHz\n", 4.0 * n / ((b.tv_sec - a.tv_sec) * 1e9 + (b.tv_nsec - a.tv_nsec)));
  return (int)(x & 1);
}
C
gcc -O2 clock.c -o clock && ./clock

The four-lane loop's counts are read from the bcryptHash4 bench program. bcryptBody4 is inlined into bcryptBodyN, so the command lists every loop there, from a backward branch's target to the branch. A load is an instruction that reads memory, and a store is one that writes it:

build/nish build/bench/bcrypt/nish4.ts -o build/bench/bcrypt/nish4-g-out/ --link build/bench/bcrypt/nish4-g -g
objdump -d --no-show-raw-insn -M intel --disassemble=nish.bcryptBodyN build/bench/bcrypt/nish4-g |
  grep -P '^\s+[0-9a-f]+:\t' | awk -F'\t' '{ a = $1; sub(/^ +/, "", a); sub(/:$/, "", a); i[++n] = $2; at[a] = n }
  $2 ~ /^j/ { split($2, t, " +"); if (t[2] in at && at[t[2]] < n) { lo[++L] = at[t[2]]; hi[L] = n } }
  END { for (l = 1; l <= L; l++) { ld = st = br = 0; for (k = lo[l]; k <= hi[l]; k++) { o = i[k]; sub(/^[a-z]+ +/, "", o)
    if (o ~ /^[^,]*PTR \[/) st++; else if (o ~ /PTR \[/) ld++; if (i[k] ~ /^(j|call)/) br++ }
    print hi[l] - lo[l] + 1 " instructions, " ld " loads, " st " stores, " br " branches" } }'

It prints ten loops, a round loop with one branch and its block loop with two for each width. A width-w round loop's loads are its 10w S-box and P words plus its reloads. The round loops print 58, 169, 103, 132 and 77 instructions, with 20, 70, 40, 55 and 30 loads, for widths 2, 6, 4, 5 and 3 (58, 180, 112, 145 and 84, with 20, 72, 44, 58 and 30, before the paired bytes; 58, 188, 123, 154 and 90, with 20, 73, 45, 59 and 30, before the rotated copy).

The bounds. Per lane half-round: the latency floor is the 11-cycle chain over the w lanes (about 2.8 cycles at four, 2.2 at five), the load-port bound is 5 loads over the core's 2 load ports (2.5 cycles, 2.8 with the reloads), and issue is 15.5 instructions at 4 a cycle (3.9 cycles).

On machine C, in rows since removed, five and six lanes gained nothing on four, as a core held at a 4-wide issue bound would show. Machine D's core issues 6 a cycle and has 3 load ports: its six lanes take 2.9 cycles per lane half-round, against an issue bound of 2.6 (15.7 instructions) and a latency floor of 1.8, so there the wider kernels still gain.

Why the kernel is Nish and not C. A C kernel was the alternative, and it would be C in runtime/ holding the secret state outside the checker's Secret rules. The C to beat is the four-lane bc_hash_n of tigokraft: 33.6 ms per hash built by gcc and 24.6 (23.0–27.0) by clang, against 23.1 (22.0–26.4) for bcryptHash4. The Nish is ahead of gcc's build outside both spreads and of clang's by its median, inside the spreads; no C row beats it. The same interleave in C at five and six lanes was later built for the ceiling, and it does not beat Nish's best width either (below).

Machine B, the run that pinned the half-round's order (--rounds 9, before the widths; a nominal 2.1 GHz), for comparison:

Implementation ms per hash
Nish bcryptHash 67.8 (66.5–69.0)
Nish bcryptHash4, four lanes 24.4 (23.3–32.0)
libxcrypt crypt_r, $2b$ 68.8 (66.0–71.3)
OpenBSD bcrypt.c, gcc -O2 69.4 (66.5–70.3)
OpenBSD bcrypt.c, clang -O2 75.4 (73.0–78.5)
tigokraft bc_hash_n, one lane, gcc -O2 -march=native 71.4 (70.6–73.3)
tigokraft bc_hash_n, four lanes, gcc -O2 -march=native 35.4 (32.1–42.9)
tigokraft bc_hash_n, one lane, clang -O2 -march=native 72.3 (70.0–75.1)
tigokraft bc_hash_n, four lanes, clang -O2 -march=native 26.2 (23.1–30.2)

The single path is level with gcc's builds and crypt_r, inside the noise, and 10% ahead of OpenBSD's clang build. No bounds check is left in the round: every S-box index is masked to 0–255 and the state's length is checked once. Each half-round closes with one XOR after its last S-box add, as gcc's do and clang's do not (below). Before that order was pinned, the single path trailed gcc. Two runs of the bench, interleaved with the branch's in one session, measured 73.1 (72.0–84.1) and 74.6 (72.1–76.9) ms on main (be8e623). The branch measured 67.8 (66.5–69.0) and 68.9 (66.6–71.0) ms, 7.3% and 7.6% less, and gcc measured 68.5 to 69.6 ms across the four.

Four lanes run in the time of 1.4 single hashes, 2.8 times the single path's throughput on one core. That is level with the four-lane C of the tigokraft submission (commit c3012257f2ee, MIT; fetched by the bench, not copied) built by clang, inside its noise, and 1.45 times its gcc build.

The four-lane rows spread widely on this machine (22.0 to 34.7 ms across the session's runs), so read them as their medians' order, not their ratios. The C rows of tigokraft are built with -march=native, as its build does, so they may use any instruction this CPU has. The Nish rows (no --cpu x86-64-v3) and the other C rows are built for baseline x86-64.

The login batcher, measured

Logins a second and latency of a login server at cost 10, from light traffic to a burst (node bench/crypto/bcrypt/batcher.mjs --rounds 5). The machine is a 4-vCPU Xeon VM, Intel(R) Xeon(R) Processor @ 2.80GHz, with one thread per core as the VM shows it and 33 MiB of L3. It is the same model as machine C, whose clock measured 3.1 to 3.25 GHz; the clock was not measured again for this run.

The program is bench/crypto/bcrypt/login.ts. Each run gets the same seeded Poisson schedule of logins of "U*U" against its cost-10 hash. A login's latency runs from its scheduled arrival to its answer, so a login that waits behind a busy server is charged for the wait. Logins a second is the count over the time from the first arrival to the last answer. Three servers are compared:

  • (a) one bcryptVerify per login, on one thread;
  • (b) one bcryptVerify per login, in one single-threaded process per core, with the logins dealt round-robin as a prefork server deals them. Each process waits on the clock for its next login, and a std/threads task cannot read the clock (monotonicNanos counts as a write), so a task per core could not run this schedule; the processes are that server's equivalent. Round-robin dealing favours (b), since every process gets an even share without a queue;
  • (c) the batcher, at bcryptCalibrate()'s width with cores set to the core count, run whenever waitNanos is 0, with a hold of 0 and of 5 ms.

On one core every process is pinned to CPU 0 with taskset, where (b) is (a). The modes run in five interleaved rounds after a warm-up. A cell is the median, the range over the rounds, and in brackets the fastest round: the most logins a second, the least latency.

The noise band is the baseline timed against a byte-identical copy of its binary, (a′) on one core and (b′) on four, in the same rounds. Their medians differ by at most 1% in logins a second. In latency they differ by up to 11% at p50 (117.6 against 130.1 ms on one core at 15/s) and 10% at p99 (84.6 against 93.5 ms on four cores at 30/s). Below, a difference inside those bands is called level.

One core:

arrivals/s logins mode logins/s p50 ms p99 ms
5 48 (a) = (b) 5.6 (5.6–5.6) [5.6] 59.0 (58.2–60.6) [58.2] 187.5 (184.4–201.4) [184.4]
5 48 (a′) twin 5.6 (5.6–5.6) [5.6] 58.5 (57.8–59.9) [57.8] 184.2 (183.3–205.3) [183.3]
5 48 (c) hold 0 5.6 (5.6–5.6) [5.6] 59.0 (58.2–60.3) [58.2] 124.1 (123.5–130.1) [123.5]
5 48 (c) hold 5 ms 5.6 (5.6–5.6) [5.6] 63.7 (63.5–64.8) [63.5] 126.7 (123.9–163.2) [123.9]
10 60 (a) = (b) 8.8 (8.8–8.8) [8.8] 59.6 (59.5–63.8) [59.5] 233.0 (228.6–255.1) [228.6]
10 60 (a′) twin 8.8 (8.8–8.8) [8.8] 60.0 (58.2–60.5) [58.2] 232.3 (230.1–236.5) [230.1]
10 60 (c) hold 0 8.8 (8.8–8.8) [8.8] 59.4 (58.6–60.1) [58.6] 138.5 (129.9–145.8) [129.9]
10 60 (c) hold 5 ms 8.8 (8.8–8.8) [8.8] 64.7 (64.3–66.2) [64.3] 142.4 (141.0–165.3) [141.0]
15 90 (a) = (b) 14.1 (14.1–14.1) [14.1] 117.6 (114.9–126.2) [114.9] 485.0 (480.1–495.7) [480.1]
15 90 (a′) twin 14.1 (14.1–14.1) [14.1] 130.1 (113.5–135.1) [113.5] 511.0 (482.1–519.7) [482.1]
15 90 (c) hold 0 14.1 (14.0–14.1) [14.1] 86.5 (83.7–88.6) [83.7] 163.8 (136.7–202.1) [136.7]
15 90 (c) hold 5 ms 14.1 (14.1–14.1) [14.1] 85.1 (82.3–86.0) [82.3] 143.1 (140.9–177.7) [140.9]
30 180 (a) = (b) 16.9 (16.8–17.0) [17.0] 2484.7 (2429.4–2519.3) [2429.4] 5061.0 (4965.4–5094.1) [4965.4]
30 180 (a′) twin 16.8 (16.8–17.1) [17.1] 2465.7 (2441.5–2536.1) [2441.5] 5095.8 (4952.6–5133.2) [4952.6]
30 180 (c) hold 0 31.7 (30.0–31.9) [31.9] 122.5 (116.7–160.2) [116.7] 248.0 (230.7–604.4) [230.7]
30 180 (c) hold 5 ms 31.8 (31.6–31.9) [31.9] 129.0 (117.2–138.4) [117.2] 263.6 (213.7–332.8) [213.7]
burst 96 (a) = (b) 16.9 (16.3–17.1) [17.1] 2829.4 (2798.1–3055.3) [2798.1] 5669.1 (5609.0–5899.5) [5609.0]
burst 96 (a′) twin 17.0 (16.8–17.2) [17.2] 2831.8 (2826.1–2890.4) [2826.1] 5660.7 (5593.6–5728.0) [5593.6]
burst 96 (c) hold 0 46.0 (44.6–46.8) [46.8] 1059.7 (1038.8–1137.7) [1038.8] 2087.4 (2052.8–2154.3) [2052.8]
burst 96 (c) hold 5 ms 47.8 (43.5–49.3) [49.3] 1031.1 (944.2–1111.8) [944.2] 2006.3 (1946.1–2204.6) [1946.1]

Four cores:

arrivals/s logins mode logins/s p50 ms p99 ms
10 60 (a) 8.8 (8.8–8.8) [8.8] 60.4 (59.0–60.9) [59.0] 233.5 (229.7–255.4) [229.7]
10 60 (b) 8.8 (8.8–8.8) [8.8] 58.8 (57.9–59.3) [57.9] 70.6 (68.3–100.1) [68.3]
10 60 (b′) twin 8.8 (8.8–8.8) [8.8] 58.4 (58.2–58.8) [58.2] 69.9 (67.0–73.1) [67.0]
10 60 (c) hold 0 8.8 (8.8–8.8) [8.8] 60.0 (58.8–61.5) [58.8] 125.0 (114.1–137.8) [114.1]
10 60 (c) hold 5 ms 8.8 (8.8–8.8) [8.8] 65.0 (63.9–65.2) [63.9] 125.6 (119.7–132.3) [119.7]
30 180 (a) 16.9 (16.8–17.0) [17.0] 2499.7 (2453.2–2520.6) [2453.2] 5066.7 (4976.0–5081.7) [4976.0]
30 180 (b) 32.1 (32.1–32.1) [32.1] 59.0 (58.3–60.2) [58.3] 84.6 (80.7–89.7) [80.7]
30 180 (b′) twin 32.1 (32.1–32.1) [32.1] 59.0 (58.3–59.4) [58.3] 93.5 (79.3–102.8) [79.3]
30 180 (c) hold 0 31.8 (31.7–32.0) [32.0] 90.8 (84.4–93.2) [84.4] 134.6 (130.1–199.1) [130.1]
30 180 (c) hold 5 ms 31.8 (31.8–32.0) [32.0] 88.5 (88.0–94.5) [88.0] 133.5 (127.4–151.5) [127.4]
60 240 (a) 16.9 (16.7–17.0) [17.0] 5245.4 (5204.0–5380.9) [5204.0] 10208.5 (10136.0–10412.0) [10136.0]
60 240 (b) 60.1 (60.0–60.1) [60.1] 84.9 (79.3–93.2) [79.3] 187.5 (174.3–209.8) [174.3]
60 240 (b′) twin 60.1 (59.7–60.2) [60.2] 84.5 (80.8–84.8) [80.8] 188.5 (177.7–210.0) [177.7]
60 240 (c) hold 0 59.6 (59.5–59.9) [59.9] 103.0 (96.6–109.9) [96.6] 156.8 (144.1–166.8) [144.1]
60 240 (c) hold 5 ms 59.6 (59.5–59.9) [59.9] 103.4 (101.4–109.7) [101.4] 169.3 (141.1–202.2) [141.1]
120 240 (a) 17.0 (16.9–17.1) [17.1] 6166.7 (6159.4–6329.7) [6159.4] 12299.8 (12230.0–12385.8) [12230.0]
120 240 (b) 66.7 (61.7–67.5) [67.5] 920.6 (899.2–1017.8) [899.2] 1842.0 (1814.0–2115.7) [1814.0]
120 240 (b′) twin 66.0 (65.4–66.7) [66.7] 928.3 (907.0–946.5) [907.0] 1867.4 (1847.8–1895.8) [1847.8]
120 240 (c) hold 0 129.3 (104.7–129.9) [129.9] 168.8 (121.5–282.6) [121.5] 288.7 (172.3–591.4) [172.3]
120 240 (c) hold 5 ms 129.2 (115.7–131.3) [131.3] 172.1 (140.4–374.3) [140.4] 297.9 (262.9–519.0) [262.9]
240 240 (a) 17.0 (16.7–17.2) [17.2] 6496.7 (6415.6–6678.0) [6415.6] 13033.1 (12901.6–13325.1) [12901.6]
240 240 (b) 66.8 (65.8–67.4) [67.4] 1258.1 (1237.4–1268.7) [1237.4] 2578.8 (2571.4–2651.0) [2571.4]
240 240 (b′) twin 66.8 (66.2–67.6) [67.6] 1240.5 (1226.3–1275.0) [1226.3] 2589.7 (2556.3–2643.4) [2556.3]
240 240 (c) hold 0 143.2 (124.1–171.1) [171.1] 381.2 (252.1–506.6) [252.1] 765.6 (516.9–989.2) [516.9]
240 240 (c) hold 5 ms 153.1 (126.6–176.7) [176.7] 334.6 (227.6–572.8) [227.6] 625.4 (427.3–961.7) [427.3]
burst 96 (a) 17.1 (17.0–17.1) [17.1] 2822.8 (2786.4–2833.6) [2786.4] 5615.9 (5598.9–5654.8) [5598.9]
burst 96 (b) 66.7 (66.0–68.2) [68.2] 715.9 (701.8–731.9) [701.8] 1438.4 (1407.9–1453.8) [1407.9]
burst 96 (b′) twin 66.3 (65.5–66.9) [66.9] 727.7 (711.2–752.0) [711.2] 1448.8 (1434.0–1465.9) [1434.0]
burst 96 (c) hold 0 154.6 (114.2–172.3) [172.3] 385.9 (283.9–585.0) [283.9] 620.9 (557.3–840.4) [557.3]
burst 96 (c) hold 5 ms 151.1 (133.0–170.6) [170.6] 389.3 (346.5–427.6) [346.5] 635.3 (562.6–722.0) [562.6]

Where the batcher wins. On one core it never loses. At 5 and 10 arrivals a second its p50 is level with (a), and its p99 is two-thirds of (a)'s or less, because logins that queue behind a busy hash share the next batch. From 15/s, (a) falls behind and (c) keeps up. At 30/s, (a) answers 16.9 logins a second and (c) 31.7.

In a burst, (c) answers 46 to 48 a second, 2.7 to 2.8 times (a), with p99 at 2.1 s against 5.7 s. On four cores, at 120 arrivals a second and above, (b) saturates at 66.7 logins a second while (c) answers 129 at 120/s, 143 to 153 at 240/s and 151 to 155 in a burst: 1.9 to 2.3 times (b). Its p99 is a sixth of (b)'s at 120/s, a quarter to a third at 240/s, and under half in a burst.

Where it does not. On four cores at light load, the batcher loses to (b) on latency:

  • at 10/s, p99 is 125 ms against (b)'s 70.6, with p50 level;
  • at 30/s, p50 is 90.8 ms against 59.0 and p99 134.6 against 84.6;
  • at 60/s, p50 is 103 ms against 84.9; its p99 is better, 157 against 188, outside the band.

Logins a second are level at all three rates, since each server keeps up with the arrivals. The cause is that run blocks its thread until every share of the run has finished. A login that arrives during a run waits for that run to end, about one hash, while (b)'s other processes are idle and take it at once. The batcher does not overlap one run with the next; a batcher per process does, which is (d) below.

At saturation it scales less than (b). From one core to four, (b) goes from 16.9 to 66.7 logins a second, 3.9 times. The batcher goes from 46 to about 150, 3.3 times, and its four-core rounds spread widely (114 to 177 a second). A run lasts as long as its slowest share, and the next run's requests wait for it.

The hold. A 5 ms hold beat a hold of 0 nowhere outside the noise. At light load it adds the hold to p50: 63.7 against 59.0 ms on one core at 5/s, and 65.0 against 60.0 on four cores at 10/s. Under load the batches fill without it, from the logins that arrive during a run. A hold of 0 is the default to start from.

One batcher per process

Mode (d) is (b)'s prefork server with a batcher in every process: one process a core, the logins dealt round-robin, each process a batcher at bcryptCalibrate()'s width with cores 1 and a hold of 0 (node bench/crypto/bcrypt/batcher.mjs --rounds 3).

Each run is one share on its process's own thread, and the processes' runs overlap: a login that arrives while one process is running goes to another, as in (b), and the logins that arrive at a busy process fill its next batch, as in (c). It needs no change to the batcher or the thread surface; overlapping runs inside one process would need a task that outlives its run, which the thread surface declines (wp29 §4.2, §9).

The run below is a different VM from the tables above, Intel(R) Xeon(R) Processor @ 2.10GHz, 4 vCPUs, three rounds after a warm-up; its (c) is not the same as the table above's (in a burst 223 logins a second against 155), so compare (d) only with the (b) and (c) of this run. The noise band, (b) against (b′): at most 2% in logins a second, 4% at p50 (83.5 against 80.1 ms at 60/s) and 11% at p99 (198.5 against 178.4 ms at 60/s). Four cores:

arrivals/s logins mode logins/s p50 ms p99 ms
10 60 (b) 8.8 (8.8–8.8) [8.8] 58.6 (58.3–64.5) [58.3] 73.2 (66.0–101.1) [66.0]
10 60 (b′) twin 8.8 (8.8–8.8) [8.8] 58.2 (58.2–64.4) [58.2] 68.3 (66.7–74.6) [66.7]
10 60 (c) hold 0 8.8 (8.8–8.8) [8.8] 60.7 (59.3–66.3) [59.3] 120.5 (113.2–130.6) [113.2]
10 60 (d) hold 0 8.8 (8.8–8.8) [8.8] 60.1 (58.1–60.8) [58.1] 66.7 (65.5–73.8) [65.5]
30 180 (b) 32.1 (32.1–32.1) [32.1] 58.4 (58.3–59.8) [58.3] 84.9 (79.3–87.4) [79.3]
30 180 (b′) twin 32.1 (32.1–32.1) [32.1] 58.6 (58.1–58.6) [58.1] 82.6 (82.4–85.3) [82.4]
30 180 (c) hold 0 31.9 (31.8–31.9) [31.9] 86.6 (84.7–91.4) [84.7] 127.5 (124.3–145.1) [124.3]
30 180 (d) hold 0 32.1 (32.1–32.1) [32.1] 58.5 (58.4–58.5) [58.4] 85.1 (78.6–85.8) [78.6]
60 240 (b) 60.1 (59.9–60.1) [60.1] 83.5 (78.5–88.2) [78.5] 198.5 (176.4–203.1) [176.4]
60 240 (b′) twin 60.1 (60.1–60.2) [60.2] 80.1 (75.8–80.1) [75.8] 178.4 (175.5–182.7) [175.5]
60 240 (c) hold 0 59.6 (59.5–59.6) [59.6] 94.8 (93.6–101.0) [93.6] 139.4 (132.4–147.6) [132.4]
60 240 (d) hold 0 60.1 (60.1–60.1) [60.1] 68.7 (64.4–69.4) [64.4] 123.1 (120.2–123.2) [120.2]
120 240 (b) 66.5 (66.5–67.8) [67.8] 921.2 (902.2–943.2) [902.2] 1849.4 (1806.8–1861.2) [1806.8]
120 240 (b′) twin 67.8 (66.8–68.3) [68.3] 910.7 (884.3–923.9) [884.3] 1805.0 (1775.3–1854.9) [1775.3]
120 240 (c) hold 0 131.5 (129.2–132.4) [132.4] 116.0 (115.9–120.0) [115.9] 157.1 (154.3–157.5) [154.3]
120 240 (d) hold 0 130.7 (130.0–131.3) [131.3] 100.3 (100.2–102.7) [100.2] 142.6 (139.9–144.5) [139.9]
240 240 (b) 67.2 (66.5–67.6) [67.6] 1238.1 (1234.8–1276.4) [1234.8] 2575.9 (2566.8–2616.6) [2566.8]
240 240 (b′) twin 67.0 (65.0–67.9) [67.9] 1238.9 (1229.8–1278.1) [1229.8] 2588.3 (2558.1–2666.8) [2558.1]
240 240 (c) hold 0 193.2 (185.8–198.8) [198.8] 174.7 (173.5–235.3) [173.5] 350.8 (284.6–377.6) [284.6]
240 240 (d) hold 0 196.7 (195.2–204.2) [204.2] 140.8 (135.8–158.6) [135.8] 294.8 (236.7–324.1) [236.7]
burst 96 (b) 67.3 (66.6–68.0) [68.0] 715.1 (714.3–717.2) [714.3] 1427.1 (1411.6–1441.1) [1411.6]
burst 96 (b′) twin 67.1 (66.2–67.7) [67.7] 723.3 (713.1–751.3) [713.1] 1431.0 (1418.8–1449.7) [1418.8]
burst 96 (c) hold 0 223.2 (211.8–251.8) [251.8] 192.3 (187.0–234.2) [187.0] 430.0 (381.2–453.4) [381.2]
burst 96 (d) hold 0 246.2 (221.0–250.5) [250.5] 199.3 (190.7–249.3) [190.7] 389.9 (383.3–434.4) [383.3]

At every rate (d) is level with or better than the better of (b) and (c):

  • at 10 and 30/s it is level with (b) at p50 and p99, where (c) loses to (b): p99 66.7 ms against (c)'s 120.5 at 10/s, p50 58.5 against 86.6 and p99 85.1 against 127.5 at 30/s;
  • at 60/s it beats both: p50 68.7 ms against (b)'s 83.5 and (c)'s 94.8, p99 123.1 against 198.5 and 139.4. (b) has started to queue behind busy processes there and (d) batches what queues;
  • at 120 and 240/s it answers as many logins a second as (c), level, about twice (b), with p50 lower: 100.3 ms against 116.0 at 120/s and 140.8 against 174.7 at 240/s. Its p99 is level with (c)'s at 120/s (142.6 against 157.1, inside the band) and lower at 240/s, 294.8 against 350.8;
  • in a burst it answers 246 logins a second against (c)'s 223, 10% more, with p50 and p99 level.

Round-robin dealing favours (d) as it favours (b). SO_REUSEPORT, which nish/net/prefork listens with, spreads connections by a hash of their addresses, so it can give a busy process a login while another is idle, and that login then waits as in (c). Nothing here measures that.

On one core (d) is (c) with cores 1, which the one-core table above already times as (c).

BMI2 and x86-64-v3: measured, not built

The question was whether bcryptHashN leaves speed to a CPU's newer instructions: BMI2's rorx and shrx and BMI1's bextr take a word's bytes out without the copy-and-shift baseline x86-64 needs, and one outside report had a BMI2 kernel halving the time. Four candidates were measured, each against the bar of the Adler-32 verdict: a candidate ships only if it beats Nish's best width by at least 20%, in two runs, and by more than the noise band. The bar was first read on medians.

After the medians on the noisy host E cleared it (below), the fastest round was adopted as the estimator to judge on: on a shared host another tenant can only slow a CPU-bound round, never speed it up, so the fastest round is the robust one. Every bench script here prints both, the median with the spread of its rounds and the fastest round, and the verdict was kept on that basis. The band is the module timed against a byte-identical copy of itself (unroll.mjs), which here moved by up to 18% (five lanes, once) and otherwise by 8.4% or less.

  • --cpu x86-64-v3. The same source built for v3, which lets LLVM use BMI2 and AVX2.
  • A hand kernel. bench/crypto/bcrypt/kernel/gen.mjs writes the cost loop's body in assembly at five and six lanes, with every lane's halves in registers and nothing spilled, in four ways of taking the bytes: base-shr, base-ah (baseline x86-64), rorx-shr and rorx-ah (BMI2). This is the ceiling: what a runtime kernel in C or assembly could reach.
  • The same interleave in C under cc -O2 (kernel/harness.c's C_BODY).
  • An unrolled generator. gen-body.mjs --unroll writes the eight round pairs out with constant P offsets, as the hand kernel does.

Machines. D is a quiet 4-core Xeon (Emerald Rapids) whose clock measures 3.15 GHz. E is a shared 4-core Xeon of the same family, cpuinfo 2.10 GHz, measured 2.92 GHz, whose rows spread by up to 30%; its figures are two passes of --rounds 9. F is a third, quieter container of the same family (cpuinfo "@ 2.10GHz"), run twice with ceiling.mjs --rounds 9. All list bmi2, avx2 and avx512f. No AMD and no AArch64 core was measured.

Per width, default and v3 (run.mjs --cpu-both; ms per hash, then ns per Blowfish block, 1,067,721 blocks a cost-10 hash):

Lanes D default D v3 E default, pass 1 / 2 E v3, pass 1 / 2 E v3 / default
1 56.9 (53.3 ns) 57.5 (53.9) 65.4 / 64.9 65.5 / 63.5 1.00 / 0.98
2 31.8 (29.8) 32.4 (30.3) 36.9 / 36.1 35.8 / 35.7 0.97 / 0.99
3 24.1 (22.6) 23.5 (22.0) 29.2 / 27.5 27.6 / 25.7 0.95 / 0.93
4 19.4 (18.2) 19.5 (18.3) 25.6 / 23.5 23.1 / 20.8 0.90 / 0.88
5 17.1 (16.0) 17.7 (16.6) 25.2 / 22.3 20.9 / 21.6 0.83 / 0.97
6 15.7 (14.7) 16.3 (15.3) 23.7 / 24.5 20.2 / 21.2 0.85 / 0.86

On the quiet machine v3 is level with the default at every width, within 4% either way. On the noisy one it reads 3 to 17% faster from three lanes up, but the wide rows' spreads there are 16 to 31 ms on both builds and the ratios do not repeat (five lanes: 0.83, then 0.97). No width clears 20%.

The ceiling (ceiling.mjs; ms per hash per lane, and Nish's best width's time over the row's, so above 1 is faster than Nish):

Body D, 6 lanes E pass 1, 5 / 6 lanes E pass 2, 5 / 6 lanes
Nish bcryptHashN 16.5 24.4 / 22.4 18.3 / 19.6
hand base-shr 16.5–16.8 20.8 (1.08) / 23.0 (0.97) 18.6 (0.98) / 20.7 (0.88)
hand base-ah 16.5–16.8 20.4 (1.10) / 18.0 (1.24) 17.7 (1.03) / 17.3 (1.05)
hand rorx-shr 15.1 (1.09) 18.4 (1.22) / 19.0 (1.18) 18.6 (0.98) / 18.5 (0.99)
hand rorx-ah 15.8 (1.04) 18.9 (1.19) / 16.7 (1.34) 19.1 (0.95) / 16.6 (1.10)
C interleave, cc -O2 16.0 (1.03) 22.6 (0.99) / 23.3 (0.96) 21.9 (0.83) / 21.3 (0.86)

The table's ratios are on medians. On D the best hand kernel, BMI2's rorx-shr at six lanes, is 9% ahead of Nish's six lanes, under the bar. On E the best hand kernel was 34% ahead in the first pass (rorx-ah), 10% in the second, and 31% in a third, --rounds 5 (rorx-shr, 15.6 (15.0–22.6) against Nish's 20.5 (16.3–29.2)): two runs of three over 20%, by different kernels, which met the stop rule. Those are medians inflated by noise.

On E Nish's best median moved from 22.4 to 18.3 ms between passes while rorx-ah's held at 16.6 to 16.7, and on fastest rounds the third run's 1.31 is 1.09 (16.3 against 15.0); Nish's fastest rounds there (15.8 to 16.9 ms) are within 10% of the hand kernels' (15.0 to 15.9).

F, at six lanes, gives both estimators; ms per hash per lane, median then fastest round, and Nish's time over the row's on each:

Body F run 1 F run 2 Nish / this, fastest Nish / this, median
Nish bcryptHashN 16.7 (15.9) 18.9 (15.2) 1 / 1 1 / 1
hand base-shr 20.2 (14.7) 19.3 (14.6) 1.08 / 1.04 0.83 / 0.98
hand base-ah 16.3 (15.5) 16.9 (15.6) 1.03 / 0.97 1.02 / 1.12
hand rorx-shr 15.7 (14.8) 15.9 (14.7) 1.07 / 1.03 1.06 / 1.19
hand rorx-ah 19.5 (15.8) 18.4 (17.3) 1.01 / 0.88 0.86 / 1.03

The whole hand-kernel ceiling, the best kernel over Nish's best width, is about 4 to 9% across D's medians (1.09) and F's fastest rounds (1.08 and 1.04). How it splits between the spills and the byte extraction cannot be told inside the noise: on F's fastest rounds the spill-free baseline base-shr is level with BMI2's rorx-shr (14.7 and 14.6 against 14.8 and 14.7), while on D's medians rorx-shr is 9 to 11% ahead of base-shr (15.1 against 16.5 to 16.8).

The medians on F move each row's ratio by up to 0.17 between two runs (rorx-ah 0.86 to 1.03), which is why they are not the estimator to judge on. The stop rule's outcome was reviewed, and this verdict was kept: no runtime kernel is built. A quiet run on a core of another family whose fastest rounds clear 20% twice would reopen it.

unroll.mjs, rerun for this review on a noisy host at 2 to 6 lanes and nine rounds, puts the source-unrolled body (gen-body.mjs --unroll) inside the noise on both estimators: on fastest rounds unrolled over module is 0.97 to 1.07, and the plain copy 0.98 to 1.03; on medians unrolled over module is 0.91 to 1.15, and the copy 0.89 to 1.03. Neither clears 20% on either. So gen-body.mjs --unroll stays an option and std/crypto/bcrypt.ts is unchanged.

Does LLVM need an upstream change? Not on these cores. On Intel Emerald Rapids the data bounds what the backend could give. Instruction selection (the missing shrx and rorx for shifts by a constant) and register allocation (the spills and reloads of Nish's six-lane round) together can reach at most the hand kernels, which hold every lane in registers and take the bytes the best way measured: 4 to 9% over Nish.

No change to either, or to both, reaches the 20% bar there, nor the 30% gain the request this record answers aimed for. Which resource limits the core past the spills these measurements do not identify: rorx-ah runs about 12.3 instructions a lane half-round, about 2.05 cycles at a 6-wide issue, yet is no faster than Nish's 15.7. The ceiling is the measured one, not a derived bound. AMD is unmeasured (below), and the answer there is open.

Why v3 does not help: the assembly. In bcryptBodyN built with -g, the default and v3 round loops for widths 2, 6, 4, 5 and 3 are 58, 188, 123, 154 and 90 instructions against 58, 188, 123, 150 and 88; both use 160 shr/movzx pairs across the five loops, and v3's loop holds no BMI2 instruction (the binary's two are an andn and a variable-count shlx, outside the body).

LLVM 18 does not choose shrx, rorx or bextr for a shift by a constant on these Intel cores, where shr already costs one cycle; v3 only reschedules and saves a few spills (stack references at six lanes, 26 against 21). Per lane half-round at six lanes, Nish issues about 15.7 instructions, base-shr 15.3, rorx-shr and base-ah 13.3 and rorx-ah 12.3.

Holding all 16 registers' worth of six lanes' halves, base and counter without a spill (Nish's six-lane round refers to the stack 26 times, the hand kernel's not at all) saves about 0.4 instructions; a better way of taking the bytes saves about 2.0 more, and ah saves as much as rorx does without BMI2. By count, then, extraction is the larger saving; by time the two cannot be told apart inside the noise (above), and neither is large.

AMD is open. Zen cores run shrx, rorx and the ah registers at other costs, and LLVM's choices may differ under their -mtune. Nobody has run this there; node bench/crypto/bcrypt/ceiling.mjs --rounds 9 on such a core answers it, and a hand kernel 20% ahead of Nish's best width in two runs reopens the question.

The outside claims do not reproduce. "7.3 ms per hash on five lanes" at cost 10 is 6.8 ns per block, about 21 cycles per block at 3.15 GHz, 1.3 cycles per lane half-round. A half-round reads five words; with 3 load ports that is 1.7 cycles at the least, so a core like D's cannot do it at cost 10. At 5.5 GHz it is about 38 cycles per block, 2.4 per lane half-round, which a fast desktop core could approach. The figure is a higher clock, another cost, several cores, or a different count. "BMI2 halved it": taking the bytes is 4 of about 15 instructions a half-round, and on D rorx gained 9% at most over Nish. A halving needs a slow starting point, not BMI2.

What a server checks first. bcryptHashN runs only the lanes it is given as one computation, so a batch of six with two passwords in it runs two lanes, at 31.8 ms each on D rather than 15.7. A server that hashes logins as they arrive gets the six-lane speed only when six are waiting: the batch's fullness moves the time per password by up to 3.6 times, an instruction set by at most 9% here.

Reproduce, on x86-64 with cc (--cpu-both refuses a CPU without avx2 and bmi2; ceiling.mjs exits 0 and says why off x86-64 or without bmi2):

node bench/crypto/bcrypt/run.mjs --rounds 9 --cpu-both
node bench/crypto/bcrypt/ceiling.mjs --rounds 9
node bench/crypto/bcrypt/unroll.mjs --rounds 9 --widths 2,3,4,5,6

Cascade Lake: the ceiling, and one copy for two bytes

The study above ran on Emerald Rapids, which renames 6 instructions a cycle and has 3 load ports. The question here was whether that verdict holds on an older, narrower Intel core, the kind a hosted benchmark runs on.

Machine G is an 8-vCPU KVM guest on a Xeon Platinum 8260 (Cascade Lake, cpuinfo "@ 2.40GHz"; bmi2, avx2 and avx512f), idle, with each program pinned to one vCPU. The core renames 4 instructions a cycle and has 2 load ports. The binaries were built with LLVM 18.1.3 (Ubuntu 24.04's clang-18) and timed as run.mjs times them: the child's user CPU time, in interleaved rounds after a warm-up, as median (spread). The rounds here spread by about 2%. Ms per hash per lane, cost 10; a kernel's row is its cost-loop bodies.

The ceiling. The four kernel/gen.mjs bodies and two more ways of taking the bytes, written in kernel/gen-tight.mjs from the ideas of the challenge's leading entries:

  • shrx, 11 instructions a lane half-round, BMI2. One rorx x, 8 gives bytes 2 and 1 as ah and al, and shrx by a count held in a register gives byte 3 with no copy. This is the shrx style of submissions/zig-iouring-nick-potts (src/bcrypt/asm_gen.zig), which rust-epoll-theCatWisel's build.rs also generates. It fits five lanes.
  • dh, 12 instructions, baseline x86-64. One copy into edx gives byte 1 as dh, then shr 16 gives byte 2 as dl and shr 8 byte 3. This is the FF macro of submissions/asm-epoll-nickita-khylkouski (src/bcrypt.s). At six lanes the state is copied to the stack and read through rsp, as that entry keeps its contexts, so twelve halves and three temporaries fill the 16 registers.

Both write the 8 round pairs out, so P is read at constant displacements, and nothing is spilled.

Body 4 lanes 5 lanes 6 lanes
Nish bcryptHashN, before the change below 23.6 (23.2–25.4) 22.9 (22.5–23.3) 23.2 (23.0–23.6)
hand base-shr 23.3 (23.0–23.5) 23.5 (23.3–25.3)
hand base-ah 21.0 (20.9–21.7) 21.5 (21.2–22.9)
hand rorx-shr 21.0 (20.8–21.3) 22.0 (21.7–23.0)
hand rorx-ah 20.2 (20.0–21.3) 20.6 (20.4–23.0)
hand dh, the state in place 19.8 (19.4–20.4) 20.4 (20.3–20.8)
hand dh, the state on the stack 20.0 (19.6–21.3) 21.5 (21.2–22.8)
hand shrx 21.6 (21.3–22.2) 19.4 (19.2–20.2)

The best hand kernel, five-lane shrx, took 15% less time than Nish's best width, five lanes: 1.18 on medians, against 1.04 to 1.09 on Emerald Rapids. That is under the 20% bar, so the verdict that no runtime kernel is built stands. Padding each lane's state to 4224 bytes (64-byte aligned, as theCatWisel's entry lays its lanes out) moved the stack-based dh by under 0.3%; 4K aliasing between the lanes is not what limits the kernel.

What limits each kernel. The counts come from perf stat on G. They are multiplexed, so read them as approximate. Five-lane shrx issues 2.8 uops a cycle and keeps load ports 2 and 3 at about 1.8 loads a cycle of their 2. It is load-port bound: 5 loads a lane half-round over 2 ports is 2.5 cycles, and it runs about 3.2.

Six-lane dh loses about a sixth of its issue slots to the front end (idq_uops_not_delivered.core), which points at its 1,200-instruction body. Nish's five-lane loop, as it was, issued 3.3 uops a cycle (15.4 instructions a lane half-round with 1.8 stack references) and ran about 4 cycles a lane half-round. On this core, then, the instruction count and the spills cost time, where on Emerald Rapids' wider front end they cost little.

Making LLVM's code tighter from Nish. Each form below was tried on bcryptBody2 to bcryptBody6 (gen-body.mjs) and timed against the module in the same rounds: ms per hash at five lanes, default target.

Form 5 lanes Note
The module as it was 22.5 to 22.6
The 8 round pairs unrolled (--unroll) 25.4 +12%; 4 and 6 lanes also +8 to 12%
x >>> 16 behind the barrier, bytes 3 and 2 as its high and low byte 23.4
x >>> 8 behind the barrier, every lane's bytes first 24.4 +8%
x >>> 8 behind the barrier, each lane's half-round whole 21.1 −6%, three runs
(x >>> 8) | (x << 24) behind the barrier, each lane whole 21.3 the same at five lanes; a rorx under v3
the module, linked with -mllvm -misched=ilpmin 21.7 a link-wide flag, see below

The barrier is ctSelect(v, 0xffffffff, 0), which is v itself but opaque. Without it LLVM folds the two middle bytes back into two shifts of the word, and the word is copied twice. With it, and with each lane's half-round written whole before the next lane's, the four- to six-lane round loops fall from 15.4 to 15.7 instructions a lane half-round to 14.0 to 15.0, with fewer spills (16 stack references a round at five lanes, from 18).

Under --cpu x86-64-v3 the rotated copy is one rorx, and the loops are 12.6 (four lanes) and 13.1 (five lanes). Written for every lane first, the same copy lengthens the values' lives and spills more. The unrolled loops are larger and spill more, 98 stack references a block at five lanes.

The change. bcryptBody3 to bcryptBody6 now take the two middle bytes from one copy behind the barrier, each lane's half-round written whole. Three to five lanes rotate the copy. Six lanes shift it, because on the default target the rotated six-lane loop measured slower, 23.3 against 23.0 ms. bcryptBody2 keeps its form: the copy measured 36.3 against 35.3 ms there. The barrier is an identity on a register. It adds no branch, no load and no store, so the round reads the same four S-box words (BCRYPT-6 unchanged), and the working values stay in registers and spill slots as before (BCRYPT-7 unchanged). Every lane's hash is unchanged: bcrypt differential with its batches of two to six, link/crypto_bcrypt_width's widths one to six, and three further seeds of 240 cases and 61 batches each, all agreeing with crypt_r.

On G, the module before and after, 15 interleaved rounds, ms per hash:

Lanes Before After Before, v3 After, v3
3 28.2 (27.7–29.4) 27.0 (26.7–28.5) −4.4% 28.4 (28.0–28.9) 26.7 (26.5–27.2) −6.0%
4 23.3 (23.0–23.8) 23.5 (23.1–25.2) +0.8% 23.5 (23.3–24.4) 22.2 (21.9–22.8) −5.4%
5 22.7 (22.4–23.5) 21.3 (21.0–21.8) −6.5% 22.2 (21.8–22.9) 20.7 (20.3–21.6) −6.7%
6 23.2 (22.9–23.8) 22.3 (22.0–24.5) −3.8% 23.5 (23.1–24.2) 22.8 (22.6–23.6) −2.9%

The one-lane and two-lane paths are unchanged, inside the noise: 60.9 and 35.2 ms against 60.9 and 35.3 in an earlier pass of the same comparison. In that pass five lanes measured 21.3 against 22.6 ms, −5.8%. At the best width, the one bcryptCalibrate picks here, a hash takes 6% less time on the default target and 9% less under --cpu x86-64-v3 than the default target took before. The fastest rounds agree: 21.0 against 22.4 ms. A perf record of five-lane hashes puts 98.6% of the time in bcryptBodyN and 0.3% in the one-lane salted expansion and magic string, so nothing outside the round loop is worth specializing.

What is left. Five-lane shrx took 19.3 ms in the same rounds: 9% less than Nish on the default target, 7% less under v3. The difference is the hand kernel's 11 instructions and no spills against Nish's 14.5 (13.1) and 1.6 stack references a lane half-round, and P at constant displacements against an index register. No Nish source form found closes it, and the compiler offers no lever that would:

  • -misched=ilpmin at the LTO link takes the old module to 21.7 ms at five lanes and 22.0 at six, with almost no spills. With the shift copy written lane by lane it gives 21.2 and 21.5. It is one flag for the whole program's code generation, though, and LLVM has no per-function attribute for the machine scheduler, so the driver could not give it to this module alone. It is not adopted.
  • BMI2 is a whole-program --cpu. What would give every user's binary the v3 loops, 2.6% more at five lanes, is per-function target-features with a CPUID dispatch between two copies of the kernel. That is a new construct, and it is not made.

The leaders' kernels are 7 to 9% ahead on this core, under the 20% bar, so the record's answer to a runtime kernel in assembly or C stays no. Measured on Intel only: AMD is still open, and a Zen run of node bench/crypto/bcrypt/ceiling.mjs --rounds 9, now with shrx and dh rows, answers it.

The paired bytes. The dh and shrx kernels above take a second byte of a register in one instruction, movzx from ah, bh, ch or dh, where Nish's loop took it by a shift and a mask. The idea is theirs: submissions/asm-epoll-nickita-khylkouski's FF macro pairs dl and dh of one copy, and rust-epoll-theCatWisel (the challenge's pull request 201) and submissions/zig-iouring-nick-potts take ah of a rotated copy. Nish reimplements it in source, with no assembly.

bcryptBody3 to bcryptBody6 now take a lane's bytes as two pairs, each the low and second byte of a copy behind the barrier: a copy of the word gives bytes 0 and 1, and that copy moved down by 16, behind a second barrier, gives bytes 2 and 3. LLVM then emits movzx from the high-byte register for the second of each pair, so a lane takes its four bytes in six instructions, where the rotated copy took seven.

Each pair's copy must sit, for its second byte, in one of the four registers that have one (eax, ebx, ecx, edx), which constrains the register allocator: up to five lanes it fits, but with all six lanes paired the loop spilled more than the pairs saved, so the sixth lane of six keeps the rotated copy's way (moved down by 8 there, as before). The cutoff at five is counted, not derived. bcryptBody2 is unchanged. gen-body.mjs --rotated still writes the previous form, and bench/crypto/bcrypt/extract.mjs counts and times the two against each other and against a byte-for-byte copy of the module, the noise band.

The round loops, clang -O3 of the IR (LLVM 18.1.3), instructions and stack references a round:

Lanes Rotated copy Paired bytes A lane half-round
3 84, 0 77, 0 14.00 → 12.83 −8.3%
4 112, 8 103, 0 14.00 → 12.88 −8.0%
5 145, 16 132, 9 14.50 → 13.20 −9.0%
6 180, 22 169, 19 15.00 → 14.08 −6.1%

Under --cpu x86-64-v3, where the rotated copy is one rorx, the two forms count about level at three to five lanes and the pairs still win at six: 78 against 78 at three lanes, 103 (no stack references) against 101 (4) at four, 132 (9) against 131 (11) at five, and 169 (19) against 186 (26) at six. v3 was not timed; on these counts a v3 build should not be slower.

On G, three runs of extract.mjs --rounds 15 (the third pinned to one vCPU, four to six lanes), ms per cost-10 hash a lane. The ratio is the median of the rounds' own ratios, paired module over rotated, and the copy column is the noise band, the module over its own copy:

Lanes Rotated copy Paired bytes Paired / rotated Copy / module
3 26.8 (26.3–28.5) 26.0 (25.7–27.5) 0.975, 0.969 1.006, 1.006
4 23.4 (23.1–26.9) 22.6 (22.4–23.0) 0.968, 0.968, 0.968 0.995, 0.995, 1.005
5 21.3 (20.9–22.2) 20.5 (20.3–24.0) 0.963, 0.967, 0.962 1.005, 1.000, 0.995
6 22.2 (22.0–23.0) 20.9 (20.8–22.8) 0.943, 0.944, 0.944 0.996, 0.996, 0.996

The medians shown are the first run's; the other two agree within 0.2 ms. Four to six lanes gain in every run by several times the noise band: 3.3 to 3.8% at five lanes, the best width, and 5.6 to 5.7% at six, which narrows six lanes' deficit to five from about 4% to 2%. Three lanes gain 2.5 to 3.1%. Five lanes remain the width bcryptCalibrate picks here. Five-lane shrx, 19.3 to 19.4 ms in the earlier rounds, is now about 5% ahead.

The barriers are identities on registers: no branch, no load and no store is added, the round reads the same four S-box words at the same indexes (BCRYPT-6 unchanged), and the four-lane loop no longer spills while five and six spill less (BCRYPT-7: fewer working values reach the stack, none newly).

Every lane's hash is unchanged: node tests/run.js bcrypt (the crypt_r differential with its batches of two to six, link/crypto_bcrypt_width's widths one to six, the $2a$/$2b$ vectors, passwords of 72 bytes and longer and with NUL bytes), and each extract.mjs run checks that every program prints the same hash. Emerald Rapids, a 6-wide core, is not expected to move (its verdict above: fewer instructions do not help it); a Zen run is still open.

node bench/crypto/bcrypt/extract.mjs --rounds 15 --widths 3,4,5,6

The half-round's critical path

Each half-round is x ^= P[n] ^ F(y), where F(y) is four S-box loads joined by add, xor, add, and y is the half the previous half-round produced. x and P[n] are ready long before F(y), so the fast shape XORs them first, off the path, and leaves one XOR after the last S-box add: (x ^ P[n]) ^ F(y). gcc builds that shape in all 16 half-rounds. LLVM, given the expression plainly, builds it in the first and puts P[n] on the path in the other 15, (P[n] ^ F(y)) ^ x: two dependent XORs after the add instead of one. bcryptBody and bcryptEncrypt therefore write each half-round as

r = ctSelect(0xffffffff, r ^ st[n], 0) ^ F(l)

ctSelect(m, a, b) lowers to (a & h) | (b & ~h), where h is m passed through the value barrier, an empty inline asm LLVM cannot see through. With b 0 the or folds away and (x ^ P[n]) & h is left.

LLVM cannot know that h is all ones, so it cannot move P[n] out of the and and into the XOR chain: the half-round keeps the order written. The barrier takes a constant, so LLVM hoists it out of the loop and merges the copies into one register holding 0xffffffff. Each half-round pays one register and, computed off the path while the S-box loads are in flight.

The barrier is safe because it is an identity on the value: with an all-ones mask, ctSelect gives x ^ P[n] in every bit, so every hash is unchanged, and the bcrypt vectors, the crypt_r differential and the batch's lane-by-lane comparisons with the single path answer as before. It adds no branch and no load. The mask is a constant, not a secret, and the and is one ALU instruction on registers, so the cache lines the round touches are still the four S-box words BCRYPT-6 records and nothing more. The working values stay in registers as before, which BCRYPT-7 records. Neither row changes.

The batch kernels, bcryptBody2 to bcryptBody6, keep the plain x ^= P[n] ^ F(y). Their chains are independent, so a core has other work while one chain waits, and one extra XOR on a chain's path costs little there. Writing the four-lane kernel's 16 half-rounds with the barrier was measured as a loss: in two runs interleaved with the plain form in one session, bcryptHash4 took 27.6 (21.4–31.8) and 24.8 (21.0–34.2) ms against 24.2 (22.5–28.3) and 22.9 (22.3–31.8) ms. Both medians were slower, inside the batch's wide spread, and nothing was gained to set against the extra and per half-round.

Build Loads Stores Stack spills Bounds checks, calls, jumps Critical path from y P on the path
Nish bcryptBody 5 0 0 0 7 instructions, 11 cycles 0 of 16
OpenBSD Blowfish_encipher, gcc -O2 5 0 0 0 6 instructions, 11 cycles 0 of 16
OpenBSD Blowfish_encipher, clang -O2 5 0 0 0 8 instructions, 12 cycles 15 of 16

The first five columns count one half-round, from perhr in the recipe below, which reads the 15 windows between consecutive S3 adds. The barrier's and is a register operation, so it adds no load. Nish stores twice per block (st[i], st[i + 1]) and the C stores its halves through its pointer arguments once per call; neither stores inside a round.

The critical path is the dependent chain from y to the next half-round's input, under 1 cycle per ALU operation, 5 cycles per L1 load and eliminated register moves. Here is one half-round from each listing, with the path marked *. The instructions are in program order, several to a line; none is changed:

; gcc: (x ^ P) ^ F, x ^ P computed off the path
  mov r9d,edx            mov ecx,edx           movzx ebx,dh
* shr r9d,0x10           shr ecx,0x18        * movzx r9d,r9b
  mov ecx,[rax+rcx*4]  * add ecx,[rax+r9*4+0x400]  movzx r9d,dl
* xor ecx,[rax+rbx*4+0x800]  * add ecx,[rax+r9*4+0xc00]
  xor edx,[rax+0x100c] * xor ecx,r8d
; Nish: ((x ^ P) & h) ^ F, x ^ P and the and computed off the path
  xor ecx,[rsi+0xc]      mov eax,edx           mov r10d,edx
* shr r10d,0xe           shr eax,0x18        * and r10d,0x3fc
* mov ebx,[rsi+r10*1+0x448]  * add ebx,[rsi+rax*4+0x48]  movzx eax,dl  movzx ebp,dh
* xor ebx,[rsi+rbp*4+0x848]  and ecx,r9d     * add ebx,[rsi+rax*4+0xc48]
* xor ebx,ecx
; clang: (P ^ F) ^ x
  mov r9d,r8d            shr r9d,0x18          mov eax,r8d
* shr eax,0xe          * and eax,0x3fc
* mov eax,[rdi+rax*1+0x400]  * add eax,[rdi+r9*4]  mov r9d,r8d  shr r9d,0x6  and r9d,0x3fc
* xor eax,[rdi+r9*1+0x800]   movzx r9d,r8b     * add eax,[rdi+r9*4+0xc00]
* xor eax,[rdi+0x1008] * xor eax,ecx

r9d is the hoisted barrier, set to 0xffffffff once before the loop. The Nish path is one instruction longer than gcc's in the same 11 cycles. It loads the second S-box word with a mov and adds the first to it, where gcc loads the first off the path and adds the second to it in one instruction. The index computations cost the same, shr and and against shr and movzx.

The 16 half-rounds are fully unrolled and the state base and length stay in registers. The second-lowest byte is one movzx …, bh where clang's C takes a shr and an and. The C expansion loops call Blowfish_encipher once per block, which Nish's inlined loop does not.

The order is made in the IR, not in the backend. Without the barrier, in the pre-link -O3 pipeline, Reassociate turns the source's x ^ (P[n] ^ F(y)) into (P[n] ^ x) ^ F(y), and a later InstCombine flips it to (P[n] ^ F(y)) ^ x. In the loop it is the InstCombine after the loop passes:

; before that InstCombinePass
%47 = xor i32 %35, %l.addr.117   ; P[n+1] ^ l
%48 = xor i32 %47, %46           ; ^ F(r)
; after it
%47 = xor i32 %35, %46           ; P[n+1] ^ F(r)
%48 = xor i32 %47, %l.addr.117   ; ^ l

The unrolling is not the cause. A copy of bcryptBody with the 16 half-rounds written out as straight-line code, which was not committed, gave the same hash and the same 15 of 16. llc keeps the tree at -O1, -O2 and -O3, and with -x86-machine-combiner=false. Three other plain forms of the source gave the same 15 of 16: writing it as (x ^ P[n]) ^ F(y), loading P[n] into a const first, and a loop of one half-round with a swap.

LLVM canonicalizes a three-operand XOR whatever order it arrives in, so only an operand it cannot see through holds the order, which is what the barrier's and is. Nish's opt and llc are the same LLVM 18.1.3 as the clang that built the C, and that build ends in the same 15 of 16.

bcrypt barrier in tests/run.js pins the shape. It compiles tests/link/crypto_bcrypt and runs opt -O3 on bcrypt.ll, then counts the XORs in bcryptBody that take the barrier's and as an operand. There must be 16, one per half-round. A source that drops the barrier leaves no such and to count, and a compiler that stops emitting the barrier opaquely folds the and away; either fails it.

To reproduce, run npm run build and then node bench/crypto/bcrypt/run.mjs once to build the programs, then:

build/nish build/bench/bcrypt/nish.ts -o build/bench/bcrypt/nish-g-out/ --link build/bench/bcrypt/nish-g -g
dis() { objdump -d --no-show-raw-insn -M intel --disassemble="$2" "$1" | grep -P '^\s+[0-9a-f]+:\t' | cut -f2-; }
onpath() { awk -v s3="$1" '$1 == "add" && index($0, s3 "]") { split($2, a, ","); r = a[1]; n++; next }
  r != "" { if ($1 == "xor" && $2 == r ",DWORD") p++; r = "" } END { print n " S3 adds, " p + 0 " with P on the path" }'; }
perhr() { awk -v s3="$1" '{ w[++m] = $0 } $1 == "add" && index($0, s3 "]") { if (n++) { for (i = 1; i <= m; i++) { o = w[i]; sub(/^[a-z]+ +/, "", o); if (o ~ /^[^,]*PTR \[/) st++; else if (o ~ /PTR \[/) ld++; if (o ~ /\[(rsp|rbp)/) sp++; if (w[i] ~ /^(call|j)/) br++ } } m = 0 }
  END { k = n - 1; print k " half-rounds: " ld / k " loads, " st + 0 " stores, " sp + 0 " stack refs, " br + 0 " calls or jumps" }'; }
for f in "build/bench/bcrypt/nish-g nish.bcryptBody 0xc48" "build/bench/bcrypt/openbsd-gcc Blowfish_encipher 0xc00" \
  "build/bench/bcrypt/openbsd-clang Blowfish_encipher 0xc00"; do set -- $f; dis "$1" "$2" | onpath "$3"; dis "$1" "$2" | perhr "$3"; done

onpath finds each add of the last S-box word (state offset 0xc48 in Nish, 0xc00 in OpenBSD's context) and checks whether the next instruction XORs a state word into the same register. It relies on the add being followed directly by that XOR. That was checked against all three listings by hand. In clang's, each S3 add is followed by the P XOR on the path or, in the first half-round, by an XOR into another register, as in all of gcc's.

In Nish's, each is followed by the half-round's one closing XOR of two registers, directly or after the barrier's and of the other half. It prints 16 S3 adds and 0, 0 and 15. perhr prints 15 half-rounds, 5 loads and no stores, stack references, calls or jumps for each. With clang/LLVM 18.1.3, gcc 13.3.0 and GNU objdump 2.42 on x86-64, the three dis listings have these sha256s (dis … | sha256sum). Branch targets keep their <symbol+offset> text through cut -f2-, so a hash pins the link layout as well as the toolchain:

Listing sha256
nish.bcryptBody e5e4a901342e13f1505fa677ba6edec9315d2aae39f479cea5c9c15ea9b0fdec
Blowfish_encipher, gcc 5bd677c28adadcd01e97a6c9c2a17b55347bda224db42e6266a0db579aa2295d
Blowfish_encipher, clang f3c2b0791101df18ec265ca65924336544990e18398d97939d953845d470b396

The -g build is needed for the symbol, because the bench's Nish binary is built with the speed profile, which strips it. The C binaries are not stripped. For the IR trace, set CC to this wrapper and rebuild:

#!/bin/bash
for a in "$@"; do [ "$a" = -c ] && exec clang "$@" -mllvm -print-changed -mllvm -filter-print-funcs=nish.bcryptBody; done
exec clang "$@"

The parallel -c steps interleave their output. Running opt -passes='lto-pre-link<O3>' -print-changed -filter-print-funcs=nish.bcryptBody on the emitted .ll gives the pass-by-pass trace in one stream.