1
$\begingroup$

I'm looking for a hashing algorithm with some unique properties:

  • Most important: It has to be small. Ideally ~400 bytes of x86 assembly
  • Resistant to preimage & collision attacks with no known vulnerabilities
  • The expected message buffer is between 1 and 256 ASCII characters
  • The ideal hash is between 128-256 bits

It doesn't need to be particularly fast. No need for HMAC or anything other than a straightforward hash.


I'm using gnu_hash() but it's easy to force collisions.

I've got a SHA-256 that's around 853 bytes. It's plenty fast, but I'd like to ask the experts for their thoughts and see if there's something that's a bit smaller.

I was looking into BLAKE3. I love the speed, but it's HUGE... thousands of bytes and not much opportunity to optimize for size.


I thought I'd ask for some of your expert thoughts. Given the above requirements, what algorithm would you reach for?

Thank you so much.

--M

$\endgroup$
2
  • $\begingroup$ Is there a speed requirement? A requirement to have withstood the test of years of cryptanalysis attempts? $\endgroup$
    – fgrieu
    Commented May 21 at 6:06
  • $\begingroup$ No, there's not speed requirement. I agree that an ideal algorithm would have years of tests, but it's not a requirement for this application. $\endgroup$ Commented May 21 at 17:48

2 Answers 2

2
$\begingroup$

Ascon, (Reference Implementation)

Also, a bare-minimum of 700-octet Kolmogorov complexity seems to be necessary for the application(s) of secure hashing.

$\endgroup$
3
  • $\begingroup$ Your last para is of personal interest. Do you have any references/details for the 700 please? $\endgroup$
    – Paul Uszak
    Commented May 21 at 12:10
  • 1
    $\begingroup$ @PaulUszak This section in the reference implementation link: github.com/ascon/… I just noted the pattern, but not sure what caused it. $\endgroup$
    – DannyNiu
    Commented May 21 at 12:37
  • $\begingroup$ @DannyNiu Thank you! There's a ton of good resources in that GitHub repo. I'll dig into it in the coming days and report back. $\endgroup$ Commented May 21 at 17:49
0
$\begingroup$

A simple ARX construct can do with less than the required 400 bytes of executable code, if we require neither:

  • speed,
  • low RAM usage,
  • having withstood the test of years of cryptanalysis attempts after publication in a respectable crypto journal.

Here is an example. Try it online for test vectors. The generated code is 135 bytes when compiled for x86 by GCC 13.2 using options -m32 -Os.

#include <stdint.h>
// hash optimized for code size
void nanohash(
    uint8_t hash[32],   // hashed output
    const uint8_t * in, // data input
    int n               // length, max 256
    ) {
    uint32_t s[128] = {0}, t = (uint32_t)n;
    while(--n>=0)
        s[n&63] = s[n&63]<<8|in[n];
    for (n = 24*128+65; --n>=0;)
        hash[n&31] = (uint8_t)(t = s[n&127]
        += ((t<<11|t>>21)+n)^s[(n+6)&127]);
}

Rationale:

  • The hash is 256-bit (the minimum for 128-bit collision resistance). We use the sponge strategy restricted to a single absorption. The permutation is built per the ARX methodology.
  • It's used 32-bit words because it's asked x86 code and that's a 32-bit CPU. We could make the code simpler and smaller (especially on lesser CPUs) by using 8-bit bytes, but at a considerable expense in speed on x86.
  • The state s is twice the maximum input size of 256 bytes. Each step of the mixing loop reversibly changes one state word, indexed circularly, according to two other state words. The mixing of the three uses Addition, Rotation, and XOR; and an extra addition of the loop counter n, to bring some irregularity.
  • One of these two words is the previously changed one cached in t, for fast diffusion.
  • The constant 6 defines how the other word is selected. It's more than 1, and small in the interest of diffusion.
  • The constants 11 and 21 define a word rotation amount. They sum to the word size 32, are not too small, and have no small positive multiple close to a multiple of 32, again for diffusion.
  • The constant 24 defines the minimum number of ARX transformations for each state word. That's 3 times as much as in chacha, and the state is 8 times larger. Such margin is intended to compensates the regular schedule and rotations.
  • The constant 65 is the lowest such that at the first iteration, the input length enters the state separately from the input data, to prevent input collisions.
  • The strange way the input is crammed into the first half of the state and the output extracted are for endian neutrality without making the code too large.

I believe this is safe, but that won't convince auditors.

$\endgroup$
1
  • 1
    $\begingroup$ In C, we usually use long or size_t for data length. (but lightweight is different anyway) $\endgroup$
    – DannyNiu
    Commented May 22 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.