Security of the Haircomb

Security of the Haircomb Signature Scheme

The security of the Haircomb signature scheme is based on the hardness of the collision search problem for the underlying hash function. The scheme is designed to resist attacks from both classical and quantum computers. The security of the scheme depends on the parameter n (number of bits in the output of the underlying hash function). The scheme is believed to be secure as long as the underlying hash function is secure and the internal parameters are chosen correctly. The expected security level of the proposed scheme, which uses SHA256 (n=256) as the underlying hash function, is estimated to be at least 128 bits, as explained below.

The security strength of a hash function against quantum attacks is usually estimated as half the number of bits in its output size. SHA-256 has a 256-bit output size, so its classical security strength is estimated to be 128 bits. However, Grover's algorithm can provide a quadratic speedup over classical algorithms for searching an unsorted database, which means that it could theoretically be used to attack a hash function like SHA-256. In the case of SHA-256, Grover's algorithm would require 2^128 operations to find a pre-image, which is still considered infeasible due to the large number of operations required. Therefore, the security strength of SHA-256 against quantum attacks, including Grover's algorithm, is currently considered to be 128 bits.

In addition to Grover's algorithm, there are other quantum algorithms that can potentially break hash functions and other cryptographic primitives. The most well-known of these is Shor's algorithm, which can be used to efficiently factor large numbers and compute discrete logarithms, breaking many popular public key cryptosystems such as RSA and Diffie-Hellman.

However, Shor's algorithm is not a direct threat to the security of hash functions like SHA-256, which are not based on these number-theoretic problems. Instead, quantum attacks on hash functions are typically based on exploiting their algebraic properties or finding collisions (i.e., different inputs that produce the same output).

One example of a quantum attack on hash functions is the Bernstein-Vazirani algorithm, which can be used to efficiently find the pre-image of a given hash value if the hash function has a particular algebraic structure. Another is the Brassard-Hoyer-Tapp algorithm, which can be used to find collisions in a hash function by exploiting the quantum parallelism of Grover's algorithm.

Analysis of the Algorithm with Respect to Known Attacks

• Direct collision attack on the message digest

• Parallel hash collision search by Rho method with distinguished points

• Signature malleability by means of Grover pre-image search

• Collision in the Comb Cutting Function

Direct collision attack on the message digest

If the attacker is capable to generate collisions in the underlying hash function (either classically, or using the Brassard-Hoyer-Tapp algorithm or similar), then he or she is able to give a collided message to the honest signer for signing. After signing by the honest signer, the attacker is able to claim that the other message was also signed.

Parallel hash collision search by Rho method with distinguished points

A potential (classical) attack on this scheme exists through parallel hash collision search by Rho method with distinguished points. The attacker calculates the midstate after hashing the 20 hash chains and keeps extending one last hash chain forward, calculating one new public key per each SHA256 cycle. If the generated public key is a distinguished point of the Rho method, it is shared with other parallel processors. Other parallel processors check whether they also reached the same distinguished point of the Rho method, and if yes, a candidate collision is found.

The parallel processors who reached the same distinguished point go back in the hash chain recreating a public key collision from a memoized seed. This collided public key then allows to sign two distinct valid messages normally (using the two private keys that correspond to a shared public key), which breaks the one-timeness property of the scheme.

It is not believed a rational actors will pursue this kind of attack, the kind of hardware suitable for pursuing this kind of attack is already suitable to get monetary reward in the case of blockchain mining. Note: The underlying calculation is in fact SHA256d, the same calculation used for Bitcoin mining.

Signature malleability by means of Grover pre-image search

If the attacker does posses a quantum computer, is given a honest signature, a pre-image search may be executed on the signature. Because the signature consists of 21 values which are assumed to be results of the underlying hash function, attacker may utilize the quantum computer to solve the pre-image of some of the 21 values.

If there is a success, the attacker can claim a distinct message m2 (m2 =/= m1) was signed, which would be plausible.

In the extreme case, the attacker will do this repeatedly, to eventually solve the final 21 pre-images (the private key).

Collision in the Comb Cutting Function

If the Comb Cutting Function weren't bijective, the attacker could be able to find two message digests with the property that signing one of them also signs the other one. But the Comb Cutting Function was proven to be bijective, and therefore this attack does not apply.