[API Proposal]: Support Balloon Hashing

[tats-u]

Background and motivation

#105745

PBKDF2 has no tolerance toward the offline attack using GPUs.
Unlike Argon2 (#19933), Balloon Hashing can be combined with existing standard hash functions like SHA-2.
Additional hash functions like Blake2 (#80900) to be implemented are unnecessary.

https://crypto.stanford.edu/balloon/

Used to be mentioned in the previous revision (3) of the draft of the next version of NIST SP 800-63B.

API Proposal

namespace System.Security.Cryptography;

public partial class BalloonHasher
{
    public HashAlgorithmName HashAlgorithm { get; }

    public BalloonHasher(HashAlgorithmName hashAlgorithm, int sCost, int tCost, int nThreads);
    public BalloonHahser(HashAlgorithmName hashAlgorithm, BalloonParameters parameters);

    public int SCost { get; set; }
    public int TCost { get; set; }
    public int NThreads { get; set; }

    public byte[] GetBytes(string passowrd, byte[] salt);
    public byte[] GetBytes(byte[] passowrd, byte[] salt);

    public byte[] GetBytes(ReadOnlySpan<char> password, ReadOnlySpan<byte> salt);
    public byte[] GetBytes(ReadOnlySpan<byte> password, ReadOnlySpan<byte> salt);

    public void GetBytes(ReadOnlySpan<char> password, ReadOnlySpan<byte> salt, Span<byte> hash);
    public void GetBytes(ReadOnlySpan<byte> password, ReadOnlySpan<byte> salt, Span<byte> hash);
}

public partial class BalloonHahser
{
    public static byte[] Balloon(
        byte[] password,
        byte[] salt,
        HashAlgorithmName hashAlgorithm,
        BalloonParameters parameters);

    public static byte[] Balloon(
        ReadOnlySpan<byte> password,
        ReadOnlySpan<byte> salt,
        HashAlgorithmName hashAlgorithm,
        BalloonParameters parameters);

    public static void Balloon(
        ReadOnlySpan<byte> password,
        ReadOnlySpan<byte> salt,
        Span<byte> destination,
        HashAlgorithmName hashAlgorithm,
        BalloonParameters parameters);

    public static byte[] Balloon(
        string password,
        byte[] salt,
        HashAlgorithmName hashAlgorithm,
        BalloonParameters parameters);

    public static byte[] Balloon(
        ReadOnlySpan<char> password,
        ReadOnlySpan<byte> salt,
        HashAlgorithmName hashAlgorithm,
        BalloonParameters parameters);

    public static void Balloon(
        ReadOnlySpan<char> password,
        ReadOnlySpan<byte> salt,
        Span<byte> destination,
        HashAlgorithmName hashAlgorithm,
        BalloonParameters parameters);
}

public record struct BalloonParameters(
    int SCost,
    int TCost,
    int NThreads
);

API Usage

using System.Security.Cryprography;

// From https://docs.rs/balloon-hash/latest/balloon_hash/struct.Params.html#fields
var balloon = new BalloonHasher(HashAlgorithmName.SHA256, new BalloonParameters(1024, 3, 1));
var salt = RandomNumberGenerator.GetBytes(16);
var hash = balloon.GetBytess("P@$$w0rD", salt);

Alternative Designs

• PBKDF2: requires huge number of iterations (100K+); no GPU attack tolerance (i.e. not memory-hard at all)
• Argon2: best, but requires an additional hash functions to be implemented (Add support to blake2 and blake3 cryptographic hash functions #80900) and has not been approved by NIST
• bcrypt: a little bit legacy, and has a input length limit and the same issues in Argon2
• Yescrypt: has not been mentioned by NIST (apparently approved though). Only used by some recent Linux distributions (e.g. Ubuntu 22.04+, RHEL 10+, Arch, Fedora)

Risks

No risks other than runtime size increase.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-security, @bartonjs, @vcsjones
See info in area-owners.md if you want to be subscribed.

[Neustradamus]

To follow this ticket :)

[vcsjones]

I've been aware of BalloonHash for a while but never really took the time to look at it, but now seemed like a good time.

I did a quick implementation of it, and my overall impression of it is that right now it is under defined from a technical perspective, and lacks a specification. The paper (which is well written) is largely focused on a theorem and showing data dependency.

It does not specify the technical details of how things are implemented. Consider the pseudo code from the paper:

buf[0] = hash(cnt++, passwd, salt)

for m from 1 to s_cost-1:
  buf[m] = hash(cnt++, buf[m-1])

Where cnt is a counter. What does it mean to hash a counter? Is it little endian? A little endian what? 32-bit? 64-bit?

The paper doesn't actually say. But this is important to know because hashes operate on byte or bit streams. If you look at the prototype associated with the paper, we find that it is implemented as a 64-bit little endian. But how a prototype implements something is not a specification.

Also, the random neighbor selection is shown as:

int other = to_int(hash(cnt++, salt, idx_block)) mod s_cost

How to_int works over a 256-bit output is not defined. Nowhere in the paper is to_int described. We however learn that the prototype implementation interprets this as a big integer.

My overall interpretation of this is while it is interesting and has, as far as I can tell, good security properties, it is not ready to be part of a large platform's standard library. The lack of any definition of functions, inputs and outputs would create significant interoperability issues if it were eventually to be defined as something different from the prototype. This has even been noted by the authors, who indicate that it was never fully specified:

Our hope at the time of writing the paper was that someone would be interested enough in the algorithm to formalize it in an RFC or similar standard at the level of precision that one would need to write an interoperable implementation. Unfortunately, that never happened.

Though that comment is years-old at this point, I am not aware of any changes that would make that comment out-of-date.

There is also a lack of test vectors, particularly around some edge cases.

[tats-u]

It is regretting that the original paper and proposal is not ready for widely implemented.
It does not have an official Modular Crypto Format either.
We might have to post some additional issues on https://github.com/henrycg/balloon.