Fix carry handling in the g function in blake.ts

[thogiti]

Incorrect Carry Handling in the g Function

The g function in Implementation in blake.ts uses ~~(lo / 0x0100000000) to compute the carry from the lower 32 bits of a 64-bit word.

Since lo can be up to 0x2FFFFFFFC (i.e., approximately 3 times 0x0100000000), the carry can erroneously be 2 or 3.

Impact

• Functional Integrity: Incorrect carry values can corrupt the internal state, leading to wrong hash outputs.
• Security Risks: The integrity of the hash function is compromised, potentially allowing for hash collisions or predictable outputs, which undermines the cryptographic strength of Blake2-512.

Recommendation

• Modify the carry calculation to ensure that only a single carry bit (0 or 1) is propagated. For example:

const carry = lo >= 0x100000000 ? 1 : 0;
v[a * 2] = (v[a * 2] + ((m[sigma[i][e] * 2] ^ u512[sigma[i][e + 1] * 2]) >>> 0) + v[b * 2] + carry) >>> 0;

• Alternatively, use BigInt for precise 64-bit arithmetic operations as in the original Blake implementation in the npm repo, which TypeScript supports, to handle carries correctly without manual intervention.

[cedoor]

A better solution for this issue might be to use the original Blake implementation directly, wrapping it with a TS class.

[hannahredler]

Hey, if you need someone to work on this I would be happy to do so and replace the custom implementation with a wrapper over this implementation

[cedoor]

@hannahredler sure, let us know if you'd like to work on this and we'll assign it to you.

[Arch0125]

@cedoor Hey ive built a wrapper around the original blake-hash implementation, let me know if i can open a PR for review

[cedoor]

Hi @Arch0125 , of course! I'll assign this issue to you

[Arch0125]

@cedoor ive raised a PR here #361

[artwyman]

Is there a known set of real inputs which can demonstrate this error? What's the likelihood of this occurring in the wild with non-malicious inputs? Two contexts in which I ask these questions:

• Zupass and related apps have already issued signed data in the POD format which makes use of the hashes in zk-kit. I'd like to know how likely we are to deal with signatures failing after this update.
• In fix(eddsa-poseidon): fixes carry handling of g function by introducing wrapper over original implementation #361 it would be great to validate the fix with a targeted unit test using an input which would produce incorrect results before the PR, and correct results after the PR. Assuming this bug doesn't exist in the circomlibjs implementation of blake512, such a test could fit in with the compatibility tests which compare results between the two libraries.

[thogiti]

Crafting specific inputs that cause the internal state to reach conditions where lo exceeds 0x100000000 (causing multiple carries) is non-trivial due to the complexity of the Blake2-512 algorithm. But, may be you can implement a targeted unit test that artificially manipulates the internal state to simulate the buggy carry handling.

import { Blake512 } from './Blake512'; // Path to Implementation 

// Mock the 'g' function to force 'lo' to exceed the carry threshold
function mockGWithHighLo(v: number[], m: number[], i: number, a: number, b: number, c: number, d: number, e: number): void {
    let lo = 0x2FFFFFFFC; // Force 'lo' to a high value
    console.log(`Mocked lo: ${lo.toString(16)}`); // Logging

    v[a * 2] = (v[a * 2] + ((m[sigma[i][e] * 2] ^ u512[sigma[i][e + 1] * 2]) >>> 0) + v[b * 2] + ~~(lo / 0x0100000000)) >>> 0;
    v[a * 2 + 1] = lo >>> 0;

    // Continue with the rest of the function as per the original 'g'
    // ...
}

// Replace the original 'g' function with the mocked version for testing
Blake512.prototype.g = mockGWithHighLo;

// Create a hash instance and perform updates
const blake = new Blake512();
blake.update(Buffer.from('test input'));

// Finalize the hash
const hash = blake.digest();

// Verify that the carry handling was incorrect
console.log(hash.toString('hex'));

@artwyman

[cedoor]

@Arch0125 are you going to work on the PR you opened: #361

btw, @thogiti I tagged you in a comment there

[artwyman]

Crafting specific inputs that cause the internal state to reach conditions where lo exceeds 0x100000000 (causing multiple carries) is non-trivial due to the complexity of the Blake2-512 algorithm. But, may be you can implement a targeted unit test that artificially manipulates the internal state to simulate the buggy carry handling.

I don't know the internals of the Blake hash well enough to review your suggestion in detail. That invasive/white-box approach is a good way to prove the bug exists, but does it extend to being able to prove the bug is fixed later or would it just override the state to make it bad again? It doesn't really apply to future regression testing if the implementation changes, and doesn't answer the question of how common these issues might be in real-world scenarios.

I'm certainly sensitive to the fact that the nature of a good hash function might make it hard to discover an input which triggers a particular output, so the ideal outcome here might not be possible.

My interest in the Blake hash is for its use in EdDSA, where it's part of key generation. My understanding there is that if the bug were fixed, and some existing private key were an input which encounters the bug, we'd expect to derive a different public key from that private key after the bugfix. If some user/server's identity were tied to that private key, their public key and commitment would change, which would be troublesome since those are probably published/shared in various places. I think that old signatures would still verify using the old public key (since Blake isn't involved in verification).

I say all this not to suggest we shouldn't fix the bug, but to understand the potential impact to existing Zupass users, and how we might mitigate it. One thing we could do pre-emptively is run key derivation using old (buggy) and new (fixed) code (or some known-good alternative implementation) and compare the results. That would be straightforward to do for widely publicized public keys like Zupass and Devcon. Harder to do for the 12K+ individual Zupass users who hold their own private keys. I could imagine putting some code into Zupass to check for that and report it to the server. Not sure what we'd do if we get a report, though.

The difficulty and uncertainty about that last piece is why I'd really like to know how common we expect this bug to be. That seems like something somebody with a deeper understanding of the algorithm could answer. Given a private key of 64 random bytes, does this bug trigger for one input in 100? Or one in 2^256? Or something in between? If it's highly unlikely that any of our users is actually effected, then I'd say just fix it and we'll only deal with fallout if it happens. But if half of Zupass users are going to have corrupted identities, then we'll need a migration plan.