Security Concern of Possible Collisions

[Metric]

According to the code, Siphash is only taking the first 16 bytes total for k0 an k1 from the sha256 hash. Which means, it has a probability of collision as that of a MD5 hash.

I am referring to this:

public Cuckoo(byte[] header) {
    byte[] hdrkey;
    try {
      hdrkey = MessageDigest.getInstance("SHA-256").digest(header);
      long k0 = u8to64(hdrkey, 0);
      long k1 = u8to64(hdrkey, 8);
      v[0] = k0 ^ 0x736f6d6570736575L;
      v[1] = k1 ^ 0x646f72616e646f6dL;
      v[2] = k0 ^ 0x6c7967656e657261L;
      v[3] = k1 ^ 0x7465646279746573L;
    } catch(NoSuchAlgorithmException e) {
      System.out.println(e);
      System.exit(1);
    }
  }

Recommendation: create k0,k1,k2,k3 each with 64bit integers from throughout the sha256 32 bytes.

would be better if it was:

public Cuckoo(byte[] header) {
    byte[] hdrkey;
    try {
      hdrkey = MessageDigest.getInstance("SHA-256").digest(header);
      long k0 = u8to64(hdrkey, 0);
      long k1 = u8to64(hdrkey, 8);
      long k2 = u8to64(hdrkey, 16);
      long k3 = u8to64(hdrkey, 24);

      v[0] = k0 ^ 0x736f6d6570736575L;
      v[1] = k1 ^ 0x646f72616e646f6dL;
      v[2] = k2 ^ 0x6c7967656e657261L;
      v[3] = k3 ^ 0x7465646279746573L;
    } catch(NoSuchAlgorithmException e) {
      System.out.println(e);
      System.exit(1);
    }
  }

This ensures it uses the full 32 bytes of the sha256 hash.

[tromp]

dear Metric,

According to the code, Siphash is only taking the first 16 bytes total for k0 an k1 from the sha256 hash. Which means, it has a probability of collision as that of a MD5 hash.

Yes, I used to think that 2^128 different PoW challenges are enough. The only risk is that with N Cuckoo Cycle PoWs already solved (among all coins using CC), there is N*2^-128 chance (per nonce tried) of being able to reuse one. It also requires the earlier solution to satisfy the current, likely higher, difficulty threshold. With N unlikely to get much larger than 2^32, the risk of PoW reuse is highly unlikely, less than 2^-64 for trying 2^32 nonces. Furthermore, it would require storage of N solutions with fast lookups.

Recommendation: create k0,k1,k2,k3 each with 64bit integers from throughout the sha256 32 bytes.

But there also seem no downsides to doubling the siphash key space, apart from losing compatibility with existing siphash libraries. So I plan to adopt your recommendation. Give me some time to consult with existing deployments and find out in what timeframe they can roll this out.

Thanks for your input!

regards, -John

[Metric]

Another possibility is to use the current 128 bit key, but then actually use the rest of the hash bytes as part of the nonce message that is being siphashed.

That way it technically still conforms to the standard SipHash format. But it still uses all of the 32 bytes associated with the sha256 hash.

On Wed, Dec 13, 2017 at 5:54 AM John Tromp notifications@github.com wrote:

dear Metric,

According to the code, Siphash is only taking the first 16 bytes total for k0 an k1 from the sha256 hash. Which means, it has a probability of collision as that of a MD5 hash.

Yes, I used to think that 2^128 different PoW challenges are enough. The only risk is that with N Cuckoo Cycle PoWs already solved (among all coins using CC), there is N*2^-128 chance (per nonce tried) of being able to reuse one. It also requires the earlier solution to satisfy the current, likely higher, difficulty threshold. With N unlikely to get much larger than 2^32, the risk of PoW reuse is highly unlikely, less than 2^-64 for trying 2^32 nonces. Furthermore, it would require storage of N solutions with fast lookups.

Recommendation: create k0,k1,k2,k3 each with 64bit integers from throughout the sha256 32 bytes.

But there also seem no downsides to doubling the siphash key space, apart from losing compatibility with existing siphash libraries. So I plan to adopt your recommendation. Give me some time to consult with existing deployments and find out in what timeframe they can roll this out.

Thanks for your input!

regards, -John

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/tromp/cuckoo/issues/36#issuecomment-351370087, or mute the thread https://github.com/notifications/unsubscribe-auth/AAPUbWym5eDo88YMeYH4jNCEdowlA-Etks5s_7sGgaJpZM4Q_9rd .

[tromp]

dear Metric,

Another possibility is to use the current 128 bit key, but then actually use the rest of the hash bytes as part of the nonce message that is being siphashed.

But then I'd want to precompute the siphash state after processing those hash bytes, for speed, and I'd still end up with a 256 bit midstate. So I might as well just double my sipkeys state to 256 bits. I decided to further simplify the siphash24 computation by avoiding the XORing of siphash keys with the 4 64-bit fixed values. You can still recover the original siphash24 values by calling setkeys with appropriately massaged values. In fact, I'm thinking of leaving in a preprocessor define option for that...

regards, -John