Turning djb2 into a cipher to curse the universe

[Leo]

Hey sci.crypt,

Here's something to play around with at this quiet period of the
newsgroup.

djb2 is a commonly used non-cryptographic string hashing function that
djb came up with. It is meant to be used for simple hashmaps in C, and
it's mixing is not very impressive even among non-cryptographic string
hashes.

So we should not be making any ciphers with it. But this is a Usenet
group for making and breaking ciphers, so here's a toy cipher with it.
To reiterate, this is a non-cryptographic hash and not even a great
one. So don't consider this a decent cipher at all.

Here is the formula for djb2.

H[i] = H[i - 1] * 33 ^ str[i]

or using a shift instead of multiplication

H[i] = ((H[i - 1] << 5) + H[i - 1]) ^ str[i]

The starting value for H is 5381.

Here's the cursed way to turn this into a stream cipher. We're going
to start with the usual value of 5381, but for each subsequent use of
djb2 we will not reset H.

The round count can be increased to have more mixing, but it causes an
equal amount of slowdown. 32 might be a decent number.

1. Round from 0 to 32
1.1. djb2 the round number as 1 byte
1.2. djb2 the key (arbitrary)
1.3. djb2 the byte number as a u64 (8 bytes)
2. Increment the byte number
3. Output the first 8 bits of H. -> (H >> 56) & 0xFF

I'll provide the C code to XOR stdin with this keystream at the end.

Here are some example outputs.

"Hello, sci.crypt!" encrypted with different keys. These will probably
make good test vectors.

test123-1 f040b0b5153022857763e74504ba38c0b4
test123-2 5478891de7c08feda05a1dc34cf80e9f6c
test123-3 7031a0442b0d06de774111d99a13666d8c
test123-4 83b503b45d58aa13b72aa5bc0f56719375
test123-5 8709d8e46ee69aa12cc33a22453a5faec6
test123-6 7b06d14c7fb646099dba51d88c781565be
test123-7 07ffcfbba3e3fdfa2da1a5b5db938d4bde
test123-8 35b0e6939d11f66fa807e83f197a048bc5
test123-9 ca15a3c3aebf26fd24bc60dd566fd28656
test123-a 7105a12d26087ed4985b48a1f10147f8b1
test123-b c1dd9fe40a1f165bd42eb0df55d0b25737
test123-c 1e89511b3205e333f261767b48f6e00fd0

As a challenge, here is a ciphertext of a famous quote from this
newsgroup.

eedb3446bca304bc27610af118c8754ecde71c268e01d037a1b3198b6210
83737ad6d7e59711c9fb0c2477c062ca8cc5383b99d0c7cd31a901904c24
a9465a0c75ec608c5a16bac744afdb198800ac72a0969aecc50c1a6bc465
b2f388cc40959dbf40841309eff555b7bdc49d6e61486cf099f18acd736b
40dbc381ca5ac3279f500f10f1b714bed209a285142c5e926198a8d111d4
7fea99168b9dd99c6504b6b67822716dd78c09e0ae5555da011f47076944
b97d3eca260bc188bfb78f68462d751ce5bd99c3c9076e46e1c4b818fb79
145a70ddcdba0d

C implementation
================

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

/* More rounds == slower but better mixing */
#define ROUNDS 32

static uint8_t* key;
static size_t keySize;

static uint64_t g_h = 5381; /* Global H */
static uint64_t g_i = 0; /* Global I */

/* This is classic djb2 if you start with 5381 */

static uint64_t
djb2_buf(uint64_t start, void* buf, size_t size)
{
size_t i;
uint64_t h = start;
uint8_t* bufc = (uint8_t*)buf;

for (i = 0; i < size; i++)
h = ((h << 5) + h) ^ bufc[i];

return h;
}

static uint8_t
next_byte(void)
{
uint8_t i;

/* For each byte, djb2 the round number, key and the byte number and
output the first byte. */

for (i = 0; i != ROUNDS; i++) {
g_h = djb2_buf(g_h, &i, sizeof(i));
g_h = djb2_buf(g_h, key, keySize);
g_h = djb2_buf(g_h, &g_i, sizeof(g_i));
}
g_i++;

return (g_h >> 56) & 0xFF;
}

int
main(int argc, char** argv)
{
int p;

/* In production (!?!?), use uniformly random keys with a KDF */
assert(argc == 2 && "You need to supply a key");
key = (uint8_t*)argv[1];
keySize = strlen(argv[1]);
assert(keySize != 0 && "Empty keys are not very secure");

while ((p = getchar()) != EOF)
putchar(p ^ next_byte());

return 0;
}

--
Leo

[Richard Heathfield]

On 16/05/2022 7:20 pm, Leo wrote:
> Hey sci.crypt,
>
> Here's something to play around with at this quiet period of the
> newsgroup.
>
> djb2 is a commonly used non-cryptographic string hashing function that
> djb came up with. It is meant to be used for simple hashmaps in C, and
> it's mixing is not very impressive even among non-cryptographic string
> hashes.
>
> So we should not be making any ciphers with it. But this is a Usenet
> group for making and breaking ciphers, so here's a toy cipher with it.
> To reiterate, this is a non-cryptographic hash and not even a great
> one. So don't consider this a decent cipher at all.
>
> Here is the formula for djb2.
>
> H[i] = H[i - 1] * 33 ^ str[i]

Also known as the Torek hash (as in Chris Torek).

I don't think the matter of correct attribution was ever solved
satisfactorily. (Last I heard, each gentleman gives the honour to
the other gentleman.)

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within