About the contract account, there are 3 subtasks that make up the bad account series. This article is the third task of the series, Orderless Hashing.
Analysis#
This task is similar to the previous one, with 2 contracts. The constructor of the account contract, GrandPharaoh, specifies a specific public key. The __validate__ function's get_multicall_hash calculates the hash recursively for each Call, and finally uses the XOR operation (^) to combine the hashes into a u256 hash. The product of low and high is the final messageHash. We need to construct the r and s values for the signature that can be verified by ECDSA.
The required Call is the RoyalSpear.equip(0) function from another contract, which can only be called by the account contract, GrandPharaoh.
Since we don't have the private key, we need to find vulnerabilities in ECDSA to crack it.
Process#
First, we need to see what the unordered multisignature calculation of the Calls list looks like. It can be [equip(0)], [equip(1),equip(0)], or more, as long as the last value is equip(0).
This part can be tested using snforge to write a test in cairo. Add (multicall_hash.low.into() * multicall_hash.high.into()).print(); in the account contract to read it.
It is obvious that [equip(0),equip(0)] corresponds to a hash of 0, which can be a starting point.
Next, delve into the check_ecdsa_signature function to see how the signature verification is performed.
Comment out use ecdsa::check_ecdsa_signature; and paste the source code into the test, so that you can add prints where necessary.
First, note that let zG: EcPoint = gen_point.mul(message_hash);, and since message_hash is 0 (infinity point), in elliptic curve, P*0=0, so zG is 0. If you check with the following code, it will output 'zG_x not exist' because the infinity point does not have an x-coordinate.
match zG.try_into() {
Option::Some(pt) => {
let (x, _) = ec::ec_point_unwrap(pt);
'zG_x'.print();
x.print();
},
Option::None => { 'zG_x not exist'.print(); },
};
The comment clearly states that the verification formula is (zG +/- rQ).x = sR.x, and the code for zG + rQ is:
match (zG + rQ).try_into() {
Option::Some(pt) => {
let (x, _) = ec::ec_point_unwrap(pt);
if (x == sR_x) {
return true;
}
},
Option::None => {},
};
Since zG is 0, we need rQ.x = sR.x, where r is the input signature.r, Q is the point on the curve corresponding to the public key, s is the input signature.s, and R is the point on the curve corresponding to r.
It is obvious that we only need r=s and Q=R to pass the verification. The public key can be found in the deployment transaction on the blockchain explorer.
Finally, use the same method as the previous task to use the invokeFunction in Starknet.js to pass the specific signature and calls to complete the task.
Summary#
If you have a deep understanding of ECDSA and know the operation rules of elliptic curves, this task is easy to solve. The design of the contract's multisignature is too simple and can be attacked using signature replay.
With this, all three tasks in the Account section are completed. I don't plan to do the task of writing a virtual machine in Cairo for the entire Cairo series, as I dislike algorithmic problems. In the future, I will update interesting things encountered in actual development on Starknet, so stay tuned.