ICS20 GetEscrowAddress pre-image domain overlaps with public keys

[ebuchman]

Surfaced from Informal Systems IBC Audit of cosmos-sdk hash 82f15f3.

GetEscrowAddress is the truncated SHA256(portID + channelID), which is the same address hash used for Ed25519 keys. While portID and channelID are bounded variable length alphanumeric strings, in principle its possible to create 32-byte portID + channelID that are valid Ed25519 public keys. This could enable an attacker to set up a channel and then steal all the funds that are escrowed.

This attack is likely infeasible at present given the need to brute force an Ed25519 public key that begins with transfer and is otherwise fully alphanumeric. However this depends on the validation criteria for channel IDs - if they were ever changed, say to allow arbitrary byte-strings, this attack may become possible.

Thus it would probably wise to use domain separation for the pre-image to these module addresses, for instance a prefix guaranteeing the pre-image is not a valid public key (ie. is too long). It looks like this is worked into ADR-028.

[andrey-kuprianov]

Another issue: encoding escrow addresses as truncated SHA256(portID + channelID) means that port/channel combinations ("transfer", "channel") and ("transfercha", "nnel") will give the same escrow address, which will be the truncated hash of `"transferchannel". This opens the road to exploits.

This exploit on your local chain is possible if your counterparty is able to choose both the port and the channel ids.
The ability to choose only channel ids opens you to the birthday attack wrt. the address length, which is 20 bytes = 160bits. Not too little, but not too many also: from 1/2^160 down to 1/2^80 chance.

I would say both port and channel ids needs to be chosen deterministically, e.g. the port id fixed to "transfer", and the channel id chosen deterministically from the counterparty chain id and some other additional parameters.

Also, for additional security it would be good when computing the hash to separate the port id and the channel id with e.g. "/", i.e. compute it as the truncated hash of SHA256(portID + "/" + channelID)

[cwgoes]

If possible, let's add a prefix to prevent any possibility of ed25519 brute-forcing. We need to check that this won't interfere with any x/bank module logic, although this problem is not specific to IBC, any module which uses a module account needs to protect against this attack (so ideally the means of doing so should be standardised).

[cwgoes]

It seems like we cannot easily add a prefix because parts of the SDK (e.g. here) are dependent on accounts using 20-character addresses. One short-term option is to use a fixed prefix and trim the hash, e.g. "ibcibcibc0" + sha256(portID + channelID)[:10].

This does come at a tradeoff of making collisions between escrow addresses used by different channels more likely, though.

[cwgoes]

... also maybe we should reconsider SHA256 because of Bitcoin mining? Maybe brute-forcing 10 or even 20 bytes is relatively easy?

[aaronc]

Have you read ADR 028 @cwgoes and the surrounding conversations? This has been talked about quite a bit, although not necessarily conclusively.

[ebuchman]

So there are two issues here: collisions between module and non-module accounts, and collisions between module accounts (eg. between those created for each channel). The former should be solved by ADR28 using a pre-image prefix. The latter I think can be solved by domain separation between the port and channel? Eg. port-id / channel-id instead of direct concatenation since neither can contain a /. I believe it should be fine for the module address to still be 20-bytes and the SHA256 hash of something, so long as we have better domain separation in the pre-image.

[colin-axner]

Sweet, thanks for the responses. I have updated the pr to use the AddressHash construction in ADR 028.

[cwgoes]

So there are two issues here: collisions between module and non-module accounts, and collisions between module accounts (eg. between those created for each channel). The former should be solved by ADR28 using a pre-image prefix. The latter I think can be solved by domain separation between the port and channel? Eg. port-id / channel-id instead of direct concatenation since neither can contain a /. I believe it should be fine for the module address to still be 20-bytes and the SHA256 hash of something, so long as we have better domain separation in the pre-image.

We should certainly domain separate the port and channel - above, though, I was talking about collisions between module accounts created not by pre-image collisions but by hash collisions, especially if we're taking the first n bytes of the hash only.

[andrey-kuprianov]

I am not a cryptographer, so here is the very approximate analysis; please take this with a grain of salt.

0. Domain separation between ports and channels: clearly necessary, as this can be exploited with a very cheap attack (constant time and space), but also easily fixable by separating the domains with "/" (see add domain separation between port and channel for transfer escrow address #7960)

As correctly pointed out by Ethan above, we need to separate the two cases:

1. A collision between module accounts and non-module accounts. Assuming the module account address Addr, an attacker will need to find a ECDSA private key, such that for the corresponding public key PK its AddressHash(PK) == Addr.

2. A collision between two module accounts. We assume that the address is obtained as AddressHash(ModuleParams), where ModuleParams e.g. are (PortId, ChannelId). Here there are two alternatives:
   2a) The address for one of the modules is fixed to Addr, and the attacker needs to find such ModuleParams that AddressHash(ModuleParams) == Addr.
   2b) The attacker can actually choose two sets of parameters ModuleParams1 and ModuleParams2, and needs to find a collision such that AddressHash(ModuleParams1) == AddressHash(ModuleParams2)

To properly analyze the cases the following is crucial:

• Case 2b) is fundamentally different from cases 1) and 2a) in that in the former the attacker needs to find a collision between two arbitrary preimages, which makes possible the birthday attack.
• The possible search speed in case 2) is much higher than in case 1), because ECDSA is much more computationally intensive than SHA256.

Let me first illustrate this speed difference:

ECDSA on 2.9 GHz i7-3520m : 42 K guesses/sec (see Table on page 65 here)

SHA256 on my laptop, 1.8GHz i7-8565U

andrey@informal:~$ openssl speed sha256
Doing sha256 for 3s on 16 size blocks: 15021816 sha256's in 3.00s
Doing sha256 for 3s on 64 size blocks: 8298638 sha256's in 3.00s

Translates to ~ 5000 K guesses/sec, so at least 2 orders of magnitude difference.

Take into account this is laptops, single core, so on specialized hardware, multi-core, it will be much faster (see e.g. here)

Taking into account that case 1 is not birthday attack and ECDSA, this case can be considered safe enough.

The most dangerous is case 2b), because birthday attack allows to reduce the probability of a single guess from 1/ 2^160 to 1/2^80. Besides, the birthday attack can be implemented quite efficiently with limited memory using rainbow tables, or even with constant memory.

I believe that birthday attack in combination with very fast guessing for SHA256 makes this computationally feasible. If needed, concrete computations of probability and the necessary resources can be easily performed.

I also strongly believe that ADR-28 does not solve this problem for the module accounts, when the preimage is not the public ECDSA key, but a simple string, as the computational complexity in that case is only the fast SHA256. Whatever prefixes are added to the simple string, the attack algorithms will stay the same.

To mitigate the problem I think this needs to be done:

• do not use a fast hash function, like SHA256, use a slow one: see this discussion for justification.
• first and foremost, prevent the birthday attack, as this makes it dramatically easier for the attacker. For that, ModuleParams should be chosen from a small set of predefined alternatives, i.e. do not allow unbounded or very large preimage spaces. In case of escrow addresses, ModuleParams could be:
  • a prefix and a version number
  • fix PortId to "transfer"
  • deterministically construct ChannelId from e.g. a combination of the Ids of communicating chains and a bounded sequence number, e.g. 1-999. E.g. the escrow address could be AddressHash("ibc-v1/transfer/cosmos-ethereum-001").

The above determinism and boundedness (second point), if implemented, will have the additional benefit of preventing any kind of collisions completely. As it will be possible to enumerate all possible module account addresses for all chain combinations, it will also make possible to reject any attempt to register a non-module account with the same address, or to have two module accounts with the same address.

Will be happy to engage in further discussions or provide other help if needed.

[colin-axner]

Awesome, @andrey-kuprianov thank you so much for the write up! All the proposed solutions can definitely be added.

Recent spec changes to connection and channel identifiers require deterministic identifier creation. After that change and after I update my pr fixing this issue, I think everything will look like this:

prefix: ibc-transfer-escrow-prefix-v1
port: transfer
channel: channel{N} (starting from 0)

AddressHash("ibc-transfer-escrow-prefix-v1/transfer/channel{N}") where {N} is the only variable. It will be bounded by max of a uint64 (will that be fine?)

As far as changing the hash function goes, we can definitely switch away from sha256. Escrow addresses are only ever computed internally and are not user/client facing. The primary reason for choosing sha256 was because of wide adoption/support. Blake2b was mentioned in the creation of ADR 028 so maybe that would be a good alternative? I will leave the pr I have open using sha256 for now, but would like @cwgoes or @ebuchman to decide what should be used

[andrey-kuprianov]

Thanks for the update, @colin-axner! The deterministic identifier selection is indeed the way to go, I think. I am not sure how many channels need to be created between the chains, but I suppose not too many? For the transfer channels I think it makes sense to limit this to a much smaller size, say uint16.

As for the hash function, it could be anything simple, but computationally expensive, e.g. SHA256(PublicKey(SHA256(id))).

As for the deterministic selection of identifiers in #7993: it's probably too late to provide some input at this point, but... some time ago I was designing a protocol that also needed to negotiate a numerical identifier between two parties. What I did was the following:

• Party 1 sends a list of allowed identifier intervals, e.g. [10, 15), [20, 100)
• Party 2 selects one particular identifier from those intervals, e.g. 30.
• They both agree on that identifier.

This approach is a bit more flexible than either sending a particular id, and also has more permission control than allowing the other side just to select anything.

The way this goes is if Party 1 has ids [1,10) and [15,20) occupied, it can just invert this set to get [10, 15), [20, 100). Plus it can impose additional restrictions. And still provide enough freedom for the other side to select an identifier that is free on both sides.

[colin-axner]

For the transfer channels I think it makes sense to limit this to a much smaller size, say uint16.

So, currently the channel identifier would have no reference to the 2 chains as you proposed above. We cannot reference the chain IDs since they are not guaranteed to be unique. We could reference the connectionID (connection{N}), if necessary (might be very unintuitive from a UI point of view).

On second thought, using the current global counter construction, I think using uint64 might be ideal since otherwise we open up for an attacker to use up all the possible channel identifiers.

This approach is a bit more flexible than either sending a particular id, and also has more permission control than allowing the other side just to select anything.

ChannelEnds don't need to agree on a particular id, they each have their own.

[andrey-kuprianov]

Re counter construction: I think uint64 provides too large preimage space, resulting in 1/ 2^33 ~ 1/ 8,5*10^9 probability of the address collision, which is too high to be neglected.

uint32 seems ideal to me: on the one hand, the probability of finding a collision via birthday attack is very little: 1 / 2^97 ~ 1 / 1,5 * 10^29; On the other hand the number of channels is 2^32 ~ 4 * 10^9, which will never be exhausted by any attacker, as only a few channels can be set up per second.

Besides, having only 4 * 10^9 possible escrow addresses makes is computationally easy to completely enumerate them all, and exclude the collision possibility completely.

EDIT: corrected the numbers above to use the right approximation formula: H+1 =~ 2*N + P where H is the bitwidth of the Hash image, N is the bitwidth of the number of guesses (i.e. 2^N guesses), and 1/2^P is the probability that after this number of guesses a collision will be found.
For H = 160, N = 64, we get p(N) =~ 1/2^33
For H = 160, N = 32, we get p(N) =~ 1/2^97

[andrey-kuprianov]

To summarize, my suggestion is as follows:

1. Fix the format as you proposed to:
   prefix: ibc-v1 (I do not think increasing the prefix length adds anything to security)
   port: transfer
   channel: channel{N} (starting from 0)
2. fix the counter to uint32: see the justification above
3. Use SHA256 as before, but exhaustively search the preimage space to exclude collisions completely.

The reason why I propose to keep SHA256 is that now its speed will be to our advantage, allowing to quickly enumerate preimages.

Hope that helps.

[andrey-kuprianov]

I would like to outline here a couple of further alternatives to the solution proposed above (let's call it Alternative 1).

Alternative 2: In case uint32 is too short, e.g. if uint64 is desired: excluding the collisions completely becomes infeasible for us due to high resource consumption (both time and memory), but finding the collision for a dedicated attacker would be still feasible. In that case the alternative recommendation is as follows:

1. Change the hashing function from fast SHA-256 to some slow one, e.g. include PublicKey computation into the pre-image.
2. Perform collision search with limited memory for some limited amount of time -- this will provide some probabilistic guarantees of collision absence.

Alternative 3: Implement protocol-level measures to prevent free choice of addresses by a potential attacker. This is more long-term; the goal here is to guarantee the absence of collisions by changing the protocols. One such protocol-level measure could be to implement window-based selection of channel ids as outlined in one of the messages above. E.g., when establishing a channel each party provides a window of local channel ids, (say [1-1000]), and the counterparty selects one id from that window. In that way we could actually leave the space of channel ids unrestricted, but whenever a channel is established provide a window that guarantees absence of collisions with any of existing escrow addresses: this will be easy and fast to do, because the windows will be in the order of e.g. bitwidth 10. At the same time, each party can prevent the other one from selecting a specific id, by choosing one from that window that guarantees absence of collisions also to the other party.

[andrey-kuprianov]

I would also like to point to the previous rather detailed cost analysis to attack truncated SHA256 performed previously in the context of Tendermint. This analysis is no less relevant today as it was back then.

[cwgoes]

@andrey-kuprianov Thank you so much for this detailed analysis! Alas, I am not a cryptographer either (seems we need one), but we'll have to make do ourselves for now - let me summarise my understanding and suggestions for moving forward.

Alternative 3: Implement protocol-level measures to prevent free choice of addresses by a potential attacker. This is more long-term; the goal here is to guarantee the absence of collisions by changing the protocols. One such protocol-level measure could be to implement window-based selection of channel ids as outlined in one of the messages above. E.g., when establishing a channel each party provides a window of local channel ids, (say [1-1000]), and the counterparty selects one id from that window. In that way we could actually leave the space of channel ids unrestricted, but whenever a channel is established provide a window that guarantees absence of collisions with any of existing escrow addresses: this will be easy and fast to do, because the windows will be in the order of e.g. bitwidth 10. At the same time, each party can prevent the other one from selecting a specific id, by choosing one from that window that guarantees absence of collisions also to the other party.

This is pretty interesting, but under our current time constraints I think it is too complicated. I'm also a little hesitant to rely on a dynamic negotiation protocol to avoid collisions (versus either enumerating or making them unlikely enough and sufficiently computationally difficult to brute force that the chance is negligible). At that point we should consider changing the SDK more fundamentally so that we can just avoid using a hash function altogether (which means a non-standard-length address).

Alternative 2: In case uint32 is too short, e.g. if uint64 is desired: excluding the collisions completely becomes infeasible for us due to high resource consumption (both time and memory), but finding the collision for a dedicated attacker would be still feasible. In that case the alternative recommendation is as follows:

1. Change the hashing function from fast SHA-256 to some slow one, e.g. include PublicKey computation into the pre-image.
2. Perform collision search with limited memory for some limited amount of time -- this will provide some probabilistic guarantees of collision absence.

If necessary we could do this.

However, I think uint32 is sufficient for the foreseeable future, so this strikes me as inferior to security- and complexity-wise Alternative 1.

To summarize, my suggestion is as follows:

1. Fix the format as you proposed to:
   prefix: ibc-v1 (I do not think increasing the prefix length adds anything to security)
   port: transfer
   channel: channel{N} (starting from 0)
2. fix the counter to uint32: see the justification above
3. Use SHA256 as before, but exhaustively search the preimage space to exclude collisions completely.

The reason why I propose to keep SHA256 is that now its speed will be to our advantage, allowing to quickly enumerate preimages.

Hope that helps.

This alternative (Alternative 1 as you enumerated them) makes most sense to me. In the current model I agree that changing the prefix length has no effect on collision resistance (for module accounts), the channel numbering scheme is already what was proposed, uint32 leaves 2^32 possible channels which is plenty for the foreseeable future (as users must pay gas fees to create them), and we can presumably write a quick script to search the preimage space and check that no collisions exist.

Do you happen to have such a script, or know of a fast SHA256 implementation? Should I just try to write one in Python or C?

I have one remaining question. In your case 1 above:

1. A collision between module accounts and non-module accounts. Assuming the module account address Addr, an attacker will need to find a ECDSA private key, such that for the corresponding public key PK its AddressHash(PK) == Addr.

It is true that this is not a collision between two arbitrary preimages, but the attacker can execute a slightly different strategy, I think. Even with enumerated channel identifiers, an attacker could first enumerate all of the SHA256 hashes of the channel addresses (assuming we pursue Alternative 1 as above), and then start searching the ECDSA public key space, checking for each generated AddressHash(PubKey) if it matched any channel address - of course, it might take the creation of many channels to reach the identifier matched, but it still is computationally less expensive. I think we probably don't need to be too concerned about this because creating millions of channels would be way too costly but I still wanted to mention it just to clarify the model here.

@colin-axner For now, we should pursue Alternative 1 - I think my last concern is probably not major.

[aaronc]

I want to point out that ADR 028 was not reviewed by any professional cryptographers. This was desired and even requested but it has not happened yet. I would like to improve the design if possible before it goes live.

[aaronc]

I wonder if for ADR 028 it would also help to increase addresses beyond the current 20 byte limit and/or add a prefix to the post-hash address instead of just the pre-image so that addresses for different purposes are strictly separated. When I initially addressed this issue, I had proposed 21 byte addresses, with the additional byte specifying the type of address (allowing up to 256 types per chain which seems reasonable).

[andrey-kuprianov]

@cwgoes thank you for the feedback!

At that point we should consider changing the SDK more fundamentally so that we can just avoid using a hash function altogether (which means a non-standard-length address).

yes, changing the address length and/or format is probably the best option in the long run. Looking at the speed of the parallelization and miniaturization happening now, I would say moving from 20-byte addresses to e.g. 32-byte addresses is bound to happen in the next decade.

Do you happen to have such a script, or know of a fast SHA256 implementation? Should I just try to write one in Python or C?

No, I don't have or know one yet, but can also write one in Rust for example, should be pretty easy. The only difficulty is that the required memory is around 200 GB, so some cloud machine e.g. AWS m5.16xlarge with 256GB is needed for that.

It is true that this is not a collision between two arbitrary preimages, but the attacker can execute a slightly different strategy, I think. Even with enumerated channel identifiers, an attacker could first enumerate all of the SHA256 hashes of the channel addresses (assuming we pursue Alternative 1 as above), and then start searching the ECDSA public key space, checking for each generated AddressHash(PubKey) if it matched any channel address

I was also thinking about this alternative. This can be analyzed approximately as follows (see A Generalized Birthday Attack, page 132 for asymptotics). For the standard case, we have the approximation formula: H+1 =~ 2*N + P where H is the bitwidth of the Hash image, N is the bitwidth of the number of guesses (i.e. 2^N guesses), and 1/2^P is the probability that after this number of guesses a collision will be found.

For the case you describe the approximation formula becomes H+1 =~ M + N + P, where M is the bitwidth of the preimage for the escrow addresses, and N is the bithwidth of the number of guesses of the public addresses. Thus, we have:

Alternative 1: H = 160, M = 32: P = 129 - N
Alternative 2: H = 160, M = 64: P = 97 - N

Thus, for Alternatives 1 and 2 this attack is equivalent to the standard collision search with a single address but with the post-image bitwidth of 129 bits or 97 bits respectively. I think actually both of those are still acceptable at present point, taking into account the slow ECDSA computation and that it won't be possible to store 2^64 addresses, but the first one is of course much more secure.

[cwgoes]

Right, makes sense. Thanks for the additional analysis - another reason to prefer Alternative 1 - sounds like we're in agreement.

[ebuchman]

Would it make sense to consider changing the hash function for module addressses in the short term to at least mitigate possible attacks from SHA2 asics?

[cwgoes]

Would it make sense to consider changing the hash function for module addressses in the short term to at least mitigate possible attacks from SHA2 asics?

Per my understanding of the discussion with @andrey-kuprianov we're just going to exhaustively search the module address space and ensure that there are no collisions.

[ValarDragon]

The problem faced in the original post has imo one underlying problem:
The lack of collision resistance on the address hashes.

Prefixing the inputs to hashes doesn't solve this. Address hashes should be 32 bytes, because many applications need collision resistant address hashes including this one! For instance, a contract model requires collision resistant address hashes for security, regardless of any domain separation you do.

As we want to allow for more applications that rely on addresses, I think we should default the ecosystem to using 32 bytes addresses.

Then domain separation of inputs is something thats great as a defense in depth, where collisions or pre-images can't be reused as widely.

32 byte addresses only introduce relatively minor bandwidth increases, that can easily be reduced with fancier solutions in the future. (e.g. for accounts, just only use the account-number to refer to the account)

[ValarDragon]

Re the second post from Andrey, we also absolutely have to ensure any data we encode to be hashed has a unique encoding, no way around that. We should probably write wrappers in the SDK to make this easier, since directly concatenating different points of user input allows to be used as a key for something allows that type of malleability attack, which repeatedly breaks security of systems.

Length prefixing each component, and then concatenating works in the general case, but if you're guaranteed that neither string can include a particular character, then you can prefix-separate as discussed in the posts above. IMO whatever is done here should ideally be standardized throughout the SDK

[ValarDragon]

On the choice of hash function discussions, I'm pretty opposed to changing the hash function to add latency into each execution step. The need for this is completely eliminated by removing the concern of collisions. (Increasing address size to 32 bytes. If we needed a slower hash function, we should be using a standard password hashing algorithm, not something thats homebrewed.

[aaronc]

Suggesting we continue the conversation in #5694 which originally attempted to address this.

[andrey-kuprianov]

@cwgoes I have checked for escrow address collisions for channel ids from uint32 -- as expected, there are none. There are a couple of lessons learned, that I would like to share here.

I have tested wrt. all prefixes proposed above + another prefix which is 260 bytes long -- so that it doesn't fit into a single 64-byte input block of SHA-256. The results for channel ids from uint16 and uint32 are summarized in the table below. Shown is the number of pairwise collisions if the post-image is truncated to the given number of bytes.

Preimage prefix + ChanId / N-byte collisions	1 byte	2 bytes	3 bytes	4 bytes	5 bytes	6 bytes	7 bytes	8 bytes
ics20-1, uint16	8418156	38093	115
ics20-1, uint32	36028799079179062	140739629121462	551890658046	2508421039	8397263	32786	132
ibc-v1, uint16	8422232	38070	122
ibc-v1, uint32	36028799590724528	140739620612778	551890871904	2508417561	8397562	32754	132
ibc-transfer-escrow-prefix, uint16	8426536	38188	146	1
ibc-transfer-escrow-prefix, uint32	36028799012808590	140739640215178	551890826238	2508564419	8396025	32920	145	1
10 * ibc-transfer-escrow-prefix, uint16	8422940	38548	133	2
10 * ibc-transfer-escrow-prefix, uint32	36028799072585034	140739657622266	551891382880	2508474595	8398864	32819	127	1

While originally I thought that a machine with 256 GB of memory is needed, after a bit of optimization I was able to conduct the uint32 tests on my low-power laptop with 16 GB of memory. Each of the uint32 tests required only 8 GB and around 3 hours to run, with the exception of the last one that lasted for 11 hours, which is expected due to the increased input size. I also know how to optimize further, so I could execute those both with less memory and time.

A few takeaways:

1. The birthday attack works as expected: N-byte input is enough to generate 2*N-byte output collisions. This means that for channel ids from uint64 the escrow addresses up to 16 bytes long are expected to collide. It's important to understand that this is only the probability, and it is a perfectly valid case when two outputs of whatever length actually collide. This is nicely demoed by the last two prefixes wrt. uint16, when the last one has fewer 3-byte collisions, but still 1 more 4-byte collisions.

2. There is no correlation of security with the length of the prefix -- all prefixes behave more or less the same, simply because SHA-256 is a good hashing function. Though longer prefixes on the table do have 8-byte collisions, while shorter ones do not, it is merely a coincidence. Also that the last prefix has 2 4-bytes collisions is because I have chosen it intentionally so: actually both 9* and 11* multiples have fewer.

3. While from the table there seem to be a correlation of behavior for small input spaces to the behavior on large input spaces, there is actually none. Knowing how a prefix behaves on uint32 will not let you know how it will behave for uint64.

4. It probably won't be possible to ever prove the absence of collisions for uint64 input space. The optimization I can think of now will require 4 GB of memory for uint32, but 18 exabytes of memory for uint64. I doubt that any further optimization is able to reduce this to anything manageable. At the same time, finding a collision will still be possible, because the attacker needs to be lucky and hit a single right pair, not to enumerate all of them.

I hope this confirms the right choice of uint32 as the input space for escrow addresses. Any further improvements to escrow address security require, I believe, changes to the address format, as discussed in #5694.

[cwgoes]

@andrey-kuprianov Thank you so much! Sounds like uint32 is indeed the right choice for the time being, and I expect it will last more than long enough for a more general approach (#5694) to be implemented.

[ValarDragon]

but 18 exabytes of memory for

btw, if you under double the computational cost, hash collision attacks take basically no memory. This is the parallel rho method of finding hash collisions, you can derive it with some slight modifications of https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms. See https://ieeexplore.ieee.org/abstract/document/8378028 for a paper on it.

[andrey-kuprianov]

@ValarDragon thanks for the references. You are right; in one of the earlier posts I have cited a similar algorithm already:

or even with constant memory

There are two points to consider though:

• Those are the algorithms that would help you to find collisions, not to prove their absence. That is, they are very helpful for an attacker, but for a defender they can provide only probabilistic guarantees.
• I believe the distinctive aspect of such algorithms is the ability to apply the function repeatedly, i.e. to compute chains x1 = f(x0), x2 = f(x1)... With the prefixed/structured input, like we have here, these algorithms will not work, as the output will be random and lack the necessary structure to go to the next iteration.