Encoding Collision Resistance

[daxpedda]

When creating protocols/algorithms that are generic over hashes, it could be useful to constrain hashes depending on their collision resistance.

The primary motivation, which also serves as an example, is properly constraining ExpandMsg implementations according to the spec. Both expand_message_xmd and expand_message_xof require the hash's collision resistance to be at least higher than the curves security level.

For expand_message_xmd this was simpler, because it requires a hash with a fixed output, so the requirement is set that the output size of the hash has to be at least twice the security level of the curve. I implemented this constraint in #1813. I don't know if this is a general property of cryptographically secure hash algorithm, but I suspect it just aligns with SHA-2/SHA-3.

For expand_message_xof, there is currently no way to extract any information from an existing trait about this. However, e.g. for SHAKE the specification is quite clear about the collision resistance.

I propose adding an associated type to HashMarker, like this:

trait HashMarker {
    type CollisionResistance: ArraySize;
}

I'm happy to do the implementation upon approval!

[newpavlov]

Sounds good, but I am not sure that HashMarker is the best place for it since it also may be useful for MACs.

Another open question is what to do with truncated outputs. For example, what should we use for the "collision resistance" number of BLAKE2b used with output variable at runtime (i.e. Blake2bVar)? What about compile time (i.e. Blake2b)? What about theoretically compromised algorithms which provide lower theoretical collision resistance than claimed (e.g. Streebog)?

[daxpedda]

Sounds good, but I am not sure that HashMarker is the best place for it since it also may be useful for MACs.

Maybe a separate trait is necessary then?

For example, what should we use for the "collision resistance" number of BLAKE2b used with output variable at runtime (i.e. Blake2bVar)?

I don't know where this is used exactly, but if desirable these would need a different trait. E.g. CollisionResistanceVar with a function to calculate the collision resistance at runtime.

What about compile time (i.e. Blake2b)?

I was thinking along the lines of:

impl<OutSize> CollisionResistanceFixed for Blake2b<OutSize>
where
    OutSize: ArrayLength<u8> + IsLessOrEqual<U64, Output = True> + Mul<U8>,
    Prod<OutSize, U8>: Div<U2>,
    Quot<Prod<OutSize, U8>, U2>: Unsigned,
{
    type CollisionResistance = Quot<Prod<OutSize, U8>, U2>;
}

What about theoretically compromised algorithms which provide lower theoretical collision resistance than claimed (e.g. Streebog)?

It seems to me that we need to go with whats claimed. Otherwise constraints would block certain hashes that would be needed in practice but in the meantime had their collision resistance reduced because of discovered attacks.

---

So after some more thinking with the input you gave, I propose the following:

trait CollisionResistanceFixed {
    type CollisionResistance: Unsigned;
}

trait CollisionResistanceXof {
    fn collision_resistance_with_output(len: u64) -> u16;
}

trait CollisionResistanceVar {
    fn collision_resistance(&self) -> u16;
}

// Implementation Examples

impl<OutSize> CollisionResistanceFixed for Blake2b<OutSize>
where
    OutSize: ArrayLength<u8> + IsLessOrEqual<U64, Output = True> + Mul<U8>,
    Prod<OutSize, U8>: Div<U2>,
    Quot<Prod<OutSize, U8>, U2>: Unsigned,
{
    type CollisionResistance = Quot<Prod<OutSize, U8>, U2>;
}

impl CollisionResistanceXof for Shake256 {
    fn collision_resistance_with_output(len: u64) -> u16 {
        ((len / 2).min(256)) as u16
    }
}

impl CollisionResistanceVar for Blake2bVar {
    fn collision_resistance(&self) -> u16 {
        (self.output_size() * 8 / 2) as u16
    }
}

#[test]
fn test() {
    assert_eq!(
        <Blake2b<U64> as CollisionResistanceFixed>::CollisionResistance::U16,
        256
    );
    assert_eq!(
        <Blake2b<U32> as CollisionResistanceFixed>::CollisionResistance::U16,
        128
    );
    assert_eq!(Shake256::collision_resistance_with_output(512), 256);
    assert_eq!(Shake256::collision_resistance_with_output(256), 128);
    assert_eq!(Shake256::collision_resistance_with_output(1024), 256);
    assert_eq!(Blake2bVar::new(64).unwrap().collision_resistance(), 256);
    assert_eq!(Blake2bVar::new(32).unwrap().collision_resistance(), 128);
}

If there is a demand to "query" XOFs at compile time, we could also provide this:

trait CollisionResistanceXofConst<O> {
    type CollisionResistance: Unsigned;
}

// Implementation Example

impl<O> CollisionResistanceXofConst<O> for Shake256
where
    O: Mul<U2>,
    Prod<O, U2>: Div<U2>,
    Quot<Prod<O, U2>, U2>: Min<U256>,
    Minimum<Quot<Prod<O, U2>, U2>, U256>: Unsigned,
{
    type CollisionResistance = Minimum<Quot<Prod<O, U2>, U2>, U256>;
}

[newpavlov]

I am not sure about utility of CollisionResistanceXof/Var. I think we could just say that the trait is not implemented for hashes with output size variable at runtime. And I think XOFs (and their readers) can implement the fixed variant, no?

[daxpedda]

I am not sure about utility of CollisionResistanceXof/Var. I think we could just say that the trait is not implemented for hashes with output size variable at runtime.

To address the constraints around hash2curve, at least CollisionResistanceXof would be necessary. E.g., very specifically, using the ed448/SHAKE-256/expand_message_xof configuration of OPRF would require this.

And I think XOFs (and their readers) can implement the fixed variant, no?

E.g. SHAKE-256, doesn't have fixed variants. Do we want to introduce fixed variants on demand, or did you have something else in mind? E.g. for my use-case that would be 512-bit output size. The newly introduced XofFixedWrapper would not be able to implement this without e.g. CollisionResistanceXofConst.

[newpavlov]

SHAKE-n provides n bits of collision resistance assuming you generated at least 2*n bits. In the trait we could specify this number with the caveat that users have to generate the sufficient number of bits to achieve it. We also could apply the same principle to the hashes with output size variable at runtime.

[daxpedda]

So going back to expand_message_xof: the output size is determined by the length parameter supplied. If length is anything else then the necessary bits to get the maximum collision resistance, we would be unable to maintain the constrain or outright disallow it.

Unless the formula min(n/2, max) applies to all hashes? Then any collision resistance from a variable output length could be calculated by the user from the maximum.

In this case the proposal would look like this:

trait CollisionResistance {
    type CollisionResistance: Unsigned;
    type OutputSize: ArrayLength<u8>;
}

[newpavlov]

Unless the formula min(n/2, max) applies to all hashes?

I think it should apply to all non-broken hashes.

We probably can just use:

trait CollisionResistance {
    type CollisionResistance: Unsigned;
}

Whether users have to take into account output size or not will depend on the concrete use case.

[daxpedda]

Unless the formula min(n/2, max) applies to all hashes?

I think it should apply to all non-broken hashes.

Nice! Thanks for confirming!

We probably can just use:

trait CollisionResistance {
    type CollisionResistance: Unsigned;
}

Whether users have to take into account output size or not will depend on the concrete use case.

I'm not following, do you mean you would like to see a use case?
ExpandMsgXof::expand_message() is the use-case I was talking about all along. According to the spec we have to make sure that the given len_in_bytes together with the given HashT isn't lower than K (introduced in #1813).
See https://www.rfc-editor.org/rfc/rfc9380.html#section-5.3.2-2.1:

• The collision resistance of H MUST be at least k bits.

And the output size of the hash is defined by the parameter len_in_bytes in the specification as well.

Equally I intend to enforce this limit at compile-time if possible in voprf.

Apologies if I misunderstood your intention here!

[newpavlov]

I mean that you would have to write in your code:

// Assuming K is converted to bytes
if 2 * len_in_bytes < K || H::CollisionResistance::USIZE < K {
    return Err(...);
}

In other words, handling potential smaller lengths used in runtime would not be an area of responsibility of the CollisionResistance trait.

[daxpedda]

Sure, that works for me.
Will go ahead and make a PR then!