Collisions in type_id

The implementation of type_id from #10182 uses SipHash on various parameters depending on the type. The output size of SipHash is only 64-bits, however, making it feasible to find collisions via a Birthday Attack. I believe the code below demonstrates a collision in the type_id value of two different ty_structs:

use std::hash;
use std::hash::Streaming;

// I believe that this pretty much the same thing as hash_crate_independent() in ty.rs
// for a ty_struct on a 64-bit platform
fn hash_struct(local_hash: &str, node: u64) -> u64 {
    let mut state = hash::default_state();
    state.input([18]);
    state.input(local_hash.as_bytes());
    do node.iter_bytes(true) |bytes| { state.input(bytes); true };
    state.result_u64()
}

fn main() {
    // This represents two structures with different node values from a crate with a 
    // local_hash value of "local" that end up getting the same hash and thus, 
    // I think, the same type_id
    assert!(hash_struct("local", 0x9e02c8943c336302) == hash_struct("local", 0x366a806b1d5f1b2));
}

I'm not entirely sure how feasible it is for a program to have 0x366a806b1d5f1b2 node ids (2.5 trillion), but this is still concerning.

We could in theory have very cheap inequality among types, and then have an expensive equality check. Something which may walk the respective TyDesc structures in parallel to make sure that they're the same. We could also bump up the hash size to using something like sha1/sha2 and have the type_id() intrinsic return [u8, ..N] to reduce the possibility of a collision.

Either way, I don't think that this is a super-pressing issue for now, but I'm nominating to discuss whether we want to get this done for 1.0. This could in theory have serious implications depending on how frequently Any is used.

Ah, it was already nominated!

Why not compare an interned version of the type data string? (i.e. what is currently passed as data to be hashed, possibly SHA-256 hashed first)

The linker can be used for interning by emitting a common symbol with the type data string as name and taking its address, and otherwise the same thing can be done manually in a global constructor.

This way it's always a pointer comparison, and there are no collisions.

I don't know how node id values are generated, but assuming that they are generated sequentially, this particular collision is not realistic. However, its not hard to find collisions for more realistic node id values by picking particular values for the crate hashes:

assert!(hash_struct("a2c55ca1a1f68", 4080) == hash_struct("138b8278caab5", 2804));

The key thing to consider isn't the number of node id values, though: its the total number of type id values. Some quick (hopefully correct) math shows that there is a 0.01% chance of a collision once there are around 60 million type id values. That's still a pretty large number of type id values for a somewhat low probability of a collision, thought. So, its unclear to me how big a deal this is for the Rust 1.0 timeframe. It all depends on what the acceptable probability of a collision is.

@alexcrichton

When I saw that @alexcrichton proposed using a hash, my first reaction was "collision!" but then I thought "...but exceedingly unlikely to occur in practice". I think this is not a matter of imminent destruction but if we can leverage the linker or some other scheme to avoid this danger, we should -- and perhaps we should just go ahead and mark the current scheme as deprecated and just plan on finding a replacement scheme.

A cryptographic hash designed for this purpose (larger output) would be enough. Although, a larger output would be more expensive to compare (four u64 comparisons for SHA2).

We don't need to deal with this right now. P-low.

How relevant is this issue today? I think that it's all the same, but am not sure.

It's 64-bit so collisions are likely with enough types (consider recursive type metaprogramming) and it doesn't have any check to bail out if one occurs. Bailing out is not a very good solution anyway, because it pretty much means that there's no way to compile the program, beyond using a different random seed and hoping for the best. It's a crappy situation.

Note that "hoping for the best" by iteratively changing the seed might work with overwhelmingly large probability after very few iterations.

use std::any::Any;

fn main() {
    let weird : [([u8; 188250],[u8; 1381155],[u8; 558782]); 0] = [];
    let whoops = Any::downcast_ref::<[([u8; 1990233],[u8; 798602],[u8; 2074279]); 1]>(&weird);
    println!("{}",whoops.unwrap()[0].0[333333]);
}

Actually a soundness issue. playground: http://is.gd/TwBayX

I'd like the lang team to devote a little time to this now that we are post 1.0. Nominating

OK, lang team discussed it, and our conclusion was that:

This issue ought to be fixed, it's silly not to.
This is an implementation detail that we could change whenever we want (right?)
Nonetheless, we probably ought to open an RFC or at least a discuss thread, with a proposal to do better, since probably people will have some clever ideas.
Probably the runtime overhead of the virtual call in the Any trait is way more than a strcmp anyhow for all realistic types.

Given that this issue has had way too many comments, I think what I'd propose to do is open a new issue that summarizes the current state of the discussion. Here's a proposed issue description; please speak up if there's something that you think is not properly represented.

Strong 👍 for this -- I found the issue summary very helpful. I'd like to encourage others to avoid directly commenting and instead limit yourselves (for the moment) to comment on what is not represented in this summary (ideally with a suggested edit), so that we can close this issue and restart afresh from a better starting point.

@the8472

From the comments so far since my summary, there's multiple discussions that should likely go into separate issues:

How can we make TypeId use a strong hash (or not depend on a hash at all) -- what's the best practical way to achieve that? That's the issue for which I wrote a summary above.
Should we really require a cryptographic hash function, or is it enough to be resistant against code that wasn't deliberately written to attack the hash? @the8472 has been suggesting a model along the lines of: yes, we have a fixed key hard-coded in the compiler, but if we assume code isn't written to attack the hash, then we can assume code is written without making use of this knowledge of the key, and therefore for this weak threat model we can act as-if the key is actually random. @briansmith has been arguing that this is not strong enough. I won't be doing the summary for this one, I hope someone else can.
One question I find interesting here is whether we can make any such collision "unstable" in the sense of making it not work across compiler versions, e.g. by putting the compiler version into the initial state of the hasher (or into the key, or so). I have no idea what the hardness would be of finding a collision that works for multiple different keys / prefixes, but if that is genuinely hard for a PRF, then this seems somewhat more secure than the status quo.

I think we're fairly sure that (1) can be done without significant perf impact, given that TypeId hashing is not a super common operation, and there are various proposals for how to make most TypeId comparisons fast. Binary size impact has yet to be determined, this requires someone to actually implement a prototype. (There's an old PR at #95845 for one of the variants that doesn't rely on a hash at all, which is the least size-efficient option. As far as I can see, perf looked completely fine, though there were some complaints about having type names in the final binary. But there's also people that want a TypeId -> TypeName function. But anyway this is all t-compiler territory.)

However, the compiler uses hashes in many places, so one question that is still unclear to me is whether just making TypeId use a stronger hash would actually fix anything, or whether it just shifts the problem to a different hash. It would be good to get input from people familiar with how our query system works on whether, for non-incremental builds, collisions in the stable hasher can lead to problems. Because if the answer is "yes", then (1) on its own seems a bit pointless, and we should evaluate the cost of making all the critical hashes more secure to really get the proper data for discussion (2). If the answer is "no", then I honestly see no good reason to not do (1); it seems like we can get protection against a stronger threat model without significant cost. At this point (2) would be about the threat model for incremental builds. The lang team has not decided on this, and existing data indicates that using a stronger hash here has a massive performance cost, but I don't know what possibilities exist to reduce that cost.

So -- @michaelwoerister and anyone else who knows the query system, can you help us answer this question? :)
@michaelwoerister you wrote in #127809

To elaborate on that: there might cases like that but at least for DepNode, DefPathHash, StableCrateId, legacy-symbol-name hashes, and incr. comp. query result hashing we need there to be no collisions. For the first three of these we check for collisions and have never found one.

but it's not clear to me whether this applies to all builds or just incremental builds.

Is a linkage capable of bringing in more types than it has bytes of machine code, or (if dynamic) types that will survive when it's unloaded? If not, we can use sequential IDs starting with the linkage address.

How can we make TypeId use a strong hash (or not depend on a hash at all) -- what's the best practical way to achieve that? That's the issue for which I wrote a summary above.

Personally, I think eddyb chose a good approach in #95845 by reusing the symbol mangling scheme, as that has the same requirements of strong collision freedom. If we decide to use a strong, wide hash then I would still go

type ==(v0_mangle)==> type-as-string ==(hash)==> type-id

That way the implementation does not need to rely on StableHasher and, more importantly, HashStable implementations. Making HashStable impls generic over the hash algorithm would lead to binary bloat and some HashStable impls do some non-trivial internal caching which makes it harder to reason about their correctness. In contrast, if we just have to hash a symbol name, we can, for example, simply use the sha256 implementation we already have in the compiler for MSVC debuginfo.

To elaborate on that: there might cases like that but at least for DepNode, DefPathHash, StableCrateId, legacy-symbol-name hashes, and incr. comp. query result hashing we need there to be no collisions. For the first three of these we check for collisions and have never found one.

but it's not clear to me whether this applies to all builds or just incremental builds.

We unconditionally check for collisions of DefPathHashes for every kind of build and every kind of compiler version (e.g. no compiler built with debug assertions is needed):

rust/compiler/rustc_hir/src/definitions.rs

Lines 58 to 76 in e08b80c

    
                   // Check for hash collisions of DefPathHashes. These should be 
        
                   // exceedingly rare. 
        
                   if let Some(existing) = self.def_path_hash_to_index.insert(&local_hash, &index) { 
        
                       let def_path1 = DefPath::make(LOCAL_CRATE, existing, |idx| self.def_key(idx)); 
        
                       let def_path2 = DefPath::make(LOCAL_CRATE, index, |idx| self.def_key(idx)); 
        
                       // Continuing with colliding DefPathHashes can lead to correctness 
        
                       // issues. We must abort compilation. 
        
                       // 
        
                       // The likelihood of such a collision is very small, so actually 
        
                       // running into one could be indicative of a poor hash function 
        
                       // being used. 
        
                       // 
        
                       // See the documentation for DefPathHash for more information. 
        
                       panic!( 
        
                           "found DefPathHash collision between {def_path1:?} and {def_path2:?}. \ 
        
                               Compilation cannot continue." 
        
                       ); 
        
                   }

We also unconditionally check for collisions of StableCrateId for all crates the compiler sees at once:

rust/compiler/rustc_metadata/src/creader.rs

Lines 177 to 181 in e08b80c

    
           } else if let Some(crate_name1) = self.metas[existing].as_ref().map(|data| data.name()) 
        
           { 
        
               let crate_name0 = root.name(); 
        
               CrateError::StableCrateIdCollision(crate_name0, crate_name1) 
        
           } else {

DepNode values are only created during incremental builds.

However, the compiler uses hashes in many places, so one question that is still unclear to me is whether just making TypeId use a stronger hash would actually fix anything, or whether it just shifts the problem to a different hash.

As said above, going through v0 mangling would basically fix this issue. The only hash that occurs in v0 is the StableCrateId. Any problem with collisions in that scheme would also be a problem with symbol names, so it is unlikely to go undetected.

One question I find interesting here is whether we can make any such collision "unstable" in the sense of making it not work across compiler versions, e.g. by putting the compiler version into the initial state of the hasher (or into the key, or so).

We already mostly do that by mixing the compiler version into StableCrateId. So types containing any kind of path already have a compiler-version-dependent stable hash. Also initializing the hashers with the compiler version seems like a good thing to do and should have a negligible performance impact.

(2) would be about the threat model for incremental builds.

Unless I'm overlooking something all incr. comp. specific hashes only need to be stable between successive incremental builds. So we can easily harden our use of SipHash there by generating random keys and then caching these in the incr. comp. cache.

@michaelwoerister

Great, thanks @michaelwoerister!
I have opened #129014 for changing type_id to be at least as good as a cryptographic hash function, aligning them with the t-lang decision.

I have opened #129016 for the questions around incremental compilation. If I missed an aspect if this, please bring it up in that issue.

For the people arguing that for type_id, we should consider a PRF (or even a weakened one like SipHash-1-3) to be good enough since we don't expect Rust programmers to try to exploit the compiler, I would suggest you file a new issue with the arguments for that and nominate it for t-lang discussion. Personally, since it seems like #129014 can be fixed without major downsides, I don't see a good case for weakening the requirement here.

initializing the hashers with the compiler version seems like a good thing to do and should have a negligible performance impact.

@michaelwoerister would it make sense to file this as a possible-improvement issue? Maybe it'd be better if you did this since you could point at where in the compiler that would even happen.

I will then close this issue, as further discussion should happen in the existing or to-be-created successor issues. Thanks all for the discussion!

@michaelwoerister

@michaelwoerister would it make sense to file this as a possible-improvement issue? Maybe it'd be better if you did this since you could point at where in the compiler that would even happen.

I'll look into opening an issue.

@michaelwoerister

I opened rust-lang/unsafe-code-guidelines#525 for potential hashing concerns related to dlopen (where the uniqueness checks @michaelwoerister mentioned can't be run).

Rollup merge of rust-lang#148394 - jieyouxu:remark-typeid-no-layout-g…

Unrolled build for #148394

Rollup merge of #148394 - jieyouxu:remark-typeid-no-layout-guarantees…

Rollup merge of rust-lang#148394 - jieyouxu:remark-typeid-no-layout-g…

Merge rust-lang#10389

Navigation Menu

Repository navigation

Collisions in type_id #10389

155 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	// Check for hash collisions of DefPathHashes. These should be
	// exceedingly rare.
	if let Some(existing) = self.def_path_hash_to_index.insert(&local_hash, &index) {
	let def_path1 = DefPath::make(LOCAL_CRATE, existing, \|idx\| self.def_key(idx));
	let def_path2 = DefPath::make(LOCAL_CRATE, index, \|idx\| self.def_key(idx));

	// Continuing with colliding DefPathHashes can lead to correctness
	// issues. We must abort compilation.
	//
	// The likelihood of such a collision is very small, so actually
	// running into one could be indicative of a poor hash function
	// being used.
	//
	// See the documentation for DefPathHash for more information.
	panic!(
	"found DefPathHash collision between {def_path1:?} and {def_path2:?}. \
	Compilation cannot continue."
	);
	}

	} else if let Some(crate_name1) = self.metas[existing].as_ref().map(\|data\| data.name())
	{
	let crate_name0 = root.name();
	CrateError::StableCrateIdCollision(crate_name0, crate_name1)
	} else {

Collisions in type_id #10389

Description

Activity

alexcrichton commented on Nov 10, 2013

alexcrichton commented on Nov 10, 2013

bill-myers commented on Nov 10, 2013

DaGenix commented on Nov 11, 2013

nikomatsakis commented on Nov 11, 2013

thestinger commented on Nov 11, 2013

pnkfelix commented on Nov 21, 2013

steveklabnik commented on Jan 20, 2015

thestinger commented on Jan 20, 2015

vks commented on Jan 21, 2015

sorear commented on Oct 14, 2015

pnkfelix commented on Oct 18, 2015

nikomatsakis commented on Oct 29, 2015

155 remaining items

nikomatsakis commented on Jul 25, 2024

RalfJung commented on Jul 25, 2024

Pr0methean commented on Aug 11, 2024

michaelwoerister commented on Aug 12, 2024

RalfJung commented on Aug 12, 2024

michaelwoerister commented on Aug 12, 2024

RalfJung commented on Aug 13, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions