Quantum Preimage Attack (Only Practical in Sci-Fi)

[phroi]

Hey Folks at Cryptape, I was re-examining the design of the design of QRL and the following attack came to mind:

• Quantum Preimage Attack: The attacker targets the 32-byte args hash and uses quantum techniques (e.g., Grover's algo) to find a preimage of the hash, bypassing the multisig protection.
• Forging Public Keys: The attacker can use weaker SPHINCS+ parameter sets (e.g., sphincs-sha2-128f) to forge public keys that still match the original args hash, bypassing the multisig requirement.
• L1 Lock Acceptance: The lock script accepts any SPHINCS+ set, meaning that an attacker can craft a configuration with a weaker parameter set and still pass the args hash check.

Follows a more verbose explanation.

Intro

A sufficiently powerful quantum attacker can exploit the design of the c-sphincs-all-in-one-lock to forge a valid multisig configuration by finding a preimage of the 32-byte args hash used to identify the lock configuration. This allows the attacker to bypass the multisig requirement and potentially unlock funds without ever recovering the honest private keys.

The weakness arises from the fact that the args hash is derived from the multisig configuration, which includes public keys and their associated SPHINCS+ parameter sets. The quantum attacker can leverage techniques such as Grover's algo to efficiently search for a preimage of the hash, allowing them to substitute forged public keys in place of the original ones.

High-Level Example

Scenario

Imagine a 170-of-255 multisig configuration using the c-sphincs-all-in-one-lock. The configuration specifies 255 public keys, each associated with a post-quantum SPHINCS+ signature, and requires 170 out of these 255 signatures to unlock the funds. For simplicity, all public keys are generated using sphincs-sha2-256s, the strongest quantum-resistant algo.

The 32-byte args hash for the lock script is derived from the multisig configuration, which includes the public keys and their associated parameter sets. This args hash is then used by the lock script to verify the identity of the configuration.

However, the lock script itself supports all 12 SPHINCS+ parameter sets, including weaker algos like sphincs-sha2-128f. This provides a potential attack vector where a quantum attacker can find a preimage of the 32-byte args hash, effectively bypassing the multisig protection.

Step-by-step Attack Process

Multisig Configuration and args Calculation

The organization sets up a 170-of-255 multisig configuration with 255 public keys, each associated with a strong SPHINCS+ algo (e.g., sphincs-sha2-256s). The lock script's args field is derived from the blake2b hash of the multisig configuration, which includes the public keys and parameter sets, e.g.,
args = blake2b(personalized("ckb-sphincs+-sct", multisig_configuration)).

Attack Goal

The attacker aims to find a preimage for the 32-byte args hash that matches the original multisig configuration, without needing to know the exact public keys or private keys. If the attacker can craft a configuration that produces the same args hash, the lock will accept it, and they can bypass the multisig requirement.

Quantum Preimage Search

The attacker uses a quantum computer and Grover's algo (or another quantum search method) to run an efficient preimage attack on the blake2b hash function, targeting the 32-byte args hash. The goal is to find a public key (or a configuration of public keys and parameter sets) that produces the same 32-byte hash as the original multisig configuration.

The attacker doesn't need to match the exact public keys used in the original configuration. They only need to find any configuration (possibly using weaker SPHINCS+ parameter sets, like a non-multisig sphincs-sha2-128f) that produces the same hash.

Forged Configuration

Once the attacker finds a valid preimage, they can substitute the forged public keys (which may use weaker SPHINCS+ algos like sphincs-sha2-128f) into the transaction witness. This results in a forged configuration that matches the original args hash.

The attacker's forged configuration, even with weaker parameter sets, matches the original 32-byte args hash, and the lock script will accept it as valid.

Bypassing the Multisig Lock

The lock script checks the 32-byte args in the transaction, and since the attacker has found a preimage that matches the hash, the lock accepts the forged configuration and bypasses the multisig check.

The attacker doesn't need to know the private keys of the original multisig participants. The lock script only cares about the 32-byte hash and doesn't distinguish between different SPHINCS+ parameter sets, allowing the forged configuration to succeed.

Result

The attacker successfully bypasses the multisig protection and gains access to the cell, despite the original configuration being designed to require 170 valid signatures from 255 public keys. The attacker has effectively substituted forged public keys in the multisig configuration, bypassing the intended security.

Conclusion

This attack illustrates how the design of c-sphincs-all-in-one-lock, particularly the way the 32-byte args hash is calculated, could constitute a future potential weakness to quantum preimage attacks. By exploiting the ability to find a preimage of the args hash, an attacker could forge public keys and bypass the multisig requirements, even if the configuration originally used strong post-quantum algos.

Any QRL configuration's security is only as strong as QRL weakest algorithm.

Keep up the great work 💪
Phroi %122

[XuJiandong]

Quantum Preimage Attack: The attacker targets the 32-byte args hash and uses quantum techniques (e.g., Grover's algo) to find a preimage of the hash, bypassing the multisig protection.

This statement is not true. With grover algorithm, it reduces security from 2^256 to 2^128. It's still safe.

[phroi]

Hey @XuJiandong, thank you for your reply!

Yes, I'm not saying that QRL is not QR (as all its components are currently QR, QR being a moving target).

I'm just dutifully noting that blake2b use makes a multi-sig configuration potentially weaker than its full non-hashed representation.

On the same line of thoughts, one could argue that if blake2b was to become QRL failure point, then we have bigger fish to fry with L1 design (same attack applied to references by data/type/..)

So I would argue that maybe we should start thinking how to enforce for L1 references that hash equality => underlying data equality (using L1 history). If hash equality, but NOT underlying data equality, then raise an error.

Love & Peace, Phroi %26