SNaP Attack: Cracking Ethereum’s Synchronizing Node Random Generator

Massimiliano Taverna and Kenneth G. Paterson published "Snapping Snap Sync: Practical Attacks on Go Ethereum Synchronising Node", a paper uncovering flaws in Ethereum networks (only PoW chains, pre Merge) that could trick a node into syncing with a malicious chain, enabling an attacker to craft an arbitrary Ethereum state for economic gain. The duo have tested these attacks on a private Ethereum network, responsibly disclosed, and provided patches.

Their paper describes different attacks against Ethereum’s synchronization protocol, Snap Sync. In this post we'll focus on the SNaP attack. The authors have named this attack SNaP, an acronym for “Security: Not a Priority,” hinting at the trade-off that Ethereum developers made when prioritizing performance over security.

The attacker only needs a small fraction of the total mining power (around 1.6%) to carry out the attack. The authors emphasize that this is due to the insecure PRNG used by the Ethereum protocol for block validation during synchronization and not because of an inherent weakness in the Proof-of-Work (PoW) consensus mechanism itself.

In simple terms, here’s the essence of the attack:

1. Adversary Model: The authors assume that an attacker controls two nodes that can join the victim’s network, has a mining power equivalent to at least 1.6% of the total honest mining power, and the victim has not synced yet.
2. The Attack: The attacker predicts which blocks the victim node will effectively validate using a “prediction oracle” and mines only those blocks, thus saving computational effort. By doing this, the attacker can create a chain of blocks that is longer (heavier) than the honest chain, and despite being invalid, the victim will accept it. The victim will then consider this weak chain as canonical and operate on it until the honest chain outgrows the attacker’s chain in terms of total difficulty.
3. Exploiting Randomness: The attacker can predict the victim’s choices because the victim uses a predictable random number generator (PRNG) for block validation.
4. The Impact: Depending on the attacker’s relative mining power and the time available for the attack, they can make the victim operate on the invalid chain for a significant amount of time. For instance, if the attacker has 2% of the total mining power and carries out the attack over 24 hours, they can make the victim deviate from the honest chain for more than two days.

Recovering the PRNG Seed

The seed recovery is a critical part of the SNaP attack, as it allows the attacker to predict the victim’s random number generation sequence. The attacker can recover the seed used by the victim’s PRNG by learning bits of information from the victim and building a reverse lookup table.

The seed recovery process involves the following steps:

1. Information leakage: The attacker (A) generates a batch of blocks (prediction chain, G) in which only headers with an index >50 have a valid Proof of Work (PoW). The attacker then instructs the victim (V) to download this batch. During verification, the victim uses the PRNG to generate two random indices for the PoW validation. If the validation of the header at the first index fails (which happens with a 50% probability if the index is less than or equal to 50), the sync ends, and V sends a disconnection message to A. The message tells A whether the randomly chosen index was less than or equal to 50, leaking one bit of information about the victim’s PRNG output.
2. Learning multiple bits: The attacker needs more than one bit of information to recover the 31-bit seed of the victim’s PRNG. To achieve this, the attacker uses two nodes (M and W) to continually disconnect and reconnect with V, each time initiating a new sync and thus learning a new bit of information about the PRNG output. The attackers repeat this process until enough bits are collected to recover the seed.
3. Seed recovery: After enough iterations (γ), the attacker can construct a bitstring σ∗ that represents the leaked information about the PRNG outputs. A precomputed lookup table (µ) is used to map this bitstring back to the original seed (s*). This table is generated offline and is reused across multiple attacks. The minimum value for γ to avoid collisions in the prediction table is 62.
4. Prediction of PoW validations: After recovering the seed, the attacker starts a new sync with the victim, providing the real blockchain. At the same time, the attacker forks the blockchain and calculates how many calls to the PRNG the victim will make before reaching the fork. The attacker then creates a clone of the victim’s PRNG, initialized with the same seed and advanced by the calculated number of steps. This clone now perfectly predicts the random choices the victim will make during the PoW validations of the forked blockchain.

Part of this process can be analyzed in the following code:

https://github.com/massitaverna/malicious-go-ethereum/blob/1644add1553039c55f63e8e7f2f699b3ccf0e27f/attack/bridge/bridge.go#L401

The practicality of the seed recovery process is enhanced by the relatively low cost of mining the prediction chain, the reasonable computational resources required to build the lookup table, and the time-efficient process of learning the necessary 62 bits of information.

Prediction Table

The prediction table (or lookup table) is a data structure that maps the PRNG outputs (bitstrings) to their respective seeds. It’s a pre-computed table generated offline once and can be reused across multiple attacks.

The published attack code does not include the prediction table, instead a remote server is queried:

https://github.com/massitaverna/malicious-go-ethereum/blob/ghost-snap/attack/orchestrator/orchestrator.go#L450

The bitstring represents the PRNG outputs that have been leaked during the syncs with the victim. Each bit of the string corresponds to a single sync: it’s ‘0’ if the first randomly chosen index is greater than 50 and ‘1’ if it is less than or equal to 50. Therefore, the bitstring is a binary number of length γ, where γ is the number of syncs performed to learn enough information about the PRNG outputs.

Here’s a simple example:

Let’s say the attacker performed 3 syncs with the victim and learned that:

1. During the first sync, the first randomly chosen index was 75.
2. During the second sync, the first randomly chosen index was 45.
3. During the third sync, the first randomly chosen index was 88.

In this case, the bitstring would be ‘010’, as the first index was greater than 50 during the first sync (‘0’), less than or equal to 50 during the second sync (‘1’), and greater than or equal to 50 during the third sync (‘0’).

Once the attacker has collected enough bits (62 in the SNaP attack), they can use the prediction table to map this bitstring back to the original seed. For example, if the prediction table contains an entry that maps ‘010’ to the seed ‘12345’, the attacker would know that the seed of the victim’s PRNG is ‘12345’.

Conclusion

In conclusion, the discovery and exploration of the SNaP attack underscore the importance of robust and relentless scrutiny in crypto systems. It’s important to highlight a lesson from this research that extends beyond Ethereum and applies to all cryptographic systems: the critical role of a robust pseudorandom number generator (PRNG) cannot be overstated. Historically, we’ve seen that even the strongest of systems can be compromised by weaknesses in their PRNGs.

In the context of Ethereum, while the private key generation process might appear as the most critical area where random numbers are used, the reality is that various algorithms require PRNGs. No matter how seemingly inconsequential, each of these instances can become a potential weak link if not appropriately hardened.

At Coinspect, we understand this. Our team is experienced at uncovering and addressing these often-overlooked vulnerabilities, ensuring that every aspect of a crypto system, down to the most minute detail, is secure.

For more information on how we can help secure your systems, visit us at Coinspect.