type_id is not sufficiently collision-resistant

[apiraino]

Meeting proposal info

• Title: type_id is not sufficiently collision-resistant
• Type: technical

Summary

See opening comment in rust#129014:

The soundness of functions like downcast relies on the type_id of two different types never being equal. Currently, the type_id is a 128-bit hash of the full type identity, computed specifically via SipHash-1-3 with an all-zero key. This is not a strong enough hash function for this purpose.

and:

We should do one of the following:

1. switch to a stronger hash function, or
2. switch to a different scheme that doesn't rely on collision-resistance of the hash function.

Discussed on Zulip during triage meeting.

About this issue

This issue corresponds to a meeting proposal for the compiler team
steering meeting. It corresponds to a possible topic of
discussion. You can read more about the steering meeting procedure
here.

Comment policy

These issues are meant to be used as an "announcements channel"
regarding the proposal, and not as a place to discuss the technical
details. Feel free to subscribe to updates. We'll post comments when
reviewing the proposal in meetings or making a scheduling decision.
In the meantime, if you have questions or ideas, ping the proposers
on Zulip (or elsewhere).

[RalfJung]

Cc rust-lang/rust#129030

[apiraino]

Meeting has been scheduled on Zulip for Dec, 6th

@rustbot label +meeting-scheduled

[RalfJung]

What was the conclusion of the meeting?

This is on the critical path for rust-lang/rust#77125; it'd be nice to make some progress. :)

[apiraino]

@RalfJung sorry, this went out of my radar. Meeting took place on Zulip.

The summary: Out of the options suggested, seems that switching to not rely on hashing for soundness could give us the best results, also taking into account an increased size and perf. cost. Instead use a pair of a (not-soundness-critical) hash and a pointer but still use hashing as an optimization.

The meeting didn't set any actionables so I'm not sure about them. You can probably talk to us, T-compiler.

(David also posted a brief comment about not treating is as a security concern because - so far - we have no concrete threat-model scenario)